Конструкции плотно упакованных кодов и нижние оценки их числа

• Автор: Кротов, Денис Станиславович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 64 с.

Содержание
Введение
1. Совершенные двоичные коды, исправляющие одну ошибку
1.1. Необходимые обозначения и вспомогательные утверждения
1.2. Комбинированная конструкция совершенных двоичных кодов
1.3. Нижние оценки числа т-квазигрупп порядка 4 и числа совершенных двоичных кодов
1.3.1. Нижняя оценка числа совершенных кодов через число т-квазигрупп
1.3.2. Построение т-квазигрупп порядка
1.4. Нелинейные совершенные коды
1.4.1. Основные понятия и обозначения
1.4.2. Конструкция Нелинейных расширенных совершенных кодов
1.4.3. Попарная неэквивалентность построенных кодов
1.4.4. Несуществование (п, 4"/4п, 4)4-кодов, неэквивалентных построенным
1.4.5. Индуктивное построение кодов С1’’’2
2. Плотно упакованные троичные равновесные коды
2.1. Необходимые обозначения и вспомогательные утверждения
2.1.1. Совершенные Х-коды и совершенные паросоче-тания в Еп
2.2. Индуктивное построение совершенных троичных равновесных кодов с расстоянием
2.2.1. Комбинированная конструкция Х-кодов
2.2.2. Нижняя оценка числа Х-кодов
2.3. Класс (п,5;?г — 1)з-кодов,
плотно упакованных в {п, п)
Литература
Введение
Объектом исследования в данной работе являются плотно упакованные двоичные коды и плотно упакованные троичные равновесные коды. В главе 1 приведены конструкции плотно упакованных, или совершенных, двоичных кодов (отметим, что двоичные коды также являются частным случаем троичных равновесных кодов), глава 2 полностью посвящена плотно упакованным троичным равновесным кодам.
В теории кодов, исправляющих ошибки, большое внимание уделяется совершенным, или плотно упакованным, кодам. В. А. Зиновьевым и В. К. Леонтьевым [10, 11, 12] (независимо
А. Титвайненом [46]) было показано, что не существует других нетривиальных совершенных д-ичных кодов, кроме кодов длины п = с параметрами кодов Хемминга (га, дп-<;, 3) (мощность <["-1:, кодовое расстояние 3) и кодов Голея - двоичного (23, 212, 7) и троичного (11,36, 5)-кодов. Последние два кода единственны с точностью до эквивалентности. Ю. Л. Васильев [4] построил первый класс неэквивалентных кодов с параметрами двоичных кодов Хемминга, опровергнув гипотезу о том, что класс совершенных кодов с расстоянием 3 также исчерпывается только линейными кодами Хемминга. Возникшая таким образом задача описания всех совершенных двоичных (а также д-ичных) кодов с расстоянием 3 до сих пор не решена ввиду большой сложности.
Известные результаты по теории совершенных кодов условно делятся на два направления: построение новых совершенных кодов (к этому направлению относится данная работа), в том числе кодов с новыми нетривиальными свойствами, и изучение свойств всех совершенных кодов.
Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. С. П. Ллойд [35] и независимо Г. С. Шапиро и Д. Л. Злотник [21] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит ни от выбора этой вершины, ни от выбора совершенного кода. Ф. Дельсарт [27] и независимо А. К. Пу-латов [18] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (га + 1)/2 зави-
Введение

сит только от размерности грани. С. В. Августинович [1] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес (п + 1)/2. А. Ю. Васильевой в работах [5, 6, 7, 8, 47] был существенно расширен список свойств, присущих всем совершенным двоичным кодам, в частности, был установлен ряд обобщённых спектральных теорем и охарактеризовано множество всех кодов в терминах линейного многообразия в 2"-мерном евклидовом пространстве.
Конструкции совершенных двоичных кодов условно делятся на свитчинговые (свитчинг, или ” переключение” - замена некоторой ’’старой” части кода на ’’новую”) и конструкции произведения кодов. В некоторых конструкциях произведения также присутствует элемент свитчинга.
Перечислим известные конструкции бесконечных классов совершенных двоичных кодов. Первый класс нелинейных кодов был построен Ю. Л. Васильевым [4] в 1962 г. В 1977 г. О. Хеден [31] построил коды, неэквивалентные кодам Васильева. Коды, описанные Ф. И. Соловьёвой [19] в 1981г., строго содержат коды Хедена. Два года спустя К. Фелпс [40] независимо переот-крыл конструкцию Соловьёвой и затем в 1984г. обобщил её конструкцией [41], использующей га-квазигруппы. Коды, построенные Дж.-М. Лабором [33], строго содержатся в конструкции Хедена. В 1986 г. М. Моллар [39] описал конструкцию произведения кодов, обобщающую коды Васильева. В 1970 г. и 1988 г. В. А. Зиновьев [9] привёл две конструкции совершенных двоичных кодов на основе конкатенации. В 1988 г. Ф. И. Соловьёва представила ещё один класс совершенных кодов [20], обобщив его в [43]. Алгебраическая конструкция Х4-линейных совершенных кодов описана в 1994г. в работе [30]. Эти коды (которые можно описать также как частный случай кодов Васильева) представляют интерес как пример нелинейных транзитивных кодов - любой кодовый вектор при помощи автоморфизма кода можно перевести в нулевой вектор. Там же показано, что расширенный совершенный код Хемминга длины больше 16 не является -линейным. В 1994 г. Т. Этцион и А. Вард и [28] описали класс совершенных кодов полного ранга. В этой же работе предложен способ построения совершенных кодов при помощи так называемых совершенных сегментаций. В 1995 г. К. Фелпс и М. ЛеВан построили совершенные коды, размерности ядер которых принимают все
1.4 Z-линейные совершенные коды

цы Odd(An,r2) состоит из двоек и получается удвоением первой строки матрицы АП,Г2_1.
Ь) Матрица А*'1-1,1 совпадает с Even(Aru°) и получается из Odd(Ari,°) вычитанием из последней строки (состоящей из единиц и троек) первой. □
Если С С Z", то через еиеп(С) обозначим множество { (0, - Сп—2) £ Z ' j (со, 0, С2, 0, . , Сга_2, Q) С С},
через odd(C) обозначим множество
{(ci,c3
Аналогично определим even(C) и odd(C) для С С Еп.
Следующие три утверждения вытекают непосредственно из определений.
Утверждение 7. Пусть С и Б - кватернарные коды длины п и п/2 соответственно. Тогда
a) В = even(C) если и только если В = even (С),
b) В = odd(C) если и только если В = odd(C).
Утверждение 8. Пусть С С Еп, у € Еп и у _L С. Тогда Even(y) A. even(C) и Odd(y) ± odd(C).
Утверждение 9. Пусть А - проверочная матрица кватер-нарного кода С. Тогда Even(A) - проверочная матрица кода even(C), a Odd(A) - проверочная матрица Kodaodd(C).
Из утверждений 6, 9 и 7 вытекает
Следствие 4.
a) Если Г > 0, Гг > 0 — целые числа, то even(Cn'r2) — odd(Cru’’2) = С™-1;
b) если ?'1 > 0 - целое число, то even(Cu()) — odd(Cri'°) = С"’1-1,1.
Рангом двоичного кода С (обозначается rank(C)) называется максимальное число линейно независимых векторов из С. Ранг равен длине кода минус максимальное число линейно независимых векторов, ортогональных С. Если два кода, содержащие