Глава 12. Альтернантные коды, коды Гоппы и другие обобщения кодов БЧХ

12.1. ВВЕДЕНИЕ

Альтернантные коды представляют собой большое и мощное семейство кодов, получающееся путем незначительной модификации (проверочной матрицы кодов БЧХ Напомним, что в гл 7 коды БЧХ над GF(q) блоковой длины и конструктивным расстоянием определялись как коды с проверочной матрицей где

примитивный корень степени из единицы. Заменив на элемент вида где — вектор с различными компонентами из поля вектор с ненулевыми компонентами из получим альтернантный код Свойства этого кода резюмированы на рис. 12.2.

Большая свобода выбора в определении альтернантных кодов служит гарантией того, что некоторые длинные альтернантные коды попадают на границу Варшамова — Гилберта (теорема 3) в противоположность ситуации, имеющей место для кодов БЧХ (теорема 13 гл. 9).

Альтернантные коды, как оказалось, действительно образуют большой класс, и многие вопросы для них пока еще остаются открытыми. Например, какие альтернантные коды лежат на границе Варшамова — Гилберта? Как находить их размерность и минимальное расстояние?

Коды БЧХ, естественно, являются частным случаем альтернантных кодов. В § 12.3-12.7 определяются различные другие подклассы альтернантных кодов, а именно коды Гоппы (§ 12.3-12.5, рис. 12.3), коды Сривэставы ( рис. 12.4) и обобщения Ченя — Чоя кодов БЧХ (§ 7, рис. 12.5). Сложные взаимоотношения между этими кодами показаны на рис. 12.1 (без выдерживания масштаба).

Рис. 12.1. Взаимосвязь между различными классами альтернантных кодов 1 — альтернантные коды. 2 — коды Гоппы, 3 — коды БЧХ, примитивные в узком смысле, 4 — коды БЧХ; 5 - обобщение Ченя — Чоя кодов БЧХ, 6 - коды Сривэставы; 7 — обобщенные коды Сривэставы

Кодирование и декодирование альтернантных кодов аналогично кодированию и декодированию кодов БЧХ и обсуждается в § 12.9. Ключевым этапом в декодировании является использование алгоритма Евклида для перехода от вектора-синдрома к многочлену локаторов ошибок и многочлену значений ошибок. Этот метод, естественно, применим также и к кодам БЧХ, и мы сможем восполнить пробел в декодировании кодов БЧХ, оставленный в § 9.6.

Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел или многочленов описывается в § 12.8. Как следствие из алгоритма мы сможем, наконец, доказать результат (следствие 15), несколько раз уже использованный нами в предыдущих главах: если взаимно простые многочлены (или целые числа), то существуют многочлены (или целые числа) такие, что