5.8. ДВОИЧНЫЙ код ГОЛЕЯ 146

где число коэффициентов Сь равных единице, четно. Тогда с (1) = = О, и поэтому X - 1 делит с (х).. Но х - 1 не делит g (х); следовательно,

с{х) = b{x){x-l)g{x) для некоторого b (х). Определим взаимный многочлен:

22 22

С (х) = Ц С22 г" = х22 i; CiX-.

Поскольку с (p-i) = о, для некоторого а (х) имеем

с (х) = а (х) й{х).

Таким образом,

с (X) с(х) = b (х) а (х) (X - 1) g (х) g (х) = b (х) а (х) (х j).

Ниже мы используем это равенство, а сейчас вычислим с (х) с (х) отметив, что произведение многочленов может быть записано в виде свертки:

44 22 и 22

С(Х)С(Х)= i; CiCj iX/ Ц Ц CiC22+i jXi.

/=0 i=0 /=0 1=0

Если считать, что коэффициенты с индексами, меньшими нуля и большими 22, равны нулю, то сумму по i можно заменить суммой от -оо до оо (это позволит избежать дальнейших хлопот с пределами суммирования). Сумму можно разбить на части следующим образом:

с(х)с(х)=] J с-22«-+ I; Ci}C +

/=0 (=-оо t"=-со

44 оо

-j- 2j 2j CjC22.i jX.

/=23 i=-оо

Второе слагаемое равно нулю, так как с? = сс в поле GF (2) и по предположению число коэффициентов Cj, равных единице, четно. В последнем слагаемом сделаем подстановку i = i + 22 - / и в обоих слагаемых заменим / на /. Тогда

21 оо

С (X) с (X) i; i; CiC22+i-rx -f

/=0 (=-00

44 cx>

+ 11 и СгЧ-/-22С/Х/. /=23 (=-pp

Далее заменим С на i во втором слагаемом и положим / = / - 1 в первом слагаемом и / = / + 22 во втором. Это дает

22 оо 22 оо

/=1 j=-оо /=1 t=-оо

22 Г 22

= 11

2j CiC22+l-i + CiC;.j-t=0

L /=! (•=-oo

Ho с (x) с (x)sc кратно многочлену x - 1, и следовательно,

I;q(c23.w + c,,,-) = 0. /= 1, . . ., 22.

Это равенство должно выполняться при сложении по модулю 2. Следовательнр, при целочисленном сложении при каждом / в левой части должно получаться четное число:

и ci (Cit-i Н- Си,) = 2aj, / = 1, . . ., 22

для некоторых чисел aj. Левая часть не меняется при замене / на 23 - /. Следовательно, Oj - Ois-j- Таким образом, суммирование по / дает

22 22 22 11

и .и Ci {C,i j + CiJ = 2 i; = 4 i; С; = 4g

y=0 (=0

для некоторого a. Наконец, левую часть можно переупорядочить. Положим / = 23 - / в первом слагаемом и i = i - / во*втором; тогда

22 22 22 22

ll £ CiCi+j + Ti CrCr-.,- = 4a,

j =1 (=.0 /=! t=0

что вырождается в

S cfj = 4g.

t=0 i+i

Так как двоичные компоненты Ci отличны от нуля в w позициях, отсюда следует, что

W {w - 1) = 4g.

В силу четности w это означает, что w кратно 4, что и доказывает лемму. □

5.8. ДВОИЧНЫЙ КОД ГОЛЕЯ 147

Теперь можно перейти к доказательству следующей теоремы.

Теорема 5.8.3. Код Голея является совершенным кодом, исправляющим три ошибки.

Доказательство. Как уже было указано в начале этого параграфа, необходимо только доказать, что минимальное расстояние равно по меньшей мере 7. В силу леммы 5.8.1 оно равно по меньшей мере 5, а в силу леммы 5.8.2 оно не может быть равно 6. Таким образом, необходимо только доказать, что код не содержит слов веса 5.

Рассмотрим кодовое слово g (х) g (х); в действительности g (х) Й{х) == i:=ix*, так как (X - 1) g (х) g (х) = х" - I = (х -- 1) k=ox. Таким образом, коду принадлежит слово, все компоненты которого равны 1. Прибавление этого кодового слова к любому кодовому слову веса w дает кодовое слово веса 23 - w. Тогда, согласно лемме 5.8.2, в коде не содержится слов с весами, равными 21, 17, 13, 9, 5 и 1; в частности, не содержится слов веса 5. Теорема доказана. □

Отметим, что из доказательства теоремы следует также, что все веса слов в коде Голея исчерпываются числами О, 7, 8, И, 12, 15, 16 и 23. Просчитанное на ЭВМ число слов каждого веса приведено в табл. 5.3.

Кроме двоичного кода Голея существует также совершенный троичный (11, 6, 5)-код Голея. Этими двумя кодами исчерпываются все нетривиальные примеры совершенных кодов, исправляющих более одной ошибки.

Таблица 5.3

Веса слов кода Голея

Число слое