(13.24)

= [1, а, а\ а?

а"-1].

Любой ненулевой синдром может быть записан в виде а = а" гдеО<а<д - 1 иО<Ь<п. Так как а" G GF (q), то этот синдром, очевидно, соответствует одной ошибке величины а"" с локатором а.

При q = 2 этот совершенный код с исправлением одной ошибки является циклическим примитивным двоичным БЧХ-кодом. Однако, при q Ф 2 он уже не циклический, так как а" 1, а констацикли-ческий и его кодовые слова - многочлены некоторого идеала в кольце многочленов по mod (х" - а").

Если (п, q - 1) = I, то над полем GF (q) в метрике Хэмминга существует циклический совершенный код с блоковой длиной ге, исправляющий одну ошибку. В качестве корней порождающего многочлена этого кода могут быть выбраны элементы р, р,

. . ., Р" , где Р G GF (д"") Ир - примитивный корень ге-й степени из единицы. В этом случае мы получим БЧХ-код с конструктивным расстоянием Хэмминга 2. Однако можно положить р = а, где а - другой примитивный корень ге-й степени из единицы, а у - решение сравнения (q - 1)/= 1 mod re. Тогда р = а, р = а+, ... и среди корней порождающего многочлена имеются две последовательные степени элемента а. При этом возникает БЧХ-код общего вида с расстоянием Хэмминга 3, согласно разд. 10.3.

Если п. о. д. (ге, g - 1) = 7 :/= 1, то над полем GF (q) в метрике Хэмминга никакой совершенный код с блоковой длиной ге, исправляющий одну ошибку, не может быть циклическим. Порождающий многочлен такого кода должен быть неприводимым делителем много-

члена X

- 1. Но х" - 1 = [] (х"з - а(«-1) */J) где а - при-

митивный элемент поля GF (q). Следовательно, любой неприводимый делитель многочлена ж" - 1 Хэмминга которого равен 2. щ

имеет делитель степени ге , вес

