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

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

Коды Рида-Соломона (РС) определены над полем . В дальнейшем рассматриваются коды над конечными полями характеристики , как наиболее распространенные. Поэтому символы кодовых слов являются элементами поля . Коды РС, таким образом, это не двоичные, а - ичные коды БЧХ длины . Они являются циклическими кодами с порождающим многочленом

.

(5.31)

где  – примитивный элемент поля ;  – целое;  – конструктивное расстояние кода.

Выбор длины кода  гарантирует, что многочлен (5.31) является делителем , и следовательно, всегда будет выполнено требование к порождающему многочлену циклического кода. Действительно, все ненулевые элементы поля ,  являются корнями многочленах , в чем легко убедиться подстановкой : , т.к. . Поэтому многочлен  представим в виде произведения линейных множителей  и делится на любой многочлен (5.31).

Слово кода РС имеет вид: , где  и  – соответственно информационные и избыточные символы, которые могут быть представлены -разрядными двоичными векторами. Число информационных символов , где  – степень порождающего полинома . Коды РС являются систематическими кодами с максимальным кодовым расстоянием , равным конструктивному .

Обозначение символов слов, длины кода, размерности, кодового расстояния прописными буквами , , ,  и  введено для того, чтобы отличить их от аналогичных параметров двоичных кодов.

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

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

При  код РС становится безызбыточным, его словами являются все  последовательностей, символами в которых служат элементы поля . Минимальное расстояние этого кода равно 1.

При  в кодовом слове имеется один проверочный символ, который равен взвешенной сумме информационных символов. Весами служат элементы поля . Так как последовательности из  информационных символов имеют минимальное расстояние, равное 1, то добавление проверочного символа, выбранного специальным образом, может увеличить кодовое расстояние до 2. Напомним, что для двоичных кодов один проверочный символ может быть связан с информационными единственным способом: он равен сумме всех информационных, что при  приводит к кодам с простой проверкой на четность. Таким образом, переход к недвоичным кодам (расширению двоичного поля, над которым задается код) предоставляет большие возможности для конструирования новых кодов.

Отметим и другие особенности кодов РС по сравнению с двоичными кодами. Так, расстояние между векторами над полем  по-прежнему определяется как расстояние Хэмминга, т. е. равно числу пар несовпадающих компонентов, хотя символы кодовых слов как -разрядные векторы могут отличаться друг от друга в  разрядах. Такое определение расстояния не учитывает, насколько сильно различаются символы слов, но зато позволяет упростить анализ кодов.

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

Проверочная матрица кода РС есть проверочная матрица кода БЧХ длины , являющаяся частью матрицы ДПФ последовательностей с компонентами из поля .

Особенности декодирования кодов РС по сравнению с двоичными кодами БЧХ связаны с тем, что вектор ошибки имеет компоненты  из поля . Поэтому при декодировании кодов РС недостаточно указать номера искаженных символов, надо еще определить, насколько искажены символы, т.е. найти значения  вектора ошибки. Последнее требование усложняет процедуру декодирования кодов РС по сравнению с декодированием двоичных кодов БЧХ.

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

Так как синдром не зависит от передаваемого слова , то для рассмотрения процедуры декодирования достаточно задать вектор ошибки . Допустим, что многочлен, описывающий вектор ошибки, , т.е. произошла двукратная ошибка, исказившая в слове  символы  и , причем принятые символы ,  остальные – .

Декодер по реализации  должен найти оценку вектора ошибки , а затем оценку переданного слова . Если оценка , то , и ошибка исправляется. Если , ошибка не исправляется.

Процедура нахождения  зависит от описания вектора ошибки . Для указания номеров искаженных символов воспользуемся многочленом локаторов ошибок  (см. 5.5.2). Для двоичных кодов многочлен  полностью определяет вектор ошибки . В случае кодов над полем , каковыми являются коды РС, необходимо еще указать значения ошибок , что делается с помощью так называемого многочлена значений ошибок  [3, 26]. Для нахождения  требуется знание обоих многочленов  и , так как

.

(5.32)

