Полиномиальные коды и их практическое применение

Основные понятия полиномиальных кодов:

При описании полиномиальных кодов n-разрядные кодовые комбинации представляются в виде многочленов c переменной x.

Например, 0011 1000 = 1*x⁶+1*x⁵1*x⁴.

Число информационных символов m - количество разрядов, необходимое для передачи сообщения без использования корректирующих символов.

Число контрольных символов k-количество разрядов, необходимое в данном коде для обеспечения заданной помехоустойчивости.

Длина кодовой комбинации n - комбинация из контрольных и информационных символов, где n = m + k.

Неприводимый минимальный многочлен (полином) M(X)-многочлен, делящийся без остатка на себя и на единицу. Неприводимые минимальные многочлены в теории циклических кодов используются для получения образующих многочленов. В таблице 1 приведены некоторые начальные неприводимые многочлены.

Таблица 1.

Начальные неприводимые многочлены

Кодовое расстояние d - это расстояние между ближайшими кодовыми комбинациями. Оно определяется числом позиций, в которых их двоичные знаки не совпадают. Это значит, что кодовое расстояние между двоичными комбинациями X и Y равно весу W(Z) некоторой третьей комбинации Z, получаемой поразрядным сложением по модулю 2 этих комбинаций:

Например: x=1000 1011; y=1011 0011;

z= x ⊕ y= 0011 1000, т.о d=3.

Образующий многочлен K(X)-многочлен, при помощи которого происходит построение того или иного кода с заданными помехоустойчивыми параметрами. Образующий многочлен может быть равен неприводимому минимальному многочлену или являться их произведением.

Пример:

К(x) = m₆(x) =  = x⁴+x²+1;

К(X) = m₇(x)*m₁₂(x) = 10011*10101 = 110001111 = x⁸+x⁷+x³+x²+1.

Теорема: Многочлен , где q - степень простого числа, равен произведению всех нормированных неприводимых над GF(q) многочленов, степени которых делят m
Коды БЧХ

В БЧХ-коде построение образующего многочлена, в основном, зависит от двух параметров: от длины кодового слова n=m+k и от числа исправляемых ошибок S.

Алгоритм кодирования (систематического):

1) Задать параметры кода, такие как коррекционная способность t, количество бит в сообщении 5, длина кода 15.

2) Найти порождающий полином.

3) Умножить информационные биты на 

4) Вычислить кодовые биты, разделив информационные биты на порождающий полином.

5) Объединить информационные биты с остатком от деления, полученным на предыдущем шаге.

Алгоритм декодирования (расширенным алгоритмом Евклида):

1) Вычислить синдромы , подставив  Если все синдромы равны 0, сообщение передано без ошибок, и алгоритм завершается. Получить синдромный полином: S(x) = s_2tx^2t + s2_t-1x^2t-1 +...+ s₁x + 1.

2) Применить алгоритм Евклида для многочленов , чтобы вычислить полином локаторов ошибок.

3) Найти корни полинома методом перебора, определить коэффициенты полинома ошибок  , где j=n - k, k - степень - корня полинома-локатора ошибок.  Если корней нет, исправить ошибки невозможно, и алгоритм завершается.

4) Сложить полином ошибок и принятое сообщение, получив сообщение без ошибок.

Пример:

Продемонстрируем кодирование сообщения кодом БЧХ. Для начала необходимо задать сообщение В = 10101 длины k, содержащее исходные данные. Если, к примеру, нам нужен код, исправляющий 3 ошибки (t = 3), то нам нужно найти такую степень двойки m, которая бы “покрыла” исходное сообщение и биты четности (т.е. все кодовое слово). Общая длина кодового слова n = - 1, а количество битов четности – n - k  mt. Наименьшая степень двойки, большая k, равна 3 (). Минимальное расстояние равно 2t + 1 = 7. Тогда минимальное расстояние между двумя кодовыми словами в двоичном представлении как минимум 7 бит, в которых 2 кодовых слова должны различаться. Если мы выберем m=3 с длиной кодового слова n=7, то минимальное расстояние не будет соблюдаться. Для того чтобы это условие выполнялось, необходимо выбрать следующую степень двойки, 4 ().

Таким образом, в данном случае мы используем код БЧХ (15,5), он позволит исправлять 3 ошибки в сообщении длиной 5.

Следующим шагом будет нахождение порождающего полинома. Для этого необходимо сначала выполнить построение поля Галуа GF(), задав его корнем уравнения  ⁴++1=0. Первые 4 элемента поля ⁰, ¹, ², ³, будут образующими. Элемент ⁴ получим как остаток от деления:

 = 1 + . Элементы ⁵-¹⁴ получим, умножая результат предыдущего шага на  и приводя к образующим элементам, например для ⁷:

6=3+2; 7=4+3 = (так как 4 =  + 1) = 3++1.

Составим таблицу:

Таблица 2.

Поле Галуа GF()

