О двоичных самодуальных экстремальных дважды четных кодах длины 80

Пусть E_q = {0,1,... ,q — 1} - алфавігт размера, q. Произвольное подмножество С С Е™ называется q-ичным кодом и об означается через (n, N, d)_q, г де n - длина кода, N - число его кодовых слов (или мощность) и d - его минимальное расстояние (Хэмминга). Линейный код С над F с параметрами (n,N = q^k,d)_q обозначается через [n,k,d\_q. Для двоичных кодов принято обозначение (n, N, d) и [n, к, d] (т.е. q опускается). Пусть J = {1, 2,..., n} - координатное множество Eq. Для вектора x = (жі,..., ж_п) € Eq обозначим через supp(x) его носитель, т.е.

supp(x) = {г € J : ж^ = 0}.

Обозначим через wt(x) вес вектора x, т.е. размер его носителя: wt(x) = |supp(x)|. Для двоичного вектора x обозначим через х дополнительный к нему вектор, т.е. вектор, полученный из x взаимной заме пой элементов 0 и 1: х = x + 1. где 1 = (1,1,..., 1). Для линейного [n, к, d]-KOfla С обозначим через С ^ дуальный к нему код относительно скалярного произведения в поле Ғф

С± = {v € F” : (v, c) = 0, Vc € С}, где (v, c) = u1c1 + • • • ипсп для векторов c = (с1,..., сп) 1і v = (щ,..., vn). Двоичный [n, к, d]-код С называется схинхзртог опальным если С С С^. Если n четно и к = n/2. то такой код называется самодуалъным. Самодуальный код С называется четным, если все кодовые слова имеют четный вес, и дважды четным, или кодом типа II, если все веса его слов

делятся на 4 (см. по этой тематике |1 3|). Мэллоус и Слоэн [4] доказали, что минимальное расстояние дважды четного самодуального [п, п/2, d]-KOfla не превышает величины d5 4^24J +4.

Код назывется экстремалъним, если его расстояние удовлетворяет с равенством приведенной выше верхней оценке. Для п = 80 эта оценка сводится к виду d < 16, поэтому (дважды четный) [80,40,16]-код является экстремальным. По дважды четным кодам длины 80 известно очень немного. Карлин [5] в 1969 г. построил такой [80,40,16]-код как расширенный кадратично вычетный код. Донтчева и Харада [6] доказали, что имеется точно 11 неэквивалентных экстремальных дважды четных таких кодов, имеющих автоморфизм порядка 19. В недавней работе [7] построены 28 неэквивалентных четных [80,40,16]-кодов (не являющихся дважды четными), а в [8] приведены три неэквивалентных экстремальных (дважды четных) [80,40,16]-кода. Эти результаты согласуются с информацией по этим кодам, которую можно найти в [9].

В недавней заметке [10], используя улучшенную обобщенную каскадную (ОК) конструкцию, код Нордстрома-Робинсона и двоичный расширенный код Голея были представлены в виде OK-кодов. Цель данной заметки - построить с помощью этой же конструкции двоичные самодуальные дважды четные коды длины 80. Пользуясь стандартными методами модификации кодов, удается построить довольно большое число неэквивалентных двоичных дважды четных [80,40,16]-кодов, что является содержанием следующей работы.

2.    Внутренние коды

Чтобы понимать приводимое здесь нами построение кодов, полезно ознакомиться с обобщенной каскадной конструкцией (ОКК) построения кодов, как это было описано в [11], а также в недавней работе [10], в которой мы представили код Нордстрома-Робинсона и двоичный расширенный совершенный код Голея в виде обобщенных каскадных кодов. Наша стратегия построения [80,40,16]-кода, который мы обозначим буквой Z = Zso, состоит в следующем. Сначала мы построим два разных [80, 39,16]-кода Zo и Z1 в виде обобщенных каскадных кодов третьего порядка, а потом докажем, что эти два кода находятся друг от друга на расстоянии 16. Это в точности повторяет метод, использованный нами в [10] для построения кода Нордстрома-Робинсона и двоичного кода Голея в виде ОК-кодов четвертого порядка.

Мы начнем с определения алфавита Е из восьми элементов поля Fs = {0,1, а, а²,..., а⁶}, где а - примитивный элемент поля F§, а именно корень уравнения ж³ + ж + 1 = 0 над F2. Элементы поля F8 удобно занумеровать числами 0,1,..., 7, так что а^г имеет номер, двоичное представление которого совпадает с представлением а^г как двоичного вектора над F2. При этом на протяжении всей статьи под сложением индексов г + ф где г,ф Е {0,1,..., 7}, подразумевается соответствующее сложение а^г + а в поле Fs. Приводимую ниже нумерацию элементов поля F8 зафиксируем на весь последующий текст:

0 <—> (0 0 0) <—> 0 1 <—> (10 0) <—> 1 а <—> (010) <—> 2 а2 <—> (0 01) <—> 4 а3 <—> (110) <—> 3 а4 <—> (011) <—> 6 а5 <—> (111) <—> 7 а6 <—> (101) <—> 5

.                                         (1)

Для построения кодов Z_s, s = 0,1, используется одна и та же система внутренних кодов, с описания которой мы и начнем построение кода Z_s. Пусть В обозначает тривиальный

[8, 8,1]-код (т.е. все двоичные векторы длины 8). Этот код В разбивается на два тривиальных подкода: [8, 7, 2]-код Во с проверкой на четность и его смежный класс (8,128, 2)-код В1 с проверкой на нечетность. Оба кода разбиваются на коды В₅,д s = 0,1, г = 0,..., 7, представляющие собой смежные классы расширенного совершенного [8,4,4]-кода Хэмминга, которые в свою очередь разбиваются на тривиальные (8, 2, 8)-коды с повторением B_s ,i,j, j = 0,..., 7. Все эти коды мы приводим вместе с нумерацией их слов. Вектор b с номером (s,i,j, к), или как мы будем писать b = b (s, г, j, к), принадлежит коду B_s ,i,j и имеет в этом коде номер к, где к = 0,1. Зафиксируем на всю статью следующее разбиение расширенного совершенного [8,4,4]-кода Хэмминга Во,о на подкоды Во,од:

В о , о , о	= { b (0,0,0,0)	= (00000000),	b (0, 0, 0, 1)	= (11111111)},
В о , о , 1	= { b (0,0,1,0)	= (01001101),	b (0, 0, 1, 1)	= (10110010)},
В о , о , 2	= { b (0,0,2,0)	= (00101011),	b (0, 0, 2, 1)	= (11010100)},
В о , о , 3	= { b (0,0,3,0)	= (01100110),	b (0, 0, 3, 1)	= (10011001)},
В о , о , 4	= { b (0, 0,4, 0)	= (00010111),	b (0, 0, 4, 1)	= (11101000)},
В о , о , 5	= { b (0, 0, 5, 0)	= (01011010),	b (0, 0, 5, 1)	= (10100101)},
В о , о , б	= { b (0, 0, 6, 0)	= (00111100),	b (0, 0, 6, 1)	= (11000011)},
В о , о , 7	= { b (0, 0, 7, 0)	= (01110001),	b (0, 0, 7, 1)	= (10001110)}.

Приведем теперь разбиение кода Во на подкоды Во,». Введенная нумерация элементов поля а^г с помощью их двоичного представления как векторов длины 3 над F2 позволяет нам задать естественную нумерацию смежных классов Во,» расширенного (линейного) кода Хэмминга Во,о, приведенного выше. Пусть 3 (г) - вектор длины 3 над F2, являющийся двоичным представлением г, т.е. 3 (г) = (3(»), 3⁽»), 3з»))>^а ^(3(г)) обозначает проверку на четность вектора 3 (г), так что

