Турбо-код

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

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

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


1. Історія

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

Турбо-коди були запропоновані К. Берроу (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) ще в свій час представляли методи кодування і декодування із загальними принципами, дуже близькими до турбо-кодами, але в той час не були доступні необхідні обчислювальні можливості.


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

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

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

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

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

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

3. Кодування

Рис.1 Загальна структурна схема турбо-кодера

На рис. 1 представлена ​​загальна структурна схема M-блокового турбо-кодера.

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

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


3.1. Перемеженіє в турбо-кодах

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

Завдання перемежітеля - перетворити вхідну послідовність так, щоб комбінації біт 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 , В залежності від необхідної глибини перемежітеля

Cледует операції виконуються для значень від 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) -М бітом вхідного інформаційного блоку. Деперемежітель здійснює запис прийнятого біта по обчисленому адресою.


3.2. Кодова швидкість

Кодова швидкість - відношення довжини кодового блоку на вході до довжини перетвореного кодового блоку на виході кодера.

У відсутність перфоратора (див. рис. 1) вихідна послідовність X_0мультиплексується з послідовностями перевірочних біт V_1, \ ldots, V_M , Утворюючи кодове слово, яке підлягає передачі по каналу. Тоді значення кодової швидкості на виході турбо-кодера

R = \ frac {k} {n (M +1)}

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

R = \ frac {k} {n (N +1)} , Де N <M , Причому N може бути дробовим, якщо число залишилися після перфорації перевірочних біт не кратно n .

Якщо врахувати, що турбо-коди оперують з блоками великої довжини c k> 10000 , То k \ approx n , І кодова швидкість дорівнює

R = \ frac {1} {N +1}

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


4. Декодування

4.1. Алгоритм декодування по максимуму апостеріорної ймовірності (MAP)

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

У своїй роботі Берроу пропонує для використання в турбо-декодерах алгоритм максимуму апостеріорної ймовірності ( англ. Maximum of A-posteriori Probability, MAP ), Також відомий під назвою алгоритму Бала ( Bahl - Cocke - Jelinek - Raviv (BCJR)). Алгоритм Бала дає "м'яку" оцінку достовірності декодованого біта. Тобто пред'являє на виході ступінь довіри результату декодування. На противагу "жорсткої" структурі, при якій на виході декодера формується лише найбільш ймовірне значення декодованого біта ("0" або "1"), при винесенні "м'якого" рішення використовується більш детальна дискретизація вихідного сигналу, що характеризує ймовірність коректного прийому біта. Завдяки використанню "м'яких" рішень в турбо-декодерах виявляється ефективним використання декількох ітерацій декодування. Апостеріорна інформація, отримана про кодовому слові на виході першої ітерації декодування, надходить на вхід блоку наступної ітерації і є для нього вже апріорної ймовірністю. Такий підхід дозволяє покращувати якість декодування від ітерації до ітерації. Таким чином, змінюючи число ітерацій декодування, можна адаптувати декодер для поточного стану каналу передачі і досягти необхідної ймовірності помилки на біт. [6]


4.2. Логарифмічне відношення правдоподібності (LLR)

Розглянемо інформаційний біт як бінарну змінну \ Boldsymbol u_k , Тобто - значення \ Boldsymbol u в момент часу k . Його логарифмічне відношення правдоподібності (LLR) визначено як логарифм відношення його основних ймовірностей.

L (u_k) = \ ln \ frac {Pr (u_k = 1)} {Pr (u_k = 0)}

Ця метрика використовується в більшості систем виправлення помилок за допомогою завадостійкого кодування і називається логарифмічним ставленням правдоподібності або LLR. Вона трохи краще, ніж лінійна метрика, так як, наприклад, логарифм полегшує обробку дуже маленьких і дуже великих значень. Якщо ймовірності прийому "0" і "1" рівні, метрика дорівнює 0.


4.3. Одна ітерація ітеративного турбо-декодера при двокаскадного кодуванні

Рис. 2 Варіант побудови однієї ітерації ітеративного турбо-декодера при двокаскадного кодуванні

На рис. 2 для простоти розуміння представлений варіант схеми однієї ітерації турбо-декодування при двокаскадного кодуванні. Ця схема нескладно узагальнюється на випадок довільної кількості каскадів кодування.

