Код БЧХ: построение и исправление ошибок

Код БЧХ - семейство помехоустойчивых кодов, которые добавляют к данным избыточность и позволяют восстановить повреждённые биты. Название составлено из первых букв фамилий Боуза, Чоудхури и Хоквингема. Ключевая идея состоит в выборе многочлена, корни которого образуют последовательность элементов конечного поля: благодаря этому можно гарантировать нужное расстояние между кодовыми словами. На примере двоичного кода длины 15 проследим путь от сообщения до синдрома и исправления. В калькуляторе меняйте сообщение и число ошибок, чтобы сравнить переданное и принятое слова.
Что защищает код БЧХ
При передаче или хранении отдельный бит может измениться с нуля на единицу или наоборот. Если отправить исходные данные без проверки, получатель не узнает, что значение изменилось. Кодирование заранее ограничивает множество допустимых последовательностей: передаются только специальные кодовые слова, разделённые достаточным расстоянием. Получив близкую к одному из них последовательность, декодер может предположить, какое слово отправили.
Это исправление ошибок канала, а не шифрование: избыточность помогает надёжно восстановить данные, но не скрывает их от постороннего. Код БЧХ относится к блоковым циклическим кодам. Он обрабатывает данные блоками, а циклический сдвиг кодового слова снова даёт кодовое слово. Другой подход к построению помехоустойчивых блоков рассмотрен в статье про код Рида - Маллера.
Параметры и расстояние
Запись задаёт длину кодового слова , число информационных битов и минимальное расстояние Хэмминга между разными кодовыми словами. Расстояние равно числу позиций, в которых слова различаются. Например, между 00110 и 01100 оно равно двум.
Рассмотрим двоичный код БЧХ . Он отображает 7 бит сообщения в 15 бит кодового слова; оставшиеся 8 позиций в систематической записи занимают проверочные биты. Его скорость равна : больше избыточности означает меньшую долю данных в передаваемом блоке, но создаёт пространство для исправления повреждений.
Гарантированное число исправляемых ошибок определяется формулой
При получаем . Области радиуса два вокруг разных слов не пересекаются: иначе два кодовых слова могли бы различаться не более чем в четырёх позициях. Если требуется только обнаружение без исправления, код обнаруживает до четырёх ошибок. Эти гарантии относятся к любому расположению ошибок в блоке; при большем числе ошибок они уже не действуют.
Полезно отличать минимальное расстояние конкретного кода от проектного расстояния . Конструкция БЧХ обеспечивает оценку , но фактическое расстояние иногда больше. В нашем примере оба равны пяти: это можно проверить перебором 127 ненулевых кодовых слов. Для линейного кода минимум их весов равен минимальному расстоянию.
Как строят порождающий многочлен
Битовую последовательность удобно записывать как многочлен над : коэффициенты равны нулю или единице, а сложение коэффициентов выполняется через XOR. Так, 1011 означает . При арифметике по модулю два вычитание совпадает со сложением: .
Для выбранного примера возьмём расширение и элемент , для которого . Это поле строится по неприводимому многочлену ; элемент имеет порядок 15. Для узкосмыслового БЧХ с в качестве корней порождающего многочлена задают . Над двоичным полем их минимальные многочлены повторяются попарно: достаточно взять наименьшее общее кратное двух разных многочленов:
Степень равна восьми, поэтому . Всякое кодовое слово делится на без остатка. Порождающий многочлен этого примера и параметры приведены в документации библиотеки конечных полей galois; общий способ через НОК минимальных многочленов описан в документации MathWorks.
Пример систематического кодирования
Пусть сообщение равно 0000001, то есть . Сначала сдвигаем его на восемь позиций: . Затем делим на по модулю два. Частное равно единице, а остаток равен
Прибавляем остаток к сдвинутому сообщению: . Получается слово 000000111010001: семь первых битов повторяют сообщение, восемь последних содержат остаток. Именно это слово показывает калькулятор при исходном положении ползунка. Для другого сообщения остаток рассчитывается заново; просто присоединить фиксированные восемь битов нельзя.
Такая запись помогает проверить результат: деление полученного на должно дать ноль. При этом деление ведётся над , а не по обычным правилам целочисленной арифметики. Порядок битов тоже важен: здесь старшая степень находится слева, а позиция ноль - крайний правый бит.
Синдром и исправление двух ошибок
Предположим, что при передаче изменились биты в позициях 1 и 4 справа. Многочлен ошибки равен , а принятое слово равно : 000000111000011. Остаток от деления на называется здесь синдромом. Поскольку делится на , синдром равен остатку ошибки и в этом случае составляет 00010010.