33 г = £ 2 1 -1 3^, ^(3(г)) = £ 3^ . 3 = 1                         1 =1

Тогда смежный класс Во,» кода Во,о, получается сдвигом на следующий вектор g», зафиксированный на всю статью:

g » = И3(г)),3(г), 0, 0, 0, 0).                                     (2)

Мы приводим все эти векторы (которые образуют линейный код и которые нам понадобятся):

до = (0 000 0000), gi = (1 1000000), g2 = (10100000), g3 = (01 100000), g4 = (10010000), g5 = (01010000), g6 = (001 10000), g7 = (1 1 1 10000).

С помощью приведенных векторов g» код Во разбивается на смежные классы Во,», причем номер этого смежного класса равен номеру вектора g» (т.е. Во,» = Во,о + g»). Более того, так как задано разбиение кода Во,о на подкоды Во,од, j = 0,1,..., 7, с помощью этих же g» задается разбиение кода Во,» на подкоды Во,»д, а именно Во,»д = Во,од + gt- В качестве иллюстрации приведем еще одно такое разбиение, а именно кода Вод = Во , о + g₁ на подкоды Во,1,3, которое нам понадобится в дальнейшем. Разбиение кода Во,1 на подкоды

Bo , i ,j имеет следующий вид:

S o , i , o

