8.9. КОДЫ ПРЕПАРАТЫ

Хороших классов нелинейных кодов известно мало, и среди них находится класс кодов Препараты. Начнем изучение этих кодов с построения в частотной области одного примера, а именно -кода Препараты.

Но прежде чем изучать коды Препараты, вернемся к рассмотренной в § 5.6 процедуре декодирования даоичных кодов БЧХ, исправляющих две ошибки; в этом случае взаимный многочлен локаторов ошибок выписывается явно; за исключением случая он равен

Частный случай соответствует случаю отсутствия ошибок и легко проверяегся. Если положить то многочлен локаторов ошибок будет включать и случай отсутствия ошибок, и в этом случае уравнение вырождается в уравнение и имеет корни случае одной ошибки уравнение принимает вид

и имеет корни

Сделаем замену переменных, полагая Тогдв новый многочлен, который мы также обозначим через будет иметь вид

Этот многочлен имеет корни в поле тогда и только тогда, когда равен нулю. В четных расширениях всегда и это условие преобразуется так:

Далее, в полях характеристики 2, согласно теореме 8.2.3. ровно половина элементов имеет равный нулю след. При каждом значении элемент может принимать только значений, которые образуют в подпространство размерности Один бит в «не используется». На первый взгляд может показаться, что на частоте кодового слова можно ввести дополнительный информации. Это невозможно, так как неиспользуемый элемента зависит от Но коды Препараты позволяют лучше распорядиться этим обстоятельством: если спектр лежит в расширении поля то можно переупорядочить другие информационные биты так, чтобы ввести дополнительный информационный -код Препараты над существует для каждого четного большего 2. По сравнению с соответствующим кодом БЧХ, исправляющим две ошибки, код Препараты всегда содержит один дополнительный информационный Мы рассмотрим только -код Препараты.

Определение 8.9.1. Двоичный -код Препараты определяется как множество двоичных слов длины 15, спектр которых удовлетворяет следующим ограничениям: где либо

либо

и, кроме того, выполняются условия сопряженности.

Отметим, что, согласно условиям сопряженности, так что может быть только элементом поля Так как представляет собой произвольный элемент поля а произвольный элемент поля то и вместе содержат

пять битов информации. Остальные три бита описываются восемью выборами так что код является -кодом.

Покажем теперь, как исправляются двойные ошибки, и тем самым докажем, что минимальное расстояние этого кода равно по меньшей мере 5. Пусть представляют собой спектральные компоненты принятого слова. Определим синдромы

Выбор приемнику не известен, но ограничен условиями определения 8.9.1. Далее,

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

Исключая получаем квадратное уравнение

Оно может быть разрешено относительно следующим образом. Сначала положим и решим получающееся при этом квадратное уравнение относительно А. Затем положим и решим получающееся линейное уравнение относительно В. Это даст нам три решения для пары Из доказательства приведенной ниже теоремы следует, что только одно из них удовлетворяет ограничениям определения 8.9.1.

Теорема 8.9.2. Минимальное расстояние -кода Препараты равно 5.

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

этого задача сводится к декодированию исправляющего две ошибки кода БЧХ.

Предположим, что произошло не более двух ошибок. Если то ошибок не произошло. Мы предполагаем, что было вычислено и оказалось отличным от нуля.

Сначала положим и найдем корни квадратного относительно А уравнения

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

Шаг 1. Сначала покажем, что рассматриваемое квадратное уравнение не может иметь двух решений, которые оба являются ненулевыми кубами. Если корни данного квадратного уравнения, то так что сумма двух корней также является ненулевым кубом. Необходимо только доказать, что в поле сумма двух ненулевых кубов не может быть равна ненулевому кубу. Выпишем множество ненулевых кубов

Тогда прямое вычисление всех возможных сумм дает множество

которое не содержит ненулевых кубов. Таким образом, в поле сумма двух ненулевых кубов не может быть ненулевым кубом, и поэтому не могут одновременно удовлетворять ограничениям определения 8.9.1.

Шаг 2. Предположим теперь, что и два решения исходного уравнения. Покажем, что оба они не могут удовлетворять накладываемым ограничениям. Разность двух уравнений дает

Пусть Тогда

Но как так и В являются ненулевыми элементами поля Следовательно, элемент А должен удовлетворять одному из следующих уравнений:

Перебирая все корни этих уравнений, получаем, что

Но в этом множестве не содержится ни одного куба. Таким образом, и не могут одновременно удовлетворять нашим ограничениям. Это завершает доказательство теоремы.

ЗАДАЧИ

(см. скан)

ЗАМЕЧАНИЯ

Спектральное описание кодов, контролирующих ошибки, можно найти в очень ранних работах, хотя связь с преобразованием Фурье не была сразу осознана. Спектральный декодер использовался в основополагающей работе Рида и Соломона [1960] для нахождения минимального расстояния предлагаемых кодов, но, так как описанный в этой работе декодер не имел практического значения, спектральные методы не изучались еще долгие годы. Мэттсон и Соломон [1961] ввели спектральный многочлен, сыгравший большую роль в теоретических исследованиях, но смысл спектрального многочлена как преобразования Фурье вновь не был осозиап, и тесная связь теории корректирующих кодов с обработкой сигналов опять осталась скрытой. Близкие идеи разрабатывал Мандельбаум [1979], но на языке интерполяции.

Преобразование Фурье над конечными полями рассматривал Поллард [1971], а использовать его в теории кодов, контролирующих ошибки, предложил Гор [1973], работа которого получила дальнейшее развитие в работах Ченн и Чоя [19751 и Лемпеля и Винограда [1977]. Приведенное в данной главе доказательство границы БЧХ частично использует перенесенное в частотную область доказательство Чеия [19721.

Идея расширения кода широко известна. Расширенные коды Рида-Соломона рассматривал Вулф [1969]. Конструкции расширения кодов БЧХ были предложены Андриановым и Сасковцом [1966]. Слоэном, Редди и Чннем [1972]; Касахарой, Сугиямой, Хирасавой и Намекавой [1975]. Описание конструкций в виде преобразований дал Блейхут [1980).

Альтернантные коды были введены Хельгертом [1974], который дал им такое название потому, что проверочная матрица этих кодов может быть записана в виде так называемой (в математической литературе) альтернантисш матрицы К альтернактным кодам относятся открытые ранее коды Гоппы [1970) Дельсарт [1975) предложил определять альтернантные коды как ограничения на подполе модифицированных кодов Рида-Соломона, так что его определение значительно отличается от исходного.

Коды Превараты имеют интересную историю. Препарата (1968) открыл этот каасс кодов в процессе исследования свойств наименьшего кода в классе, а именно -кода, известною под названием кода Нордстрома-Робинсона [1967]. Два последних автора построили этот нелинейный (15, 8, 5)-кода помощью ЭВМ как расширение ранее построенного Некдлером нелинейного (12, 5, 5)-кода [1962) или нелинейного (13, 6, 5)-кода Грина [1966]. В свою очередь коды Препараты стимулировали открытие еще более сложных нелинейных кодов, а именно низкоскоростных кодов Кердока (1972) и исправляющих три ошибки кодов Геталса [1976].