Спектральные свойства совершенных двоичных кодов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Васильева, Анастасия Юрьевна

• Васильева, Анастасия Юрьевна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Васильева, Анастасия Юрьевна

Введение

1 Граневые спектры совершенных кодов

1.1 Обобщение теоремы Шапиро - Злотника.

1.2 Граневой спектр совершенного кода

1.3 К строению дополнений совершенных кодов.

1.4 Расстояния между совершенными кодами.

1.5 О мощности пересечения совершенного кода с ¿-мерной .гранью

2 Локальные и межвесовые спектры совершенных кодов

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

2.2 Свойства локальных спектров

2.3 Межвесовые спектры совершенных кодов.

3 Линейное представление характеристических функций совершенных кодов

3.1 Характеризация совершенных кодов в терминах линейного многообразия.

3.2 Свойства множества совершенных кодов.

3.3 Новое представление некоторых классов совершенных кодов

Введение диссертации (часть автореферата) на тему «Спектральные свойства совершенных двоичных кодов»

Объектом исследования в данной работе являются совершенные двоичные коды длины п с кодовым расстоянием 3. В диссертации устанавливаются некоторые структурные свойства таких кодов, и на этой основе проводится изучение множества всех совершенных двоичных кодов с расстоянием 3 и дается характеризация этого множества в терминах линейных многообразий.

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

Везде далее под совершенными кодами мы будем иметь ввиду совершенные двоичные коды с расстоянием 3, если специально не оговорено иное. Исключительное рассмотрение совершенных кодов с расстоянием 3 обусловлено несуществованием других совершенных д-ичных {я. > 2) кодов, кроме кодов с параметрами кода Хэмминга — длина п = (д* — 1)/(д— 1), мощность кода дп~*, расстояние между кодовыми вершинами й = 3 — и единственных с точностью до эквивалентности двоичного (23,212,7) и троичного (11,Зб,5)-кодов Голея, доказанным

В.А. Зиновьевым и В.К. Леонтьевым [12, 13, 14] и независимо А. Ти-твайненом [36]).

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

Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. В 1957 году С.П. Ллойд [29] и в 1959 году независимо Г.С. Шапиро и Д.Л. Злотник [35] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит ни от выбора этой вершины, ни от выбора совершенного кода. В 1972 году Ф. Дельсарт [23] и независимо в 1973 году А.К. Пулатов [16] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (п + 1)/2 зависит только от размерности грани. В 1995 году C.B. Августинович [2] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес (n + 1)/2.

