Конструкции плотно упакованных кодов и нижние оценки их числа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1. Совершенные двоичные коды, исправляющие одну ошибку

1.1. Необходимые обозначения и вспомогательные утверждения

1.2. Комбинированная конструкция совершенных двоичных кодов.

1.3. Нижние оценки числа m-квазигрупп порядка 4 и числа совершенных двоичных кодов.

1.3.1. Нижняя оценка числа совершенных кодов через число т-квазигрупп

1.3.2. Построение m-квазигрупп порядка 4.

1.4. ^-линейные совершенные коды.

1.4.1. Основные понятия и обозначения.

1.4.2. Конструкция ^-линейных расширенных совершенных кодов.

1.4.3. Попарная неэквивалентность построенных кодов

1.4.4. Несуществование (п, 4п/4гг, 4)4-кодов, неэквивалентных построенным

1.4.5. Индуктивное построение кодов СГиГ2.

2. Плотно упакованные троичные равновесные коды

2.1. Необходимые обозначения и вспомогательные утверждения

2.1.1. Совершенные Х-коды и совершенные паросочетания в Еп.

2.2. Индуктивное построение совершенных троичных равновесных кодов с расстоянием 3.

2.2.1. Комбинированная конструкция Х-кодов

2.2.2. Нижняя оценка числа Х-кодов.

2.3. Класс (гг,5;п — 1)з-кодов, плотно упакованных в Jz(n, п)

Объектом исследования в данной работе являются плотно упакованные двоичные коды и плотно упакованные троичные равновесные коды. В главе 1 приведены конструкции плотно упакованных, или совершенных, двоичных кодов (отметим, что двоичные коды также являются частным случаем троичных равновесных кодов), глава 2 полностью посвящена плотно упакованным троичным равновесным кодам.

