Группы автоморфизмов кодов Хэмминга и их компонент

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

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

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

Рассмотрим множество последовательностей длины п над конечным алфавитом мощности q, называемое также q-ичным кубом. Снабжённый некоторой метрикой, g-ичный куб образует метрическое пространство Vй. В настоящей работе рассматриваются только пространства Хэмминга. Расстояние Хэмминга между двумя последовательностями х, у 6 V71 определяется числом позиций, в которых х и у различаются.

Произвольное подмножество С С Vй называется g-ичным кодом длины п. Элементы кода суть кодовые слова. Наименьшее ненулевое расстояние между кодовыми словами кода С обозначается d = d© и называется кодовым расстоянием. Длина, мощность и кодовое расстояние g-ичного кода составляют его параметры и записываются в виде (п, |С|, d) q. Число символов кодирующего алфавита q часто не указывают, если ясно, о каких кодах идёт речь.

Напомним, что изометрия — это преобразование метрического пространства, сохраняющее расстояние между его элементами. Автоморфизмом кода С С V" n называется изометрия пространства Vn, отображающая код С в себя. Два кода С и Сч являются эквивалентными, если существует изометрия пространства У&trade-, отображающая эти коды друг в друга.

A.A. Марков в 1956 г. показал [19], что группа изометрий пространства Vй представляет собой полупрямое произведение.

Aut (yn) = Sn X SJ = {(тга) | тг G Sni, а G SJ} .

Иначе говоря, каждая изометрия Vn является парой преобразований (7гот). Подстановка тг 6 Sn переставляет элементы каждой последовательности из Vй. Кортеж, а = (сгх,., <тп) представляет собой набор подстановок из в котором каждая подстановка <У{ действует на символах кодирующего алфавита и в соответствии с этим изменяет элемент хг произвольной последовательности х е Vй.

Пусть задан некоторый код С С Vй с кодовым расстоянием (1. Легко видеть, что шары радиуса? = [^р] с центрами в кодовых словах кода С не пересекаются. Предположим, что при передаче данных по каналу связи с использованием этого кода в последовательности х € С происходит не более I ошибок (замен символов). Тогда декодирование по принципу максимального правдоподобия — декодирование полученной последовательности в ближайшее к ней кодовое слово, которым является х, — даёт верный результат. В связи с этим говорят, что код С исправляет? ошибок.

В пространстве Уп мощность произвольного шара радиуса? рав-£ на ^ Сп (<7 — 1) гЭто означает, что для мощности кода С длины п с г=0 кодовым расстоянием в, справедлива следующая оценка, называемая границей Хэмминга: п.

0 < ——, (1).

Е с* (9 -*=0 где t = ] — число ошибок, которое исправляет код.

Код, достигающий границы Хэмминга, называется совершенным. Наличие равенства в (1) эквивалентно тому, что шары радиуса? с центрами в кодовых словах кода С образуют разбиение, или плотную упаковку метрического пространства V71. Совершенный код, исправляющий? ошибок, иногда также называют ¿—совершенным. Тривиальными примерами совершенных кодов являются одноэлементные множества, а также само Vй. Не менее простым примером служит двоичный код с повторением, имеющий нечётную длину п, исправляющий^тр ошибок, однако содержащий всего два кодовых слова — 00. О и 11. 1.

В конце 1940;х гг. для исправления одиночных ошибок Р. У. Хэм-минг [35] использовал линейный совершенный двоичный код с кодовым расстоянием d = 3. Этот код сейчас называется кодом Хэмминга. Немного ранее, в 1948 г., М. Голей построил [33] два совершенных кода, исправляющих более одной ошибки. Это были двоичный код длины 23, исправляющий 3 ошибки, и троичный код длины 11, исправляющий 2 ошибки. В настоящее время эти замечательные линейные коды хорошо известны как коды Голея, каждый из них единственен с точностью до эквивалентности (см. [32,50,53]), и они имеют применение во многих областях математики. Например, двоичный код Голея широко используется в теории конечных групп (см., например, книгу [30]).

Было предпринято несколько попыток построить другие совершенные коды, исправляющие более одной ошибки, но безуспешно. Вместе с тем стали появляться результаты, перечисляющие параметры, при которых совершенные коды не могут существовать. Первые из них касались кодов над конечными полями? q = GF (q), где q = рт для некоторого простого р и целого г ^ 1, и опирались на необходимое условие существования совершенного кода с параметрами q, п, i, вытекающее из границы Хэмминга. Если такой код существует, то мощность шара радиуса t делит мощность всего пространства Vй. Отсюда следует, что существует целое 1 ^ s ^ пг, такое что t.

ГCi (q-iy=ps. i=О n.

Так как ^ Cln (q — 1) г = qn, то, вычитая предыдущее, находим: г=0 qn — ps = 0 (mod q — 1).

Следовательно, ps = qm для некоторого целого 1 ^ га ^ п. Таким образом, необходимым условием существования ¿—совершенного кода длины п над является равенство (условие сферической упаковки).

Некоторые решения равенств (2) и (3) легко обнаружить. В частности,? = т = п соответствует коду из одного словап = 2Ь + 1 — двоичному коду с повторениемп — 2 т ~ 1 и? = 1 — кодам, исправляющим одну ошибку, число которых оказалось дважды экспоненциальным, а их свойства столь разнообразны, что активно исследуются уже на протяжении более полувека. Результатов этих исследований коснёмся ниже. Другие известные решения не столь очевидны: q = 2, п = 23, Ь = 3, а также д = 3, п = 11,? = 2 соответствуют кодам Голеякроме того, много раз было доказано (см., например, [33]), что для-д = 2, п = 90,? = 2, удовлетворяющих условию (3), не существует совершенных кодов.

В поиске новых решений многие авторы обнаруживали параметры, при которых равенство (2) не имеет решений вовсеэто означает, что не. существует совершенных кодов с такими параметрами. Обзор первых подобных результатов см., например, у Дж. X. ван «Пинта [40]. При их получении в случае? = 2 условие упаковки удалось связать с теорией диофантовых уравнений, а часть больших параметров были отсечены перебором при помощи компьютера.

Для дальнейшего отсечения «пустых» параметров требовались более тонкие необходимые условия существования совершенных кодов. Для двоичных кодов такое условие было найдено значительно ранее С. П. Ллойдом [43], в 1957 г. Позднее Ф. Дж. Мак-Вильямс [44] обобщила его для конечных полей, а П. Дельсарт [31] и X. У. Ленстра-мл. [38].

2) которое в двоичном случае принимает вид:

3) независимо показали, что структура алфавита не имеет значения и его мощность д может быть произвольной. Теорема Ллойда гласит, что если ¿—совершенный код длины п над алфавитом из д символов существует, то полином ь.

Рь{х) = - 1 у-' г=О имеет? различных корней среди чисел 1, 2,., п.

Рассмотрение нулей полинома Ллойда Р^х) в конечном итоге привело к полному описанию возможных параметров совершенных кодов над конечными полями. Дж. X. ван Линт [41,42] показал, что для t ^ 7 все параметры совершенных кодов уже известны и других не существует. Наконец, А. Титвайнен [56]- а также независимо В. А. Зиновьев и В. К. Леонтьев [13] разрешили проблему полностью и показали, что нетривиальный совершенный код над ¥-д, исправляющий более одной ошибки, должен иметь параметры одного из кодов Голея.

