10.7. КОДИРОВАНИЕ КОДОВ РИДА—СОЛОМОНА

Так как коды РС являются циклическими, к ним применим любой из методов кодирования, описанных в § 7 8 Однако некоторые практические преимущества имеет следующий простой метод

кодирования (фактически представляющий собой метод, описанный в оригинальной работе Рида и Соломона).

Пусть информационные символы, которые должны быть закодированы, и пусть

В качестве кодового слова, соответствующего и, выбирается вектор с, многочлен Мэттсона-Соломона которого равен где Таким образом,

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

Действительно, согласно равенству (8.8) многочлен являющийся МС-многочленом вектора с, равен

где .

Отсюда, приравнивая коэффициенты и пользуясь равенством справедливым в поле получаем, что

для Таким образом, вектор с принадлежит коду РС и описанная процедура является процедурой кодирования для этого кода. Заметим, однако, что это кодирование не является систематическим.

Определение. Предположим, что линейный или нелинейный -код над полем кодер кода отображает сообщение в кодовое слово Кодер называется систематическим, если имеются координаты такие, что т. е. если сообщение входит в кодовое слово без изменений.

Например, такой кодер:

является систематическим (причем ), в то время как тот же самый код может иметь несистематический кодер:

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

Упражнение. (5). Показать, что любой линейный код имеет систематический кодер. А что можно сказать о нелинейных кодах

Рассмотрим, например -код РС над описанный в примере 2 (§ 10.2). Кодер из § 7.8 отображает сообщение в кодовое слово . С другой стороны, только что описанный кодер отображает в кодовое слово

Упражнение. (6). Проверить два последних утверждения.

Рис. 10.6 Свойства кодов Рида — Со юуонэ

10.8. ОБОБЩЕННЫЕ КОДЫ РИДА—СОЛОМОНА

Несколько более общий класс кодов, чем коды получается, если выражение (10.6) заменить на следующую формулу:

где ненулевые элементы GF(q).

Выражение (10.6) соответствует случаю, когда для всех Это подсказывает дальнейшее обобщение.

Определение. Пусть где различные элементы и пусть где ненулевые (но не обязательно различные) элементы Тогда обобщенный

код обозначаемый через состоит из всех векторов вида

где пробегает все многочлены степени меньше К с коэффициентами из поля

Этот код представляет собой -код над Так как многочлен имеет самое большее корней, то минимальное расстояние кода равно по крайней мере следовательно, в точности равно Это код МДР.

Теорема 4 Код, дуальный -коду, является к -кодом для некоторого вектора

Доказательство Предположим сначала, что и пусть код дуален коду Тогда имеет размерность 1 и состоит из всех векторов, пропорциональных некоторому фиксированному вектору Мы должны показать, что все Вектор удовлетворяет следующим равенствам

или

Если произвольное то (10.10) дает систему уравнений относительно других матрица коэффициентов которой представляет собой матрицу Вандермонда Следовательно, по лемме 17 гл 4 получаем, что для всех игуг значит, все что невозможно

Но тогда дуален коду для всех так как в силу (10 10)

Из теоремы 4 вытекает, что проверочная матрица кода равна порождающей матрице кода которая имеет вид

В § 12.2 мы снова встретимся с этими кодами. Упражнение. (7). (а). Показать, что если где то

В каких случаях коды эквивалентны?

(c). Показать, что тогда и только тогда, когда где