Декодер для однієї ітерації містить каскадне з'єднання двох елементарних декодерів, кожен з яких, грунтуючись на критерії максимуму апостеріорної ймовірності, виносить "м'яке" рішення про переданому символі. На перший декодер першої ітерації з виходу демодулятора надходять "м'які" рішення символів послідовностей X_0 і X_1 . Таким чином на виході першого декодера з'являється оцінка інформаційного символу, яка після подальшого перемежения потрапляє на вхід другого декодера і є для нього апріорній інформацією. Використовуючи "м'яке" рішення про послідовність X_2 , Другий декодер формує свою оцінку. [7]


4.4. Трехітераціонний турбо-декодер при двокаскадного кодуванні

Рис. 3 Варіант побудови трехітераціонного турбо-декодера при двокаскадного кодуванні

З виходу кожної ітерації рішення переходить на вхід наступної. Організація роботи трехітераціонного турбо-декодера показана на рис. 3. Від ітерації до ітерації відбувається уточнення рішення. При цьому кожна ітерація працює з "м'якими" оцінками і на вихід віддає також "м'які". Тому такі схеми отримали назву декодерів з м'яким входом і м'яким виходом ( англ. Soft Input Soft Output (SISO) ). [8] Процес декодування припиняється або після виконання всіх ітерацій, або коли ймовірність помилки на біт досягне необхідного значення. Після декодування з отриманого "м'якого" рішення проводиться остаточне "жорстке". [7]


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

5.1. Переваги

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


5.2. Недоліки

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

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

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


6. Застосування турбо-кодів

Компанії France Telecom і Telediffusion de France запатентували широкий клас турбо-кодів, що обмежує можливість їх вільного застосування і, в той же час, стимулює розвиток нових методів кодування таких, як, наприклад, LDPC.

Турбо-коди активно застосовуються в системах супутникової і мобільного зв'язку, бездротового широкосмугового доступу і цифрового телебачення. [8] Турбо-коди затверджені в стандарті супутникового зв'язку DVB-RCS. Турбо-коди також знайшли широке застосування в мобільних системах зв'язку третього покоління (стандарти CDMA2000 і UMTS). [9]


Примітки

  1. Золотарьов В. В., Овечкін Г. В., Овечкін П. В. Многопороговое декодування для цифрових систем передачі даних - www.mtdbest.iki.rssi.ru / pdf / article_competition.pdf. Читальний - www.webcitation.org/654zutpzh з першоджерела 30 січня 2012.
  2. Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit Error-correcting coding and decoding: Turbo-codes - www-elec.enst-bretagne.fr/equipe/berrou/Near Shannon Limit Error.pdf (Англ.) (1993). Читальний - www.webcitation.org/654zvRndw з першоджерела 30 січня 2012.
  3. Berrou C. Ten-year-old Turbo Codes are Entering Service - www-elec.enst-bretagne.fr/equipe/berrou/com_mag_berrou.pdf (Англ.) (2003). Читальний - www.webcitation.org/654zvtf0B з першоджерела 30 січня 2012.
  4. Семенов Ю. А. Протоколи мереж X.25 - book.itep.ru/4/43/x25_432.htm. Читальний - www.webcitation.org/654zwJk7U з першоджерела 30 січня 2012.
  5. ECSS-E-ST-50-01C - ecss.nl / (Англ.) . Читальний - www.webcitation.org/654zx9OeA з першоджерела 30 січня 2012.
  6. 1 2 Зубарєв Ю. Б., Кривошеєв М. І., Красносельський И. Н. Цифрове телевізійне мовлення. Основи, методи, системи. - М.: Науково-дослідний інститут радіо (НИИР), 2001. - P. 112-120.
  7. 1 2 Комаров С. В., Постніков С. А., Левшин В. І., Дремачев Д. В., Артем'єв М. В. Застосування турбо-кодів в мультимедійних системах зв'язку третього покоління: Збірник статей. Теорія і техніка радіозв'язку. - 2003. - P. 112-119.
  8. 1 2 Архіпкін А. Турбо-коди - потужні алгоритми для сучасних систем зв'язку - kedah.ru / pdf / news / press / files / turbocodes.pdf (журнал. Бездротові технології) (2006). Читальний - www.webcitation.org/654zxla5z з першоджерела 30 січня 2012.
  9. 1 2 Варгаузін В., Протопопов Л. Турбо-коди та Ітеративний декодування: принципи, властивості, застосування - www.telemultimedia.ru/art.php?id=77 (2000). Читальний - www.webcitation.org/654zyKGyX з першоджерела 30 січня 2012.
  10. Moon, Todd K. Error correction coding: mathematical methods and algorithms. - John Wiley & Sons, 2005. - Page 612.