Однако различных совершенных кодов весьма много. Первый мощный класс совершенных кодов был построен в 1962 году Ю.Л. Васильевым [5, 6] и содержит 2 2 неэквивалентных совершенных кодов, наилучшая на данный момент нижняя оценка количества совершенных кодов длины п получена в 1996 году C.B. Ав тт » roil a2aïi-lQs(n+1^2!iT§-lQe(n+1) густиновичем и Ф.И. Соловьевой [21] и равна тг 6 , а наилучшая верхняя оценка количества совершенных кодов получена в

1995 году C.B. Августиновичем [2] и равна 22" °е"+ +oelogn+ . Опишем некоторые свойства, свидетельствующие об отсутствии единообразия строения совершенных кодов.

Код С называется дистанционно регулярным, если выполнено следующее условие: если вершины х, у £ С находятся на расстоянии к, то количество вершин z € С, для которых расстояние до вершины х равно i и расстояние до вершины у равно j, зависит только от г, j и к, но не зависит от выбора вершин х и у. C.B. Августинович и Ф.И. Соловьева [4] доказали, что все совершенные коды длины 15 и более не являются дистанционно регулярными.

Два кода называются эквивалентными, если один из них можно перевести в другой последовательным применением некоторой перестановки координат и сдвига на некоторую вершину n-куба. Два кода называются изометричными, если существует отображение одного кода на другой с сохранением расстояния. C.B. Августинович показал [1], что любые два неэквивалентные совершенные кода неизометричны.

В 1986 году К. Фелпс [32] доказал, что любая конечная группа изоморфна группе перестановочных автоморфизмов (т.е. автоморфизмов, оставляющих на месте нулевую вершину) некоторого совершенного кода. В 1998 C.B. Августиновичем и Ф.И. Соловьевой [22] и С.А. Малюгиным [31] были построены совершенные коды с тривиальной группой автоморфизмов.

Совершенный код С называется систематическим, если существует такая log(n + 1)-мерная грань, что во всех параллельных ей гранях содержится ровно по одной вершине кода С. До 1996 года было неизвестно, существуют ли несистематические совершенные коды. C.B. Августинович и Ф.И. Соловьева [3, 20] построили такие коды для длин п = 2* — 1, £>8. В 1997 аналогичный результат для t = 4,5,6,7 был получен К. Фелпсом и М. ЛеВаном [34], а также для t = 4 A.M. Романовым [18].

Ядром кода называется множество таких вершин кода, что прибавление ко всем вершинам кода данной вершины оставляет код на месте. Ранг кода — это размерность наименьшего подпространства в n-кубе, содержащего код. К. Фелпс и М. ЛеВан [33] установили, что для произвольного t > 4 существуют совершенные коды длины п = 2' - 1 с размерностями ядер от 1 до 2* — t — 3. Т. Этцион и А. Варди [25] описали спектр возможных рангов совершенных кодов и построили для любого t > 4 совершенные коды полного ранга.

Перейдем к описанию результатов диссертации. В работе большое внимание уделяется рассмотрению пересечения граней га-мерного единичного куба с совершенным кодом. Большая часть дальнейших результатов диссертации опирается на изучение следующих двух структур расстояний внутри кода, связанных с гранями куба и являющихся обобщениями весового спектра кода.

Во-первых, исследуется структура расстояний от некоторой грани гс-куба до вершин совершенного кода, далее называемая граневым спектром кода относительно данной грани, т. е. для произвольного целого г мы интересуемся количеством вершин данного совершенного кода, находящихся на расстоянии г от данной грани п-куба. Оказалось, что граневой спектр зависит только от размерности исходной грани и мощности ее пересечения с кодом, причем эта зависимость получила аналитическое выражение. Исходя из этого, приводятся оценки естественным образом введенного расстояния между совершенными кодами в зависимости от того, насколько они различаются в некоторой грани куба. Главное же применение граневые спектры получают в доказательстве характеризации совершенных кодов длины п как точек 271-мерного евклидова пространства с координатами 0 и 1, принадлежащих некоторому несложно описываемому линейному многообразию. По поводу этого линейного многообразия следует отметить, что среди совершенных кодов из произвольного класса эквивалентных кодов найдется базис параллельного ему линейного подпространства.

Во-вторых, исследуется структура расстояний внутри грани п-куба от некоторой ее вершины до вершин совершенного кода, содержащихся в этой грани, далее называемая локальным спектром совершенного кода в данной грани относительно данной вершины. Здесь для произвольного целого г нас интересует, сколько кодовых вершин, принадлежащих данной грани, находятся на расстоянии г от данной вершины. Оказалось, что если мы возьмем две ортогональные грани в кубе, сумма размерностей которых равна гг, а они всегда пересекаются по единственной вершине, то локальный спектр в одной из них относительно этой вершины однозначно определяется локальным спектром в другой относительно этой же вершины. Следующее свойство совершенных кодов, опять же касающееся регулярности их строения, устанавливается при помощи только что изложенного факта: количество пар вершин совершенного кода, одна из которых имеет вес г, другая — вес находящихся на расстоянии А друг от друга, зависит только от г,Л и того, принадлежит ли нулевая вершина куба данному коду.

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

Будем называть п-мерным единичным кубом (п-кубом) множество Еп всех векторов длины п с компонентами из множества {0; 1}.

Обозначим через 0" (соответственно 1") вершину га-куба, все координаты которой равны нулю (единице).

Расстояние Хэмминга /?(х, у) между вершинами х и у из п-куба определяется как количество координат, в которых эти вершины различаются.

