Теория информации


Полиномиальные коды - часть 2


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

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

Пусть - минимальное расстояние между кодовыми словами, оно равно минимуму среди весов ненулевых кодовых слов. Предположим . Тогда существует такой, что и степень не больше . Вес равен 2, поэтому

и . Следовательно, , что означает, что

должен делиться на , а это невозможно по условию. Если предположить, что , то это приведет к утверждению о том, что должен делиться на , что тоже противоречит условию. Итак, .

Кодирующий многочлен определяет совершенный -код Голея (Golay) с минимальным расстоянием между кодовыми словами 7.

В 1971 году финскими и советскими математиками было доказано3), что кроме кодов Хэмминга и Голея других совершенных кодов нет.

Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида есть кодовое слово .

Упражнение 43

По кодирующему многочлену построить полиномиальные коды для двоичных сообщений 0100, 10001101, 11110.

Упражнение 44

Принадлежат ли коду Голея кодовые слова 10000101011111010011111 и 11000111011110010011111?

  1)

  1

  2)

  1

  3)

  20

© 2003-2007 INTUIT.ru. Все права защищены.




Начало  Назад