Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
*> Обычно такие выражения не называют многочленами, но здесь это удобно.
260
Soo(D) — S0 -f- Sx D -f- S2 D2 -j- ..., (6.7.18)
где Sj при всех i ^ 0 задается соотношением
Si= f VjUrj+i- i> 0. (6.7.19)
j'=i
Напомним, что при 0 i ^ d — 2 можно вычислять S, непосредственно по у; при i > d — 2 величина St неизвестна, но по крайней мере определена для заданной шумовой последовательности z. Можно переписать (D) в виде
с» е
Soo (D) = 2 2 VjUrj + l Di =
i — 0 / = 1 e оо e
= 2 ^ ^ 2 u‘> D‘ ” 2 vt u‘ гзтттп • <6'7'201
/—I < = 0 j= 1 ^
где через 1/(1 — UjD) обозначен многочлен бесконечной степени 1 + UjD + U2jD2 + .... Теперь введем многочлен cr (D) = а0 + c^Z) + + ... + с1 eDe следующим образом:
o(D)= П (1-UjD). (6.7.21)
/= 1
Вычисляя произведение правых частей (6.7.20) и (6.7.21), получаем*)
o(D)S„(D)= 2 ^?// П (1 -UlD)~A(D). (6.7.22)
/=i /=1
i^i
Чтобы интерпретировать это равенство, полезно ввести некоторые дополнительные обозначения. Для произвольного многочлена В (D) (конечного или бесконечного) пусть [В (D)]j определяется соотношением
[B(D)]{= \SiBlDl’ !>t’ (6-7-23)
[О, j < i.
Если / превышает степень В (D), равную L, условимся полагать
BL + l = BL + 2 = ... = Bj = 0. Обозначим далее S (D) = S0 + + SXD + ... + Sd_2Dd-2.
*> Читатель, не привыкший к таким формальным преобразованиям, может непосредственно убедиться, что
[ П (1 — U+ UjD + U*D* + ...] = П (1 - UiD), l=l l^j и равенство выполняется для всех степеней D.
261
В введенных выше обозначениях
S(D)^[Sx(D)]d~2. (6.7.24)
Так как члены в Sx (D), степень которых больше d — 2, влияют лишь на те члены многочлена Sx (D)a (D), степень которых больше чем d—2, то из (6.7.22) получим
[a(D)S(D)]d0~2-.[A (6.7.25)
Наконец, заметим, что согласно равенству (6.7.22), определяющему A (D), степень А (D) не может превышать е—1. Поэтому скобки вокруг А (D) в (6.7.25) могут быть опущены и, более того,
[a (D) S (D)]d~2 = 0. (6.7.26)
Из соотношения (6.7.26) следует, что коэффициент при D1 в произведении о (D)S (D) равен 0 для е / ^d — 2. При более подробной
записи (6.7.26) эквивалентно следующей системе равенств:
<y0Se ~j- oL Se— i -f- ...~h oe S0 = 0,
CT0 Se+ 1 4~ Se '{-¦¦¦ oe Sy =0,
: : (6.7.27)
CT0 Sd— 2 + <^i Sd—3 -f- ... -j-(Te Sd~4 — e = 0.
Равенства (6.7.27) дают систему d — 1 — e линейных уравнений, по которым декодер может найти е неизвестных оъ ..., а е [согласно (6.7.21), а0 = 1]. Если эти уравнения разрешимы, то по о (D) могут
быть найдены локаторы ошибок Uu ..., Uе, поскольку L^1, •••, Ue1
являются корнями cr (D). Теперь общая картина процедуры декодирования ясна и можно сформулировать ее для последующих ссылок в виде четырех этапов.
Этап 1. Вычислить S0, ..., Su—2 по принятой последовательности у.
Этап 2. Найти а (D) из (6.7.26) или (6.7.27).
Этап 3. Найти корни а (D) и, следовательно, локаторы ошибок.
Этап 4. Найти значения ошибок Уъ ..., Vе. Отметим, что в случае двоичных БЧХ-кодов все значения ошибок равны 1 (так как, по определению, они ненулевые) и, следовательно, этап 4 не нужен.
Теперь обсудим более подробно этап 2, а к рассмотрению реализации остальных этапов вернемся несколько позднее. Отметим, что при отыскании a (D) из (6.7.26) декодеру неизвестно число ошибок е. Следующая теорема утверждает, что o(D) может быть однозначно определен без предварительного знания е.
Теорема 6.7.2. Предположим, что произошло е sC |______(d — 1)/2__|
ошибок и что а (D) определяется равенством (6.7.21). Пусть е — минимальное целое число, для которого существует многочлен a (D) с ст0 = = 1, степень которого не превышает е и который удовлетворяет соотношению [а (D)S (D)]|~~2 = 0. Тогда е = е и а (D) = а (D).
262
Доказательство. Соотношение [ct(D) S (D)]~ 2.^--0 можно переписать в виде
Равенство (6.7.29) можно рассматривать как систему d — 1 — е линейных уравнений относительное е неизвестных V{Uj1), где
1 ^ ^ е. Так как е равно минимальному целому числу, для которого выполняется (6.7.28), и так как [ст (D)S (D)]de~2 = 0, то должно выполняться е^е. Аналогично, так как е [_ (d —1)/2 ', то справедливо неравенство е ^ d — 1 — е. Теперь рассмотрим лишь е первых уравнений в (6.7.29) при е ^ i ^ е + е — 1. Эти е уравнений с е неизвестными VjO (Uf1) являются линейно независимыми по тем же причинам, которые были указаны при установлении линейной независимости (6.7.10) в теореме 6.7.1. Поэтому единственное решение этих уравнений:
