Svertochnye_kody - Стор 4
Важливою характеристикою коду, що повністю визначає його коригувальні властивості, є спектр вільних відстаней коду, тобто перерахування кількості кодових послідовностей, що мають дане значення вільної відстані [15, 23].
Мінімальну вільну відстань d L згорткового коду можна визначити за допомогою діаграми станів або гратової діаграми для відповідного кодера.
Оскільки згортковий код є лінійним кодом, то серед різних шляхів на гратковій діаграмі коду обов'язково буде шлях з нульовою вагою (нульовий шлях), тобто шлях, послідовність кодових символів якого повністю складається з нулів. Отже, мінімальна вільна відстань згорткового коду дорівнюватиме мінімальної кількості одиниць, тобто мінімальної ваги шляхів, які розходяться і зливаються з нульовим шляхом. Граткову діаграму коду можна використовувати для визначення мінімальної вільної відстані, якщо для кожної її гілки записати вагу відповідних кодових символів на виході кодера, а потім підрахувати вагу шляхів, що розходяться та зливаються з нульовим шляхом. На рис. 5.1 показана подібна граткова діаграма з мітками ваг для кодера згорткового коду (рис. 2.5 б), побудована на базі гратової діаграми (рис. 4.2).
Мал. 5.1. Граткова діаграма з мітками ваг для кодера (рис. 2.5, б)
З неї можна бачити, що з усіх ненульових шляхів, що розходяться і зливаються з горизонтальним нульовим, буде один, що має вагу 5, що відходить від нульового шляху на 3 гілки
два шляхи, що відходять від нульового шляху на 4
та 5 гілок і мають вагу w = 6
Таким чином, мінімальна вага ненульового шляху для даного згорткового коду дорівнює 5, отже,мінімальна вільна відстань цього коду d min = 5. Очевидно, цей код може виправити (див. далі п. 11) будь-які дві помилки, що відбулися в каналі зв'язку, оскільки ці дві помилки можуть призвести до того, що послідовність кодових символів, що приймається, буде мати хеммінгова відстань від переданої послідовності, що дорівнює двом, а від усіх інших послідовностей ця відстань буде принаймні не менше трьох. Отже, при декодуванні мінімуму хеммінгової відстані будь-які дві помилки цим кодом будуть виправлені.
Очевидно потенційно коригуюча здатність згорткового коду тим вища, чим більша його мінімальна вільна відстань. Тому структуру кодера згорткового коду, тобто його багаточлени, що породжують, прагнуть вибрати таким чином, щоб максимізувати мінімальну вільну відстань коду. Це за інших рівних умов забезпечує найвищу здатність коригувального згорткового коду при його декодуванні по максимуму правдоподібності, зокрема, при декодуванні за алгоритмом Вітербі (див. розд. 8.3).
Поряд з оцінкою мінімальної вільної відстані згорткового коду по гратчастій діаграмі, можна значення d min визначити за послідовністю вихідних символів B(X) – на повній довжині кодового обмеження l П (5.7).
У табл. 5.1 на підставі побудови B(X) на інтервалі l П в останній колонці наведено значення d min відповідних кодів, які рівні ваги w послідовностей B(X):
де W l П - вага кодової послідовності на повній довжині кодового обмеження l П.
Звернімо увагу на те, що для кодера на рис. 2.5 б (другий рядок табл. 5.1) вихідна послідовність B(x) по структурі повністю збігається зі структурою вихідного коду при вступі на вхід кодера послідовності A(X) =1000 ... для гратової діаграми (рис. 4.2), так як шлях по решітці визначає тотожну B (X) = 111011000 ....
Таким чином, мінімальна вільна відстань d min для різних варіантів коротких згорткових кодів можна знайти (5.14), визначивши структуру вихідної послідовності B(X) на довжині l П (табл.5.1.), що і робиться при виконанні лабораторної роботи.
11. Коригуюча здатність коду визначається кратністю (кількістю) виправлюваних g І помилок, під якою розуміють гарантоване число помилок у кодових комбінаціях, що виправляються заданим кодом. Очевидно, що чим більша кратність g, тим ефективнішим є код. Хеммінг визначив просту залежність між значенням мінімальної кодової відстані та кратністю помилки. Прийнята, уражена на заваді кодова послідовність ототожнюється на приймальній стороні з тією з інформаційних, на яку вона найбільше схожа, тобто з тією, від якої вона відрізняється меншим числом символів. Хеммінг показав, що це для блокових кодів виконується за умови
звідки випливає, що
x означає цілу частину числа x.
При згортковому кодуванні кратність помилок, що виправляються, визначається аналогічним виразом з урахуванням мінімальної вільної відстані d L при обробці кодових послідовностей з довжиною L. Якщо в послідовності відбулося не більше g І помилок, при-
чим g І задовольняє нерівності
то помилки виправляються.
Зокрема, при довжині L кодової послідовності, що дорівнює повній довжині кодового обмеження l П відповідно до (5.11),
що збігається з (5.15) і (5.16) для блокових кодів, так як постійна довжина блокового коду еквівалентна повній довжині кодового обмеження для згорткових кодів.
12. Потужність коду визначаєздатність кодів виправляти множинні, поодинокі та багаторазові помилки, що виникають у кана-
ле зв'язку. Потужність коду залежить від вхідної довжини кодового обмеження l (5.5) і від виду поліномів, що утворюють. [23] показано, що ймовірність виправлення помилок при декодуванні в явному вигляді пов'язана з вільною кодовою відстанню d L . Так, для розглянутого раніше кодера (рис. 2.5 б), що генерує код (2, 1, 3) з утворюють полі-
номами G 1 і G 2 (табл. 5.1), величина d min = 5. Для коду (2, 1, 5) з поліномами, що утворюють
G 1 (X) = 1 + X 3 + X 4
який використовують при кодуванні мовного сигналу в системі стільникового зв'язку GSM, d min = 7. У ще більш потужному коді (2, 1, 7) з поліномами, що утворюють
G 1 (X) = 1 + X 2 + X 3 + X 5 + X 6
(X) = 1 + X + X 2 + X 3 + X 6
застосовуваному в системах супутникового зв'язку d min = 10. Отже, коди з великим кодовим обмеженням l є
13. Енергетичний виграш коду η визначає виграш по завадостійкості при застосуванні коригуючого кодування. Як правило, у системах припускають застосування символів з двопозиційної фазової модуляцією використовує протилежні сигнали з початковою фазою 0° при передачі символу "1" і 180° при передачі "0" (або навпаки).
Для отримання заданого значення ймовірності помилкового прийому одного символу p 1 в інформаційній послідовності треба забезпечити на виході демодулятора приймача деяке мінімально необхідне відношення сигнал/шум.
При передачі інформації з коригуючим кодуванням замість k інформативних символів за заданий час потрібно передача n символів з додаванням перевірочних за той же час при тому ж рівні сигналів.
При цьому доведеться скорочувати тривалістьсимволів під час передачі (при швидкості R = 1/3 – втричі), що вимагатиме розширення смуги частот у n/k раз. Вихідне задане значення ймовірності p 1 забезпечуватиметься вже при іншому відношенні сигнал/шум. Різниця відносин сигнал/шум при застосуванні кодування і без нього при її поло-
ном значенні визначає енергетичний виграш коду, що виражається в децибелах.
Швидка орієнтовна оцінка енергетичної ефективності з метою оперативного порівняння кодів проводиться за асимптотично-
му енергетичному виграшу від кодування (АЕВК)
η = 10lgRd min (дБ),
де R = k/n - відносна швидкість коду; d min – мінімальна кодова відстань.
Величина АЕВК характеризує ЕВК за ймовірності p 1 → 0 і є верхньою межею реального ЕВК при p 1 ≠ 0 [23].
У табл. 5.2 наведено основні характеристики коротких згорткових кодів зі швидкістю R = 1/2, із зазначенням значень АЕВК.
Коди задані багаточленами, що породжують, у вісімковій формі запису і вказані значення пам'яті коду (5.5) і мінімальної кодової відстані (5.11).
Виграш від кодування може бути використаний найбільш ефективним способом, наприклад шляхом зменшення потужності передавачів в системах зв'язку, зменшення розмірів антен або збільшення швидкості передачі.
Як зазначається в [15], для отримання значного виграшу від кодування найбільш придатні згорткові коди з малою довжиною кодового обмеження та декодування за алгоритмом Вітербі. Зокрема, добре відомий код R = 1/2, l = 6, який має ЕВК 5дБ при p 1 = застосовується в багатьох системах при різних швидкостях передачі даних.
14. Складність кодеків згорткових кодів визначає можливість практичної реалізації кодера на стороні передачі та декодераза прийому системи зв'язку.
Складність згорткового кодера визначається числом його найпростіших елементів, якими є розряди в регістрі зсуву, суматори по модулю 2 і суматорів зв'язку з розрядами зсувів. Найчастіше довжина регістру зсуву має порядок кількох десятків одиниць, кожен суматор зв'язується приблизно з половиною розрядів регістру. Тому можна вважати, що складність кодера згортки лінійно залежить від довжини регістра m або від довжини кодового обмеження l. Практична реалізація пристрою, що складається з декількох десятків або сотень найпростіших елементів, нескладно.
Складність декодерів визначається шляхом декодування. В даний час використовується три основних методи декодування згорткових кодів: граничне, аналогічне мажоритарному методу декодування блокових кодів, послідовне та декодування за алгоритмом Вітербі.
Найбільш простими у реалізації є алгоритми мажоритарного декодування як блокових, і згорткових кодів. Складність реалізації декодерів зростає практично пропорційно до повної довжини кодового обмеження l П (5.7). Декодери досить прості при виправленні помилок невисокої кратності (g = 1, 2). Однак подальше збільшення кратності помилок, що виправляються, призводить до значного ускладнення схемної побудови декодерів, яке не виправдовується зростанням величини ЕВК.
Найбільшу складність мають декодери Вітербі, об'єм обчислень (складність) яких зростає експоненційно із зростанням довжини кодового обмеження. З використанням алгоритму Вітербі збільшення ДКО на одиницю більш як удвічі збільшує обсяг декодера, але дає приріст ЕВК – 0,4 …0,5 дБ [23]. Тому декодери, що практично використовуються, виконуються для кодів з ДКО l ≤ 7…8. ПідвищенняШвидкодія таких декодерів можлива при розпаралелювання процедур декодування, а зниження обсягу - за рахунок переходу до мікропроцесорної техніки.
15. Надійність кодування – визначається ймовірністю правильного декодування інформаційної послідовності, що передається. Очевидно, що не всякий вибір зв'язків у згортковому кодері призведе до гарної побудови кодера. Наприклад, свідомо погано пов'язувати кожен із суматорів з тими самими розрядами регістру.
Значною мірою надійність кодування визначається сукупністю кодових відстаней між послідовностями, що породжуються кодером.
Щоб побудувати хороший згортковий код, потрібно знайти визначальні коди, багаточлени, що породжують, або матриці, що задають зв'язки між суматорами і відведеннями регістра. Побудову ведуть виходячи з отримання максимального ЕВК або мінімальної ДКО l при заданому d min або мінімальної ймовірності збою символу. Пошук кодів здійснюють, зазвичай, перебором на ЕОМ. До теперішнього часу знайдено велику кількість згорткових кодів з різними параметрами для боротьби з різного роду перешкодами.
16. Трудомісткість – характеризує процес декодування згорткового коду і визначається числом обчислювальних операцій, витрачених на декодування одного відповідного блоку послідовності символів, що приймається. Зрозуміло, що й необхідне число операцій у одиницю часу за будь-якого методу декодування даного згорткового коду перевищує швидкодію існуючої обчислювальної техніки, такий код немає практичного інтересу. У цьому випадку буде потрібне, зокрема, зниження технічної швидкості передачі.
Розглянувши цілу низку параметрів та характеристик згорткових кодів, перейдемо до короткого огляду різновидів цих кодів.
6.РІЗНОВИДНОСТІ СВЕРТОЧНИХ КОДІВ
6.1. Систематичні та несистематичні коди
Якщо послідовності формованих кодером кодових символів можна відокремити r = n – k надлишкових символів від k інформаційних, код називають систематичним. У систематичному кодері на виходах k будуть інформаційні послідовності. На інших виходах – послідовності перевірочних знаків, що формуються як лінійні комбінації інформаційних.
Перші k виходів систематичного кодера з'єднані безпосередньо з першими розрядами регістрів. Коди Фінка є систематичними, на рис. 2.5 показані: а) – систематичний, б) – несистематичний кодери при швидкості коду R = 1/2, т. е. при k = 1. Для кодерів з k = 1 для формування систематичних кодів одне із породжують многочленов чи G 1 (X ) = 1, або G 2 (X) = 1, щоб інформаційна послідовність була частиною вихідної послідовності.
Систематичні коди дозволяють отримати на приймальній стороні оцінку інформаційних символів, не виробляючи декодування або іншої обробки символів, що приймаються. У кодових несистематичних послідовностях інформація безпосередньо не міститься, вони мають будуватися так, щоб за відсутності помилок її можна було легко відновити у декодері.
Перевагою несистематичних згорткових кодів є те, що їхня мінімальна вільна відстань вища, ніж у систематичних за інших рівних умов.
Це пояснюється тим, що система-
Систематичний матичний згортковий код мож-