В приемнике или случайной интерференцией при построчной передаче символов. Однако поскольку внутренний кодер формирует столбцы, такой способ передачи требует использования так называемой перемежающей памяти (corner-turning memory) между внутренним кодером и каналом. В такой памяти слова внутреннего кода записываются в столбцы до тех пор, пока не будет построено все кодовое слово каскадного кода, которое затем построчно считывается из памяти в канал.

Используя каскадный принцип построения кодов, можно даже сочетать блоковые и сверточные коды. В гл. 12 будет описан простой сверточный код с декодированием по Витерби, хорошо исправляющий отдельные ошибки в длинных последовательностях двоичных символов. В то же время большое число близко расположенных ошибок при декодировании по Витерби приведет к пакету ошибок. Для исправления этих пакетов может использоваться внешний код Рида-Соломона. Известно, что этот метод каскадирования кода Рида-Соломона и слабого, но простого сверточного кода является мощным орудием конструирования декодеров для каналов с гауссовским шумом.

7.9. КОДЫ ЮСТЕСЕНА

Любой код над полем GF (д") можно превратить в код над полем GF (q), «развернув» каждый "-ичный символ исходного кода в последовательность т q-тных символов. В результате из линейного (Л, /С)-кода над G/ (д"") получится линейный (mN, тК)-коА над GF (q). В кодовом слове минимального веса d* ненулевых символов запишутся в виде последовательности из md* символов, из которых только часть будут ненулевыми. Скорость полученного кода будет такая же, как и у исходного кода, а минимальное расстояние будет составлять много меньшую долю длины.

Это «развертывание» представляет собой простой способ построения кода, исправляющего многократные пакеты ошибок. Если исходный код имел минимальное расстояние, равное 5, то в результате получится код, исправляющий одиночные пакеты -ичных ошибок длины m + 1 и многие конфигурации из двух пакетов меньшей длины. Например, (п, к)-кол Рида-Соломона над GF (2") развертывается в двоичный [тп, т/г)-код, исправляющий многократные пакеты ошибок. Однако, как правило, такой код плохо исправляет случайные ошибки.

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

7.9. КОДЫ ЮСТЕСЕНА 233

реса. Эти коды могут служить примером построения хороших кодов с большой длиной. Алгоритмы декодирования кодов Юстесена еще не достаточно разработаны.

Кодовое слово {2mN, ш/О-кода Юстесена представляет собой \2т У. {сГ - 1)]-таблицу элементов поля GF (q). Построение кода Юстесена начинается с выбора фиксированного (Л, /С)-кода Рида-Соломона, содержащего столько слов, сколько должно содержаться в конструируемом коде Юстесена. Прежде всего построим начинающуюся с кодового слова с = (cq, с, Cjv i) кода Рида-Соломона (2 X Л)-таблицу над GF (q"):

Со Ci С2 . . . Cjr l

а% aCi aCa • • • a~Cjv i J *

Каждый элемент этой таблицы лежит в поле GF (q"). Заменим теперь каждый символ в таблице соответствующим ш-мёрным вектором-столбцом над GF (д). Получившаяся таблица элементов из GF (q) размера 2/п X будет образовывать одно кодовое слово кода Юстесена. Эту таблицу можно любым удобным образом преобразовать в вектор. После повторения такой процедуры для каждого слова кода Рида-Соломона получится код Юстесена.

Прежде всего заметим, что указанная процедура приводит к линейному коду. Это важно, поскольку в этом случае для определения минимального расстояния кода достаточно найти значение минимального веса в коде. Остановимся теперь на той особенности конструкции Юстесена, благодаря которой она относится к классу хороших кодов. Поскольку слова кода Рида-Соломона имеют вес не менее N ~ К + 1, каждая представляющая кодовое слово таблица содержит не менее - /С + 1 ненулевых столбцов. Далее, если в двух столбцах таблицы совпадают т верхних элементов, то в этих столбцах т нижних элементов обязательно будут различными. Таким образом, в таблице нет двух одинаковых ненулевых столбцов. Чтобы оценить минимальный вес кодового слова, допустим, что все - /С + 1 ненулевых столбцов различны и имеют минимальный возможный вес. Искомая оценка получится суммированием весов N - К -\- 2т-мерных векторов минимального веса.

Теорема 7.9.1. Для минимального расстояния (2mN, 2mK)-кода Юстесена, построенного из {N, К)-кода Рида-Соломона, При каждом I, удовлетворяющем неравенству

имеет место оценка d* S i{q-~

I{q-\y[":)NK\,

существует столбец веса /. Минимальное расстояние кода будет не меньше суммы весов

d*hi{q~-\y{;:\ °

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

Лемма 7.9.2. Для всех р, удовлетворяющих условию О < р < < 1/2, причем пр - целое число, имеет место неравенство

I L U2"«<p),

где Н (р) = -р log., (р) - {1-р) loga (1 - р).

Доказательство. Пусть К - произвольное положительное число. Справедлива следующая цепочка неравенств:

k = (1-р) п

<2*(;) = (1+2.

Отсюда получаем

Доказательство. Кодовое слово минимального веса содержит - /С + 1 различных ненулевых столбцов. Таким образом, вес этого слова не меньше веса слова, которое получится при записи в этих - /( + 1 столбцах - /С + 1 различных последовательностей длины 2т, имеющих минимальный вес.

Существует ("] способов выбора г ненулевых элементов в последовательности длины 2т, а число таких ненулевых элементов равняется q - 1. Следовательно, при любом /, удовлетворяющем неравенству