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

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

История

Развитие теории помехоустойчивого кодирования во второй половине XX века было обусловлено потребностями космической связи, цифровых вычислительных машин и телекоммуникаций. В 1948 году Клод Шеннон заложил теоретические основы, показав возможность передачи информации с произвольно малой вероятностью ошибки при скоростях ниже пропускной способности канала. Однако практические схемы кодирования, способные приблизиться к этому пределу, требовали разработки эффективных алгоритмов.

В 1959 году французский математик Марсель Хоквингем опубликовал работу, в которой описал класс циклических кодов, исправляющих две и более ошибки. Почти одновременно, в 1960 году, американские исследователи Алексис Боуз и Д. К. Чоудхури представили независимый вывод тех же кодов. Впоследствии выяснилось, что все три автора пришли к одной и той же конструкции, получившей название кодов Боуза — Чоудхури — Хоквингема. Позднее, в 1960—1970-х годах, были разработаны эффективные алгоритмы декодирования, в том числе алгоритм Берлекэмпа — Месси (1969) и алгоритм Питерсона — Горенстейна — Цирлера, что сделало БЧХ-коды практичными для реализации в аппаратуре и программном обеспечении.

Математическое описание

БЧХ-коды являются подклассом циклических кодов. Для их описания используются понятия конечных полей (полей Галуа) и многочленов над этими полями.

Основные параметры

Любой БЧХ-код характеризуется тремя основными параметрами: длина кода \( n \), размерность (число информационных символов) \( k \) и минимальное расстояние \( d \). Обычно код обозначается как \( (n, k) \)-код. Для примитивных БЧХ-кодов длина равна \( n = 2^m - 1 \), где \( m \) — натуральное число (порядок поля Галуа). Непримитивные БЧХ-коды могут иметь длину, отличную от этого значения, но также делящую \( 2^m - 1 \).

Конструктивное расстояние \( d_0 \) — это нижняя граница минимального расстояния кода, задаваемая при проектировании. Гарантируется, что минимальное расстояние кода \( d \ge d_0 \). Если \( d_0 = 2t + 1 \), то код гарантированно исправляет любые \( t \) ошибок.

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

БЧХ-код задаётся своим порождающим многочленом \( g(x) \) степени \( n - k \). Этот многочлен является наименьшим общим кратным минимальных многочленов элементов поля Галуа, являющихся корнями порождающего многочлена. В частности, для кода с конструктивным расстоянием \( d_0 \) порождающий многочлен должен иметь своими корнями последовательные степени примитивного элемента поля: \( \alpha, \alpha^2, \dots, \alpha^{d_0-1} \). Если среди них есть сопряжённые элементы, соответствующие минимальные многочлены совпадают, что уменьшает степень порождающего многочлена.

Кодирование

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

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

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

1. Вычисление синдрома. По принятому слову \( r(x) \) вычисляются значения синдрома \( S_j = r(\alpha^j) \) для \( j = 1, 2, \dots, 2t \). Если все синдромы равны нулю, считается, что ошибок нет.
2. Определение многочлена локаторов ошибок. На основе синдромов строится многочлен \( \Lambda(x) \), корни которого обратны позициям ошибок. Для этого используется алгоритм Берлекэмпа — Месси или алгоритм Питерсона — Горенстейна — Цирлера (для малого числа ошибок).
3. Поиск корней многочлена локаторов. Корни \( \Lambda(x) \) находятся методом перебора по Ченю (Chien search) — подстановкой всех возможных значений поля.
4. Вычисление значений ошибок. Для кодов, исправляющих только ошибки (бинарные БЧХ-коды), значение ошибки равно 1 (или соответствующему элементу поля). Для небинарных кодов (например, Рида — Соломона) значения ошибок вычисляются с помощью алгоритма Форни.

Алгоритм Берлекэмпа — Месси

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

Алгоритм Питерсона — Горенстейна — Цирлера

Этот прямой метод основан на решении системы линейных уравнений для нахождения коэффициентов многочлена локаторов ошибок. Он прост для понимания, но вычислительно сложен при большом числе исправляемых ошибок (требует обращения матрицы размера \( t \times t \)).

Разновидности

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

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

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

Применение

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

• Системы хранения данных: используются в жёстких дисках (HDD), твердотельных накопителях (SSD), оптических дисках (CD, DVD, Blu-ray) для защиты от сбоев чтения/записи. В частности, в CD применяется код Рида — Соломона (частный случай небинарного БЧХ-кода) с перекрестным перемежением (CIRC).
• Цифровая связь: применяются в спутниковой связи, системах сотовой связи (например, в стандарте GSM для кодирования канала управления), в системах цифрового телевидения (DVB).
• Космическая связь: используются в телеметрии и передаче данных с космических аппаратов (например, в программе «Вояджер» использовались коды Рида — Соломона).
• Криптография: на основе БЧХ-кодов построена криптосистема Мак-Элиса (McEliece cryptosystem), которая является одной из перспективных постквантовых криптосистем.

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

БЧХ-коды являются обобщением кодов Хэмминга (коды Хэмминга — это частный случай БЧХ-кодов с конструктивным расстоянием \( d_0 = 3 \)). Коды Рида — Соломона (RS-коды) являются подклассом небинарных БЧХ-кодов, у которых длина кода равна размеру поля минус один (\( n = q - 1 \)), и корни порождающего многочлена — последовательные степени примитивного элемента поля. RS-коды широко применяются в системах хранения данных и цифрового телевидения.

Достоинства и недостатки

Достоинства:

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

Недостатки:

• При малых длинах кода могут уступать по эффективности некоторым другим классам кодов (например, свёрточным или LDPC-кодам).
• Алгоритмы декодирования сложнее, чем для кодов Хэмминга.
• Для небинарных БЧХ-кодов (Рида — Соломона) требуется больше вычислительных ресурсов.

Источники

• Хоквингем, М. (1959). «Коды, исправляющие ошибки». IRE Transactions on Information Theory.
• Боуз, Р. К., Чоудхури, Д. К. (1960). «Класс двоичных кодов, исправляющих ошибки». Information and Control.
• Питерсон, У. У., Уэлдон, Э. Дж. (1972). Коды, исправляющие ошибки. М.: Мир.
• Блейхут, Р. (1986). Теория и практика кодов, контролирующих ошибки. М.: Мир.
• Берлекэмп, Э. Р. (1968). Алгебраическая теория кодирования. McGraw-Hill.
• Мак-Вильямс, Ф. Дж., Слоан, Н. Дж. А. (1977). Теория кодов, исправляющих ошибки. North-Holland.