• ^B 0 , 1 , 1

• ^B 0 , 1 , 2

• ^B 0 , 1 , 3

• ^B 0 , 1 , 4

• ^B 0 , 1 , 5

• ^B 0 , 1 , 6

• ^B 0 , 1 , 7

{ b (0,1, 0, 0)

{ b (0,1,1, 0)

{ b (0,1, 2, 0)

{ b (0,1, 3, 0)

{ b (0,1,4, 0)

{ b (0,1, 5, 0)

{ b (0,1, 6, 0)

{ b (0,1, 7, 0)

(11000000),

(10010101),

(11110011),

(10100110),

(11001111),

(10011010),

(11111100),

(10101001),

b (0,1, 0,1) =

b (0,1,1,1) =

b (0,1, 2,1) =

b (0,1,3,1) =

b (0,1, 4,1) =

b (0,1, 5,1) =

b (0,1,6,1) =

b (0,1, 7,1) =

(00111111)}

(01101010)}

(00001100)}

(01011001)}

(00110000)}

(01100101)}

(00000011)}

(01010110)}

Приведем также разбиение кода Bi,o на подкоды Bi,oj:

B 1 , 0 , 0	= { b (1, 0, 0, 0)	= (10000000),	b (1, 0, 0, 1)	= (01111111)},
B 1 , 0 , 1	= { b (1, 0,1, 0)	= (11001101),	b (1, 0, 1, 1)	= (00110010)},
B 1 , 0 , 2	= { b (1,0,2,0)	= (10101011),	b (1, 0, 2, 1)	= (01010100)},
B 1 , 0 , 3	= { b (1, 0, 3, 0)	= (11100110),	b (1, 0, 3, 1)	= (00011001)},
B 1 , 0 , 4	= { b (1, 0, 4, 0)	= (10010111),	b (1, 0, 4, 1)	= (01101000)},
B 1 , 0 , 5	= { b (1, 0, 5, 0)	= (11011010),	b (1, 0, 5, 1)	= (00100101)},
B 1 , 0 , 6	= { b (1, 0, 6, 0)	= (10111100),	b (1, 0, 6, 1)	= (01000011)},
B 1 , 0 , 7	= { b (1, 0, 7, 0)	= (11 110001),	b (1, 0, 7, 1)	= (00001110)}.

