Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Более подробное описание алгоритма состоит в следующем: при любом п параметры [C’n + 1(D), 1п + 1]-регистра определяются через параметры [Сп (D), /J-регистра и параметры априорного регистра в последовательности [Chn, lhJ, где kn < п. При любом я > 0 целое число kn определяется следующим рекуррентным соотношением:
П
dn — Sn+ ^ Cn.iSn—i
(6.7.34)
_f — i, если ln — ln—i,
\n—1, если
(6.7.35)
Многочлен Cn+i(D) и ln+l равны:
265
где dn и dhn определяются (6.7.34) или,- точнее,
dhn ^ ^hn + 2 СЬп. ‘ i.
<= 1
Алгоритм начинает работу с п = 0 при начальных условиях С0 (D) = С_ j (D) -- 1, 10 = 1-1=0, *„ = —1, d_, = 1.
Следующая ниже теорема утверждает, что Сп (D) и 1п определяют [Сп (D), /J-регистр и что этот регистр генерирует [5 (D)]"-1. В последующей теореме будет показано, что [Сп (D), /J-регистр является самым коротким регистром, генерирующим IS (?))]?-'.
Теорема 6.7.3. При любом 0:
(а) kn < п, (6.7.38)
(б) Сп,о = 1, где C„(D) = C„,0 + C„, ,D + ..., (6.7.39)
(в) степень (D)] ^ 1п, (6.7.40)
(г) [Cn(D)S(D)]rl= 0. (6.7.41)
Доказательство.
Утверждение а. Согласно начальным условиям при п = 0 имеем ?о<0. При и > 0 доказательство немедленно следует из (6.7.35) с помощью индукции по п.
Утверждение б. Согласно начальным условиям С0 0 = 1. Теперь предположим, что Сп> о = 1 при любом заданном п. Так как п — kn>0, то из (6.7.36) следует, что Сп + 1у0 = 1. Поэтому по индукции получим, что СП'0 = 1 при всех п^0.
Утверждения виг. Вновь воспользуемся индукцией по п. Согласно начальным условиям соотношения (6.7.40) и (6.7.41) выполняются при п = — 1,0. Пусть задано некоторое п; предположим, что при — I i <Z п
степень [Сг(0) 1</г, (6.7.42)
[Ci(D)S (D)];-1 =0. (6.7.43)
Доказательство будет завершено, если показать, что из этих соотношений следует справедливость (6.7.42) и (6.7.43) для i = п + 1. Рассмотрим отдельно случаи dn = 0 и йпФ0. При dn = 0 имеем Сп + г (D) = Сп (D) и 1п + 1 = 1п. Поэтому справедливость (6.7.42)
при i = п влечет за собой справедливость (6.7.42) при i = п + 1.
Аналогично из (6.7.43) для i — п следует, что
[Cn+1(D)S(D)l7n-11= 0.
Из (6.7.34) получим [C„+i (D)S (D)]n =dn~0. Поэтому [C„+1(D)x xS {D)]?n + j =0, откуда вытекает справедливость (6.7.43) для / = = п+1. Теперь предположим, что йпф0. Согласно (6.7.36) имеем: 266
степень [Cn+ ((D)Kшах {степень [Cn(D)], n—kn~f--f степень [Ckn (D)]) < max {/„, n—kn + lhn)=ln + u
где было использовано (6.7.42) при i — ti и i — kn и затем использовано (6.7.37).
Наконец, из (6.7.36) получим
[С„+, (D) S (D)]?n + l = [Сп (D) S (D)]?n+ 1 -
r=-DB-*»Cftn(D)S(D)]n .
1
dkr.
(6.7.44)
я 5п in Сп (В)
РСМОС
О 1 0 1
1 1 1 1+Л
2 1 1 1 + Л
3 0 1 1+Л
4 1 3 1+л+л3
5 1 3 1 + Л+Л1
6 О 3 1+Л+Л1
7 1 3 1+Л+Л2
& 3 1+Л+Л2
Рис. 6.7.2. Действия алгоритма в GF (2) для S(D) = l-f-D-f-?>2+?>4+?5+?>7 до
п~я
dn ^п Ik с к г, (Я) dk,
1 -1 0 1 1
0 0 0 1 1
0 О 0 1 1
1 О 0 1 1
О 3 1 1+17 1
1 3 1 1+Л 1
О 3 f 1+Л 1
О 3 1 1+Л . 4
-dnDn.
(6.7.45)
Так как /„+1>/л, то имеем
[Cn(D)S(D)\l+l
Что касается последнего выражения в (6.7.44), то нетрудно убедиться, что Dn~ п можно вынести за скобки, если уменьшить одновременно пределы на п — kn. Таким образом,
Dn~k«Ckn(D)S(D)
akn
ln+ 1
%
Dn-k"\Ckn(D)Sm п
(ln+ \ — n + kn) =~-Dn~k»dhnDk",
(6.7.46)
где для доказательства того, что ln + 1 — п + kn~^lkn^ было использовано (6.7.37). Подставляя (6.7.45) и (6.7.46) в (6.7.44), получаем I^n + i (D) S Ф)^\п + 1 = 0, что завершает доказательство.|
267
На рис. 6.7.2 представлен пример работы описанного алгоритма для простейшего случая многочленов над GF (2). На рис. 6.7.3 изображены графики зависимости 1п и п — 1п от п для этого примера.
Имеются некоторые важные моменты во взаимосвязи между 1п и п — 1п, справедливые в более общих случаях. Заметим, во-первых, что 1п не убывает с ростом п\ согласно (6.7.37) это выполняется в общем случае. Следующие три результата являются более тонкими.
Лемма 1. При любом п ^ О
K — hn>i'~h\ — 1 <i<kn, (6.7.47)
