Код Боуза — Чоудхури — Хоквингема

Код Боуза — Чоудхури — Хоквингема (БЧХ-код) — это класс циклических помехоустойчивых кодов, используемых для обнаружения и исправления ошибок при передаче и хранении цифровых данных. Относится к семейству блоковых кодов с гарантированной корректирующей способностью, которая задаётся при проектировании. БЧХ-коды являются обобщением кодов Хэмминга на случай исправления двух и более ошибок и широко применяются в системах связи, компьютерной памяти и устройствах хранения данных.

История

БЧХ-коды были независимо разработаны в 1959—1960 годах тремя учёными: французским математиком Алексисом Боузом, индийским учёным Д. К. Чоудхури и американским инженером Славеном Хоквингемом. Первая публикация Боуза и Чоудхури вышла в 1960 году, а Хоквингем опубликовал свою работу чуть позже, в том же году. Код был назван в честь всех трёх авторов.

Первоначально БЧХ-коды были разработаны для двоичных каналов связи, но впоследствии были обобщены на недвоичные алфавиты (например, коды Рида — Соломона). В 1960-е годы они стали основой для многих систем передачи данных, включая спутниковую связь и первые компьютерные сети. К настоящему времени БЧХ-коды остаются одними из наиболее изученных и практически используемых помехоустойчивых кодов.

Основные характеристики

БЧХ-коды являются циклическими кодами, то есть любое циклическое смещение кодового слова также является кодовым словом. Это свойство упрощает реализацию кодирования и декодирования с помощью сдвиговых регистров.

Основные параметры БЧХ-кода:

• n — длина кодового слова (количество символов в блоке);
• k — количество информационных символов;
• d — минимальное кодовое расстояние (минимальное количество позиций, в которых различаются два любых кодовых слова);
• t — максимальное количество ошибок, которое код гарантированно исправляет. Связь между d и t: d ≥ 2t + 1.

Для двоичных БЧХ-кодов длина n обычно выбирается как n = 2^m − 1, где m — целое число (m ≥ 3). Например, при m = 3 длина n = 7, при m = 4 длина n = 15, при m = 5 длина n = 31 и так далее. Такие коды называются примитивными. Существуют также непримитивные БЧХ-коды, длина которых является делителем 2^m − 1.

Корректирующая способность t задаётся при проектировании. Чем больше t, тем меньше информационная скорость R = k/n, так как больше избыточных символов добавляется для защиты.

Принцип построения

БЧХ-коды строятся на основе теории конечных полей (полей Галуа). Кодовые слова представляются в виде многочленов над полем GF(2) (для двоичных кодов) или над GF(q) для недвоичных. Порождающий многочлен g(x) кода выбирается так, чтобы его корнями были последовательные степени примитивного элемента α поля GF(2^m). Если требуется исправлять t ошибок, то корнями g(x) должны быть α, α^2, α^3, ..., α^(2t). Это гарантирует, что минимальное кодовое расстояние d ≥ 2t + 1.

Процесс кодирования заключается в умножении информационного многочлена на g(x). Декодирование выполняется с использованием алгоритмов, основанных на вычислении синдромов и решении систем уравнений (например, алгоритм Берлекэмпа — Месси или алгоритм Питерсона — Горенстейна — Цирлера).

Классификация

БЧХ-коды делятся на два основных типа:

Двоичные БЧХ-коды

Используют двоичный алфавит (символы 0 и 1). Наиболее распространённый класс. Примеры:

• Код (7, 4) с t = 1 — эквивалентен коду Хэмминга (7, 4).
• Код (15, 7) с t = 2.
• Код (31, 16) с t = 3.
• Код (63, 51) с t = 2.

Недвоичные БЧХ-коды

Используют символы из поля GF(q), где q > 2. Наиболее известный подкласс — коды Рида — Соломона (РС-коды), которые являются частным случаем БЧХ-кодов с m = 1. РС-коды широко применяются в системах хранения данных (CD, DVD, RAID), цифровом телевидении и спутниковой связи.

Применение