Приведенные выше разбиния кода Bo,o на подкодві Bo , o ,j и Bo на подкодві Bo,^ индуцируют следующее взаимно однозначное отображение всех 128-ми троек (г,3,к^ целых чисел над алфавитом Е 8 х Е 8 х Е2 на пространство двоичны.г четных векторов длины 8:

у_сс(г,^, к) = ь (0,г,з,к), г,з е {0,1,...,7}, к е {0,1},                    (3)

которое мв1 распространяем естественным образом на векторы произвольной длины, компонентами которых являются такие тройки чисел, т.е.

^уеv ^((г 1 , ^j1 , ^к 1 ), . . . , ^(гп, ^j n , ^кп⁾⁾ = ^(уеу^(г 1 , 31, ^к1), ^{. . .} , Уеу^(гп, ^j n , ^кп)) ^.

Под сложением двух кодов Bo,^ и Bo,i‘ мы понимаем код Bo,i, являющийся следующим смежным классом кода Bo,o:

^B o ,i = ^B0 ,i ^{+ B}o ,i ‘ = ^{{b + b}‘ ^{: b е B}0 ,i , ^b‘ ^{е B}o ,i ‘ ^} = ^B o , o ⁺ g i,   g i = g i + g i - .      (4)

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

вектор b имеет номер (1, г, j, к) если и только если вектор b + (1000000 0) имеет номер (0,г, j, к).

Иначе говоря, код Bi ,i,j представляет собой сдвиг кода Bo ,i,j на вектор (10 0000 00). Тем самым мы определили также следующее взаимно однозначное отображение всех 128-ми троек целых чисел на нечетное полупространство двоичных векторов длины 8:

Уо d(M, к) = b^M, к), М е {0, 1,..., 7}, к е {0,1}.                 (Ф

Это отображение мы также распространяем аналогичным образом (как и для четного отображения) на векторы произвольной длины, компонентами которых являются такие тройки чисел.

Два введенных отображения ‘_ev и ‘а индуцируют следующее взаимно однозначное отображение ‘ всех 256-ти четверок (s, г, j , к) целых чисел над алфавитом Е2 х Е8 х Е8 х Е2 на линейное пространство Е⁸ всех двоичных векторов длины 8:

( ‘ev, если s = 0, [ ‘_Od, если s = 1.

Итак, каждый двоичный вектор длины 8 имеет один номер ДгД, к), и, наоборот, каждая такая четверка целых чисел, где s, к Е {0,1} и г,j Е {0,1,..., 7}, однозначно задает двоичный вектор длины 8. Более того, заданная нумерация линейна по всем индексам при сложении векторов и кодов из всего множества подкодов кода В, которые мы рассматриваем. В частности, верно следующее

Предложение 1.  (i) Отображение ‘ линейно при сложении индексов и кодов, содержа щих слова с этими индексами, т.е. покомпонентная сумма в F2 двух векторов длины 8 с ном ерами b(s‘,г‘ ,j ‘ ,к‘) и b(s‘‘,г‘‘,j ‘‘, к’’) из кодов Bs‘,i‘,j‘ и Bs’’ ,i",j" равна вектору b(s, г, j, к) с номером ьдгдк) = b(s‘,г'д ‘,к‘) + b(s‘‘,г‘‘,j‘‘,к‘‘) = = b(s‘ + s’, г + г‘‘,j‘ + j ‘‘,k‘ + кД, причем этот вектор принадлежит коду Bs,i,j. Напомним, что под сложением индексов г’ + г’’ 11 j ‘ + j" подразумевается соответствующее сложение в поле F8.

(ii) Код B_s ,i,j из (І) равен сумме кодов B_s‘ ,^,ji и B_s‘‘ ,i ‘‘ ,j ‘’.

(Hi) Отображение ‘ линейно по индексам при сложении векторов с этими индексами, т. е. для любых двух векторов b(s, г, j, к) и b(s‘, г’, j‘, к’) имеет место равенство

Ж^М, ^{к) +} (бЖД ‘, ^к’)) = ЖЖ,Ъ ^{к)) +} ЖЖ',^j‘, ^к' )).

3.    Построение [80,40,16]-кодов

Самодуальный [80,40,16]-код, который обозначен буквой Z, строится, как OK-код четвертого порядка, и, как уже было сказано, мы в точности следуем построению двоичного расширенного совершенного кода Голея как обобщенного каскадного кода третвего порядка, приведенному в [10]. Код Z строится как объединение двух OK-кодов третвего порядка, т.е. Z = Zo U Zi. Для построения Z, Zo и Zi, в качестве внешних выберем следующие пять кодов:

тривиальный [10,1,10]-код Ai с повторением:

