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

     Шмаргунов 492. ИДЗ.

     Код Рида-Соломона.

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).

Код Рида — Соломона является частным случаем БЧХ-кода.

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

Коды Рида — Соломона являются важным частным случаем БЧХ-кода, корни порождающего полинома которого лежат в том же поле, над которым строится код (m = 1). Пусть α — элементполя   порядка  . Если α — примитивный элемент, то его порядок равен q − 1, то есть  . Тогда нормированный полином g(x)минимальной степени над полем  , корнями которого являются d − 1 подряд идущих степеней   элемента α, является порождающим полиномом кода Рида — Соломона над полем  :

где l0 — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается l0 = 1. Степень многочлена   равна d − 1.

Длина полученного  кода n, минимальное расстояние d (минимальное расстояние d линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов, см.Линейный код). Код содержит r = d − 1 = deg(g(x)) проверочных символов, где deg() обозначает степень полинома; число информационных символов k = n − r = n − d + 1. Таким образом   и код Рида — Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона).

Кодовый полином c(x) может быть получен из информационного полинома m(x),  , путем перемножения m(x) и g(x):

c(x) = m(x)g(x).

Код Рида — Соломона над  , исправляющий t ошибок, требует 2t проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной t и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя 2tдополнительных проверочных символов исправляется t ошибок (и менее).

Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной t и менее, должен содержать, по меньшей мере, 2t проверочных символов.

Код, двойственный коду Рида — Соломона, есть также код  Рида-Соломона. Двойственным кодом  для циклического кода называется код, порожденный его проверочным многочленом.

Матрица   порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы Pk * (n − k) отличен от нуля.

При выкалывании или укорочении кода Рида-Соломона снова получается код Рида — Соломона. Выкалывание — операция, состоящая в удалении одного проверочного символа. Длина n кода уменьшается на единицу, размерность k сохраняется. Расстояние кода d должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен.Укорочение - фиксируем произвольный столбец (n,k,d) кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство. 

Примеры.

16-ричный (15,11) код Рида —  Соломона

Пусть t = 2,l0 = 1. Тогда

g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10

.

Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.

8-ричный (7,3) код Рида —  Соломона

Пусть t = 2,l0 = 4. Тогда

g(x) = (x − α4)(x − α5)(x − α6)(x − α0) = x4 + α6x3 + α6x2 + α3x + α

.

Пусть информационный многочлен имеет вид

m(x) = α4x2 + x + α3

.

Кодовое слово несистематического кода запишется в виде

c(x) = m(x)g(x) = (α4x2 + x + α3)(x4 + α6x3 + α6x2 + α3x + α) = α4x6 + αx5 + α6x4 + 0x3 + 0x2 + α5x + α4

что представляет собой  последовательность семи восьмеричных символов.