7.2.5. Характеристики последовательных декодеров

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

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

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

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

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

Результаты моделирования для некоторых значений отношения метрик при декодировании кода с и с жестким решением на выходе демодулятора показаны на рис. 7.18. Оптимальной метрикой для минимизации является метрика Хемминга (которая почти точно соответствует Заметим, что отношения метрик, получаемые при (они лежат между приводят к существенному увеличению

Рис. 7.18. Характеристики кода с при жестком решении

Рис. 7.19. Характеристики для систематических кодов с при жестком решении и отношении метрик

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

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

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

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

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

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

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

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

где показатель Парето определяется по (7.57). Моделирование показывает, что эта формула дает достаточно точную оценку вероятности переполнения буфера в случае, когда несколько больше среднего числа операций, приходящихся на одно ребро (что позволяет буферу большую часть времени оставаться пустым). Константа А в (7.66) зависит от реализации декодера и обычно лежит между 1 и 2. При реализации высокоскоростных последовательных декодеров было замечено, что оценка (7.66) не столь точна, если близко к С. В этом случае для надежной оценки следует использовать моделирование.

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

Использование формул (7.66) и (7.67) для оценки характеристики системы зависит от того, применяется ли в системе при возникновении переполнения стирание блока или дополнительное декодирование.

В системах с автоматическим запросом повторения наиболее разумный путь состоит в объявлении блока стертым. Вероятность

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

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

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

где для систематических кодов; для кодов с быстрым просмотром; определяется по (7.67). Хотя общая вероятность ошибки символа задается формулой (7.65), для кодов с большой длиной кодового ограничения обычно вносит основной вклад в

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

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

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

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