Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Пусть заданы значения к, v и а и отображение a-символьной двоичной последовательности в символы канала; рассмотрим ансамбль кодов, в котором значения всех элементов gjt t (I) и всех элементов последовательности v являются значениями’ независимых равновероятнее двоичных символов.
292
Лемма 6.9.1. Для рассмотренного выше ансамбля кодов кодовая последовательность ... , ..., соответствующая
какой-либо данной информационной последовательности, является случайной последовательностью с символами, статистически независящими один от другого и выбираемыми с вероятностями Q (k). Более того, если две информационные последовательности и и и' совпадают в первых b ¦— 1 подблоках и отличаются в Ь-м подблоке, то соответствующие кодовые последовательности совпадают в первых b — 1 подблоках и статистически независимы во всех последующих подблоках.
Доказательство. Если задана некоторая произвольная выходная последовательность двоичного сверточного кодера s, то из независимости и равновероятности двоичных символов последовательности v вытекает, что s 0 v состоит из независимых равновероятных двоичных символов, поэтому любая кодовая последовательность состоит из независимых букв с вероятностями появления Q (k). Предположим, что и и и' совпадают в первых b — 1 подблоках и отличаются в Ь-м подблоке, и что s и s' — соответствующие им выходные последовательности двоичного сверточного кодера. Тогда s"-=s0s' является выходной последовательностью сверточного кодера при входной последовательности u" = u0u'; поскольку первые b—1 подблоков последовательности и" целиком состоят из нулей, то первые b — 1 подблоков s" — также нулевые. Пусть теперь, по крайней мере при одном значении /, например /', величина иь{‘ * = 1 и при любых п ^ b
s'U)=gi',i(n-b)®2igj,i(n-b)uH»® v v
1=Ь+1/=1
Так как gj>, ,• (п — Ь) является двоичной случайной величиной с равновероятными значениями, не зависящей от всех остальных g)t ; (/), то s„(!)—также двоичная случайная величина с равновероятными значениями. Точно так же величина s„(l) статистически не зависит от всех Sml) при т <. п и всех snU ) при Г Ф i, так как они не зависят от gi’.i (п— Ь). Поэтому все подблоки последовательности s", кроме первых b — 1, образуются независимыми и равновероятными двоичными символами. Следовательно, s0v и s'0v статистически независимы во всех подблоках, кроме первых b — 1, и поэтому х и х' статистически независимы во всех подблоках, кроме первых b — 1. |
Найдем теперь верхнюю границу W0 среднего числа F-проверок, выполняемых последовательным декодером в начальном узле и в дереве неправильных путей, исходящем из начального узла. Усреднение будет проводиться по ансамблю кодов, шумам канала и последовательностям сообщения. После этого найдем верхнюю границу для р-го момента U?g величины W0 при всех р ^ 1. Те же границы, как мы увидим, справедливы для Wn в каждом узле правильного пути.
Случайные величины W0 зависят как от цен узлов вдоль правильного пути, так и от цен узлов в неправильном поддереве, исходящем из начального узла. Число непосредственных потомков начального
293
узла, принадлежащих неправильному поддереву, равно 2я — 1 (оставшийся непосредственный потомок принадлежит правильному пути). Число узлов в данном неправильном поддереве, лежащих на глубине 2, равно 2я (2% — 1), и вообще число узлов на глубине I в данном неправильном поддереве равно 2я</ — 1) (2я — 1). Обозначим через т (I) т-й узел среди этих узлов, лежащих на глубине /, при некотором произвольном упорядочении; пусть Т'тщ является ценой этого узла. Обозначим через Г„ цену п-го узла на правильном пути и через Ттт — нижнюю грань Г„ при 0<л < оо.
Лемма 6.9.2. Узел т (I) может проверяться в г'-й раз, г ^ 1, лишь в том случае, когда Г„(о ^ Гт1-„ — 2 А + /Д.
Доказательство. Согласно пункту б) теоремы 6.9.1, при первой ^-проверке узла т (I) окончательный порог не может превысить Аналогично, окончательный порог при i-й ^-проверке узла m (/) не превышает Г'тщ — tA + А. Лемма будет доказана, если показать, что порог никогда не может быть сделан ниже чем Гтгта •— А. Согласно пункту б) теоремы 6.9.1 порог при последовательных F-npo-верках в начальном узле уменьшается от 0 скачками, равными Д. Согласно пункту в) теоремы в любом другом узле порог не может быть сделан ниже финального порога при последней F-проверке в начальном узле. Следовательно, впервые порог принимает значение, равное Тт{п или меньше, при F-проверке в начальном узле и этот порог больше чем Vmin — А. Так как траектория правильного пути проходит всюду не ниже этого порога, то начальный узел в дальнейшем никогда не будет проверен вновь и порог никогда не будет сделан ниже Гт;п — Д. I
Определим теперь двоичную случайную величину w [т (/), i] с помощью соотношения
= 6СЛИ Гот{/) >Tmin~2A + iA, (6.9.11) (О в противном случае.
Так как i-й раз F-проверка в т (/)-м узле может быть выполнена только в том случае, если w [т (I), i] = 1, то легко видеть, что число .F-проверок в т (/)-м узле ограничено сверху суммой