Не так много результатов имеется для д, не равного степени простого числа, но те, что удалось получить, в значительной степени продвинули решение проблемы в общем. Используя обобщение теоремы Ллойда, М. Р. Вест [28] существенно ограничил широту поиска, установив, что в этом случае Ь € {1,2, 6,8}. До сих пор не удалось доказать, что таких кодов не существует вообще. Некоторые частные случаи в оставшемся наборе параметров покрываются работами С. В. Голома и Е. С. Познера [34], Л. А.-Вассалыго и др. [11] и некоторых других авторов (см., например, обзор У. Хедена [36]). Вместе с тем, исследование X. У. Ленстры-мл. [38] показывает, что код над «составным» алфавитом, возможно, трудно построить, так как он не может быть эквивалентным никакому групповому коду.

Куб над конечным полем образует п-мерное линейное пространство Всюду далее рассматриваются коды над конечными полями и, ввиду теоремы Зиновьева-Леонтьева-Титвайнена, под термином совершенный понимается совершенный код с кодовым расстоянием 3, то есть исправляющий одну ошибку. Из условия упаковки, такой код может иметь длину п =^рг и мощность qn~m. В пространстве F^ существует единственный с точностью до эквивалентности линейный (образующий линейное подпространство) совершенный код. Это код код Хэмминга, который строится для любого m ^ 2.

