Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Atn,b'~ U U Am, b' (и, у). (6.10.16)
и = 0,1 ti= О, I
Из рассмотрения рис. 6.10.3 непосредственно проверяется, что
Ат,ь--1=Ат,ь' {0,0). (6.10.17)
Отсюда следует, что
ЦЛ.,6' l=\\Am<b’-i\\a(m, b'), (6.10.18
где а(т,Ь') равно числу комбинаций и и v, для которых Amib’(u,v) непусто. Так как |!Лт,г,'|| и \\Amib'-il являются степенью 2, то а(т,Ь') равно 1,2 или 4.
Далее заметим, что согласно рис. 6.10.5, если 5 (D) ? Ат> ь’—i (и, v), то DS (D)?Am, ь> (и, v). Поэтому, если множество Ат, ь- (и, v) не пусто для одного из значений Ь', то оно не пусто и для всех больших значений Ь'. Следовательно, a (tn, Ь') не убывает с ростом Ь'.
Согласно определению величины b (корректирующей пакеты способности кода) существует некоторый пакет длины b + 1, про-
314
стирающийся от 0-й до b-н позиций, который имеет такой же синдром, что и некоторый пакет с длиной, не превышающей 6 + 1, начинающийся, например, на позиции т'. Этот синдром принадлежит Ат' Ь+1 (1,1). Более того,
Ий+1>т'(1,1)!!=1. (6.10.19)
Доказательство этого опирается на тот факт, что большее число синдромов содержат ненулевой синдром из Ат> ь+\, (0, 0).Но такой синдром содержал бы два интервала, каждый из которых целиком состоит не менее чем из N — L — b нулей, либо сливающихся, либо нет. Если интервалы сливаются в один, то длина получающегося интервала должна быть не менее N — L, что влечет за собой требование, чтобы синдром был равен 0. Если интервалы не сливаются, то существуют два пакета, длина которых не превышает Ь, с таким синдромом, что противоречит определению Ь.
Учитывая, что эти множества являются смежными классами и используя (6.10.16) и (6.10.17), получаем
II Ап', ь+\II > 2; || Ат ь II = 1 • (6.10.20)
Наконец, отметим, что при b’ = N — L все синдромы принадлежат А пг', b' И
|| Ал' n—l|| =2л'~l. (6.10.21)
Так как величина а (т', Ь'), входящая в соотношение (6.10.18), не убывает с ростом Ь' и принимает при b + 1< b'^N — L лишь значения 2 или 4, соотношения (6.10.20) и (6.10.21) полностью определяют Ат’.ь’\ при всех промежуточных значениях величины Ь':
\\Ащ’ ь> || = I2* ~Ь; b<b'<N~L—b' (6.10.22)
11 \22b’-(N-L). N-L — b^b'<^N~L. 1
Используя равенство (6.10.17) и равенство|| Ат' ь' (0. 0)||=|1Ап' ь' (1, 1)1, получаем
|Ап', ь (1,1)|| = Р b+1<b'<N~L — b+l> (6.10.23)
" 11 (2 2b'-2~(N-L). N^L_b+l^b'^N — L.
Каждый синдром S(D) ?Аг, ь- (1. 1), для которого S0 — 1, соответствует путающему пакету длины Ь', расположенному на позициях от 0 до b' — 1. При Ь' = 6+1 единственный синдром из Ат>, ь+ i (1, 1) имеет 50 = 1, а при больших Ь' ровно половина синдромов из Атг,б'( 1,1) имеет 50 = 1. Чтобы показать это, заметим, что если S(D)^Am', ь+1 (1. 1),toS' (D)=Db'~b~l S(D) принадлежит Ат',ь'(1,1) cS0 = 0 и S"(D) = (lJrDb'-b-'1) S(D) принадлежит Ат’,ь' (1. 1) с So = l. Так как множество S(D) ? Ат>, ь- (1, 1) с 50=1 и аналогичное множество с S0 = 0 являются оба смежными классами подгруппы S(D) ? Ат', ь' (0,0) с 50 = 0, то эти множества имеют одинаковую мощность. Далее, так как существует всего 2Ь'~2 различных пакетов, занимающих позиции от 0 до Ь'¦—1, то доля путаю-
315
щих пакетов, занимающих позиции от 0 до b'— 1, ограничена снизу величинами
\Ат..ьЛ 1,1)||2-й' + 2; 6' = 6+1,
\Ат.,Ь'(+ Ь’>Ь+1.
Так как по крайней мере половина путающих пакетов декодируется неправильно, последнее соотношение в сочетании с (6.10.23) приводит к нижней границе f (b') вида (6.10.13).
Чтобы получить верхнюю границу / (Ь'), следует прежде всего оценить j) Атш Ь< (1, 1)1 при каждом значении т. Пусть Ьт при любом заданном т — наибольшее целое число, для которого ||Лт,ь || = 1. Тогда || Ат? ь +i («, v) | — 1 при некоторой ненулевой паре значений и, и. Если ||ЛОТ, ьт+\(1, 1)1= 1, то, повторяя предыдущие рассуждения, можно получить
II Лт, ь/ (1, 1) || ^ I! Лт<, ь' (1, 1)1; b+\^b'^N-L. (6.10.24)
Вместе с тем, если || Ат> ьт+\(1, 1)|| —0, то || Ат, у (1, 1)Ц = 0 при всех Ь', таких, что а(т, Ь')=- 2, и а (т, Ь')=4 для || Ат, ь' (1> 1)||>0. Следовательно,
1226' — 2 — (N — L)
или (6.10.25)
0
и поэтому (6.10.24) справедливо при всех т, I ^ т ^ N — L. .
Любой неисправимый пакет длины V, занимающий позиции от 0 до b' — 1, соответствует синдрому 5 (D) в Ат,ь' (1, 1) при некотором т, I ^m^.N — L, с S0 = 1. Поэтому общее число неисправимых пакетов длины Ь', занимающих позиции от 0 до b' — 1, ограничено сверху величиной V2 (N— 1) ЦЛт'.*'(1,1) Ц для b + 1 < Cb'^N — L — Ь+1 и величиной (N — 1) || Ат>, ь- (1,1) Ц для других значений Ь'. Учитывая (6.10.23), отсюда получаем верхнюю оценку / (&') вида (6,10.14) . |
