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

Змн.

Арк.

№ докум.

Підпис

Дата

Арк.

ОГЛЯД НАУКОВО  ТЕХНІЧНОЇ ЛІТЕРАТУРИ ПО ЗАВАДОСТІЙКОМУ КОДУВАННЮ

1. Класифікація завадостійких кодів

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

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

а) повторення передавання,

б) одночасне передавання даних по декільком каналам, в) використання завадостійких кодів,

У деяких випадках застосовують і комбінації цих способів.

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

Усі відомі в даний час коди умовно ділять на дві групи: ефективні і завадостійкі.

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

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

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

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

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

Рис.1. Класифікація завадостійких  кодів.

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

До неперервних кодів відносять і згорткові коди, в яких для кожного вхідного символу пристрій кодування видає декілька перевірочних, які визначають сумуванням по модулю два цього символа та k-1 попередніх інформаційних символів. Рекурентні коди дозволяють коректувати групові помилки у каналах зв’язку.

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

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

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

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

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

Найбільш відомі серед систематичних кодів - коди Хемінга, які історично були побудовані раніше інших кодів та відіграли видатну роль у розвитку теорії коректуючих кодів. У цих кодах використовується принцип перевірки на парність визначеного набору інформаційних символів. Коди Хемінга з кодовою відстанню d_min = 3 дозволяють виправити одиничну помилку. Розширені коди Хемінга доповнюють код з кодовою відстанню d_min  = 3 ще одною, загальною перевіркою кодової комбінації на парність та ще одним перевірочним символом. Це дозволяє збільшити мінімальну кодову відстань до чотирьох (d_min = 4).

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

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

В даній  роботі використаний згортків код, так  як він має ряд переваг:

• Процес кодування та декодування здійснюється безупинно
• Невелика надлишковість
• Ефективність в каналі з білим шумом.

2. Аналіз згорткових кодів

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

Канали зв'язку в стандарті GSM поділяються на фізичні і логічні. Фізичний канал утворюється шляхом комбінування тимчасового і частотного розділення сигналів. 
До формування фізичного каналу повідомлення дані, представлені в цифровому вигляді, групуються і об'єднуються в логічні канали двох типів: 
- Канал зв'язку - для передачі кодованої мови і даних; 
- Канал управління - для передачі сигналів управління і синхронізації. 
Кодування і перемеження є важливими ступенями тракту обробки інформаційних цифрових сигналів і сигналів управління. У цифрових ССРЗ здійснюється перетворення аналогового мовного сигналу в цифрову послідовність, яка піддається шифруванню та кодування, що необхідно для захисту інформації від помилок в процесі передачі і прийому. Для цього використовуються:

- Блочне кодування - для швидкого виявлення помилок при прийомі; 
- Згорткове кодування - для виправлення одиночних помилок; 
- Перемеження - для перетворення пакета помилок в одиночні помилки. 
У цифрових ССРЗ кодуються всі передані по радіоканалу сигнали. В аналогових ССРЗ кодують цифрові сигнали управління.

При кодуванні переслідують різні цілі. Найнижчий рівень має виявлення помилок в повністю прийнятому сигналі. У порівнянні з ним більш високим рівнем має виявлення помилок в окремих сегментах сигналу, яке може бути виконано за допомогою простих блокових кодів, наприклад, з перевіркою на парність. У сучасних системах використовують коди з виправленням помилок. Це можуть бути блокові коди (канали сигналізації в NMT-450, DECT) і згорткові коди (GSM, системи з кодовим поділом - CDMA). Вибір коду визначає велике число чинників: характеристики каналів, швидкість передачі, вид модуляції і т. п. Важливе значення набуває елементно-технологічна база. Застосування швидкодіючих процесорних НВІС відкрило шлях до використання потужних згорткових кодів при обробці сигналів у реальному часі. Згорткові коди добре виправляють випадкові поодинокі помилки, але дають погані результати при пакетах помилок. Тому згорткове кодування і поєднують з перемеженям (перетасовуванням) інформаційних символів, що забезпечує перетворення пакетів помилок в одиночні.

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

