6.10. НЕ СУЩЕСТВУЕТ НЕИЗВЕСТНЫХ СОВЕРШЕННЫХ КОДОВ

В конце 40-х годов были открыты три типа совершенных кодов:

(i). Линейные коды Хэмминга, исправляющие одиночные ошибки. С двоичным вариантом этих кодов мы встречались в § 1.7. В гл. 7 мы построим коды Хэмминга над GF(q). Эти коды имеют параметры

(ii). Двоичный [23, 12, 7]-код Голея (§ 2.6 и гл. 20).

(iii). Троичный [11, 6, 5]-код Голея

Как мы увидим в гл. 20, параметры двух кодов Голея определяют их однозначно: любой код с такими параметрами эквивалентен одному из кодов Голея. Однако положение не таково для совершенных кодов, исправляющих одиночные ошибки. В 1962 г. Васильев построил семейство нелинейных двоичных кодов, исправляющих одиночные ошибки и имеющих те же самые параметры, что и коды Хэмминга (см. § 2.9). Позднее Шонхейм и Линдстрем построили нелинейные коды с теми же самыми параметрами, что и коды Хэмминга, над полями Галуа GF(q) для всех q. Этот вопрос все еще не решен до конца.

Задача (нерешенная). (6.6). Найти все совершенные нелинейные коды, исправляющие одиночные ошибки, над полями Галуа GF(q).

Наконец, имеются еще тривиальные совершенные коды: (i) код, содержащий только одно кодовое слово;

(ii) все пространство

(iii) двоичный код с повторением нечетной длины.

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

Теорема 33. (Титвайнен и Ван Линт). Нетривиальный совершенный код над любым полем Галуа GF(q) должен иметь те же самые параметры что и один из кодов Хэмминга или Голея.

Доказательство мы разобьем на пять частей, а именно на теоремы 37—41. Идея доказательства состоит в том, чтобы пока

зать, что только в случаях, приведенных выше, многочлен Ллойда имеет различные целые корни, лежащие на отрезке

Пусть код на всем протяжении § 6.10 обозначает совершенный -код над где простое число, и пусть обозначают целые корни многочлена (см. теорему 32).

Вначале приведем несколько лемм.

Лемма 34. (Условие сферической упаковки.) Число кодовых является степенью и для некоторого целого числа выполняется равенство

Доказательство. Так как код — совершенный (см. теорему 6 гл. 1), то

Следовательно,

Таким образом, делит число По лемме 9 гл. делит а значит, является степенью

Лемма и если код нетривиален, то не равны нулю.

Доказательство. Из выражения (6.23), используя равенство (см. упражнение (18) гл. 1), получаем

(по лемме 34).

Кроме того, из (6.23) следует:

что не равно нулю, так как и

что равно нулю, только если Но и поэтому это влечет неравенство которое означает, что код тривиальный.

Лемма 36. Числа удовлетворяют равенствам:

Доказательство. Из теоремы 15 гл. 5 вытекает, что представляет собой многочлен от степени Коэффициент при Xе равен а коэффициент при херавен

Теорема 37. Совершенный код над исправляющий одиночные ошибки, имеет те же самые параметры что и код Хэмминга.

Доказательство. Условие сферической упаковки (лемма 34) означает, что

а теорема Ллойда (теорема 32) говорит, что многочлен

имеет целый корень Таким образом, Следовательно, Теперь из границы сферической упаковки получаем, что мощность этого кода равна

Более того, как и код Хэмминга, этот совершенный код имеет одинаковые спектры весов и расстояний. Это следует из теоремы 4, обобщенной на случай кодов над так как

Теорема 38. Не существует нетривиального двоичного совершенного кода, исправляющего двукратные ошибки.

Доказательство. Условие сферической упаковки означает, что

Многочлен Ллойда имеет вид где Следовательно, по лемме 35 этот многочлен должен иметь различные корни являющиеся четными числами, большими чем 4. Так как то где Тогда и поэтому условие (6.27) принимает вид

Это равенство невозможно, так как приведение обеих его частей по модулю 16 дает сравнение т. е. противоречие.

