Турбо-код

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Турбо-код — паралельний каскадний блоковий систематичний код, здатний виправляти помилки, що виникають при передачі цифрової інформації по каналу зв'язку з шумами. Синонімом турбо-коду є відомий в теорії кодування термін — каскадний код (англ. concatenated code) (запропонований Д. Форні в 1966 році).

Турбо-код складається з каскаду паралельно з'єднаних систематичних кодів. Ці складові називаються компонентними кодами. Як компонентні коди можуть використовуватися згорткові коди, коди Хеммінга, Ріда — Соломона, Боуза — Чоудхурі — Хоквінгема та інші. Залежно від вибору компонентного коду турбо-коди діляться на згорткові турбо-коди (англ. Turbo Convolutional Codes, ТСС) та блокові турбо-коди добутку (англ. Turbo Product Codes, TPC)[1].

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

Історія[ред.ред. код]

До моменту виникнення турбо-коду був широко поширений метод каскадного кодування, при якому дані кодувалися спочатку кодом Ріда — Соломона, а потім згортковим кодуванням. Він досить близько підходить до межі Шеннона[en] і об'єднує в собі блок корекції помилок, який використовує код Ріда — Соломона і блок згорткових кодів, які декодуються за допомогою алгоритму Вітербі.

Турбо-коди були запропоновані К. Берроу (C. Berrou), А. Главьйо (A. Glavieux) і П. Сітімашимой (P. Thitimajshima) з (фр. Ecole Nationale Superieure des Telecommunications de Bretagne (ENST), Вища національна школа телекомунікацій Бретані (Франція)) в 1993 році в статті «Кодування і декодування з виправленням помилок поблизу межі Шеннона: турбо-коди» (англ. «Near Shannon Limit Error-correcting Coding and Decoding: Turbo-code»)[2], опублікованій в працях IEEE. У наступній статті[3] Берроу віддає належне інтуїції Г. Беттейла (G. Battail), Дж. Хагенауера (J. Hagenauer) і П. Хоера (P. Hoeher), які в кінці 1980-х теоретично передбачили ймовірнісну обробку даних. Також Берроу згадує, що Роберт Галлагер[en] і М. Таннер (M. Tanner) ще у свій час представляли методи кодування і декодування із загальними принципами, дуже близькими до турбо-кодів, але в той час не були доступні необхідні обчислювальні потужності.

Структура турбо-коду[ред.ред. код]

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

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

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

Існує кілька схем турбо-кодів:

  • PCCC — у разі конкатенації паралельних згортальних кодів
  • SCCC — схема з послідовним з'єднанням згортальних кодів, коди SCCC мають високі характеристики при великих відносинах сигнал / шум
  • TPC — турбо-код-добуток, використовує блокові коди замість згортальних; два різних блокових кода (зазвичай коди Геммінга) з'єднані послідовно без проміжного перемежітеля. Оскільки два коду незалежні і працюють в рядах і колонках, що саме по собі забезпечує досить хорошу рандомізацію, то застосування перемежітеля не потрібно.

Кодування[ред.ред. код]

Спочатку на вхід формувача пакетів PAD[en] (англ. Packet Assembler / Disassembler) надходить блок даних довжиною біт. У формувачі пакетів до даних додається ще додаткових біт службової інформації, відповідних використовуваному стандарту формування пакету і включають у себе символи його початку та кінця[4]. Тобто виходить пакет , що складається з біт.

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

Перемеження в турбо-кодах[ред.ред. код]

У перемежітелях за випадковим законом відбувається перемішування надходжених біт. На відміну від посимвольного прямокутного перемежітеля, використовуваного в кодах Ріда-Соломона, в турбо-кодах використовується перемеження окремих біт, яке подібне випадковим перестановкам. Причому згодом, при операціях декодування цей закон перемеження буде вважатися відомим. Отримані послідовності надходять на входи кодерів.

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

Перестановка для кожної зазначеної довжини блоку задається певним переупорядкованням цілих чисел як передбачено наступним алгоритмом (ECSS-E-ST-50-01C)[5].

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

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

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

Переваги та недоліки турбо-кодів[ред.ред. код]

Переваги[ред.ред. код]

Серед усіх практично використовуваних сучасних методів корекції помилок турбо-коди і коди з малою щільністю перевірок на парність найбільш близько підходять до межі Шеннона, теоретичної межі максимальної пропускної спроможності зашумленого каналу. Турбо-коди дозволяють збільшити швидкість передачі інформації, не вимагаючи збільшення потужності передавача, або вони можуть бути використані для зменшення необхідної потужності при передачі із заданою швидкістю. Важливою перевагою турбо-кодів є незалежність складності декодування від довжини інформаційного блоку, що дозволяє знизити ймовірність помилки декодування шляхом збільшення його довжини[6].

Недоліки[ред.ред. код]

Основний недолік турбо-кодів — це відносно висока складність декодування і велика затримка, які роблять їх незручними для деяких застосувань. Але, наприклад, для використання в супутникових каналах цей недолік не є визначальним, оскільки довжина каналу зв'язку сама по собі вносить затримку, викликану скінченністю швидкості світла.

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

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

Примітки[ред.ред. код]

  1. Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое декодирование для цифровых систем передачи данных (ru). Архів оригіналу за 2015-10-14. 
  2. Berrou C., Glavieux A., Thitmajshima P. (1993). Near Shannon Limit error-correcting coding and decoding: Turbo-codes (en). Архів оригіналу за 2015-10-14. 
  3. Berrou C. (2003). Ten-year-old Turbo Codes are Entering Service (en). Архів оригіналу за 2015-10-14. 
  4. Семенов Ю. А. Протоколы сетей X.25 (ru). Архів оригіналу за 2015-10-14. 
  5. ECSS-E-ST-50-01C (en). Архів оригіналу за 2015-10-14. 
  6. Варгаузин В., Протопопов Л. (2000). Турбо-коды и итеративное декодирование: принципы, свойства, применение (ru). Архів оригіналу за 2015-10-14.