8.6. AN-коды, исправляющие кратные ошибки

В предыдущем разделе были описаны коды, исправляющие одиночные ошибки. Как показывают теоремы 8.4 и 8.5, такие коды могут строиться систематическим образом. Что касается -кодов, исправляющих кратные ошибки, то, за исключением специального случая описанных ниже циклических -кодов, общих методов их построения неизвестно.

В табл. 8.9 приведено несколько примеров -кодов с минимальным расстоянием и 5. Эти коды были построены с помощью утверждения 8.2.1, а именно путем последовательного вычисления весов кодовых чисел с целью нахождения минимального числа такого, что Однако объем вычислений резко возрастает с ростом

В настоящее время одним из полезных методов построения AN-кодов, исправляющих кратные ошибки, является построение по известным кодам с некоторым минимальным расстоянием кодов с тем же минимальным расстоянием имеющих большую длину. Здесь приведем следующую теорему, принадлежащую И. Л. Ерошу и С. Л. Ерошу [10].

Теорема 8.7. Если А порождает AN-код длиной с минимальным расстоянием порождает AN-код длиной с минимальным расстоянием то при выполнении любого из следующих двух условий:

число порождает AN-код длиной с минимальным расстоянием

Доказательство. Докажем теорему в предположении, что выполняется условие (8.66). При выполнении условия (8.67) доказательство проводится аналогично.

Предположим, что по крайней мере для одной совокупности чисел или имеет место сравнение

Пусть где если если Тогда формулу (8.68) можно переписать в виде

Эта система сравнений должна иметь место также по модулю и по модулю Поэтому

(Здесь мы воспользовались также условием Так как порождает -код длиной с минимальным расстоянием то последнее сравнение может иметь место только в том случае, если

Кроме того, имеется еще система сравнений по мудулю

Если в формуле для слагаемых и для слагаемых то

Если предположить здесь, что то Прибавляя к обеим частям и принимая во внимание равенство (8.71), получаем

Так как, согласно формулам (8.66), числа взаимно просты, то обе части последнего сравнения можно разделить на результате имеем

где Однако это сравнение не может выполняться, так как по условию теоремы порождает AN-код длиной с минимальным расстоянием Следовательно, не выполняется и система сравнений (8.68).

В случае если прибавляя к обеим частям число приходим к тому же выводу.

Теорема 8.8. Пусть — целые числа. Если целое число порождает AN-код длиной с минимальным расстоянием порождает AN-код длиной с минимальным расстоянием порождает AN-код длиной « с минимальным расстоянием то при выполнении любого из следующих двух условий:

и

число порождает AN-код длиной с минимальным расстоянием

Теорема 8.9. Пусть — целые числа. Если порождают AN-коды длиной с минимальным расстоянием такие, что

порождает AN-код длиной с минимальным расстоянием взаимно просто с является делителем то порождает AN-код длиной с минимальным расстоянием

Теоремы 8.8 и 8.9 могут быть доказаны точно так же, как и георема 8.7, но здесь эти доказательства опускаются). Приведем некоторые утверждения, полезные при построении кодов с помощью этих теорем.

Сначала заметим, что любое целое число вида

или

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

Далее, при любом целом положительном число

порождает -код длины с минимальным расстоянием При этом

Минимальным целым положительным числом, имеющим вес является

но для таких

В табл. 8.10 приведено несколько кодов с минимальным расстоянием 5, построенных с помощью теорем