Сверточные коды

Сверточные коды описываются тремя числами n,k,K. Длина n кодового слова является не только функцией входного сообщения длиной k, но и функцией кодового ограничения K (число разрядов в регистре сдвига- см. рисунок 6.4).

Схема, изображенная на рисунке 4 дает в каждый момент времени на выходе кодовую последовательность , состоящую из k бит , значение которых вычисляются как линейная функция входных битов. Слово «сверточный» отражает от факт, что данные на выходе генерируются с помощью линейного сложения (т.е. «свертки») смещенных во времени импульсов последовательности на входе с импульсной характеристикой кодера ( заполнения регистров предыдущими битами).

Рисунок 6.4. Схема устройства сверточного кодирования.

Рассмотрим сверточный кодер со степенью кодирования (иногда этот параметр называется скоростью передачи кода, т.к. описывает, в какое число раз увеличивается скорость передачи бит на выходе по сравнению со входом ) ½ и величиной кодового ограничения K=3, изображенный на рисунке 6.5. В этом кодере может возникнуть ограниченное число состояний. Под состоянием в общем смысле понимается наименьшее количество информации, на основе которой вместе с текущими входными данными можно определить данные на выходе системы. Для сверточного кодера со степенью кодирования состояние представляется содержимым K-1 крайних правых разрядов кодера и поэтому можно сказать, что будущие состояния ограничиваются прошлыми состояниями.

Рисунок 6.5. Сверточный кодер со степенью кодирования ½ и величиной кодового ограничения K=3.

Одним из способов представления простых кодирующих устройств является диаграмма состояний (рисунок 6.6). Состояния, показанные в рамках диаграммы, представляют собой возможное содержимое K-1 крайне правых разрядов регистра, а пути между состояниями – ответвляющиеся слова на выходе, являющиеся результатом переходов между такими состояниями. Существует всего два исходящих из каждого состояния перехода, и два входящих соответствующие двум возможным входным битам. И главное то, что за один переход невозможно перейти из данного состояния в любое произвольное.

Рисунок 6.6. Диаграмма состояний кодера со степенью кодирования ½ и K=3.

Несмотря на то, что диаграммы состояний полностью описывают кодер, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени. Древовидная диаграмма (рисунок 6.7) прибавляет к диаграмме состояния временное измерение. В каждый последующий момент прохождения входящего бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает ответвленное слово на выходе. Узлы решетки представляют собой состояния кодера, сплошная линия обозначает выходные данные, генерируемые входным нулевым битом, а пунктирная – выходные данные, генерируемые входным единичным битом. Фиксированная структура древовидной диаграммы реализуется после достижения глубины К. С этого момента в каждое состояние можно войти из любого из двух предыдущих состояний. Их каждого состояния можно также перейти в одно из двух состояний. Над каждой ветвью написано число, представляющее собой метрику по Хэммингу (количество совпадающих цифр в символе сообщения и выходном символе кодера). Эти пометки на ветвях решетки накапливаются декодером в процессе.

Рисунок 6.7.. Решетчатая диаграмма кодера ( степень кодирования ½, К=3)

Чтобы пометить ветви декодера подходящей метрикой расстояния Хэмминга, рассмотрим диаграмму состояний кодера. Переход между состояниями порождает на выходе ответвляющееся слово 00, однако получено 11. Следовательно, на решетке декодера помечаем переход между состояниями расстоянием Хэмминга между ними, а именно 2. Глядя вновь на диаграмму состояний, видим, что переход между состояниями порождает ответвляющееся слово 11, точно соответствующее полученному в момент времени кодовому символу. Следовательно, переход на решетке декодера между состояниями помечаем расстоянием Хэмминга 0. В итоге метрика входящих в решетку декодера ветвей описывает разницу между тем, что было получено и тем, что «могло быть» получено, имея ответствленные слова, связанные с теми ветвями, с которых они были переданы.