В теории кодов, исправляющих ошибки, большое внимание уделяется совершенным, или плотно упакованным, кодам. В.А.Зиновьевым и В.К.Леонтьевым [10, 11, 12] (независимо А. Титвайненом [46]) было показано, что не существует других нетривиальных совершенных g-ичных кодов, кроме кодов длины п = с параметрами кодов Хемминга (мощность q"~k, кодовое расстояние 3) и кодов Голея - двоичного (23, 212, 7) и троичного (11, З6, 5)-кодов. Последние два кода единственны с точностью до эквивалентности. Ю. Л. Васильев [4] построил первый класс неэквивалентных кодов с параметрами двоичных кодов Хемминга, опровергнув гипотезу о том, что класс совершенных кодов с расстоянием 3 также исчерпывается только линейными кодами Хемминга. Возникшая таким образом задача описания всех совершенных двоичных (а также g-ичных) кодов с расстоянием 3 до сих пор не решена ввиду большой сложности.

Известные результаты по теории совершенных кодов условно делятся на два направления: построение новых совершенных кодов (к этому направлению относится данная работа), в том числе кодов с новыми нетривиальными свойствами, и изучение свойств всех совершенных кодов.

Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. С. П. Ллойд [35] и независимо Г. С. Шапиро и Д. Л. Злотник [21] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит ни от выбора этой вершины, ни от выбора совершенного кода. Ф. Дельсарт [27] и независимо А. К. Пу-латов [18] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (гг + 1)/2 зависит только от размерности грани. С. В. Августинович [1] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес (n + 1)/2. А.Ю.Васильевой в работах [5, б, 7, 8, 47] был существенно расширен список свойств, присущих всем совершенным двоичным кодам, в частности, был установлен ряд обобщённых спектральных теорем и охарактеризовано множество всех кодов в терминах линейного многообразия в 2п-мерном евклидовом пространстве.

Конструкции совершенных двоичных кодов условно делятся на свитчинговые (свитчинг, или "переключение" - замена некоторой "старой" части кода на "новую") и конструкции произведения кодов. В некоторых конструкциях произведения также присутствует элемент свитчинга.

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

Л0 Щ1-Iog(» + l) 9 ^ - log( п +1 ) совершенных кодов, дающии не менее чем 2 ' о различных совершенных кодов длины п, а в [3, 22] построили класс несистематических совершенных кодов для п > 255 (двоичный код мощности 2к систематический, если можно так выбрать к координат, называемых информационными, что в них кодовые слова принимают все возможные 2к наборов значений, каждый по одному разу). В 1997г. А. Лобстейн и В. А. Зиновьев предложили обобщенный метод конкатенации для построения совершенных кодов [36, 37]. В 1998 г. С. В. Августинович и Ф.И.Соловьёва [23], а также С.А.Малюгин [38] представили классы несистематических совершенных кодов (длин > 127 и > 15 соответственно), имеющих тривиальную группу автоморфизмов. В 1999 г. С. А. Малюгину удалось улучшить нижнюю оценку числа двоичn-f 1 . , . и , п — 3 ных совершенных кодов, построив не менее 2 2 таких кодов.

Наибольшее внимание в теории кодирования заслуженно уделяется двоичным кодам, и связано это с тем, что многие явления, имеющие место в общем д-ичном случае, могут быть исследованы в двоичном и затем обобщены. В последние годы более интенсивно стали изучаться также троичные коды. В диссертации М. Сванстрёма [44] изложена серия результатов по троичным равновесным кодам. Там же, а так же в [45] описан класс совершенных (п, 3; п — 1)з~кодов, п = 2к > 4 (совершенных троичных равновесных кодов длины п с весом п — 1 и расстоянием 3), построенный на основе циклического представления двоичного кода Хемминга. В таких кодах максимальное подмножество слов с одним и тем же носителем образует линейный двоичный совершенный код с расстоянием 3 - код Хемминга в алфавите {1,2} (в этом смысле этот код Хемминга содержится в соответствующем троичном равновесном коде). Дж. ванЛинт и Л. Толхьюзен показали в [34], что не существует нетривиальных совершенных равновесных кодов с расстоянием 3, кроме (п,3;п — 1)з-кодов и (п, 3; п)з-кодов.

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

Диссертация состоит из двух глав. Первая глава полностью посвящена совершенным двоичным кодам. Материал по совершенным двоичным кодам можно излагать, пользуясь терминологией совершенных кодов с расстоянием 3 или расширенных совершенных кодов с расстоянием 4, в зависимости от предпочтений авторов или специфики изложения. Перевод материала из одной терминологии в другую обычно несложен и, хотя иногда и требует преодоления некоторых терминологических трудностей, может привести к новым взглядам на те или иные явления. В данной работе отдаётся предпочтение преимущественно расширенным совершенным кодам.

В разделе 1.2 "Комбинированная конструкция совершенных двоичных кодов" приводится конструкция расширенных совершенных кодов, которая объединяет в себе элементы нескольких ранее известных способов построения совершенных кодов. Построенный в.Еп код (длины п+1) состоит из компонент (в тексте они называются ju-компонентами, где ц £ Ет+1, т+1 = 2к < n + 1), каждая из которых является частью кода Фелпса [41], кода Моллара [39], кода Малюгина [16], кода, построенного при помощи метода а-компонент [2], или построена каким-нибудь другим, может быть неизвестным на данный момент, способом. Таким образом, с одной стороны, новая конструкция выделяет общее звено в построении некоторых ранее известных кодов, с другой стороны, возникает новая подзадача задачи конструирования и описания совершенных кодов - конструирование и описание /./-компонент, которая интересна даже в частных случаях, например, при т + 1 = (п + 1)/4.

Частными случаями комбинированной конструкции являются обобщения конструкций Фелпса и Моллара, которые получаются за счёт возможности независимо выбирать параметры компонент. Интересным следствием является новое нетривиальное свойство совершенных кодов - "универсальность": для данного набора из М совершенных кодов длины г существует совершенный код длины mr + m + r, где М < содержащий все заданные коды (а также любые их сдвиги) в параллельных г-мерных гранях.

В разделе 1.3 приводится конструкция rra-квазигрупп порядка 4, которая даёт нижнюю оценку их числа и в сочетании с основанной на m-квазигруппах конструкцией совершенных кодов Фелпса [41] позволяет получить рекордную нижнюю оценку числа совершенных кодов, равную 2Z 3 I

1. Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2, №1. С. 4-6.

2. Августинович С. В., Соловьёва Ф. И. Построение совершенных двоичных кодов последовательными сдвигами «-компонент // Проблемы передачи информации. 1997. Т. 33, Вып.З. С. 15-21.

3. Августинович С. В., Соловьева Ф. И. О несистематических совершенных кодах // Проблемы передачи информации. 1996. Т. 32. Вып. 3. С. 47-50.

4. Васильев Ю. JI. О негрупповых плотно упакованных кодах // Проблемы кибернетики. М.: Наука, 1962. Вып. 8. С. 337-339.

5. Васильева А. Ю. Спектральные свойства совершенных двоичных (п,3)-кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2. №.2. С. 16-25.

6. Васильева А. Ю. О расстояниях между совершенными двоичными кодами // Дискрет, анализ и исслед. операций. Серия 1. 1998. Т. 5. №.4. С. 16-25.

7. Васильева А. Ю. Локальные спектры совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 1999. Т. 6. №. 1. С. 16-25.

8. Зиновьев В. А. Комбинаторные методы конструкции и анализа нелинейных кодов, исправляющих ошибки. Автореферат, док. дисс. М., 1988. 30с.

9. Зиновьев В. А., Леонтьев В. К. Теорема о несуществовании совершенных кодов над полями Галуа. М., 1973. (Препринт / ИППИ АН СССР).

10. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // М.: ИППИ, 1972. Вып. 1. С. 26-35.

11. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. 1973. Вып. 2. С. 123-132.

12. Кузьмин А. С., Нечаев А. А. Построение помехоустойчивых кодов с использованием линейных рекуррент над кольцами Галуа // Успехи математических наук. 1992. Т. 47, вып. 5. С. 183-184.

13. Кузьмин А. С., Нечаев А. А. Линейно представимые коды и код Кер-дока над произвольным полем Галуа характеристики 2 // Успехи математических наук. 1994. Т. 49, вып. 5. С. 165-166.

14. Мак-Вильямс Ф.Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

15. Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 1999. Т. 6, №4. С. 44-48.

16. Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1, вып. 4. С. 123-139.

17. Пулатов А. К. К структуре плотно упакованных (гг,3)-кодов // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1976. Вып. 29. С. 53-60.

18. Соловьёва Ф. И. О двоичных негрупповых кодах // Методы дискретного анализа в изучении булевых функций и графов: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1981. Вып. 37. С. 65-76.

19. Соловьёва Ф. И. Факторизация кодогенерирующих дизъюнктивных нормальных форм / / Методы дискретного анализа в изучении булевых функций и графов: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1988. Вып. 47. С. 66-88.

20. Шапиро Г. С., Злотник Д. JI. К математической теории кодов с исправлением ошибок // Кибернетический сб. М.: Изд-во иностр. лит., 1962. Вып. 5. С. 7-32.

21. Avgustinovich S.V., Solov'eva F.I. Existence of nonsystematic perfect binary codes // Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory, Sozopol, Bulgaria, June 1996. P. 15-19.

22. Avgustinovich S. V., Solov'eva F.I. Perfect binary codes with trivial au-tomotphism group // Proc. of Int. Workshop on Information Theory, Killarney, Ireland, June 1998. P. 114-115.

23. Avgustinovich S. V., Lobstein A. C., Solov'eva F. I. Partitions by perfect binary codes, using concatenation and latin squares // Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. June, 2000. P.45-50.

24. Delsarte P. Bounds for unrestricted codes by linear programming, Philips Res. Reports. 1972. V. 27, 272-289.

25. Etzion Т., Vardy A. Perfect binary codes: Constructions, properties and enumeration // IEEE Trans. Inform. Theory, 1994. Vol.40. N3. P. 754-763.

26. Hamburger P., Pippert R.E., and Weakley W.D. Oil a leverage problem in the hypercube // Networks, 1992. Vol.22. P. 435-439.

27. Hammons A. R., Jr, Kumar P. V., Calderbank A. R., Sloane N.J. A., Sole P. The ^-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inform. Theory., 1994. Vol.40, №2. P.301-319.

28. Heden O. A new construction of group and nongroup perfect codes // Inform, and Control, 1977. Vol.34. N4. P.314-323.

29. Kurakin V.L., Kuzmin A. S., Mikhalev A.V., and Nechaev A. A.1.near recurring sequences over rings and modules // J. of Math. Sciences, 1995. Vol.76, N6. P.2793-2915.

30. Lloyd S. P. Binary block coding, Bell Syst. Techn. J., 36 (1957) 517. (Русский перевод: С.П. Ллойд. Бинарное блочное кодирование // Кибернетический сб. М.: Изд-во иностр. лит., 1960. Вып. 1. С. 206-226.)

31. Lobstein А. С., Zinov'ev V. A. On new perfect binary nonlinear codes // Appl. Algebra Eng. Common. Comput., 1997. Vol.8. P. 415-420.

32. Lobstein A. C., Zinov'ev V. A. Constructions of perfect binary nonlinear codes // Proceedings of Sixth international workshop "Algebraic and combinatorial coding theory". Pskov, Russia, September, 6-12, 1998. P 249-254.

33. Malyugin S. A. Perfect codes with trivial automorphism group // Proc. of II Int. Workshop on Optimal Codes, Sozopol, Bulgaria, June 1998. P. 163-167.

34. Mollard M. A generalized parity function and its use in the construction of perfect codes // SIAM J. Algebraic Discrete Methods. 1986. Vol. 7. N 1. P. 113115.

35. Phelps К. T. A combinatorial construction of perfect codes // SIAM J. Algebraic Discrete Methods. 1983. Vol.4, N.3. P. 398-403.

36. Phelps К. T. A general product construction for error correcting codes // SIAM J. Algebraic Discrete Methods, 1984. Vol.5, N. 2. P. 224-228.

37. Solov'eva F. I. Constructions of perfect binary codes // Preprint 98-042. Univ. Bielefeld, 1998. 12p.

38. Svanstrom М. Ternary codes with weight constraints. Dissertation №572. Linkoping Univ., 1999.

39. Svanstrom M. A class of perfect ternary constant-weight codes // Desighns, Codes and Cryptography. 1999. Vol. 18, N 1-3. P. 223-230.

40. Tietavainen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. Vol.24, N1. P. 88-96.

41. Vasil'eva A. Yu. On centered characteristic function of perfect binary codes // Proceedings of Sixth international workshop "Algebraic and combinatorial coding theory". Pskov, Russia, September, 6-12, 1998. P. 224-227.

42. Кротов Д. С. О совершенном коде, содержащем в качестве подкодов заданный набор совершенных кодов // Дискрет, анализ и исслед. операций. Серия 1. 2000. Т. 7, №1. С. 40-48.

43. Кротов Д. С. Нижние оценки числа m-квазигрупп порядка 4 и числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 2000. Т. 7, №2. С. 47-53.

44. Кротов Д. С. Z4-линейные совершенные коды j j Международная конференция "Дискретный анализ и исследование операций": материалы конференции (Новосибирск, 26 июня 1 июля 2000). Новосибирск: Изд-во Института математики, 2000. С. 74.

45. Krotov D. S. Combining construction of perfect binary codes and of perfect ternary constant-weight codes // Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. June, 2000. P. 193-198.