Оцінка ефективності модифікованого алгоритму ітеративного декодування турбокодів

Вступ У теперішній час широке розповсюдження одержали технології бездротового широкосмугового радіодоступу (Wi-Fi, WiMAX, LTE), які дозволяють організовувати як мережі загального користування, так і мережі технологічного радіозв'язку різного призначення й забезпечують доступ до мережі Інтернет. Крім того, практично всі оператори мобільного зв’язку також пропонують послугу доступу до мережі Інтернет на основі радіотехнологій GPRS, EDGE (GSM), HDSPA, Rev (UMTS, CDMA). Причому слід зазначити тенденцію до збільшення швидкості передачі інформації (від 40 кбіт/с до 14 — 100 Мбіт/с).

Існують два основних напрямки застосування бездротових мереж — робота в замкнутому об'ємі (офіс, виставочний зал і т.п.) і з'єднання віддалених локальних мереж (або віддалених сегментів локальної мережі). Для з'єднання віддалених локальних мереж може використовуватися обладнання зі спрямованими антенами й антенні підсилювачі. При цьому як подібне обладнання можуть виступати, наприклад, пристрої Wi-Fi з додатковими антенами. Зв’язувати віддалені сегменти можна й за технологією WiMAX, у той час як у самому сегменті для зв’язку буде використовуватися Wi-Fi або провідний Ethernet.

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

Одним з найбільш ефективних методів підвищення вірогідності переданої інформації є завадостійке кодування [3−10]. При високих вимогах до достовірності й низькому енергетичному відношенні сигнал/шум доцільно застосування каскадних кодів, які, на відміну від інших кодів, забезпечують високу ефективність кодування при меншій складності реалізації декодера.

Особливістю каскадних схем кодування є кодування (декодування) інформації декількома складовими кодерами (декодерами).

В 1993 році був запропонований новий клас каскадних кодів — паралельні каскадні коди (турбокоди). У цей час прийняті стандарти на використання турбокодів у системах супутникового зв’язку, телеметрії, цифрового супутникового телебачення й радіомовлення, системах мобільного зв’язку третього й четвертого покоління.

На відміну від відомих послідовних каскадних кодів, турбокоди, що є паралельними каскадними кодами, дозволяють для їхнього декодування застосовувати процедуру ітеративного декодування. При цьому виявляється можливою передача інформації при енергетичному відношенні сигнал/шум близьким до гранично можливого значення, обумовленого теоремою Шенона, оскільки характеристики ітеративного турбодекодера близькі до декодера максимальної правдоподібності. Тому використання турбокодування переданої інформації є одним з перспективних напрямків.

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

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

1 Загальний аналіз методів підвищення вірогідності передавання інформації.

Способи підвищення достовірності передачі інформації вельми численні і різноманітні, проте їх можна розділити на три групи:

— заходи експлуатаційного і профілактичного характеру (зменшення числа джерел завад, поліпшення стабільності роботи основних вузлів, резервування і т.п.);

— зменшення імовірності помилкового прийому за рахунок підвищення відношення сигнал/завада (вибір методів модуляції, прийому, тривалості, спектрів, потужності);

— використовування завадостійких кодів.

1.1 Класифікація методів підвищення вірогідності передавання інформації.

Завдання підвищення вірогідності переданих даних вирішується шляхом застосування спеціальних методів, їхня загальна класифікація представлена на рисунку 1.1.

З рисунка 1.1 виходить, що підвищення вірогідності передаваних даних можливо як на сигнальному, так і на дискретному рівнях.

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

Рисунок 1.1 — Методи підвищення вірогідності передавання даних Одним з найбільш ефективних методів підвищення вірогідності переданої інформації є завадостійке кодування, що полягає у внесенні кодером надмірності в передане повідомлення. На прийомній стороні декодер здійснює виявлення або виправлення помилок на основі аналізу надлишкових елементів повідомлення і їхніх відповідностей переданим даним.

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

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

З рисунку 1.2 виходить, що більшість кодів є блоковими кодами. Побудова й декодування блокових кодів базується переважно на алгебраїчних методах. Найбільше розповсюдження серед блокових кодів одержали коди з перевіркою на парність, коди Хемінга, коди БЧХ і коди Ріда-Соломона.

До безперервних кодів відносяться деревоподібні коди. Лінійні постійні в часі деревоподібні коди є згорточними кодами.

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

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

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

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

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

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

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

1.2 Аналіз згорточних кодів При використанні згорточних кодів потік даних розбивається на набагато менші блоки довжиною символів (в окремому випадку), які називаються кадрами інформаційних символів.

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

