Совершенный код Голея

В этом разделе с помощью конструкции квадратично-вы- четных кодов мы построим совершенный код Голея, т. е. код, содержащий 212 слов длины 23, который исправляет 3 ошибки (кодовое расстояние равно 7). Вычислением можно найти объем 23-мерного шара радиуса 3 в Е23:

Поэтому в булев куб Я23 можно вложить не более 212 шаров радиуса 3. Так что построенный код будет разбивать булев куб Я23 на шары радиуса 3. (Поэтому он и называется совершенным.)

Обозначим через G23 квадратично-вычетный код при р = 23, который в обозначениях предыдущего раздела порожден многочленом /(&*).

Теорема 4.14. Количество кодовых слов в С?2з равно 212, а кодовое расстояние равно 7.

Доказательство. Квадратичных вычетов, которые образуют подгруппу индекса 2 мультипликативной группы поля вычетов GF(23) столько же, сколько и квадратичных невычетов (смежный класс по этой подгруппе), степень многочлена f(x) при р = 23 равна 11. Значит, размерность идеала (f(x)) равна 12 и он содержит 212 элементов.

Остачпось найти кодовое расстояние. Из (4.G) следует, что оно не больше 7.

Докажем сначала, что если вес многочлена (точнее соответствующего класса вычетов в кольце GF(2)/(.т23 — 1)) из кода Голея нечетен, то он не меньше 7. Используем те же обозначения, что в предыдущем разделе.

Возьмем многочлен с(х) Е G23 нечетного веса w = 2s + 1. Его корнями будут такие степени шк примитивного корня, для которых к Е (?23-

Вес многочлена с(х) = с(:с-1) также равен w. Поскольку — 1 является квадратичным невычетом по модулю 23, корнями с(х) будут такие u;fe, что к Е JV23 (произведение вычета на невычет является невычетом).

Поэтому произведение с(х)с(х) делится на взаимно простые многочлены f(x) и д{х), а значит, и на их произведение

Но с(1) = с(1) ^ 0, так как w нечетен, то есть с(х)с(х) не делится на х + 1. Значит, выполняется равенство

При перемножении с(х) и с(х) получается нс более w2 мономов, из которых w равны 1 (произведения хк и х~к. Чтобы в результате получилось не меньше 23 мономов, должно выполнятся неравенство

из которого получаем w ^ 7.

Пусть теперь вес w многочлена из кода Голея с(х) Е G23 четен.

Докажем, что w ^ 4. Для этого заметим, что

так как 1, 2, 3, 4 являются квадратичными вычетами по модулю 23 (211 = 23-89 + 1. З11 = 23-7702 + 1). Поэтому применимо то же рассуждение с матрицей Вандермонда, что и в случае кодов БЧХ.

Наконец докажем, что если вес многочлена из кода Голея четен, то он делится на 4. Это, в частности, исключает слова веса 6. (Рассуждение заимствовано из книги [3].)

Пусть с(.т) — многочлен четного веса w. Тогда с(1) = 0, т. е. (# — 1) | с(х), откуда следует, что с(х)с(х) = 0 mod х23 1.

Из равенства с(х)с(х) = 0 получаем равенства для коэффициентов с* многочлена с(х), рассматриваемых как целые числа: для г = 0,..., 22 имеем

Меняя местами г и j, получаем равенства аг = а 23 при г ф 0. Поэтому

т. е. из четности w следует, что w делится на 4. ?

Мы доказали существование кода Голея, но не предъявили его явно. Код Голея порождается, например, многочленом q(x), который записывается явно как

Действительно, 2 — квадратичный вычет по модулю 23 и умножение на 2 по модулю 23 сохраняет и квадратичные вычеты, и квадратичные невычеты. Поэтому

(в первом равенстве мы учли, что характеристика поля равна 2). То же самое выполняется и для сумм степеней, которые являются квадратичными невычетами. Поэтому

(последнее равенство вытекает из со23 = 1). Так как —1 является квадратичным невычетом, а со~1 также является порождающей группы корней 23-й степени из единицы, выбором порождающей со можно добиться, чтобы А = 0. Это означает, что со является корнем многочлена /, a w_1 - нет. Кроме того, q( 1) = 1^0. Поэтому (q(x),x23 1) = f(x) и многочлен q(x) порождает код Голея, так как q(x)/f(x) является обратимым элементом кольца GF(2)/(x23 — 1) (умножение порождающей идеала на обратимый элемент не изменяет идеал).

Итак, код Голея образуют линейные комбинации строк, которые получаются циклическими сдвигами из строки (коэффициенты многочлена записаны в убывающем порядке)

00001010011001101011110.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >