Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.3.2. Коды Голея

Проводя поиск совершенных кодов, Голей заметил, что равенство (1.4) удовлетворяется при (см. [11]). Отсюда вытекает возможность существования совершенного -кода. Такой код действительно существует и является непримитивным кодом БЧХ, который строится следующим образом.

Пусть а — примитивный элемент Поскольку порядок равен 23. Код задается требованием, согласно которому должны быть корнями Корнями минимальной функции элемента являются

Заметим, что корнями являются, в частности, все элементы, которые должны быть корнями Поэтому . В зависимости от того, какой неприводимый многочлен используется для построения порождающий многочлен -кода Голея задается либо формулой

либо

Этот порождающий многочлен был получен исходя из требования, чтобы код БЧХ исправлял две ошибки. Алгоритм декодирования кодов БЧХ, который будет описан в гл. 5, обеспечивает исправление двойных ошибок. В действительности кодовое расстояние этого кода равно 7 и все тройные ошибки можно исправлять либо табличным поиском, либо с помощью одного из методов, описанных в следующей главе. Расширенный -код весьма полезен, поскольку для него

Известен спектр этих кодов. Для -кода весовая функция

Отсюда легко получить весовую функцию расширенного -кода, поскольку вес любого кодового слова -кода, имеющего нечетный вес, увеличивается на 1, так что

Код Голея с параметрами -единственный известный нетривиальный совершенный двоичный код, исправляющий кратные ошибки. Другими известными двоичными совершенными

кодами являются коды Хемминга и коду с повторениями при нечетном Наконец, единственным известным недвоичным совершенным кодом является троичный [определенный над полем GF (3)] (11,6) - код Голея с d = 5.

<< Предыдущий параграф Следующий параграф >>
Оглавление