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

 

 

 

              (2.12)

 

 

 

 

 

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

1) Додавання метрик попередніх станів з метриками відповідних гілок;

2)  Порівняння метрик вхідних шляхів;

3) Вибір шляхів з найменшими метриками, величини яких використовують як метрики станів на наступному кроці декодування. Якщо метрики порівнюваних шляхів однакові, вибір одного з двох шляхів виробляють випадковим чином. На кожному кроці в результаті порівняння половина можливих шляхів відкидається і надалі не використовується. Інша половина утворює продовження шляхів для наступного кроку декодування. З кожного стану на наступному кроці знову з'являються два варіанти продовження шляхів. Це забезпечує сталість обчислень, вироблених на кожному кроці. Декодер простежує по кодової решітці шлях, який має мінімальну відстань від шляху, який генерує кодер.

При простежуванні на досить велику глибину виживших шляхи, як правило, зливаються. для швидкості R = 1/2 достатньо взяти шлях рівний трьом. При цьому будуть виправлятися поодинокі помилки з частотою появи один через шість (ці помилки будуть виправлятися зі стовідсотковою ймовірністю, але можливі ситуації в яких буде виправлятися навіть дві помилки).

Приклад декодера зі швидкістю R = 1/2 досить просто зрозуміти. Для декодера зі швидкістю R = 2/3 процес складніший.

 

2.6  Декодування одиночних помилок за алгоритмом Вітербі

 

