Вернер М. Основы кодирования

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

4-6. Декодирования по максимуму правдоподобия 253,

При

передаче информации противоположными сигналами

по ка-

налу

АБГШ

приеме

помощью согласованных фильтров исполь-

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

на

рис.

4.22 (см.

Часть

раздел

7.5.2).

Согласно

рис. 4.22,

отдельный

бит

кодового слова

«1» или «О»

после передачи

но

каналу

без

шума

детектирования

принимает аналоговое значение

го или

—

TQ.

Из-за наличия шума

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

г на

выходе

приемника является

непрерывной стохастической переменной

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

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

/(г/1)

/(г/0)

/(г/1)

Рис.

4.22.

Условные плотности распределения

вероятно-

стей

продетектированного сигнала

г при

пере-

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

по

каналу

АБГШ.

"(4.75)

/27ГО2

Замечание.

Значения

Г(,

и <т

зависят

от

канала

передачи

инфор-

мации.

Приведенные

примере

рассуждения

можно

обобщить

и на

случай

М-ичных

сигналов

использовать

там

аналогичную

мет-

рику.

Будем предполагать,

что «1» и «О»

передаются независимо

друг

от

друга

вероятностями, равными

1/2.

Канал

АБГШ также

яв-

ляется каналом

без

памяти, поэтому,

для

декодера максимального

правдоподобия приращение метрики можно определить

как

logPirj/vj) = log

exp (_

(4.76)

,254 Глава 4-

Сверточные

коды

где +го при Vj = 0 и —го при Vj = О. Выражение

(4.76)

можно

упростить

log

P{rj/vj)

= -

(Г

^' log e - - log 27ГС7

(4.77)

Так

как для декодера МП все константы несущественны, их мож-

но

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

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

между

нродетек-

тированным сигналом г и значениями ±го

(rj/vj)

—

(г ± го)

(4-78)

Можно

произвести дальнейшие упрощения. Из

(г

± го) = г

± 2гг

+ г

(4.79)

следует,

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

•

(4-80)

+Г

ДЛЯ Vj = 1

Таким

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

ко

учитывать знак переменной г.

Заметим, что метрика декодера является непрерывной величи-

ной.

В этом

случае

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

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

ется на два уровня «0» и «1». Ниже приводится пример практиче-

ской

реализации декодера Витерби с мягким решением, при этом, в

частности, учитывается сложность реализации. Во многих практи-

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

повышенные

требования к стоимости декодера. Очень часто деко-

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

схему,

размещенную в одном

чипе.

Важную

роль играют так же надежность в эксплуатации и ми-

нимальная

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

требованиями, разработчики декодеров стремяться минимизировать

их сложность с минимальными потерями эффективности, при этом,

особую

роль играют целочисленное представление метрики и про-

стота арифметических операций декодирования.

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

решения.

Во многих применениях достигнут разумных компромисс

между

сложностью декодера Витерби с мягким решением и мини-

мальной мощностью принимаемого сигнала.

4-6.

Декодирования

по

максимуму

правдоподобия

255^

Пример:

Декодер Витерби с мягким решением для канала с

АБГШ.

/(г/0)

-го

Рис.

4.23. Квантование принятого сигнала.

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

символов «О» и «1» передается по каналу с АБГШ. В этом случае

на

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

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

условных вероятностей /(г/0) и /(г/1) (рис. 4.23). Вместо жестко-

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

уровня, рассмотрим реализацию декодером простейшего мягкого ре-

шения.

При таком решении на

вход

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

дового слова «О» и «1», имеющие длину, равную двум битам. Такая

информация

соответствует 4 уровням квантования текущих значе-

ний

переменной г (см. рис. 4.23). Дополнительный двоичный разряд

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

«плохие»

би-

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

имеет положительное значение, очень близкое к нулю, то вероят-

ность «1» лишь немного превышает вероятность «О». В этом случае

имеет смысл говорить о «ненадежной» или

«плохой»

единице. Если

значение г превышает г

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

утверждать, что была принята единица.

Замечание.

Интервалы

квантования

переменной

были

выбраны

интуитивно, для

того,

чтобы

продемонстрировать

реализацию

де-

кодера

Витерби

с мягким

решением.

При

мягком решении с минимальными техническими затрата-

ми

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

4.7. В этом случае текущее значение метрики рассматриваемого пути

^256

Глава

Свершенные

коды

Таблица 4.7. Таблица приращений метрик.

Принятый

символ

00 —Од

01 —

ОЬ

10— 1Ь

11 — 1д

Приращение

метрики Коментарий

«хороший»

ноль

«плохой»

ноль

«плохая»

единица

«хорошая»

единица

будет

складываться с некоторым целым числом из интервала ]0,3[.

Выбор этого числа зависит от уровня квантования, в который по-

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

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

•6

\ •/

111

^ /

111

ООН

6 Такт

Рис.

4.24. Декодирование с помощью алгоритма Витерби

с мягким решением.

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

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

на

компьютере канала с г

= 1 и а

= 1/2 и сведены в таблицу 4.8. В

первой строке этой таблицы приведена передаваемая кодовая после-

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

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

сигналы «1» и «-1». Третья строка содержит значения продетектиро-

4-6. Декодирования по максимуму

правдоподобия

2571

Таблица

4.8.

Передача информации

по

каналу

АБГШ

прием

квантованием принятого сигнала

на 4

уровня.

Кодовые биты

Биполярные

символы

Принято

Мягкий

вход

Кодовые биты

Биполярные

символы

Принято

Мягкий

вход

0,3

1Ь

1,4

2,0

0,5

0,4

1,3

-1

0,4

0,3

1,2

-1

-0,0

-1

-0,7

1,0

-0,5

-1

0,0

1,0

0,8

-1

-0,7

1,8

0,4

1,4

2,2

ванного

сигнала

г,

полученные моделированием,

и,

наконец,

в чет-

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

из

табл.

4.7,

соответствующие переменной

г из

предыдущей строки.

Процесс

декодирования представлен на рис. 4.24.

Входные

симво-

лы последовательно сопоставляются

двоичными кодовыми симво-

лами исследуемых путей

и, в

соответствии

табл.

4.7,

вычисляются

метрики

этих путей.

На

первом шаге декодирования

на

вход

декодера поступает

по-

следовательность символов

«lb, lg, lb». В

этом

случае

метрика пути,

содержащего кодовые символы

«0, 0, 0»,

равна 1-1 0+1—2,

метри-

ка

пути

«1, 1, 1»

равна 2+3*2-7.

Чем

больше метрика,

тем

выше

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

лам исследуемого пути

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

путь

наибольшей метрикой.

Рассмотренный

пример показывает,

что

декодер Витерби

с мяг-

ким

решением может быть реализован

помощью целочисленной

арифметики.

Выигрыш

от

применения мягкого решения может быть

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

что в

реальных

си-

стемах

связи

переход

от

жесткого решения

мягкому

квантовани-

ем продетектированного сигнала

на 2

= 8

уровней позволяет полу-

чить дополнительный выигрыш

отношении сигнал/шум, равный

2,5

дБ.

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

за-

Глава

Сверточные

коды

поминаемого пути. Как правило, эта длина задается равной 3-5

длинам кодового ограничения выбранного сверточного кода. Если

происходит переполнение памяти, равной произведению числа состо-

яний

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

дительное решение о старших декодированных символах. Такое ре-

шение

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

на

момент принятия решения, метрикой. В нашем примере при длине

кодового ограничения п

= 3, длина запоминаемого пути должна

составлять 9 - 15 бит. При небольшой глубине декодирования сни-

жение этой длины приводит к резкому снижению корректирующей

способности кода.

Мягкое

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

турбо-

кодов,

обладающих уникальными свойствами. Модифицированный

декодер Витерби осуществляет декодирование каждого принятого

бита но максимуму апостериорной вероятности (MAP). Для это-

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

идентичности «О» и «1». Таким образом, модифицированный деко-

дер Витерби имеет мягкое решение на выходе. При многоступенча-

том декодировании это мягкое решение используется при декодиро-

вании

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

следующих

ступеней (обычно в

турбо-кодах

используется 2 3 ступени кодирования). Путем нескольких итера-

ций

этой процедуры, турбо-коды позволяют достичь скорости пере-

дачи информации, близкой к пропускной способности канала [2], [13].

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

концепцию

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

модуляцией. Вместо расстояния Хэмминга, эти коды характеризу-

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

сигналов [12], [13].

4.7.

Детектор

Витерби

Приципы

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

Витерби

могут

успехом

применяться при детектировании узкопо-

лосных сигналов (мобильные сети связи) и при считывании инфор-

мации

с магнитных носителей. Дело заключается в том, что

структу-

ра таких каналов

соответствует

структуре

сверточного кодирования

с одним

входом

и одним выходом.

На

рис. 4.25 представлена модель канала, в которой имеет место

многолучевое

распространение

радиоволн. В этой модели каждый

символ дискретной последовательности d[n] проходит через линию

4-7. Детектор Витерби

задержки (содержащую ряд элементов задержки

D ) и

многократно

складывается

некоторым весом

предыдущими

последующими

символами.

Таким образом выход незашумленного канала

каждый

дискретный

момент времени зависит

от

символа, поступающего

на

вход

приемника, состояния х

{

[п]

коэффициента

/,[п].

На рис.

4.25

этому сигналу добавлен аддитивный белый гауссовский шум.

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

символов

Коэффициенты

^ -=j= ~Т"

"J"

/'"'

i^m

Принятая

„..

_r . i

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

АБГШ

Рис.

4.25.

Передача

последовательности

d\n]

по

дискрет-

ному

во

времени

каналу

элементами

задержки

выходом

v[n\,

гауссовским

шумом

г[п\

при-

нятой

последовательностью

z[n].

Из-за

наличия цепи, содержащей элементы задержки

D, в

таком

канале

происходит «наслоение» соседних символов, что приводит

межсимвольной интерференции

(МСИ/.

Качество принимаемого сигнала может быть существенно

улуч-

шено,

если

при

детектировании принимать

во

внимание наличие

МСИ.

Для этого детектор должен знать коэффициенты fi[n)

каж-

дый момент времени

п. В

сети мобильной связи GSM

по

каналам

периодически

передается фиксированная последовательность сим-

волов

производятся необходимые измерения.

Если

внимательно проанализировать работу детектора компен-

сирующего МСИ

(его

обычно называют экволайзером),

то

можно

обнаружить, что алгоритм его работы почти

точности совпадает

алгоритмом Витерби. Продемонстрируем работу детектора Витерби

на

простом примере.

Пример:

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

Примем

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

на

рис.

4.25.

Ограничимся рассмотрением канала

одним элементом

задержки

D. В

этом

случае

возможны два состояния канала 5Ь

и Si.

^260 Глава 4- Сверточпые коды

Таблица

4.9.

Состояние

канала

МСИ

уровни

сигналов.

Символ

на

входе

d[n]

-1

1-1

-1

Значение

[fl]

-1

Состояние

S[n]

Уровень

v[n]

-0,7-0,3=

-l,0 =

+0,7-0,3

+0,4

= di

-0,7 +

0,3 = -0,4

+0,7

0,3 =

+1,0

= d

Пусть

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

сигналов

d[n]

состоит

из

биполярных

сим-

волов

d[n]e{-l,l}.

•

(4.81)

Выберем

коэффициенты

/о и f\

равными

/о

= 0,7 и Л =0,3.

(4.82)

В таблице

4.9 для

входных символов d[n]

зависимости

от

значения

xi[n],

определяющей состояние канала

So и Si,

приведены уровни

незашумленных сигналов

v[n].

Согласно модели канала

рис. 4.25 к

этим

сигналам добавляется гауссовский

шум г[п]. На

входе

детекто-

ра

мы

имеем сигнал

z[n] с

нормальным распределением

средними

значениями

из {^0,^1,^2,^3}

(табл.

4.9).

На

каждом такте декодер сравнивает величину

z[n] с

уровнями

сигнала

из

{do,di,d2,d$}

вычисляет метрики соответствующих пе-

реходов

между

состояниями канала. Исходя

из

принципа максималь-

ного

правдоподобия

нормального распределения

z[n], в

качестве

метрик

выбираются величины

= {z- di)

(4.83)

На

сетевой диаграмме (рис.

4.26)

показаны состояния канала, пере-

ходы

между

ними

приращения текущих метрик, соответствующие

этим

переходам.

После

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

при-

мер работы детектора Витерби.

таблице

4.10

приведены последова-

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

символов

последовательность сигналов

на

входе

детектора. Работа

детектора Витерби представлена

на

рис.

4.27.

Детектор Витерби

на

сетевой диаграмме рис.

4. 27

начинает деко-

дирование

на

первом такте

из

состояния

Si (на

нулевом такте канал

4-7. Детектор Витерби 261

принудительно переводится

в это

состояние путем передачи «+1»).

На

первом такте возможны только

два

перехода. Найдем прираще-

ния

метрик

на

этих переходах

нанесем

их на

сетевую

диаграмму

(2-d

)

(2,2-l)

= l,44

(4.84)

(z-d

)

(2,2

0,4)

=6,76.

Рис.

4.26.

Переходы

между

состояниями

приращения

метрик.

Таблица

4.10. Передача информации

по

каналу

МСИ.

Такт

Символ

d[n]

Канал

v[n]

Принято

z[n

0,7

1,1

1,0

2,2

-1

-0,4

0,02

0,4

-0,06

-1

-0,4

-ОДЗ

0,4

-0,31

1,0

0,99

1,0

0,97

-1

-0,4

-0,40

-1

-1,0

-1.2

-1

-1,0

-0,23

0,4

-0,93

0,3

0,6

Инициализация (посылаемый

бит

известен приемнику).

Замирание.

Так

как

на

первом такте

не

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

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

регистры

метрик

оптимальных путей для состояний SQH

S\.B

регистры путей

для состояний

So и Si

заносятся соответственно

«0» и «1».

На

втором такте декодирования возможны

уже все

переходы.

Найдем

приращения метрик

для

всех четырех переходов

и для

про-

должения выберем путь

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

Так

как

для

пер-

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

для

состояний

So и S\,

будем

считать первый принятый

бит

продетектированным.

Продолжая этот процесс далее, продетектируем

всю

последова-

тельность входных символов.

^262

Глава

Сверточные

коды

Несмотря

на значительное воздействие на детектируемый сигнал

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

Начальное

состо

ие 1.44

а96

®\

\ 0,18

/ 0.14

6.76 I/ V

0 [ 1.04

2J9

"•'ML

\ /

\ 0.21

/ом

0.88

2,46

0.76

0,00

Рис.

4.27. Сетевая диаграмма детектора Витерби.

4.8.

Упражнения

Упражнение

4.1: Сверточный код.

1. Найдите порождающий многочлен двоичного сверточного ко-

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

скоростью R = 1/2 и длиной кодового ограничения п

= 6;

2. Приведите

схему

кодера;

3. Нарисуйте диаграмму состояний;

4. Проведите кодирование информационной последовательности

{м[п]}

{1,0,0,1,1,0,1}

с лсмощью диаграммы состояний.

Для этого, прежде всего, найдите последовательность состо-

яний,

считая, что процедура кодирования начинается и закан-

чивается в нулевом состоянии;

5. Предположим, что принята последовательность

01,11,01,10,

10,10,01,11}.

Проведите декодирование данной

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