Турбо-код

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

Турбо состоит из каскада параллельно соединённых систематических ов. Эти составляющие называются компонентными ами. В качестве компонентных ов могут использоваться свёрточные ы, ы Хемминга, Рида — Соломона, Боуза — Чоудхури — Хоквингема и другие. В зависимости от выбора компонентного а турбоы делятся на свёрточные турбоы (англ. Turbo Convolutional Codes, ТСС) и блоковые ы-произведения (англ. Turbo Product Codes, TPC)[1].

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


История[ | ]

До момента возникновения турбоа был широко распространён метод каскадного ирования, при котором данные ировались сначала ом Рида — Соломона, а затем свёрточным ом. Он достаточно близко подходит к границе Шеннона и объединяет в себе блок коррекции ошибок, использующий Рида — Соломона и блок свёрточных ов, деируемых с помощью алгоритма Витерби.

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

Структура турбоа[ | ]

Согласно Шеннону, наилучшим ом является , который передает сообщение за бесконечно большое время, формируя в каждый момент времени случайные овые элементы[источник не указан 499 дней]. У приёмника есть бесконечные версии сообщения, искажённого случайным образом. Из этих копий деер должен выбрать копию, наиболее близкую к переданному сообщению. Это представляет собой теоретически идеальный , который может ис все ошибки в сигнале. Турбо является шагом в этом направлении. Ясно, что мы не должны посылать информационное сообщение в течение бесконечного времени. Для приемлемой работы достаточно удвоить или утроить время передачи, что обеспечит довольно приличные результаты для каналов связи.

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

В турбоах блоки имеют длину порядка нескольких Кбит. Цель такой длины состоит в том, чтобы эффективно рандомизировать последовательность, идущую на второе ирующее устройство. Чем длиннее размер блока, тем лучше его корреляция с сообщением первого ера, то есть корреляция мала.

Существует несколько схем турбоов:

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

ирование[ | ]

Рис.1 Общая структурная схема турбоера

На рис. 1 представлена общая структурная схема M-блочного турбоера.

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

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

Перемежение в турбоах[ | ]

В перемежителях по псевдослучайному закону происходит перемешивание поступающих бит. В отличие от посимвольного прямоугольного перемежителя, используемого в ах Рида-Соломона, в турбоах используется перемежение отдельных бит, которое подобно случайным перестановкам. Причём впоследствии, при операциях деирования этот закон перемежения будет считаться известным. Полученные последовательности поступают на входы еров.

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

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

, где одному из следующих значений : , , , , в зависимости от необходимой глубины перемежителя

Следующие операции выполняются для значений от до , чтобы получить адреса перестановки . В уравнениях ниже, обозначает наибольшее целое число, меньше или равное , и обозначает одно из следующих четырёх простых чисел:

Интерпретация перестановки чисел такова, что -й бит, переданный перемежителем, является -м битом входного информационного блока. Перемежитель осуществляет запись принятого бита по вычисленному адресу.

овая скорость[ | ]

овая скорость — отношение длины ового блока на входе к длине преобразованного ового блока на выходе ера.

В отсутствие перфоратора (см. рис. 1) исходная последовательность мультиплексируется с последовательностями проверочных бит , образуя овое слово, подлежащее передаче по каналу. Тогда значение овой скорости на выходе турбоера

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

, где , причём может быть дробным, если число оставшихся после перфорации проверочных бит не кратно .

Если учесть, что турбоы оперируют с блоками большой длины c , то , и овая скорость равна

Из приведённых формул видно, что с помощью перфоратора, выкалывая разное число проверочных бит, возможно регулирование овой скорости. То есть можно построить ер, адаптирующийся к каналу связи. При сильном зашумлении канала перфоратор выкалывает меньше бит, чем вызывает уменьшение овой скорости и рост помехоустойчивости ера. Если же канал связи хорошего качества, то выкалывать можно большое число бит, вызывая рост скорости передачи информации[6].

Деирование[ | ]

Алгоритм деирования по максимуму апостериорной вероятности (MAP)[ | ]

При осуществлении деирования с исправлением ошибок существенен анализ априорной и апостериорной вероятностей прихода верного ового слова. Априорной называется информация, которой обладает деер до прихода ового слова, а апостериорной называется информация, полученная после обработки ового слова.

В своей работе Берроу предлагает для использования в турбодеерах алгоритм максимума апостериорной вероятности (англ. Maximum of A-posteriori Probability, MAP), также известный под названием алгоритма Бала (Bahl — Cocke — Jelinek — Raviv (BCJR)). Алгоритм Бала дает «мягкую» оценку достоверности деированного бита. То есть предъявляет на выходе степень доверия результату деирования. В противоположность «жёсткой» структуре, при которой на выходе деера формируется лишь наиболее вероятное значение деированного бита («0» или «1»), при вынесении «мягкого» решения используется более подробная дискретизация выходного сигнала, характеризующая вероятность корректного приема бита. Благодаря использованию «мягких» решений в турбодеерах оказывается эффективным использование нескольких итераций деирования. Апостериорная информация, полученная о овом слове на выходе первой итерации деирования, поступает на вход блока следующей итерации и является для него уже априорной вероятностью. Такой подход позволяет улучшать качество деирования от итерации к итерации. Таким образом, изменяя число итераций деирования, можно адаптировать деер к текущему состоянию канала передачи и достичь требуемой вероятности ошибки на бит[6].

