6.6. Вопросы сложности, переполнения буфера и устройства других систем

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

то, как это следует из (5.1.32) и (5.4.13), вероятность ошибки на бит асимптотически при больших х и скоростях

где

Как было показано в § 5.2, характеристики сверточного кода как функции сложности выглядят гораздо привлекательнее, чем характеристики блочных кодов. В данном рассмотрении -разрядного блочного кода необходимо было бы положить х равным числу вычислений метрики кодовых векторов, приходящемуся на один бит. При этом из (3.2.14) и (3.6.45) следовало бы, что для вероятности ошибки на блок для скоростей справедливо асимптотическое равенство

Так как при значительно меньше, чем то абсолютное значение показателя экспоненты из (6.6.2) значительно больше, чем соответствующая величина из (6.6.3), что

означает превосходство сверточных кодов с декодированием Витерби.

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

При этом согласно (6.2.20) и (6.4.9) вероятность того, что декодер не может выполнить декодирование в заданном узле из-за того, что для этого требуется большее число вычислений, чем это допустимо, оценивается соотношением

где

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

Сравнение (6.6.2) с (6.6.5) или (6.6.1) с (6.6.4) показывает, что Для последовательного декодирования должно выбираться следующим образом: где К аналогично используемому

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

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

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

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

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

где

Из теоремы 6.2.1 известно также, что эта граница является асимптотически точной для при условии, что первоначально буфер пуст. Более того, если расширить класс рассматриваемых кодов, включив в него произвольные меняющиеся во времени решетчатые (нелинейные сверточные) коды, то, как следует из (6.2.23) и работы Сэвиджа [1966], эта граница будем асимптотически точной во всем диапазоне скоростей. В предположении, что рассматривается этот расширенный класс кодов, вероятность переполнения буфера для узла при первоначально пустом буфере оценивается соотношением

где константа. Эксперименты (Форни и Боуэр [1971], Джилхаузен и др. [ 1971]) показывают, что имеет порядок от 1 до 10 и длительный поиск является довольно редким явлением при условии, что предположение о пустоте буфера в начале поиска выполняется достаточно точно. При достаточно малых вероятностях переполнения буфера на узел, что является условием фективной работы декодера, получаем

где параметр, связанный с параметрическим соотношением (6.6.8).

Так как явление переполнения представляет собой в некотором смысле «катастрофой», то единственным возможным условием нормальной работы последовательного декодера с конечным объемом буфера и конечной скоростью вычислений является деление данных на блоки длиной 3? ребер бит) и введение между ними

хвостов из ребер, состоящих из нулей. В этом случае если даже в некотором блоке из ребер произойдет катастрофическое переполнение буфера, то хвост позволит привести декодер в нормальное состояние и снова начать декодирование, потеряв при этом самое большее бит. Конечно, введение хвостов приводит к снижению вычислений скорости в раз и усложнению синхронизации декодера. Поэтому, чтобы ухудшение было небольшим, отношение должно выбираться достаточно малым. С другой стороны, параметр не может быть выбран чрезмерно большим, поскольку он входит в виде мультипликативной константы в выражение (6.6.10) для вероятности переполнения буфера на блок. Типичными значениями для последовательных декодеров являются значения размер буфера в ребрах В та Скорость вычислений зависит от скорости поступления данных, измеряемой в битах на секунду, а также от быстродействия и сложности логических схем, используемых для выполнения вычислений. Например, если максимальное быстродействие логических схем составляет вычислений ребер/с, а скорость поступления данных равна то Ясно, что необходимо всегда иметь хотя бы для того, чтобы просто справляться с поступающими данными. Поэтому при относительно малых скоростях передачи данных (меньших 100 Кбит/с) можно получить произведения большие 107. Конечно, зависит также от сложности вычисления метрики. Например, вычисление метрики Хэмминга для ДСК много проще, чем вычисление метрики для канала с восьмеричным выходом; отсюда следует, что для ДСК будет в несколько раз больше.

Из сравнения (6.6.9) с (6.6.2) видно, что произведение при последовательном декодировании играет ту же роль, что и величина для декодера Витерби. Конечно, как уже отмечалось, при малых скоростях может иметь величину порядка 107, в то время как число регистров, необходимых для хранения указателей пути и метрик при декодировании по максимуму правдоподобия, равное невозможно сделать большим чем 103. С другой стороны, при больших скоростях передачи данных ( бит/с и выше) практически трудно сделать больше единицы, как это требуется для эффективного последовательного декодирования, за

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

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

Последним важным фактором, который должен учитываться всегда, когда делается выбор между декодированием Витерби и последовательным декодированием, является относительная чувствительность декодирования к изменению параметров канала, т. е. его робастность. В этом последовательный декодер уступает декодеру Витерби, так как его характеристики сильно зависят выбора метрики, в свою очередь, зависящей от параметров канала (например от вероятности ошибки в канале для ДСК, от отношения сигнал-шум для АБГШ канала). Другой причиной изменения параметров канала является неточность отслеживания фазы (см. § 2.5). Действительно, уже было показано, что изменения как фазовых, так и амплитудных характеристик канала приносят вред последовательным декодерам больше, чем декодерам Витерби (Хэллер и Джекобе [1971], Джилхаузен и др. [1971]). Наглядным подтверждением робастности декодеров Витерби является и то, что в некоторых случаях они компенсируют несовершенство предшествующих им демодуляторов (Джекобе [1974]).