Згортальні ґратчасті коди та алгоритм Вітербі

Ґратчастий код є загальним, і більш зручним способом представлення згортальних кодів. В основі його лежить поняття орієнтованого графа-решітки (див. рис. 5). При застосуванні таких графів слід дотримуватися певних правил:

1. Кожна вершина графу відповідає поточному внутрішньому стану кодера. Початковому стану кодера відповідає одна із вершин – перед початком кодування – це вершина “00”.

2. Ребро відповідає одному з можливих поточних символів джерела (для двійкового джерела верхнє ребро - 0, нижнє - 1).

3. Над кожним ребром відмічені значення символів, які передаються в канал.

4. Послідовності ребер (шлях на ґратах) – це послідовність символів, виданих джерелом – результати кодування на відповідному кроці.

Рис. 5. Приклад орієнтованого графа-решітки

Приклад 1: Нехай комбінація на вході кодера – “100”. Початковий стан кодера – вершина “00”, позначена на рис. 5 як точка “а”. Оскільки першим символом цієї комбінації є “1”, то з точки “a” йдемо по нижньому ребру в точку “ b ”. У канал передається комбінація, якою помічене ребро “ а – b ”, тобто “11”.

Рис. 6. Приклад кодування за орієнтованою граф-решіткою

Другий символ – 0. Тому з точки “ b ” йдемо по верхньому ребру в точку “ f ” і в канал передається “10”.

Третій символ – 0. З точки “ f ” йдемо по верхньому ребру в точку “ n ”. У канал передається “10”.

В результаті отримуємо комбінацію на виході кодера: “1 1 1 0 1 0”.

В процесі демодуляції прийнятий сигнал декодується за алгоритмом Вітербі, як оптимальному, і найбільш універсальному. Саме цей алгоритм за рахунок введеної надлишковості і знання передісторії процесу прийому дозволяє по критерію максимальної правдоподібності вибрати з сигнального простору найбільш достовірну точку.

Універсальність алгоритму Вітербі визначається можливістю його використання для різних розподілів сигналів і завад, неоднорідних каналів і для поєднання декодування і модуляції і т.д.

Зміст алгоритму Вітербі полягає в наступному. Оскільки сигнал, що приймається на k -му тактовому інтервалі нам відомий, то можна обчислити Евклідову (або Гільбертову) відстань між прийнятим сигналом і всіма можливими сигналами відповідно до критерію середньо квадратичного відхилення між ними :

; ,

- часовий інтервал оцінки; - кількість можливих сигналів, - номер такту.

Цей алгоритм стосовно решітки згортального коду означає вибір такого шляху на решітці згортального коду, при якому сума кодових відстаней, тобто величина , виявиться мінімальною.

Особливість структури решітки така, що при декодуванні можливий ряд варіантів просування по ній в процесі декодування. Алгоритм Вітербі передбачає запам’ятовування цих варіантів з наступною мінімізацією суми метрик на попередніх кроках. Шлях на решітці в процесі декодування комбінацій який є мінімальним по метриці, забезпечує виправлення спотворень у комбінації, тобто вказує комбінацію, яка була передана з найбільшим ступенем ймовірності.

Приклад 2. Нехай передано повідомлення “ 1 1 1 0 1 0”, одержане за прикладом 1, а прийнято – “ 1 1 1 0 1 0”. Тобто спотворень немає. Декодування здійснюється поетапно, шляхом аналізу “ n ” біт, де n – кількість біт, якою кодувався кожен біт вихідного повідомлення (нагадаємо, що це було повідомлення “100”). Для розглянутого кодера n = 2.

1. Прийняли перші два біти – “ 1 1 ”. За діаграмою “ґрат” можливо два шляхи: al і ab.

Метрики цих шляхів дорівнюють кодовим відстаням між прийнятою комбінацією “1 1” і відповідно комбінаціями шляхів: “0 0” і “1 1”. Ці відстані або метрики d визначаються додаванням за модулем 2 відповідно:

; .

Зберігаємо мінімальний шлях ab, оскільки у них min .

2. Приймаються наступні 2 біти “ 1 0”. З точки “ b ” можливі два шляхи: bf і bc з кодами “1 0” і “0 1”.

