Perfect binary codes of infinite length.pdf 1. Основные определения Пусть N - множество натуральных чисел. Бесконечномерный куб {0,1}N состоит из всевозможных бесконечных последовательностей u = (u1,... ,un,...), где un G {0,1}; n G N. Сумма двух элементов u,v G {0,1}N определяется формулой u + v = (u1 ф v1, ... ,Un Ф vn,...), где u = (ui,... ,un,...), v = (vi,... ,v.n,...) и un ф v.n - сумма элементов un,vn в двухэлементном поле Галуа GF(2) = {0,1}. Относительно такой операции сложения куб {0,1}N является бесконечномерным векторным пространством над полем GF(2). Элементы куба {0,1}N далее будем называть векторами. Нулевой вектор обозначаем через 0, а базисные векторы с единичной i-й координатой - через ei = (0,..., 0,1,0,...). Носитель вектора u G {0,1}N (множество индексов i, для котоi рых ui = 1) обозначается через [u]. Число ненулевых координат вектора u называется его весом и обозначается через | u| . В отличие от конечномерного случая вес может принимать также значение то. Расстояние Хемминга между векторами u,v E {0,1}N определяется как |u + v|. Расстояние Хемминга задаёт в пространстве {0,1}N «обобщённую» метрику Хемминга со значениями в N U {то}. Определение 1. Подмножество C в бесконечномерном двоичном кубе {0,1}N называется совершенным двоичным кодом с расстоянием 3, если все шары единичного радиуса (в метрике Хемминга) с центрами из C попарно не пересекаются и их объединение покрывает куб {0,1}N. Следует отметить, что изучение кодов бесконечной длины (МДР-кодов, задаваемых квазигруппами с бесконечным числом аргументов) впервые было предпринято В.Н. Потаповым в [1]. Рассмотрим в {0,1}N следующее отношение эквивалентности: u ~ v ^^ |u + v| = то (u,v E {0,1}N). Куб {0,1}N относительно этого отношения разбивается на попарно не пересекающиеся классы эквивалентности, которые далее будем называть слоями куба {0,1}N. Слой, содержащий нулевой вектор, будем обозначать символом {0,1}N и называть его нулевым слоем. Он состоит из всех векторов конечного веса (такие векторы будем называть финитными). Очевидно, что нулевой слой является подпространством в {0,1}N, а любой другой слой L является смежным классом по этому подпространству. Пусть L - произвольный слой в кубе {0,1}N. Определение 1'. Подмножество C С L называем совершенным двоичным кодом слоя L, если все шары единичного радиуса с центрами из C попарно не пересекаются и их объединение покрывает слой L. Легко видеть, что изучение совершенных кодов в кубе {0,1}N фактически сводится к изучению совершенных кодов в нулевом слое {0,1}^ Совершенный код в {0,1}N называется кодом Хемминга, если он является линейным подпространством в {0,1}[^. Код Хемминга Hи можно определить следующим образом. Для конечных n код Хемминга Hn длины n = 2k - 1 (k > 1) определяется стандартным образом. Добавляя справа к векторам u E Hn бесконечное число нулевых координат, можно вложить код Hn в нулевой слой {0,1}^ Это вложение будем обозначать символом Hfn. Тогда, так как Яп С H2п+' (n = 2k - 1), можно положить U ~ , hи = и a2-i. fc=2 2. Эквивалентность линейных совершенных кодов в нулевом слое и их группа автоморфизмов Как и в конечномерном случае, для любой изометрии A : {0,1}N ^ {0,1}N существует вектор a E {0,1}N и перестановка п : N ^ N, такие, что A(u) = 7r(u) + а, где 7T((Ui, . . . ,u„, . . . )) = (un-l(i), . . . ,un-l(n), . . . ). Определение 2. Два совершенных двоичных кода C',C2 С {0,1}N называются эквивалентными, если существует изометрия A нулевого слоя {0,1}N, такая, что A(Ci) = C2. Два совершенных двоичных кода Ci, C2 С {0,1}U называются изоморфными, если существует перестановка п : N ^ N, такая, что ^(C') = C2. Лемма 1. Все коды Хемминга в слое {0,1}N эквивалентны между собой. 3. Континуальность множества классов эквивалентности совершенных двоичных кодов бесконечной длины В коде Хемминга HU рассмотрим подпространство Ri, порождённое всеми векторами веса 3 с i-й координатой равной единице. Всевозможные смежные классы вида Ru = Ri + u (u G И™) называются i-компонентами кода И™, i G N. Рассмотрим некоторое семейство B = {R"1, R"2,... }, состоящее из конечного или бесконечного числа попарно не пересекающихся ^-компонент, где up G И™, 1 ^ p < m + 1 (m G N U Одна из основных конструкций нелинейных совершенных двоичных кодов состоит в том, что в коде Hn сдвигаются по координатам ip все компоненты из семейства B. Доказательство этого факта в точности такое же, как и в случае кодов конечной длины [2-5]. Далее будем говорить, что код И™(B) построен из кода Хемминга И™ сдвигами (или свитчингами) компонент из семейства B. Если при фиксированном индексе i имеем ip = i для всех p, то код И™(B) называем кодом Васильева бесконечной длины. Такие коды конечной длины впервые были построены в [6]. Для нахождения мощности множества всех классов эквивалентности кодов бесконечной длины достаточно ограничиться рассмотрением кодов Васильева. Положим i =1. Компонента R1 порождается всеми векторами vp веса 3 с носителями [vp] = {1, 2p, 2p +1}, p G N. Рассмотрим векторы w1 = 0, wp = e8 + e9 + ■ ■ ■ + e2p+2-2, p G N, p ^ 2. Из определения проверочной матрицы следует, что wp G И™, p G N. Для бесконечного семейства компонент B1 = {Rwи любого е G {0,1}N (е = (е1,е2,...)) рассмотрим следующий код Васильева: И™(Bi, е) = (ы™ \ и R?) U ( U (RWP + epei)) . То есть код И™(B1, е) получается из кода Хемминга И™ сдвигами только тех компонент R^ из семейства B1, для которых ер =1. Лемма 2. Пусть L - любое линейное пространство над полем GF(2) и И С L - его подпространство. Пусть A : L ^ L - аффинный изоморфизм пространства L и F : L ^ {0,1}3 - линейное отображение, такое, что F(И) = {0,1}3 и FoA(H) = {0,1}3. Рассмотрим два подмножества C1, C2 С L, удовлетворяющих условиям C1 \ KerF = C2 \ KerF = И \ KerF, Ci \ И С KerF, C2 \ И С KerF. Тогда если A(C1) = C2, то A(H) С И и a G И. Эта лемма позволяет доказать следующий ключевой факт. Теорема 1. Если е,е' G {0,1}N, е = е' е1 = е[ = 1, то коды Васильева И™(В1,е), И™ (B1, е') не эквивалентны. Мы построили континуум попарно не эквивалентных кодов Васильева бесконечной длины. Так как в счётном множестве {0,1}N может быть не более континуума различных кодов, то из теоремы 1 сразу получается Следствие 1. Мощность множества всех классов эквивалентности совершенных двоичных кодов бесконечной длины равна континууму. 4. Совершенные двоичные коды в кубе {0,1}N Существование совершенных двоичных кодов в кубе {0,1}N сразу следует из существования таких кодов в слое {0,1}^ Для этого пронумеруем все слои числами из отрезка [0,1], т.е. каждому числу a G [0,1] сопоставляем слой La С {0,1}N, при этом {0,1}N = U La. Выберем в каждом слое по одному элементу ua и для любого совер-«е[о,1] шенного кода C0 С L0 = {0,1}N полагаем C = (J (C0 + ua). Очевидно, множество C «е[о,1] является совершенным двоичным кодом в {0,1}N. Отметим, что при построении кода C была применена аксиома выбора. Лемма 3. В кубе {0,1}N существуют линейные совершенные двоичные коды. Посмотрим, как устроены изометрии куба {0,1}N. Так как разные слои этого куба находятся на бесконечном расстоянии Хемминга друг от друга, то изометрия допускает, во-первых, произвольную перестановку (континуального) множества всех слоев. Далее, в каждом слое допускается (независимо от других слоёв) перестановка координат па и перенос на вектор aa E {0,1}N. Изометрия может не быть аффинным преобразованием всего куба. На этом основании вводим два различных определения. Определение 3. Два совершенных кода C',C2 С {0,1}N называются изомет-ричными (соответственно, эквивалентными), если существует изометрия A пространства {0,1}N (соответственно, изометрия, являющаяся аффинным преобразованием пространства {0,1}N), такая, что A(C') = C2. Лемма 4. Все линейные совершенные коды в {0,1}N эквивалентны между собой. Мощность континуума принято обозначать символом с. Мощность всех подмножеств континуального множества будем обозначать символом 2c. Эту мощность называют также гиперконтинуумом. Пример 1. В пространстве {0,1}N строится гиперконтинуальное семейство линейных совершенных двоичных кодов H = {HY}7ег, такое, что для любых HYl, HY2 E H (Y' = y2) не существует ни одной перестановки п : N ^ N, такой, что Н72 = 7т(Н71 ). Теорема 2. Мощность множества всех классов эквивалентности совершенных двоичных кодов в пространстве {0,1}N равна гиперконтинууму 2с.

Скачать электронную версию публикации