Турбо-код

Турбо-код — паралельний, каскадний, блоковий, систематичний код, який здатен виправляти помилки, що виникають при передачі цифрової інформації каналом зв'язку з шумами. Синонімом турбо-коду є відомий в теорії кодування термін — каскадний код (англ. 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-х теоретично передбачили ймовірнісну обробку даних. Також Берроу згадує, що Роберт Галлагер і М. Таннер (M. Tanner) ще у свій час представляли методи кодування і декодування із загальними принципами, дуже близькими до турбо-кодів, але в той час не були доступні необхідні обчислювальні потужності.

Структура турбо-коду

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

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

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

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

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

Кодування

Спочатку на вхід формувача пакетів PAD (англ. Packet Assembler / Disassembler) надходить блок даних $U$ довжиною $k$ біт. У формувачі пакетів до даних додається ще $(n-k)$ додаткових біт службової інформації у відповідності з задіяним стандартом формування пакету^[4]. Тобто результатом є пакет $X_{0}$ , що складається з $n$ біт.

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

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

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

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

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

$k=8*k_{0}$ ,

де $k_{0}$ дорівнює одному з наступних значень: $223,223*2,223*4,223*5$ , залежно від необхідної глибини перемежовувача.

Наступні операції виконуються для значень від $s=1$ до $s=k$ , щоб отримати адреси перестановки ${\boldsymbol {\pi }}(s)$ . У рівняннях нижче, ${\mathcal {b}}{\boldsymbol {x}}{\mathcal {c}}$ позначає найбільше ціле число, яке менше або рівне ${\boldsymbol {x}}$ , і ${\boldsymbol {p}}_{q}$ позначає одне з наступних чотирьох простих чисел: $p_{0}=31$ , $p_{1}=37$ , $p_{2}=43$ , $p_{3}=47$ ,

$m=(s-1)\mod 2$

$i={\mathcal {b}}{\frac {s-1}{2*k_{0}}}{\mathcal {c}}$

$j={\mathcal {b}}{\frac {s-1}{2}}{\mathcal {c}}-i*k_{0}$

$q=(19*i+1)\mod 4$

$c=(p_{q}*j+21*m)\mod k_{0}$

${\boldsymbol {\pi }}(s)=2*(q+4*c+1)-m$

Інтерпретація перестановки чисел полягає в тому, що ${\boldsymbol {s}}$ -й біт, переданий перемежовувачем, є ${\boldsymbol {\pi }}(s)$ -м бітом вхідного інформаційного блоку, де перемежовувач здійснює запис прийнятого біта за обчисленою адресою.

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

Переваги

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

Недоліки

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

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

Див. також

Примітки

↑ Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое декодирование для цифровых систем передачи данных (PDF) (рос.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015. [Архівовано 2016-03-04 у Wayback Machine.]
↑ Berrou C., Glavieux A., Thitmajshima P. (1993). Near Shannon Limit error-correcting coding and decoding: Turbo-codes (PDF) (англ.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.
↑ Berrou C. (2003). Ten-year-old Turbo Codes are Entering Service (PDF) (англ.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.
↑ Семенов Ю. А. Протоколы сетей X.25 (рос.). Архів оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.
↑ ECSS-E-ST-50-01C (англ.). Архів оригіналу за 30 січня 2012. {{cite web}}: Cite має пусті невідомі параметри: |description= та |datepublished= (довідка)
↑ Варгаузин В., Протопопов Л. (2000). Турбо-коды и итеративное декодирование: принципы, свойства, применение (рос.). Архів оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.

[ref-1-1] Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое декодирование для цифровых систем передачи данных (PDF) (рос.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015. [Архівовано 2016-03-04 у Wayback Machine.]

[ref-2-2] Berrou C., Glavieux A., Thitmajshima P. (1993). Near Shannon Limit error-correcting coding and decoding: Turbo-codes (PDF) (англ.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.

[ref-3-3] Berrou C. (2003). Ten-year-old Turbo Codes are Entering Service (PDF) (англ.). Архів (PDF) оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.

[ref_—_4-4] Семенов Ю. А. Протоколы сетей X.25 (рос.). Архів оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.

[ECSS-5] ECSS-E-ST-50-01C (англ.). Архів оригіналу за 30 січня 2012. {{cite web}}: Cite має пусті невідомі параметри: |description= та |datepublished= (довідка)

[ref-6-6] Варгаузин В., Протопопов Л. (2000). Турбо-коды и итеративное декодирование: принципы, свойства, применение (рос.). Архів оригіналу за 30 січня 2012. Процитовано 14 жовтня 2015.

[1]

[2]

[3]

[4]

[5]

[6]