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

Тип работы:
Реферат
Предмет:
Коммуникации, связь, цифровые приборы и радиоэлектроника


Узнать стоимость

Детальная информация о работе

Выдержка из работы

/10

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

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

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

Важное семейство кодов исправляющих ошибки образуют линейные двоичные блочные коды [1−3]. Эти коды представляют информационные и кодовые слова в форме двоичных векторов. Вместо k бит информационного вектора в канал передается n бит кодового вектора. Кодирование линейного блокового (n, k) — кода задается порождающей матрицей G размером (k х n). Таким образом, кодовое слово v и информационное слово u связаны соотношением v = u*G.

Блочные коды чрезвычайно разнообразны, однако большинство из них не в состоянии справиться с пакетами ошибок. Коды Боуза-Чоудхури-Хоквенгема (БХЧ) позволяют исправлять множественные ошибки. Данный вид кодов предоставляет большую свободу выбора длины блока, степени кодирования, размеров алфавита и возможностей коррекции ошибок. Одним из подклассов кодов БХЧ с недвоичными символами являются коды Рида-Соломона (РС). Символы этих кодов представляют собой многобитовые (m-битовые) последовательности. Коды Р С способны исправлять t=] (n — k) /2 [ошибок.

Одна из трудностей в понимании кодов РС заключается в использовании при их построении и декодировании полей Галуа.

Полем называют множество элементов, если для любых элементов этого множества определены операции сложения и умножения, а также выполняется ряд аксиом (замкнутости, ассоциативности, коммутативности, дистрибутивности …) [2].

В каналах связи множество передаваемых сигналов всегда конечно. Поля с конечным числом элементов q называют полями Галуа по имени их первого исследователя Эвариста Галуа и обозначают GF (q).

Важным моментом при кодировании и декодировании кодов РС является деление полиномов. Проведение этой операция по правилам обычной алгебры на ЭВМ крайне неэффективно и сложно. Это приводит к появлению чисел с плавающей запятой. При использовании же полей Галуа при любой операции мы получим число из этого поля. Увеличения разрядности и потери точности не происходит.

В высшей математике доказано, что число элементов конечного поля 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 (что эквивалентно двоичному вектору 100 101 011), который определяет конечное поле GF (2m), где степень полинома m=8. Поле, определяемое выбранным нами полиномом, имеет 2m=28=256 элементов от 0го до 255го. Для удобства рассмотрения процесса формирования поля, равным нулю обозначим не 0ой элемент, а 255ый.

Представим математическое описание процесса формирования элементов поля:

А [0] =1, А [255] =0;

При, А [i-1] < {10 000 000} А [i] =А [i-1] < <1;

При, А [i-1] => {10 000 000} А [i] = (А [i-1] < <1) +100 101 011.

Где символом < < обозначен сдвиг влево двоичного представления числа, а знак «+» обозначает операцию сложения по модулю 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

1

1

12

11 100 110

230

1

10

2

13

11 100 111

231

2

100

4

14

11 100 101

229

3

1 000

8

15

11 100 001

225

4

10 000

16

16

11 101 001

233

5

100 000

32

17

11 111 001

249

6

1 000 000

64

18

11 011 001

217

7

10 000 000

128

19

10 011 001

153

8

101 011

43

20

11 001

25

9

1 010 110

86

21

110 010

50

10

10 101 100

172

22

1 100 100

100

11

1 110 011

115

23

11 001 000

200

Проводить операции умножения и деления с элементами поля GF (28) удобно, сформировав обратное поле. Основное поле, сформированное на основании приведенного выше математического описания, позволяет по значению степени примитивного элемента (первый и четвертый столбцы таблицы 1) найти значение элемента поля. Обратное поле позволяет по заданному значению элемента поля найти степень примитивного элемента (числа 2). Обратное поле — это поле логарифмов по основанию 2. Элементы обратного поля вычисляются следующим образом:

L [А [i]] =i. (3)

Программная реализация процедуры формирования элементов поля GF (28) и обратного поля в десятичном представлении на языке С++:

A [0] =1;

A [255] =0;

for (i=1; i< =254; i++)

{if (A [i-1] < 128)

A [i] =A [i-1] *2;

else

A [i] =show_summ (2*A [i-1], 299); }

for (i=0; i< =255; i++)

{n=A [i];

L [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.

Программная реализация процедуры вычисления остатка от деления на языке С++:

for (j=0; j< =r-1; j++)

{P [0] [j] =A [n-r+j]; }

for (s=1; s< =n-r; s++)

{P [s] [0] =show_summ (A [n-r-s], show_proizv (g [0], P [s-1] [r-1]));

for (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 с.

2. Вернер М. Основы кодирования. М.: Техносфера, 2006 — 286 с.

3. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2006 — 319 с.

ПоказатьСвернуть
Заполнить форму текущей работой