6.4. Распределение числа операций и вероятность переполнения буфера

Как будет показано ниже, при последовательном декодировании в некоторой области скоростей передачи вероятность ошибки стремится экспоненциально к нулю с ростом длины кодового ограничения. Однако вероятность ошибки при декодировании не является тем параметром, который определяет поведение алгоритмов последовательного декодирования. Чтобы найти правильный путь при наличии сильных шумов, приемник должен обследовать большое число ребер, а для этого он должен хранить в памяти достаточно большое число принятых символов. Емкость памяти декодера в реальных системах ограничена, и поэтому при возникновении пачки шумов все элементы памяти могут оказываться занятыми, т. е. возникает так называемое переполнение буфера. Вероятность переполнения буфера является обычно тем параметром, который определяет поведение алгоритмов последовательного декодирования.

В предыдущем разделе было найдено среднее число операций, необходимых для декодирования одного ребра, однако величиной, определяющей переполнение буфера, является не среднее число операций, а распределение числа операций, а именно вероятность того, что число операций при декодировании с превысит значение Как уже было показано выше, случайная величина с, определяющая число операций, выполняемых декодером в неправильных подмножествах кодового дерева, связана с ценами путей всех возможных длин; поскольку эти пути являются зависимыми, то нахождение точных значений вероятности является трудной задачей. Поэтому очень важно попытаться обойти статистическую зависимость неправильных путей кодового дерева и получить верхнюю и нижнюю границы для вероятности которые бы достаточно точно описывали ее поведение. Ниже такие границы будут получены, и из этих границ будет следовать, что распределение числа

операций при декодировании является распределением Парето, а именно

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

6.4.1. Структура и функционирование буфера

Структура буфера показана на фиг. 6.12.

Фиг. 6.12. Стандартная структура буфера.

Как видно из этой фигуры, часть емкости буфера используется для хранения символов принимаемых последовательностей, которые вводятся в буфер слева блоками в порядке поступления последних (каждый блок соответствует определенному ребру кодового дерева), а другая часть емкости буфера используется для хранения результатов предварительного декодирования принятых блоков.

Буфер содержит два указателя Один из них, так называемый указатель предела, указывает первое слева ребро, обследованное декодером. Другой указатель, так называемый указатель поиска, указывает положение, в котором в данный момент времени декодер осуществляет поиск. Согласно фиг. 6.12, декодер может хранить В ребер. Защитная память, показанная на фиг. 6.12 справа, устанавливается для того, чтобы при переполнении буфера можно было выделить ненадежно декодированные данные.

При слабых шумах оба указателя находятся, как правило, вблизи левого конца буфера, а также близко друг к другу. По мере возрастания уровня шумов, действующих в канале, оба указателя обычно смещаются вправо. При этом указатель

поиска всегда располагается справа от указателя предела и расстояние между этими указателями возрастает медленнее, чем расстояние между указателем предела и левым концом буфера. Так как при малом уровне шумов цены правильного и неправильного путей сильно различаются, то в результате проводимого поиска сразу удается разделить правильный и неправильный пути. При пачке шумов цены правильного пути начинают падать и декодер, исследуя как падающий участок правильного пути, так и неправильные пути, цены которых лежат выше минимальной цены правильного пути, постепенно понижает порог. С уменьшением уровня шумов цены правильного пути начинают возрастать и декодер движется вперед, вновь повышая значения порога. Однако, возвращаясь к фиг. 6.7, заметим, что до этого декодер должен обследовать неправильные пути между узлами (7) и (9). Так как число ребер неправильных путей, лежащих в этой области, растет экспоненциально с ростом длины этого участка, то резко возрастает и объем проводимых вычислений. В результате указатель предела перемещается вправо на значительное расстояние от левого конца буфера, однако при этом расстояние между указателями предела и поиска оказывается несколько меньшим.

6.4.2. Нижняя граница для ...

Распределение числа операций при декодировании двоичных информационных символов было найдено Джекобсом и Берлекэмпом [12]:

Точнее, ими была получена нижняя граница для распределения числа операций с, необходимых декодеру для декодирования первых информационных символов, из которой следовало приведенное выше приближенное равенство. Эта нижняя граница была получена методом, в основных чертах совпадающим с методом получения нижней границы для вероятности ошибки при декодировании списком, использованным Шенноном, Галлагером и Берлекэмпом [5].

Пусть задан дискретный канал без памяти, и пусть

Верхнюю огибающую будем обозначать через Для большого числа реальных каналов и вместо всегда можно использовать Использование в подобных случаях позволяет упростить нижнюю границу.

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

то, согласно формулам (1.68) и (1.69),

где функции, стремящиеся к нулю с ростом Эта граница справедлива для произвольного блокового кода длины и произвольного декодера со списком объема

Прежде чем применить эту границу для нахождения распределения числа операций при декодировании, введем следующие величины:

Покажем, что вероятность можно оценить сверху функцией, которая имеет тот же вид, что и распределение Парето.

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

