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

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

три порождающих многочлена G

(1)

(x)=x

, G

(2)

(x)=x

, G

(3)

(x)=x

, то

структурная схема кодера ДФСК имеет вид(рис. 6.14):

Рис. 6.14. Структурная схема кодера ДФСК

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

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

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

как передаваемый информационный символ. В результате с выходов кодера

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

Процесс формирования проверочной последовательности Т

(3)

(х)

иллюстрируется таблицей 6.3

Таблица 6.3. Последовательность формирования проверочной

последовательности ДФСК с R=2/3

№

n n

(1)

(x)

(2)

(x)

Состояние ячеек

памяти регистра

кодера

(1)

(x)

(2)

(x)

(3)

(x)

0 1 1 0

1 1 0

1 0 1 1

0 1 1

2 1 0 0

1 0 0

3 0 0 1

0 0 0

4 1 1 0

1 1 1

5 1 0 1

1 0 0

6 0 1 1

0 1 0

7 0 1 0

0 1 1

8 1 0 0

1 0 1

9 0 0 1

0 0 0

10 1 0 0

1 0 1

11 1 0 1

1 0 1

12 1 0 1

1 0 0

13 1 1 1

1 1 1

14 0 0 1

1 0 1

15 0 0 1

1 0 0

… … …

…

… … …

(x),I(x)T(x),I(x)T

(2)(2)(1)(1)

].x(x)]/[1I)x(x(x)Ix)[(x(x)T

4(2)6(1)2(3)

+⋅++⋅+=

(1)

(x)

(2)

(x)

(1)

(x)

(2)

(x)

(3)

(x)

В декодере по принятым информационным символам вновь формируются

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

последовательность S(x):

или с использованием порождающих полиномов

Вычисленные синдромные символы S(x) записываются в регистр сдвига БАС

Структурная схема порогового декодера ДФСК с R=2/3 приведена на рис.6.15.

Рис. 6.15. Структурная схема порогового декодера ДФСК с R=2/3

Для последовательности шумовых символов E

(i)

(1)

(2)

(3)

1(1)

…

последовательность синдромных символов равна:

∑

⊕⋅=

(3)(i)(i)

(x)T(x)G(x)TS(x)

K(x)E)x(1(x)E)xx(1(x)E)x(1xS(x)

(3)4(2)2(1)62

⋅+⊕⋅+⊕⋅+=

(1)

(x)

БАС

T’

(1)

(x)

T’

(2)

(x)

T’

(3)

(x)

(2)

(x)

(i)

(3)

(2)

(1)

(2)

(3)

(1)

Отсюда следует, что синдромные символы имеют определенный интервал

перемежения, который носит название коэффициента диффузности кода. Кроме

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

только от числа ошибок в информационных символах и очень слабо зависит от

количества ошибок в проверочных символах. Так как кратность корректируемого

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

символов (р = x

– х

, j=l,2,. .,b=t

) каждого потока, то кратность корректируемых

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

показателями степеней порождающих полиномов, т.е. t

= x

- х

, k>н. Таким

образом, корректирующая способность ДФСК с алгоритмом ПД зависит как от

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

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

полиномов ДФСК. С целью повышения корректирующей способности ДФСК

возможно использование мягкого решения.

6.5. Вероятностное декодирование сверточных кодов

6.5.1. Декодер Витерби

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

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

максимальному правдоподобию. Такой же вывод справедлив и для СК. Если

обратиться к кодовому дереву СК с R=l/2 и k=2 (рис. 6.6), то можно заметить, что

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

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

кодового слова в наименьшем числе позиций. При передаче информации по

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

декодирование по минимуму расстояния. Декодер, реализующий декодирование

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

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

окажется ближайшим к принятому.

Реализация декодера СК по минимуму расстояния связана с существенными

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

декодирования СК, то реализация декодера СК упрощается за счет удаления

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

декодирования СК алгоритм Витерби является наиболее эффективным[1…3].

Алгоритм Витерби базируется на методах теории динамического

программирования и достаточно просто реализуется для двоичных СК с длиной

кодового ограничения k'≤7 и R=l/2, обеспечивая энергетический выигрыш

порядка 6дБ при Р

/Р

=10дБ, использовании ДФМ, и мягкого декодирования с

Q=8.

Как отмечалось в разделе 6.3 увеличение числа ячеек памяти RG кодера

приводит к экспоненциальному росту числа кодовых путей. Последовательное

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

путей, сколько их увеличилось после перехода к новой величине кодового

дерева(узла). Благодаря этому имеется возможность уравнять число вновь

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

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

путей[1..3].

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

диаграммы СК сравнивается n

путей, входящих в один узел. При этом

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

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

называются выжившими путями[3].

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

равным трем ячейкам памяти (к'=3) и свободным кодовым расстоянием d

св

=5.

Предположим, что на вход кодера СК поступила нулевая информационная

последовательность I(х)=000…00... .Следовательно, выходная кодовая

последовательность также будет нулевой: Т(х)=..0000..…000.. Пусть принятая

последовательность имеет вид Т’ (х)=..100010000..., т.е. содержит два ошибочных

символа (две ошибки на первой и пятой позициях кодовой последовательности),

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

св

=5. Далее

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

жесткое решение (с выхода демодулятора на вход декодера СК поступают

двоичные символы). В этом случае в качестве веса можно использовать

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

решетчатой диаграммы.

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

диаграмм, фиксирующих состояния декодера СК после обработки каждой

следующей ветви.(рис 6.16)[3].

Десятичные цифры, представленные в соответствующих узлах решетки,

указывают расстояние Хэмминга, накопленное "выжившим" путем в этом узле.

На уровне 2 решетки (рис 6.7) произошла только одна из двух ошибок; выжившие

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

На уровне 3 каждый из путей с уровня 2 расходятся(рис. 6.16.а), так что

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

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

пары сохраняется лишь "лучший путь", так что общее число путей вновь

становится равный четырем. Этот процесс повторяется при каждом приеме

любого ребра. Заметим, что на уровне 5 (рис. 6.16.в) вес нулевого пути выше, чем

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

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

Из данного примера видно, что выживающие пути можно отличать друг от

друга в течении многих тактов. Однако на уровне 10 (рис. 6.16.д) первые 8 ребер

всех выживших путей совпадают друг с другом. В этот момент времени алгоритм

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

приходят из одной вершины, т. е. соответствуют одному информационному сим-

волу.

Глубина (количество тактов), на котором происходит такое слияние, не

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

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

реализации декодера Витерби не следует ожидать указанного слияния, а нужно

установить фиксированную глубину декодирования. Каждый раз при обработке

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

Рис.6.16. Траектории выживших путей и их веса

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

Однако для уменьшения сложности вычислений и реализации декодера Витерби

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

последовательность с неисправляемой комбинацией ошибок Т'(х)=1101000... В

этом случае имеются три неполные решетчатые диаграммы (рис.6.17)[3].

Из приведенных фрагментов решетчатых диаграмм видно, что на уровне 3

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

неизбежно. Кроме того, выжившие пути имеют одно и тоже первое ребро. На

уровне 5 (рис.6.17.б) все выжившие пути имеют одинаковые первые два ребра, а

на уровне 9 (рис.6.17.в) у всех выживших путей совпадают девять ребер.

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

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

состоящего всего лишь из трех ребер. В действительности же информационная

последовательность соответствующая этому пути, имеет вид 100000..., так что

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

характеризует типичное поведение декодера Витерби. Ошибочное декодирование

влияет на сравнительно небольшую длину последовательности (несколько длин

кодового ограничения ) и приводит к коротким пакетам ошибок.

Рис.6.17. Траектории кодовых путей с использованием неполных

решетчатых диаграмм

Таким образом , рассмотренный пример показывает, что декодер Витерби

реализует выполнение следующих операций над принятыми символами[2,3]:

1) для каждого кодового блока n

, соответствующего k

входным

информационным символам, вычисляются веса ветвей; такая операция

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

кодовых

символов. Таким образом, все ветви (ребра) решетчатой диаграммы - путь

каждого шага декодирования;

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

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

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

все пути с большими значениями весов. Это обеспечивает уменьшение объема

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

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

наименьшим весом . Данный путь считается "выжившим путем";

4) приписывается узлу вес "выжившего пути";

5) в память путей записывается "выжившие пути";

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

