Статья:

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

Конференция: XXVIII Студенческая международная научно-практическая конференция «Технические и математические науки. Студенческий научный форум»

Секция: Физико-математические науки

Выходные данные
Вражнов И.А., Коновалов В.Ф. Полиномиальные коды и их практическое применение // Технические и математические науки. Студенческий научный форум: электр. сб. ст. по мат. XXVIII междунар. студ. науч.-практ. конф. № 5(28). URL: https://nauchforum.ru/archive/SNF_tech/5(28).pdf (дата обращения: 27.09.2020)
Лауреаты определены. Конференция завершена
Эта статья набрала 561 голос
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Вражнов Илья Александрович
студент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, Самара
Коновалов Виталий Федорович
студент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, Самара
Додонова Наталья Леонидовна
научный руководитель, канд. физ.-мат. наук, доцент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, г. Самара

 

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

При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды отличаются от других блочных кодов только алгоритмами кодирования и декодирования.

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

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

Например, 0011 1000 = 1*x6+1*x51*x4.

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

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

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

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

Таблица 1.

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

№ п/п

Степень m

Аналитическое представление многочлена

dmin

Коррекция

r =, s =

1.

1

x + 1

2

r = 1, s = 0

2.

2

x2 + x + 1

3

r = 2, s = 1

3.

3

x3 + x + 1

3

r = 2 , s = 1

4.

x3 + x2 + 1

3

r = 2, s = 1

5.

4

x4 + x + 1

3

r = 2, s = 1

6.

x4 + x2 +1

3

r = 2, s = 1

 

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

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

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

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

Пример:

К(x) = m6(x) =  = x4+x2+1;

К(X) = m7(x)*m12(x) = 10011*10101 = 110001111 = x8+x7+x3+x2+1.

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

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

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

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

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

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

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

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

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

1) Вычислить синдромы , подставив  Если все синдромы равны 0, сообщение передано без ошибок, и алгоритм завершается. Получить синдромный полином: S(x) = s2tx2t + s2t-1x2t-1 +...+ s1x + 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(), задав его корнем уравнения  4++1=0. Первые 4 элемента поля 0123, будут образующими. Элемент 4 получим как остаток от деления:

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

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

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

Таблица 2.

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

Вектор

Многочлен

Степень

0 0 0 0

0

0

1 0 0 0

1

1

0 1 0 0

0 0 1 0

2

2

0 0 0 1

3

3

1 1 0 0

 + 1

4

0 1 1 0

2 + 

5

0 0 1 1

3 + 2

6

1 1 0 1

3 +  + 1

7

1 0 1 0

2 + 1

8

0 1 0 1

3 + 

9

1 1 1 0

2 +  + 1

10

0 1 1 1

3 + +

11

1 1 1 1

3 + 2 +  + 1

12

1 0 1 1

3 + 2 + 1

13

1 0 0 1

3 + 1

14

 

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

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

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

Таблица 3.

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

0

 + 1

0

1

4 +  + 1

1

2

4 +  + 1

2

3

+3 + 2 +  + 1

3

4

4 +  + 1

4

5

2 +  + 1

5

6

4 + 3 +  + 1

6

 

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

g(x)=**.

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

10101 0000000000   В виде полинома: x14+x12+x10.

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

=+

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

10101 1001000111.

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

10001 1101010111

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

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

 = r () =+ 1 = 14;

 = r(2) = r ())2 = 14)2 = 3 +2 + 1 =13;

 = r (3) = 3 + 1 = 14;

 = r (4)) = ( r ())2)2 = + = 11;

 = r (5) = 0;

 = r (6) = ( r (3))2 = 3 +2 + 1 =13.

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

Шаг 0. r−2(x) = x7 ,

r−1(x) = s(x) = α13x6 + α11x4 + α14x3 + α13x2 + α14x + 1,

y−2(x) = 0,

y−1(x) = 1.

Шаг 1. r−2(x) = r−1(x)q0(x) + r0(x),

q0(x) = α2x,

r0(x) = α13x5 + α1x4 + x3 + α1х2 + а2х,

y0(x) = y−2(x) + y−1(x)q0(x) = q0(x) = α2х.

Шаг 2. r−1(x) = r0(x)q1(x) + r1(x),

q1(x) = х+а3 ,

r1(x) = α6x4 + α4x3 + α9x2 + α12x + 1,

y1(x) = y−1(x) + y0(x)q1(x) = 1+α2x2 + α5x.

Шаг 3. r0(x) = r1(x)q2(x) + r2(x),

q2(x) = а7х+1,

r2(x) = α7x2+1,

y2(x) = y0(x) + y1(x)q2(x) = α9x3 + α7x2 + α14x+1

Тогда полином локаторов ошибок  α9x3 + α7x2 + α14x+1.

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

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

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

e(x)+p(x)=x12+x8+x4 +=.

Описанный код БЧХ (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- кодах

 

 

Заключение:

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

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

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

 

Список литературы: 
1. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера, 2005. – 320 с.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ./ ред. К. Ш. Зигангирова. – М.: Мир, 1986. – 576 с.
3. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки: Пер. с англ – М: Связь, 1979. – 744 с.
4. ГОСТ НА QR - коды: ГОСТ Р ИСО/МЭК 18004-2015