После появления кодов Хэмминга и Голея некоторое время не удавалось обнаружить какие-либо другие совершенные коды. Г. С. Шапиро и Д. Л. Злотник в [52] доказали в 1959 г., что весовое распределение произвольного совершенного двоичного кода зависит только от веса того кодового слова, у которого он является минимальным в коде. Аналогичное свойство у равномерно упакованных g-ичных кодов, подклассом которых являются совершенные, выявили JT. А. Бассалыго и др. [10]1. В связи с этим в [52] было выдвинуто предположение, что все совершенные двоичные коды эквивалентны коду Хэмминга. Эта гипотеза была опровергнута Ю. J1. Васильевым [12]- который в 1962 г. построил дважды экспоненциальное число попарно неэквивалентных совершенных двоичных кодов любой допустимой длинысреди кодов Васильева при п ^ 15 имеет множество нелинейных. Позднее Й. Шёнхайм [51]* и Б. Линдстрём [39] в своих работах 1968;1969 гг. представили нелинейные совершенные коды над произвольными конечными полями. В дальнейшем было предложено более 20 различных конструкций, обзор которых можно найти, например, в лекциях Ф. И. Соловьёвой [54].

Долгое время оставался открытым вопрос, все ли совершенные коды в булевом кубе изометричны друг другу (см., например, [1]). Лишь в 1994 г. C.B. Августинович [3] доказал, что если два совершенных двоичных кода одинаковой длины п > 15 изометричны, то они эквивалентны. Несколько лет спустя аналогичный результат был получен Ф. И. Соловьёвой и др. [55] для совершенных g-ичных кодов.

Изометрии двоичного (или булева) куба исчерпываются перестановками координат и сдвигами пространства на вектор. Таким образом действие изометрии (-7г, v) е Аи^ПЛ,) на двоичный вектор хбЕ^ записывается в виде.

Х (7Г, V) = хтг + V, где 7 Г? и V 6 Это происходит от того, что обе возможные подстановки элементов поля Ег могут быть представлены сложением в самом поле: тождественная подстановка есть сложение с 0, а результат подстановки (01) совпадает с прибавлением 1.

В общем случае это не так. Подстановки над представимы через операции поля, если в дополнение к сложению рассмотреть умножение. Аналогично, в случае д = 4 для этой цели можно использовать автоморфизмы самого поля из группы Галуа Оа!^). Например, подстановка (0 а2 1 о-), где, а — примитивный элемент ?4, представляется многочленом (х + а)2. Однако при д ^ 5 подстановок на элементах из? q значительно больше, чем тех, которые могут быть заменены операциями в поле. Как следствие, не все изометрии пространства Р&tradeмогут быть выражены в терминах этих операций.

Примечателен результат К. Т. Фелпса [47] о том, что каждая конечная группа изоморфна группе перестановочных автоморфизмов некоторого совершенного двоичного кода. Однако задача нахождения группы автоморфизмов для заданного кода представляется ещё более трудной. Пусть С — совершенный двоичный код. Из свойства антиподаль-ности (см. [52]) кода С следует, что его группа автоморфизмов Аи^С) содержит тождественную подстановку координат е и сдвиг на вектор 1, состоящий из всех единиц. Группа Аи^С), образованная только этими двумя преобразованиями, называется тривиальной. С. В. Августино-вич и Ф. И. Соловьёва [26] построили несистематические совершенные двоичные коды с тривиальной группой автоморфизмов. Независимо.

С. А. Малюгин [45] доказал, что существуют и систематические коды с таким свойством.

Изометрии пространства оставляющие неподвижным нулевой вектор, будем называть симметриями. Хорошо известно, что группа полулинейных симметрий кода Хэмминга длины п = изоморфна общей полулинейной группе ГЬш (д) = Оа1(?д) X С?1/т (д) (см. [37, теорема 7.2]). В случае д > 4 среди симметрий пространства имеются те, которые не являются полулинейными. В связи с этим возникает естественный вопрос, все ли симметрии кода Хэмминга являются полулинейными. В настоящей диссертации дан положительный ответ на этот вопрос.

В булевом кубе код Хэмминга И является одним из самых симметричных среди совершенных кодов в том смысле, что его группа автоморфизмов максимальна по мощности. Этот интересный факт был получен Ф. И. Соловьёвой и С. Топаловой [24]. Затем эти же авторы доказали [25], что максимальный порядок группы автоморфизмов имеет только код Хэмминга. Вместе с тем, независимо С. А. Малюгин [18] для произвольного нелинейного совершенного двоичного кода С установил, что |А^(С)| <

С. В. Августинович с соавторами [9] исследовали структуру группы перестановочных автоморфизмов кодов Васильева. Перестановочные автоморфизмы задаются лишь подстановкой на позициях координат вектора. Там же доказано, что группа перестановочных автоморфизмов (или, что-то же при д = 2, группа симметрий) линейной компоненты двоичного кода Хэмминга длины N = 2 т — 1 изоморфна полупрямому произведению Бп X, где п = 2т~1 — 1. Ниже изучение группы автоморфизмов линейной компоненты продолжено для д ^ 2. Полученные результаты распространены на другие компоненты д-ичного кода Хэмминга, такие как простые компоненты и их обобщение, которое предложено называть ^-компонентой.

