Лекція 10. Сучасні блокові, згорткові та каскадні коди
Курс “Теорія інформації та кодування”

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

Огляд. Сучасні блокові коди
Принципи потокових (згорткових) кодів
Властивості згорткових кодів
Каскадні рішення та турбо-коди

10.1 Огляд. Сучасні блокові коди

Огляд сучасних кодів із захистом від помилок
Такий огляд представлений на рис.10.1:

Рисунок 10.1 Огляд сучасних кодів із захистом від помилок

- виділяються два основних види таких кодів: блокові, де пакету інформаційних розрядів відповідає множина контрольних (зокрема у вигляді «хвостовика»), а також потокові (зазвичай їх називають також згортковими), де окремі фрагменти інформаційних розрядів захищаються короткими групами контрольних. Певний гібрід утворюють так звані каскадні коди, які включають блокові та потокові складові на двох окремих рівнях. Всі ці напрямки мають власні царини у відповідності до їх специфічних переваг;

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

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

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

Рисунок 10.2 Ітеративні коди

- крім перевірки парності тут можуть застосовуватися код Хеммінга або CRC. Подібні коди називають ітеративними, оскільки ті самі інформаційні розряди тут обробляються по рядках і стовпцях саме послідовно. В загальному випадку блок інформаційних розрядів ai, j включає k1 стовпців і k2 рядків. Загальна кількість стовпців і рядків з урахуванням контрольних розрядів bi,j складає відповідно n1 і n2. Кодова відстань по рядку d1min, а по стовпцю d2min. При цьому для рядків і стовпців можуть використовуватися різні способи кодування (умовно код X і код Y) - рис.10.2 А;

- принципово важливо, що мінімальна кодова відстань для всього блоку дорівнює добутку відстаней по рядку і стовпцю (це доведено математично). У разі найпростішого матричного коду з перевіркою парності, як ми пам'ятаємо, dmin=2х2=4 (код може виправляти поодинокі помилки). Якщо, наприклад, по рядку буде застосовуватися код Хеммінга із dmin = 3, а по стовпцю - перевірка парності, то dmin = 3х2 = 6 (виправляються також помилки кратності 2). А при використанні для кожної з координат коду Хеммінга значення dmin = 3х3 = 9, що дозволяє виправляти вже всі помилки кратності до 4;

- вибір коду для рядка і стовпця матриці може визначатися не тільки вимогами до dmin. Наприклад, для стрічкових накопичувачів широко застосовувався варіант, в якому за стовпцями виконувалося циклічне кодування з поліномом g(x) ступеня 8 в поєднанні з контролем парності по рядках. Цей код, запропонований фірмою IBM, дозволяє виявляти пачки помилок, поява яких характерно для смужок магнітного запису. При цьому перевірка парності по рядку дозволяє виправляти помилки, оскільки одночасний збій на двох і більше смужках малоймовірний (рис.10.2 Б);

- додаткове збільшення коректуючої здатності матричних кодів можливо за рахунок використання «третього виміру», коли в єдиний блок об'єднується пакет з декількох матриць. На рис.10.7б показано найпростіше подібне рішення, коли N матриць містять інформаційні розряди і біти контролю парності по рядках (вісь Y) і стовпцями (вісь X). Додаткова матриця N + 1 включає тільки контрольні біти, значення яких підтримують контроль парності по осі Z. Зрозуміло, такий підхід може бути узагальнений на випадок використання різних кодів по кожній з координат. Більш того, теоретично можуть бути введені і додаткові координати. При цьому, як і раніше, діє правило, коли мінімальна кодова відстань для всього блоку коду визначається як добуток dmin за всіма його координатами (рис.10.2 В).

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

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

Рисунок 10.3 До кодів БЧХ та РС

