Декодування згорткових кодів
Алгоритм Вітербі. По суті, декодування відповідно до принципу максимуму правдоподібності зводиться до завдання ототожнення прийнятої послідовності з однією з 2" дозволених послідовностей. Рішення приймається на користь найбільш ймовірної з них – тієї, яка найменшою мірою відрізняється від прийнятої.
При передачі послідовності і = (їх, і2, ..., іп) у двійковому гауссовском каналі з адитивним білим шумом Щ), щільність умовної ймовірності /? (гі) появи на виході каналу послідовності відліків суміші сигналу і шуму г = (г, , г2, ..., гп), де r (t) = u (t) + 4 (0, має вигляд
Тут p(r. iij) - густина розподілу прийнятого сигналу р. за умови, що був переданий сигнал і. Легко бачити, що отримана добутком функцій щільності ймовірності п незалежних, розподілених за Гауссом випадкових величин з математичним очікуванням, рівним рівню сигнального відліку і дисперсією, що дорівнює спектральної щільності шуму NJ2.
Декодування відповідно до принципу максимальної правдоподібності зводиться до вибору такої кодової послідовностіі',яка максимізує функцію правдоподібності:
Оскільки вираз (2.38) можна привести до вигляду
пошук максимуму (2.39), як правило, зводиться до максимізації логарифмічної функції правдоподібності
Максимум (2.40) досягається при мінімальному значенні виразу NT(r.-W() 2 , що є квадратом Евклідова відстані між
оцінкою прийнятою послідовністю та відповідною дозволеною.
Тому декодування за критерієм максимальної правдоподібності, валентно пошуку дозволеної послідовності з мінімальної ^^: відстані за Евклідом щодо прийнятої послідовникаГсГ^^
Перше тадругий доданок у виразі (2.41)
при використанні алфавіту з рівносильними сигналами є константами так що мінімізаціяdEзводиться до максимізації скалярного твору
Вітербі показав існування простого і водночас оптимального розв'язання задачі декодування за принципом максимальної правдоподібності з лінійною складністю. Все різноманіття шляхів декодування так чи інакше проходить через2 твузлів (станів) у будь-якому поперечному перерізі кодової решітки. Доказ Вітербі ґрунтувався на спостереженні про те, що шлях з найменшою метрикою, що входить у вузол і зливається в ньому з іншим шляхом, вже ніколи в майбутньому не перевершує останній у сенсі накопиченої сумарної метрики. Тому з двох шляхів, що злилися у вузлі, шлях з меншою метрикою завжди можна виключити. Ідея, по суті, полягала в тому, щоб замість обчислення та відстеження метрик шляхів, кількість яких у геометричній прогресії зростає зі зростанням п, визначати, запам'ятовувати та відстежувати метрики станів (вузлів), кількість яких постійно і дорівнює 2 до
В принципі алгоритм Вітербі може бути описаний наступним чином. Для кожного з2 тможливих станів (вузлів) пристрій обчислення метрик за прийнятою вибіркою демодулятора обчислює поточну оцінкуприрощенняметрики (2.42). У разі двійкового каналу число станів декодера на кожному такті подвоюється, оскільки вказана оцінка обчислюється з урахуванням двох гіпотез про прийнятий символ - «Про» і «1» (відповідних прийому сигналів 1 і h) Вже починаючи з третього такту кількість шляхів стає рівним 8. Йди декодер порівнює метрики пар шляхів, що ведуть у кожен вузол, і зкал пари залишає один шлях, що вижив з найбільшою метрикою (^ ысТдс-воївся) – оскільки, якзазначалося вище, всі наступні модулятори вибірки не можуть якісно змінитивідносиниправдох^ шляхів. Цей процес повторюється щоразу з
новий символ.Ув результаті число оброблюваних шляхів невище
Для зменшення обсягу пам'яті декодуючого пристрою відомості про відкинуті шляхи і відповідні їм накопичені метрики стираються Для цього метрики станів періодично усікаються на одну і ту ж величину (з накопичених кожним з вузлів метрик періодично віднімається мінімальна з них).
Наприклад, у момент часуt2перший зверху вузол (рис. 2.32 – вузол №1) відповідає стану декодера, описуваного парою символів . У цей стан декодер приходить за двох різних гіпотез.
Гіпотеза А. Стан декодера в момент часу tx відповідає наявності в його регістрі символів на вхід декодера з демодулятора надходить символ «0». З урахуванням зсуву вмісту регістру вправо, новий стан у моментt2як і раніше визначається символами, а на виході регістра з'являється символ «0» (декодер залишається в стані №1, і відповідні вузли в моментиtіt2зв'язує гілка у вигляді суцільної лінії).
Гіпотеза Б. Стан декодера в момент tx описується символами (вузол №3), але вхід з демодулятора як і надходить символ «0». Тоді в моментt2стан декодера визначатиметься символами , але на виході регістра з урахуванням зсуву вправо з'явиться символ «1» (тому вузол №3 у момент tx і вузол №1 у момент t2 пов'язує гілку, позначену пуктиром) .
Мал. 2.32. Приклад декодування за алгоритмом Вітербі
Якщо припустити (як приклад), що метрики станів вузлів №1 і №3 у момент / відповідно дорівнюють 4.0 і 2.0, а значення оцінокприрощення метрик у згадуваних гілках дорівнюють +1.5 і -1.5, то оновлене (у момент L) значення метрики вузла №1 як максимальне з двох обчислених складе 5.5 -див. Мал. 2.32. Стрілки, відповідні «гілкам», що вижили, відібраним декодером на аналізованому такті обробки, наведені жирної лінії.
З усіх можливих шляхів, що вижили, декодер в кінцевому рахунку повинен вибрати єдиний найбільш правдоподібний - шлях з найбільшою метрикою.
Однак у поточний момент часу, навіть якщо один із шляхів вірогідніший за інші, декодер, не маючи відомостей про подальші фрагментиприймаємої послідовності, «утримується» від остаточного рішення і запам'ятовує всі шляхи, що вижили, на час прийому певної кількості наступних відліків.
Емпірично встановлено, що після закінчення деякого інтервалу часу тривалістю L тактів всі шляхи зливаються в один найбільш правдоподібний (див. рис. 2.33), і прийом всіх наступних символів не впливає на його траєкторію. Величину L називають шириною вікна декодування. Її оптимальне значення залежить від конфігурації помилок у послідовності символів, що приймається. Декодер може приймати оптимальне рішення щодо символу ділянки шляху, що вижив, запізнюється щодо поточного що надходить віддемодуляторасимволу на L , тактів.
Мал. 2.33. Шлях, що вижив, знайдений декодером Вітербі [3]
Очевидно, що при поспішному прийнятті рішення (L< Lop) може виникати неоднозначність у виборі шляху, що вижив, у той час як при L » L має місце невиправдана затримка в прийнятті рішення. Оптимальне значення Lnpt є випадковою величиною і може бути обчислено заздалегідь. Насправді при реалізації декодера встановлюють деяку фіксовануширину вікна (як правило, Z
Складність декодера Вітербі залежить від тривалості оброблюваної послідовності символів, але експоненційно зростає зі зростанням довжини кодового обмеження. У сучасних системах бездротового зв'язку найбільше часто застосовуються згорткові коди зі швидкостями 1/2, 1/3,2/3, 3/4, 5/6 при довжині кодового обмеження 5, 7 або 9.