Код БЧХ

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

История

Коды БЧХ были независимо разработаны в 1959—1960 годах французским математиком Алексисом Хоквингемом и американскими учёными Раджем Чандра Боузом и Двиджендра Кумар Рай-Чоудхури. Первоначально работы Хоквингема были опубликованы в 1959 году, а статья Боуза и Рай-Чоудхури вышла в 1960 году. Название кода образовано по первым буквам фамилий авторов (Bose — Chaudhuri — Hocquenghem). В русскоязычной литературе часто используется аббревиатура БЧХ.

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

Определение

Код БЧХ над конечным полем \( GF(q) \) (где \( q \) — степень простого числа) длины \( n \) с конструктивным расстоянием \( d \) определяется как циклический код, порождающий многочлен которого является наименьшим общим кратным минимальных многочленов элементов \( \alpha^b, \alpha^{b+1}, \ldots, \alpha^{b+d-2} \) из расширения поля \( GF(q^m) \), где \( \alpha \) — примитивный элемент поля \( GF(q^m) \), а \( m \) — порядок поля расширения.

Наиболее распространены двоичные коды БЧХ (\( q = 2 \)). Для них параметры кода обычно задаются как \( (n, k, t) \), где:

• \( n \) — длина кода (количество символов в кодовом слове);
• \( k \) — размерность кода (количество информационных символов);
• \( t \) — максимальное количество ошибок, которое код гарантированно исправляет.

Конструктивное расстояние \( d \) связано с \( t \) соотношением \( d \ge 2t + 1 \). Фактическое минимальное расстояние кода может быть больше конструктивного.

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

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

• Примитивные коды БЧХ — коды с длиной \( n = q^m - 1 \). Для двоичного случая \( n = 2^m - 1 \). Такие коды являются наиболее изученными и часто используемыми.
• Непримитивные коды БЧХ — коды, длина которых является делителем \( q^m - 1 \), но не равна ему. Они строятся с использованием элементов, порядок которых меньше \( q^m - 1 \).

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

Устройство и характеристики

Порождающий многочлен

Порождающий многочлен \( g(x) \) кода БЧХ вычисляется как произведение минимальных многочленов \( m_i(x) \) для последовательных степеней примитивного элемента: \[ g(x) = \text{НОК}\{ m_b(x), m_{b+1}(x), \ldots, m_{b+d-2}(x) \}. \] Степень порождающего многочлена равна \( n - k \). Для двоичных кодов БЧХ часто выбирают \( b = 1 \), что упрощает вычисления.

Минимальное расстояние

Минимальное расстояние \( d_{\min} \) кода БЧХ не меньше конструктивного расстояния \( d \). Для многих кодов БЧХ \( d_{\min} = d \), но существуют случаи, когда фактическое расстояние больше. Например, для двоичного кода (15, 7, 5) конструктивное расстояние равно 5, и код исправляет до 2 ошибок.

Параметры

Наиболее известные двоичные коды БЧХ:

• (7, 4, 1) — код Хэмминга, исправляет одну ошибку.
• (15, 11, 1) — код Хэмминга, исправляет одну ошибку.
• (15, 7, 2) — исправляет до двух ошибок.
• (31, 26, 1) — код Хэмминга.
• (31, 21, 2) — исправляет до двух ошибок.
• (31, 16, 3) — исправляет до трёх ошибок.
• (63, 57, 1) — код Хэмминга.
• (63, 51, 2) — исправляет до двух ошибок.
• (63, 45, 3) — исправляет до трёх ошибок.
• (63, 39, 4) — исправляет до четырёх ошибок.
• (63, 36, 5) — исправляет до пяти ошибок.

Скорость кода

Скорость кода \( R = k/n \) определяет долю информационных символов в кодовом слове. Для кодов БЧХ скорость уменьшается с ростом \( t \). Например, код (63, 57, 1) имеет скорость 0,905, а код (63, 36, 5) — 0,571.

Кодирование

