7. Оценки для кодового расстояния

Выше мимоходом отмечалось, что кодовое расстояние

(VI.7.1)

Коды, в которых

(VI.7.2)

условимся называть максиминными.

Теорема VI.5. Система линейных форм определяет максиминный код лишь тогда, когда любые m ее форм линейно независимы.

Следствие 1 (теоремы VI.5). В контрольной подматрице максиминного кода любой минор порядка имеет ранг .

Следствие 2 (теоремы VI.5). Не существует максиминных кодов для случая и . (Исключая лишь тривиальные коды с или .

Доказательство приведенных положений читатель может провести на основе теорем (VI.1)-(VI.4) Отметим, что ряд максиминных кодов может быть синтезирован на основе матриц Вандермонда [57] и на основе латинских (магических) квадратов [151, 32].

Оценка (VI.7.1) приемлема для малых значений m и k и в основном оказывается полезной для кодов с основанием больше двух. (В бинарном случае существуют лишь тривиальные максиминные коды.) По мере роста k оценка (VI.7.1) оказывается все более и более завышенной. Для достаточно больших k (сравнительно с ) успешно применяется другая оценка, получаемая на основании следующих рассуждений.

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

(VI.7.3)

Учитывая симметрию линейного кода и то, что число d задается кодовой комбинацией наименьшего веса, приходим к выводу: число d максимально тогда, когда конечное число А отличных от нуля символов равномерно распределено среди комбинаций кода (среди всех комбинации кола, кроме комбинации , состоящей только из символов 0). Таким образом, имеет место утверждение.

Теорема VI.6. В линейном коде число

(VI.7.4)

Следствие 1 (теоремы VI.6). Если в каком-нибудь линейном коде , то этот код является оптимальным и эквидистантным [любая комбинация, кроме , содержит точно отличных от нуля символов и, следовательно, отличается от любой другой точно в позициях [см. (VI.4.9) и следствие (леммы VI.3)].

Легко заметить, что эквидистантные коды должны существовать при

(VI.7.5)

так как в этом случае оказывается целым числом, равным

(VI.7.6)

где .

Оценка (VI.7.4) более универсальна, чем (VI.7.1). Она впервые была опубликована в широко доступной литературе почти одновременно в работах (56, 139] и носит название оценки Плоткина.

Следствие 2 (теоремы (VI.6). Если значность кода

(VI.7.7)

то максимально достижимое значение

(VI.7.8)

Доказательство этого утверждения сводится к доказательству того, что

(VI.7.9)

Действительно,

(VI.7.10)

В силу условия (VI.7.7)

(VI.7.11)

и, следовательно, равенство (VI.7.9) имеет место, ибо

(VI.7.12)

Следствие 3 (теоремы VI.6. Для бинарных кодов значности

(VI.7.13)

оценка

(VI.7.14)

оказывается завышенной по крайней мере на единицу для всех

(VI.7.15)

или, что то же самое,

(VI.7.16)

Согласно теореме VI.4 и следствиям 1—2 (теоремы VI.4) строки контрольной подматрицы кода при должны содержать не менее чем символов 1 и отличаться одна от другой менее чем в позициях.

Эти требования не выполняются даже для двух ее строк, когда число k удовлетворяет условию (VI.7.15).

Уточнение неравенств (VI.7.15) и (VI.7.16) связано с определением числа k, исходя из предположений о том,

что при — условию теоремы VI. 4 должны удовлетворять 3, 4, контрольной подматрицы.

Рис. VI.1. Границы для кодового расстояния при достаточно больших (по материалам работы 1 — верхняя граница Хэмминга; 3-нижняя граница Варинамова— Гилберта; 3 — верхняя граница Плоткина.

Вывод этих соотношений как в бинарном, так и в небинарном случае представляет безусловный интерес.

Для кодов с необходимое число проверочных символов k оценивается с помощью соотношения, предложенного Хэммингом [176]:

(VI.7.17)

Оценка Хэмминга приводит к удовлетворительным результатам для кодов с . Ее смысл будет разъяснен при рассмотрении способа коррекции ошибок методом контрольных чисел.

Все приведенные выше оценки дают представление о верхней границе числа d при фиксированных значениях и b или оценку снизу числа k при заданных m, d и . Гильберт [78] нашел условие, при выполнении которого заведомо может быть построен код с заданными параметрами.

Варщамов Р. Р. [70-72] существенным образом уточнил его для бинарных кодов, а Остиану В. М. [133-135], используя методику Варшамова, обобщила его на случай кодов с .

Теорема VI.7. Всегда можно построить групповой код значности и наперед заданным d, если число проверочных символов

(VI.7.18)

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

Кривые рис. VI. 1 иллюстрируют приведенные оценки [29]. Ряд других видов оценок можно найти в [42, 87, 88, 101, 131, 149, 163].