Далее, подставим в правую часть (6.40) вместо и выберем минимально возможное такое, что

Пусть X — некоторая постоянная и минимальное кратное X, для которого выполняется неравенство (6.41). При таком выборе наряду с (6.41) имеет место и другое неравенство:

При этом справедливы также неравенства (6.36) и (6.37). Подставляя выражение (6.39) в (6.37), получаем

Возьмем натуральный логарифм от обеих частей (6.42):

Используя эту формулу, преобразуем неравенство (6.43) к виду

Как следует из формулы (6.44), имеет порядок

Используя это соотношение, запишем формулу (6.45) в виде

Эта оценка может быть использована следующим образом.

Предположим, что в начале принятой последовательности возникла пачка ошибок длины Допустим, что длина этой пачки является целым числом, кратным некоторой постоянной X и удовлетворяющим неравенствам (6.41) и (6.42). Обозначим через совокупность передаваемых последовательностей длины выходящих из начального узла кодового дерева. Эту совокупность, содержащую последовательностей, можно рассматривать как блоковый код длины со скоростью Обозначим через первые символов принятой последовательности. Для каждой фиксированной последовательности совокупность вероятностей упорядочим в порядке их убывания. Пусть -совокупность индексов последних вероятностей из этого списка. Если принята последовательность то указывает наименее правдоподобных сообщений или, другими словами, выделяет совокупность сообщений, которые при декодировании списком по максимуму правдоподобия не включаются в список.

Условная вероятность того, что при передаче последовательности индекс 1 которой принадлежит будет принята последовательность равна

и, следовательно, при декодировании списком по максимуму правдоподобия вероятность ошибки определяется равенством

Неравенство (6.47) представляет собой нижнюю границу для этой вероятности.

Далее, предположим, что принята последовательность и рассмотрим, каким образом последовательный декодер осуществляет поиск правильного пути, выходящего из начального узла кодового дерева. Поведение любого последовательного декодера характеризуется следующими особенностями:

1) Поиск ребер осуществляется последовательно. Если в некотором узле кодового дерева декодер выберет ребро, которое раньше не обследовалось, то это решение не зависит от принятой последовательности, соответствующей ребрам, лежащим на кодовом дереве глубже.

2) Декодер выполняет по крайней мере одну операцию на каждом обследуемом пути.

В результате этого поиска передаваемые последовательности обследуются до полной длины и декодер после символа продолжает двигаться вперед; здесь мы рассмотрим лишь пути кодового дерева длины

На время допустим, что на месте символа имеется некий учитель, который указывает декодеру, выбрал ли он правильную последовательность или некоторую неправильную последовательность. Если последовательность является неправильным путем, то декодер установленным для данного алгоритма порядком возвращается назад и начинает обследование другого пути до длины Если и этот путь является неправильным, то учитель вторично указывает декодеру на ошибку. Декодер вновь возвращается назад в исходное состояние и начинает обследование третьей последовательности и т. д. Другими словами, эти действия декодера для каждой фиксированной принятой последовательности длины можно интерпретировать как один из способов упорядочения последовательностей из

Результат упорядочения зависит от принятой последовательности передаваемых последовательностей и алгоритма

последовательного декодирования. Однако результирующий порядок, согласно особенности 1, не зависит от символов передаваемой и принятой последовательностей, находящихся на расстоянии и более от начального узла кодового дерева. Пусть -множество индексов последних последовательностей из упорядоченных указанным выше образом.

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

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

Для каждой фиксированной последовательности наборы задают подмножества из кодовых слов множества Так как определяет подмножество наименее правдоподобных кодовых слов, то

и, следовательно,

Эта оценка показывает, что распределение числа операций при декодировании является распределением Парето. Заметим, что полученная оценка является оценкой снизу числа операций, выполняемых декодером в узлах кодового дерева, лежащих на глубине и менее. Так как в число этих операций входят также и операции, выполняемые декодером в подмножестве неправильных путей, то левая часть (6 51) также является оценкой снизу для распределения числа операций с, выполняемых в подмножестве неправильных путей, т. е.

Таким образом, нижняя оценка для получена.

6.4.3. Верхняя граница для ...

Для вывода верхней границы для потребуются следующие два неравенства:

1) Неравенство Чебышева.

Пусть произвольная случайная величина, ее среднее значение и дисперсия. Тогда

Справедливо также следующее неравенство:

где случайная величина, принимающая только отрицательные значения.

2) Неравенство Минковского.

Пусть неотрицательные случайные величины, принимающие с вероятностью соответственно значения а Тогда для любого

и, кроме того,

Используя эти два неравенства и верхнюю границу для числа операций при декодировании, даваемую соотношением (6.15), Сэвадж [9] получил следующую верхнюю границу для

Теорема 6.2. (Сэвадж). Существует сверточный код со скоростью передачи для которого распределение числа операций с для типичного подмножества неправильных путей в дискретном канале без памяти удовлетворяет неравенству

