Главная > Теория информаци и связи > Помехоустойчивость и эффективность систем передачи информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3. ПОМЕХОУСТОЙЧИВОСТЬ ДЕКОДИРОВАНИЯ СВЕРТОЧНЫХ КОДОВ

Оверточный код является групповым (все возможные кодовые последовательности образуют группу по сложению), что позволяет рассматривать свойства кода, используя в качестве исходной любую из кодовых последовательностей. Удобно в качестве исходной считать последовательность из одних снулей, которая генерируется кодером при поступлении на его вход также нулевой информационной последовательности. Тогда все множество разрешенных путей, выходящих из нулевого состояния и возвращающихся в него, может быть описано порождающей функцией. Расчленив диаграмму состояний (см. рис. 3.2,а) в узле перейдем к модифицированной диаграмме. Она имеет вид, показанный на рис. При этом удобно ветви диаграммы маркировать формальными переменными Показатель степени при переменной равен весу (количеству единиц) соответствующего перехода между состояниями. Например, при переходе из состояния 00 в состояние 10 кодер генерирует пару символов 11, вес которой равен 2. Показатель переменной равен числу единиц, поступающих на вход кодера при выполнении данного перехода. При поступлении на вход кодера символа 0 показатель Переменная входит обозначение каждой ветви и используется для определения числа шагов по диаграмме. Порождающая функция для простейших кодов может быть найдена путем алгебраических вычислений [33]. В частности, для кодера, представленного на рис. 3.1, а порождающая функция имеет вид

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

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

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

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

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

При достаточно малом уровне шума в канале ошибочные события происходят редко. В этом случае, как и при вычислении вероятности ошибки при приеме многопозиционных сигналов, можно воспользоваться правилом сложения вероятностей (см. § 2.2). Результирующая вероятность ошибки ограничена сверху суммой вероятностей различных ошибочных событий:

Перечисление параметров всех возможных ошибочных событий содержится в выражении для порождающей функции кода. Подставив в выражение для порождающей функции (3.11) значение 1, получим

Производная функция по при

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

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

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

Компактным описанием диаграммы состояний является матрица смежностей общий член которой равен весу ветви выходящей из узла и входящей в узел. Если ветви между узлами нет, 0. Матрица смежностей диаграммы, показанной на рис. имеет вид

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

представляющий собой набор весов путей длиной в ветвей, ведущих из начального узла решетчатой диаграммы 50 (см. рис. 3.3) в каждый из узлов — число узлов). Начальное состояние вектора .

Для получения вектора порядка справедливо выражение

где матрица смежностей. Соответственно каждый элемент нового вектора

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

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

Здесь число ошибочных путей с одинаковым весом вес информационной последовательности, соответствующей ошибочному пути веса

Вычисляя производную порождающей функции (3.21), получаем

Как видно из сравнения выражений (3.14) и (3.22), набор коэффициентов при различных и определяет спектр весов сверточного кода.

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

с законом перфорации. В частности, при использовании кода (7,5) в качестве исходного и перфорации с целью получения кода со скоростью матрицы смежностей на неперфорированном и перфорированном шагах диаграммы (см. рис. 3.4, б) будут иметь вид:

В табл. 3.2 приведены также примеры спектров оптимальных кодов по критерию максимума на скорость и 3/4, найденных в работе [82]. Порождающие матрицы этих кодов, обозначенных как приведены в [58]. Сравнение оптимальных кодов с перфорированными позволяет сделать вывод о том, что перфорированные коды характеризуются несколько худшим спектром весов, а в некоторых случаях и меньшим свободным расстоянием.

Таблица 3.2 (см. скан)

Например, при скорости кода свободное расстояние кода составляет тогда как свободное расстояние кода

При известном спектре весов верхняя граница вероятности ошибки на бит на выходе декодера может быть определена по формуле (3.15). Вероятность выбора ошибочного пути веса зависит от того, в каком канале производится декодирование. Если ошибочный путь на решетчатой диаграмме отличается от

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

