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

/10

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

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

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

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

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

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

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

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

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

В высшей математике доказано, что число элементов конечного поля q всегда удовлетворяет условию:

q=p^m, (1)

где р — простое число называемое характеристикой поля, а m — положительное целое.

Если m=1, то такое поле называется простым, если m>1, то такое поле называется расширенным. В простом поле операции сложения и умножения выполняются по модулю р, а сами элементы образуют последовательность, состоящую из чисел {0, 1, 2, …, р-1}. В простом поле существует, по крайней мере, один примитивный элемент б, такой, что каждый не нулевой элемент GF (р) может быть представлен как некоторая степень б по модулю р.

Если простое поле образуется из чисел, то расширенное поле образуется из многочленов. Таким образом, можно провести и аналогию формирования поля. Элементы простого поля формируются из степеней примитивного элемента по модулю простого числа р, а элементы расширенного поля формируются из степеней примитивного элемента по модулю примитивного полинома. В качестве примитивного элемента обычно берётся число 2.

Примитивный полином — это нередуцируемый полином f (X) порядка m, если наименьшим положительным целым числом n, для которого Xⁿ+1 делится на f (X) без остатка, будет n=2^m-1. Нередуцируемый полином — это полином, который нельзя представить в виде произведения полиномов меньшего порядка.

Для построения кодов БХЧ используются символы из поля расширения GF (2^m). Каждый элемент поля GF (2^m) можно представить в виде слова длины m над полем GF (2) или многочлена с двоичными коэффициентами.

a = a (X) =a_m-1X^m-1+…+a₂X²+a₁X+a₀, (2)

где a_m-1,…, a₂, a₁, a_{0 -} бинарные числа.

Учитывая, что коэффициенты a_m-1,…, a_1, a₂, a₀ являются либо 0 либо 1, каждый элемент конечного поля GF (2^m) можно представить двоичным вектором или просто двоичным числом. В некоторых случаях удобно представлять элементы поля десятичными, восьмеричными или шестнадцатеричными числами.

Бесконечное множество элементов образуется из стартового множества {0, 1, б¹} добавлением дополнительных элементов путем умножения последнего элемента на б. Тогда бесконечное множество элементов поля будет представлено как {0, б⁰, б¹, б², б³…}.

Рассмотрим образование конечного множества содержащего 2^m элементов {0, б⁰, б¹, б², …,}. Из (2) мы знаем, что максимальный порядок полинома m-1, но очевидно, что через m-1 проведенных умножений на б, (которые эквивалентны сдвигу полинома) этот порядок будет превышен. Итак, если у нас на очередном шаге формирования элементов поля получилось, что порядок полинома элемента равен m-1 (то есть, очевидно, что при сдвиге полученного полинома произойдет выход за ограничение порядка полинома), то при формировании следующего элемента после сдвига полинома мы вычитаем из результата примитивный полином.

В цифровых системах передачи и хранения данных наиболее естественно применение полей, число элементов которых укладывается в 1 байт, то есть содержащих 2⁸=256 элементов. Для построения поля GF (2⁸) возьмем примитивный полином f (X) =X⁸+X⁵+X³+ X+1 (что эквивалентно двоичному вектору 100 101 011), который определяет конечное поле GF (2^m), где степень полинома m=8. Поле, определяемое выбранным нами полиномом, имеет 2^m=2⁸=256 элементов от 0^го до 255^го. Для удобства рассмотрения процесса формирования поля, равным нулю обозначим не 0^ой элемент, а 255^ый.

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

А =1, А =0;

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

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

Где символом << обозначен сдвиг влево двоичного представления числа, а знак «+» обозначает операцию сложения по модулю 2.

Более привычно и компактно представлять элементы поля в виде десятичных чисел. Представим теперь математическое описание процесса формирования элементов поля, представив их десятичными числами.

А =1, А =0;

При, А [i-1] <128 А [i] =А [i-1] *2;

При, А [i-1] =>128 А [i] = (А [i-1] *2) +299.

код ошибка поле галуа Заметим, что суммирование элементов поля GF (2⁸), представленных в виде десятичных чисел, по модулю 2 необходимо проводить после их перевода в двоичный вид. Операции вычитания и сложения элементов поля сводятся к побитовому сложению по модулю 2 их двоичных представлений.

В таблице 1 показаны разные виды представления элементов поля GF (2⁸) для первых 24 элементов.

Таблица 1. Разные виды представления элементов поля GF (2⁸)

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

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

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

A =1;

A =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= (m₀, m₁, m₂,…, m_k-1) — вектор информационного сообщения. Тогда вектор кодового слова при систематическом кодировании будет выглядеть следующим образом:

A= (m_0, m_1, m_2,…, m_k-1, p_0, p_1, p_2,…, p_n-k-1), (4)

где p_0, p_1, p_2,…, p_{n-k-1 -} проверочные символы.

Вектор сообщения можно записать в полиномиальной форме следующим образом:

М (X) = m_k-1X^k-1+…+ m₂X²+ m₁X+ m₀. (5)

Чтобы получить полином кодового сообщения необходимо осуществить сдвиг полинома сообщения в k крайне правых разряда кодового слова, а затем прибавить проверочные биты в n-k разрядов слева. Получить сдвинутый вправо полином сообщения мы можем путем умножения его на X^n-k:

X^n-k М (X) = m_k-1X^n-1+ …+ m₁X^n-k+1+m₀ X^n-k. (6)

Полином кодового сообщения можно представить как:

А (Х) = X^n-k М (X) + Р (X). (7)

Проверочные символы мы получаем, используя генератор кода g (Х).

Р (X) = X^n-k М (X) по модулю g (Х). (8)

То есть Р (X) получается как остаток от деления X^n-kМ (X) на g (Х). Полиномиальный генератор имеет вид:

g (X) = g_n-kX^n-k +…+ g₂X² + g₁X + g₀. (9)

Р (Х) можно записать следующим образом:

Р (X) = p_n-k-1X^n-k-1 +…+ p₂X²+ p₁X + p₀. (10)

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

А (Х) =X^n-kМ (X) +Р (Х) =m_k-1X^n-1+…+m₁X^n-k+1+m₀X^n-k+p_n-k-1X^n-k-1+…+p₂X²+p₁X+p₀. (11)

Рассмотрим более подробно процедуру вычисления остатка Р (X).

Мы имеем полином-делимое, А (Х) = X^n-kМ (Х) степени n-1 и полином-делитель g (Х) степени r = n-k. Деление полиномов осуществляется с некоторыми отличиями по отношению к традиционной математики. На каждом шаге деления между соответствующими коэффициентами полиномов выполняется не вычитание, а операция сложения по модулю 2. На каждом шаге деления получается остаток, состоящий из r коэффициентов. Всего шагов деления s=1… n-r. Старший коэффициент полинома остатка всегда равен нулю, так что степень полинома остатка будет r-1. На каждом шаге проводить вычислении старшего коэффициента нет необходимости. Очередной коэффициент частного удобно брать из остатка вычисленного на предыдущем шаге. С учетом всего вышесказанного получаем математическую модель процедуры вычисления остатка:

Р_j⁰=A_n-r+j, j=0…r-1;

Р_j^S=A_n-r-s+g₀Р_r-1^S-1, j=0;

Р_j^S= Р_j-1^S-1+g_jР_r-1^S-1, j=0…r-1.

Р_j⁰ здесь — начальный остаток, а Р_j^S остаток после шага s.

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

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

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

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

{P [s] =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 с.