2.3. Алгоритмы декодирования сверточных кодов и их характеристики
Данный алгоритм реализует поиск пути, соответствующего переданной информационной последовательности на решетке кода. Информация, полученная в процессе декодирования, используется не только для вынесения решения об информационных символах, но и для оптимизации дальнейшего поиска наиболее правдоподобных продолжений.
Практическое применение нашел алгоритм Фано [28].При малой вероятности ошибки в канале поиск максимально правдоподобного пути происходит достаточно быстро. Если искаженных символов много, в процессе поиска необходимо выполнить большое количество вычислений. Для сглаживания неравномерности вычислений декодер содержит буферную память, переполнение которой при интенсивном потоке ошибок ведет к отказу от декодирования. Поэтому данный алгоритм не получил широкого распространения, несмотря на то, что сложность его реализации пропорциональна малой степени длины кодового ограничения СК, что позволяет применять достаточно длинные коды. Данный алгоритм использовался для связи с космическими аппаратами Pioneer-10, 11 и 12 для полетов на Юпитер, Сатурн и Венеру соответственно, и обеспечивал РО|П=10*5 при Ь02:-2.7дБ.
Пороговый алгоритм
Пороговый алгоритм декодирования СК характеризуется
простотой реализации, высоким быстродействием, однородностью структуры декодера, но также и сравнительно малым выигрышем в помехоустойчивости, что обусловлено свойствами кодов, допускающих пороговое декодирование. Модификацией порогового алгоритма является многоиороговый алгоритм, который, сохраняя преимущества порогового алгоритма, позволяет получить значительный энергетический выигрыш. Существенным недостатком модифицированного алгоритма является большая задержка декодирования, возрастающая пропорционально числу дополнительно вводимых ступеней решения.
Алгоритм Витерби
Для декодирования коротких сверточных кодов наиболее эффективным является алгоритм Витерби.
Декодирование по этому алгоритму состоит в прослеживании по кодовой решетке пути с максимальной апостериорной вероятностью. При декодировании выбирают такую последовательность сигналов sL = (§о, §|, s2, S3..SL-1) (где L - длина последовательности), которая обеспечивает минимум суммыL-l N
МП = Е Е (z! - s!)2 = min,
называемой метрикой декодированного пути. В данной формуле Zl~ (zo> Zj, z2 ... zL-i) - последовательность, поступающая на вход декодера, как и выбираемая последовательность, представлена набором координат в N-мерном пространстве. Метрика пути содержит в качестве слагаемых метрики ветвей
мп = Емвь
N
где метрики ветвей MBt= Е (z! - st)2.
1=1
Периодическая структура решетчатой диаграммы существенно упрощает сравнение и выбор путей в соответствии с правилом минимизации метрики пути.
В соответствии с алгоритмом Витерби сравнение и отбрасывание отрезков путей производится периодически на каждом шаге декодирования. В каждом из состояний решетчатой диаграммы производятся следующие однотипные операции:
сложение метрик предыдущих состояний с метрикой соответствующих ветвей;
сравнение метрик входящих путей;
выбор путей с наименьшими метриками, величины которых используются как метрики состояний на последующих шагах декодирования.
На каждом шаге в результате сравнения половина возможных путей отбрасывается и в дальнейшем не используется. Поэтому количество вычислений на каждом шаге остается постоянным. Декодер прослеживает по кодовой решетке путь, имеющий минимальное расстояние от пути, который генерирует кодер.
Значения ЭВК, полученные при различных вероятностях ошибки для сверточных кодов, определяемых разными порождающими многочленами, приведены на рис. 2.7 и 2.8.
ЭВК, дБ 7 г -
!К= 1/2
0,01
0,0000001
ош
Результаты соответствуют когерентному приему BPSK и
декодированию по алгоритму Витерби с мягкими решениями. Графики для длины кодового ограничения v = 8 получены с помощью моделирования, остальные заимствованы из [52]. Анализ результатов показывает, что применение сверточных кодов позволяет получить ЭВК до 5.8 дБ при вероятности ошибки Рош = 10"5.