Затем по теореме для GF() q=2, m=4:

 +  = (+1)(²++1)(⁴++1)(⁴+³+1)(⁴+³+²++1). Поскольку поле задано корнем уравнения ⁴ +  + 1 = 0, то минимальный многочлен для каждого из элементов можно найти так:

возьмем к примеру строку ⁵ таблицы 3. Подставим ⁵в многочлен   ¹⁰ + ⁵ +1. Подставляя значения из Таблицы 1 убедимся что ¹⁰ + ⁵ + 1 = (² +  + 1) + (² + ) + 1 = 0. Элемент таблицы найден.

Таблица 3.

Минимальные многочлены для элементов из GF()

Используя арифметику полей Галуа, а также формулу для порождающего многочлена, находим порождающий многочлен:

g(x)=**= .

Дополним исходное сообщение справа 10 нулевыми битами:

10101 0000000000   В виде полинома: x¹⁴+x¹²+x¹⁰.

Чтобы получить кодовую последовательность, разделим этот полином на порождающий:

=+

Перепишем остаток в векторном виде - 1001000111. Это и есть оставшаяся часть кодового слова. Тогда кодовое слово запишется как:

10101 1001000111.

Допустим, что при передаче произошло 3 ошибки, например

10001 1101010111

Нужно учитывать, что при приеме слова нам неизвестны ни позиции ошибок, ни их количество!

Число t=3, значит синдромов будет 2*t = 6. Их можно найти, подставив в принятое сообщение  в степени номера синдрома:

 = r () =³ + 1 = ¹⁴;

 = r(²) = r ())² = ¹⁴)² = ³ +² + 1 =¹³;

 = r (³) = ³ + 1 = ¹⁴;

 = r (⁴)) = ( r ())²)² = ³ + ² + = ¹¹;

 = r (⁵) = 0;

 = r (⁶) = ( r (³))² = ³ +² + 1 =¹³.

Применим алгоритм Евклида:

Шаг 0. r₋₂(x) = x⁷ ,

r₋₁(x) = s(x) = α¹³x⁶ + α¹¹x⁴ + α¹⁴x³ + α¹³x² + α¹⁴x + 1,

y₋₂(x) = 0,

y₋₁(x) = 1.

Шаг 1. r₋₂(x) = r₋₁(x)q₀(x) + r₀(x),

q₀(x) = α²x,

r₀(x) = α¹³x⁵ + α¹x⁴ + x³ + α¹х² + а²х,

y₀(x) = y₋₂(x) + y₋₁(x)q₀(x) = q₀(x) = α²х.

Шаг 2. r₋₁(x) = r₀(x)q₁(x) + r₁(x),

q₁(x) = х+а³ ,

r₁(x) = α⁶x⁴ + α⁴x³ + α⁹x² + α¹²x + 1,

y₁(x) = y₋₁(x) + y₀(x)q₁(x) = 1+α²x² + α⁵x.

Шаг 3. r₀(x) = r₁(x)q₂(x) + r₂(x),

q₂(x) = а⁷х+1,

r₂(x) = α⁷x²+1,

y₂(x) = y₀(x) + y₁(x)q₂(x) = α⁹x³ + α⁷x² + α¹⁴x+1

Тогда полином локаторов ошибок  α⁹x³ + α⁷x² + α¹⁴x+1.

Теперь необходимо подбором найти корни, т.е. значения αⁿ такие что =0.

Зная корни, можно легко вычислить полином ошибок. Чтобы получить ненулевые коэффициенты этого полинома, достаточно отнять от 15 степени корней полинома-локатора ошибок:

15-3=12; 15-7=8; 15-11=4. Значит e(x)=x¹²+x⁸+x⁴ - полином ошибок, а переданное сообщение:

e(x)+p(x)=x¹²+x⁸+x⁴ +=.

Описанный код БЧХ (15,5) используется в информации о формате QR- кодов. Обратимся к ГОСТ на QR-коды, чтобы выяснить чему соответствует код из примера. Пер­вые два бита данных содержат уровень исправления ошибок символа, а остальные 3 - уровень маски данных. 10 - последовательность для уровня исправления ошибок H, 101 - последовательность для маски ((i j) mod 2)+((i j) mod 3)=0.  К ним добавляют 10 кодовых бит, которые в нашем случае совпадут с полученными в примере 1001000111 .Затем к 15 битам информации о формате 10101 1001000111 применяют операцию XOR с маской 10101 0000010010, чтобы гарантировать, что никакая комбинация уровня исправления ошибок и указателя шаблона маски данных не имеет в результате 15 нулевых битов. В результате получается последовательность 00000 1001010101. Запишем эту последовательность в формат QR-кода, учитывая что черный квадрат означает 1, а белый - 0.  В каждом QR коде содержится две копии этих данных, отмеченных на рисунке зелеными и голубыми рамками.

Рисунок. Пример применения БЧХ кода для хранения информации о формате в QR- кодах

Заключение:

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

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

В работе были рассмотрены алгоритмы систематического кодирования и декодирования БЧХ кодов, приведен пример создания кодовой последовательности для некоторого слова, а также изучен вопрос практического применения рассмотренного в примере кода.