Построение кодов исправляющих ошибки с использованием арифметики полей Галуа
Построение
кодов исправляющих ошибки с использованием арифметики полей Галуа
Ключевые слова: коды Рида-Соломона, поля Галуа,
систематическое кодирование.
Применение кодирования с исправлением ошибок позволяет
восстанавливать данные, потерянные как при передаче, так и в процессе хранения.
Использование кодов Рида-Соломона с недвоичными символами позволяет исправлять
пакеты ошибок. Важным моментом при кодировании и декодировании кодов
Рида-Соломона является деление полиномов. Использование арифметики полей Галуа
делает процесс кодирования и декодирования более эффективным и простым.
Важное семейство кодов исправляющих ошибки образуют линейные
двоичные блочные коды [1-3]. Эти коды представляют информационные и кодовые
слова в форме двоичных векторов. Вместо k бит информационного
вектора в канал передается n бит кодового вектора. Кодирование линейного блокового (n, k) - кода задается
порождающей матрицей G размером (k х n). Таким образом, кодовое слово v и информационное слово u связаны соотношением v = u*G.
Блочные коды чрезвычайно разнообразны, однако большинство из
них не в состоянии справиться с пакетами ошибок. Коды Боуза-Чоудхури-Хоквенгема
(БХЧ) позволяют исправлять множественные ошибки. Данный вид кодов предоставляет
большую свободу выбора длины блока, степени кодирования, размеров алфавита и
возможностей коррекции ошибок. Одним из подклассов кодов БХЧ с недвоичными
символами являются коды Рида-Соломона (РС). Символы этих кодов представляют
собой многобитовые (m-битовые) последовательности. Коды РС способны исправлять t=] (n - k) /2 [ошибок.
Одна из трудностей в понимании кодов РС заключается в
использовании при их построении и декодировании полей Галуа.
Полем называют множество элементов, если для любых элементов
этого множества определены операции сложения и умножения, а также выполняется
ряд аксиом (замкнутости, ассоциативности, коммутативности, дистрибутивности …)
[2].
В каналах связи множество передаваемых сигналов всегда
конечно. Поля с конечным числом элементов q называют полями Галуа по имени их
первого исследователя Эвариста Галуа и обозначают GF (q).
Важным моментом при кодировании и декодировании кодов РС
является деление полиномов. Проведение этой операция по правилам обычной
алгебры на ЭВМ крайне неэффективно и сложно. Это приводит к появлению чисел с
плавающей запятой. При использовании же полей Галуа при любой операции мы
получим число из этого поля. Увеличения разрядности и потери точности не
происходит.
В высшей математике доказано, что число элементов конечного
поля q всегда удовлетворяет условию:
=pm, (1)
где р - простое число называемое характеристикой поля, а m - положительное целое.
Если m=1, то такое поле называется простым, если m>1, то такое поле
называется расширенным. В простом поле операции сложения и умножения
выполняются по модулю р, а сами элементы образуют последовательность, состоящую
из чисел {0, 1, 2, …, р-1}. В простом поле существует, по крайней мере, один
примитивный элемент α, такой, что каждый не
нулевой элемент GF (р) может быть представлен как некоторая степень α по модулю р.
Если простое поле образуется из чисел, то расширенное поле
образуется из многочленов. Таким образом, можно провести и аналогию
формирования поля. Элементы простого поля формируются из степеней примитивного
элемента по модулю простого числа р, а элементы расширенного поля формируются
из степеней примитивного элемента по модулю примитивного полинома [2]. В
качестве примитивного элемента обычно берётся число 2.
Примитивный полином - это нередуцируемый полином f (X) порядка m, если наименьшим
положительным целым числом n, для которого Xn+1 делится на f (X) без остатка, будет n=2m-1. Нередуцируемый
полином - это полином, который нельзя представить в виде произведения полиномов
меньшего порядка.
Для построения кодов БХЧ используются символы из поля
расширения GF (2m). Каждый элемент поля GF (2m) можно представить в
виде слова длины m над полем GF (2) или многочлена с двоичными коэффициентами.
a = a (X) =am-1Xm-1+…+a2X2+a1X+a0,
(2)
где am-1,…,
a2, a1, a0 - бинарные числа.
Учитывая, что коэффициенты am-1,…,a1, a2, a0 являются либо 0 либо 1, каждый элемент конечного поля GF (2m) можно представить двоичным вектором или
просто двоичным числом. В некоторых случаях удобно представлять элементы поля
десятичными, восьмеричными или шестнадцатеричными числами.
Бесконечное множество элементов образуется из стартового множества
{0, 1, α1} добавлением дополнительных элементов
путем умножения последнего элемента на α [3]. Тогда бесконечное множество
элементов поля будет представлено как {0, α0, α1, α2, α3…}.
Рассмотрим образование конечного множества содержащего 2m элементов {0, α0, α1, α2, …,}. Из (2) мы знаем, что максимальный
порядок полинома m-1, но очевидно, что через m-1 проведенных умножений на α, (которые эквивалентны сдвигу полинома)
этот порядок будет превышен. Итак, если у нас на очередном шаге формирования
элементов поля получилось, что порядок полинома элемента равен m-1 (то есть, очевидно, что при сдвиге полученного полинома
произойдет выход за ограничение порядка полинома), то при формировании
следующего элемента после сдвига полинома мы вычитаем из результата примитивный
полином.
В цифровых системах передачи и хранения данных наиболее естественно
применение полей, число элементов которых укладывается в 1 байт, то есть
содержащих 28=256 элементов. Для построения поля GF (28)
возьмем примитивный полином f (X) =X8+X5+X3+ X+1 (что эквивалентно двоичному вектору
100101011), который определяет конечное поле GF (2m), где степень полинома m=8.
Поле, определяемое выбранным нами полиномом, имеет 2m=28=256 элементов от 0го
до 255го. Для удобства рассмотрения процесса формирования поля,
равным нулю обозначим не 0ой элемент, а 255ый.
Представим математическое описание процесса формирования элементов
поля:
А [0] =1, А [255] =0;
При А [i-1] <{10000000} А [i] =А [i-1] <<1;
При А [i-1] =>{10000000} А [i] = (А [i-1] <<1) +100101011.
Где символом << обозначен сдвиг влево двоичного
представления числа, а знак "+" обозначает операцию сложения по
модулю 2.
Более привычно и компактно представлять элементы поля в виде
десятичных чисел. Представим теперь математическое описание процесса
формирования элементов поля, представив их десятичными числами.
А [0] =1, А [255] =0;
При А [i-1] <128 А [i] =А [i-1] *2;
При А [i-1] =>128 А [i] = (А [i-1] *2) +299.
код ошибка поле галуа
Заметим, что суммирование элементов поля GF (28),
представленных в виде десятичных чисел, по модулю 2 необходимо проводить после
их перевода в двоичный вид. Операции вычитания и сложения элементов поля
сводятся к побитовому сложению по модулю 2 их двоичных представлений.
В таблице 1 показаны разные виды представления элементов поля
GF (28) для первых 24 элементов.
Таблица 1. Разные виды представления элементов поля GF (28)
степень α (номер элемента поля)
|
Двоичное число
|
Десятичное число
|
степень α (номер элемента поля)
|
Двоичное число
|
Десятичное число
|
0
|
00000001
|
1
|
12
|
11100110
|
230
|
1
|
00000010
|
2
|
13
|
11100111
|
231
|
2
|
00000100
|
4
|
14
|
11100101
|
229
|
3
|
00001000
|
8
|
15
|
11100001
|
225
|
4
|
00010000
|
16
|
16
|
11101001
|
233
|
00100000
|
32
|
17
|
11111001
|
249
|
6
|
01000000
|
64
|
18
|
11011001
|
217
|
7
|
10000000
|
128
|
19
|
10011001
|
153
|
8
|
00101011
|
43
|
20
|
00011001
|
25
|
9
|
01010110
|
86
|
21
|
00110010
|
50
|
10
|
10101100
|
172
|
22
|
01100100
|
100
|
11
|
01110011
|
115
|
23
|
11001000
|
200
|
Проводить операции умножения и деления с элементами поля GF
(28) удобно, сформировав обратное поле. Основное поле,
сформированное на основании приведенного выше математического описания,
позволяет по значению степени примитивного элемента (первый и четвертый столбцы
таблицы 1) найти значение элемента поля. Обратное поле позволяет по заданному
значению элемента поля найти степень примитивного элемента (числа 2). Обратное
поле - это поле логарифмов по основанию 2. Элементы обратного поля вычисляются
следующим образом:
L [А [i]] =i. (3)
Программная реализация процедуры формирования элементов поля
GF (28) и обратного поля в десятичном представлении на языке С++:
[0] =1;[255] =0;(i=1; i<=254; i++)
{if (A [i-1] <128)[i] =A [i-1] *2;[i] =show_summ (2*A
[i-1], 299); }(i=0; i<=255; i++)
{n=A [i];[n] =i; }
Где "show_summ" - обращение к функции сложения
элементов поля Галуа.
Теперь, имея сформированное основное и обратное поле,
определим проведение операции умножения чисел Ma и Mb.
Если (L [Ma] +L [Mb]) <255, то Ma*Mb=А [ (L [Ma] +L [Mb])];
Если (L [Ma] +L [Mb]) =>255, то Ma*Mb=А [ (L [Ma] +L [Mb] - 255)];
Определим проведение операции деления чисел Dm и Dl.
Если (L [Dm] +L [Dl]) >0, то Dm/Dl =А [ (L [Dm] - L [Dl])];
Если (L [Dm] +L [Dl]) <=0, то Dm/Dl =А [ (L [Dm] - L [Dl] +255)];
Программная реализация функции деления аналогична функции
умножения и приводить её нет смысла. Далее рассмотрим построение
систематических кодов РС. Пусть M= (m0, m1, m2,…,mk-1) - вектор
информационного сообщения. Тогда вектор кодового слова при систематическом
кодировании будет выглядеть следующим образом:
A= (m0, m1, m2,…,
mk-1, p0, p1, p2,…, pn-k-1),
(4)
где p0, p1, p2,…, pn-k-1 - проверочные символы.
Вектор сообщения можно записать в полиномиальной форме
следующим образом:
М (X) = mk-1Xk-1+…+ m2X2+ m1X+ m0. (5)
Чтобы получить полином кодового сообщения необходимо
осуществить сдвиг полинома сообщения в k крайне правых разряда
кодового слова, а затем прибавить проверочные биты в n-k разрядов слева. Получить
сдвинутый вправо полином сообщения мы можем путем умножения его на Xn-k:
Xn-k М (X) = mk-1Xn-1+ …+ m1Xn-k+1+m0 Xn-k. (6)
Полином кодового сообщения можно представить как:
А (Х) = Xn-k М (X) + Р (X). (7)
Проверочные символы мы получаем, используя генератор кода g (Х).
Р (X) = Xn-k М (X) по модулю g (Х). (8)
То есть Р (X) получается как остаток от деления Xn-kМ (X) на g (Х). Полиномиальный
генератор имеет вид:
g (X) = gn-kXn-k +…+ g2X2
+ g1X + g0. (9)
Р (Х) можно записать следующим образом:
Р (X) = pn-k-1Xn-k-1 +…+ p2X2+ p1X + p0. (10)
Запись кодового слова через все члены полинома имеет вид:
Рассмотрим более подробно процедуру вычисления остатка Р (X).
Мы имеем полином-делимое А (Х) = Xn-kМ (Х) степени n-1 и полином-делитель g (Х) степени r = n-k. Деление полиномов
осуществляется с некоторыми отличиями по отношению к традиционной математики.
На каждом шаге деления между соответствующими коэффициентами полиномов выполняется
не вычитание, а операция сложения по модулю 2. На каждом шаге деления
получается остаток, состоящий из r коэффициентов. Всего шагов деления s=1… n-r. Старший коэффициент
полинома остатка всегда равен нулю, так что степень полинома остатка будет r-1. На каждом шаге
проводить вычислении старшего коэффициента нет необходимости. Очередной
коэффициент частного удобно брать из остатка вычисленного на предыдущем шаге. С
учетом всего вышесказанного получаем математическую модель процедуры вычисления
остатка:
Рj0=An-r+j,
j=0…r-1;
РjS=An-r-s+g0Рr-1S-1, j=0;
РjS= Рj-1S-1+gjРr-1S-1, j=0…r-1.
Рj0 здесь - начальный остаток, а РjS остаток после шага s.
Программная реализация процедуры вычисления остатка от
деления на языке С++:
(j=0; j<=r-1; j++)
{P [0] [j] =A [n-r+j]; }(s=1; s<=n-r; s++)
{P [s] [0] =show_summ (A [n-r-s], show_proizv (g [0], P [s-1]
[r-1]));(j=1; j<=r-1; j++)
{P [s] [j] =show_summ (P [s-1] [j-1], show_proizv (g [j], P
[s-1] [r-1])); }}
Где "show_proizv" - обращение к функции умножения
элементов поля Галуа.
Литература
1.
Скляр Б. Цифровая связь. Теоретические основы и практическое применение. М.:
Издательский дом "Вильямс", 2007 - 1104 с.
.
Вернер М. Основы кодирования. М.: Техносфера, 2006 - 286 с.
.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы,
применение. М.: Техносфера, 2006 - 319 с.