Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

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

Коды Рида-Соломона строятся сначала как коды над некоторым полем GF(q), где q обычно есть степень числа 2, q = 2p. Далее элементы поля GF(2p) представляются как двоичные векторы длины p. Таким образом, код Рида-Соломона хорошо приспособлен для исправления пачек ошибок длины p.

Пусть a - примитивный элемент поля GF(q), q = 2p. Рассмотрим элементы a, ..., a2t и многочлены (x - a), ..., (x - a2t) как многочлены с коэффициентами из поля GF(q). Тогда, согласно результатам предыдущих параграфов, произведение g(x) = (x - a)× ...×(x - a2t)  можно выбрать в качестве порождающего многочлена для кода, слова которого имеют длину n = q - 1 и состоят из элементов поля GF(q). Данный код является циклическим (n, n-2t)-кодом, т. е. имеет 2t проверочных символов (из поля GF(q)). Согласно теореме 8.1, данный код исправляет любую комбинацию из t или менее ошибок.

Представим теперь каждый символ из поля GF(q), q = 2p, двоичным вектором длины p. Получим двоичный код длины pn, который имеет 2tp проверочных символов и исправляет любую комбинацию из tp или менее ошибок, если эти ошибки произошли только в двоичных наборах, которые заменяют t символов из поля GF(q).

Пример: Рассмотрим поле GF(q), q = 23, построенное по модулю неприводимого многочлена x3 + x + 1. Обозначим элементы поля 0, 1, ..., 7. Элемент 2 (010) является примитивным элементом. Соответственно 22 = 4. Рассмотрим многочлен (x - 2)(x - 4) = (x + 5)(x + 3) = x2 + 6x + 4 с коэффициентами из поля GF(23). Построим (4,2)-циклический код, слова которого состоят из символов поля GF(23) и имеют длину 4. Каждому кодовому слову соответствует многочлен степени не больше 3, который делится на многочлен x2 + 6x + 4. Согласно теореме 8.1. построенный код имеет расстояние не меньше 3, т. е. исправляет любую одиночную ошибку. После замены каждого символа из поля GF(23) соответствующим двоичным вектором мы получим двоичный код с длиной кодового слова 12, исправляющий все ошибки, которые произошли в одной из троек двоичных символов, заменяющих элементы поля GF(23).

Запишем степени элемента 2: 21 = 2, 22 = 4, 23 = 3, 24 = 6, 25 = 7, 26 = 5, 27 = 1. Пусть информационное слово равно (4,1). Умножив многочлен 4x + 1, соответствующий информационному слову (4,1), на порождающий многочлен кода x2 + 6x + 4 (над полем GF(23)), получим многочлен 4x3 + 4x2 + 4, соответствующий кодовому слову (4,4,0,4). Предположим, что при передаче кодового слова произошла ошибка, и принято слово (4,3,0,4). Разделим соответствующий многочлен 4x3 + 3x2 + 4 на многочлен x2 + 6x + 4 и получим остаток 4x + 1. Непосредственной проверкой можно убедиться, что остаток от деления многочлена 7x2 на многочлен x2 + 6x + 4 также равен 4x + 1, т. е. образующий смежного класса, которому принадлежит принятое слово (4,3,0,4) в стандартном расположении, равен (0,7,0,0).

        

Сложив принятое слово (4,3,0,4) с образующим (0,7,0,0) смежного класса, получим переданное кодовое слово (4,4,0,4), т. е. ошибка будет исправлена.

Заметим, что если данный код рассматривать как двоичный (12,6)-код, то его расстояние не может быть больше 3, так как кодовое слово (4,4,0,4) в двоичной записи имеет вес 3. Таким образом, несмотря на то, что код, построенный по многочлену x2 + 6x + 4, не исправляет все комбинации из 3 или менее ошибок, данный код исправляет комбинацию из 3 ошибок, которые произошли в двоичной пачке символов, заменяющих символ из поля Галуа GF(23).