МДР [10, 3, 818-код A2:

МДР [10, 7,4]8-код A3, дуальный к А₂. т.е. A3 = А^:

тривиальный [10, 9, 2]-код А4 с проверкой на четность;

тривиальный (10, 29, 2)-код V4 с проверкой на нечетность.

Поясним построение МДР-кодов. Код А2 имеет следующую порождающую матрицу Од;

где

1 1 1 1 1 . .          1.         . .1 Од = 0 1 0 X1 х2 . . Xi . .   Xq-1 0 0 1 У1 У2   . . Уі . . yq—1 , о?г

аг

1 + а^і + а² , ^^г   1 + а^і + а^{2і 1}

где a - примитивный элемент поля Fs. Эта матрица отличается от матрицы, приведенной Бушем [12], где он построил такие МДР-коды длины q + 2 для четного q = 2m. Смысл приведенного нами здесв выбора порождающей матрицы в том, что каждый символ, который встречается в каждом кодовом слове, встречается там точно два раза

(что упрощает приводимые доказательства). Для рассматриваемого поля Fs, с примитивным элементом a, таким что a³ = a + 1, эта матрица Ga принимает следующий вид:

Ga =

1111 1 1 1 1 1 1 0 10 1 a³ a⁶ a⁵ a⁵ a⁶ a³ 0 0 11 a⁴ a a a² a⁴ a²

В качестве кода A3 возьмем МДР [10, 7,4]8-код, дуальный к A2, полученный расширением совершенного [9, 7, 3]8-кода Хэмминга над F§. Порождающая матрица Ga t ко да A3, которая нам понадобится, имеет следующий вид:

1 1 1 1 0 0 0 0 0 0 a2 a3 a4 0 1 0 0 0 0 0 a4 a6 a 0 0 1 0 0 0 0 Gat = a2 a5 a 0 0 0 1 0 0 0 ,                               (9) a a5 a2 0 0 0 0 1 0 0 a a6 a4 0 0 0 0 0 1 0 a4 a3 a2 0 0 0 0 0 0 1 где a - тот же самый примитивный элемент поля F§, определенный выше. Строим два OK-кода третьего порядка:

код Z q с тремя внеш ними кодами A2, A3, A4 и внутренними кодами Во, B q ,*, Bo ,j,j' код Zi с тремя внешними кодами V = A2, V = A3, V и внутренними кодами Bi, Вщ, Bi ,t,j. С помощью введенных отображений коды Zq и Zi строятся следующим образом:

Z q = { x = Vc_v( a ⁽²⁾, a ⁽³⁾, a ⁽⁴⁾), a^M E A j , г = 2, 3,4}, Zi = { у = Vo d( v ⁽²⁾, v ⁽³⁾, v ⁽⁴⁾), V^м E V j , г = 2, 3,4}.

По OK-конструкции [10, 11] каждый из кодов Zq и Zi представляет собой (80, 2³⁹,16)-код. Наша цель сейчас показать, что эти коды находятся друг от друга также на расстоянии 16. Сначала мы докажем несколько простых утверждений.

Каждое слово с этих кодов по построению делится па блоки, т.е. с = ( c i, C 2, • • • , сщ). где каждый блок-вектор имеет длину 8. Координатное множество I = {1, 2,..., 80} кодов Zq и Z1 разделим па подмножества I = {8г + 1, 8г + 2,..., 8г + 8} раз/гера 8. г,те г = 0,1,..., 9. т.е. Ij - это координатное mi южсство б.ток-всктора щ.

Лемма 1. Код Z q представляет собой линейный код.

Доказательство. Надо доказать, что сумма любых двух слов, скажем, z = x + у кода Zq. является коновым слове)м. По построению слова x и у имеют вит x = Vc_v( a ⁽²⁾, a ⁽³⁾, a ⁽⁴⁾) и у = Ve v( c ⁽²⁾, с ⁽³⁾, с ⁽⁴⁾), г Де a ^(j), c ^(j) Е Aj для г = 2, 3,4, г де a ^(j) = («!"),..., a^) и c ^(j) = (ci*),..., ci)])) - слова внешнего кода Aj для г = 2, 3,4. Таким образом, нам надо доказать следующее равенство:

z = x + у = Ve _v( u ⁽²⁾, u ⁽³⁾, u ⁽⁴⁾),                                (10 )

где u ^(j) = a ^(j) + c ^(j) и u ^(j) - слово внешнего кода Aj для г = 2,3,4. Как уже говорилось. векторы x и у имеют блочный вит: x = ( x i, x 2,..., x io) 11 у = ( y i, У 2,..., ущ ). где

/ (2)   (3)   (4)                      (2)   (3)(4)

xi = уеv(oi , о- , о- ) и уі = уеу(с- , с- , с- ) По определению четного отображения x = ус y(a(2), a(3), a(4)) =

• (2)   (3)   (4)                 (2)   (3)(4)

= ^(усү^(а і , ^а 1 , ^а 1 ),-••, ^усү^(а іо , ^а 10 , ^а 10 )) =

• (2)   (3)   (4)                  (2)   (3)(4)

= ^(ь(и,^а і , ^а і , ^а і ),..., и ⁽и,^а іо , ^а іо , ^а іо ^)).

