2. Декодирование сверточных кодов

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

Диаграмма состоит из узлов и ветвей. Число ветвей, исходящих из узла, равно основанию кода. Число узлов равно 2^{V - 1}, V – длина кодового ограничения. Единичному символу сообщения приписываются штриховые линии, а нулевому символу – сплошные линии. Выходные символы записываются над ветвями. Надписи у узлов характеризуют состояние кодирующего устройства.

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

Корректирующая способность сверточного кода определяется свободным расстоянием d_св , которое несет ту же информацию о коде, что и кодовое расстояние для блочных кодов. Оно определяется как минимальный вес (минимальное число единиц) пути на решетчатой диаграмме, начинающегося и заканчивающегося на нулевом узле. Для рассматриваемого кода d_св = 5.

Рис. 15. Кодер:

а - сверточного кода (1/2, 3); б - решетчатая диаграмма кода

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

К методам декодирования без вычисления проверочной последовательности относится, например, декодирование по принципу максимума правдоподобия. Такое декодирование сводится к отождествлению конкретной принятой последовательности с одной из 2^N возможных, где N – длина информационной последовательности. Решение принимается в пользу той последовательности, которая в меньшем числе позиций отличается от принятой. Заметим, что для больших значений N метод труднореализуем.

Существенное упрощение метода предложил А. Витерби.

Рассмотрим сущность алгоритма декодирования А. Витерби для кода (1/2).

Пусть начальное состояние кодирующего устройства известно. Из рассмотрения решетчатой диаграммы видно, что в любой i–й узел на любом такте из начального состояния ведут несколько путей, которым соответствуют определенные кодовые последовательности.

Из всех путей выбираем тот, которому соответствует кодовая последовательность , наиболее близкая к принятой последовательности (отличается от принятой в меньшее число символов). Этот путь называется «выжившим».

Обозначим расстояние Хэмминга между этими последовательностями через . Припишем вес i–му узлу. Проделаем процедуру для всех прочих узлов.

Возьмем любой k–й узел решетчатой диаграммы в следующий тактовый момент, связанный с i–м узлом путем ik, с j–м узлом путем jk. Вычислим величины и , где приращение расстояния Хэмминга при продолжении путей из узла j к узлу k. Приращения определяются по принятому сегменту последовательности и символам, соответствующим рассматриваемым ветвям. Если , то ветвь ik считается истинний и записывается в память декодирующего устройства, а ветвь jk и все ей предшествующие ветви отбрасываются. Аналогичная операция выполняется для всех других узлов. В результате в памяти декодирующего устройства на l + 1 шаге будет храниться 2^{V - 1} путей, а через примерно 5V тактов в кодовом дереве останется лишь один путь с минимальным весом. Поэтому решение о том, какое сообщение передавалось, можно принимать на m + 5 V такте.

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

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

Декодирование по методу Витбери особенно перспективно в каналах с независимыми ошибками.

5.3. Кодирование с перемежением

Основным назначением помехоустойчивых кодов является борьба с одиночными независимыми ошибками. При таком подходе избыточность исправляющих ошибки кодов остается небольшой, а кодеки реализуются достаточно просто.

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

Очевидно, существует такой способ передачи информации, при котором пакет ошибок, возникающий из-за неустранимых внешних причин и сос­тоящий из искаженных символов одного кодового блока (слова, кодовой комбинации), можно было бы преобразовать в пакет из независимых друг от друга ошибок и принадлежащих разным ко­довым блокам. В этом случае даже при достаточно длинных па­кетах ошибок возможно использование сравнительно коротких корректирующих кодов.

Одним из возможных решений этой задачи является приме­нение кодека, исправляющего случайные ошибки, вместе с парой устройств, состоящих из устройства перемежения и устройства восстановления после перемежения. При этом последовательность на выходе кодера подвергается перемежению до передачи в ка­нал и восстанавливается перед декодированием, вследствие че­го на вход кодера поступают кодовые слова, содержащие ошибки (рис. 16).

Рис. 16. Канал связи, использующий кодирование с деперемежением

Устройство перемежения переупорядочивает (переставляет) символы в кодовой последовательности некоторым детерминированным образом.

Устройство деперемежения (восстановления) на приемной стороне осущест­вляет обратную перестановку символов и восстанавливает, та­ким образом, исходные кодовые слова. Зависимые ошибки за счет этой операции разрушаются, что упрощает исправление ошибок при декодировании.

Существует много типов устройств перемежения, которые образуют два основных класса - периодические и псевдослучайные.

Периодическим называется такое устройство перемежения, в котором перестановка является периодической функцией вре­мени. Различают два типа таких устройств - блоковые и сверточные, различие между которыми очень похоже на различие между блоковыми и сверточными кодами.

В блоковых устройствах перемежения на вход поступают кодовые слова, из которых формируется матрица размером b · N , где N - число строк, а b - число столбцов» При этом устройство называется (b, N)-устройством перемежения. Запись осуществляется по столбцам, а считыва­ние - по строкам (или наоборот):

Устройство восстановления осуществляет обратную операцию: записывает символы по строкам, а считывает их по столбцам.

Наиболее важные свойства блокового перемещения:

1. Любой пакет ошибок длиной b ≤ B переходит на выхо­де устройства восстановления в одиночные ошибки, каждые две из которых разделены не менее чем N символами;

2. Любой пакет ошибок длиной l = rb (r>1) переходит в пакеты ошибок длиной не больше r символов, каждые два из которых разделены не менее чем N - r символами.

3. Периодическая последовательность одиночных ошибок, разделенных b символами, переходит в один пакет ошибок длиной N на выходе устройства восстановления.

4. Задержка устройства составляет 2NB символов (в добавление к задержке в канале), и каждое из устройств требу­ет наличия памяти емкостью NB символов.

В типичных случаях параметры устройств перемежения вы­бирают такими, чтобы длина l всех ожидаемых пакетов ошибок не превышала B. Если, однако, характеристики пакетов оши­бок нестационарны, то, согласно свойству 3, устройства переме­жения становятся неустойчивыми.

Выбор параметра N зависит от используемой схемы коди­рования, и этот параметр N должен быть выбран бόльшим, чем длина отрезка, на котором производится декодирование. Для блоковых кодов значение N должно быть больше длины кодово­го слова, а для сверточных кодов - больше длины кодового ог­раничения.

Псевдослучайное устройство перемежения представляет собой блоковое устройство, которое берет блоки из L символов после кодирования и переставляет их псевдослучайным образом. Это можно сделать, записав L символов последовательно в память и затем считать их случайным (псевдослучайным) образом.

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

Псевдослучайное перемежение используется преимущественно в каналах с преднамеренными по­мехами.

Еще одним способом борьбы с пачками ошибок является каскадное кодирование, которое используется вместо мощных корректирующих кодов. При этом осуществляется так называемое каскадирова­ние нескольких сравнительно коротких корректирующих кодов.

Наиболее часто используется система с двумя уровнями кодирования. Одним из кодов является внешний код (обычно используется код Рида – Соломона, являющийся подклассом кодов БЧХ, способных исправлять пакеты ошибок), а в качестве второго - внутреннего - выбирается один из многих различных кодов.

Входные данные подвергаются сначала внешнему кодированию, а затем внутреннему. В результате получают эквивалентный (или каскадный) код.

На приемной стороне сначала выполняется внутреннее декодирование, а затем внешнее.

Комбинацию внутреннего кодера, канала и внутреннего де­кодера называют суперканалом, комбинацию внешнего и внутрен­него кодеров - суперкодером, а комбинацию внутреннего и внеш­него декодеров - супердекодером.

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

Контрольные вопросы

1. В каком случае метод кодирования считается эффективным?

2. Что понимается под трудоемкостью кодирования?

3. Поясните преимущества рекуррентных кодов по сравнению с блочными.

4. Поясните обозначение сверточного кода.

5. Как определить корректирующую способность сверточного кода?

6. Какой рекуррентный код называется систематическим?

7. Какие подходы используются при декодировании сверточных кодов?

8. Поясните принцип построения решетчатой диаграммы сверточного кода.

9. Каково назначение решетчатой диаграммы?

10. Как с помощью решетчатой диаграммы закодировать сообщение?

11. Поясните принцип работы декодера по алгоритму Витерби.

12. Какие функции в канале передачи информации выполняет устройство перемежения?