Контрольные вопросы
9.1. Назовите основные параметры сверточных кодов.
9.2. Каковы правила построения диаграммы состояний СК?
9.3. Какова связь между диаграммой состояний СК и решетчатой диаграммой?
9.4. Как определить свободное расстояние СК по диаграмме состояний?
Задания
9.1. Заданы порождающие многочлены СК (g(1), g(2)) = (1101,1111). определите параметры такого СК. Каково восьмеричное и многочленное представления (g(1)(D), g(2)(D)) этого кода?
9.2. Приведите функциональную схему кодера из задания 9.1.
9.3. Постройте диаграмму состояний и решетчатую диаграмму кода из задания 9.1. Покажите, как по ним определить свободное расстояние кода. отыщите строку, соответствующую этому коду в таблицах СК приложения А.3. По аналогии с упражнением 9.1 проанализируйте взаимосвязь параметров этого кода с величиной свободного расстояния. Сделайте обобщающие выводы.
9.4. Подготовьте решетчатую диаграмму кода (1, 5) из упражнения 9.1, необходимую для иллюстрации алгоритма Витерби.
10. Алгоритмы декодирования сверточных кодов
10.1. Классификация алгоритмов декодирования СК [1, разд. 10.12; 2, разд. 3.6].
10.2. Алгоритм А. Витерби для декодирования сверточных кодов [2, разд. 3.6].
10.1. Классификация алгоритмов декодирования
При оптимальной обработке с целью вынесения решения принятую из канала последовательность символов необходимо сопоставить со всеми возможными передаваемыми последовательностями. Так как число возможных последовательностей длины N двоичного кода равно 2n, то при больших длинах последовательностей декодер становится недопустимо сложным (экспоненциальная сложность декодирования, см. разд. 6.3), а оптимальное декодирование – практически трудно реализуемым. Однако, именно при больших n возможно значительное повышение надежности передачи, так как действие шума усредняется на длинной последовательности. Поэтому важной является проблема снижения сложности алгоритмов декодирования СК. Известны две группы методов декодирования сверточных кодов:
1) Алгебраические методы декодирования основаны на использовании алгебраических свойств кодовых последовательностей. В ряде случаев эти методы приводят к простым реализациям кодека. Такие алгоритмы являются неоптимальными, так как используемые алгебраические процедуры декодирования предназначены для исправления конкретных (и не всех) конфигураций ошибок в канале. Алгебраические методы отождествляют с поэлементным приемом последовательностей, который для кодов с избыточностью, как известно, дает худшие результаты, чем «прием в целом». Наиболее простым из алгебраических алгоритмов является алгоритм порогового декодирования сверточных кодов. Этот алгоритм далек от оптимального и поэтому редко используется, а используется, в первую очередь, в системах с высокой скоростью передачи информации. Более подробное описание порогового алгоритма и его модификации можно найти в литературе [2, разд. 3.6.3].
2) Вероятностные методы декодирования значительно ближе к оптимальному «приему в целом», так как в этом случае декодер оперирует с величинами, пропорциональными апостериорным вероятностям, оценивает и сравнивает вероятности различных гипотез и на этой основе выносит решения о передаваемых символах.
Алгебраические алгоритмы оперируют с конечным алфавитом входных данных, для получения которых на выходе непрерывного канала необходимо выполнить квантование принимаемого сигнала с шумом. Процессы обработки сигналов в решающем устройстве на выходе демодулятора противоположных сигналов показаны на рис. 10.1, где представлены:
а, в) – формы противоположных сигналов в момент отсчета на входе решающего устройства демодулятора.
б) – шкала квантования и граф переходов при жестком решении.
г) – шкала квантования и граф переходов при мягком решении.
В простейшем случае производят квантование каждого канального символа в отсчетный момент времени на два уровня (именуемое в литературе как «жесткое решение» на выходе демодулятора). При жестком решении число уровней квантования L = 2. При этом жесткое решение представлено одним двоичным символом. Это показано на рис. 10.1,б.
При «мягком решении» число уровней квантования L > 2 (рис. 10.1, г).
При мягком решении выход квантователя более точно описывает величину отсчета сигнала с помехой, что повышает помехоустойчивость декодирования.
Известны два основных вероятностных алгоритма декодирования сверточных кодов, а также их различные модификации.
1. Алгоритм последовательного декодирования обеспечивает произвольно малую вероятность ошибки при ненулевой скорости передачи сообщений по каналу. При последовательном декодировании производится поиск пути на кодовой решетке, соответствующего переданной информационной последовательности. Последовательное декодирование используется для декодирования длинных сверточных кодов. Детальное изложение алгоритма последовательного декодирования представлено в литературе [4, разд. 13.18].
Другой разновидностью вероятностных алгоритмов является алгоритм, основанный на принципе динамического программирования, и известный как алгоритм Витерби.
Принцип динамического программирования был сформулирован в 1940 г. Р. Беллманом. С тех пор он нашел широкое приложение в теории управления и теории цепей. В 1970 г. динамическое программирование, в форме алгоритма декодирования СК (алгоритма Витерби), было применено А. Витерби к проблемам телекоммуникации.
2. алгоритм Витерби находит широкое применение и реализует поиск максимально правдоподобного пути на кодовой решетке с отбрасыванием части наименее правдоподобных вариантов путей на каждом шаге декодирования. Алгоритм Витерби характеризуется постоянством вычислительной работы, однако сложность декодера Витерби растет, как при всех переборных алгоритмах, по экспоненциальному закону от длины кодового ограничения сверточного кода. Поэтому алгоритм Витерби используется для декодирования коротких сверточных кодов.