Поэтому с учетом предложения 1 получаем для Тх блоков векторов x и у

• (2)    (3) (4)              (2) ’ (3) ’ (4)й

Xi + У і = b (0, а- ' аЧ ,-i Д + b (0, с- , ci Д ci ) =

= b (0, а ( ²⁾ + с ( ²⁾,а ( ³⁾ + с ( ³⁾,а ( ⁴⁾ + с ( ⁴⁾) =

= b(0,U2),u(3),u(4)) =

= усvCu^/uF/Uj4)) = zi, г = !,..., 10, где u^ = а^ + с^ для j = 2, 3,4. Так как все внешние коды Ai линейны, то a(j) + c(j) является кодовым словом, скажем, u(j) для Aj для всех j = 2, 3,4. Поэтому координатные ( j)                                                                                      ( j)        ( j)                        ( j)        ( j) m элементы ui равны сумме коор,тішатііых элементов о-  іі с-  векторов ai  и с- . Таким образом, покоординатная сумма слов уеv(x) и уеДу) является кодовым словом Z0.   □

Приведем без доказательства следующее простое

Предложение 2. Пусть x = ( хі , X2 ,..., x_n) и у = ( уі , у₂ ,..., у „) - два двоичных вектора одинаковой длины, которые разбиты на блоки одинакового размера. Пусть веса обоих векторов wt( x ) и wt( y ) делятся на 4. Если расстояние между каждыми двумя блоками d(xi, yi) кратно 4. то вес их суммві x + у также делнтся на. 4.

Код Zo разобъем на четыре подмножества z0i1,i2):

Z o =    J    z 0 ^i1,i2),                                      (11)

• i1,i2e{ o , 1 }

г^е

Z 0 ^i1,i2) = {усДг і а ⁽²⁾,г 2 а ⁽³⁾, a ⁽⁴⁾) : a ^(j) e Aj , j = 2, 3,4, г і ,» 2 е {0,1}}.

Лемма 2. Вес любого кодового слова кода Z 0 делится на четыре.

Доказательство. Рассмотрим произвольное слово кода Z0, скажем, x = Уеv( a ⁽²⁾, a ⁽³⁾, a ⁽⁴⁾), где a ⁽ⁱ⁾ = (а^), ..., -ід) - слова внешнего кода A_i для г = 2, 3,4. Вектор x имеет блочный вид: x = ( x ₁, x ₂,..., x^ ). г,те x^ ) = у_сv(а⁽²⁾, а⁽³⁾, а⁽⁴⁾) для г = 1,..., 10.

Если x е Z0^i1,0), то утверждение, очевидно, выполняется, так как по построению кода A2 каждое его слово содержит две позиции с одинаковыми элементами. Так как каждый блок четен и встречается два раза, то независимо от значения кодового слова a⁽⁴⁾ в таких двух позициях вес любого слова x = у_еv( a ⁽²⁾, 0 , a ⁽⁴⁾) (т. е. с нулевым словом из A3) всегда кратен 4. Действительно, разные 'значения а⁽⁴⁾ в этих позициях м<зияют вес блока на 4 пли на. 8.

Поэтому рассмотрим случай, когда a ⁽³⁾ = 0. В силу предложения 1, любое слово у_еv( a ⁽²⁾, a ⁽³⁾, a ⁽⁴⁾) можно представить в виде суммы двух кодовых слов, а именно:

у_сv( a ⁽²⁾, a ⁽³⁾, a ⁽⁴⁾) = у_сv( 0 , a ⁽³⁾, a ⁽⁴⁾) + у_сv( a ⁽²⁾, 0 , 0 ).

