2.8. ВВЕДЕНИЕ В КОД НОРДСТРОМА—РОБИНСОНА

Расширенный код Голея § 24 может быть использован для построения нескольких интересных нелинейных кодов, исправляющих две ошибки.

Построение. Удобно изменить порядок столбцов в коде так, чтобы он содержал кодовое слово Пусть порождающая матрица для этого нового варианта кода 24

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

Разделим все кодовые слова в соответствии с их значениями на первых семи позициях; всего имеется 27 возможностей, и для каждой из них в коде найдется кодовых слова. Таким образом, в коде имеется кодовых слов, которые, начинаются либо с семи нулей (и тогда восьмая координата тоже нуль), либо с шести нулей и одной единицы (при этом восьмая координата равна единице).

Определение. Выбрасывая первые восемь координат в этих 256 кодовых словах, получаем код Нордстрома — Робинсона

(см. рис. 2.18, на котором код заключен внутри двойных линий).

Теорема 32. Код Нордстрома — Робинсона представляет собой (16, 256, 6)-код.

Доказательство. Пусть различные слова кода полученные укорочением слов кода Так как то

Рис. 2.18. Построение кода Нордстрома — Робинсона

Заметим, что код составлен из линейного [16, 5, 8]-кода, обозначим его через (образованного теми словами кода первые восемь координат которых равны нулю), и семи его смежных классов в коде В гл. 15 будет приведено несколько обобщений кода Нордстрома — Робинсона, а именно коды Кердока и коды Препарата, также имеющие структуру подобного вида.

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

Так как код содержит вектор из единиц то его подкод содержит вектор Все другие слова кода должны тогда иметь вес 8. Поэтому весовой спектр кода таков:

Рассмотрим один из смежных классов кода в коде скажем, Ясно, что в смежном классе могут встречаться лишь веса:

Так как то наряду с вектором веса 14 смежный класс должен был бы содержать вектор веса 2, что невозможно. Аналогично Следовательно, весовой спектр кода таков:

(В гл. 14 мы увидим, что Я является кодом Рида-Маллера первого порядка, а векторы кода представляют собой экстремально нелинейные функции Объединяя все результаты вместе, мы находим, что весовой спектр кода имеет вид, показанный на рис. 2.19.

Упражнения. (15). Показать, что для любого слова с кода число кодовых слов, находящихся на растоянии от него, также задается рис. 2.19. Таким образом, код инвариантен относительно расстояния. [Указание. Рассмотреть весовой спектр кода с образованного сдвигом, и воспользоваться рис. 2.18.]

Таким образом, мы знаем, что в коде спектр расстояний равен его весовому спектру и задается рис. 2.19.

Рис. 2.19. Весовой спектр кода Нордстрома — Робинсона

Укорочением кода мы получаем коды (15, 128, 6), (14, 64, 6) и (13, 32, 6). Все четыре кода оптимальны Кроме того, известно, что коды (16, 256, 6), (15, 256, 5), (15, 128, 6), (14, 128, 5), (1,4, 64, 6), (13, 64, 5) и (13, 32, 6) единственны, но это неверно для укороченного (12, 32, 5)-кода.

Следующие упражнения дают другие способы построения -кода и

(16). (Ван Линт) Пусть

Показать, что вектор 0 и строки матриц образуют (12, 32, 5)-код, где

(17). (Семаков и Зиновьев). Пусть матрицы перестановок размера такие, что и пусть

Показать, что строки матриц и их дополнения образуют (16, 256, 6)-код, где

где черточка обозначает дополнение, нулевую матрицу.

Задача (нерешенная). (2.7). Обобщить конструкции упражнений (16) и (17).