7.2.4. Вычислительные сложности последовательного декодирования

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

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

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

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

2. Для каждой вершины каждого рассматриваемого пути декодер производит по крайней мере одно вычисление.

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

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

вычислительных операций.

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

Заметим, что допускаются лишь те значения которые делятся на и при этом удовлетворяют условию Таким образом, если первых символов оказались стертыми, то с вероятностью, не меньшей 1/2, будет проделано или более операций, откуда

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

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

Точно описать поведение числа операций при последовательном декодировании можно через функцию Галлагера задаваемую формулой (1.64), и экспоненту обсуждавшиеся в разд. 1.4. Джекобе и Берлекэмп [80] показали, что распределение числа операций при любом алгоритме последовательного декодирования в дискретном канале без памяти ограничивается снизу следующим образом:

где показатель распределения Парето для кода со скоростью в этом канале определяется как решение уравнения

В формуле (7.56) Этот результат верен для где С — пропускная способность канала. Интересно, что согласно этому результату ни для какого алгоритма

последовательного декодирования распределение числа операций не может убывать с ростом быстрее, чем функция вида Показатель в этой границе зависит только от скорости хода и от канала, и его легко вычислить с помощью (7.57). Показатель, определяемый таким образом, дает лучшую оценку, чем показатель, определенный в предыдущем примере. Экспериментальные и теоретические результаты, в особенности верхняя граница для числа операций, найденная Севиджем [81], подтверждают, что фактическое распределение является распределением Парето, и его показатель может быть рассчитан по формуле (7.57). Знание показателя распределения Парето позволяет точно оценить объем буфера, требуемого для получения данной характеристики (вероятности переполнения буфера). Таким образом, учет (7.56) и (7.57) очень важен при проектировании декодера.

Заметим, что параметр задаваемый равенством

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

7.2.4.1. Поведение системы с когерентной ФМ. Рассмотрим случай двоичных противоположных сигналов в аддитивном гауссовском канале. Пределом для применения последовательного декодера с кодом, имеющим скорость является такое значение при котором достигается значение Этот параметр был вычислен в разд. 1.4 для случая сигналов с фазовой модуляцией и когерентным обнаружением. Зависимость требуемых значений от показана на рис. 1.12. Приведены кривые, соответствующие квантованию демодулятора на и со уровней. Использование последовательного декодера при значениях меньших указанных, приведет к очень большой вычислительной нагрузке на декодер. Заметим, что для кодов с требуемое значение составляет при жестком решении и при квантовании на восемь уровней. Последнее значение существенно лучше того, которое можно достичь при декодировании коротких кодов с помощью алгоритма Витерби.

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

Показатель Парето задается как решение неявного уравнения

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

7.2.4.2. Поведение при М ортогональных сигналах и некогерентном обнаружении. Как отмечалось в гл. 6, некогерентная система с алгоритмом декодирования Витерби оказывается более эффективной при использовании ортогональных сигналов. Джордан заметил, что то же верно и для системы, в которой осуществляется последовательное декодирование [82]. Это можно показать, исследуя поведение параметра Кратко поясним сказанное.

Рис. 7.14. Зависимость показателя Парето от и от скорости кода:

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

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

Таким образом, для нахождения нужно подставить (1.10) и (1.11) в (7.61) и выполнить численное интегрирование. Это было проделано для нескольких значений и значение необходимое для достижения как функция показано на рис. 7.15. Скорость кода измеряется в битах информации на один -ичный символ.

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

Рис. 7.15. Зависимость значения необходимого для достижения при некогерентном приеме ортогональных сигналов от

ребер, исходящих из одной вершины дерева (например, R = 1 приводит к двоичному дереву, к -ичному дереву и т. д.). При таком подходе двоичное дерево оказывается оптимальным при При наиболее эффективным оказывается -ичное дерево однако использование двоичного дерева ухудшает характеристики лишь на Аналогично при наиболее эффективным оказывается -ичное дерево. Эта система была построена Джорданом [82], и ее измеренные характеристики оказались очень близкими к значениям предсказываемым согласно рис. 7.15 с учетом неидеальности фильтрации и квантования. Наконец, из рассматриваемого рисунка следует существование оптимальной скорости кодирования не только в системе с последовательным декодированием, но и в системе с декодированием Витерби. Напомним, что -ичные коды, рассмотренные в гл. 6, имели лишь скорости или Так, рассмотренный там -дуальный код был -ичным кодом с Согласно рис. 7.15 коды с примерно на менее эффективны, чем коды с Причина, по которой был выбран код с состоит в том, что длина кодового ограничения была столь малой, что требовалось дополнительное кодовое расстояние. Из рисунка следует также, что коды с почти оптимальны для -ичных сигналов. Однако для больших алфавитов или 32) пользователь может захотеть использовать коды с

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

Рассмотрим прежде всего, как влияет сопоставление метрик на среднее число операций. Вид метрики на ребрах дается формулой (7.52). В случае ДСК величина, добавляемая к метрике пути, когда принятый символ совпадает с гипотетическим символом в канале, составляет

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

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

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

Для нахождения подходящего отношения метрик для ДСК при из уравнения (1.67) определяют соответствующее значение Используя это значение и полагая в (7.62) и получаем необходимое значение отношения метрик. Полученные значения и для кодов с 2/3 и 3/4 приведены в табл. 7.3. (Заметим, что оптимальные значения метрики для кода с при равны примерно при каждом согласовании символов и —4,5 при каждом несогласовании; именно эти значения использовались в примере подразд. 7.2.1.)

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

Таблица 7.3. (см. скан) Вероятность ошибки в двоичном симметричном канале и оптимальное значение при

Рис. 7.16. Среднее число вычислительных операций для систематического кода с при жестком решении

Рис. 7.17. Распределение числа операций для систематического кода с при жестком решении

В рассматриваемой области последнее выбранное значение может оказаться более предпочтительным, поскольку уменьшает вероятность необнаружения ошибки. (Заметим, что согласно (7.62) и (7.63) значение оптимально при Результаты моделирования подтверждают это наблюдение.)

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

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

где — константа, значение которой обычно лежит между показатель Парето, задаваемый формулой (7.57). Для когерентной системы с фазовой модуляцией этот показатель можно найти непосредственно из рис. 7.14. Константа А зависит от особенностей используемого алгоритма и параметров декодера. Оптимизация правила сопоставления метрик и расстояния между порогами может уменьшить эту константу. Известно также, что неправильное сопоставление метрики или неправильная установка автоматической регулировки усиления в демодуляторе может снизить показатель Парето при декодировании с мягким решением. Результаты моделирования алгоритма Фано для декодирования кода с приведены на рис. 7.17 (снова предполагается жесткое решение). На этом рисунке показана измеренная вероятность при Показатели Парето, соответствующие этим распределениям, близки к показателям, предсказываемым формулой (7.57). Таким образом, хвост распределения может быть определен формулой (7.64) при постоянной