Логарифмическое отношение правдоподобия (LLR)[ | ]

Рассмотрим информационный бит как бинарную переменную , то есть — значение в момент времени . Его логарифмическое отношение правдоподобия (LLR) определено как логарифм отношения его основных вероятностей.

Эта метрика используется в большинстве систем исправления ошибок с помощью помехоустойчивого ирования и называется логарифмическим отношением правдоподобия или LLR. Она немного лучше, чем линейная метрика, так как, например, логарифм облегчает обработку очень маленьких и очень больших значений. Если вероятности приёма «0» и «1» равны, метрика равна 0.

Одна итерация итеративного турбодеера при двухкаскадном ировании[ | ]

Рис. 2 Вариант построения одной итерации итеративного турбодеера при двухкаскадном ировании

На рис. 2 для простоты понимания представлен вариант схемы одной итерации турбодеирования при двухкаскадном ировании. Эта схема несложно обобщается на случай произвольного количества каскадов ирования.

Деер для одной итерации содержит каскадное соединение двух элементарных дееров, каждый из которых, основываясь на критерии максимума апостериорной вероятности, выносит «мягкое» решение о переданном символе. На первый деер первой итерации с выхода демодулятора поступают «мягкие» решения символов последовательностей и . Таким образом на выходе первого деера появляется оценка информационного символа, которая после последующего перемежения попадает на вход второго деера и является для него априорной информацией. Используя «мягкое» решение о последовательности , второй деер формирует свою оценку[7]

Трёхитерационный турбодеер при двухкаскадном ировании[ | ]

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

С выхода каждой итерации решение переходит на вход следующей. Организация работы трёхитерационного турбодеера показана на рис. 3. От итерации к итерации происходит уточнение решения. При этом каждая итерация работает с «мягкими» оценками и на выход отдает также «мягкие». Поэтому такие схемы получили название дееров с мягким входом и мягким выходом (англ. Soft Input Soft Output (SISO))[8]. Процесс деирования прекращается либо после выполнения всех итераций, либо когда вероятность ошибки на бит достигнет требуемого значения. После деирования из полученного «мягкого» решения производится окончательное «жёсткое»[7].

Преимущества и недостатки турбоов[ | ]

Преимущества[ | ]

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

Недостатки[ | ]

Основной недостаток турбоов — это относительно высокая сложность деирования и большая задержка, которые делают их неудобными для некоторых применений. Но, например, для использования в спутниковых каналах этот недостаток не является определяющим, так как длина канала связи сама по себе вносит задержку, вызванную конечностью скорости света.

Ещё один важный недостаток турбоов — сравнительно небольшое овое расстояние (то есть минимальное расстояние между двумя овыми словами в смысле выбранной метрики). Это приводит к тому, что, хотя при большой входной вероятности ошибки (то есть в плохом канале) эффективность турбоа высока, при малой входной вероятности ошибки эффективность турбоа крайне ограничена.[10] Поэтому в хороших каналах для дальнейшего уменьшения вероятности ошибки применяют не турбоы, а LDPC-ы.

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

Применение турбоов[ | ]

Компании France Télécom и Telediffusion de France запатентовали широкий класс турбоов, что ограничивает возможность их свободного применения и, в то же время, стимулирует развитие новых методов ирования таких, как, например, LDPC.

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

Примечания[ | ]

  1. Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое деирование для цифровых систем передачи данных. Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
  2. Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit error-correcting coding and decoding: Turbo-codes (англ.) (1993). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
  3. Berrou C. Ten-year-old Turbo Codes are Entering Service (англ.) (2003). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
  4. Семенов Ю. А. Протоколы сетей X.25.
  5. ECSS-E-ST-50-01C (англ.). Архивировано 30 января 2012 года.
  6. 1 2 Зубарев Ю. Б., Кривошеев М. И., Красносельский И. Н. Цифровое телевизионное вещание. Основы, методы, системы. — М.: Научно-исследовательский институт радио (НИИР), 2001. — P. 112—120.
  7. 1 2 . Комаров С. В., Постников С. А., Левшин В. И., Дремачев Д. В., Артемьев Н. В. Применение турбоов в мультимедийных системах связи третьего поколения : Сборник статей. Теория и техника радиосвязи. — 2003. — P. 112—119.
  8. 1 2 Архипкин А. Турбоы - мощные алгоритмы для современных систем связи (Журнал. Беспроводные технологии) (2006). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
  9. 1 2 Варгаузин В., Протопопов Л. Турбоы и итеративное деирование: принципы, свойства, применение (2000).
  10. Moon, Todd K. Error correction coding: mathematical methods and algorithms. — John Wiley & Sons, 2005. — page 612.

См. также[ | ]