Доказательство. Покажем, что при сделанных предположениях выражения для SI и Sgv совпадают. С одной стороны,

, ;г-1 2 я-1 п-1

Sv = ( Х AiSv-i ) = 2j AiSv-i = A£S2v-2i"-t=l / 1=1 j=l

С другой стороны,

n-l п-1 n-l

Szv = S AjiSzv-k = 2j 2j AjAiSzv-h-i-

Из симметрии последнего выражения следует, что каждое слагаемое с i Ф k входит в сумму дважды. Поскольку вычисления производятся в расширении поля GF (2), сумма этих слагаемых будет равняться нулю. Поэтому вклад в последнюю сумму дадут только диагональные члены, для которых i -= k:

S2v = AS2v-Si-

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

Таким образом, по индукции получаем, что равно нулю для четных г; поэтому можно рассматривать только нечетные итерации, формально объединяя две последовательные итерации:

Л() (х) = Л(-2) (к) - Axsc-s) (х),

(х) = б,АГЛ<-> (х) + (1 - б,)хВ<-> (X).

Используя эти формулы, можно пропустить итерации с четными номерами, и в результате декодирование двоичных кодов ускоряется. Заметим, что поскольку при доказательстве теоремы были использованы лишь соотношения сопряженности между компонентами синдрома и ничего не говорилось о двоичных конфигурациях ошибок, то описанное упрощение возможно даже для конфигураций более чем t ошибок. Поэтому те же виды проверки применяются при числе ошибок, большем t.

7.7. ДЕКОДИРОВАНИЕ

С ПОМОЩЬЮ АЛГОРИТМА ЕВКЛИДА

Декодирование с помощью алгоритма Евклида представляет собой один из способов декодирования, отличный от рассмотренных ранее. Принцип работы такого декодера несколько проще понять, однако считается, что он менее эффективен в практиче ском использовании; впрочем, справедливость такого мнения, возможно, в значительной мере зависит от конкретного применения.

в гл. 4 алгоритм Евликда был описан как рекуррентная процедура нахождения наибольшего общего делителя двух многочленов. Небольшое расширение этого алгоритма позволяет дополнительно вычислять многочлены а (х) и b (х), такие, что

НОД [s (х), t{x)] а (х) s{x) +h (х) t (х).

Для двух произвольных многочленов s (х) м t (х) повторим алгоритм Евклида в более удобной для нас матричной форме, используя для алгоритма деления запись s (х) = Is {x)/t {x)i t (х) -f г (x).

Теорема 7.7.1 (алгоритм Евклида для многочленов). Пусть заданы два многочлена s (х) и t (х), такие, что deg s (х) deg t (х

а

пусть s(0) (х) = s(x), /О) (х) = t (х), и пусть АО) {х) = Тогда решением рекуррентных уравнений

1 О О 1

Q<)(x) =

" О 1

. 1 -{X)

1 -QM(x)J

А(-) (х),

= А(+) (х)

s(x) Vt{x)\

s(+i)(x)l [0 1 ] rsH(x) Цг+Х) (x) J [ 1 -Q<> (x) J [ t(r) (X) . будет многочлен

(X) = у НОД [s (x), t (x)],

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

у НОД [S (X), t (X)] = Л(f) (X) S (X) -j- Л(«) (X) t (X),

где R таково, что f- (х) = 0.

Доказательство. Поскольку deg /(+> (х) < deg С) (х), то в конце концов <) (х) = О при некотором R, и процесс обязательно закончится. Таким образом,

s(«) (х) О

-Q> (X) J

s(x) Vt{x)\

откуда следует, что любой делитель многочленов s (х) и t (х) делит также и s<> (х). Легко проверить, что

ГО 1

1 -Q(r) (х)

И поэтому

так что многочлен s*) (х) должен делить s (х) и (х), а следовательно, и НОД [s (х), t (х)]. Отсюда получаем, что НОД [s (х), t (х)] делит s<) (х) и сам делится на s() (х); таким образом,

(х) = у НОД [six), iix)].

Далее

= А(«) (х)

six) lt{x)}

s(«) (х)

и, следовательно,

s\x) = A\f\x)s{x) + A\§ix)tix).

Это доказывает последнее утверждение теоремы. □

В теореме 7.7.1 найден смысл матричных элементов А{> ix и А[§> (х). Можно интерпретировать и два остальных элемента,) для чего нам потребуется обратить матрицу А) (х). Напомним, что

О 1

Из этого равенства видно, что определитель матрицы А) (х) равен (-l)*". Обратная матрица запишется в следующем виде:

W Л[п ix) ]-1 [- Ag) ix) --А{п ix)

[Л(1)(х) AiQix)}

1-А<гЦх) ЛИ(х)

Следствие 7.7.2. Многочлены Л<р (х) и Л> (х), полученные с помощью алгоритма Евклида, удовлетворяют равенствам

Six) = (-1)« Л<«) (X) уНОД [s(x), /(X)],

tix) = - i~l)R Л(«) (X) у НОД [S ix), t ix)].

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

six)

Л<«)(.) -Л<«)(х)1 rsW(x) -Л(«)(х) Л(«)(х)] L О

откуда и вытекает утверждение следствия. □

Опишем два совершенно различных способа использования алгоритма Евклида при декодировании; один из них будет приведен ниже, а другой - в § 9.1.

8 Р. Блейхут ,