У різних логічних каналах використовуються різні згоркові коди, оскільки швидкості передачі і вимоги щодо захисту від помилок також різні. Для спрощення процедур кодування і декодування при формуванні кодів використовуються тільки кілька поліномів. Це дозволяє використовувати в стандарті GSM згортковий код з однією швидкістю R = 1/2. У ряді режимів для вирівнювання швидкості в мовному каналі до R = 1/2 застосовують проріджування, тобто періодичний пропуск (перфорацію) кодованих символів. Оскільки складність декодування за найбільш вигідним, з точки зору реалізації, алгоритму Вітербі зростає експоненціально з збільшенням довжини кодового обмеження l, то типові значення ДКО малі і лежать в інтервалі l = 3 – 10.

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

Для істотного поліпшення завадостійкості при використанні згорткових кодів необхідно збільшувати швидкість передачі символів, а отже, і ширину смуги, наприклад, в 2 рази при відносній швидкості передачі коду 1/2 або в 4/3 рази при відносній швидкості 3/4. Таким чином, застосування згорткових кодів виявляється особливо вигідним в супутникових системах зв'язку, енергетичний потенціал яких обмежується потужністю бортового ретранслятора, тобто в каналах, де визначальним фактором є обмеження потужності, а не смуги частот. В системах з обмеженою енергетикою кодування дозволяє зменшити необхідне відношення сигнал - шум, оптимальним чином розподілити потужність ретранслятора між каналами і збільшити число каналів.

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

Кодер загорткового коду містить тактовий регістр пам’яті для збереження визначеного числа інформаційних символів і перетворювач вхідної інформаційної послідовності у вихідну кодову послідовність. Структурна схема кодера ЗК (7.5) зображена на малюнку 1.1.

Мал.1.1 – Структурна схема кодера

Послідовність кодування детально розписана в  таблиці 1.

Таблиця 1 - Процес кодування послідовності  інформаційних бітів 01101000

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

Кодові  грати цього коду показані на мал. 1.1. При його складанні враховано, що кодер містить пам'ять у  вигляді дворозрядного регістра. Кожному з чотирьох можливих станів цього регістра відповідає один з  чотирьох вузлів решітки. Тому лівий символ в позначенні вузла дорівнює останньому інформаційному біту, вже записаному в регістр. При записі в регістр чергового інформаційного символу регістр міняє стан на одне з двох сусідніх. Цей перехід позначений ребрами грат. Порядок вузлів вибраний таким, що при нульовому поточному інформаційному символі (а=0) перехід в наступний стан відповідає верхньому ребру, а при = 1 - нижньому.

Рисунок 1.1 - Кодові грати

Кожній  інформаційній послідовності відповідає певний шлях на кодових гратах і  кодова послідовність. Наприклад, вхідним  інформаційним бітам 01100 відповідає кодове слово 00 11 01 01 11, якому відповідає на мал. 1.1 шлях, відмічений жирною лінією.

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

Алгоритм Вітербі реалізує оптимальне (максимально правдоподібне) декодування  як рекурентний пошук на кодових гратках шляху, найближчого до послідовності, що приймається. На кожній ітерації алгоритму Вітербі зіставляються два шляхи, що ведуть в даний стан (вузол гратки). Найближчий з них до прийнятої послідовності зберігається для подальшого аналізу. Нехай передається нульове кодове слово, а в каналі виникла трикратна помилка, так що прийнята послідовність має вигляд 10 10 00 00 10 00 ... 00 .... Результати пошуку найближчої дороги після прийому 14 елементарних блоків показані на рисунку 1.2.

Рисунок 1.2 - Приклад роботи алгоритму Вітербі

ТЕОРЕТИЧНА  ЧАСТИНА

2.1.

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

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

Кадри інформаційних символів кодуються кадрами кодових символів довжиною n_o символів. При цьому кодування кадру інформаційних символів в кадр кодового слова проводиться з урахуванням попередніх m кадрів інформаційних символів. Процедура кодування, таким чином, пов'язує між собою послідовні кадри кодових слів. Передана послідовність стає одним напівнескінченних кодовим словом. 
Розвиток теорії і практики згорткових кодів помітно відрізняється від розвитку блокових кодів. При побудові блокових кодів і методів їх декодування широко використовувалися алгебраїчні методи. У разі згорткових кодів це не так. Більшість хороших згорткових кодів було знайдено шляхом перегляду за допомогою ЕОМ великого числа кодів і подальшого вибору кодів з хорошими властивостями. Декодування згорткових кодів проводиться методами, близькими до методів максимального правдоподібності, причому в цьому випадку вони реалізуються досить просто.

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

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

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

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

-   k = (m+1) • k₀ - інформаційна довжина слова;

-   n = (m+1) • n₀ - кодова довжина блоку.

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

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

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

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

з відносною швидкістю R = 1/2.

Рисунок 2.1 - Схема кодера для згорткового коду з відносною швидкістью R=1/2.

Згортковий кодер належить до класу пристроїв, відомих як кінцевий автомат. Це загальна назва дана системам, які мають пам'ять про минулі сигнали. Прикметник "кінцевий" показує, що існує обмежена кількість станів, що може виникнути в системі. Що мається на увазі під станом в системах з обмеженим їх числом? У більш загальному сенсі стан включає найменшу кількість інформації, на основі якої разом з поточними вхідними даними можна визначити дані на виході системи. Стан дає певне уявлення про минулі події (сигналах) і про обмеженому наборі можливих вихідних даних в майбутньому. Майбутні стани обмежуються минулими станами.

Одним із способів подання простих кодуючих пристроїв є діаграма стану; таке подання кодера показано на малюнку 2.2. Стан показане в рамках діаграми, представляє собою можливе вміст К-1 крайніх правих розрядів регістра, а шлях між станами - кодові слова гілок на виході, що є результатом переходів між такими станами. Стани регістра вибрані наступними: а=00, b=10, c=01, d=11; діаграма показана на рис. 2.2, ілюструє всі можливі зміни станів для кодера показаного на рис. 2.2. Існує всього два вихідних з кожного стану переходу, що відповідають двом можливим вхідним бітам. Далі для кожного шлях між станами записано кодове слово на виході, пов'язане з переходами між станами. При зображенні шляхів, суцільною лінією прийнято позначати шлях, пов'язаний з нульовим вхідним бітом, а пунктирною лінією - шлях, пов'язаний з одиничним вхідним бітом. Зазначимо, що за один перехід неможливо перейти з даного стану в будь-яке довільне. Так як за одиницю часу переміщається тільки два можливих переходу між станами, до яких регістр може переходити за час проходження кожного біта. Наприклад, якщо стан кодера - 00, то при наступному зміщенні можливе виникнення тільки станів 00 або 10.

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

   0        8

1000  1000

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

Схема кодера показана на малюнку 2.1.

Побудуємо таблицю станів кодера:

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

V1 = S1 + S2 + S3;

V2 = S1 + S3.

Кодування по таблиці станів здійснюється наступним чином. За розрядами вхідної кодової комбінації (U) визначається стан кодера (S1, S2, S3) на кожному такті, а по ним розряди на виході кодера (V1, V2). Таким чином, з таблиці отримуємо:

Вхід     1 0  0   0  1  0  0  0

Вихід 1110110011101100

Кодування по спрямованому графу:

Побудуємо спрямований граф:

Малюнок 2.2 – Діаграма станів кодера (степень кодування R=1/2).

Закодуємо з даного графу ту ж саму послідовність, що і в таблиці станів кодера. Для цього, починаючи з початкового стану (S1 = 0, S2 = 0), необхідно переміщатися по стрілках в залежності від того, які значення кодера U (0 або 1) надходять на вхід (тобто розряди вихідної кодової послідовності) до відповідного стану S1 і S2. Кожен такий перехід відповідає отриманню деякої кодової комбінації вихідних розрядів (V1 і V2) сукупність яких і буде представляти собою вихідну кодову послідовність, тобто вихід кодера. Таким чином, отримуємо:

Вхід    1   0  0  0  1  0  0  0

Вихід 1110110011101100.

2.2  Синдромное декодування згорткових кодів

Припустимо, що нами прийнята напівнескінченна послідовність r, що складається зі слова згортального коду і вектора помилки:

r = U + e.        (2.1)

Аналогічно тому, як це робиться для блокових кодів, можна обчислити синдром прийнятої послідовності:

S = r•H = e•H.                                             (2.2)

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

Малюнок 2.3 - Схема декодера для згорткового (12,9)-кода Вайнера-Еша.

Виправлення помилок за допомогою даного декодера проводиться на сегментах з трьох кодових кадрів - п = 12.

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