18.7.3. КОДЫ, ИСПРАВЛЯЮЩИЕ ОДИНОЧНЫЕ И ДВОЙНЫЕ ОШИБКИ

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

Упражнение. (16). Доказать это утверждение!

По крайней мере для половины значений существуют нелинейные коды, имеющие больше кодовых слов (см. теорему 34 гл. 2 и рис. ПА.2.).

Задачи (нерешенные). (18.1). Найти величину для рис. ПА.1 для значений

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

(18.2). Что представляет собой двоичный линейный код наибольшей длины, исправляющий двойные ошибки и имеющий фиксированную избыточность где Обозначим эту длину через Известны следующие значения этой величины (из работы Хелгерта и Стинаффа

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

(i). Примитивные коды БЧХ с параметрами Однако они всегда хуже следующего семейства кодов.

(ii). Непримитивные коды БЧХ с параметрами получаемые укорочением кода длины порождающий многочлен которого имеет корни .

(iii). Коды Препараты с параметрами для четных значений .

(iv). Коды Препараты, расширенные с помощью конструкции X, с параметрами (18.16).

(v). Код Адамара из § 2.3 с параметрами (11, 24, 5) и рассмотренный в примере -код.

Кроме того, известны следующие коды, исправляющие двойные ошибки:

(vi). Приведенные ниже в упражнении (28)

укороченные коды БЧХ.

(vii). Укороченный альтернантный -код (Хелгерт [633]) и укороченный обобщенный -код БЧХ (Чень и Чой [286]).

(viii). Квазисовершенный -ход Вагнера ([1378]).

Задача (нерешенная). (18.3). Предложить простой способ построения последнего кода.

Обозначим через длину двоичного кода, исправляющего двойные ошибки (линейного или нелинейного) наибольшей длины, имеющего заданную избыточность Конечно, Из следует, что

Упражнение (17). Показать, что [Указание. Воспользоваться следствием 14 гл. 17.]

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

качестве выберем код Хэмминга — код с расстоянием , имеющий избыточность и наибольшую длину

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

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

Упражнения. (18). Показать, что для четных выполняется неравенство

(19). Показать, что

Известные нам наилучшие нижние оценки величины изображены на рис. ПА.2 (и в таблице II работы [1237]). Единственными известными точными значениями являются

(см. упражнение (17)). Кроме того, или 20.

Задача (нерешенная). (18.4). Найти величину

Еще меньше известно о кодах, исправляющих тройные ошибки!