Припустимо, що при передачі кодового повідомлення по дискретному каналу виникла одиночна помилка. В наслідок чого замість вихідної послідовності на вхід декодера надходить послідовність: Z⁽³⁾ Z⁽²⁾ Z⁽¹⁾ = 110 011 000 001 101 010 100... . Маємо в 3-й трійці помилку в першому розряді 0 замість вихідної 1-ці. Розглянемо процес побудови декодером гратчастої діаграми. На першому етапі розвитку діаграми (перші п'ять кроків) відбуваються різні відхилення, шлях на першому кроці декодується правильно (через не важливості цього моменту він опущений, але в цьому легко переконатися самостійно). Другий етап представляє набагато більший інтерес.

Малюнок 2.8 - Декодовані шляхи при виникненні помилки.

 

На малюнку 2.8 показано розвиток гратчастої діаграми вірного і помилкового шляху на другому етапі. Тут початковою є вершина два і від неї здійснюється розвиток гратчастої діаграми. Дивлячись на малюнок, можна переконатися, що метрика правильного шляху (що складаються з малих відрізків) дорівнює 1, а метрика помилкового 3. Інші метрики мають великі значення за умови прийому без спотворення даних, а в зв'язку з помилкой яка сталася мають ще більше значення, отже, в процесі декодування буде обраний правильний шлях (з мінімальною метрикою) на першому кроці другого етапу. І надалі алгоритм продовжить свою роботу на третьому етапі, починаючи декодування з істинної вершини під номером 7 (вершини нумерують зверху вниз).

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

Цей метод дозволяє усувати помилки при їх проходженні через 10 інформаційних біт. Це пов'язано з вибором глибини перегляду вглиб гратчастої діаграми рівною п'яти. Якщо ж брати її більше, то значно зростає кількість обчислень (при глибині перегляду сім час збільшується вдвічі і росте далі в експоненційної залежності), пов'язаних з декодуванням шляху. Зазвичай її рекомендують брати не більше 10. 
 Так складність реалізації алгоритму визначається в основному структурою гратчастої діаграми. Тому її використовують для коротких згорткових кодів і швидкість передачі зазвичай беруть рівною 1/2 або 2/3 і не більше.

2.7  Оцінка згорткових кодів з алгоритмом декодування Вітербі

 

Найбільш корисним методом оцінки характеристик системи згортального кодування є використання адитивної границі. В якості оцінюваних параметрів, розглянемо вірогідність першї помилкової події Ре і більш часто ймовірність помилки символу РЬ. Для цього будемо використовувати адитивну границю. Перш ніж отримати адитивну границю, розглянемо правильний шлях і інший шлях який відрізняється від нього в j позиціях. Позначимо ймовірність вибрати на виході каналу цей інший шлях замість правильного через Рj. Якщо в дискретному каналі діє ймовірність помилки р величина Рj дорівнює сумі ймовірності появи більш j/2 помилок і половині ймовірності появи рівно j/2 помилок. Оскільки коди, описані в розділі 2.3, є лінійними, можна припустити, що правильний шлях відповідає нульовій переданій послідовності. Виникнення першої помилки при обробці i-го прийнятого ребра означає, що в цьому місці нульовий шлях замінюється деяким іншим, зливающимся з ним шляхом. Ймовірність Рj заміни нульового шляху на зливающийся з ним шлях ваги j залежить тільки від ваги цього шляху. Кількість шляхів ваги j, які зливаються з нульовим шляхом, дорівнює nj, і повна інформаційна вага цих шляхів дорівнює Wj. При цьому розподіл ваги шляхів, що входять у стан 0, збігається з розподілом ваги шляхів, що виходять зі стану 0.

Адитивна границя для ймовірності Ре першої помилки на i-му ребрі виходить підсумовуванням ймовірностей помилки для всіх можливих шляхів, що зливаються з нульовим шляхом у цьому місці. Ця верхня границя має наступний вигляд:

.     (2.13)

Адитивна границя для ймовірності РЬ помилки символу може бути отримана з (8.1) множенням кожного члена на відповідне число помилок символів (інформаційна вага шляху). Однак для коду з R = m/n на кожному ребрі декодується n символів. Тому границя для РЬ має вигляд:

.     (2.14)

Справедливість нерівності (2.14) проілюстрована на малюнку 2.9. Помилкове подія полягає в тому що відбувається одна або декілька помилок в символах. Припустимо, що помилка виникла на К-му кроці і правильний шлях був замінений на шлях X’. На наступному кроці порівнюються X” і X’ а не X” і правильний шлях. Ймовірність того, що при такому порівнянні Xвиявиться вижившим шляхом, не перевищує ймовірності першого помилкового події, оскільки правильний шлях замінюється на шлях з більшою метрикою. Для отримання верхньої оцінки середнього числа помилкових символів за N кроків можна підсумувати, по всіх шляхах твори ймовірностей помилки на число помилкових символів і, потім взявши суму отриманих величин за всіма N кроками.

Малюнок 2.9 - Типова помилка при декодуванні за алгоритмом

 Вітербі.

Малюнок 2.10 - Імовірність помилки символу в залежності від величини відношення сигнал-шум.

 

Помічаючи, що при цьому декодуються N інформаційних символів так, що середня імовірність помилки, на символ дорівнює сумі N однакових виразів, поділеній на N, отримуємо оцінку (2.9).

Ймовірність помилки РЬ символу залежить також від відношення сигнал-шум і довжини кодового обмеження (і це зрозуміло, чим більше потужність сигналу тим менше впливає перешкода на сигнал). Часто довжина кодового обмеження (ДКО) визначається як логарифм за основою два від числа станів. Для нашого випадку ДКО дорівнює трьом. Графічно можна представити цю залежність на малюнку 2.9.

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

 

2.8  Реалізація алгоритмів кодування і декодування згорткових кодів

Виходячи з того, що алгоритми кодування і декодування згорткових кодів будуть реалізовуватися на базі мікропроцесора. В якості останнього вибираємо мікроконтролер сімейства МК51 1816 серії КР1816ВЕ51. Будемо вважати, що він і є мікропроцесорним ядром високошвидкісного модема.

Мікроконтролер КР1816ВЕ51 відноситься до восьмирозрядним високопродуктивним однокристальним мікроЕОМ (ОМЕОМ), виконаним за високоякісної n-МОП технології. Данна ОМЕОМ містить усі вузли необхідні для автономної роботи:

а) центральний восьмирозрядний процесор; 
б) пам'ять програм обсягом 4 Кбайт; 
в) пам'ять даних обсягом 128 байт; 
г) чотири восьмирозрядних програмованих каналу введення / виводу; 
д) два 16-бітових багаторежимних таймера / лічильника; 
е) систему переривань з п'ятьма векторами і двома рівнями; 
ж) послідовний інтерфейс; 
з) тактовий генератор.

ОМЕОМ 1816 серії також містить:

а) 32 регістра загального призначення (РЗП); 
б) 128 визначаються користувачем програмно-керованих прапорів; 
в) набір регістрів спеціальних функцій.

ОМЕОМ КР1816ВЕ51 містить масочно-програмоване в процесі виготовлення кристала ПЗП пам'яті програм ємністю 4096 байт і вбудоване ОЗП <spa