БЧХ-коды используются в различных областях, где требуется надёжная передача или хранение информации:

• Спутниковая и космическая связь — для защиты данных от помех при передаче на большие расстояния.
• Системы хранения данных — в некоторых типах RAID-массивов и флеш-памяти (NAND) для исправления ошибок, вызванных износом ячеек.
• Цифровое телевидение — в стандартах DVB-T, DVB-S и других для коррекции ошибок в транспортном потоке.
• Мобильная связь — в ранних стандартах (например, GSM) для защиты служебных каналов.
• Компьютерные сети — в некоторых протоколах передачи данных, например, в беспроводных сетях Wi-Fi (стандарт IEEE 802.11) для коррекции ошибок в пакетах.
• Криптография — в некоторых схемах аутентификации и кодах аутентификации сообщений (MAC) на основе БЧХ-кодов.

Примеры

Пример 1: Код (7, 4) с исправлением одной ошибки

• Длина n = 7, информационных символов k = 4, t = 1.
• Порождающий многочлен: g(x) = x^3 + x + 1.
• Кодовые слова: 16 слов длиной 7 бит. Любые два слова отличаются минимум в 3 позициях (d = 3).
• Исправляет одну ошибку в блоке из 7 бит.

Пример 2: Код (15, 7) с исправлением двух ошибок

• Длина n = 15, информационных символов k = 7, t = 2.
• Порождающий многочлен: g(x) = x^8 + x^7 + x^6 + x^4 + 1.
• Минимальное кодовое расстояние d ≥ 5.
• Исправляет две ошибки в блоке из 15 бит.

Преимущества и недостатки

Преимущества

• Гарантированная корректирующая способность, задаваемая при проектировании.
• Эффективные алгоритмы декодирования (полиномиальная сложность).
• Возможность построения кодов с различной длиной и скоростью.
• Хорошая совместимость с аппаратной реализацией на сдвиговых регистрах.

Недостатки

• При большом t и длине n сложность декодирования возрастает (хотя остаётся полиномиальной).
• Для некоторых значений параметров не существует БЧХ-кодов с оптимальными характеристиками (например, не всегда достигается граница Синглтона).
• Декодирование с мягкими решениями (soft-decision) сложнее, чем для некоторых других кодов (например, LDPC).

Связь с другими кодами

• Коды Хэмминга — частный случай БЧХ-кодов с t = 1.
• Коды Рида — Соломона — недвоичные БЧХ-коды с m = 1.
• Коды Гоппы — обобщение БЧХ-кодов на основе алгебраических кривых.
• Коды LDPC и турбокоды — более современные классы, обеспечивающие лучшую производительность при больших длинах, но с более сложным декодированием.

Интересные факты

• БЧХ-коды являются одними из первых классов кодов, для которых была строго доказана возможность исправления заданного числа ошибок.
• Алгоритм Берлекэмпа — Месси, используемый для декодирования БЧХ-кодов, был разработан в 1968—1969 годах и до сих пор остаётся стандартным методом.
• В космической программе «Вояджер» (США) использовались коды Рида — Соломона (частный случай БЧХ-кодов) для передачи изображений с планет-гигантов.
• В стандарте цифрового телевидения DVB-T2 для коррекции ошибок применяются LDPC-коды, но в сочетании с БЧХ-кодами в качестве внешнего кода (каскадная схема).

Источники

1. Bose, R. C., & Ray-Chaudhuri, D. K. (1960). On a class of error correcting binary group codes. Information and Control, 3(1), 68–79.
2. Hocquenghem, A. (1959). Codes correcteurs d'erreurs. Chiffres, 2, 147–156.
3. Peterson, W. W., & Weldon, E. J. (1972). Error-Correcting Codes (2nd ed.). MIT Press.
4. MacWilliams, F. J., & Sloane, N. J. A. (1977). The Theory of Error-Correcting Codes. North-Holland.
5. Блейхут, Р. (1986). Теория и практика кодов, контролирующих ошибки. Мир.
6. Proakis, J. G., & Salehi, M. (2008). Digital Communications (5th ed.). McGraw-Hill.