Теорема 39. Единственными возможными параметрами для нетривиального совершенного кода, исправляющего двукратные ошибки, над полем являются параметры троичного кода Голея.

Доказательство. Условие сферической упаковки выглядит теперь таким образом:

что влечет

Из леммы 36 следует, что

Заменяя получаем, что

Так как по лемме то можно положить где . Подставляя это в (6.29), возводя в квадрат и деля обе части на получаем выражение

Все члены этого выражения, кроме — , делятся на Следовательно, или Если то должно делиться на 4, и поэтому что невозможно в силу теоремы 38.

Теперь предположим, что Если то (6.30) принимает вид

Если то это уравнение не имеет решения. Для значений после деления на 3 получаем соотношение

Следовательно, и поэтому Это влечет т. е. мы получили параметры троичного кода Голея.

Наконец, предположим, что где Сравним обе части уравнения (6.30) по модулю 9:

что показывает, что так что или иначе (умножая обе части на 4)

Следовательно, Из условия следует, что Тогда выражение (6.30) принимает вид

или

Таким образом получили, что правая часть этого равенства делится на более высокую степень 3, чем левая часть.

Замечание. Поиск на вычислительной машине что единственными решениями уравнения (6.25) в диапазоне являются тривиальные решения, параметры кодов Голея и кодов Хэмминга и еще одно решение: Но теорема 38 показывает, что кода с такими параметрами не существует.

Задача (нерешенная). (6.7). Как близко мы можем подойти к этим параметрам: существует ли [90, 77, 5] двоичный линейный код?

Теорема 40. Не существует нетривиальных совершенных кодов над полями Галуа исправляющих ошибок если

Доказательство, (i). Вначале мы покажем, что Если целое число, где то положим Ясно, что По лемме поэтому

Следовательно, либо два некоторых числа равны, скажем, либо для случая, когда числа равны числам в некотором порядке

В первом случае и если то Во втором случае для некоторых и (меняя местами если это необходимо) получаем, что Следовательно, .

(ii). Легко получить теперь, что

Полагая сразу же получаем неравенство

(iii). Далее имеем

(если из суммы взять только член с

(iv). Теперь мы воспользуемся известным неравенством между взвешенным средним геометрическим и взвешенным средним арифметическим, которое утверждает, что

для любых действительных чисел и удовлетворяющих условию

Поэтому

[ силу (i) b (6.34]

(снова согласно

Итак, мы применили к числам усиленный вариант неравенства между средним геометрическим и средним арифметическим. В силу леммы 36 последнее выражение равно

это неравенство получено путем элементарных преобразований условии, что Объединение выражений (6.33) и (6.36) дает следующую верхнюю оценку для

или

(v). Так как число

должно быть целым, то получаем следующее условие:

Предположим, что а является наибольшей степенью делящей одно из чисел Что в таком случае мы можем сказать о числе, являющемся степенью и делящем произведение Это число равно самое большее

и при этом необходимо, чтобы Следовательно,

Таким образом, число делит для некоторого и поэтому

Из (6.37) и (6.39) следует, что

откуда получаем, что Но упоминавшийся выше машинный поиск показал, что в этом диапазоне нетривиальных совершенных кодов не существует.

Теорема 41. Единственными возможными параметрами нетривиального двоичного совершенного кода, исправляющего ошибок, являются параметры кода Голея.

Доказательство. Из (6.26) получаем, что

Так как число - четное, то из (6.38) и (6.40) следует, что число делится на следовательно,

Оставшаяся часть доказательства проводится аналогично доказательству теоремы 40: используя соотношения (6.32) и (6.35), получают верхнюю границу для подобную оценке (6.37).

Код, параметры которого совпадают с параметрами двоичного -кода Голея, имеет те же самые спектры весов и расстояний, что и код Голея. Это следует из теоремы 4, так как Аналогичное утверждение справедливо и для троичного кода Голея.

ЗАМЕЧАНИЯ К ГЛ. 6

(см. скан)

(см. скан)