9.11. КОДЫ НЕ-БЧХ, ИСПРАВЛЯЮЩИЕ ТРИ ОШИБКИ

В этом заключительном параграфе описываются двоичные коды не-БЧХ, исправляющие три ошибки. Эти коды аналогичны кодам БЧХ и имеют те же самые параметры, но техника

определения их минимального расстояния отлична от рассмотренной для кодов БЧХ и представляет самостоятельный интерес. Эти коды будут использованы в § 15.7 для построения нелинейных кодов Геталса.

Блоковая длина равна где — примитивный элемент поля и -минимальный многочлен элемента

Порождающий многочлен двоичного кода БЧХ, исправляющего три ошибки, равен Порождающий многочлен нового кода равен где Согласно упражнению (14) гл. 7 степень обоих многочленов равна Первыми кодами в новом семействе являются:

-код с порождающим многочленом -обычный код БЧХ с исправлением трех ошибок.

-код с порождающим многочленом

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

Пусть представляет собой многочленную запись двоичного вектора длины весом и локаторами Заметим, что

Элементы множества X могут быть представлены как двоичные -последовательности. Обозначим через V а подпространство в порожденное этими «-последовательностями.

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

Каждый вектор подпространства представляет собой некоторый элемент из Положим Так как то для

Из результатов § 4.9 следует, что -линеаризованный многочлен, т. е.

Лемма 25. Если слово кода ранга то а для всех

Доказательство. Для рассматриваемого имеем:

где

Для всех согласно (9.42) выполняется равенство следовательно, по (9.41)

Выделяя первое слагаемое, имеем:

Далее согласно определению кода

следовательно, а Более того, для —2

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

Следствие 26. Если -слово кода ранга то

Доказательство. Из леммы 25 вытекает, что Тогда согласно границе

Теорема 27. Минимальное расстояние кода равно по меньшей мере 5.

Доказательство. Если то (по следствию 26), что приводит к противоречию.

Упражнения. (10). Показать, что если то т. е.

где линейно независимы над

(11). Пусть -слово четного веса кода Хэмминга с порождающим многочленом Пусть вектор, задаваемый множеством Показать, что также принадлежит коду Хэмминга.

Наконец, найдем минимальное расстояние рассматриваемого кода, исправляющего три ошибки.

Теорема 28. Пусть с порождающим многочленом Тогда минимальное расстояние кода равно 7.

Доказательство. Пусть код Хэмминга с порождающим многочленом Тогда следовательно, минимальное расстояние кода не меньше 5.

Предположим, что вес вектора равен 5. Тогда согласно упражнению (10), Следовательно, что приводит к противоречию.

Предположим теперь, что Так как то Пусть и пусть -вектор, задаваемый множеством Мы покажем, что и это даст нам противоречие, так как Согласно упражнению (11) Кроме того, так как то

Аналогично

Задача (нерешенная). (9.7). Имеет ли код такой же весовой спектр, как и код БЧХ, исправляющий три ошибки? Если да, то не являются ли эти коды эквивалентными? (Мы предполагаем, что нет.)

ЗАМЕЧАНИЯ К ГЛ. 9

(см. скан)

(см. скан)

(см. скан)