Основними характеристиками згорточних кодів є величини:

— - розмір кадру інформаційних символів;

— - розмір кадру кодових символів;

— - довжина пам’яті коду;

— - інформаційна довжина слова;

— - кодова довжина блоку.

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

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

Згорточні коди можуть бути систематичними і несистематичними й визначаються як лінійні згорточні (n, k)-коди.

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

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

Більш зручним способом опису згорточного коду є його завдання за допомогою імпульсної перехідної характеристики еквівалентного фільтра Хафмена (лінійної послідовної схеми або регістра зсуву зі зворотними зв’язками) або відповідного йому породжуючого багаточлена.

Декодування здійснюється за допомогою метода максимальної правдоподібності.

Для двійкового симетричного каналу без пам’яті (каналу, у якому імовірності передачі 0 і 1, а також імовірності помилок виду 0 1 і 1 0 однакові, помилки в j-м і i-м символах коду незалежні) декодер максимальної правдоподібності зводиться до декодера мінімальної відстані Хеммінга. Останній обчислює відстань Хеммінга між прийнятою послідовністю й всіма можливими кодовими векторами й виносить рішення на користь того вектора, що виявляється ближче до прийнятого.

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

Характеристики згорточних кодів, як і будь-яких інших кодів, поліпшуються в міру збільшення їхнього розміру, у цьому випадку — кодової довжини блоку. Тому, декодер Витербі стає не реалізовано складним. Так, при n = 10 він повинен пам’ятати вже не менш 2¹⁰ = 1024 шляхів, що виживуть.

Для зменшення складності декодера максимальної правдоподібності при великих n була розроблена стратегія, що ігнорує малоймовірні шляхи пошуку по ґратам. Однак рішення про те, щоб остаточно відкинути даний шлях, не приймається. Час від часу декодер повертається назад і продовжує залишений шлях.

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

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

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

1.3 Дослідження потенційних можливостей м’якого декодування завадостійких кодів.

Визначимо теоретично граничне значення, при якому можлива передача інформації.

Пропускна здатність каналу зв’язку (біт/відлік) визначається вираженням.

(1.1).

де — середня взаємна інформація між й , — вхідний алфавіт або алфавіт джерела, — реалізація вхідного сигналу, — апріорний розподіл імовірностей джерела сигналу, — вихідний алфавіт.

Застосування м’якого декодування відповідає моделі каналу з безперервним вихідним алфавітом. При цьому сигнал з виходу демодулятора називають м’якими рішеннями демодулятора.

Розглянемо канал без пам’яті з АБГШ із безперервними вхідним і вихідним алфавітами (безперервний канал).

.

Схема каналу представлена на рисунку 1.3.

Вілікі шуму, у дискретні моменти часу кратні являють собою випадкові величини, що мають нормальний розподіл з нульовим середнім значенням і дисперсією, де — спектральна щільність потужності шуму. Будемо вважати, що відліки не залежать від, а відліки залежать від відліків, тільки коли .

Рисунок 1.3 — Схема безперервного каналу без пам’яті з АБГШ Середня взаємна інформація може бути визначена з вираження.

(1.2).

де — диференціальна ентропія вихідного сигналу, — умовна диференціальна ентропія вихідного сигналу, коли відомий вхідний сигнал.

Тому що, а й — незалежні випадкові величини, то й (2) можна представити як.

(1.3).

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

а при інших розподілах диференціальна ентропія не перевершить цього значення.

Таким чином, можна зробити висновок, що буде максимальна, якщо має нормальний розподіл. Тому що має нормальний розподіл, те також повинен мати нормальний розподіл. З огляду на вищесказане, можна записати в такий спосіб.

(1.4).

де.

Позначимо ,.

де — потужність сигналу, — потужність шуму.

З (1.1) одержимо.

(1.5).

Пропускна здатність визначається наступним вираженням.

(1.6).

де — смуга частот каналу.

Представимо (1.6) у такий спосіб.

(1.7).

З огляду на, що.

(1.8).

де — енергія одного біта й припускаючи максимально можливу швидкість передачі інформації представимо (7) у такий спосіб.

(1.9).

Визначимо значення, при якому :

Це граничне значення називають границею Шенона. Таким чином, можна зробити висновок про неможливість передачі інформації без помилок на фоні АБГШ, якщо У реальних телекомунікаційних системах вхідний алфавіт звичайно є дискретним. Тому розглянемо дискретно-безперервний АБГШ канал без пам’яті з дискретним вхідним алфавітом і безперервним вихідним алфавітом .

