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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формальное описание[править | править вики-текст]

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


Пусть  — примитивный элемент поля (то есть ), пусть , — элемент поля порядка . Тогда нормированный полином минимальной степени над полем , корнями которого являются подряд идущих степеней элемента для некоторого целого (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем с длиной и минимальный расстоянием . Поясним почему у получившегося кода будут именно такие характеристики (длина кода , минимальное расстояние ). Действительно, как показано у Сагаловича[1], длина БЧХ кода равна порядку элемента , если и равна порядку элемента , если , тогда, так как случай нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента ,то есть равна . Минимальное расстояние может быть больше , когда корнями минимальных функций[2] от элементов будут элементы расширяющие последовательность, то есть элементы .


Число проверочных символов равно степени , число информационных символов , величина называется конструктивным расстоянием БЧХ-кода. Если , то код называется примитивным, иначе непримитивным.

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

Построение[править | править вики-текст]

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

  • выбрать , то есть поле , над которым будет построен код;
  • выбрать длину кода из условия , где  — целые положительные числа;
  • задать величину конструктивного расстояния;

1) построить циклотомические классы элемента поля над полем , где  — примитивный элемент ;

2) поскольку каждому такому циклотомическому классу соответствует неприводимый полином над , корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать таким образом, чтобы суммарная длина циклотомических классов была минимальна; это делается для того, чтобы при заданных характеристиках кода и минимизировать количество проверочных символов ;

3) вычислить порождающий полином , где  — полином, соответствующий -ому циклотомическому классу; или вычислить , как НОК минимальных функций от элементов [3].

Примеры кодов[править | править вики-текст]

Примитивный двоичный (15, 7, 5) код[править | править вики-текст]

Пусть , требуемая длина кода и минимальное расстояние . Возьмем  — примитивный элемент поля , и  — четыре подряд идущих степеней элемента . Они принадлежат двум циклотомическим классам над полем , которым соответствуют неприводимые полиномы и . Тогда полином

имеет в качестве корней элементы и является порождающим полиномом БЧХ-кода с параметрами .

16-ричный (15, 11, 5) код (код Рида — Соломона)[править | править вики-текст]

Пусть и  — примитивный элемент . Тогда

Каждый элемент поля можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60 = 15 × 4 битам, таким образом набору из 44 бит ставится в соответствие набор из 60 бит. Можно сказать, что такой код работает с полубайтами информации.

Кодирование[править | править вики-текст]

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

Методы декодирования[править | править вики-текст]

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

Главной идеей в декодировании БЧХ кодов является использование элементов конечного поля для нумерации позиций кодового слова(или, эквивалентно, в порядке коэффициентов ассоциированного многочлена). Ниже приведена такая нумерация для вектора , соответствующего многочлену .

значения
локаторы позиций

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

Синдромы определены как значения принятого полинома в нулях порождающего многочлена кода:

       
       
       
              

Здесь Для нахождения множества локаторов ошибок, введем в рассмотрение многочлен локаторов ошибок

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами[5]:

    
    
     
    

Известны следующие методы для решения этой системы уравнений относительно коэффициентов многочлена локаторов ошибок (ключевая система уравнений).

  • Алгоритм Берлекемпа — Мэсси (BMA)[⇨]. По числу операций в конечном поле этот алгоритм обладает высокой эффективностью. BMA обычно используется для программной реализации или моделирования кодов БЧХ и кодов Рида — Соломона.
  • Евклидов алгоритм (ЕА)[⇨]. Из-за высокой регулярности структуры этого алгоритма его широко используют для аппаратной реализации декодеров БЧХ и кодов Рида — Соломона.
  • Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ). Исторически это первый метод декодирования, найденный Питерсоном для двоичного случая , затем Горенстейном и Цирлером для общего случая. Этот алгоритм находит коэффициенты многочлена локаторов ошибок прямым решением соответствующей системы линейных уравнений. В действительности, так как сложность этого алгоритма растет как куб минимального расстояния , прямой алгоритм может быть использован только для малых значений , однако именно этот алгоритм лучше всего проясняет алгебраическую идею процесса декодирования.

Алгоритм Берлекемпа — Мэсси[править | править вики-текст]

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра(сдвига) с обратной связью, генерирующего известную последовательность синдромов . Его фактическая цель — построить полином наименьшей степени, удовлетворяющему следующему уравнению . Решение этого уравнения эквивалентно следующему условию . Итеративный процесс построения такого многочлена и есть Алгоритм Берлекемпа — Мэсси.

Евклидов алгоритм[править | править вики-текст]

В основе этого метода лежит широко известный алгоритм Евклида по нахождению наибольшего общего делителя двух чисел (НОД), только в данном случае ищем НОД не двух чисел, а двух полиномов. Обозначим полином значений ошибок как , где синдромный полином равен . Из системы уравнений (*) следует что . Задача по сути сводится к тому чтобы определить удовлетворяющего (2) и при этом степени не выше . По сути такое решение и будет давать расширенный алгоритм Евклида, примененный к многочленам и , где . Если на -ом шаге расширенный алгоритм Евклида выдает решение , такое что , то и . При этом найденный полином дальше не принимает участия в декодировании(он ищется только как вспомогательный). Таким образом будет найден полином локаторов ошибок .

Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ)[править | править вики-текст]

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

Можно составить -ый синдром принятого слова :

Задача состоит в нахождении числа ошибок , их позиций и их значений при известных синдромах .

Предположим, для начала, что в точности равно . Запишем в виде системы нелинейных уравнений в явном виде:

Обозначим через локатор -ой ошибки, а через величину ошибки, . При этом все различны, так как порядок элемента равен , и поэтому при известном можно определить как .

Составим полином локаторов ошибок:

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на . Полученное равенство будет справедливо для :

Положим и подставим в . Получится равенство, справедливое для каждого и при всех :

Таким образом для каждого можно записать своё равенство. Если их просуммировать по , то получится равенство, справедливое для каждого :

.

.

Учитывая и то, что (то есть меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:

Или в матричной форме

где

Если число ошибок и в самом деле равно , то система разрешима, и можно найти значения коэффициентов . Если же число , то определитель матрицы системы будет равен . Это есть признак того, что количество ошибок меньше . Поэтому необходимо составить систему , предполагая число ошибок равным . Высчитать определитель новой матрицы и т. д., до тех пор, пока не установим истинное число ошибок.

Поиск Ченя[править | править вики-текст]

После того как ключевая система уравнений решена, получаются коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля . К ним найти элементы, обратные по умножению, — это локаторы ошибок . Этот процесс легко реализовать аппаратно.

Алгоритм Форни[править | править вики-текст]

Общая схема декодирования БХЧ кодов (алгоритм Форни)

По локаторам можно найти позиции ошибок (), а значения ошибок из системы , приняв . Декодирование завершено.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]