Ипатов В. Широкополосные системы и кодовое разделение сигналов (2007) (1151883), страница 77
Текст из файла (страница 77)
Расстояния двух путей, входящих в А, можно найти, измерив ме~прики ребер, т. е. расстояния последних от принятой группы п наблюдаемых символов, и прибавив их к метрикам узлов В и С. Путь с меньшим расстоянием считается выжившим для узла А и запоминается вместе с его расстоянием (метрикой узла), тогда как другой отбрасывается. По выполнении этих операций для всех узлов решетчатой диаграммы декодер переходит к следующему шагу.
Резюмируя сказанное, декодер Витерби на каждом шаге находит метрики ребер, добавляет их к метрикам всех узлов, аккумулированным ранее, после чего из двух путей, ведущих к каждому узлу, отбрасывает более удаленный от наблюдения. Поскольку всего имеется 2~' 1 узлов (т.е. состояний регистра), сложность декодера определяется исключительно длиной кодового ограничения о, и остается фиксированной вне зависимости от теоретически неограниченного числа кодовых слов (путей). Возвращаясь к принятому выше допущению о единственности выжившего пути для каждого узла, заметим, что в силу целочисленности расстояния Хэмминга всегда существует вероятность равенства текущих расстояний двух путей, ведущих в один узел, от наблюдения у.
Возможны различные стратегии разрешения подобных коллизий. Одна из них предполагает рандомизацию типа подбрасывания правильной монеты и провозглашения выжившим пути, ассоциированного заранее с определенной стороной монеты. Это до некоторой степени нарушает оптимальность декодирования, хотя сопутствующие энергетические потери, как правило, пренебрежимо малы. Как альтернативный вариант можно посчитать оба конкурирующих пути выжившими и хранить их до тех пор, пока коллизия не разрешится на последующих шагах. При такой стратегии декодирование останется строго оптимальным, за что придется заплатить ббльшим объемом памяти декодера. Пример 9.8.
Рассмотрим декодирование наблюдения р = 0100110000... для кода из примера 9.5. На рис. 9.9, иллюстрирующем процедуру, метрики узлов помещены непосредственно рядом с узлами, а принимаемые на текущем шаге пары символов наблюдения заключены в рамки. Декодер инициализируется в предпо- (376 Глава й. Канальное кодирование в широканоласнььх системах ППИ (00) (ю> (оц (1Ц 1 2 3 (00) 00> (оц (1Ц г 5 (ОО) 00> (оц (1Ц г г Шаг (00) (ю> (оц (1Ц (00) цо> (оц (1Ц Рис.
9.9. Динамика декодирования сверточного кода примера 9.5 ложении нулевого (т.е. 00) начального состояния регистра кодера. Два первых (и,— 1 = 2) шага отвечают переходному режиму кодера, когдалишь единственное ребро входит в каждое состояние (см. рис. 9.9), и поэтому все пути выживают. На первом шаге декодер сравнивает первую группу иэ п = 2 символов наблю- 00 11 11 00 ю о! о! ю Шаг 00 11 1! ° 00 ю ° О1 о! ° ю Швг ОО 11 11 ° 00 ю ° о! о! ° ю Шаг 00 !! !1 ° ОО ю ° О! О> ° ю Швг г 4 4 г 4 3 4 3 5 2 5 4 3 г 4 г 3 4 4 б 4 4 4 5 4 5 8 2 5 4 3 3 4 3 3 б 9.2 С р д 377)) денна с двумя ребрами, выходящими из состояния (00). В соответствии с их расстоянием Хэмминга от наблюдаемых символов 01 и сплошное, и пунктирное ребра решетки получают одинаковую, равную единице метрику, оцифровывзюшую каждое из ребер. Тем самым, метрики двух узлов, в которые входят ребра, равны единице.
На следующем шаге расстояние измеряется между второй группой наблюдаемых символов 00 и двумя парами ветвей, исходящих из узлов (00) и (10), имея результатом метрики, маркирующие ребра. Прибавленные к метрикам узлов предшествующего шага они обновляют метрики узлов (00) и (10), а также инициализируют метрики еще двух узлов (01) и (11).
Начиная с третьего шага в любой узел решетчатой диаграммы рис. 9.9 входят по два ребра, означая, что декодер должен решать, какое из них принадлежит выжившему пути. Чтобы не перегружать рисунок, метрики ребер на нем с этого шага опущены. Как видно, на третьем шаге имеются два пути, ведущие к узлу (00). Их расстояния от наблюдаемых символов 010011 равны 3 и 2 соответственно. Первый из них не выживает и отбрасывается декодером вместе с его метрикой, поэтому на рисунке он зачеркнут, а на диаграмме, отвечающей следующему шагу, отсутствует. Второй путь выживает и запоминается со своей метрикой до следующего шага.
Точно так же декодер выделяет выжившие пути и дяя остальных узлов. На последующих шагах декодер действует аналогично, сохраняя в памяти только 2'" ~ = 4 выживших путей, и каждая очередная диаграмма рис. 9.9 содержит только пути, выжившие на предшествующем шаге. На 7-м шаге декодер впервые сталкивается с неоднозначностью: два пути приходят в узел (01), как и в узел (11), с равными расстояниями.
Тот выбор выжившего пути, который показан на рисунке, может считаться основанным на бросании монеты. Подобные события имеют место и на 8-м и 9-м шагах. Читатель может убедиться (задача 9.19), что любое альтернативное разрешение коллизий не повлияет на окончательный результат декодирования, за исключением, быть может, номера шага, на котором возможно первое считывание декодированных битов данных (см.
ниже). По завершении девятого шага возникает критически важная ситуация: все выжившие пути совпадают друг с другом вплоть до седьмой группы наблюдаемых символов. Что бы ни произошло впоследствии, эта часть всех слившихся путей останется общей навсегда, означая, что соответствуюшне ей биты данных можно сразу выдать на выход как декодированные. Таким образом, декодер выдает декодированные данные 1000000. Сравнивая кодовое слово и = 11101100000000..., отвечающее указанному битовому потоку, с наблюдением у = 0100110000, можно видеть, что расстояние Хэмминга между ними равно двум, и если выданное декодером слово было передано в действительности, значит имело место исправление двух символьных ошибок в полном согласии со свободным расстоянием Иу = 5.
Подобные ситуации будут возникать и в дальнейшем, позволяя декодеру выдавать декодированиые биты по ходу обработки потока символов наблюдения. Понятно, что выдача декодированных данных в случайные моменты слияния выживших путей, как в нашем примере, не вполне практична, и предпочтительнее была бы процедура более регулярного характера. ~~~378 Глава в. Канальное кодирование в широноиолоснмх системах С помощью многократных и практически исчерпывающих компьютерных тестов и имитационных экспериментов было установлено, что к г-му шагу декодирования слившийся участок всех выживших путей почти всегда заканчивается после г — 5ь, битов данных, так что решение о любом бите может регулярно выдаваться на выход с задержкой в 5рс [94).
Замечательное свойство сверточных кодов, придающее им еще ббльшую привлекательность, сравнительная простота осуществления мягкого декодирования. В общем случае произвольного блокового кода с М словами мягкое декодирование означает прямое вычисление М евклидовых расстояний или корреляций, причем никакие алгебраические ухищрения типа синдромного декодирования при этом невозможны. При значительных объемах кода М, характерных для большинства приложений, сложность мягкого декодирования нередко оказывается неприемлемой. В то же время упрощение декодера.
за счет жестких решений оплачивается энергетическими потерями, составляющими для АБГШ канала 2 дБ и более, что ныне считается довольно значимой цифрой. Вернемся теперь к алгоритму Витерби и попросту заменим в нем расстояние Хэмминга евклидовым (в квадрате). Подобная замена, очевидно, преобразует декодирование в мягкое, оптимальное для АБГШ канала. При этом метрики ребер и узлов станут в точности соответствующими евклидовыми расстояниями (эквивалентно — корреляциями). Такая модификация никоим образом не лишит алгоритм Внтерби присущих ему реализационных преимуществ. Действительно, метрики узлов будут вычисляться, как и ранее, рекурсивно, пошаговым аккумулированием метрик ребер, и на каждом шаге тот из двух путей, входящих в узел, который имеет худшую метрику, будет вновь отброшен как не выживший.
Разумеется, цифровая реализация декодеров наиболее рациональна, подразумевая необходимость в квантовании входного наблюдения. Общепринято относить к числу мягких любые декодеры двоичных кодов с квантованием наблюдений более чем на два уровня. Детальные исследования показали, что в большинстве случаев 3-битовое (8-ми уровневое) квантование достаточно для достижения почти потенциальной (теоретически ожидаемой при непрерывной обработке) достоверности декодирования [94).
9.3.4. Приложения В настоящее время известно много эффективных сверточных кодов, диапазон реального и потенциального применения которых в телекоммуникациях чрезвычайно широк. В частности, в 20 и ЗС стандартах сйшаОпе и Ъ'СПМА используются коды с длиной кодового ограничения 9.~. Трр6 . ~ 379) г, = 9 и скоростями В, =- 1/2, В, = 1/3, обеспечивающие асимптотический выигрыш от кодирования около 7,8 дБ ~18, 69, 921. В 30 стандарте сс1ша2000 в дополнение к упомянутым вьппе предусмотрен код с параметрами г, = 9, В, = 1/4.
Сверточные коды, представляя весьма значительную собственную ценность, служат также основой для построения других кодов, например турбо-кодов, кратко обсуждаемых в следующем разделе и позволяющих надежно передавать данные со скоростями, близкими к границе Шеннона. 9.4. Турбо-коды Как отмечалось в 3 9.1, в течение десятилетий с момента опубликования фундаментальных работ Шеннона, заложивших основы теории информации, многократные и упорные попытки отыскания регулярных правил кодирования, позволяющих работать на скоростях передачи, близких к пропускной способности, оставались безуспешными.
В свете этого открытие в 1993 г. турбо-кодов явилось впечатляющим прорывом, первоначально встреченным телекоммуникационным сообществом с объяснимым недоверием. В настоящее время, однако, турбо-коды широко признаны в качестве эффективного инструмента высоконадежной связи, особенно при относительно малом отношении сигнал-шум на бит. Строгая и компактнал теория этого класса кодов остается пока скорее воодушевляющей целью, чем осуществленной реальностью, и в накоплении многих результатов значительная роль продолжает принадлежать интуиции в сочетании с обширными компьютерными тестами. 9А.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
