Построение кодов исправляющих ошибки с использованием арифметики полей Галуа

 

Построение кодов исправляющих ошибки с использованием арифметики полей Галуа


Ключевые слова: коды Рида-Соломона, поля Галуа, систематическое кодирование.

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

Важное семейство кодов исправляющих ошибки образуют линейные двоичные блочные коды [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)

степень ? (номер элемента поля) Двоичное числоДесятичное числостепень ? (номер элемента поля) Двоичное числоДесятичное число00000000111211100110230100000010213111001112312000001004141110010122930000100081511100001225400010000161611101001233500100000321711111001249601000000641811011001217710000000128191001100115380010101143200001100125901010110862100110010501010101100172220110010010011011100111152311001000200

Проводить операции умножения и деления с элементами поля 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)


Запись кодового слова через все члены полинома имеет вид:


А (Х) =Xn-kМ (X) +Р (Х) =mk-1Xn-1+…+m1Xn-k+1+m0Xn-k+pn-k-1Xn-k-1+…+p2X2+p1X+p0. (11)


Рассмотрим более подробно процедуру вычисления остатка Р (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 с.


Построение кодов исправляющих ошибки с использованием арифметики полей Галуа Ключевые слова: коды Рида-Соломона, поля Галуа, систематическое кодирование.

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