9.5. Последовательное и пороговое декодирование сверточных кодов.

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

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

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

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