Доказательство. Рассматривая суммы по в (6.15), т. е. в неравенстве

как суммы по неравенства (6.56), получаем

где черта сверху означает усреднение по принимаемым последовательностям и ансамблю кодов. Здесь воспользуемся ансамблем кодов, в котором все символы кодовых слов являются независимыми величинами с распределением Аналогично тому, как было получено неравенство (6.33), можно показать, что

где

При величина и, следовательно, сходятся. Это означает, что существует код, для которого момент порядка величины с не превышает некоторую константу Из неравенств получаем, что Согласно неравенству Чебышева, типичное для ансамбля кодов распределение величины с должно удовлетворять неравенству

Это доказывает существование по крайней мере одного кода, распределение величины с для которого удовлетворяет (6.57).

Таким образом, мы получили верхнюю и нижнюю границы распределения числа операций при декодировании с. Эти границы показывают, что рассматриваемое распределение является распределением Парето.

6.4.4. Связь с вероятностью переполнения буфера

Установить связь между распределением и вероятностью переполнения буфера точно очень трудно. Поэтому здесь сначала обсудим эту связь качественно, а затем покажем, как, следуя подобным качественным рассуждениям, можно получить нижнюю границу для вероятности переполнения буфера.

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

операциями, связанными с обследованием коротких путей этого неправильного подмножества. Действительно, длинные пути имеют цены, значительно отличающиеся от цен правильного пути. В силу этого вероятность того, что выполняемые декодером операции связаны с обследованием длинного пути, является очень малой. Это позволяет предположить, что операции, выполняемые декодером в неправильных подмножествах кодового дерева, являются операциями, которые, как правило, декодер выполняет в небольших локальных «впадинах», образующихся на траектории правильного пути. Поэтому, если некоторая впадина правильного пути содержит неправильных подмножеств, то суммарное число операций, выполняемых декодером при обследовании этой впадины, является суммой чисел операций, выполняемых декодером в каждом из неправильных подмножеств, а поэтому естественно предположить, что эта сумма имеет то же распределение, что и число операций, выполняемых декодером в каждом из упомянутых выше неправильных подмножеств. Обозначим через суммарное число операций, необходимых для обследования каждой впадины, и пусть с — число операций, выполняемых декодером в одном неправильном подмножестве кодового дерева. Тогда в силу вышеизложенного при больших значениях с и имеем

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

Обозначим через а число операций, выполняемых декодером за время получения одного ребра, и через В — объем регистра в ребрах. Тогда

и, следовательно,

Приведенные выше качественные рассуждения подтверждаются результатами моделирования. Кроме того, теоретическим подтверждением правильности этих качественных рассуждений является нижняя граница для полученная с их помощью Джекобсом и Берлекэмпом [12] на основании оценки

(6.50). В оставшейся части этого раздела остановимся на этой нижней границе.

Предположим, что емкость памяти декодера такова, что в ней могут храниться все данные, необходимые для декодирования 0 двоичных информационных символов. Тогда, если за время поступления и двоичных информационных символов по крайней мере и символов оказались не декодированными, то возникает переполнение буфера. За время поступления и двоичных информационных символов декодер может выполнить не более чем операций. Следовательно, всегда, когда для декодирования и двоичных информационных символов необходимо выполнить более чем операций, возникает переполнение буфера. Пусть

и — число двоичных информационных символов, соответствующих символам канала. Тогда при любой скорости передачи имеет место следующее равенство:

где целое число, удовлетворяющее соотношениям (6.41) и (6.42) (через здесь и ниже обозначается минимальное (максимальное) целое число, большее (меньшее) или равное

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

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

то, используя разложение бинома, для вероятности переполнения буфера для одного подблока получаем следующую оценку:

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

Следующее неравенство следует непосредственно из (6.42):

Из формул (6.65) и (6.66) для получаем следующую оценку:

(Здесь мы воспользовались также тем, что Разлагая второе слагаемое в правой части последнего неравенства, получаем

Из формул (6.69) и (6.71) непосредственно следует, что

Объединяя слагаемые, содержащие имеем

Отсюда следует, что если

то

Заметим, что условие (6.73) в большинстве практически интересных случаев выполняется.

Согласно формулам (6.66) и (6.73),

Отсюда, а также из формул (6.52), (6.65), неравенства со и формулы (6.75) получаем

Предположим, что (о и таковы, что При этих предположениях из формул (6.68) и (6.69) получаем

Таким образом, сравнительно просто была получена нижняя граница для вероятности ошибки или переполнения буфера. Этот результат не является столь же сильным, как верхняя граница. Нижняя граница и верхняя граница, полученная с помощью качественных рассуждений, похожи друг на друга. Из формул (6.64) и (6.57) следует, что

Полагая в нижней границе получаем

Таким образом, вероятность переполнения буфера линейно возрастает с и убывает с ростом