Пропускна здатність дискретно-безперервного АБГШ каналу.

(1.10).

де — апріорний розподіл імовірностей символів алфавіту ,.

— щільність розподілу значень сигналу на прийомній стороні каналу,.

— щільність розподілу значень сигналу на прийомній стороні каналу за умови, що був переданий символ .

Для протилежних рівноймовірностних сигналів (двійкова ФМ).

(1.10).

приймає вид.

(1.11).

Розглянемо пропускну здатність каналу з дискретними вхідним і вихідним алфавітами.

:

(1.12).

де — апріорний розподіл імовірностей символів алфавіту ,.

— імовірність прийому символу за умови, що був переданий символ.

.

Окремим випадком дискретного каналу без пам’яті з АБГШ є двійковий симетричний канал (ДСК). Модель ДСК відповідає випадку, коли здійснюється квантування сигналу з виходу демодулятора на два рівні. Квантований на два рівні сигнал називають жорсткими рішеннями демодулятора. Для ДСК вираження (1.12) приймає вид.

(1.13).

а визначається вираженням де.

На рисунку 1.4 представлена залежність і від відношення сигнал/шум. З порівняння кривих виходить, що пропускна здатність каналу з безперервним вихідним алфавітом перевищує пропускну здатність ДСК. При цьому енергетичний виграш каналу з безперервним вихідним алфавітом (енергетичний виграш від м’якого декодування) становить приблизно в порівнянні із ДСК (жорстке декодування) при малому відношенні сигнал/шум.

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

Рисунок 1.4 — Залежність пропускної здатності від відношення сигнал/шум для різних видів каналів (а); залежність мінімального відношення від швидкості коду для різних видів каналів (б) Визначимо граничне значення для системи кодування зі швидкістю коду. Для цього представимо відношення сигнал/шум на виході погодженого фільтра рівне як функцію пропускної здатності каналу, використовуючи вираження (1.5).

(1.14).

Якщо прийняти й урахувати, що, то можна одержати.

(1.15).

Необхідно відзначити, що (1.15) вірно для каналу з АБГШ із безперервним вхідним і вихідним алфавітами. Для дискретного вхідного алфавіту необхідно скористатися вираженнями (1.11) або (1.13) і, приймаючи, вирішити так рівняння.

(1.16).

