Детальное доказательство методом последовательного применения алгоритма деления приводится в разд. 2.1.

Покажем, что если а (х) ж М {х) имеют общий делитель d (ж), то деление на а {х) по модулю М {х) не всегда возможно.

Действительно, если а {х) = г (х) d (х) и М {х) = s (ж) d (х), то а (х) s{x) = г (х) М (ж) S О mod М (х). Если бы всегда было выполнимо деление на а (х), то мы пришли бы к неправильному выводу, что s{x) 0 mod М {х).

Однако, если (а (х), b (х)) = 1, то, согласно алгоритму Евклида, существуют такие А (х) и В (х), что

а (х) А{х) + Ь (х) В {х) = 1,

так что а (х) А (х) = i mod b (х).

Очевидно, что деление на а (х) эквивалентно умножению на А (х).

Если, в частности, М (х) является неприводимым многочленом, т. е. не имеет делителей, отличных от скаляров и скалярных кратных самого себя, то для каждого а (х) ф О возможно деление на а (х) mod М (х). Как будет показано в разд. 2.1, многочлены с коэффициентами из поля однозначно разлагаются в произведение неприводимых многочленов, подобно однозначному разложению чисел в произведение простых сомножителей.

Покажем теперь, что двоичный многочлен

М{х) = х + х + i

неприводим. Ясно, что х не является его делителем. Проверим, будет ли делителем х i:

+ x + i

х + х*

х* + х + х

х + х

х + х х + х

Так как остаток равен 1, то не будет. Исчерпав все линейные делители, проверим квадратные. Ясно, что х не подходит, так же кякя х + х{х + 1)х и + 1 = ж + 2а; -Ы = (а; -f l) Остается проверить еще один делитель:

х +x + i a:-f а: + 1

х + х + х х+х

х*л-а + х х + х + х""

Следовательно, возможные делители М (х) должны иметь степень 3. Но все произведения таких делителей имеют степень 6. Значит, многочлен М (х) неприводим.

Таким образом, многочлены можно складывать, умножать и делить (не на нуль) по модулю + + 1. Интерпретируя все двоичные 5-мерные векторы как классы вычетов по модулю М (х), мы получаем значительно более удобный аппарат для выбора функции /, определяющей вторую пятерку строк искомой проверочной матрицы, задающей код с исправлением двойных ошибок с блоковой длиной 31 и скоростью 21/31.

Предположим, что и Ра - номера искаженных символов. Используя двоичную запись чисел и можно представить эти номера в виде классов вычетов по модулю М {х), т. е. установить соответствие р, р(*) (х), где р(*) (х) - двоичные многочлены степени < 5.

Первые пять проверочных уравнений определяют р + Ра! второе множество проверочных уравнений должно определить / (р) + / (Рг)-Декодер должен определить р и Рг по заданным

