6.4. Распределение числа вычислений: нижняя граница

Перейдем к доказательству того, что верхняя граница, даваемая теоремой 6.2.1 для сверточных кодов, является асимптотически точной по крайней мере при скоростях и что граница (6.2.3), полученная для решетчатых кодов, асимптотически точна при Доказательство основано на сравнении списка путей, обследуемых последовательным декодером, со списком путей с наибольшими значениями метрики, формируемыми фиксированным блочным декодером, и использовании нижней границы из леммы 3.8.1 для блочного декодирования списком длины

Начнем с рассмотрения последовательного декодера, которому помогает добрый «джин», наблюдающий за действиями декодера в каждом неправильном подмножестве. Если какой-либо неправильный путь из неправильного подмножества оказывается обследованным на участке из ребер символов), следующих за узлом то «джин» останавливает декодер и сообщает ему о необходимости прекратить обследование этого пути. При условии, что в узле ошибки декодирования не происходит, распределение вычислений в неправильном подмножестве ограничено снизу вероятностью того, что «джин» остановит декодер раз. Отметим, что вычисление было определено ранее как вычисление ребра и что число вычислений, приходящихся на последние ребра всех неправильных путей, обследование которых было прекращено «джином». Следовательно, при выводе нижней границы не учитываем вычислений всех ребер пути, за исключением последних. Более того, декодер может обследовать много других путей, но не до глубины I ребер. Наконец, если «джин» отсутствует, то на неправильных путях может выполняться еще

больше вычислений; однако если в подмножестве ошибки не совершаются, то возвращаемся к ситуации, когда «джин» как бы присутствует. Таким образом, при отсутствии ошибок

Естественно, что если правильный путь достигнет глубины за узлом то декодер может проследовать по нему. Предположим, что построен список первых путей (неправильных или правильных), исходящих из узла правильного пути и обследуемых «джином» в узле Обозначим через дополнительное множество из путей, не вошедших в этот список. Вероятность того, что «джин» остановит декодер более чем раз, для заданного принятого вектора у определяется выражением

где правильный путь на заданном сегменте длины символов. Так как все путей этой длины, исходящие из общего узла априори равновероятны, то

Эта процедура напоминает декодирование списком длины описанное в § 3.8 и задаче 3.16. При декодировании по максимуму правдоподобия кода из кодовых векторов списком размера формируется список, состоящий из кодовых векторов, имеющих наибольшие значения функции правдоподобия (метрики). Предположим, что число кодовых векторов Список наиболее правдоподобных кодовых векторов обозначим через а его дополнение, состоящее из кодовых векторов, не вошедших в этот список, обозначим через Для любого блочного кода, состоящего из априори равновероятных кодовых векторов длины N символов, вероятность ошибки на блок при использовании такого декодера

Основанное на помощи «джина» последовательное декодирование всех путей длины N символов, начинающихся в узле, можно также рассматривать как операцию декодирования некоторого специального (усеченного сверточного) блочного кода из

векторов. Хотя такой декодер и порождает список размера этот список не соответствует декодированию по максимуму правдоподобия. Следовательно, для каждого найдется некоторый вектор такой, что

Так как то, проведя суммирование для заданного у по элементам множеств дополнений, получим

Здесь мы воспользовались тем, что состоит из векторов с минимальными значениями отношения правдоподобия, а может содержать элементы, входящие в

Наконец, объединяя (6.4.1) с (6.4.4) и используя (6.4.6) в сочетании с (6.4.5), имеем

Воспользуемся леммой 3.8.1, которая задает границу снизу вероятности ошибки при декодировании списком результате получим

где

Для того чтобы применить эту границу, необходимо выбрать параметр наиболее удобную для "джина" точку наблюдения. Предположим, что выбрано

Тогда из (3.8.2), (3.8.3), (3.6.46) и (6.4.8) получим

Для определения взаимосвязи между скоростью передачи и параметром уожно воспользоваться следующим получающимся из (3.6.46), (3.8.3) и (6.4.8) равенством:

Следовательно,

Таким образом, доказана следующая теорема.

Теорема 6.4.1. Нижняя граница распределения вычислений (Джекобе Берлекэмп [1967]). Распределение вычислений, выполняемых в произвольном неправильном подмножестве любого сверточного (или решетчатого) кода, при отсутствии ошибок декодирования ограничено снизу неравенством

где

Сравнивая теоремы 6.2.1 и 6.4.1, видим, что обе границы, задаваемые этими теоремами, асимптотически совпадают при При малых скоростях 0 нижняя граница (6.4.11), как уже указывалось выше, асимптотически точна только для меняющихся во времени решетчатых (нелинейных сверточных) кодов. Для линейных сверточных кодов показатель экспоненты нижней границы (6.4.11) при малых скоростях не совпадает с показателем экспоненты верхней границы (6.2.22). Какой из этих показателей экспонент является точным, в настоящее время неизвестно.

Учитывая важность распределения Парето для функционирования последовательного декодера, интересно исследовать, каким: образом параметр называемый показателем Парето, зависит от распределения переходных вероятностей конкретных наиболее широко используемых каналов. Для ДСК, получающегося и» АБГШ канала с двоичным входом при жестком квантовании выхода канала функция полученная впервые в § зависит только от отношения энергии, приходящейся на символ, плотности шума [см (3.4.1), где определяется В результате решения относительно параметрического уравнения (6.4.12) для различных значений скорости кода

получаются кривые, показанные на рис. 6.4 (параметр представлен в виде функции отношения измеряемого в децибелах).

Значительный интерес представляет изучение поведения декодера при мягком (многоуровневом) квантовании выхода АБГШ канала.

Рис. 6.4. Показатель экспоненты Парето как функция для АБГШ канала с жестким квантованием

Рис. 6.5. Показатель экспоненты Парето как функция для АБГШ канала с квантованием на восемь уровней

На рис. 6.5 приведены соответствующие результаты для квантователя на восемь уровней (3 бит), показанного на рис. 2.15 и представленного на рис. 2.16, с шагом квантования В этом случае получается подстановкой в общее выражение (3.1.18) переходных вероятностей, задаваемых соотношением (2.8.1). Заметим, что при этом улучшение по сравнению со случаем жесткого квантования очень близко к то же значение улучшения было получено для малых отношений в § 3.4 (см. рис. 3.8).

Заметим также, что равенство соответствует скорости следовательно, пересечения линии с кривыми, приведенными на рис. 6.4 и 6.5, могут быть найдены по кривым с приведенным на рис. 3.86, путем определения точек, в которых