Известны также и другие классы совершенных кодов с исправлением одной ошибки. Васильев [1962] и Шёнгейм [1968] построили много систематических нелинейных совершенных кодов, исправляющих одну ошибку. Ллойд [1957[ и Рус [1965] показали, что если существуют некоторые другие нелинейные совершенные коды, то они также должны иметь определенную алгебраическую структуру. Представляется также возможным существование совершенных кодов с метрикой Хэмминга, исправляющих одну ошибку над алфавитом, порядок которого не есть степень простого числа. В настоящее время не известно ни одного примера таких кодов. Голомб и Познер [1964] показали, что при д = 6иге = 7в метрике Хэмминга пет ни одного кода, исправляющего одиночные ошибки. Часть своего доказательства они приписывают Р. Блоку и М. Холлу.

Теорема 13.25 доказывает существование коротких совершенных кодов над алфавитом составного порядка, исправляющих несколько ошибок в метрике Ли.

13.25. Теорема. Для любого натурального t над кольцом классов вычетов mod g = 2 -f 2i + 1 в метрике Ли существует совершенный код с блоковой длиной ге = 2, исправляющий t ошибок. Этот код является негациклическим и порождается многочленом g(x)= х + {2t + 1).

Доказательство. Как видно из рис. 13.3, множество векторов ошибок {Ео, для которых 1 -f 1 1 < , может

Рис. 13.3. Двумерный шар с радиусом Ли, равным 3.

быть разбито па пять классов:

класс 1: Е-0, ЕО; класс 2: Eg <0, Е 0;

Если q - составное нечетное число, то д - 1 ненулевых г-мер-ных последовательностей над кольцом классов вычетов по mod q молчно разбить на (д" - 1)/2 подмножеств, каждое из которых содержит векторы вида (oj, а, • •, а) и (-Oj, -а, • •, -а). Если в качестве столбцов проверочной матрицы SB выбрать по одному представителю из этих {q - 1)/2 множеств, то получим в метрике Ли линейный совершенный код с блоковой длиной п = (q"" - 1)/2 и скоростью передачи (п - г)/п, исправляюш,ий одну ошибку.

Покажем теперь, что если q - степень простого числа, то над GF (q) для чисел п вида (13.22) суш;ествует линейный совершенный код с блоковой длиной п, исправляющий одну ошибку в метрике Хэмминга. Пусть а - примитивный элемент поля GF (q), и пусть код задается проверочной матрицей

<>>>><>><><>*ХХХХХХХ(<< >>>>>iHiH><iDiDXXXXXb.<i

SXQ Й Й Й Й Й Й Й С?§ § § § § рц рц о, еааМ W М Й Й й Й § § §S § § § й й й

WQQPPQ00C!OOO&(p4f4fi<P4fQWHHWHMW

ддрдддроооооорчрчрчмррмннннй*!; <;ддддд>чоооооос>Рн1ПРрррт1Пннн<:<: <л<;ддд>.>ч>чо.иооо><!РРМРРммммн<;-<<!; -<<;<;Дн>ч>ч>нчооо><!Х>«дррмР5<!;<5-<<;

о о. в-

р. в

класс 3: < О, <0; класс 4: £о > О, < 0; класс 5: Ео = Ei = 0.

Число векторов ошибок в каждом из классов 1, 2, 3 и 4 равно

i t (t + 1)/2, так что обш,ее число векторов ошибок с весом

Ли < t равно = I + At{t + 1)/2 == д. Следовательно, любой код длины п = 2 над кольцом вычетов mod g = 2 + 2< + 1, исправляющий t ошибок в метрике Ли, является совершенным.

Покажем теперь, что минимальный вес для негациклического кода с порождающим многочленом g (х) = х {2t + i) и h (х) = = X - {2t + I) равен 2t + 1. Действительно, пусть [Со, Cjl - ненулевое кодовое слово веса < 2t. Предположим, что С - координата с меньшим модулем (в противном случае можно было бы рассмотреть негациклический сдвиг [-Cj, Col) исходного слова. Если I Со I -f I Ci I < 2< и I Ci < Со I, то I Ci Ki, так что \Ci\ = t - а, где 0< a<.t. Так как С (х) кратен g (х), то Со = {2t + 1) С mod д. Так как {2t + I) (t - а) = д - {2а + 1) t - а - I, то либо I Со I > 2«+ 1 и I Со I + I Ci I > 2i + 1, либо I Со I = (2а + 1) + а + + i и I Со I + I Ci 1= (2а + 2) f -f 1 > 2 -f 1, причем равенство достигается тогда и только тогда, когда а = 0. Следовательно, минимальный вес любого ненулевого кодового слова равен 2< + 1. Он достигается на словах [- {t + 1), t], [{t + 1), - и их нега-циклических сдвигах, щ

13.26. Следствие. Если число 2f + 2i -Ь 1 делит д, то над алфавитом вычетов mod д в метрике Ли существует совершенный, код длины п = 2, исправляющий t ошибок.

Доказательство. Пусть q = к {2t + 2t + 1). В качестве кода можно взять множество из к (2t + 2i + 1) слов вида 1Со + i {2t + 2t + 1), Ci + i {2t + 2t + 1)], где 0 < i </c, 0 < <:k и с = [Со, Cil - слово совершенного кода над кольцом вычетов mod (2it-j-2<4-1), исправляющего « ошибок в метрике Ли.

Теорема 13.25 гарантирует существование совершенных линейных кодов в метрике Ли над некоторыми кольцами чисел, не являю- щимися нолями. Хорошие линейные коды над такими алфавитами! весьма исключительны. Например, Леви [1964] показал, что лучшие из длинных линейных кодов над некоторыми алфавитами, не являю щимися полями, обеспечивают минимальное расстояние, лежащее! существенно ниже известных нижних границ (теорема 13.71) длг нелинейных кодов над такими алфавитами.

На рис. 13.4 дается геометрическая интерпретация совершеппогс кода длины 2 над кольцом вычетов mod 25, исправляющего 3 ошибк1 в метрике Ли. 25 кодовых слов обозначены жирными буквами А

квазисовершенных двоичных кодов. Как будет показано в разд. 13.6, очень длинные коды могут быть квазисовершенными только тогда, когда их скорость передачи очень велика.

*13.3. Границы dn + I - к

Как было показано в разд. 1.2, ка;кдый линейный код с длиной п и размерностью к может быть задан с помощью проверочной матрицы с п столбцами и п- к линейно независимыми строками. Если к этой матрице дописать к - 1 дополнительных строк, представляющих собой п-мерные единичные векторы, то получится проверочная матрица некоторого подкода исходного кода. Этот линейный подкод непулевой размерности состоит из тех кодовых слов, у которых в соответствующих к - 1 позициях расположены нули. Так как ненулевые координаты в словах этого подкода расположены только в п - (к - 1) позициях, то для кодового расстояния выпо.ппяется неравенство

(13.31) d + \ - к.

Это неравенство сохраняется также и для исходного кода. Рассмотрим теперь коды, для которых

(13.32) d = п + I - к.

Такие коды мы будем называть кодами с достижимым максималъ ным расстоянием ). Коды этого класса обладают и другими свойствами. Для любых заданных d позиций такой код должен содержать q - 1 кодовых слов веса d, все ненулевые символы которых расположены в заданных d позициях. Размерность подкода, состоящего из этих слов, равна 1; размерность объемлющего подкода, состоящего из кодовых слов, содержащих в произвольных заданных п - W позициях нули {w d), равна w -\- \ - d.

Любой код, удовлетворяющий условию (13.32), имеет точно одно слово веса d, содержащее символ 1 в произвольно заданной позиции, п ненулевые символы точно ъ d - 1 других позициях; он содержит точно п - {d - i) ~ к кодовых слов веса имеющих символ 1 в произвольно заданной позиции и ненулевые символы в каждой из d - 2 наперед заданных позиций. Если бы какая-либо пара из этих к кодовых слов имела бы один и тот же ненулевой символ в одной и той же из d - 2 фиксированных позиций, то разность этих слов дала бы кодовое слово веса << d. Следовательно, kq - 1. Таким образом,

(13.33) если d = n + l-/с>2, тog>•--l.

) Некоторые авторы называют такие коды оптимальны.чи или .чаксималъ-иыми (в русской литературе встречается термин «максиминные» - перев.). Мы не будем использовать столь общих названий для этих кодов с весьма специальными свойствами.

В, С, . . ., V (Например, А = [О, 0], J = [9, 131.) Буква в каждой из 625 клеток таблицы соответствует тому слову, которое должен выбирать декодер, исходя из полученного слова. Например, если получено слово [11,7], то декодер декодирует его как М, так как слово М = [12,9] является к нему ближайшим. Аналогично, полученное слово [0,4] будет декодировано как [-3,4] = [22,4[ = W.

Верхняя строка на рис. 13.4 яв.ляется соседней с нижней, а левый столбец - соседним с правым: пространство, изображенное на рис. 13.4, топологически эквивалентно тору. С этой точки зрения задача конструирования совершенных кодов в метрике Ли эквивалентна задаче сферической упаковки тора. Рис. 13.4 иллюстрирует упаковку тора размерами 25 X 25 25 двумерными сферами радиуса 3.

Голомб и Велч [1968] показали, что эта задача является частным случаем более общей задачи об упаковке (polyomino-packing problem). Они высказали гипотезу, что при / >1,7г>2ид>3не существует совершенных кодов в метрике Ли, и доказали несколько частных случаев этого предположения.

Помимо двоичных кодов с повторением известны только два совершенных кода с/>1ии>2 - так называемые коды Голея. Оба они являются циклическими. Двоичный код Голея имеет блоковую длину 23, скорость передачи 12/23 и совпадает с БЧХ-кодом, исправляющим две ошибки, рассмотренным в примере 5.6. БЧХ-конструкция этого кода гарантирует, что минимальное расстояние этого кода 5. Однако истинное минимальное расстояние кода равно 7. Он является совершенным и исправляет три ошибки. Троичный код Голея имеет блоковую длину 11, скорость 6/11. Это совершенный код с исправлением двух ошибок. Оба кода Голея принадлежат к кодам, построенным с помощью квадратичных вычетов, которые мы будем рассматривать в разд. 15.2.

Другие совершенные коды не известны. Числа п ш t, для которых делит д, редки. Но даже для таких чисел может не существовать совершенных кодов. Например, в двоичном случае Kj"" = 2. Однако Голей [1949], Кохен [1964] и Э.лтер [1968] доказали, что для g = 2, 3, 4, 5, 7 и 9 троичный код Голея является единственным нетривиа.тьпым совершенным кодо.м, исправляющим две ошибки.

Для линейного совершенного кода с исправлением t ошибок! каждое слово веса ;=С t должно быть лидером смежного класса! и каждый лидер смежного к.тасса до.лжен иметь вес t.

Если каждое слово веса t является лидером смежного класса! и вес каждого лидера смежного класса t + i, то код называется квазисовершенным. Двоичных квазисовершенных кодов оказалось значительно больше, чем двоичных совершенных кодов. Горенстейн,! Питерсон и Цирлер [1960] показали, что все двоичные примитивные БЧХ-коды с исправлением двух ошибок являются квазисовершенными, а Вагнер [1966, 1967] построил несколько нециклических