Материал: 636_Nosov_V.I._Seti_radiodostupa_CH.1_

Таблица 4.7 Некоторые примитивные полиномы

можно представить все степени . Для рассматриваемого случая в соответствии с рисунком 4.13 и выражением (4.33) необходимо представить значения

131

Отображение элементов поля в базисные элементы, которое описывается уравнением (4.31), можно проиллюстрировать с помощью схемы линейного регистра сдвига с обратной связью (Linear Feedback Shift Register — LFSR) (рис. 4.14). Схема генерирует (при m = 3) 2m -1 ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (4.35)-(4.36). Следует отметить, что показанная на рис. 4.14 обратная связь соответствует коэффициентам полинома f (X ) 1 X X 3 , как и в случае двоичных циклических кодов.

Пусть вначале схема находится в некотором состоянии, например, 100. При выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис. 4.13, циклически будет появляться в разрядах регистра сдвига. На данном конечном поле GF(23) можно определить две арифметические операции – сложение и умножение. В таблице 4.8 показана операция сложения, а в табл. 4.9 – операция умножения, но только для ненулевых элементов. Правила суммирования следуют из уравнений (4.34) и (4.35); и их можно доказать, обратившись к рисунку 4.13, поскольку сумму двух элементов поля можно рассчитать путем сложения (по модулю 2) соответствующих коэффициентов их базисных элементов. Правила умножения, указанные в таблице 4.9, следуют из обычной процедуры, в которой произведение элементов поля вычисляется путем сложения по модулю (2m - 1) их показателей степеней или, для данного случая, по модулю 7.

Рис. 3.18 Отображение элементов поля Галуа в базисные элементы

132

4.6.2 Кодирование Рида-Соломона

В уравнении (3.32) представлена наиболее распространенная форма

ошибочных битов в символе, которые может исправить код. Генерирующий полином для кода Рида-Соломона имеет следующий вид

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

133

полиномиальный генератор имеет порядок 2t, мы должны иметь в точности 2t последовательные степени , которые являются корнями полинома. Обозначим корни Р(X) как 2t . Нет необходимости начинать именно с корня это

можно сделать с помощью любой степени .

Возьмем к примеру код (7, 3) с возможностью коррекции двухсимвольных ошибок. Мы выразим полиномиальный генератор через 2t = п - k = 4 корня следующим образом

Поменяв порядок расположения членов полинома на обратный и заменив знаки "минус" на "плюс", так как над двоичным полем +1 = -1, полиномиальный генератор Р(X) можно будет представить следующим образом

Кодирование в систематической форме.

Так как код Рида-Соломона является циклическим, кодирование в систематической форме аналогично процедуре двоичного кодирования, разработанной в разделе, посвященном циклическим кодам. Мы можем осуществить сдвиг полинома сообщения D(Х) в крайние правые k разряды регистра кодового слова и произвести последующее прибавление полинома четности (или остатка от деления) R(Х) в крайние левые n-k разряды. Поэтому мы умножаем D(Х) на X n k , проделав алгебраическую операцию таким образом, что D(Х) оказывается сдвинутым вправо на п - k позиций. В разделе посвященном циклическому кодированию это показано на примере двоичного кодирования. Далее мы делим X n k D(X) на полиномиальный генератор Р(X), что можно записать следующим образом

(4.41)

X n k D( X ) Q( X )P( X ) R( X ).

134

Здесь Q(X) и R(Х) — это частное и остаток от полиномиального деления. Как и в случае двоичного кодирования, остаток будет четным. Уравнение (4.41) можно переписать следующим образом

Результирующий полином кодового слова T(X), с учетом уравнений (4.41) и (4.42), можно переписать следующим образом

Продемонстрируем шаги, подразумеваемые уравнениями (4.42) и (4.43), закодировав в соответствии с рисунком 4.13 сообщение из трех символов

с помощью кода Рида-Соломона (7,3), генератор которого определяется уравнением (4.40).

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

Затем, из уравнения (4.43), полином кодового слова можно записать следующим образом

T(X ) 0 2 X 4 X 2 6 X 3 1X 4 3 X 5 5 X 6. (4.46)

Систематическое кодирование с помощью (n-k) разрядного регистра сдвига.

135