Здесь вероятность ошибки в канале с определяемая по формуле (3.10).

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

Таким образом, расчет вероятности ошибки на бит на выходе декодера максимального правдоподобия сводится к вычислению спектра весов в соответствии с выражением (3.22), расчету вероятностей ошибочного выбора пути по формулам (3-23) либо (3.24) для жесткого либо гибкого решения и к последующим вычислениям по формуле

Как видно из данных табл. 3.2, составляющие спектра С с ростом возрастают. В то же время значения вероятностей убывают, так что вклад последующих членов в сумму ряда с ростом убывает. Обычно достаточным оказывается вычисление первых пяти членов ряда (3.25), если вероятность

Результаты расчетов вероятности ошибки в зависимости от энергетических затрат для различных кодов при декодировании с гибким решением показаны на рис. 3.6. Параметры кодов приведены в табл. 3.3. Рассмотрены лучшие из известных коротких сверточных кодов, предназначенных для декодирования по

алгоритму Витерби. Коды со скоростями (№ 1—9) — оптимальные по критерию максимального свободного расстояния Оптимальными по критерию являются также коды со скоростью . Оптимальные неперфорированные коды со скоростями 2/3 и 3/4 типа (№ 22, 26, 30, 33, 36, 40 и 42) выбраны по рекомендациям работы [82], Различные варианты перфорированных кодов рассмотрены в работах [83...85].

Рис. 3.6. (см. скан) Характеристики помехоустойчивости сверточных кодов

(см. скан)

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

Приведенные на рис. 3.6 данные позволяют оценить возможности построения универсальных кодеков на скоростях (либо с другими вариантами скоростей), когда для работы на различных скоростях используют один «набор кодовых генераторов. К примеру, код № 14 (31,33) с обеспечивает близкий к максимальному при таких параметрах Перфорация этого кода при скоростях (коды № 29 и 37) обеспечивает и соответственно. Другой вариант исходного кода № 13 с такими же параметрами обеспечивает на скорости меньший предельного однако при он выше, чем у кода № 14 и составляет соответственно и Таким образом, выбор варианта кода для работы на различных скоростях зависит от условий конкретной задачи. В табл. 3.4 показаны оптимальные варианты перфорации, параметры кода и значения ЭВК, когда исходным является широко используемый код (133,171),


Таблица 3.4 (см. скан)

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

Расчеты вероятности ошибки по формуле (3.25) производились в предположении, что прослеживание «выживших» путей при декодировании по решетчатой диаграмме не ограничено конечной длиной памяти декодера. Подробные исследования снижения при ограничении длины прослеживаемых путей в памяти декодера, в частности при декодировании перфорированных кодов, выполнены в работе [84]. Показано, что при декодировании кодов скорость достаточным является объем памяти что совпадает с рекомендацией [33]. Для декодирования перфорированных кодов без существенных потерь ЭВК объем памяти декодера должен быть увеличен до при при — длина регистра кодера).

В заключение этого параграфа приведем основные данные по величине энергетического выигрыша, получаемого при декодировании достаточно длинных сверточных кодов с использованием многопорогового алгоритма. Предполагается, что демодулятор в этом случае обеспечивает жесткое решение [78» 79]. Параметры кодов сведены в табл. 3.5, Здесь же для сравнения показан при декодировании коротких сверточных кодов алгоритмом Витерби с гибким решением Здесь число ступеней решения (порогов) многопорогового алгоритма; старшая степень порождающего многочлена сверточного кода. Из приведенных данных следует, что оптимизация процедуры порогового декодирования позволяет получить энергетический выигрыш, соизмеримый с выигрышем при оптимальных методах декодирования при малых ошибках на выходе декодера. В области многопороговые декодеры значительно уступают оптимальным и выигрыша практически не дают.

Таблица 3.5 (см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление