Light-industry-up.ru

Экосистема промышленности

Код БЧХ

10-05-2023

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

Содержание

Формальное описание

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

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

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

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

.

Построение

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

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

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

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

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

Примеры кодов

Примитивный 2-ичный (15,7,5) код

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

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

16-ричный (15,11,5) код (код Рида — Соломона)

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

.

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

Кодирование

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

Методы декодирования

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

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

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

Пусть принятое слово ассоциировано с полиномом , где многочлен ошибок определён как: , где число ошибок в принятом слове. Множества {e_{J_1},e_{J_2},\ldots,e_{J_\nu}} и называют значениями ошибок и локаторами ошибок, соответственно, где и .

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

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

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

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

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

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

Основная статья: Алгоритм Берлекэмпа — Мэсси

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

Евклидов алгоритм

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

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

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

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

.

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

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

{ \begin{cases} S_1 = e_{i_1} \beta^{l_0 i_1} + e_{i_2} \beta^{l_0 i_2} + \dots + e_{i_t} \beta^{l_0 i_t} \\ S_2 = e_{i_1} \beta^{(l_0+1) i_1} + e_{i_2} \beta^{(l_0+1) i_2} + \dots + e_{i_t} \beta^{(l_0+1) i_t} \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ S_{d-1} = e_{i_1} \beta^{(l_0+d-2) i_1} + e_{i_2} \beta^{(l_0+d-2) i_2} + \dots + e_{i_t} \beta^{(l_0+d-2) i_t} \\ \end{cases} }

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

{ \begin{cases} S_1 = Y_1 X_1^{l_0} + Y_2 X_2^{l_0} + \dots + + Y_t X_t^{l_0} \\ S_2 = Y_1 X_1^{l_0+1} + Y_2 X_2^{l_0+1} + \dots + + Y_t X_t^{l_0+1} \quad \quad \quad \quad \quad\quad(2) \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ S_{d-1} = Y_1 X_1^{l_0+d-2} + Y_2 X_2^{l_0+d-2} + \dots + + Y_t X_t^{l_0+d-2} \end{cases} }

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

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

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

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

.

.

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

{ \begin{cases} S_1 \Lambda_t + S_2 \Lambda_{t-1} + \dots + S_t \Lambda_1 = -S_{t+1} \\ S_2 \Lambda_t + S_3 \Lambda_{t-1} + \dots + S_{t+1} \Lambda_1 = -S_{t+2} \quad \quad \quad \quad \quad\quad(4) \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ S_t \Lambda_t + S_{t+1} \Lambda_{t-1} + \dots + S_{2t-1} \Lambda_1 = -S_{2t} \end{cases} }

.

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

S^{(t)} \bar\Lambda^{(t)} = -\bar s^{(t)}

,

где

S^{(t)}={ \left[ \begin{matrix} S_1 & S_2 & \dots & S_t \\ S_2 & S_3 & \dots & S_{t+1} \\ \cdots & \cdots & \cdots & \\ S_t & S_{t+1} & \dots & S_{2t-1} \end{matrix} \right] }, \quad \quad \quad \quad \quad\quad(5)

\bar\Lambda^{(t)} = { \left[ \begin{matrix} \Lambda_t \\ \Lambda_{t-1} \\ \cdots \\ \Lambda_1 \end{matrix} \right] }, \quad \quad \bar s^{(t)} { \left[ \begin{matrix} S_{t+1} \\ S_{t+2} \\ \cdots \\ S_{2t} \end{matrix} \right] }

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

Поиск Ченя

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

Алгоритм Форни

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

Примечания

  1. ↑ 1 2 3 Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие. — М.: МФТИ, 2007. — С. 175-176. — ISBN 5-7417-0191-4
  2. Введение в алгебраические коды
  3. Искусство помехоустойчивого кодирования

См. также

Литература

  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
  • Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.
  • Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие. — М.: МФТИ, 2007. — 262 с. — ISBN 5-7417-0191-4
  • Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. — М.: Техносфера, 2005. — 320 с. — ISBN 5-94836-035-0

Код БЧХ.

© 2014–2023 light-industry-up.ru, Россия, Краснодар, ул. Листопадная 53, +7 (861) 501-67-06