5.2. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ПО МАКСИМУМУ ПРАВДОПОДОБИЯ

Пусть последовательность слов передается по каналу с аддитивным гауссовским белым шумом и отношением энергии сигнала к мощности шума и пусть принятое слово, искаженное шумами В качестве СКК могут рассматриваться и CKKI, и CKKII Для сокращения описания все алгоритмы будем трактовать как бы для CKKI, а отличия,

возникающие при использовании CKKII, указывать после описания алгоритма.

Рассмотрим два класса алгоритмов декодирования с независимым декодированием внешними кодами по максимуму правдоподобия и по максимуму правдоподобия Каждый из этих алгоритмов применим для произвольных и линейных внешних кодов.

Рассмотрим сначала СКК с произвольными внешними кодами. Алгоритм декодирования СКК с независимым декодированием по максимуму правдоподобия с произвольными внешними кодами состоит из шагов На каждом шаге производятся процедуры приема сигналов по максимуму правдоподобия (декодирования внутренним кодом) и декодирование внешним кодом по максимуму правдоподобия.

Пусть к началу шага определены некоторые векторы внешних кодов Тогда каждый сигнал декодируется во внутреннем коде При мягком декодировании внешними кодами определяются условные вероятности

В случае жесткого декодирования внешними кодами определяем такой, что По у определяем номера подкодов которым они принадлежат В результате получаем вектор который декодируем по максимуму правдоподобия. Результатом такого декодирования является вектор для которого

При мягком декодировании внешними кодами результатом декодирования является вектор, максимизирующий вероятность

Легко убедиться, что сложность реализации такого алгоритма (как при жестком, так и мягком декодировании) в некоторых элементарных операциях, например сложениях,

Также легко убедиться, что декодирование как, впрочем, и для любого другого алгоритма декодирования

произвольного кода, ничем не отличается от CKKI. В данном случае каждый двоичный код длины трактуется как некоторый код длины и тогда CKKI и CKKII ничем не отличаются.

Рассмотрим теперь алгоритм декодирования СКК по максимуму правдоподобия в целом Алгоритм также состоит из шагов На первом шаге декодируем каждый принятый сигнал в коде При мягком декодировании внешними кодами определяются условные вероятности жестком декодировании внешними кодами определяем жестокое решение о сигнале в коде Далее для каждого из слов первого внешнего кода определяем вероятность в случае мягкого декодирования и жесткого.

Одновременно определяем вероятности

На втором шаге декодирования для каждого вектора первога внешнего кода проводим декодирование каждого принятого -мерного сигнала . В случае мягкого декодирования внешними кодами определяют условные вероятности Для жесткого декодирования внешними кодами определяем а есть жесткое решение о сигнале в коде Далее для каждого из слов второго внешнего кода определяем вероятность в случае мягкого декодирования и жесткого. По результатам декодирования кодов определяем вероятности

при мягком и

при жестком декодировании.

Одновременно определяем обратные вероятности:

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

Как видно, алгоритм с жестким декодированием внешними кодами на самом деле использует некоторую дополнительную информацию по сравнению с предыдущим алгоритмом Римп. Как и при декодирование CKKI и ничем не различается. Сложность реализации алгоритма элементарных операциях:

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

Если воспользоваться решетчатой диаграммой двоичного кода длины то нельзя организовать процедуру декодирования по Витерби, так как каждому канальному символу соответствует несколько ребер кода. Следовательно, решетчатую диаграмму надо модифицировать. Рассмотрим решетчатую диаграмму кода Из каждого узла выходят и в каждый узел входят два ребра Укрупним эту диаграмму, оставив только вертикальные ярусы с номерами, кратными все ребра будем «метить» двоичными числами. Каждому ребру модифицированной диаграммы узла с номером в узел с номером соответствует путь по обычной решетчатой диаграмме из узла с номером в узел с номером Естественно, что у такой решетчатой диаграммы могут иметься параллельные пути из узла в узел, и тогда диаграмма соответствует -ичному коду длины не оптимальному с точки зрения хэммингова расстояния. Но смысл введения указанной диаграммы состоит в использовании евклидова расстояния СКК

Рис. 5.2 Примерный вид модифицированной диаграммы двоичного -кода

Примерный вид модифицированной диаграммы показан на рис. 5 2. На рис. 5.3 показан пример модификации диаграммы кода при

После того как произвольный внешний линейный код представлен модифицированной решетчатой диаграммой, алгоритм декодирования ничем не отличается от алгоритма декодирования Сложность реализации алгоритма с линейными внешними кодами в элементарных операциях ограничена неравенством

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

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

Рис. 5.3 Пример получения из решетчатой диаграммы ( кода модифицированной диаграммы при

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

На втором шаге проведем укрупнение решетчатой диаграммы. Для этого каждый узел решетки в вертикальном ярусе с номером расщепим на узлов с номерами где частичный синдром кода частичный синдром кода Каждое ребро решетки с меткой из узла в узел заменим на часть решетки кода из вертикального яруса в Тогда каждому ребру укрупненной решетки будет соответствовать пара значений всего узлов в укрупненной решетке — не более

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

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

Так как имеется взаимооднозначное соответствие между символами и сигналом то пометим ребра решетки сигналами Тем самым получим решетчатую диаграмму для CKKI. Аналогично можно получить решетчатую диаграмму для CKKII, если воспользоваться при ее построении модифицированными решетчатыми диаграммами внешних кодов.

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

(кликните для просмотра скана)

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

Следует отметить, что как при мягком, так и при жестком декодировании этот алгоритм абсолютно идентичен по помехоустойчивости алгоритму произвольных СКК Сложность реализации ограничена неравенством

Пример 5.1 Рассмотрим при с внутренним ансамблем сигналов и двумя внешними двоичными кодами Тем самым получается CKKI (8, 2, 16) Ансамбль сигналов данной СКК показан на рис. на рис 5 4,6 иллюстрируется процесс получения решетчатой диаграммы СКК

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

На рис 5 4, г показано декодирование по Витерби СКК в целом, которое приводит к правильному слову СКК Цифрами у узлов показаны текущие метрики правдоподобия

Данный пример показывает, что декодирование по максимуму правдоподобия СКК в целом часто может оказаться очень выгодным, особенно для СКК не очень большой размерности. Однако, как будет видно, не следует пренебрегать и независимым декодированием внешними кодами.