- коди БЧХ є підкласом циклічних кодів і звідси їх властивості визначаються утворюючим поліномом g(x). При цьому сам такий поліном будується спеціальним способом - виходячи із заданого dmin (з урахуванням кратності виправляє помилок s) і заданої довжини кодового слова n. Така довжина повинна відповідати умові n = 2m-1, де m - ціле число. Властивості коду визначаються трійкою значень (n, k, dmin). Наприклад, позначення (15, 7, 5) відповідає коду з довжиною блоку 15 розрядів, з яких 7 інформаційні, при цьому його мінімальна кодова відстань 5 дозволяє виправляти всі помилки з кратністю s=1 та s=2. Популярним є код (255, 231, 7), який використовують для виявлення помилок з кратністю до 6 включно;

- процедура побудови g(x) є досить громіздкою. Тут лише зазначимо, що утворюючий поліном будується виходячи із заданих значень s, n на базі набору неприводимих поліномів fi(x), які обираються з довідкових таблиць. Наприклад, для згаданого коду (15, 7, 5) утворюючий многочлен виходить як g (x) = f1 (x)*f2 (x) = (x4 + x + 1) ( x4 + x3 + x2 + x + 1) = x8 + x7 + x6 + x4 + 1;

- кодування за заданим g (x) може виконуватися по тій самій процедурі, що і для будь-якого циклічного коду: «хвостовик» блоку будується за поліномом r(x) - залишком від ділення вихідного кодового многочлена f(x) на який утворюючий g (x). Декодування також починається з обчислення залишку отриманого в результаті передачі многочлена f*(x) на утворюючий. Однак надалі для з'ясування розташування всіх помилок доводиться використовувати досить складні процедури (зокрема за так званим алгоритмом Вітербі);

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

10.2 Принципи побудування потокових («згорткових») кодів

Простий потоковий код Фінка-Хегельбергера
Ми познайомимося з реалізацією потокового кодування на прикладі простого коду, запропонований радянським вченим та інженером Фінком і згодом незалежно "перевідкритим" американцем Хегельбергером. Крім того, що цей код став історично першим в даному класі, тут нам не знадобиться складний математичний апарат (рис.10.4):

Рисунок 10.4 Логіка та схема кодера простого коду Фінка

- в даному коді контрольні розряди b(i) (на рисунку показані червоним кольором) чергуються з інформаційними a(i). У найпростішому випадку при кодуванні контрольні розряди визначаються як b(i) = a(i) + a(i+1) (додавання по mod2). При декодуванні вони розраховуються знову b(i)* = a(i)* + a(i+1)* та порівнюються з отриманими в результаті передачі. Параметр коду s=0 означає, що для формування контрольних використвуються саме сусідні інформаційні розряди;

- помилка виявляється, якщо отримане при передачі значення контрольного розряду не збігається з розрахунковим. При цьому враховується закономірність: якщо спотвореним виявився інформаційний розряд а(i), то розбіжність проявиться для двох контрольних розрядах, що його "обрамляють"; якщо ж при передачі був спотворений контрольний розряд, то розбіжність буде тільки в ньому. Це дозволяють гарантовано виправляти поодинокі помилки, проте вже при появі пари помилок (в інформаційному і сусідньому контрольному розрядах) такий варіант коду не може з ними впоратися;

- схема простого кодера Фінка включає двохрозрядний регістр зсуву, на вхід якого поступають інформаційні розряди a(i). В першій половині кожного такту ці розряди без змін поступають на вихід схеми завдяки комутатору. В другій половині такту на вихід проходять контрольні розряди b(i), які формуються суматором за модулем 2. Для декодування застосовується та сама схема, на вхід якої поступають одержані в результаті передачі розряди a(i)*, а одержані контрольні розряди порівнюються із вхідними за правилами, які пояснює рис.10.4.

Розширений код Фінка-Хегельбергера
Важливою метою використання потокових кодів є усунення «пачок» помилок (хоч би й досить коротких). Таку задачу дозволяє вирішувати удосконалений вариіант коду Фінка, який ілюструє зокрема рис.10.5:

Рисунок 10.5 Логіка та схеми розширеного коду Фінка

- можливість усунення коротких пачок помилок дає модифікація коду, яка передбачає інтервал між інформаційними розрядами, що беруть участь у визначенні контрольних: b(i) = a(i+s) + a(i+1+s), де s = 1, 2, .. . Зокрема при s = 1 між розрядами, які беруть участь в контролі знаходитиметься ще пара "проміжних", при s = 2 їх буде чотири (при s = 0 формула виродиться в раніше розглянутий варіант);