Рассмотрим расстояния между блоками слова уеv(a(2), 0, 0) и слова уеv(a(2), a(3), a(4)). Координатные позиции вектора a(2) указывают номер смежного класса [8,4,4]-кода Хэмминга, а позиции a(3) и a(4) указывают, какое слово мы выбираем из (8,16, 4)-кода (с расстоянием 4). Поэтому с учетом предложения 2 достаточно убедиться, что любое слово a(3) имеет вес. кративій 4. Так как a(3) - это сумма строк r^. I = 1,..., 7. порождающей матрицы G3 ко да A3, с точностью до умножения на элементы поля Fs, то, еще раз учитывая предложение 2 (так как прибавление любой строки к линейной комбинации других строк не выводит слово из кода, в котором мы находимся), достаточно рассмотреть только все кодовые слова вида реv(0, /Згі, 0), где I = 1,..., 7, а 3 G F§. Но это слова результирующего кода, блоки которых имеют номера b = b(0, 0,j, к), и блочные векторы (длины 8) с этими номерами принадлежат коду Bo,o,j- Так как Bo,o - это расширенный код Хэмминга, то все его слова имеют вес, кратный 4. Тем самым в силу предложения 2 все слова кода Zo имеют вес, который делится на 4. □

Лемма 3. Любое слово кода Zo ортогонально коду Zo, т.е. Zo - самоортогоналънын код.

Доказательство. Нам надо доказать, что любые два слова кода Zo, скажем, x и у, ортогональны друг другу. Так как Zo линеен (лемма 1), то сумма x + у векторов x и у также принадлежит коду Zo. Чтобьi слово x + у имело вес, кратный 4, мощность пересечения ненулевых позиций, т.е. |supp(x) Hsuрр(у)|, должна быть четным числом, откуда и следует ортогональность x и у, а значит, и x и Zo. Таким образом, Zo самоортогонален. □

Итак, мы доказали, что при любом разбиении кода Bo на его подкоды Bo,j, являющиеся сдвигами кода Хэмминга Bo,o, результирующий код Zo представляет собой линейный дважды четный самоортогональный код, т.е. веса всех кодовых слов делятся на 4 и любое кодовое слово ортогонально коду Zo.

Докажем теперь такое же утверждение для кода Zo U Zi.

Лемма 4. Код Z = Zo U Z1 представляет собой линейный код.

Доказательство. По построению код Zi является смежным классом кода Zo. Действительно, к произвольному слову x кода Zo прибавим слово u = р( 1 , 0 , 0 , v ⁽⁴⁾), где v ⁽⁴⁾ - произвольное слово кода V4. В результате получаем у = x + u, т.е. произвольное слово кода Zi. откуда в силу линейности и взаимной однозначности отображения р (предложение 1) следует утверждение леммы. □

Лемма 5. Каждое слово кода Z имеет вес, кратный 4.

Доказательство. По построению любое слово у = ( у і, у 2,..., ущ ) кода Zi имеет вид у = x + u, где u = ( u i,..., u io) и г де u j - это либо вектор веса 1 вида u j = (10 0 0 0 0 0 0), либо вектор uj веса 7 вида Uj = (01111111), причем число таких векторов веса 7 нечетно. Вектор x получен четным отображением OK-конструкцией из внешних кодов A2, A3 и A4. Так как вес вектора u, (содержащего (21 + 1) «тяжелых» блоков Uj)) равен (21 +1)7 + (10 — (21 +1)) = 16 +121, т.е. кратей 4 для любо го целого I, наша цель сейчас свести вычисление веса вектора у к вычислению веса u. Как мы убедились выше, веса четных отображений кодовых слов кодов A2 и A3 кратны 4. Осталось выяснить влияние слова V4 из кода V4. В силу предложения 2, достаточно только вычислить вес любого слова р₀<1( 0 , 0 , v ⁽⁴⁾)- Как мы выяснили раньше, вес этого слова равен весу вектора u. который, как мы показали, равен 16 + 121, т.е. всегда делится на 4. □