На рисунку 1.4, б представлені залежності граничного значення від швидкості. Крива 1 — безперервний канал; крива 2 — дискретно-безперервний канал із двійкової ФМ (м'які рішення демодулятора); крива 3 — ДСК із ФМ (жорсткі рішення демодулятора).

З рисунку 1.4, б видно, що при нормальному розподілі на вході каналу досягається найменше відношення, а найбільше — для двійкового симетричного каналу. Наприклад, для швидкості коду мінімальне відношення становить 0,19 дБ для протилежних сигналів і каналу з безперервним вихідним алфавітом у порівнянні з 0 дБ, якщо розподіл на вході каналу нормальне або 1,78 дБ для ДСК. Для швидкості коду мінімальне відношення становить -0, 51дБ для протилежних сигналів, у той час як для нормального розподілу на вході каналу мінімальне відношення становить — 0,56дБ, а для ДСК 1,12 дБ. Таким чином, можна зробити висновок, що використання м’яких рішень демодулятора дозволяє зменшити мінімальне відношення на 2 дБ у порівнянні із жорсткими рішеннями.

Для порівняння різних систем завадостійкого кодування зручно використовувати графік, представлений на рисунку 1.5. На графіку по осі абсцис відкладені значення відносини, по осі ординат — швидкість коду. Передбачається наявність у каналі аддитивного білого гауссовского шуму. Крива 1 — теоретичне мінімальне відношення або границя Шенона для кодів з різними швидкостями; крива 2 — пропускна здатність каналу із двійкової ФМ і м’якими рішеннями демодулятора (безперервний вихідний алфавіт); крива 3 — пропускна здатність каналу із двійкової ФМ і жорсткими рішеннями демодулятора (ДСК, дискретний вихідний алфавіт). Точки на графіку відповідають необхідному відношенню для досягнення ймовірності помилки на біт для системи кодування зі швидкістю коду.

Рисунок 1.5 — Залежність мінімального відношення від швидкості коду Наприклад, при відсутності завадостійкого кодування й використанні двійкової ФМ для досягнення необхідне відношення дБ, при цьому біт/переданий символ. Якщо використовується завадостійке кодування, то відношення для досягнення такої ж імовірності помилки буде менше в порівнянні з некодованою передачею інформації. Різниця між відношенням при використанні завадостійкого кодування й при некодованій передачі інформації називається ефективністю кодування.

Висновки.

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

2. Застосування м’якого декодування завадостійких кодів створює потенційні можливості для отримання низького значення ймовірності помилки при малому відношенні сигнал/шум.

2 Дослідження шляху підвищення вірогідності передавання інформації за рахунок застосування турбокодів.

2.1 Аналіз методів турбокодування.

Турбокод являє собою паралельний каскадний код, утворений двома або більше складовими кодами [1−8]. Схема турбокодера із двома складовими кодерами зі швидкістю кодування представлена на рисунку 2.1.

Рисунок 2.1 — Схема турбокодера Нехай — двійкова інформаційна послідовність, що надходить одночасно на вхід першого кодера, на перемежувач і на вихід турбокодера. На виході кодера 1 формується послідовність перевірочних символів. Перемеженна інформаційна послідовність надходить на вхід кодера 2, на виході якого формується послідовність перевірочних символів. Відносна швидкість кодування для розглянутого випадку —. Для підвищення швидкості кодування до перевірочні послідовності надходять на схему виколювання, що робить почергове видалення перевірочних символів.

У якості складових кодерів найбільш часто використовують систематичні рекурсивні згорточні кодери (РСК), що пов’язане з відносною простотою реалізації м’якого декодування згорточних кодів й особливостями вагового розподілу кодових слів.

На рисунку 2.2, а представлений рекурсивний згорточний кодер, на рис. 1.2, б — нерекурсивний згорточний кодер. З рисунка видно, що їхня відмінність полягає в наявності зворотного зв’язку в рекурсивного згорточного кодера.

Рисунок 2.2 — Рекурсивний і нерекурсивний згорточні кодери з.

Породжувальна матриця нерекурсивного згорточного коду має вигляд.

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

На рисунку 2.2.

.

З метою спрощення запису рекурсивний згорточний код звичайно задають у восьмеричній формі - (7, 5) ₈, де (7) ₈ відповідає багаточлену зворотного зв’язку, (5) ₈ — багаточлену прямого зв’язку .

Тому що турбокод і складові його коди є лінійними, то замість розгляду дистанційного спектра можна розглядати ваговий спектр кодів. При цьому вага ненульового кодового слова буде являти собою відстань Хемінга від нульового слова. Кількість помилок, які може виправити код, визначається мінімальною відстанню Хемінга — найменшим числом позицій, на які відрізняються будь-які два кодових слова.

Основні властивості рекурсивних згорточних кодів.

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

— Для кожного існують напівнескінченні вхідні послідовності ваги 2 виду.

, (.

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

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

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

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

Для дослідження можливості підвищення достовірності переданої інформації проведемо аналіз верхньої границі ймовірності помилки турбокодів за умови їхнього декодування декодером максимальної правдоподібності.

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

(1.1).

Де — кількість кодових слів із загальною вагою ;

— середня інформаційна вага кодового слова із загальною вагою ;

Апроксимуємо (2.1) першим доданком, з огляду на тільки кодові слова з мінімальною відстанню.

(2.2).

Де — кількість кодових слів ваги ;

— середня вага інформаційних символів у кодовому слові ваги .

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

Розглянемо для прикладу турбокод із двома складовими рекурсивними згорточними кодами з породжувальними багаточленами, , і з (виколювання). В знайдено, що, ,. Імовірність помилки на біт для даного коду.

(2.3).

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

(2.4).

З аналізу виражень (2.3) і (2.4) треба, що аргумент Q функції згорточного коду більше, ніж турбокоду, що призводить до більшої крутості кривої залежності ймовірності помилки від енергетичного відношення сигнал/шум згорточного коду в порівнянні з турбокодом. Однак коефіцієнт перед функцією набагато більше для згорточного коду, чим для турбокоду, тому крива залежності ймовірності помилки від енергетичного відношення сигнал/шум турбокоду буде лежати нижче аналогічної кривої для згорточного коду.

Аналізуючи криві залежності ймовірності помилки від енергетичного відношення сигнал/шум згорточного коду й турбокоду, представлені на рисунку 2.3, які отримані шляхом моделювання для каналу з аддитивним білим гаусовским шумом (АБГШ) і двійковою фазовою маніпуляцією (ФМ), а також за допомогою виражень (2.2) і (2.4), можна зробити висновок, що при малому значенні турбокоди мають переваги перед згорточними кодами.

Рисунок 2.3 — Залежність від для турбокоду й згорточного коду:

1 — результати моделювання згорточного коду;

2 — результати розрахунку для згорточного коду за допомогою.

вираження (2.3);

3 — результати моделювання турбокоду;

4 — результати розрахунку для турбокоду за допомогою вираження (2.2).

Зі збільшенням обидві криві наближаються друг до друга через їхню різну крутість і при відношенні дБ перетинаються. Тому в області більших значень згорточні коди мають переваги перед турбокодами, що пов’язане з меншим значенням турбокодів у порівнянні зі згорточними кодами. З (2.2) також треба, що обернено пропорційнийо. Тому крива залежності від турбокоду буде знижуватися зі збільшенням (див. рис. 2.3).

Таким чином, принципова відзнака турбокодів від відомих каскадних кодів полягає в застосуванні складових рекурсивних згорточних кодів разом із процедурою перемеження, що дозволяє забезпечити малу кількість кодових слів мінімальної відстані шляхом вибору структури перемежувача. Ефективність кодування зростає зі збільшенням довжини інформаційної послідовності. Реалізація турбокодування блоками великої довжини не являє собою значних труднощів через використання складових згорточних кодів, оскільки складність згорточного кодування не залежить від довжини інформаційної послідовності. У результаті, турбокоди можуть забезпечити високу ефективність кодування при низькому енергетичному відношенні сигнал/шум. При високому енергетичному відношенні сигнал/шум ефективність кодування зменшується, що пов’язане з малою мінімальною відстанню турбокодів. Для оцінки ефективності систем з турбокодуванням зробимо вибір показника ефективності.

2.2 Вибір показника оцінки ефективності системи передавання з турбокодуванням.

Ефективність системи передавання характеризується великою сукупністю показників ефективності, записуваної у вигляді вектора Оптимальною вважається така система, який відповідає найбільше (найменше) значення цільової функції від приватних показників ефективності :

Де — узагальнений показник ефективності;

— цільова функція системи.

Оскільки ефективність системи визначається швидкістю й достовірністю переданої інформації, виберемо як часткові показники ефективності коефіцієнти й, що визначають енергетичну й частотну ефективність Де — швидкість передачі інформації;

— відношення сигнал/шум, , — потужність сигналу, спектральна щільність потужності шуму;

— смуга частот каналу.

При використанні завадостійкого кодування в каналі з адитивним білим гаусовським шумом (АБГШ) коефіцієнти й мають вигляд:

Де , — відносна швидкість кодування, — питома швидкість сигналів у каналі, що визначається видом модуляції (для двійкової ФМ ,).

Узагальненим показником ефективності виберемо коефіцієнт використання пропускної здатності каналу (інформаційну ефективність):

(2.5).

Де — пропускна здатність каналу.

Використовуючи формулу Шенона для безперервного каналу з АБГШ.

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

(2.6).

Отримане вираження є граничним і відбиває найкращий обмін між й. При цьому ефективність може змінюватися в межах від 0 до (для двійкової ФМ), а ефективність обмежена зверху: при (1,6 дБ).

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

Застосування завадостійкого кодування дозволяє понизити або при заданому значенні підвищити енергетичну ефективність системи. Тому остаточне рішення про застосування завадостійкого коду й відповідного алгоритму декодування можна винести лише після порівняння показників ефективності системи з кодуванням і без нього, для чого визначимо енергетичний виграш від кодування (ЕВК) як.

Де — енергетична ефективність обраної системи;

— енергетична ефективність еталонної системи.

Криві залежності ?_N від ?_N для безперервного каналу (відсутність квантування сигналу з виходу демодулятора й передача безперервних повідомлень, ентропія яких максимальна [5, 7]), двійкового дискретно-безперервного каналу (відсутність квантування сигналу з виходу демодулятора, передача рівноймовірних двійкових символів [5, 7] - м’які рішення демодулятора) і двійкового симетричного каналу (передача рівноймовірних двійкових символів, квантування сигналу з виходу демодулятора два рівні - жорсткі рішення демодулятора) представлені на рис. 1.4, з якого слід, що використання м’яких рішень демодулятора дозволяє одержати енергетичний виграш до 2 дБ у порівнянні із жорсткими рішеннями демодулятора.

При проведенні аналізу ефективності на основі узагальненого показника ефективності, у якості якого будемо використовувати інформаційну ефективність, виберемо найбільш доцільний варіант системи виходячи із принципу мінімуму витрат [11, 15]. Під витратами будемо вважати складність декодування (кількість операцій декодування, що доводиться на один інформаційний символ), оскільки вона є основним обмежуючим фактором застосування турбокодів.

Для кожного варіанта системи будемо визначати інформаційну ефективність і складність декодування. Після чого проведемо аналіз за принципом мінімальних витрат:

(2.7).

Де — припустима область зміни інформаційної ефективності;

— задане значення ймовірності помилки.

Рисунок 1.4 — Залежність ?_N від ?_N.

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

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

2.3 Аналіз алгоритму ітеративного декодування турбокодів.

Будемо вважати, що використовується двійкова ФМ у каналі без пам’яті з АБГШ, а турбокод складається із двох складових згорточних кодів. Нехай декодування турбокоду здійснюється ітеративним турбодекодером [5], схема якого представлена на рисунку 2.5.

Позначимо послідовності прийнятих інформаційних і перевірочних символів першого й другого кодерів як.

, ,.

Де;; ;, ,.

— випадкові величини, що мають нормальний розподіл з нульовим середнім значенням і дисперсією .

Рисунок 2.5 — Схема ітеративного турбодекодера із двома складовими декодерами систематичних згорточних кодів На відміну від декодера каскадного коду, у якому складові декодери приймають незалежні рішення, складові декодери ітеративного турбодекодера обмінюються м’якими рішеннями з метою уточнення результату декодування. М’які рішення першого декодера після перемеження використовуються як апріорна інформація для другого декодера. М’які рішення другого декодера після деперемеження використовуються як апріорна інформація для першого декодера. Подібний обмін м’якими рішеннями між декодерами назвемо ітерацією. Остаточне рішення турбодекодером приймається після деякої кількості ітерацій з використанням прийнятої інформаційної послідовності й м’яких рішень першого та другого складових декодерів.

Інформаційний символ може приймати значення 0 й 1 з апріорною ймовірністю.

й, причому.

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

.

(2.8).

де Вираження (2.8) справедливо, якщо не залежить від, а залежить тільки від для всіх, що завжди виконується для каналу без пам’яті.

Нехай — відношення апостеріорних імовірностей інформаційних символів після фази ітерації (,), що будемо називати апостеріорним відношенням правдоподібності інформаційного символу або м’яких рішень декодера.

Вираження для має вигляд Використовуючи вираження (2.7), одержимо.

. (2.9).

Позначимо Будемо називати апріорним відношенням правдоподібності інформаційного символу або апріорною інформацією. На першій фазі першої ітерації апріорна інформація про передані символи звичайно відсутній, тому.

а.

Нехай Будемо називати внутрішнім відношенням правдоподібності інформаційного символу або внутрішньою інформацією. Протягом всіх ітерацій. Для каналу без пам’яті з АБГШ і двійкової ФМ внутрішнє відношення правдоподібності визначається як:

де.

Позначимо.

(2.10).

Будемо називати зовнішнім відношенням правдоподібності інформаційного символу або зовнішньою інформацією.

Для другої фазий ітерації вираження (1.8) приведемо до виду:

.

Де — внутрішня інформація після перемеження;

— зовнішня інформація після перемеження.

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

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

На рисунку введені наступні позначення.

, , де, ,.

Рисунок 2.6 — Схема турбодекодера У загальному випадку турбодекодер може містити й більшу кількість складових декодерів, що призводить до значного росту складності декодування, через що в цей час не використовують турбодекодери з кількістю складових декодерів більше двох.

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

2.4 Аналіз алгоритмів м’якого декодування згорточних кодів Відомі наступні алгоритми м’якого декодування згорточних кодів: МАР (maximum a posteriori probability), log-MAP, min-log-MAP й SOVA (soft output Viterbi algorithm). Проведемо аналіз зазначених вище алгоритмів для випадку декодування систематичного згорточного коду з і пам’яттю, припускаючи використання двійкової ФМ у каналі без пам’яті з АБГШ.

MAP алгоритм. MAP алгоритм був запропонований в [1, 6]. В розроблена модифікація MAP алгоритму для декодування систематичних згорточних кодів.

Нехай інформаційний символ асоціюється з переходом кодера зі стану в стан. Будемо вважати, що послідовність інформаційних символів складається з незалежних символів, які можуть приймати значення 0 й 1 з апріорною ймовірністю й,. Початковий і кінцевий стани кодера — нульові. Послідовність необхідна для установки кодера в кінцевий нульовий стан.

Визначимо прийняту послідовність:

.

Де — прийняті символи під час ;

;

 — незалежні випадкові величини, що мають нормальний розподіл з нульовим середнім значенням і дисперсією .

Визначимо відношення правдоподібності інформаційного символу в такий спосіб:

(2.11).

Де — апостеріорна ймовірність, .

Правило прийняття жорстких рішень визначимо як:

Відношення правдоподібності представимо в такий спосіб:

(2.12).

Де — пряма метрика стану під час ;

— зворотна метрика стану під час ;

— метрика гілки.

Метрики, можна обчислити рекурсивно:

Метрику гілки представимо як.

(2.13).

На рисунку 2.7 представлені схеми обчислення й, а на рисунку 2.8 — схема обчисленнятого складати знаменателя, що, у вираженні (2.12). На рисунку жирними лініями показані всі шляхи, які визначають, і .

Вираження (2.13) для АБГШ каналу з дисперсією шуму приймає вид.

(2.14).

Де — перевірочний символ для даного інформаційного символу й стану ;

— константа, яку можна не враховувати, тому що вона входить у чисельник і знаменник вираження (2.12).

Рисунок 2.7 — Схема обчислення й.

Рисунок 2.8 — Шляхи в ґратчастій діаграмі, які використовуються при обчисленні, і.

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

Log-MAP алгоритм. Один зі шляхів зменшення складності декодування МАР алгоритму — це здійснення обчислень у логарифмічній області. У цьому випадку всі операції добутку й ділення заміняються операціями додавання й вирахування, які реалізувати значно простіше. Операція додавання перетвориться в Е операнд, що визначимо в такий спосіб.

(2.15).

Де,, .

Функція швидко убуває й має максимальне значення (для). Якщо значенням функції у вираженні (1.15) можна зневажити й установити .

Уведемо позначення:, ,,. Перетворимо вираження (2.12) з урахуванням уведених позначень.

(2.16).

(2.17).

(2.18).

Де — константа;

— апріорна інформація log-MAP декодера;

Вираження (2.16) з урахуванням уведених позначень прийме вид де — зовнішня інформація log-MAP декодера.

Таким чином, здійснення обчислень у логарифмічній області дозволяє замінити операції множення й розподілу операціями додавання й вирахування. При цьому операція додавання заміняється Е операндом, якому можна представити за допомогою операції знаходження мінімального значення й деякого виправлення, що може бути задана таблично. Характеристики log-MAP декодера такі ж, як й в MAP декодера.

Min-log-MAP алгоритм. Спростимо вираження (2.16 — 2.18), установлюючи й замінивши Е операнд функцією знаходження мінімального значення:

Min-log-MAP алгоритм є субоптимальним алгоритмом у порівнянні з log-MAP алгоритмом.

Використання складових min-log-MAP декодерів у турбодекодері зменшує складність декодування, однак призводить до збільшення ймовірності помилки декодування й зменшенню енергетичного виграшу від кодування на 0,3?0,6 дБ.

SOVA алгоритм. Алгоритм SOVA являє собою модифікацію алгоритму Вітербі.

Нехай є послідовність спостережень дискретного за часом марковського процесу з кінцевим числом станів, спостережуваного в каналі без пам’яті з АБГШ. Знайдемо послідовність станів,, для якої апостеріорна ймовірність максимальна.

Нехай — метрика шляху, що веде в стан. Метрика може бути обчислена рекурсивно.

. (2.19).

Уведемо позначення, .Представимо (2.19) з урахуванням уведених позначень як Де, , — константа, який можна зневажити.

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

У ґратчастій діаграмі двійкового згорточного коду з існують два шляхи, що ведуть у стан. Будемо називати ці шляхи шляхами, що зливаються, у стані .

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

М’яке рішення для шляху, що вижив:

.

Де — різницева метрика що вижили й відкинутого шляху, .

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

М’яке рішення SOVA алгоритму визначаються як добуток жорстких рішень алгоритму Вітербі на найменшу з різницевих метрик:

Перевага турбодекодера зі складовими SOVA декодерами — найменша складність декодування. Енергетичний програш — найбільший, котрий становить 0,5?1,0 дБ у порівнянні з МАР або log-MAP складовими декодерами.

Висновки.

1. Проведений аналіз методів турбокодування показав, що турбокоди можуть забезпечити високу ефективність кодування при низькому енергетичному відношенні сигнал/шум.

2. Для оцінки ефективності турбокодування доцільно застосовувати узагальнений показник ефективності - коефіцієнт використання пропускної здатності каналу (інформаційна ефективність) на основі часткових показників ефективності - енергетичної й частотної ефективності. Порівняння показників ефективності системи з кодуванням і без нього будемо робити на основі аналізу енергетичного виграшу від кодування. Вибір найбільш прийнятного варіанта системи будемо робити на основі аналізу системи по двох показниках — інформаційної ефективності й складності декодування виходячи із принципу мінімуму витрат.

3. З аналізу алгоритму ітеративного декодування турбокодів треба, що для реалізації ітеративного турбодекодера необхідні алгоритми м’якого декодування складових кодів, що дозволяють оцінити апостеріорні ймовірності інформаційних символів.

4. Із проведеного аналізу алгоритмів м’якого декодування згорточних кодів виходить, що найбільшою складністю декодування володіють МАР й log-MAP алгоритми. Подальше спрощення log-MAP алгоритму приводить до min-log-MAP алгоритму, що є субоптимальним у порівнянні з log-MAP алгоритмом. Енергетичний програш турбодекодера зі складовими min-log-MAP декодерами становить 0,3?0,6 дБ у порівнянні з МАР або log-MAP декодерами. Найменшу складність декодування забезпечує SOVA алгоритм, що є модифікацією алгоритму Вітербі. Енергетичний програш турбодекодера зі складовими SOVA декодерами найбільший, і становить 0,5?1,0 дБ у порівнянні з МАР або log-MAP декодерами.

3. Дослідження модифікованого алгоритму ітеративного декодування турбокодів.

3.1 Модифікований алгоритм ітеративного декодування турбокодів.

Основними алгоритмами декодування, що виробляють м’які рішення, є МАР, log-MAP, min-log-MAP й SOVA алгоритми. Алгоритми МАР й log-MAP дозволяють забезпечити найменшу ймовірність помилки декодування. Недоліком МАР алгоритму є висока складність декодування. Використання log-MAP алгоритму дозволяє спростити апаратну реалізацію турбодекодера, однак складність декодування усе ще залишається високою. Тому навіть при використанні сучасної елементної бази застосування МАР й log-MAP алгоритмів приводить до зниження швидкості обробки інформації з порівняння з min-log-MAP й SOVA алгоритмами.

Проведений у розділі 2 аналіз показав, що використання в турбодекодері тільки субоптимальних складових декодерів (min-log-MAP, SOVA) хоча й дозволяє зменшити складність декодування, але приводить до значного збільшення ймовірності помилки декодування.

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

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

Нехай — м’яке рішення SOVA декодера для інформаційного символу. Умовну щільність розподілу м’яких рішень — апроксимуємо нормальним законом розподілу:

; (3.1).

(3.2).

Де — середнє значення м’яких рішень;

— дисперсія м’яких рішень.

Визначимо логарифм відношення правдоподібності для інформаційного символу в такий спосіб:

(3.3).

Використовуючи формулу Байєса й припускаючи, що.

перетворимо вираження (3.3).

(3.4).

Підставляючи (3.1) і (3.2) в (3.4), одержимо [15]:

(3.5).

З (3.5) треба, що м’які рішення SOVA декодера необхідно додатково помножити на коефіцієнт:

(3.6).

Для обчислення коефіцієнта необхідна оцінка середнього значення й дисперсії м’яких рішень SOVA декодера на кожній ітерації. Діапазон зміни коефіцієнта для малих значень становить 0,3?0,7, тому пропонується замість обчислення коефіцієнта за допомогою вираження (3.6) використати постійне значення, що дозволить поліпшити характеристики SOVA декодера при збереженні низької складності декодування.

Однак навіть із введенням коефіцієнта ймовірність помилки залишається вище, ніж в log-MAP турбодекодері. Тому з метою зниження як складності декодування, так й імовірності помилки будемо використовувати складові декодери з різними алгоритмами декодування — log-MAP й SOVA. Застосування різних складових декодерів призведе до неоднакового використання виправляючої здатності складових кодів і збільшенню ймовірності помилки. Для усунення цього будемо змінювати на кожній ітерації алгоритм декодування складових кодів. Схема модифікованого алгоритму ітеративного декодування турбокодів представлена на рисунку 3.1. На рисунку 3.2 представлена схема модифікованого ітеративного турбодекодера, у якому використовуються різні складові декодери, і змінюється на кожній ітерації алгоритм декодування складових кодів. При цьому м’які рішення SOVA декодера, які є апріорною інформацією для log-MAP декодера, помножуються на постійний коефіцієнт А.

Рисунок 3.1 — Схема модифікованого алгоритму ітеративного декодування турбокодів.

Рисунок 3.2 — Схема модифікованого ітеративного турбодекодера.

3.2 Оцінка ефективності розробленого алгоритму ітеративного декодування турбокодів.

3.2.1 Розробка програмної моделі системи передавання з турбокодуванням та оцінка достовірності результатів моделювання.