ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ. КОД РИДА – СОЛОМОНА

В данной работе рассматриваются базовые принципы помехоустойчивого кодирования и изучается один из способов кодирования – код Рида – Соломона.

Основные определения

Определение 1 Поле – алгебра над множеством F, образующая коммутативную группу по сложению над F и коммутативную группу по умножению над F/{0}, при выполняющемся свойстве дистрибутивности умножения относительно сложения.

Определение 2 Поле Галуа – поле, состоящее из конечного числа элементов. Обозначение –GF(p^m), где p^m– количество элементов в поле или индекс поля, p – характеристика поля, причем p – простое число.

Определение 3 Примитивный элемент конечного поля – генератор мультипликативной группы, первообразный корень степени p^m-1.

Определение 4 Расстояние Хэмминга – число позиций, в которых соответствующие символы слов одинаковой длины различны.

Определение 5 Кольцо – это алгебра над множеством F, образующая коммутативную группу по сложению над F и полугруппу по умножению, при свойстве дистрибутивности умножения относительно сложения.

Определение 6 Кольцо многочленов – кольцо, образованное многочленами с коэффициентами из другого кольца.

Определение 7 Неприводимый многочлен – многочлен, который не раскладывается на простые множители в кольце многочленов.

Определение 8 Факторизация – разбиение множества на непересекающиеся непустые множества или классы эквивалентности.

Введение

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

Постановка проблемы

Необходимо ознакомиться с принципами помехоустойчивого кодирования, математический инструмент, позволяющий найти ошибку и исправить её при работе с информацией. Рассмотреть код Рида – Соломона как один из способов кодирования и попытаться зашифровать и расшифровать данные с помощью кода.

Помехоустойчивое кодирование

Основным принципом помехоустойчивого кодирования является избыточность. При кодировании у нас есть определенный набор символов, с помощью которых мы образуем слова или кодовые комбинации. Мы работаем только с определенными словами, по-другому они называются разрешенные кодовые комбинации. Если произошла ошибка, наши разрешенные кодовые комбинации переходят в разряд запрещенных кодовых комбинаций. Получив такие слова, мы понимаем, что где-то произошла ошибка, и пытаемся исправить ее. Допустим мы используем kсимволов и составляем слово, которое мы хотим отправить. Затем, дополняя до n символов, по определенному алгоритму получаем разрешенную кодовую комбинацию, которую и передаём по каналу связи. При передаче произошла ошибка, и мы получили запрещенную кодовую комбинацию, которую по алгоритму распознаем, что она является запрещенной и исправляем ошибку.

На практике чаще всего используются линейные коды. Код Рида – Соломона – один из представителей линейных кодов. Количество ошибок, которое мы можем обнаружить, используя линейный код, можно выразить через минимальное расстояние Хэмминга, то есть минимальное расстояние среди всех кодовых комбинаций. Минимальное расстояние для линейного кода d=n-k+1. Тогда максимальное количество ошибок, которое можно обнаружить f=d-1. Другая важная характеристика это – корректирующая способность кода, то есть количество ошибок, которые возможно исправить. Корректирующая способность определяется как t=(d-1)/2, где t округляется в меньшую сторону. Линейный код обозначается как (n,k). Все комбинации линейного кода образуют линейное пространство над полем. Для кода Рида – Соломона используется поле Галуа.

Поле Галуа

Рассмотрим, как образуется поле Галуа GF(p^m). Пусть m=1, тогда GF(p) – простое поле. Пример GF(7) на Рис.1.

Рисунок 1. Поле Галуа GF(7)

Красным выделены примитивные элементы. Как видно из рисунка, степени этих чисел образует мультипликативную группу. При работе с кодом Рида – Соломона на практике используется поле Галуа с характеристикой 2. Рассмотрим GF(2³) на Рис. 2.

Рисунок 2. Поле Галуа GF(2³)

Характеристика поля Галуа влияет на то, какое кольцо многочленов мы используем для построения поля. В данном случаем мы находимся в кольце многочленов с коэффициентами 0 и 1, так как характеристика поля равна 2. Чтобы получить элементы поля, факторизуем наше кольцо по неприводимому многочлену x³ +x² +1, старшая степень зависит от степени характеристики поля. Получим класс эквивалентности с различными остатками при делении на x³ +x² +1.

Код Рида–Соломона

Перейдем непосредственно к самому коду Рида – Соломона. Существуют два способа кодирования: систематический и несистематический. При несистематическом кодировании информационное слово умножается на неприводимый порождающий многочлен поля Галуа. При систематическом кодировании процедура кодирования состоит из нескольких шагов. Во-первых, к нашему информационному слову мы должны до писать 2t нулей, получая новый многочлен. Полученный полином делится на порождающий многочлен, остаток приписывается к делителю, то есть просто складывается. Существует еще одна процедура кодирования – дискретное преобразование Фурье (ДПФ).

Рассмотрим подробнее несистематическое кодирование. Для получения кодовой комбинации, нам необходимо получить порождающий многочлен. Общая формула для порождающий многочлена: g(x)=(x-α^l)( x- α^l+1 )…(x-α^l+d-1).α-примитивный элемент поле Галуа, l–число, на практике применяют равное 1 или количество проверочных символов кода.

 Пусть дан код (7,3). Данный код может распознать 4 ошибки и исправить 2 ошибки. Порождающий многочлен для данного кода равен g(x)=(x- α)( x- α²)(x- α³)(x- α⁴). Пусть информационный многочлен имеет вид m(x)= α⁴x² +x+α³ . Кодовое слово несистематического кода будет выглядеть следующим образом: c(x) = m(x)g(x) =α⁴x⁶ + αx⁵ + α⁶ x⁴+ α⁵ x+α⁴.

Перейдем к операции декодирования. Пусть мы приняли полином r(x) = v(x)+e(x), где v(x) – переданный полином, e(x) – полином ошибок.e(x) =e_j1x^j1+…e_jnx^jn, где nt (максимальное количество ошибок, которое может исправить код). Множество { e_j1…e_jn} – значения ошибок, e_jпринадлежитGF(p^m), а {α^j1… α^jn} – локаторы ошибок.

Синдромы ошибок будут равны:

Многочлен локаторов ошибок:

Получаем ключевую систему уравнений относительно коэффициентов.

Вся задача сводится к решению данной системы. Существуют несколько алгоритмов решения системы: алгоритм Берлекемпа – Мэсси, алгоритм Евклида и прямое решение. Рассмотрим алгоритм Евклида.

Пусть получен многочлен r(x) = αx²+α5x4. При кодировании начальный многочлен выбирается равным r₀(x)=x^d. В коде (7,3) d=7-3+1=5, тогда начальный многочлен равен x⁵ . Синдром будет равен S(x) = 1+ α⁶x+ α⁵x² +αx³ +αx⁴ . Многочлен b₀(x) = 0, b₁ (x) = 1. На 1 шаге при делении r₀(x) на S(x) в остатке получаем многочлен r₁(x) = α⁵x³+x²+αx+α⁶, q₂(x) = α⁶x+ α⁶, b₂(x) = b₀(x)+q₂(x)b₁(x). На 2 шаге r₂(x) = α⁶x²+ αx+ α³ . Алгоритм остановится, когда степень остаточного многочлена, равна количеству ошибок, которые может исправить код. В данном случае, когда степень будет равна 2. Многочлен b₃(x)= σ(x) = α³+ α⁴x+ α²x² , решая полным перебором мы находим j₁ = 2, j₂ = 4.

Заключение

В данной работе были изучены принципы помехоустойчивого кодирования, был рассмотрен один из методов кодирования – код Рида – Соломона.

Список литературы:

1. Арнольд В. И Динамика, статистика и проективная геометрия полей Галуа. Москва, издательство МЦНМО, 2005
2. Берлекэмп Э. Алгебраическая теория кодирования = AlgebraicCodingTheory. — М.: Мир, 1971. — С. 478.