2.7. СИСТЕМА ШТЕЙНЕРА S(5,6,12) И НЕЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ОДНУ ОШИБКУ

Лемма 29. Нелинейный код, состоящий из строк матрицы (см. рис. 2.13), попарных сумм этих строк и дополнений ко всем полученным векторам, является -кодом.

Доказательство. Всего имеется кодовых слова. Типичное кодовое слово имеет вид а или а где различные строки возможно Для того чтобы показать, что расстояние между кодовыми словами по крайней мере равно 3, мы должны рассмотреть четыре случая:

(i). согласно абзацу, предшествующему лемме 18.

(ii). Аналогично .

(iii). . В противном случае соответствующее кодовое слово кода 24 имело бы вес, меньший чем 8, что приводит к противоречию.

iv). Аналогично

Теорема 30. Кодовые слова расширенного (12, 132, 4)-кода образуют блоки системы Штейнера S(5, 6, 12).

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

Поэтому 132 блока покрывают различных векторов

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

Используя следствие 14, мы получаем системы Штейнера .

Нелинейные коды, исправляющие одну ошибку. Удобно переставить координаты -кода из теоремы 30 так, чтобы он содержал кодовое слово (или блок) Обозначим координаты через Теперь мы можем включить в этот код 12 векторов, изображенных на рис. 2.16, не уменьшая минимального расстояния, и получить (12, 144, 4)-код, который мы обозначим через

Рис. 2.16. Двенадцать добавочных кодовых слов

Лемма 31. В коде имеется кодовое слово (обозначим его с), находящееся на расстоянии 4 от 51 кодового слова.

Доказательство. Докажем, что в качестве слова с можно выбрать Для системы Штейнера S(5, 6, 12) индексы блоковых пересечений имеют следующий вид

Блоки, находящиеся от с на расстоянии 4, должны иметь с ним 4 общих элемента. Число таких блоков равно

Из кодовых слов, изображенных на рис. 2.16, шесть также находятся на расстоянии 4 от вектора с, что и дает общее число 51.

(Из этого доказательства ясно, что для любого кодового слова число кодовых слов, находящихся от него на расстоянии 4, не превосходит 51.)

Из кода построим четыре более коротких кода:

(i). Выбрав в коде 12 кодовые слова, для которых мы получим (11, 72, 4)-код Те же рассуждения, что и в лемме 31, показывают, что в коде имеется кодовое слово, находящееся на расстоянии 4 от 34 других слов.

(ii). Выбрав в коде кодовые слова, для которых мы получим -код . В коде имеется кодовое слово, находящееся на расстоянии 4 от 22 других слов.

(iii). Выбрав в коде кодовые слова, для которых мы получим -код который содержит нулевой вектор 0. В этом коде имеется слово, находящееся на расстоянии 4 от 30 других кодовых слов.

(iv). Выбрав в коде кодовые слова, для которых мы получим -код содержащий нулевой вектор 0. В коде имеется слово, находящееся на расстоянии 4 от 18 других слов. (Другой (9, 20, 4)-код был приведен в § 2.4.) Если в этом коде выбросить одну координату, то этот код станет (8, 20 3)-кодом.

Рис. 2.17. Код (8, 20, 3)

Другой способ построения (8, 20, 3)-кода показан на рис. 2.17. Отметим, что этот код является циклическим в том смысле, что циклический сдвиг любого кодового слова снова является кодовым словом.

Так как число кодовых слов не равно степени 2, ни один из приведенных кодов не является линейным. Как уже указывалось в § 2.4, код (9, 20, 4) оптимален.

Задачи (нерешенные) (2.4). Оптимальны ли коды с параметрами 12, 144, 4)? В настоящее время наилучшие известные оценки таковы: (см. гл. 17 и приложение А).

(2.5). Обобщить способ построения (12, 144, 4)-кода для нахождения других хороших нелинейных кодов с помощью матрицы Адамара, выбирая в качестве кодовых слов ее строки, суммы двух строк и т. д.

(2.6). Обобщить способ построения, изображенный на рис. 2.17, для нахождения хороших нелинейных циклических -кодов с длиной больше чем

Заметим, что имеется несколько неэквивалентных конструкций кодов так как 12 кодовых слов, изображенных на рис. 2.16, могут быть переставлены многими способами.