Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
*я-*я-Л„ + 1, (6-7.48)
/„+!>/„ тогда и только тогда, когда ln < и йпФ 0. (6.7.49)
Доказательство. Сначала покажем, что из (6.7.48) следует
(6.7.49). Согласно (6.7.37) 1п+1>г
> 1п тогда и только тогда, когда одновременно выполняется dn Ф 0 и
,п—{К—кп)>1п- (6.7.50)
Согласно (6.7.48) соотношение
(6.7.50) эквивалентно ri>2ln— Рис. 6.7.3. Величины 1п и п-—1„ как — 1 или 1п^п/2, что дока-
функции п. зывает (6.7.49). Совершенно
очевидна справедливость (6.7.47) и (6.7.48) при п = 0; предположим, что они справедливы при некотором заданном п. Утверждение можно доказать по индукции, если показать справедливость этих соотношений при ti + 1.
Если ln + i = 1п, то kn + 1 = kn, и (6.7.47), и (6.7.48) выполняются
при п + 1. Если 1п + 1 ;> 1п, то из (6.7.35) следует, что kn + 1 = п я
kn+\ 1ьп+\~п (6.7.51)
Величина kn показывает, когда в последний раз до момента п произошло изменение длины регистра; поэтому = 1п при kn <С i <С п и, следовательно,
kn+i—lkn+l>i—1{, kn<i<ti. (6.7.52)
Кроме того, из (6.7.37) следует п — ln > kn — lkn; поэтому на основании (6.7.51) и (6.7.47) получим
^п4-1 — lkn-1-1^ ^ ^ (6.7.53)
что подтверждает справедливость (6.7.47) при п + 1.
Предполагая, как и ранее, что /п + 1>/п, можно, используя соотношение (6.7.50), справедливое при п, и соотношение (6.7.51), получить
kn + i-lhn + l = ln + i + l. (6.7.54)
268
Последнее доказывает справедливость (6.7.48) при п + 1, что завершает доказательство. |
Из этой леммы следует, что п — /„ как функция п имеет вид возрастающей последовательности пиков; величина kn для каждого п указывает на местонахождение предшествующего пика, который превышает любой из предыдущих пиков (мы считаем, что в точке п имеется пик, если п — 1п~^(п+ 1) — ln + i)-
Прежде чем доказывать, что описанный алгоритм при любом п приводит к самому короткому возможному регистру, необходимо привести две леммы.
Лемма 2. Предположим, что [А (D), /] и [В (D), 1} — это два регистра, удовлетворяющие соотношениям
[A (D) S (D)\1 = aDn; аф 0, (6.7.55)
[5(D)S(D)]? = 0; (6.7.56)
тогда при некотором /, 0^/^/, существует [F (D), I—/]-регистр,
удовлетворяющий соотношению
[F{D)S{D)\ntZir fDn~L, f фО. (6.7.57)
Доказательство. Имеем
{[A (D) — В (D)) S (?>)} 1 = aD\ (6.7.58)
Пусть / — минимальное целое число, для которого А]ФВ] и пусть у = Aj — Bj. Пусть F (D) определяется соотношением
A (D) — В (D) = yD'F (D). (6.7.59)
Тогда Г0=1и
степень F (D) <
< min [степень A (D), степень В (D)]—j ^ / — /. Поэтому [F (D), I — /] является регистром. Подставляя (6.7.59) в (6.7.58) и замечая, что D> можно вынести за скобки, если одновременно уменьшить пределы на /, получим
7 [F(D)S (D)]n-j = a D»~/.
Поскольку aly Ф 0, это завершает доказательство. |
Л е м м а 3. Предположим, что при заданных S (D) и п, [Сг (D), / г 1-регистр является самым коротким регистром, генерирующим [5 (D)]‘0_I при всех г<л. Тогда не существует такого [А (D), /,41-регистра, для которого при некотором па< п одновременно выполняются соотношения
ПА (6.7.60)
и
[A{D)S {D)]ntAA=aDnA-, афЪ, (6.7.61)
269
Доказательство. Покажем, что предположение о несправедливости леммы приводит к противоречию. Пусть [А (D), 1а]—самый короткий регистр, для которого при па < п выполняются (6.7.60) и (6.7.61).
Случай а. Допустим, что nA>nk. Известно, что /,• = /„ при tik<_i<_n и потому \Cn{D), 1„] является самым коротким регистром, генерирующим [S(Z))]o_1 при nk<i<n. При i = nA отсюда следует, что /л<;/л. Поэтому, поскольку Па<Сп, то для [Cn(D), /л]-реги-стра выполняется равенство
[Cn(D)S(D)]n[AA=0. (6.7.62)
Согласно предыдущей лемме из (6.7.61) и (6.7.62) следует существование [F (D), 1а — /1-регистра, для которого при некотором j > 0 выполняется равенство
[F(?>)S(D)]^i; = fDnA ; /^=0.
Этот регистр короче, чем [А (D), /^-регистр и удовлетворяет (6.7.60) и (6.7.61). Это противоречит сделанному предположению.
Случай б. Допустим, что nA^nk. По предложению, fC^D), Z j -
регистр является кратчайшим регистром, генерирующим [S (D)]nQA и поэтому 1п ^1А- Следовательно, в силу (6.7.47),
