ГЛАВА IX. ОПТИМАЛЬНЫЕ КОДЫ

1. Эквидистантные коды

В § 6 гл. VI было показано, что при определенных значениях пит оптимальные (в смысле Хэмминга) коды должны оказаться эквидистантными. Задачу о линейных формах, представляющих такие коды, решает следующее положение.

Теорема IX.1. Если линейные формы

(IX.1.1)

представляют собой все возможные линейные формы, определенные над данным нолем, то значность кода равна

(IX.1.2)

а его комбинации отличаются одна от другой точно в

(IX.1.3)

позициях, причем все комбинации (кроме ) содержат нулей и по всех остальных символов.

Первое утверждение теоремы очевидно, так как число всех возможных линейных форм, определенных над данным полем согласно (VIII.5.25) и (VIII.5.4), равно

(IX.1.4)

что совпадает с (IX.1.2).

Определим далее вес комбинаций кода (IX.1.1). Для этого воспользуемся соотношением (VIII.5.26) и учтем, что в нашем случае множество совпадает с для всех i от 1 до

(IX.1.5)

Подставляя в (IX.1.5) значение (VIII.5.8), найдем

Изменяя порядок суммирования, получим

(IX.1.6)

учитывая, что

(IX.1.7)

так как

(IX.1.8)

, если , если . Подставляя (IX.1.7) в (IX.1.6), найдем

(IX.1.9)

откуда окончательно получим

(IX.1.10)

Таким образом, каждая комбинация кода (IX.1.1) действительно содержит одинаковое число отличных от нуля символов.

Доказательство третьего положения теоремы IX.1 несложно.

Пример. Пусть , Тогда множество линейных форм (IX.1.1) запишется так [см. VI.1.7):

(IX.1.11)

На табл. VI.4 приведены все комбинации кода (IX.1.11). Непосредственной проверкой нетрудно убедиться, что у этого - кода число символов , и все комбинации отличаются точно в позициях, что соответствует условию теоремы IX.1. Кроме того, каждая комбинация приведенного кода (кроме ) содержит два символа 0 и по три символа 1 и 2, что находится в полном соответствии с теоремой IX.1.

Выделим из (IX.1.1) максимальное подмножество, такое, что любые две его формы были бы -попарно линейно независимы.

В случае (IX.1.11) такой системой является

(IX.1.12)

либо

(IX.1.13)

и другие, им аналогичные.

Теорема IX.2. Если линейные формы

(IX.1.14)

представляют собой максимальное множество попарно линейно независимых форм, определенных над данным полем относительно независимых переменных, то знач-ность кода (IX.1.14) равна

(IX.1.15)

а его комбинации отличаются одна от другой точно в

(IX.1.16)

позициях.

Доказательство этой теоремы по своему существу не отличается от доказательства предыдущей теоремы.

Построив коды (IX.1.12)-(IX.1.13), можно убедиться, что они являются эквидистантными.

В заключение заметим, что линейные формы, представляющие эквидистантныи код с параметрами и , могут быть найдены простым -кратным повторением линейных форм (IX.1.14). В частности, при получится эквидистантный код с параметрами (IX.1.2)-(IX.1.3). Однако комбинации такого кода уже не будут содержать по всех отличных от нуля символов, как это было в случае (IX.1.1).