Сами по себе изометричные пространства, равно как и эквивалентные коды, в некотором смысле устроены одинаково. Дело обстоит иначе, если рассматриваемый вопрос касается специфики того, как код вложен в объемлющее пространство. Например, существуют изометричные коды Адамара, которые не являются эквивалентными. Код, любая изометрия которого продолжается до изометрии всего пространства, называется метрически жёстким. Вопросы, связанные с метрической жёсткостью кодов, являются частным случаем более общей проблемы — восстановимое&tradeобъекта по частичной информации о нём. Иначе говоря, при рассмотрении любого объекта актуальным представляется поиск его инвариантов, которые бы определяли этот объект с некоторой степенью точности. Вопросам восстановимости двоичных кодов посвящена последняя глава диссертации.

Настоящая диссертация содержит три главы. В первой главе описаны результаты исследования симметрий д-ичного кода Хэмминга. В параграфе 1.1 приведены необходимые обозначения и определения различных групп автоморфизмов кодов, показана связь автоморфизмов с матрицами над конечными полями. Параграф 1.2 включает в себя известные факты о строении групп автоморфизмов линейных кодов, а также содержит замечания, раскрывающие характер действия полулинейных симметрий на векторы пространства Е&trade-. В параграфе 1.3 исследуются перестановочные автоморфизмы кода Хэмминга. Доказано, что группа перестановочных автоморфизмов кода Хэмминга длины п —^рг с проверочной матрицей в каноническом виде изоморфна унитреуголыюй группе матриц ?7Тто (д) (теорема 5). Вместе с тем показано, что группа перестановочных автоморфизмов циклического кода Хэмминга не может быть изоморфна ?7Тт (д) (утверждение 1). Таким образом установлено, ча-о в случае д > 2 группы перестановочных автоморфизмов различных кодов Хэмминга могут быть неизоморфны друг другу (следствие 1). В параграфе 1.4 доказано, что все симметрии кода.

Хэмминга являются полулинейными. Этот результат позволил получить представление о всей группе автоморфизмов д-ичного кода Хэмминга (теорема 6).

Во второй главе исследуется структура групп мономиальных автоморфизмов различных компонент кода Хэмминга. Мономиальные автоморфизмы характеризуются тем, что действие каждого из них на векторы пространства Е&tradeможет быть задано умножением векторов на некоторую мономиальную матрицу над полем В параграфе 2.1 приведены известные связи между кодом Хэмминга и конечными проективными геометриями, необходимые для изложения результатов второй главы. В параграфе 2.2 дано описание группы мономиальных автоморфизмов линейной компоненты д-ичного кода Хэмминга (теорема 7). В параграфе 2.3, наряду с понятием простой компоненты кода Хэмминга, рассматриваются ^/-компоненты, заданные как линейные пространства над подполями поля Идеи предыдущего параграфа обобщаются для таких компонент, в результате чего получена информация о структуре их групп мономиальных автоморфизмов (теорема 8).

Третья глава описывает исследование восстановимости двоичных кодов по размерностям их подкодов, которое было выполнено автором совместно с С. В. Августиновичем. Здесь, как и в работах [1,5], под размерностью кода понимается размерность наименьшей грани булева куба, содержащей этот код. Оказалось, что произвольный двоичный код определяется с точностью до эквивалентности набором размерностей всех своих подкодов чётной мощности (теорема 9). Глава завершается примерами, показывающими неулучшаемый характер обнаруженных достаточных условий эквивалентности двоичных кодов.

В диссертации получены следующие основные результаты.

1. Доказано, что все симметрии д-ичных кодов Хэмминга являются полулинейными. Получено описание группы автоморфизмов таких кодов.

2. Для д-ичного кода Хэмминга с проверочной матрицей в каноническом виде показано, что его группа перестановочных автоморфизмов изоморфна унитреугольной группе. Обнаружены коды Хэмминга с неизоморфными группами перестановочных автоморфизмов.

3. Описана структура групп мономиальных автоморфизмов различных компонент кода Хэмминга над полем ¥-д: простой, линейной и ^-компоненты.

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

Основные результаты опубликованы в работах [57−65].

Заключение

.

Автор выражает глубокую благодарность своему научному руководителю профессору Ф. И. Соловьёвой за постановку задач о группах автоморфизов кодов, постоянное внимание и неоценимую поддержку в работе. Автор также выражает признательность С. В. Августиновичу и Д. С. Кротову за ценные замечания и дискуссии, которые способствовали плодотворным исследованиям.