Таким чином,

і шлях із точки “ а ” в точку “ f ” через точку “ b”:

.

Аналогічно:

,

а із точки “ а ” в точку “ c ” через точку “ b”:

.

Зберігаємо мінімальний шлях abf, оскільки у нього min .

3. Приймаються наступні 2 біти – “ 1 0”. У нас є 1 точка, з якої можливими є два шляхи. Ці точка f з якої слід розглянути шляхи: fn, fj. Як і раніше:

; .

; .

Вибираємо шлях з найменшою метрикою . Це a b f n.

Комбінація на цьому шляху: “ 1 1 1 0 1 0”. Надалі звертаємо увагу на те, що для одержання першої пари біт “11” потрібно із точки “а” в точку “ b” йти нижнім ребром, що є еквівалентним початковому символу “1”. Для одержання другої пари біт “10” потрібно із точки “ b ” в точку “ f” йти верхнім ребром, що є еквівалентним початковому символу “0”. Для одержання третьої пари біт “10” потрібно із точки “ f ” в точку “ n” йти також верхнім ребром, що є еквівалентним початковому символу “0”. В результаті робимо висновок, що передавалася комбінація “100”, що і було насправді. Тобто помилки немає.

Приклад 3. Нехай передано повідомлення “ 1 1 1 0 1 0”, одержане за прикладом 1, а прийнято – “ 1 0 1 0 1 0”. Тобто сталося спотворення в другому символі.

1. Прийняли перші два біти – “ 1 0”. За діаграмою “ґрат” можливо два шляхи: al і ab.

Метрики цих шляхів дорівнюють кодовим відстаням між прийнятою комбінацією “1 0” і відповідно комбінаціями шляхів: “0 0” і “1 1”. Ці відстані або метрики d визначаються додаванням за модулем 2 відповідно:

; .

Зберігаємо мінімальні (обидва) шляхи al і ab, оскільки у них min .

2. Приймаються наступні 2 біти “ 1 0”. З точки “ l ” можливі два шляхи: lm і li з кодами “0 0” і “1 1”.

Таким чином,

і шлях із точки “ а ” в точку “ m ” через точку “ l”:

.

Аналогічно:

,

а із точки “ а ” в точку “ і ” через точку “ l”:

.

З точки “ b ” можливі два шляхи: bc і bf з кодами “0 1” і
“1 0”. Таким чином,

і шлях із точки “ а ” в точку “ с ” через точку “ b”:

.

Аналогічно:

і шлях із точки “ а ” в точку “ f ” через точку “ b”:

.

Зберігаємо мінімальні шляхи: alm, ali, abf - ті, що вижили, а шлях abc відкидаємо, як максимальний.

3. Приймаються наступні 2 біти – “ 1 0”. У нас є 3 точки, з яких можливими є по два шляхи. Ці точки m, i, f з яких слід розглянути шляхи: mn, mj; ig, id; fn, fj. Як і раніше:

; .

; .

; .

; .

; .

; .

Вибираємо шлях з найменшою метрикою . Це a b f n.

Комбінація на цьому шляху: “ 1 1 1 0 1 0”. Надалі звертаємо увагу на те, що для одержання першої пари біт “11” потрібно із точки “а” в точку “ b” йти нижнім ребром, що є еквівалентним початковому символу “1”. Для одержання другої пари біт “10” потрібно із точки “ b ” в точку “ f” йти верхнім ребром, що є еквівалентним початковому символу “0”. Для одержання третьої пари біт “10” потрібно із точки “ f ” в точку “ n” йти також верхнім ребром, що є еквівалентним початковому символу “0”. В результаті робимо висновок, що передавалася комбінація “100”, що і було насправді. Помилка виправлена. Таким чином, структурна схема декодера згортального коду буде мати вигляд рис. 6:

Рис. 6. Структурна схема декодера

Складність алгоритму Вітербі полягає в тому, що він потребує обробки всієї послідовності сигналів для оптимального декодування навіть першого інформаційного символу, а отже має значні часові затримки.

Дата добавления: 2014-01-04