Вес Хэмминга ги£(х) вершины х из п-куба определяется как расстояние от вершины х до вершины 0".

Для произвольного г, 0 < г < га, через Т^ обозначим множество вершин гс-куба, имеющих вес Хэмминга i.

Обозначим через ег вершину (О1-1,1,0"~1), где единица стоит на ¿-м месте.

Через |х| обозначим сумму по модулю 2 координат вершины х.

Совершенный двоичный код С с расстоянием 3 - такое подмножество вершин из гс-куба, что шары радиуса 1 с центрами из С образуют разбиение гс-куба.

Будем называть т-мерной гранью гс-куба множество всех таких вершин из Еп, у которых данные (гс — ш) координат фиксированы.

Две т-мерные грани 7 и У назовем параллельными , если

7 = {х = (хи х2,., хп) € Еп | Х{ - а{, г £ {гь ., гт}}, У = {х = (ягь ®2,. • •, хп) € Еп | х{ = Ъь г £ {гь., гт}}.

Две грани — га-мерную грань 7 и (п — т)-мерную грань у1 — назовем ортогональными, если

7 = {х = (хи ■ - ■, хп) еЕп \х{ = аи1$ {гь . ,гт}},

7х = {х = (я?1, ®2, • ■ •, ®п) € -Б" | х{ = а», г € {и,., гт}}, где а = («1, а2, • ■ ■, - их единственная общая вершина.

Р{{х\ Ы) = Е}=о("~ I)"7 ^ ^ | ( ^ многочлен Кравчука, (см., например, [30]), где N - натуральное число и 0 < г < N.

Пусть С — совершенный код длины п и В — некоторое множество вершин п-куба. Обозначим через Vе (В) количество вершин кода С, принадлежащих этому множеству:

Vе (В) = \СПВ\.

Введем также величину

Д= ь°{В) - -М.,

71 + 1 которую неформально можно пояснить как "отклонение количества вершин совершенного кода С в множестве В от среднего по кубу". Если множество В состоит из одной вершины Ь, то вместо ^({Ь}) и АС'({Ь}) будем писать Vе"(Ь) и АС'(Ь) соответственно.

В разделе 1.1 главы 1 формулируется и доказывается весьма широкое обобщение теоремы Г.С. Шапиро и Д.Л. Злотника [35].

Систему множеств М = {М; С Еп\ 0 < г < назовем правильным расслоением, а множество Мо — его начальным слоем, если а) при любом 0 < г < д,

Д£ = {х€Яя | /»(х,М0) = |} где />(х,М0) = шт{/)(х,у)|у € М0}; б) при любом г, 0 < г < д, количество вершин слоя М;, находящихся на расстоянии 1 от данной вершины х £ М», не зависит от выбора вершины х и равно в) при любом г, 0 < г < д — 1, количество вершин слоя находящихся на расстоянии 1 от данной вершины х £ М», не зависит от выбора вершины х и равно щ.

Для произвольного совершенного кода С вектор назовем спектром кода С относительно расслоения М.

Теорема 1 утверждает, что спектр любого совершенного кода относительно правильного расслоения гс-куба однозначно определяется количеством кодовых вершин, принадлежащих начальному слою. В силу общности формулировки теорема не дает аналитического выражения для спектра. Ее доказательство проводится путем составления системы линейных алгебраических уравнений относительно величин

Vе = 0,

Большое значение имеет частный случай теоремы 1 — теорема 2, составляющая основное содержание раздела 1.2 главы 1. Здесь рассматривается граневое расслоение куба, т. е. такое, когда начальным слоем является некоторая ¿-мерная грань, и для любого г, не превосходящего п — к, г-й слой состоит из граней размерности параллельных начальной грани и находящихся на расстоянии г от нее. В этом случае нетрудно вычислить параметры {¿¿} и {и*} расслоения. Поэтому для системы уравнений, для которой в общем случае мы могли только утверждать единственность решения при заданном "разумном" значении Vе(Мо), в этой ситуации указывается явный вид решения в зависимости от Vе(Мо). Точнее говоря, исходя из системы линейных алгебраических уравнений, составляется линейное дифференциальное уравнение с начальным условием для производящей функции последовательности «/'(Мо),.,Ьс(Мп^к)-, из которого и находится вид этой функции: 2к

-¿-(1 + + (>(М0) - (1 + - х)

П+1 \ 71+1)

2+1

Поскольку по смыслу задачи производящая функция должна быть многочленом, то из вида полученной функции заключаем, что в случае к > ^ коэффициент Vе (Мо) — ^ должен быть равен '«улю. Таким образом, из теоремы о граневых спектрах вытекает теорема о равномерной распределенности вершин совершенного кода по граням большой размерности, являющаяся частным случаем результатов Ф. Дельсарта [23] и А.К. Пулатова [16]. При условии, что к < коэффициенты производящей функции выражаются через значения многочленов Кравчука:

Vе Vе(Мо) Ш

71+ 1 п +

71 + 1 к т.е. АС(М{) = Ас(М0)р> п — к

В разделе 1.3 главы 1 исследуется дополнение совершенного кода до п-куба. Граневую структуру произвольной булевой функции /(х) естественно рассматривать в терминах максимальных (нерасширяе-мых) граней, которые определяются как максимальные по включению грани, содержащиеся в множестве {х £ $п|/(х) = 1}. Для произвольного совершенного кода рассматривается характеристическая функция его дополнения и, соответственно, ее максимальные грани. В доказательствах всех утверждений этого параграфа используется теорема о граневых спектрах (теорема 2), и обычно в качестве начальной грани рассматривается некоторая максимальная грань дополнения совершенного кода. В работе [17] приводятся два утверждения, касающиеся максимальных граней дополнения кода Хэмминга. В теоремах 3 и 4 доказывается, что эти свойства являются характеристическими для линейных совершенных кодов. Они эквивалентны следующему утверждению: для произвольного нелинейного совершенного кода, во-первых, размерность хотя бы одной максимальной грани, не содержащей кодовые вершины, строго меньше (п—1)/2, во-вторых, существует хотя бы одна кодовая вершина, находящаяся на расстоянии 2 от некоторой максимальной грани, не содержащей кодовые вершины.

В разделе 1.4 главы 1 производится оценивание расстояния в, между двумя произвольными совершенными кодами, определяемого как мощность симметрической разности этих кодов. Вопрос о возможных расстояниях между совершенными кодами представляется важным для выяснения соотношений между различными кодами, т. е. структуры множества всех совершенных кодов длины п. Однако определение расстояния предполагает просмотр всех вершин данных кодов. В теореме 5 предлагается оценивать расстояние, просматривая только некоторую грань куба: если и Сг — произвольные совершенные коды, Г — произвольная ¿-мерная грань п-куба, к < (гс — 1)/2, то

Многочлены Кравчука рассматриваются в связи с различными вопросами теории кодирования и схем отношений (см, например, [27, 28]), однако почти всегда связанные с ними вычисления представляют собой отдельную весьма трудную задачу. Данный случай, видимо, не является исключением. Поэтому мы рассмотрим два частных случая, в которых соответствующие значения многочленов Кравчука принимают простой вид.

В случае к = О мы приходим к утверждению, которое впервые установили Т. Этцион и А. Варди [25], о том, что пересечение любых двух различных совершенных кодов С\ и Сч содержит не более — 2т~ где ьс»с>(Г)=\\С1Г)Т\-\С2т\вершин. В терминах расстояний это означает (см. следствие 5), что d{CuC2)>2^l\

В случае, когда размерность к грани Г равна (п—1)/2, утверждение теоремы 5 принимает следующий вид: d{CuC2) >

Из результатов главы 3 будет следовать, что для любых двух различных совершенных кодов существует ^^-мерная грань, в которой количества их вершин не совпадают. Поэтому из последней оценки также следует оценка расстояния, принадлежащая Т. Этциону и А. Варди. В статье этих авторов [25] было показано, что существуют совершенные коды, расстояние между которыми равно 2aiL. В данной работе для произвольного h, 0 < h < 2йз1/(га + 1) указываются совершенные коды С* и С|, на которых достигается оценка, полученная в случае к = ^уЦ т. е. существует такая (гг — 1)/2-мерная грань Г, что

Л = (Г) и d(ClС*2) =

К вопросу об оценке из теоремы 5 добавим, что параметр Л (Г) принимает те же значения, что и возможное количество кодовых вершин в грани размерности dim Г. А относительно этого параметра в разделе 1.5 главы 1 устанавливается (теорема 6), что для любого целого v, удовлетворяющего условию 0 < v < 2к¡{щ + 1), (га* = 2* — 1 — такая кодовая размерность, что (п^ —1)/2 < к < Пк) существует такой совершенный код, что в одной из граней гс-куба содержится ровно v вершин этого кода.

В главе 2 вводятся понятия локального и межвесового спектров кода, устанавливается взаимосвязь локальных спектров совершенного кода в ортогональных гранях, и затем на этой основе доказывается инвариантность межвесового спектра совершенного кода.

Пусть 7 — некоторая грань п-куба, и а — ее вершина. Обозначим через множество вершин грани 7, находящихся на расстоянии г от вершины а. Локальный спектр кода С в грани 7 относительно вершины а (кратко, (7, а)-локальный спектр) определим как вектор

В разделе 2.1 главы 2 также приводится вспомогательная лемма 4, связывающая линейными соотношениями компоненты локального спектра в произвольной грани 7 с компонентами локальных спектров в гранях на единицу большей размерности, содержащих грань 7.

Основное содержание раздела 2.1 составляет теорема о взаимоопределенности локальных спектров произвольного совершенного кода в двух ортогональных гранях относительно их общей вершины (теорема 7). Обозначая через

Г1 грань, ортогональную к грани Г и полагая, что а — их единственная общая вершина, сформулируем эту теорему.

Г1, а)-локальный спектр совершенного кода однозначно определяется (Г, а)-локальным спектром этого кода и задается коэффициентами разложения по степеням х функции

Л-М = гхт^ + *)""'+ п + 1

1 - + ЕЙ)* («"ЮС)) - ( * ))

Эта теорема доказывается по индукции, причем базис индукции опирается на уже упоминавшуюся ранее теорему о весовом спектре совершенного кода [29, 35]. На каждом последующем шаге, исходя из вспомогательной леммы, составляется линейное обыкновенное дифференциальное уравнение с начальным условием для производящей функции (Г1, а)-локального спектра и доказывается, что функция /г ему удовлетворяет.

На языке " отклонений от среднего" А формула из теоремы принимает более симметричный вид:

Е д^ргЧУ = (1 - х)п-Р-к(1 + х)п-^-к з=о ?=о

Поскольку сумма размерностей двух ортогональных граней равна п, то всегда размерность одной из них не превосходит Из аналитической записи связи (Гх, а)- и (Г, а)-локальных спектров видно, что локальный спектр в большей грани из этой пары ортогональных граней выражается через локальный спектр в меньшей. Пусть для определенности ЛтГ = к < !!=А. Тогда

Д^СГ1)) = £ (-1)'Дс(£°(Г))рг - к; п - 2к).

Ч+т=] V z /

В случае к > ^ аналогичное выражение выписать невозможно, однако можно доказать наличие линейной зависимости между компонентами (Г, а)-локального спектра (следствие 8).

Упомянем также следствия, содержащиеся в разделе 2.2 и касающиеся дополнений совершенных кодов и систематичности совершенных кодов. Относительно дополнений совершенных кодов в терминах локальных спектров можно сказать следующее (следствие 9): грань Г из п-куба лежит в дополнении совершенного кода С тогда и только тогда, когда локальные спектры кода С относительно вершин грани Г в гранях, ортогональных к Г и содержащих соответствующие вершины грани Г, совпадают. Из определения систематического совершенного кода и теоремы 7 непосредственно вытекает, что совершенный код С является систематическим тогда и только тогда, когда существует такая ^(гс + 1)-мерная грань, что во всех ортогональных к ей гранях локальные спектры кода С относительно содержащихся в них кодовых вершин совпадают (следствие 10).

Раздел 2.3 главы 2 направлен на исследование еще одного семейства спектральных параметров совершенных кодов, дающих картину расстояний между кодовыми вершинами, находящимися на двух данных уровнях n-куба. Назовем (г, ?)-весовым спектром кода С вектор где Т/-(С) равно количеству пар вершин совершенного кода, в которых одна вершина имеет вес г, а другая — вес j и расстояние между этими вершинами равно d. Совокупность всех (г, ^-весовых спектров будем называть межвесовым спектром кода. Основная теорема (теорема 8) этого раздела заключается в следующем: межвесовой спектр совершенного кода зависит только от принадлежности нулевой вершины гс~куба этому коду.

Для того, чтобы доказать эту теорему, предварительно доказываются три леммы (леммы 5, 6 и 7), описывающие связь некоторых сумм и сумм произведений компонент локальных спектров совершенного кода с компонентами весового спектра и межуровнего спектра этого кода. Лемма 8 является основной и содержит систему линейных алгебраических уравнений относительно компонент (г, У)-весового спектра, в правых частях которых стоят компоненты (г',/)-весовых спектров для г',/ < min(i,jf). Для составления такой системы кроме предварительно доказанных лемм существенно привлекается аналитическая запись связи локальных спектров совершенного кода С в ортогональных гранях. Грубо говоря, (г, ,?)-весовой спектр выражается через локальные спектры во всех гранях, содержащих вершину 1" и имеющих непустое пересечение с г-м и j-м уровнями n-куба. По теореме о взаимосвязи локальных спектров в ортогональных гранях эти выражения записываются через локальные спектры в гранях, все вершины которых имеют вес, строго меньший i и j. Теорема доказывается индукцией по минимуму из чисел i и j.

Отметим, что теорема о межвесовых спектрах совершенных кодов имеет связь с доказанной C.B. Августиновичем и Ф.И. Соловьевой [4] дистанционной нерегулярностью всех совершенных кодов длины не менее 15. Она означает, что даже при условии, что нулевая вершина принадлежит совершенному коду С, для произвольного с?, |г — < ё < г + У, количество вершин совершенного кода веса находящихся на расстоянии й от некоторой вершины веса г, вообще говоря, зависит от выбора вершины веса г. Из теоремы 5 следует, что при том же условии сумма таких количеств по всем вершинам веса i постоянна.

В главе 3 проводится изучение множества всех совершенных кодов длины п. Здесь устанавливается теорема 9, характеризующая совершенные коды как несложно задаваемое множество точек 2п-мерного евклидова пространства. Говоря точнее, это множество является пересечением множества вершин куба со стороной 1 с некоторым линейным многообразием размерности ^ ^ П1)/2 )" ^ это^ главе нас будут интересовать главным образом две функции на п-кубе — ^(х) и Д^(х) — называемые соответственно характеристической и центрированной характеристической функциями совершенного кода С. Перед описанием результата обозначим А = И^п+ц/г, N — 2" и введем функции /а, а € Еп, подпространство V и линейное многообразие V следующим образом: а(х) = (-1){а'х), х € Еп, где <а,х) = £"=1 ад, аеА г. п + 1

Теорема 10 утверждает, что действительнозначная функция, принимающая значения из множества {0; 1}, принадлежит линейному многообразию V тогда и только тогда, когда существует такой совершенный код С, что она является его характеристической функцией.

Несмотря на большую наглядность уже приведенной формулировки, для доказательства и дальнейшего применения более удобна другая, аналогичная формулировка (теорема 9): действительнозначная функция, принимающая значения из множества {—принадлежит линейному подпространству V тогда и только тогда, когда существует такой совершенный код С, что она является его центрированной характеристической функцией.

Доказательство этой теоремы проводится непосредственным вычислением коэффициентов разложения центрированной характеристической функции совершенного кода по системе функций {/а|а € Еп}, про которую известно, что она является ортогональным базисом пространства Н^. Отметим, что вычисление этих коэффициентов опирается на теорему о граневых спектрах совершенного кода и соответствующие формулы, полученные в разделе 1.2 главы 1. Далее обсуждаются возможности других подходов к доказательству этой теоремы с помощью схем отношений (схемы Хэмминга) и теории двойственности кодов.

Упомянутое ранее разложение центрированной характеристической функции совершенного кода будем называть его координатным представлением. Оказывается (следствие 13), координатное представление выражается через количества вершин данного совершенного кода в каждой из ^-мерных граней 7(а), содержащих нулевую вершину гс-куба и вершину аф Iя веса (гс — 1)/2:

Ас(х) = 2-^ £ Ас(7(а))/а(х). а£А

Поскольку теоремы 9 и 10 отделяют совершенные коды от прочих функций на гс-кубе, то возникает вопрос о внутренних взаимосвязях между центрированными характеристическими функциями совершенных кодов. Действительно, оказалось, что центрированные характеристические функции одних совершенных кодов можно с помощью линейного комбинирования выражать через центрированные характеристические функции других совершенных кодов, т. е. что среди центрированных характеристических функций совершенных кодов можно выбирать базисы подпространства V, причем большим количеством способов.

Множество всех совершенных кодов длины п разбивается на классы эквивалентных кодов. Теорема 11 из раздела 3.2 главы 3 утверждает, что базис подпространства V можно выбрать среди центрированных характеристических функций совершенных кодов из произвольного класса попарно эквивалентных. Эта теорема доказывается указанием линейного преобразования, переводящего множество центрированных характеристических функций совершенных кодов из произвольного класса попарно эквивалентных в систему функций {/а|а £ Л}, задающую подпространство V. Существенным моментом в доказательстве является то очевидное наблюдение, что в координатном представлении любого совершенного кода есть хотя бы один ненулевой коэффициент.

Следовательно, мощность произвольного класса попарно эквивалентных совершенных кодов не меньше, чем размерность подпространства V. Из этого с очевидностью следует оценка сверху для мощности группы автоморфизмов произвольного совершенного кода.

Из теоремы 11 вытекает, что центрированная характеристическая функция любого совершенного кода может быть представлена в виде линейной комбинации (над полем действительных чисел) центрированных характеристических функций совершенных кодов из произвольного класса попарно эквивалентных. Например, в качестве класса попарно эквивалентных кодов может быть выбран класс линейных совершенных кодов, т. е. кодов Хэмминга.

Последний раздел 3.3 главы 3 имеет целью отыскание координатных представлений некоторых известных классов совершенных кодов. Во-первых, это коды Хэмминга. В силу их линейности их центрированные характеристические функции выражаются через функции а|а € А} наиболее простым образом: в координатном представлении только п коэффициентов, отвечающих вершинам кода Адамара Я1, двойственного к данному коду Хэмминга Я", не равны нулю, причем их величины одинаковы: лЯ = ^тт Е Г

П + 1 а€#х\{0п}

Далее вычисляются координатные представления двух классов кодов, строящихся по двум известным конструкциям [5, 6] и [19]. Выбор конструкций определяется следующим фактором: эти конструкции хорошо обозримы и представляют два различные (хотя и весьма условно выделяемые) направления в построении новых совершенных кодов: построение сдвигами компонент (конструкция Васильева) и построение объединением декартовых произведений кодов (конструкция Соловьевой). Их координатные представления уже не отличаются такой простотой, как у кода Хэмминга, но позволяют прослеживать характерные свойства конструкций.

Действительно, в координатном представлении первой конструкции нетрудно заметить, что коэффициенты изменяются (относительно коэффициентов в представлении исходного кода, с которого и начинается построение — кода Хэмминга) в строгом соответствии с тем, сколько минимальных ¿-компонент оказались сдвинутыми. В координатном представлении второй конструкции прослеживаются две вещи: неполный ранг строящихся с ее помощью совершенных кодов и то, что в конструкции используются декартовы произведения. Первое обстоятельство отражается в том, что большинство координат оказываются равными нулю, а второе — в том, что ненулевые координаты могут быть вычислены с помощью произведения некоторых матриц.

Список литературы диссертационного исследования кандидат физико-математических наук Васильева, Анастасия Юрьевна, 1999 год

1. Августинович C.B. О изометричности совершенных двоичных кодов // Труды Ин-та Математики СО РАН. 1994. Т. 27. С. 3-5.

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

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

4. Августинович C.B., Соловьева Ф.И. О дистанционной регулярности совершенных двоичных кодов // Проблемы передачи информации. 1998. Т. 34. N. 3. С. 47-49.

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

6. Васильев Ю. JI. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм // Проблемы кибернетики. М: Наука, 1963. Вып. 10. С. 5-61.

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

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

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

10. Васильева А. Ю. Характеризация совершенных кодов через принадлежность линейному многообразию // XII Международная конференция "Проблемы теоретической кибернетики". Тезисы докладов, часть 1. М.; 1999. С. 31.

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

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

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

14. Зиновьев В.А. Комбинаторные методы построения и анализа нелинейных корректирующих кодов: Дисс. докт. физ.-мат. наук: 01.01.09. -Москва, 1988. 300 с.

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

16. Романов A.M. О несистематических совершенных кодах длины 15 // Дискрет, анализ и исслед. операций. 1997. Т. 4. N. 4. С. 75-78.

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

18. 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) 15-19.

19. Avgustinovich S.V., Solov'eva F.I., Construction of perfect binary codes by sequential translations of the г-components, Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory. Sozopol, Bulgaria. June (1996) 9-14.

20. Avgustinovich S.V., Solov'eva F.I., Perfect binary codes with trivial automotphism group, Proc. of Int. Workshop on Information Theory, Killarney, Ireland. June (1998) 114-115.

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

22. P. Delsarte An algebraic approach to the association scheme in coding theory, Philips Res. Reports. 1973. No. 10. (Русский перевод: Дель-сарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.: Мир, 1976.)

23. Etzion Т., Vardy A. Perfect binary codes: constructions, properties and enumeration // IEEE TYans. Inform. Theory. 1994. V. 40, N 3. P. 754-763.

24. Etzion Т., Vardy A., On perfect codes and tilings: problems and solutions, SIAM J. Discrete Math. 11 (2) (1998) 205-223.

25. Krasikov ILitsin S. On integral zeros of Krawtchouk polynomials // J. Comb. Theory. Series A. 1996. V. 74. N. 1. P. 77-99.

26. Levenshtein VJ. Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces // IEEE TVans. Inform. Theory. 1995. V. 41. P. 1303-1321.

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

28. MacWilliams F.G., Sloane N.J.A. The theory of error correcting codes. New York: North-Holland. 1977. P. 744. (Русский перевод: Мак-Вилъямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки: Пер. с англ. М.:Связь. 1979. С. 744.)

29. Malyugin S.A. Perfect codes with trivial automorphism group // Proc. Second Int. Workshop on Optimal Codes and Related Topics. Sozopol, Bulgaria, June 1998, P. 163-167.

30. Phelps К. T. Every finite group is the automorphism group of some perfect code. J. of Combin. Theory, series A 43 (1) (1986) 45-51.

31. Phelps К.Т., LeVan M.J.t Kernels of nonlinear Hamming codes, Designs, Codes and Cryptography, 6 (1995),247-257.

32. Phelps K.T., LeVan M.J., Non-systematic perfect codes, SIAM Journal of Discrete Mathematics, 12(1)(19ЭЭ\27-34.

33. Tietavainen A. On the nonexistence of perfect codes over finite fields. 11 SIAM J.Appl.Math. 1973. V. 24. P. 88-96.

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