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

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

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

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

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

Кодовое слово -кода Юстесена представляет собой Ьтаблицу элементов поля Построение кода Юстесена начинается с выбора фиксированного -кода Рида-Соломона, содержащего столько слов, сколько должно содержаться в конструируемом коде Юстесена. Прежде всего построим начинающуюся с кодового слова кода Рида-Соломона -таблицу над

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

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

Теорема 7.9.1. Для минимального расстояния Юстесена, построенного из -кода Рида-Соломона, при каждом удовлетворяющем неравенству

имеет место оценка

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

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

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

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

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

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

Выберем теперь к тогда

что доказывает лемму.

Лемма 7.9.3. Для любого множества различных ненулевых двоичных слов длины сумма весов слов удовлетворяет неравенству

где X — любое число в интервале (0, 1/2).

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

Таким образом, для каждого X существует не менее слов веса более Следовательно, сумма весов слов множества удовлетворяет неравенству

Лемма доказана.

Теорема 7.9.4. Пусть для каждого фиксированного Тогда при каждом целом Юстесена имеет скорость не менее и минимальное расстояние, удовлетворяющее неравенству

где функция от стремящаяся к нулю при

Доказательство. Поскольку и, следовательно, скорость кода превышает Кодовое слово с содержит не менее различных ненулевых столбцов, т. е. не менее различных ненулевых двоичных последовательностей длины Далее,

Выберем этих последовательностей длины Тогда условия леммы 7.9.3 удовлетворяются, и из этой леммы следует оценка

или

Полагая

приходим к утверждению теоремы.

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

При фиксированном отношение отделено от нуля при Коды Юстесена являются единственным известным классом кодов с заданной в явном виде конструкцией, для которых установлено это свойство

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

ЗАДАЧИ

(см. скан)

(см. скан)

(см. скан)

ЗАМЕЧАНИЯ

Коды БЧХ независимо открыли Хоквингем [1959] и Боуз и Рой-Чоудхури [1960]. Вскоре Горенстейн и Цирлер [19611 установили, что открытые ранее Ридом и Соломоном [19601 коды являются частным случаем недвоичных кодов БЧХ.

Поведение минимального расстояния и скорости кодов БЧХ большой длины исследовалось многими авторами на протяжении большого промежутка времени. Коды БЧХ длины становятся неудовлетворительными, когда эта длина оказывается много больше Для умеренных длин кодов так происходит потому, что в случае двоичных кодов на каждую исправляемую ошибку приходится порядка проверочных символов, а в случае кода с порядка проверочных символов. Асимптотическое поведение таких кодов несколько лучше, хотя все еще остается неудовлетворительным. Точное изложение вопросов потребовало бы значительных усилий.

Касами и Токура [1969] открыли бесконечный подкласс примитивных кодов БЧХ, для которых граница БЧХ строго меньше истинного минимвльного расстояния, первым примером такого кода был -код БЧХ с . Чинь [1970] придумвл примеры циклических кодов, которые лучше кодов БЧХ; одним из таких примеров является циклический -код.

Впервые процедура исправления ошибок для двоичных кодов БЧХ была предложена Питерсоном [1960], а для кодов БЧХ с произвольным алфавитом — Горенстенном и Цирлером [1961]. Чень [1964] и Форни 11965] упростили эту процедуру. Итеративный алгоритм нахождения многочлена локаторов ошибок был предложен Берлекэмпом [1968]. Месси [1969] представил этот алгоритм в виде процедуры построения авторегрессиоиных фальтров. Бартон [1971] показьл, как осуществлть алгоритм Берлекэмпа-Месси. не используя деления, хотя для вычисления значений ошибок деление все равио необходимо.

Сугияыа, Касахара, Хирасава и Намекава [1975] впервые предложили использовать при декодировании алгоритм Евклида. Велч и Шольц 119791 построили использующий разложение в непрерывную дробь декодер, совершенно эквивалентный декодеру, использующему алгоритм Евклида. Другой способ использования алгоритма Евклида при декодировании был предложен Мандельбаумом [19771 и будет рассмотрен в § 9.1