где    – номер искаженного символа;  – формальная производная многочлена  в точке , которая для кодов, заданных над полями характеристики 2, содержит только четные степени. Коэффициенты при нечетных степенях производной являются четными числами и обращаются в ноль.

Итак, произвольный вектор ошибки над полем  может быть задан с помощью двух многочленов  и . Отметим, что эти многочлены определены с точностью до постоянного множителя  – элемента поля . Многочлен  имеет множество корней, совпадающее с множеством корней многочлена , и следовательно, оба определяют одни и те же номера искаженных символов.

Главная задача декодера состоит в оценке многочленов  и . Если эти оценки правильно описывают реальную ошибку, т.е. множества корней о  и  совпадают, то такая ошибка исправляется. В противном случае исправления не произойдет.

Многочлены локаторов , значений ошибок  и синдрома  связаны ключевым уравнением [26, 30]:

.

(5.33)

Трудность решения этого уравнения состоит том, что в соответствии с принципом максимального правдоподобия должны быть найдены многочлены  и  минимальных степеней, причем степень  должна быть больше степени , но менее степени .

Разработаны различные методы решения ключевого уравнения, некоторые из которых уже упоминались в третьем разделе.

Заданная в примере конфигурация двукратной ошибки в соответствии с (5.29) описывается многочленом локаторов, имеющим корни, обратные элементам  и :

.

Напомним, что вычисления производятся в поле , пример которого дан в табл. 5.2. Сложение удобно выполнять, используя полиномиальное или векторное представление элементов поля, а умножение – степенное представление. Поэтому .

Этапы декодирования данного кода при сделанных предположениях о характере искажении описываются следующими операциями.

Этап 1. По принятой реализации символов  вычисляются 6 компонентов синдрома , являющихся коэффициентами ДПФ последовательности . Для заданного искажения  компоненты синдрома определяются по формуле

, .

Используя табл. 5.2 задания элементов поля , находим

.

Читателю предлагается самостоятельно произвести вычисления остальных коэффициентов ДПФ и убедиться, что , , , , .

Результатом выполнения первого этапа является многочлен синдрома

.

Этап 2. Декодер решает ключевое уравнение (5.33) при , оценивает многочлены  и  с помощью алгоритма Евклида нахождения НОД. Не вдаваясь в детали этого алгоритма, с которыми можно познакомиться в [26], приведем результат решения (5.33):

,  .

Анализ показывает, что , т.е. в данном случае многочлен локаторов определен правильно.

Этап 3. Исправление ошибок производится при сложении символов принятой комбинации  с компонентами  вектора ошибки на позициях, номера которых обратны корням многочлена . Корни  определяются путем непосредственной подстановки в многочлен всех ненулевых элементов поля , . Если , то предполагается, что искажен символ .

Проделав такую подстановку, найдем корни многочлена :  и . Действительно, для элемента :  .

Для оценки вектора ошибки , т.е. для определения  и , найдем производную многочлена локаторов  и с помощью формулы (5.32) Получим:

,
.

Оценка многочлена ошибки  совпадает с , по предположению исказившим кодовое слово. Поэтому , и двукратная ошибка исправлена.

В заключение рассмотрим декодирование данного кода, если кратность ошибки больше трех, например, . Такая ошибка описывается многочленом локаторов 4-й степени. Декодер, конечно, «не знает» о кратности произошедших искажений и выполняет алгоритм декодирования, предназначенный для исправления ошибок кратности не более 3.

На первом этапе определяется синдром, содержащий по-прежнему 6 компонентов. Синдром ненулевой, так как кратность ошибки меньше кодового расстояния , и ошибка кратности 4 обнаруживается. В результате решения ключевого уравнения (если это окажется возможным) будет найден многочлен локаторов, степень которого не превышает 3. Ясно, что множества корней многочленов разных степеней не совпадают (многочлен локаторов не имеет кратных корней). Поэтому корни , найденные на третьем этапе декодирования, будут неправильно указывать номера искаженных символов. Ошибка кратности 4 обнаруживается, но не исправляется.

Коды РС имеют важное теоретическое и практическое значение, так как при заданных  и  имеют максимальное кодовое расстояние, используются для обнаружения и исправления пакетов ошибок и построения высокоэффективных каскадных кодов.