Применение сверточного кода в цифровых системах связи

Після аналогічних перевірок для другого і третього кадрів прийнятої

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

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

 

Таблиця 2.1 – Конфігурація помилок в кадрах

Конфігурація помилок в прийнятому сегменті				Синдром
1-й кадр	2-й кадр	3-й кадр	…	…
1000	0000	0000		111
0100	0000	0000		011
0010	0000	0000		101
0001	0000	0000		001
0000	1000	0000		110
0000	0100	0000		110
0000	0010	0000		010
0000	0001	0000		010
0000	0000	1000		100
0000	0000	0100		100
0000	0000	0010		100

 

2.3  Кодове дерево і решітчаста діаграма

 

Ще одним дуже наочним способом опису та ілюстрації роботи згорткових кодів є використання так званого кодового дерева. 
Розглянемо згортковий (6.3)-код зі схемою, зображеною на малюнок 2.2.

Малюнок 2.4 – схема зі згортковим (6.3)-кодом.

 

Відповідно цьому кодеру кодове дерево - це послідовність вихідних станів кодера при подачі на його вхід ланцюжка вхідних символів 0 і 1 - наведено на малюнку 2.5.

Малюнок 2.5 –  кодове дерево.

На діаграмі (малюнок 2.5) зображені вхідні і вихідні послідовності кодера: вхідні - напрямком руху по дереву (вгору - 0, вниз - 1), вихідні - символами вздовж ребер дерева. При цьому кодування полягає в русі вправо по кодовому дереву.