- на рис.10.5 показано виправлення пачки з трьох помилок (включаючи 2 інформаційних розряду) для випадку, коли s=1. При цьому оскільки в формуванні контрольного розряду b(i) повинен брати участь не просто попередній йому інформаційний розряд а(i), а й попередній по відношенню до нього а(i-1), на початку кодування доводиться використовувати умовне значення a(0) на рисунку показано зеленим кольором;

- зі збільшенням параметру s зростає довжина «пачки» помилок, що виправляється кодом. Зокрема для s=1 вона сягає 3 розрядів, а для s=2 - 5 розрядів. Але тут проявляється додаткове обмеження коду: між пачками помилок, які він може усувати має бути так званий «захисний інтервал», довжина якого lз досить швидко зростає. Зокрема при s=1 потрібно lз =13, а для s=2 уже lз =21. В практиці значення s>2 не застосовуються;

- схеми кодування для удосконаленого коду Фінка включають розширений регістр зсуву. Зокрема при s=1 він повинен включати три елементи пам'яті, а при s=2 — п'ять (рис.10.5).

Загальні засади кодування для «згорткових» кодів
Для побудування потокових кодів із заданими властивостями потрібно застосовувати відповіний математичний апарат. Такий апарат використовує представлення кодів у вигляді поліномів (як і у випадку кодів CRC) і зокрема математичне перетворення «згортання» поліномів (саме завдяки цій базовій операції такі коди більше відомі як «згорткові») - (рис.10.6):

Рисунок 10.6 Принцип кодування згорткових кодів та його схемне втілення

- вхідна кодова послідовність відображається у вигляді поліному A(X). Вихідна послідовність створюється в результаті операції згортання вхідного поліному із утворюючим поліномом G(X): Bj(X)=A(X)Gj(X). Такий запис відповідає компактній векторній формі. Формула для визначення окремих розрядів вихідного коду наведена на рисунку;

- властивості утворюючого полінома Gj(X) задаються уже знайомою нам схемою кодера, яка включає регістр зсуву, суматори за модулем 2, чиє розташування відображає структуру Gj(X). При цьому потокам інформаційних і контрольних розрядів відповідають окремі утворюючі поліноми, а втім і окремі групи суматорів. Відповідні складові вихідного потоку Bj(X) обєднуються комутатором. Також схема може масштабуватись для кількох вхідних потоків даних A(X), кожному з яких відповідатиме свій регістр зсуву. Надалі ми розглянемо відповідні приклади;

- основні характеристики коду включають кількість вхідних і вихідних розрядів, оброблюваних схемою за один такт (відповідно k і n). Ці параметри визначаються кількістю вхідних потоків A(X) та вихідних потоків Bj(X). Їх співвідношення задає відносну швидкість кодування R = k/n. Також до основних хараетристик коду належить значення dmin, яке визначає кратність помилок, що можуть бути виправлені кодом.

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

Рисунок 10.7 Можливості сучасних потокових кодерів

- на рис. 10.7А і 10.7Б показані схеми кодерів з одним вхідним і двома вихідними каналами (k=1, n=2, R = 1/2). При цьому кодер на рис.10.6А, який реалізує вже знайомий нам код Фінка, є систематичним (тут інформаційні розряди надходять на вихід незмінними і лише доповнюються контрольними розрядами). Кодер на рис.10.6Б є несистематичним. Тут інформаційні розряди також змінюють значення з урахуванням контрольних співвідношень. Такий підхід дозволяє без збільшення надмірності значно посилити коригувальну здатність (значення dmin зростає з 3 до 5, що дозволяє виправляти не тільки одноразові, а й подвійні помилки). Декодування несистематических кодів вимагає досить складних математичних методів і ми не будемо його розглядати;

- на рис. 10.7В та 10.7Г відображені схеми з трьома вихідними каналами (в кожному такті на виході формується три розряди коду). Як можна бачити, це дозволяє додатково наростити dmin до 7 (при цьому можна виправляти вже триразові помилки). Платою є зменшення швидкості кодування (рис. 10.7В). Однак, це може бути компенсовано розпаралелюванням вхідного потоку (рис. 10.7Г);