Р1 + Р2 = 1 / (Pl> + / (Р2) = и.

Рассмотрим теперь несколько возможных выборов функции /. Простейшей возможностью является умножение на константу:

/ (Р) = а Р {х) mod М {х).

Ясно, что эта идея себя не оправдывает, так как в этом случае ?2 = <1> и, следовательно, два уравнения зависимы. Вторые пять проверок (определяющих 2) не дают декодеру ничего нового.

Ничего не дает также функция / (Р) = р -- а при любом а. В этом случае 2 =

Испытаем теперь степенные функции. Сначала положим

/ (Р) = Р.

Двумя уравнениями для декодера при этом являются

Pi + Р2 = 1, Pi + PI = 2-

Читателю, не знакомому с полями характеристики 2 (которые мы изучаем в гл. 4), эти уравнения могут,показаться независимыми. Но это не так, ибо

й = (Pi + Р2) = Р? + 2Р,Р2 + Р1 = Р? + PI = 2.

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

Не отчаиваясь, попробуем, однако,

/ (Р) = Р-Уравнения для декодера имеют вид

р1 + Рг =

Р? + PI =

откуда

?2 = PHP-=(Pl + P2)(Pl-PlP2 + P) =

так что при 1 О

= Ci(P!+PlP2 + PD = = Sl(PlP2-).

Pl+p2=Sl.

£2

PiP2 = +f

Значит, Pi и Рг удовлетворяют уравнению

Ра1+Р)-йн-

или, иначе.

P+iP+(e+--)-o.

(1.45) 1+,р-1+(+)р-.=.0.

Таким образом, если произошли точно две ошибки, то их локаторы удовлетворяют этому уравнению. Так как в поле двоичных многочленов по модулю М [х) данное уравнение имеет точно два корня, то декодер всегда сможет найти два нужных локатора.

Если произошла только одна ошибка, то

Следовательно, в этом случае единственная ошибка удовлетворяет уравнению

Р + 1 = О или 1 + Cip-i = 0. Наконец, декодер всегда декодирует, если ошибок не произошло, так как в этом случае

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

обратными. Это так называемый многочлен локаторов ошибок, который обозначается через а (z) и определяется равенством

(1.46)

a(z)= П (1-Pz).

Р-локаторы ошибок

Удобно также использовать символ 5 для обозначения сумм А-х степеней локаторов ошибок. В рассматриваемом примере

1 = SP = -З = SP = 2-

Выражения для многочлена локаторов ошибок в этих обозначениях принимают вид:

1, если ошибок не произошло; при этом Si = Sz = 0. I l + iz, если произошла одна ошибка;

(1.47) a(z)={ при этом О, 3 = 5?.

l-]-iSiZ+ сли произошли две ошибки;

при этом 1:0, 8зф81.

Так как эти случаи отличаются друг от друга равенствами = О пли = SI, то ясно, что при не более чем двух ошибках декодер может определить номера ошибок. Если же искажаются три или более символов, то произойдет ошибка декодирования или отказ от декодирования. В гл. 16 на этом принципе будет построен алгоритм декодирования 16.481.

Таким образом, функция f {х) - я? подходит для построения нижних пяти строк проверочной матрицы SS двоичного кода с блоковой длиной 31 и 10 проверочными символами, исправляюп],его все двойные ошибки. Первые пять проверок задают сумму номеров ошибок; вторые пять проверок задают сумму кубов номеров ошибок. Процедура декодирования состоит из трех основных шагов: (1) производится проверка и вычисляются и S; (2) находится многочлен локаторов ошибок а (z); (3) вычисляются взаимные величины для корней о (z) и изменяются символы в соответствующих позициях полученного слова.

Для первого шага процедуры декодирования требуется 10 отдельных множеств сумматоров по модулю 2. Входами каждого из них являются соответствующие подмножества из 31 полученных символов. Так как этот шаг является сравнительно простым, то мы откладываем рассмотрение нескольких известных способов вычисления проверок до разд. 5.2.

Второй шаг декодирования связан с операциями сложения, умножения, деления и возведения в квадрат в поле классов вычетов по модулю М {х). Более детальное исследование и реализация этих операций дается в гл. 2.

Третий шаг требует, чтобы декодер определил взаимные к корням алгебраического уравнения ) над полем классов вычетов по модулю двоичного многочлена М (х). Этот шаг рассматривается подробно в разд. 5.4.

Задачи

1.1. Рассмотрим три кода Хэмминга, определяемые следующими проверочными матрицами:

(a) Для каждого из трех кодов декодировать следующие два принятых слова: R = [1 1 1 О О О 0], R = [1 1 1 1 О О 0].

(b) Показать, что две из трех выписанных выше матриц задают одинаковые

коды. „

Указание. Показать, что строки любой из этих матриц являются линейными комбинациями строк другой.

1.2. Сколько слов содержат коды, определяемые каждой из следующих проверочных матриц?

ГО 1 О 1 О 1 О 1 О 1-1 1 0 0 1 1 0 0 1 1 1010001000 О О 11 1 О 1 1 1 0. ГО О О 1 1 О 1 1 О 1 1 0 1 1 0 0 0 0 II. 0 110 110 0 0

00001101 1.

1.3. Для кода, задаваемого проверочной матрицей II задачи 1.2, найти лидеры смежных классов, содержащих следующее слова:

(a) R = [1 1 1 1 О 1 О О 0],

(b) R = [1 1 О 1 О 1 О 1 1],

(c) R = [1 О О О 1 О О О 1],

(d) R = [О 1 О О 1 О О 1 0].

1.4. Заполнить последние пять строк в матрице (1.41).

1.5. Используя код предыдущей задачи, определить Si и s3 для следующего принятого слова:

[0 1101011101101011100010110111 И].

Какой вид имеет многочлен локаторов ошибок, если произошло не более двух ошибок?

1.6. (а) Проверить неприводимость многочлена х* -\- -\- + х + i по модулю 2.

(Ь) Используя этот многочлен, построить проверочную матрицу БЧХ-кода с блоковой длиной и = 15, г = 8 проверочными символами и А = 7 информационными символами, исправляющего две ошибки.

1) Иногда мы будем их называть взаимными корнями уравнения. - Прим. перев.