Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(б) Поскольку рассматриваемый код циклический, любое устройство, исправляющее гЛГ_1, может быть использовано после циклического сдвига приня-
Поинять/е
Символы
порог
I
Выход равен U если, и или $олее входных символов равны f
654
Той последовательности для Исправления zN_2 и т. д., вплоть до z0. Так как (N — 1)/2 нечетно, то при любой конфигурации не более чем (N — 3)/4 ошибок более половины указанных выше проверочных уравнений будет выполняться
если 2уу_[ = 0 и более половины из них будет нарушено, если
-N— 1
= 1. Поэто-
му zN_j исправляется и, следовательно, после циклического сдвига принятой последовательности можно исправить остальные символы.
(в) Пусть J + D + D4 — порождающий многочлен дуального кода. Кодовое слово веса 3 с единицами на 14-й и 13-й позициях может быть найдено по рис. 6.6.3; заметим, что а14 + а13 = а2. Это вытекает из того, что а является корнем многочлена Du + D1^ + D2, поэтому Du + D13 + D2 имеет делителем 1 + D + D4 и, таким образом, является кодовым словом дуального кода. Аналогично, многочлены Du + D12 + D5, ?>14 + D11 + D10, Du + Ds + -f D4, Du + Da + D6, Du + D7- -\- D и Du + D3 + 1 являются кодовыми словами дуального кода. В регистр сдвига изображенного выше декодера вначале подается полное принятое слово; затем пороговое устройство производит исправление; после этого регистр сдвигается на одну позицию вправо, причем исправленный символ поступает слева. После 14 последовательных исправлений и сдвигов в регистре будет находиться исправленное кодовое слово.
6.40. При данном дереве принятых цен декодер проверит следующую последовательность узлов: а, 0, 00, 01, 0, 1, 10, 11, 1, 10, 100. Заметим, что последний узел имеет меньшую цену в дереве принятых цен, чем узел 010, однако узел 010 никогда не будет просмотрен, хотя все потомки узла 100 в конце концов располагаются ниже нулевого порога.
6.41. (а) В соответствии с соотношением (6.9.2) имеем
l v
=Е I
/=1/=1
1л
р{у\п№п)
со (у\‘})
-В
Это выражение является суммой lv независимых, одинаково распределенных случайных величин. Каждая пара {входная буква — выходная буква} выбирается с вероятностью Q(k) P(j\k) и поэтому согласно (5.4.16) получим
Рг [Г; < tД] < e~s,A [g (s)]/v; любое s<0, (1)
где
g(s)=1iQ(k)PU\k) ехр k, i
j^s ln
P (/1 k)
M (/)
-sB
= e“sB2 Q(k)PU\k)l+sa(!)-s-
k,j
(2)
Выбирая распределение па входе, на котором достигается пропускная способность канала, получаем
dg(s)
ds
s = О
-B + ’ZQWPU | A) ln
kti ® (1)
Поэтому при любом заданном В < С и отрицательных значениях s, достаточно близких к 0 величина g(s) < 1. Следовательно, Рг[Гг < г'Д] стремится к нулю экспоненциально с ростом I. Отметим здесь, что значение s < 0, минимизирующее правую часть (1), меняется с изменением I, но оно стремится к пределу при / -*- оо. Если использовать это предельное значение при всех /, то правая часть (1), равная e~s‘A при I = 0, будет убывать экспоненциально по /; величина e—siд больше 1 при г > 0.
(б)
I v
rf-2 2
i-1 /=1
1п
) I V.'»)
)
О)
(у\п)
655
Это выражение также является суммой lv независимых случайных величин, однако здесь в (г,/)-е слагаемое суммы входит передаваемый символ х^О и независимый от х^О символ х'^р, который проверяется. Поэтому вероятность пары
значений х'^\ i/Ф равна
,(/)
Теперь из (5.4.15) выводим, что при любом г > О
Рг [Г; > гД]
< е'
-г/Д
2 Q (к) со (/)
k,j
ехр
г In
— riL — lvrB
vrars Q(k)P(i\k)r®(i)
L k,j
Отсюда, полагая г = 1 + s и используя (2), имеем
P(i\k) со с/)
l-rl/v
-гВ
IV
Рг [г/ > /Д] < е-‘Л-
-si Д
lv
s> —1.
Можно заметить, что если не обращать внимания на область изменения s, то эта граница равна умноженной на ехр [— iA — IvB] границе вероятности Рг[Г; <
< /Д]. Кроме того, легко видеть из рассмотрения (2) (вычисляя g(s) при s = О и s = —1), что g(s) имеет минимум при s, лежащем в пределах от 0 до —1 для
О < В < С.
Наконец, число путей на глубине I, отличающихся в первом подблоке от правильного пути, меньше и Рг[Г/ > ih для любого пути на глубине /] <
< ехр [—(s + 1) /Д - /V (В — R)] g(s)lv.
При R < В и таких s, что g(s) < 1, эта граница убывает экспоненциально с ростом I. Из этого результата нетрудно сделать вывод, что среднее число вычислений для последовательного декодера при данном конкретном значении Гтгп всегда конечно, если R < В < С. Резкое возрастание среднего числа вычислений при R > ?0(1) объясняется тем фактом, что это условное среднее возрастает слишком быстро с возрастанием величины i.