- в практиці застосовуються стандартизовані варіанти згорткових кодів. Так, у мобільному зв'язку в рамках стандарту GSM, застосовуються кодери з dmin = 7. У системах супутникової передачі даних використовуються кодери з dmin = 10. Утворюючі поліноми для обох кодів показані на рис.10.7. Як видно, обидва ці коди є двоканальними (відносна швидкість кодування становить 1/2) і несистематичними (останнє, як ми вже знаємо, дозволяє при заданому рівні надмірності отримати максимум здатності до корекції).

10.3 Властивості згорткових кодів

Аналіз здатності до корекції помилок
Найважливіший показник здатності згорткових кодів до корекції - кратність помилок, що випраляються (sm). Вона визначається виходячи з мінімального кодової відстані коду за правилом 2sm + 1 <= dmin. Зокрема, при dmin = 3, 5, 7 відповідні значення sm = 1, 2 і 3. Як можна бачити, формула для визначення кратності помилок, що виправляються (в даному випадку вона збігається з довжиною пачки помилок), по суті збігається з тією, яка була отримана для блокових кодів. При цьому існують суттєві особливості у визначенні мінімальної кодової відстані: для блокових кодів довжина всіх кодових слів однакова, а в разі ж згорткових кодів вона не є фіксованою. Не вдаючись до подробиць підходів до визначення dmin для згорткових кодів, охарактеризуємо відповідне практичне рішення.

На практиці для визначення dmin використовується наступний підхід (рис. 10.8):
- шляхом моделювання роботи кодера визначається вихідна послідовність B(X), яка відповідає вхідний виду А (X) = 10000 ... (всі «0» нулі після першої «1»);
- dmin визначається як кількість «1» на інтервалі довжиною lп від початку B (X).
На рисунку показані «тестові» послідовності B (X) і відповідні значення dmin для декількох розглянутих вище структур кодерів (інтервал довжиною lп для підрахунку кількості «1» при визначенні dmin підкреслений).

Рисунок 10.8 Характеристика здатності згорткових кодів до корекції помилок

У практиці вимоги до корегувальної здатності згорткових кодів залежать від сфери застосування. Зокрема, в мобільному зв'язку, де згортковий код є елементом стандарту GSM, застосовуються стандартизовані кодери з dmin = 7 (зокрема G1 (X) = 1 + X3 + X4, G2 (X) = 1 + X + X3 + X4). У системах супутникової передачі даних застосовуються кодери з dmin = 10 (зокрема G1 (X) = 1 + X2 + X3 + X5 + X6, G2 (X) = 1 + X + X2 + X3 + X6).

Напрямки реалізації потокового декодування
Декодування згорткових кодів є значно складнішою задачею, ніж для коду Фінка. Зокрема нині використовується декілька напрямків такого декодування (рис.10.9):

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

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

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

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

10.4 Каскадні рішення та турбо-коди

Класичні каскадні коди
Каскадні коди використовуються для надійної передачі повідомлень в складних умовах. Прикладом може бути передача мови в мобільному зв'язку, де відносно низька надійність радіоканалу поєднується з вимогою безперервності потоку даних, який приймається. Використання каскадного кодування передбачено, зокрема, стандартом GSM. Ідея цього способу полягає в тому, щоб система кодування включала три рівні (рис.10.10):

Рисунок 10.10 Схема каскадного кодування

-на "нижньому" рівні схеми кодування (внутрішній контур) потік розрядів обробляється потоковим (згортковим) кодом з виправленням поодиноких та подвійних помилок, які більш часто зустрічаються;

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

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

- найпростіший спосіб перемежінням - «блоковий» (рис.10.10). Тут вихідна послідовність записується після кодування за стовпцями, а видається для передачі по рядках. Після відновлення сусідні спотворені розряди, що утворюють в каналі «пачку» помилок, виявляються рознесеними в різні рядки матриці. У прикладі на рис.10.10 довга пачка помилок в 6 розрядів розбивається на 4 коротких фрагмента по 1-2 помилки, які можуть бути усунені потоковим кодом.

В цілому спосіб каскадного кодування відрізняється гнучкістю, оскільки тут коди з різними властивостями беруть на себе характерні для них функції. Розвитком цього підходу явлются так звані "турбо-коди", в яких використовується одночасно кілька каналів перемежіння. Застосування подібних удосконалень дозволяє наблизити ефективність кодування до теоретичної межі, визначеної теоремою Шеннона.

Уявлення про «турбо-коди»: етап кодування
Турбо-коди стали удосконаленою версією каскадних рішень, використовуючи більш ресурсоємні та досконалі алгоритми. Нині це досить до цього класу відносять досить різні рішення, що включають як блочні та згорткові коди, зазвичай використовуючи принцип каскадування. Зокрема на стадії кодування використовуються три різні підходи (рис.10.11):

Рисунок 10.11 Підходи до кодування турбо-кодами

- паралельні згорткові коди (схема PCCC) передбачають обробку інформаційних блоків в кількох паралельних каналах, які включають згорткові кодери та переміжувачі П, що забезпечують максимальне розділення потоків з позицій кодової відстані. При цьому розділення та поєднання потоків забезпечують блоки демультіплексування та мультіплексування (ДМ та М), а блок ПФ виконує так звану «перфорацію» коду, регулючи підсумкову щільність контрольних розрядів у відповідності до рівню шуму в каналі;

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

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

Уявлення про «турбо-коди»: декодування
На стадії декодування турбо-кодів застосовуються насупні принципи (Рис.10.12):

Рисунок 10.12 Особливості декодування турбо-кодом

- так зване «м'яке» оцінювання значення прийнятих розрядів коду передбачає використання не двійкових, а безперервних величин (в практиці такі величини піддаються квантуванню). Значення відповідних величин відповідають рівням сигналів, які одержуються на вхід декодера. В результаті перетворень декодер формує на виході теж квантовані безперервні оцінки «близькості» величин до їх двійкових значень. Така схема зокрема зветься схемою з «м'яким» входом (soft input) та «м'яким» виходом (soft output) або SISO – рис.10.12А. При цьому кінцевим результатом «м'якої» обробки все одно повинні бути «жорсткі» двійкові значення кодових розрядів;

- застосування «м'яких» перетворень самом по собі може дати певні переваги при декодуванні, збільшуючи його достовірність (рис.1012Б). Однак найбільший виграш тут одержується за рахунок використання ітеративного підходу, коли одержані недвіййкові оцінки знову подаються на вхід декодера для наступного уточнення. Тут є певна аналогія із принципом використання вихлопних газів двигуна внутрішнього згорання для більш ефективної подачі повітря (так званий турбо-режим). Саме ця аналогія дала назву турбо-кодам;

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

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

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

Рисунок 10.13 До класифікації кодів із захистом від помилок

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

- за використовуваного математичного апарату виділяються лінійні коди (для яких застосовуються тільки операції по модулю 2), а також нелінійні (для них можуть застосовуватися і інші математичні операції). Як приклади нелінійних кодів використаємо коди «рівного ваги» з однаковою кількістю 1 в блоці (помилка виявляється, якщо прийняте число 1 відрізняється від заданого), а також код Бергера, де кількість 1 кодується в хвостовику (такий спосіб застосовується в «асиметричних» каналах, де помилки виражаються тільки в зміні 1 на 0);

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

- за рівнем оптимальності (в сенсі близькості до теоретичної межі Шеннона) виділяються звичайні (сюди відносяться всі розглянуті нами вище коди) і квазіоптимальні. В останню категорію потрапляють, зокрема, так звані «турбо-коди» коди LDPC із «низькою щільністю перевірок на парність". Перші максимально пристосовані до високої ймовірності помилок і дозволяють використовувати довгі блоки даних. Другі краще працюють на більш "чистих" каналах. Квазіоптимальний коди були створені відносно нещодавно і відрізняються високою складністю, але зараз активно застосовуються в системах мобільного та супутникового зв'язку.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2021 • Теория информации и кодирования
UP