который имеет наименьший вес.

Вес пути и соответствующая ему информационная последовательность

состоит из весов получаемых на отдельных тактах. В конце вычислений в

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

декодер Витерби позволяет на длине (4..7)⋅k тактов вычислить расстояние

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

последовательностью, выбрать наиболее правдоподобный путь и на основе этого

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

На рис.6.18 и рис.6.19 представлены соответственно структурная схема

декодера Витерби и блок-сxeмa алгоритма работы декодера Витерби.

Для правильного разделения принятой входной последовательности

символов на подпотоки C

(x) и C

(x), соответствующие символам первого потока

(x) и второго потока Т

(х), вводится устройство ветвевой синхронизации (УВС).

Блок фазовой автоподстройки частоты (ФАПЧ) декодера предназначен для

формирования тактовых частот f

...f

, необходимых для функционирования

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

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

символами

решетчатой диаграммы или состояниями кодера СК.

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

из n

символов выполнятся 2

операций. Так как в каждый узел решетчатой

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

ребер, то для определения

веса каждого ребра необходимо иметь 2

⋅log

⋅n

двоичных символов. Блок

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

Рис. 6.18. Структурная схема декодера Витерби( УВС – устройство ветвевой

синхронизации, РУ – решающее устройство, ФАПЧ – фазовая

автоподстройка частоты)

Рис. 6.19. Блок-схема алгоритма работы декодера Витерби

РУ

ФАПЧ

Декод

е-

УВС

Блок

вычисления

весов

Блок обновл

е-

ния и хранения

весов

Блок обновления и хране-

ния информационных по-

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

Т1

Т2

Т3

Т4

Т5

T(x)

(x)

Вых.

I(x)

(x)

Для всех 2

узлов производится отбор путей с наи-

меньшим весом(выбор выживших путей)

Вычисление расстояний миниблоков на длине n

Вычисление всех 2

путей, ведущих к данному узлу

Хранение выживших путей

Выбор выжившего пути с наименьшим расстоянием

Выдач

а информации

Вычисленные значения весов ребер поступают в блок вычисления и

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

СК. Для этого к расстоянию, которое было определено на предыдущем такте,

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

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

шаге декодирования. По окончании вычисления весов путей для всех

анализируемых (конкурирующих) путей выбирается путь с наименьшим

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

низкоскоростных (R<1/2) и высокоскоростных (R>1/2) СК различаются. Это

связано с тем, что при использовании СК с R>1/2 увеличивается число узлов

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

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

процессоре.

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

выжившего пути поступают на вход блока обновления и хранения

последовательности. Данный блок декодера осуществляет формирование

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

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

решения о номере состояния в двоичном коде, из которого ранее вышел

декодируемый путь. Отметим, что на реализацию данного блока декодера

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

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

декодирования, равной L

ветвей, объем запоминающего устройства (буфера)

должен обеспечивать хранение информации (3…10)⋅L

множеств ветвей, как уже

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

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

⋅log

⋅n

двоичных символов. Кроме того, при высокой скорости передачи

информации необходимо построение памяти с обеспечением возможности

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