Наприклад, вхідна послідовність m=(01000...... кодується як U=(0011101100000..., послідовність m=(1010100000... –як U=(1110001000... .

Якщо уважно подивитися на будову наведеного на малюнку 2.5 кодового дерева, можна помітити, що починаючи з четвертого ребра його структура повторюється, тобто яким би не був перший крок, починаючи з четвертого ребра значення вихідних символів кодера повторюються. Однакові ж вузли можуть бути об'єднані, і тоді починаючи з деякого перерізу розмір кодового дерева перестане збільшуватися. 
Іншими словами, вихідна кодова послідовність в певний момент перестає залежати від значень вхідних символів, введених в кодер раніше.

Дійсно, з малюнка 2.5 видно, що, коли третій вхідний символ вводиться в кодер, перший вхідний символ залишає зсувний регістр і не зможе надалі впливати на вихідні символи кодера. 
З урахуванням цього необмежене кодове дерево, зображене на малюнку 2.5, переходить в обмежену ґратчасту діаграму (кодове дерево зі зливаються вузлами) малюнок 2.6.

11

10

01

00

Малюнок 2.6 – гратчаста діаграма.

Кодування згортковими кодами з використанням ґратчастої діаграми, як і у випадку з кодовим деревом, являє собою надзвичайно просту процедуру: чергові символи вхідної послідовності визначають напрямок руху з вузлів решітки: якщо 0, то йдемо по верхньому ребру, якщо 1 - по нижньому ребру. Однак на відміну від кодового дерева ґратчаста діаграма не розростається по ширині з кожним кроком, а має починаючи з третього перетину постійну ширину. 
Як приклад закодуємо за допомогою ґратчастої діаграми кілька інформаційних послідовностей.

Нехай m=(0110000… . Відповідна їй кодова послідовність

буде мати вигляд: U= (001101011100..., чи m = ( 110100... , тоді U= (1101010010110000...; чи m = ( 000000… , тоді U= (1101010010110000 і т.д.

 

2.4  Алгоритм декодування згорткових кодів

 

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

Алгоритм послідовного декодування реалізує пошук шляху, 
відповідного переданій інформаційній послідовності. Суттєвим є те, що інформація, отримана в процесі декодування, використовується для оптимізації подальшого пошуку найбільш правдоподібних продовжень шляху. Для згладжування нерівномірності обчислень декодер містить буферну пам'ять, переповнення якої при інтенсивному потоці помилок веде до відмови від декодування (і це треба визнати недоліком при роботі алгоритму). Крім того, послідовний алгоритм чутливий до спотворень в каналі зв'язку (зміни рівня сигналу, флуктуації фази і так далі). Тому в супутникових системах зв'язку, що пред'являють великі вимоги до перешкодозахищеності інформації, потужності сигналу, надмірності коду, швидкодії кодека, послідовний алгоритм широкого розповсюдження не отримав, не дивлячись на те, що складність реалізації такого алгоритму пропорційна малому ступені довжини кодового обмеження згортального коду.

Іншим алгоритмом декодування, заснованому на використанні імовірнісних характеристик сигналів, що приймаються, є алгоритм максимального правдоподібності, запропонований А. Вітербі. Алгоритм має ряд переваг перед іншими, і його широко використовують для декодування коротких згорткових кодів. Розглянемо алгоритм на прикладі коду зі швидкістю R = 1/n.

Нехай починаючи з моменту t = 0, на вхід кодера подається інформаційна послідовність довжиною в L символів U = (U₀ U₁ U₂ … U_L-1). На виході кодера буде послідовність символів V = (V₀ V₁ V₂ … V_L-1). Стан кодера в момент t визначають як набір з Y інформаційних символів W = (U₁ U₂ … U_t-2 … U_t-Y-1)

t ≥ Y - 1. Гратчаста діаграма коду однозначно пов'язує інформаційну послідовність U_L, послідовність станів кодера W_L=(W₀ W₁ W₂ … W_L) і послідовність символів на його виході V_L.

Кожній гілці коду U₁ в каналі відповідає сигнал, який може бути представлений набором координат в N-мірному просторі S_L=(S_t⁽⁰⁾ S_t⁽¹⁾ S_t⁽²⁾ … S_t^(N)). У каналі діє адитивна перешкода і надходить на вхід декодера послідовність Z_L=S_L+N_L где S_L = (S₀ S₁ S₂ … S_L-1). N_L=( N₀ N₁ N₂ … N_L-1), N_t=( S_t⁽⁰⁾ S_t⁽¹⁾ S_t⁽²⁾ … S_t^(N)) – N-мірний вектор перешкоди. Декодування полягає в прослеживании по кодової решітці шляху з максимальною апостеріорну ймовірністю. Декодований шлях можна вказати одним із способів набором оцінок кодових гілок V = (V₀ V₁ V₂ … V_L-1), складових шлях; послідовністю оцінок станів кодера W_L=(W₀ W₁ W₂ … W_L-1), або послідовністю оцінок інформаційних символів на вході кодера U=(U₀U₁U₂…U_L-1), які збігаються з першими символами оцінок станів W_t=(U₁U₂…U_t-2…U_t-Y+1). Послідовність Z_L декодована з мінімальною ймовірністю помилки, якщо для всіх можливих шляхів вибрати оцінку Q_L, для якої максимальна апостеріорна ймовірність Р (V_L/Z_L).

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

Р (Z_L / V_L) = МАХ.                                (2.3)

У каналі без пам'яті апостеріорної ймовірності Р (Z_L / V_L) пропорційно добутоку умовних плотностей ймовірностей суми сигналу і завади:

.   (2.4)

В гаусівському каналі при дії білого шуму з односторонньою спектральною щільністю потужності NQ кожен співмножник цього добутку має вигляд:

   .    (2.5)

Для відшукання максимуму виразу (3.3) зручно його прологаріфміровать:

.   (2.6)

При декодуванні за критерієм (3.1) вибирають таку послідовність сигналів S_L = (S₀ S₁ S₂ … S_L-1) і однозначно пов'язану з нею послідовність гілок V_L = (V₀V₁V₂…V_L-1) яку називають метрикою декодованого шляху, яка забезпечує мінімум суми:

.     (2.7)

Метрика шляху містить в якості доданків метрики гілок:

.      (2.8)

.      (2.9)

В гауссівському каналі метрика гілки пропорційна квадрату, Евклідову відстані між вектором прийнятої суми сигналу і завади (5.8) і вектором

Z_t = (Z_t⁽⁰⁾ Z_t⁽¹⁾ Z_t⁽²⁾ …Z_t^(N)).     (2.10)

сигналу S_t, відповідного гілці коду V_t. В дискретному каналі для оцінки відстаней використовують метрику Хемінга.

Розглянемо застосування алгоритму більш детально для конкретної швидкості. Для кращого розуміння дії алгоритму розберемо його для швидкості R =1/2. А потім, уже розуміючи його принципи дії, докладно зупинимося на його роботі зі швидкістю R =2/3.

 

 

 

 

2.5  Алгоритм декодування Вітербі для коду зі швидкістю R=1/2

 

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

Розглянемо декодування символів, які передаються по дискретному каналу. В цьому випадку метрика гілки МВ дорівнює відстані Хеммінга між набором символів Z⁽²⁾ Z⁽¹⁾ на вході кодера і набором символів V⁽²⁾ V⁽¹⁾, відповідній даній, гілці на гратчастій діаграмі. Якщо Z⁽²⁾ Z⁽¹⁾ = 01, то можливі значення метрик гілок з гратами будуть: МВ (00) = 1, МВ (01) = 0.  МВ (11) = 1, МВ(10) = 2. Метрика шляху є сума метрик гілок, що утворюють певний шлях на гратчастій діаграмі. Шлях кінцевої довжини закінчується в певному стані. Метрика стану МС дорівнює метриці шляху, який закінчується в даному стані. Крок декодування полягає в обробці декодером прийнятих з каналу даних в інтервалі між двома сусідніми рівнями вузлів.

Рисунок 2.7 - процес кодування символів за алгоритмом Вітербі.

На малюнку 2.7 показано розвиток процесу декодування символів. Пари символів надходять з каналу Z⁽²⁾ Z⁽¹⁾ = 11 10 00 10 ... (вони позначені в верхньому ряді і слідують в порядку надходження з каналу на кожному кроці декодування). Цифрами біля гілок позначені метрики гілок, цифри в кружках означають метрики станів. У початковий момент часу ми вважаємо, що декодер знаходиться в стані 00 і вихідна метрика МС(00) = 0. Якщо з каналу надійшли символи 11, то метрики двох гілок, що виходять з цього стану,    МВ(00) = 2 і МВ(11) = 0. Це зазначено на першому кроці декодування. Так як інших гілок зі стану 00 в состояния 00 і 10 немає, то метрики цих станів приймають рівними метрикам вхідних гілок: МС(00) = 2 и МС(01) = 0. Аналогічно і на наступному кроці, коли з каналу надходять символи 10. Тут МВ(00) = 1, МВ(11)= 1, МВ(10) = 0, МВ(01) = 2. Метрики станів на цьому визначаються як суми метрик вхідних гілок з метриками попередніх станів:

МС(00) = МВ(00) + МС(00) = 2+1 = 3;         

 МС(10) = МВ(10) + МС(10) = 2+1 = 3;                                          (2.11)

МС(01) = МВ(01) + МС(01) = 0+0 = 0;      

МС(11) = МВ(00) + МС(00) = 0+2 = 2.      

 

На цьому початковий розвиток гратчастій діаграми закінчується.

Далі алгоритм періодично повторює один основний крок. В момент часу t в пам'яті декодера зберігаються метрики станів, обчислених на попередньому кроці (i-1): МС(00)^(i-1), МС(10)^(i-1), МС(01)^(i-1), МС(11)^(i-1). За прийнятими кодовими посилками від кодера виробляємо обчислення метрик гілок на кроці (i): МВ(00)⁽ⁱ⁾, МВ(11)⁽ⁱ⁾, МВ(10)⁽ⁱ⁾, МВ(01)⁽ⁱ⁾ і формування чотирьох нових метрик станів МС(00)⁽ⁱ⁾, МС(10)⁽ⁱ⁾, МС(01)⁽ⁱ⁾, МС(11)⁽ⁱ⁾ по наступному правилу.            К каждому новому состоянию ведут два пути. До кожного нового стану ведуть два шляхи. Приміром, до стану 00 ведуть шляхи з станів 00 і 01. Декодер обчислює метрики шляхів як суми метрик попередніх станів і метрик вхідних гілок. Метрика шляху є сума метрик гілок, що утворюють певний шлях на гратчастій діаграмі. Метрика даного стану дорівнює метриці шляху (МП), який закінчується в даному стані таким чином: