8.5. Обнаружение и исправление независимых ошибок веса 1

Как следует из теоремы 8.1, код с минимальным расстоянием является кодом, обнаруживающим независимые ошибки веса 1. Следующая теорема дает простой способ построения таких кодов.

Теорема 8.3. Если нечетное число, то

Доказательство. Если допустить существование конечного целого положительного числа такого, что то при некотором целом положительном будет иметь место равенство Следовательно, делится на 2, но этого не может быть, поскольку по условию теоремы нечетное число. Это доказывает (8.58).

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

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

В разд. 8.1.7 было дано определение показателя целого числа а по модулю Для взаимно простых введем величину следующим образом. По определению минимальное целое положительное число такое, что

Если существует, то

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

Теорема 8.4. Если нечетное число, то

Доказательство. Сначала предположим, что не существует. По определению

или, что то же самое, Следовательно, существует целое положительное число такое, что Отсюда и из определения имеем

Покажем, далее, что целые положительные числа такие, что удовлетворяют неравенству Во-первых, очевидно, что Далее, поскольку — нечетно, то, согласно теореме Если же то существуют такие целые числа что

Так как нечетно, то следовательно, должно делить т. е. Из определения имеем Следовательно

и, таким образом, мы показали, что

Если существует, то доказательство проводится аналогично.

Лемма -код имеет минимальное расстояние тогда и только тогда, когда

для всех таких, что

Доказательство. Так как, согласно формуле (8.63), то в число кодовых чисел рассматриваемых -кодов не входят целые числа

веса 2. Кроме того, если существует целое такое, что то . В этом случае что противоречит условиям леммы. Следовательно, в число кодовых чисел рассматриваемых -кодов не входят и числа веса 1. Кроме того, заметим, что существует только одно число веса 0, а именно Следовательно, минимальное расстояние рассматриваемых кодов не меньше 3.

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

Теорема 8.5. Пусть нечетное простое число. Тогда полная система вычетов по модулю А образует конечное поле Если 2 является примитивным элементом то

Если 2 не является примитивным элементом но — 2 является примитивным корнем то

Верно и обратное, а именно если выполняется (8.64а), то 4 — нечетное простое число и 2 — примитивный корень по модулю А. Далее, если выполняется равенство (8.646), то А — нечетное простое число, — 2 — примитивный корень, а 2 примитивным корнем не является.

Доказательство. Так как А — нечетное простое число, то согласно теореме Ферма,

В разд. 8.1.5 указывалось, что полная и приведенная системы вычетов по простому модулю являются соответственно полем и его мультипликативной группой

Если 2 является примитивным элементом то В этом случае т. е. , и так как 2 — примитивный элемент то множество чисел

будет приведенной системой вычетов по модулю

Следовательно числа при делении на имеют различные остатки. Замечая, что и полагая получаем, что для всех удовлетворяющих условию Отсюда и из леммы 8.3 следует справедливость равенства (8.64а).

Далее рассмотрим случай, когда примитивным элементом является число —2. Если четное число, то и, поскольку — простое число, то, используя формулу (8.65), вновь приходим к сравнению

Так как —2 является примитивным элементом, то числа

принадлежат различным классам вычетов. Это означает, что число 2 также является примитивным корнем и, следовательно, в этом случае применима формула (8.64а).

Если —2 является примитивным корнем, а 2 не является примитивным корнем, то, как следует из вышеизложенного, число должно быть нечетным. Кроме того, Так как то Вновь обращаясь к формуле (8.65), получаем, что а именно Отсюда следует, что приведенной системой вычетов является также множество чисел

Таким образом, числа являются попарно несравнимыми по модулю Так как то, полагая получаем, что для всех удовлетворяющих условию Отсюда из леммы 8.3 следует справедливость равенства (8.646).

Наоборот, если имеют место равенства (8.64а) или (8.646), то из леммы 8.3 следует, что для всех удовлетворяющих соответственно условию

или

и любых Эти условия выполняются только в том случае, если чисел а именно

пробегают все элементы приведенной системы вычетов по модулю Следовательно, вычеты по модулю А имеют вид ±2 и А является нечетным числом. Отсюда в свою очередь следует, что число А взаимно просто с числом 2 и, кроме того, со всеми вычетами по модулю является нечетным простым числом. Это означает, что система вычетов по модулю является конечным полем. Так как все степени числа 2, не превосходящие различны, то порядок числа 2 не меньше Кроме того, заметим, что порядок числа 2 должен делить Следовательно, порядок числа 2 равен либо либо Для числа —2 рассуждения полностью аналогичны. В любом конечном поле существует примитивный элемент Если порядки чисел —2 и 2 равны то числа вида ±2 должны быть нечетными степенями а, но этого быть не может. Следовательно, по крайней мере одно из чисел 2 или —2 имеет порядок одно из чисел 2 или —2 является примитивным корнем.

По аналогии с совершенными кодами Хэмминга, исправляющими ошибки веса 1, даваемые теоремой 8.5 -коды, исправляющие ошибки веса 1, также можно назвать совершенными в указанном ниже смысле. AN-код длины исправляющий ошибки веса 1, должен обладать способностью различать посредством вычетов по модулю каждую из возможных ошибок веса 1 и правильное кодовое число, т. е. всего различных исходов. Согласно лемме 8.3, каждому из этих исходов должен соответствовать «собственный» вычет, что возможно только в случае, если Теорема 8.5 дает необходимые и достаточные условия для того, чтобы выполнялось точное равенство. Условия теоремы таковы, что у даваемых ею кодов число вычетов по модулю равно возможным различным исходам. В этом смысле эти коды являются совершенными. Все -коды с минимальным расстоянием приведенные в табл. 8.9, являются кодами этого типа.

Чанг и Рид [12] доказали следующую теорему, из которой следует, что, за исключением кодов, указанных в теореме 8.5, других совершенных -кодов, исправляющих ошибки веса 1, не существует.

Теорема -код длины исправляющий ошибки веса 1, является совершенным тогда и только тогда, когда А — простое число, и одно из чисел 2 или —2 является примитивным корнем по модулю А.

Пример 8.7. Если то 2 является примитивным корнем Из теоремы 8.5 следует, что Следовательно, -код с имеет минимальное расстояние и может исправлять ошибки веса 1. Этот код имеет три кодовых числа которым соответствуют следующие кодовые слова: и 10110.

При этом ненулевыми вычетами по модулю являются следующие числа:

(см. скан)

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

(см. скан)

В заключение обратим внимание на аналогию -кодов и обычных циклических кодов.

Пусть многочлен степени над и пусть минимальное целое число, такое, что делит Тогда циклический код порядка, порождаемый будет представлять собой совокупность последовательностей длины таких, что многочлен

делится на Следовательно, все многочлены соответствующие кодовым словам, имеют вид

где многочлен степени или менее.

Если имеет четное число ненулевых членов, то . В действительности верно и обратное. В этом случае для всех

кодовых слов все кодовые слова имеют четный вес. Такие коды имеют минимальное расстояние Хэмминга, не меньшее 2, и, следовательно, могут обнаруживать ошибки веса 1 (в смысле расстояния Хэмминга). Многочлен порождает код этого типа, имеющий минимальную избыточность, равную 1 при любом Такие коды полностью соответствуют -кодам, описанным в теореме 8.3.

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