Для короткого учебного кода можно заранее составить таблицу синдромов: включить маску без ошибок, 15 масок с одной ошибкой и масок с двумя. Всего получается 121 разный синдром. По синдрому 00010010 таблица выбирает маску ; повторный XOR с принятым словом возвращает исходное кодовое слово. Калькулятор использует именно такой поиск.
Почему совпадение синдромов в этой таблице исключено? Пусть две разные маски, каждая не тяжелее двух ошибок, дают одинаковый остаток. Их сумма по XOR тогда делится на и является ненулевым кодовым словом. Но в этой сумме было бы не более четырёх единиц, что противоречит минимальному расстоянию пять. Поэтому внутри гарантированного радиуса таблица однозначно определяет маску, независимо от того, какое сообщение было передано.
Проверим это на практике по шагам. Получатель не знает отправленного слова и не сравнивает его с исходным, как это делает учебный рисунок. Он вычисляет остаток принятого блока, ищет соответствующую маску в таблице и меняет найденные позиции. После этого он ещё раз проверяет делимость результата на и извлекает первые семь битов систематической записи. Повторная проверка показывает принадлежность результата к коду, но не доказывает, что ошибок было не больше двух.
Для более длинных БЧХ-кодов полная таблица быстро растёт. На практике используют алгебраическое декодирование: вычисляют значения принятого многочлена в заданных корнях поля, находят многочлен локаторов ошибок, затем его корни указывают позиции повреждений. В лекционных материалах MIT разобрана связь синдромов с поиском нескольких ошибок. Словом «синдром» называют как набор таких значений, так и остаток от деления: это связанные, но по-разному записанные представления проверки.
Что происходит за пределом гарантии
При трёх ошибках декодер с радиусом два может не найти подходящего слова и сообщить об отказе. Но возможна и ложная коррекция: принятое слово оказывается в пределах двух изменений от другого кодового слова. Тогда проверка исправленного результата даст нулевой остаток, хотя восстановлены не отправленные данные. В калькуляторе третий переключаемый бит находится в позиции 9; попробуйте этот режим и сравните результат с исходным словом.
Даже нулевой синдром принятого слова сам по себе не доказывает отсутствие повреждений: ошибки могут превратить одно допустимое слово в другое. Дополнительная проверка целостности и повторная передача зависят от устройства всей системы. БЧХ также не восстанавливает стёртые или изменённые данные сверх выбранной модели автоматически: свойства зависят от конкретного декодера и того, известны ли позиции стираний.
Помехоустойчивость связана с ценой передачи избыточных битов. Для общей картины полезно различать её и количество информации по Шеннону: БЧХ описывает конкретную конструкцию кода, а информационная мера отвечает на другой вопрос. Аналогично, равномерное и неравномерное кодирование сравнивает длины представлений символов, а не обязательно исправление ошибок. Сами последовательности битов могут представлять текст, например через ASCII, до добавления защитного кода.
Частые ошибки
- Путать и число проверочных битов. В примере , а проверочных позиций восемь.
- Считать проектное расстояние точным для любого БЧХ. Оно задаёт нижнюю границу; точное значение нужно доказывать отдельно.
- Обещать исправление четырёх ошибок. Расстояние пять гарантирует обнаружение до четырёх или исправление до двух при соответствующей задаче.
- Считать любой нулевой синдром доказательством верной передачи. Повреждение может привести к другому кодовому слову.
- Забывать порядок битов и поле. Здесь степени убывают слева направо, сложение - XOR.
FAQ
Чем БЧХ отличается от кода Хэмминга? Код Хэмминга исправляет одну ошибку в стандартной конструкции; подход БЧХ позволяет строить семейства с заданной гарантией исправления нескольких ошибок. Некоторые коды Хэмминга можно получить как частный случай БЧХ.
Всегда ли число проверочных битов равно ? Нет. Для примитивного двоичного БЧХ длины это полезная верхняя оценка числа проверочных битов при обычной конструкции с исправлением ошибок, но степени минимальных многочленов могут перекрываться.
Зачем декодеру известен порождающий многочлен? Он определяет допустимые слова и проверочные условия. Отправитель и получатель должны использовать согласованные параметры, включая порядок битов и конкретный многочлен.
Коротко
Код БЧХ строит блоковый код через последовательные корни в конечном поле. В примере семь информационных битов превращаются в 15-битное слово, а расстояние пять гарантирует исправление двух ошибок. Синдром помогает найти их положение, но за пределом этой гарантии декодер может отказать или восстановить другое слово.
Читайте также

LDPC-коды: проверки чётности и исправление ошибок
LDPC-коды простыми словами: разреженная матрица проверок, граф Таннера и итеративное декодирование. Разбираем синдром и одиночную ошибку на числовом примере.

Код Хэмминга: исправление ошибок на примере
Код Хэмминга для исправления ошибок: как расставить проверочные биты, вычислить синдром и восстановить данные на примере кода (7, 4), а также каковы его ограничения.

Код Рида-Маллера: параметры, построение и декодирование
Код Рида-Маллера простыми словами: как считать длину, размерность и кодовое расстояние RM(r, m), рекурсивное построение u, u+v и мажоритарное декодирование с примерами и калькулятором.

Абсолютно неупругий удар: сохранение импульса
Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

АЦП последовательного приближения: схема и принцип работы
Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.