Рассмотрим расстояние между кодами Zo и Zi. Пусть x = (xi,..., xio) и у = ( у і,..., ую ) - два произвольных слова из этих кодов соответственно. Каждый блок xj имеет четный вес, а каждый блок у ₅ имеет нечетный вес. Поэтому d(cj, V j) > 10. На самом деле имеет место следующая

Лемма 6. Минимальное расстояние между кодами Zo и Zi рае но 16, т.е. d(Zo, Zi) = 16.

Доказательство. Так как Zo содержит нулевое слово, найдем минимальный вес слов кода Zi. Пусть у = р₀j( v ⁽²⁾, v ⁽³⁾, v ⁽⁴⁾) - произвольное кодовое слово кода Zi. Так как код Bi не содержит нулевого слова, то, по крайней мере, для одной позиции найдется ненулевая тройка ( v ⁽²⁾, v ⁽³⁾, v ⁽⁴⁾) = (0, 0, 0), даже если слова v ⁽²⁾ и v ⁽³⁾ являются нулевыми: v ⁽²⁾ = v ⁽³⁾ = 0. В этом случае (т.е. когда, имеется одна, ненулевая тройка.) у имеет вес 9 + 7 = 16.

Всего код Bi содержит восемь блоков веса 1, которые имеют номера (1, г, 0,0), где г Е {0,1,..., 7}. Но код Bi, как мы отметили выше, содержит слова нечетного веса. Индексы г - это координатньіе элементы слова v⁽²⁾, которые удовлетворяют следующему свойству (см. определение кода): координатные элементы встречаются по парам, т.е. любое слово v⁽²⁾ содержит в виде координат пять пар одинаковых элементов. Ясно, что если слово v ⁽⁴⁾ ко да Bi имеет вес 3 или больше, то для любых слов v ⁽²⁾ и v ⁽³⁾ соответсвующее слово у = Aod( v ⁽²⁾, v ⁽³⁾, v ⁽⁴⁾) будет иметь вес 16 или более. Поэтому наихудший для нас случай, когда слово v ⁽⁴⁾ имеет вес 1 (с единицей в позиции г) и когда блок у ’ = у₀d(v⁽²⁾, г⁽³⁾, 0) имеет вес 3 или 5. В этом случае единица (г⁽⁴⁾ = 1) пере водит у’ в у^, при чем у^ имеет вес 5 или 3. В результате по.тучасм слово у вооа 14 пли 12 соответствешю. Но. если блок у ' имеет вес 3 или 5, это означает, что в позиции г елова v ⁽³⁾ стоит ненулевой элемент, т. е. v ⁽³⁾ = 0. Так как код A3 имеет кодовое расстояние d(A3) = 4, то вектор v⁽³⁾ должен иметь по крайней море 4 ненулевые позиции. Каждая ненулевая позиция вектора v⁽³⁾ с ное юром г означает, что образ соответствующей тройки элементов (^Р),^v(3),^v(4)) при ее нечетном отображении будет иметь вес 3 пли более. Так как число ненулевых позиций слова v⁽³⁾ по крайней мере 4. то результирз’тощий вектор у = у₀d( v ⁽²⁾, v ⁽³⁾, v ⁽⁴⁾) будет иметь вес 16 пли бо.тее. □

Лемма 7. Любое слово кода Z1 ортогонально коду Zq, т.е. Z - самоортогоналъный код.

Доказательство. Утверждение следует в точности из таких же аргументов, которые мы использовали при доказательстве леммы 3.   □

Так как код Z = Z q U Zi имеет к = 40 информационных символов, то нами доказана следующая главная

Теорема 1. При любом разбиении кода B q на его подкоды B q ,j, являющиеся сдвигами двоичного кода Хэмминга B q , q длины 8, результирующий двоичный код Z, построенный приведенной выше обобщенной каскадной конструкцией, представляет собой самодуалъ-ный экстремальный дважды четный [80, 40,16]-код.

Исследование выполнено в ИППИ РАН в рамках фундаментальных исследований по математическим основам теории передачи информации и при частичной финансовой поддержке Национального научного фонда Болгарии (ННФБ) (номер проекта № 20-51-18002).