Кодирование для кодов БЧХ выполняется так же, как для любого циклического кода. Информационный многочлен \( u(x) \) степени не выше \( k-1 \) умножается на \( x^{n-k} \), затем делится на порождающий многочлен \( g(x) \). Остаток от деления \( r(x) \) является проверочной частью, а кодовое слово \( c(x) \) имеет вид: \[ c(x) = u(x) \cdot x^{n-k} + r(x). \] Кодирование может быть реализовано с помощью линейных регистров сдвига с обратными связями.

Декодирование

Декодирование кодов БЧХ является более сложным, чем кодирование, и включает несколько этапов:

1. Вычисление синдрома — для принятого слова \( v(x) \) вычисляются значения синдрома \( S_j = v(\alpha^j) \) для \( j = b, b+1, \ldots, b+d-2 \).
2. Построение многочлена локаторов ошибок — по синдромам находится многочлен \( \sigma(x) \), корни которого указывают на позиции ошибок. Для этого используется алгоритм Берлекэмпа — Месси или алгоритм Петерсона — Горенстейна — Цирлера (для малых \( t \)).
3. Поиск корней — корни многочлена \( \sigma(x) \) находятся методом перебора (алгоритм Ченя) или с помощью преобразования Фурье.
4. Вычисление значений ошибок — для недвоичных кодов (например, кодов Рида — Соломона) требуется определить амплитуду ошибки. Для двоичных кодов значения ошибок равны 1, и достаточно инвертировать биты в найденных позициях.

Алгоритм Берлекэмпа — Месси является наиболее эффективным для декодирования кодов БЧХ с большим \( t \). Его сложность составляет \( O(t^2) \) операций в поле.

Применение

Коды БЧХ нашли широкое применение в различных областях:

• Системы связи — используются в спутниковой связи, цифровом телевидении (стандарты DVB), модемах и системах передачи данных.
• Хранение данных — применяются в жёстких дисках, твердотельных накопителях (SSD), оптических дисках (CD, DVD, Blu-ray) и флеш-памяти. Например, в технологии NAND-флеш используются коды БЧХ для коррекции ошибок, возникающих из-за износа ячеек.
• Компьютерные сети — входят в состав протоколов передачи данных, таких как Wi-Fi (стандарт IEEE 802.11) и Ethernet.
• Криптография — коды БЧХ используются в некоторых криптосистемах, например, в криптосистеме Мак-Элиса, основанной на сложности декодирования линейных кодов.
• Космическая связь — применялись в программах NASA и ESA для передачи данных с космических аппаратов.

Пример

Рассмотрим двоичный код БЧХ (15, 7, 2). Длина кода \( n = 15 \), количество информационных символов \( k = 7 \), код исправляет до 2 ошибок. Порождающий многочлен для этого кода равен: \[ g(x) = x^8 + x^7 + x^6 + x^4 + 1. \] Степень многочлена равна 8, что соответствует \( n - k = 8 \). Код может быть использован для защиты данных от одиночных и двойных ошибок в каналах с умеренным уровнем шума.

Сравнение с другими кодами

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

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

• Коды БЧХ являются частным случаем кодов Рида — Соломона, если рассматривать последние как недвоичные коды БЧХ с конструктивным расстоянием, равным длине кода.
• В 1960-х годах коды БЧХ использовались в системе связи «Вояджер» для передачи изображений планет Солнечной системы.
• Алгоритм Берлекэмпа — Месси, используемый для декодирования, также применяется в криптоанализе и теории управления.

Источники

• Боуз Р. Ч., Рай-Чоудхури Д. К. Класс двоичных кодов, исправляющих ошибки // Bell System Technical Journal. — 1960. — Т. 39, № 3. — С. 565—593.
• Хоквингем А. Коды, исправляющие ошибки // Philips Research Reports. — 1959. — Т. 14. — С. 399—407.
• Берлекэмп Э. Р. Алгебраическая теория кодирования. — М.: Мир, 1971. — 480 с.
• Мак-Вильямс Ф. Дж., Слоан Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979. — 744 с.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — 594 с.