Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
что b^(N — L)/2, поскольку пакет B(D), образуемый с помощью
усечения g (D) до первых L(./V—L + l)/2_j членов, всегда может быть воспринят как g (D) — В (D). Также легко увидеть, что граница b^i[(N — L)/2], справедливая для циклических кодов, эквивалентна более общей границе, приведенной в теореме 6.10.1.
К сожалению, довольно мало изучена проблема нахождения при заданных N я L многочлена g (D), максимизирующего 6. Файр (1959) нашел большой класс циклических кодов со сравнительно большими значениями 6, а Элспас и Шорт (1962) опубликовали небольшую таблицу циклических кодов с оптимальными значениями 6. Казами (1963, 1964) также указал упрощенную процедуру решения данных выше уравнений и также привел таблицу укороченных циклических кодов с оптимальными значениями 6. Для любого циклического (N, L) кода укороченный циклический код с длиной блока N', N — L <С N' <;
< N образуется с помощью отбрасывания первых N — N' информационных символов циклического кода и заменой этих отброшенных символов нулями при вычислении проверочных символов.
Теперь исследуем долю исправимых пакетов ошибок, имеющих длины, большие, чем корректирующая пакеты способность.
312
Теорема 6.10.2. Пусть циклический (N, L)-код имеет корректирующую пакеты способность, равную 6. Тогда при 6 < 6' < N — L доля / (6') пакетов длины 6', неправильно декодированных оптимальным для пакетов декодером, ограничена неравенствами
[2-е<6'>; 6' = 6 + 1,
[!/2 2—е <6'); 6+l<6'<W — L; (6.10.13)
[2(N— 1)2~е 6'= &-|-1 и TV — L — 6+1 <6',
i(7V—1)2-е(&'); 6+l<6'</V — L— 6+1, (6.10.14)
где
e(b') =
6; 6+ 1 <6'<ЛГ — L — 6,
W —L—6'+1; jV —L —6 + 1<6'<jV—L.
Обсуждение. Наибольший интерес эта теорема представляет для больших 6 и (TV— L), когда величина коэффициентов в (6.10.14) не имеет большого значения.
Весьма интересно, что при 6'<
< N — L — log2TV исправляется большинство пакетов. При фиксированном значении скорости L/-N и возрастании N отношение этой оценки к верхней границе корректирующей пакеты способности стремится к 2. График функции е (6') приведен на рис. 6.10.4. Можно заметить, что при возрастании корректирующей пакеты способности 6 горизонтальный участок функции е (6') поднимается, уменьшая долю неисправимых пакетов в окрестности 6' = (N — 1)/2.
Доказательство. Назовем синдромом S (D), соответствующим шумовой последовательности z (D), многочлен
S(D) = RDN_l[z(D)h(D)], (6.10.15)
где h (D) — (DN — 1 )/g (D). Заметим, что две шумовые последовательности имеют один и тот же синдром, если их сумма является кодовым словом. Отметим также, что множество всех синдромов, соответствующих всем различным z (D), просто совпадает с множеством кодовых слов в дуальном коде, порождаемом многочленом h (D). Пакет ошибок называется путающим, если его синдром совпадает с синдромом другого пакета меньшей или равной длины. Отметим, что любой неисправимый пакет будет путающим и по крайней мере половина путающих пакетов любой длины декодируется оптимальным декодером неправильно. Наконец, доля путающих пакетов длины 6', расположенных на позициях от 0 до 6' — 1, совпадает с долей путающих пакетов длины 6', начинающихся в любой другой позиции.
При любых целых значениях т, l^.m^.N—1, и любых 6'5 0^6'^jV — L, обозначим через Ат> ъ, (и, v) (рис. 6.10.5) множество
313
Рис. 6.10.4. Показатель экспоненты доли неисправных пакетов длины V.
синдромов S (D), для которых = «, = v и
St = 0 при т — (iV — L — b') ^ i^m — 1 и L + b’ ^ t ^ N — 1. Коэффициенты здесь выбираются как вычеты по модулю N. Из рассмотрения положений интервалов нулей на рис. 6.10.5 видно, что каждый синдром в- Ат, ь' (1,1) может быть представлен как в виде 5 (D) = Вг (D) h (D), так и в виде 5 (D) = RDN_i Ют Вг (D) х X h (D)], где каждый из полиномов By{D) и В2 (D) имеет степень Ь'. Найдем сначала границу числа элементов в этих множествах синдромов, а затем укажем ее связь с числом неисправимых пакетов длины Ь'. Заметим, что Ат, ь> (0, 0) всегда содержит все нулевые синдромы и образует подгруппу множества всех синдромов относительно сложе-
с\
I
• \?
Л ^
^ ч'
Q ? ? V
хх .7. хи Ой ~ X и 00 ••• о
Рис. 6.10.5. Множество синдромов Ат,ь{и, v)\ х — произвольные двоичные символы.
ния многочленов по модулю 2. Заметим также, что при любых и, v множество Ат,Ь' (и, и) или пусто или образует смежный класс для Ат, ьг (0, 0). Так как общее число синдромов является степенью 2, то из теоремы Лагранжа (теорема'6.3.1) следует, что каждая из этих подгрупп и каждый из этих смежных классов имеют число элементов, равное степени 2. Определим множество Ат, ь’ следующим образом:
