Королёв А.И. Коды и устройства помехоустойчивого кодирования

Подождите немного. Документ загружается.

обращении к памяти блока, что требует применения эффективных способов

обновления путей

Сформированные в результате декодирования символы информационных

последовательностей поступают на вход выходного решающего устройства (РУ)

декодера, в котором принимается окончательное решение о каждом принятом

информационном символе (как правило, РУ - это мажоритарный элемент). С

выхода решающего устройства информационные символы одновременно

поступают на вход устройства и на соответствующий вход устройства ветвевой

синхронизации.

Существенным недостатком декодера Витерби с R=l/2 является высокая

избыточность. С целью устранения этого недостатка предложен способ

перфорации для получения высокоскоростных CK(c R≥2/3).

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

В перфорированных СК удаляются некоторые кодовые символы,

образующие несущественные связи в кодовой решетке, формируемые при

кодировании информации. Исключенные символы не передаются в канал связи,

что приводит к увеличению скорости передачи СК. Структурная схема декодера

СК с устройствами перфорации и деперфорации(восстановления) кодовых

символов и соответствующие временные диаграммы для перфорированного СК с

R=2/3, построенного на основе СК с R=l/2 и с длиной регистра сдвига равного

трем (k'=3) ячейкам памяти, представлены соответственно на рис.6.20 и 6.21.

Анализ временных диаграмм перфоратора показывает, что каждый четвертый

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

перфорированный СК будет иметь три кодовых символа на два входных

информационных символа и поэтому скорость передачи перфорированного СК

увеличивается до R=2/3.

Практические выгоды от использования перфорированных СК состоит в

уменьшении сложности реализации высокоскоростных декодеров с R≥2/3. Так,

для перфорированного СК с R=2/3 выигрыш в уменьшении сложности реализации

декодера равен (2

-1)/( n

-1) на каждый декодированный символ по сравнению с

реализацией неперфорированного СК с R=2/3.

Рис. 6.20. Структурная схема кодера перфорированного СК

На решетчатой диаграмме перфорированного СК (рис. 6.22) звездочкой

обозначены удаленные кодовые символы. Переходы между узлами решетчатой

диаграммы, соответствующие переданным информационным символам

перфорированного СК с R=2/3 и исходного СК с R=l/2, совпадают.

Однако такой переход между узлами решетчатой диаграммы

перфорированного СК совершается через множество промежуточных состояний,

т.к. кодовые символы поступают в декодер по одному, а не парами.

Puc.6.21. Временные диаграммы перфорированного СК

(x)

Деперфоратор кодовых символов

• ФАП

ФПС

I(x)

T’(x)

T’’(x)

(x)

Перфоратор кодовых символов

(x)

T’

(x)

T’

(x)

T’

(x)

Рис. 6.22. Решетчатая диаграмма перфорированного СК

Лучшими перфорированными СК считаются коды, которые в двоичном

симметричном канале без памяти обеспечивают более высокий энергетический

выигрыш кодирования при равных параметрах данных кодов.

Асимптотическая вероятность ошибочного декодирования перфорированных

СК задается соотношением[3]:

где d

= d

св

– свободное расстояние кода,

) - полный входной вес по всем информационным

последовательностям, которые приводят к пути на кодовом дереве

веса d

На рис. 6.23 представлены кривые вероятности ошибочного декодирования

перфорированного СК с R=2/3 рассчитанные по формуле 6.18.

Анализ длин зависимостей показывает, что энергетический выигрыш в

диапазоне Р

/Р

= (3...10) дБ на (0,1... 0,25) дБ меньше энергетического выигрыша

неперфорированного СК с такими же параметрами (пунктирные кривые на

рис.6.23). Однако затраты на реализацию декодера перфорированного СК с

алгоритмом Витерби в (1,5... 12) раз меньше соответственно, чем

)(dW

1)(nd

)(dW

0ξ

ξi

ξξi













⋅⋅⋅=













⋅

−

⋅

−

≈

(6.18)

неперфорированного.

Рис. 6.23. Вероятность ошибочного декодирования перфорированного СК с

R=2/3; 1 – потенциальная помехоустойчивость ДФМ

6.5.3. Последовательное вероятностное декодирование сверточных кодов

Увеличение энергетического выигрыша алгоритма Витерби, как отмечалось в

разделе 6.5.1 возможно лишь с увеличением длины кодового ограничения и

использования мягкого решения на выходе канала. Однако реализация декодера

Витерби уже при длине кодового ограничения k'>11 практически неприемлемо

ввиду высокой сложности реализации. Для больших длин кодового ограничения

разработаны последовательные алгоритмы декодирования СК, которые не

учитывают маловероятные пути на кодовой решетке. Однако данные кодовые

пути не исключаются полностью или окончательно из алгоритма декодирования.

Впервые последовательный алгоритм декодирования СК был предложен

Возенкрафтом Дж. и развит Р.Фано, К.Зигангировым и др.

Последовательное декодирование СК по своим корректирующим свойствам

приближается к характеристикам декодирования по максимуму правдоподобия и

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

3 4 5 6 7 8 9 10

, дБ

ош

, дек.

1 2

бк

количество операций зависит от уровня мощности шумов Р

: чем меньше Р

, тем

меньшее количество операций требуется. Это позволяет упростить реализацию

декодера.

Сущность последовательного декодирования СК состоит в соответствующем

определении пути по кодовой решетке: прослеживается лишь тот кодовый путь,

который "показался" декодеру наиболее вероятным. Поскольку время поиска

кодового пути ограничено, то нельзя быть уверенным, что данный кодовый путь

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

рассматривать как метод проб и ошибок. Последовательный декодер, в отличие от

декодера Витерби, анализирует в каждом узле кодовой решетки только один блок

, т.е. на каждом уровне кодового дерева последовательный декодер выбирает

ребро кодового дерева, ближайшее к принятому кадру кодовой

последовательности и переходит в узел на следующем уровне кодового дерева.

Если ошибки в принятой последовательности отсутствуют, то алгоритм

декодирования реализуется эффективно. Однако при наличии ошибок в принятой

последовательности декодер с определенной вероятностью ошибки может

выбрать неправильное ребро или кодовый путь в целом. Продолжая следовать по

неверному кодовому пути декодер может это обнаружить по увеличению

количества ошибок декодирования. В этом случае декодер возвращается назад на

несколько кодовых блоков n

и заново исследует другие кодовые пути до тех пор,

пока не обнаружит правдоподобный путь и в дальнейшем будет следовать вдоль

этого пути. Следовательно, последовательный декодер анализирует кодовые пути

с разной скоростью и поэтому неравномерно будет выдавать на выходе

информационные символы.

Неравномерное декодирование информации (движение декодера вперед-

назад, приостановка выдачи информационных символов на сложных участках

кодового дерева) возможно только при большом объеме вычислений и высоком

быстродействии декодера, что накладывает определенные ограничения на

параметры СК.

Важнейшим параметром последовательного декодера СК является вес

кодового ребра, значение которого служит указанием декодеру , верными ли были

предыдущие решения. Вес кодового ребра в некоторой вершине i кодового дерева

СК определяется следующей формулой [2,3]:

где t

– переданный информационный символ;

– принятый кодовый символ;

Ф – параметр смещения или окно декодирования.

Вес кодового пути в вершине i кодового дерева СК равен:

Параметр смещения измеряется числом блоков принятой последовательности

и определятся таким образом, чтобы значение веса λ

кодового пути возрастало

при правильном принятии решения.

Типичное поведение веса кодового пути при последовательном

декодировании СК представлено на рис. 6.24.

Рис.6.24. Кодовые пути последовательного декодера СК

Из рис.6.24 видно, что вес правильного кодового пути может время от

времени сильно уменьшаться (↓*). Однако общей тенденцией веса на больших

∑





















−













,Ф

)P(r

)tP(r

logλ

∑

λL

-L

∆

Правильный кодовый

путь

Неправильный кодовый

путь

↓

↓**

временных интервалах является ее увеличение. Вес неправильного кодового пути

под воздействием сильных помех также может возрастать и сделать

неправильный кодовый путь похожим, на правильный, но с уменьшением уровня

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

Для обнаружения ситуации увеличения или уменьшения веса кодового пути

в последовательном декодере используется переменный порог (П), который

может быть увеличен или уменьшен на некоторую величину ∆, называемую

приращением порога. Если в процессе декодирования метрика текущего кодового

пути становится меньше порога П, то в декодере вырабатывается команда -

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

следовательно, необходимо организовать поиск верного кодового пути.

Критерием близости пути на кодовом дереве к принятой последовательности

является расстояние Хемминга между ними; если расстояние Хемминга между

последовательностями длины N не превышает выбранный порог П, то кодовые

последовательности можно считать совпадающими. При передаче информации по

двоично-симетричному каналу порог П выбирается таким образом, чтобы

вероятность между переданной и принятой последовательностями была больше,

чем порог П и не превышала величины 2

-L

, где L - некоторая заданная постоянная

величина. При этом вероятность ошибочного декодирования должна быть меньше

допустимой вероятности ошибочного приема информации.

В канале без памяти с вероятностью ошибочного приема двоичного символа

, расстояние Хемминга, вычисляемое вдоль верного кодового пути, почти

всегда будет расти со скоростью Р

вместе с количеством обработанных

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

скоростью 0,5. Различные пути кодового дерева отличаются друг от друга

приблизительно в половине кодовых символов. Таким образом, расстояния

Хемминга, вычисленные вдоль верного и ложного кодового пути кодового дерева,

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

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

который будет обнаружен через определенное время.

Рассмотрим в качестве примера последовательный декодер Фано на основе

запоминающего устройства (рис.6.25).

Принятые кодовые символы разделяются на поток информационных

символов I

(i)

( х ) и поток проверочных символов Р' (x). Сформированные

синдромные символы S(х) = Р'(х)⊕Р

сф

(х) поступают на вход буфера декодера.

Принятые информационные символы поступают на вход ЗУ, выполняющего

функции входного буфера, где задерживаются на время определяемое временем

обработки синдромных символов в буфере декодера (ОЗУ) центрального

процессора. По мере необходимости синдромные символы S(х) извлекаются из

ОЗУ центральным процессором и поступают в блок регистров синдромов S(х).

Центральный процессор декодера содержит оперативную память достаточного

объема, позволяющего избежать избыточных обращений к ОЗУ. Каждый

синдромный символ S(х) извлекается из ОЗУ один раз и позднее заменяется

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

процессором - при возвращении назад все эти данные содержатся в памяти

центрального процессора. Память процессора имеет такой объем, позволяющий

вместить все предыдущие пробные решения для кодовых символов,

расположенных примерно на пять длин кодового ограничения. Глубину

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

поиска. Таким образом, в процессоре предусматривается хранение символов S(x),

(i)

(х) и E

(s)

(х) - символов коррекции синдрома.

В регистре синдромов S(х) содержатся последующие символы синдрома, на

основе которых формируются символы коррекции ошибок. После декодирования

вперед по кодовому дереву символы регистра синдромов S(х) сдвигаются вправо.

Символы последовательности ошибок записываются в устройства хранения Е

(i)

(х)

и Е

(s)

(х). Используя содержимое регистра синдромов S(х), центральный

процессор формирует и выдает оценки для ошибок. Коррекция информационных

символов осуществляется путем суммирования по модулю два I

(i)

(х) и Е

(s)

(х).

Рис. 6.25. Структурная схема последовательного декодера Фано

При движении назад по кодовому дереву последние символы

последовательностей Е

(i)

(х) и Е

(s)

(х) используются для того, чтобы восстановить

содержимое регистра синдромов S(x) таким, каким оно было до принятия

пробного решения; при этом символы синдрома записываются в ОЗУ для их

хранения Е

(s)

(х)/S(x).

После того, как декодер вновь начнет двигаться вперед, эти символы

синдрома возвращаются в регистр синдромов S(x) и ОЗУ для определения

отношения Е

(s)

(х)/S(х).

Таким образом, в последовательном декодере Фано должны реализоваться

следующие операции:

1) не должен двигаться вперед-назад по пути, лежащему ниже текущего

Центральный процессор

сф

(x)

Кодер СК ЗУ

М2

Буфер декодера

(ОЗУ)

P’(x)

(i)

(x)

(i)

(x)

Вых I(x)

Параллельный

или последова-

тельный буфер

Хранение

(i)

(x)

Хранение

(x)/s(x)

Регистр си

н-

дромов S(x)

Устройство

управления

I’(x)

ФССs(x)

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

двигаться назад по кодовому дереву без пересечения значения текущего порога

при этом оценивает все кодовые пути, которые не были рассмотрены с текущим

значением порога;

2) если ни один из кодовых путей не удовлетворяет текущему значению

порога, то порог уменьшается на величину приращения порога ∆ и декодер вновь

пытается двигаться вперед по кодовому дереву;

3) при движении вперед по кодовому дереву декодер анализирует наиболее

вероятный кодовый путь, исходящий из данной вершины узла, а при движении

назад осуществляет переход в предшествующую вершину кодового дерева.

Движение декодера в сторону по кодовому дереву означает переход в вершину,

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

являющуюся следующей за данной, при упорядочении вершин кодового дерева

по их правдоподобию.

Реализация отмеченных правил последовательного декодирования СК

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

объем оборудования декодера и минимальную вероятность ошибочного

декодирования. Сложность реализации алгоритма последовательного

декодирования существенно увеличивается с увеличением скорости передачи

кода, количество ячеек памяти регистра сдвига и скорости передачи информации.

6.6. Сверточные коды в сигнально-кодовых конструкциях

Большинство современных дискретных каналов связи относятся к каналам

имеющим ограничения по частоте и мощности передаваемых сигналов. Это

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

необходимостью увеличения скорости передачи информации от источника и,

следовательно, приводит к расширению спектра передаваемых частот

(уменьшению длительности бита) и соответственно полосы частот. Если полосу

частот канала расширить невозможно (∆F

= const), то увеличение скорости