Лекции по Теоретическим основам цифровой связи   

7. Канальное кодирование: часть 2

7.4 Свойство сверточных кодов

7.4.1. Пространственные характеристики сверточных кодов

Рассмотрим пространственные характеристики сверточных кодов в контексте простого кодера и его решетчатой диаграммы (рис 7.7.). Мы хотим узнать расстояние между всеми возможными парами последовательности кодовых слов. Как и в случае блочных кодов (см. раздел 6.5.2), нас интересует, минимальное расстояние между всеми такими парами последовательности таких кодовых слов в коде, поскольку минимальное расстояние связано с возможностями кода в коррекции ошибок. Поскольку сверточный код является групповым или линейным [6], можно без потери общности просто найти минимальное расстояние между последовательностью кодовых слов и нулевой последовательностью. Другими словами, для линейного кода  данное контрольное сообщение окажется точно таким же «хорошим», как и любое другое. Так почему бы не взять то сообщение, которое легко проследить, а именно нулевую последовательность? Допустим, что на вход передана нулевая последовательность; следовательно, нас интересует такой путь, который начинается и заканчивается в состоянии 00 и не возвращается к состоянию 00 нигде внутри пути. Всякий раз, когда расстояние любых других путей, которые сливаются с состоянием а = 00 в момент     окажется меньше расстояния нулевого пути. Иными словами, при нулевой передаче ошибка возникает всегда, когда не выживает нулевой путь. Следовательно, ошибка, о которой идет речь, связана с выживающим путем, который расходиться, а затем снова сливается с нулевым путем. Может возникнуть вопрос, зачем нужно чтобы пути сливались? Не будет ли для обнаружения ошибки достаточно лишь того, что бы пути расходились? В принципе, достаточно, но если ошибка характеризуется только расхождением, то декодер, начиная с этой точки, будет выдавать вместо оставшегося сообщения сплошной «мусор». Мы хотим выразить возможности декодера через число обычно появляющихся ошибок, то есть хотим узнать «самый легкий» для декодера способ сделать ошибку. Минимально расстояние для такой ошибки можно найти, полностью изучив все пути из состояния 00 в состояние 00. Итак, давайте заново начертим решетчатую диаграмму, как показано на рисунке 7.16, и обозначим каждую ветвь не символом ответвляющегося слова, а её расстояние Хемминга от нулевого кодового слова. Расстояние Хемминга между двумя последовательностями разной длины можно получить путем их сравнивания, т.е. прибавив к началу более короткой последовательности нужное количество нулей. Рассмотрим все пути, которые расходятся из нулевого пути и затем в какой то момент снова сливаются в произвольном узле. ИЗ диаграммы на рисунке 7.16 можно получить расстояние этих путей до нулевого пути. И так, на расстоянии 5 от нулевого пути имеется один путь; этот путь отходит от нулевого в момент в . Точно так же имеется два пути с расстоянием 6, один отходит в момент   и сливается с ним в момент , а другой отходит в момент  и сливается с ним в момент  и т.д. Также можно видеть (по пунктирным и сплошным линиям на диаграмме), что входными битами для расстояния 5 будет 100; от нулевой последовательности эта последовательность отличается только одним битом. Точно так же входные биты для путей с расстоянием 6 будут 1100 и 10100; каждая из этих последовательностей отличается от нулевого пути в двух местах. Минимальная длина пути из числа расходящихся, а затем сливающихся путей называетсяминимальным просветом (minimum free distance), или просто просветом (free  distance). Его можно видеть на рис. 7.16, где он показан жирной линией. Для оценки возможностей кода коррекции ошибок, мы повторно приведем уравнение (6.44) с заменой минимального расстояния  на просвет .

       (7.11)

Здесь [x] означает наибольшее целое, не большее х. Положив =5, можно видеть, что код, описываемый кодером на рис. 7.3, может исправить две любые ошибки канала (см. раздел 7.4.1.1).

Рис. 7.16. Решетчатая диаграмма с обозначенными расстояниями от нулевого пути

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

Хотя на рис. 7.16 представлен способ прямого вычисления просвета, для него можно получить более строгое аналитическое выражение, воспользовавшись для этого диаграммой состояний, изображенной на рис. 7.5. Для начала обозначим ветви диаграммы состояний как , как это показано на рис. 7.17, где показатель D означает расстояние Хэмминга между ответвленным словом этой ветви и нулевой ветвью. Петлю в узле а можно убрать, поскольку она не дает никакого вклада в пространственные характеристики последовательности кодовых слов относительно нулевой последовательности. Более того, узел а можно разбить на два узла (обозначим их а и е), один из них представляет вход, а другой — выход диаграммы состояний. Все пути, начинающиеся из состояния а=00 и заканчивающиеся в е=00, можно проследить на модифицированной диаграмме состояний, показанной на рис. 7.17. Передаточную функцию пути a b c e (который начинается и заканчивается в состоянии 00) можно рассчитать через неопределенный “заполнитель” D как . Степень D — общее число единиц на пути, а значит, расстояние Хэмминга до нулевого пути. Точно так же пути a b d c e и а b c b с е имеют передаточную функцию D6 и, соответственно, расстояние Хэмминга, равное 6, до нулевого пути. Теперь уравнения состояния можем записать следующим образом

                                        (7.12)

                                                

Здесь  являются фиктивными переменными неполных путей между промежуточными узлами. Передаточную функцию,T(D), которую иногда называют производящей функцией кода, можно записать как . Решение уравнений состояния (7.12) имеет следующий вид [15, 16].

              (7.13)

Передаточная функция этого кода показывает, что имеется один путь с расстоянием 5 до нулевого вектора, два пути — с расстоянием 6, четыре — с расстоянием 7. Вообще, существуют  пути с расстоянием l+5 до нулевого вектора, причем l = 0,1,2,... . Просвет df кода является весовым коэффициентом Хэмминга члена наименьшего порядка разложения T(D). В данном случае df=5. Для оценки пространственных характеристик при большой длине кодового ограничения передаточную функцию T(D) использовать нельзя, поскольку сложность T(D) растет с увеличением длины кодового ограничения как степенная функция.

Рис. 7.17. Диаграмма состояний с обозначенными расстояниями до нулевого пути

С помощью передаточной функции можно получить более подробную информацию, чем при использовании лишь расстояния между различными путями. В каждую ветвь диаграммы состояний введем множитель L так, чтобы показатель L мог служить счетчиком ветвей в любом пути из состояния а = 00 в состояние е = 00. Более того, мы можем ввести множитель N во все ветви переходов, порожденных входной двоичной единицей. Таким образом, после прохождения ветви суммарный множитель N возрастает на единицу, только если этот переход ветви вызван входной битовой единицей. Для сверточного кода, описанного на рис. 7.3, на перестроенной диаграмме состояний (рис. 7.18) показаны дополнительные множители L и N. Уравнения (7.12) теперь можно переписать следующим образом.

                                        (7.14)

                                           

Передаточная функция такой доработанной диаграммы состояний будет следующей.

(7.15)

Таким образом, мы можем проверить некоторые свойства путей, показанные на рис. 7.16. Существует один путь с расстоянием 5 и длиной 3, который отличается от нулевого пути одним входным битом. Имеется два пути с расстоянием 6, один из них имеет длину 4, другой — длину 5, и оба отличаются от нулевого пути двумя входными битами. Также есть пути с расстоянием 7, из которых один имеет длину 5, два — длину 6 и один — длину 7; все четыре пути соответствуют входной последовательности, которая отличается от нулевого пути тремя входными битами. Следовательно, если нулевой путь является правильным и шум приводит к тому, что мы выбираем один из неправильных путей, то в итоге получится три битовые ошибки.

Рис. 7.18. Диаграмма   состояний   с   обозначением расстояния, длины и числа входных единиц

7.4.1.1. Возможности сверточного кода в коррекции ошибок

В главе 6 при изучении блочных кодов говорилось, что способность кода к коррекции ошибок, t, представляет собой количество ошибочных кодовых символов, которые можно исправить в каждом блоке кода путем декодирования по методу максимального правдоподобия. В то же время при декодировании сверточных кодов способность кода к коррекции ошибок нельзя сформулировать так лаконично. Из уравнения (7.11) можно сказать, что при декодировании по принципу максимального правдоподобия код способен исправить t ошибок в пределах нескольких длин кодового ограничения, причем "несколько" — это где-то от 3 до 5. Точное значение длины зависит от распределения ошибок. Для конкретного кода и ошибочной комбинации длину можно ограничить с использованием методов передаточной функции. Такое ограничение будет описано позднее.



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.