Турбокод

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

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

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

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

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

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

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

Кодирование

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

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

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

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

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

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

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

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

${\displaystyle k=8*k_{0}}$, где ${\displaystyle k_{0}=}$ одному из следующих значений : ${\displaystyle 223}$, ${\displaystyle 223*2}$, ${\displaystyle 223*4}$, ${\displaystyle 223*5}$, в зависимости от необходимой глубины перемежителя

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

${\displaystyle m=(s-1)\mod 2}$

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

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

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

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

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

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

Кодовая скорость

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

В отсутствие перфоратора (см. рис. 1) исходная последовательность ${\displaystyle X_{0}}$ мультиплексируется с последовательностями проверочных бит ${\displaystyle V_{1},\ldots ,V_{M}}$, образуя кодовое слово, подлежащее передаче по каналу. Тогда значение кодовой скорости на выходе турбокодера

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

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

${\displaystyle R={\frac {k}{n(N+1)}}}$ , где ${\displaystyle N<M}$, причём ${\displaystyle N}$ может быть дробным, если число оставшихся после перфорации проверочных бит не кратно ${\displaystyle n}$.

Если учесть, что турбокоды оперируют с блоками большой длины c ${\displaystyle k>10000}$, то ${\displaystyle k\approx n}$, и кодовая скорость равна

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

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

Декодирование

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

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

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

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

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

${\displaystyle L(u_{k})=\ln {\frac {Pr(u_{k}=1)}{Pr(u_{k}=0)}}}$

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

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

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

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

Декодер для одной итерации содержит каскадное соединение двух элементарных декодеров, каждый из которых, основываясь на критерии максимума апостериорной вероятности, выносит «мягкое» решение о переданном символе. На первый декодер первой итерации с выхода демодулятора поступают «мягкие» решения символов последовательностей ${\displaystyle X_{0}}$ и ${\displaystyle X_{1}}$. Таким образом на выходе первого декодера появляется оценка информационного символа, которая после последующего перемежения попадает на вход второго декодера и является для него априорной информацией. Используя «мягкое» решение о последовательности ${\displaystyle X_{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  (рус.). Дата обращения: 23 ноября 2008. Архивировано 13 октября 2011 года.
5. ECSS-E-ST-50-01C (англ.). Архивировано 30 января 2012 года.
6. Зубарев Ю. Б., Кривошеев М. И., Красносельский И. Н. Цифровое телевизионное вещание. Основы, методы, системы. — М.: Научно-исследовательский институт радио (НИИР), 2001. — P. 112—120.
7. . Комаров С. В., Постников С. А., Левшин В. И., Дремачев Д. В., Артемьев Н. В. Применение турбокодов в мультимедийных системах связи третьего поколения : Сборник статей. Теория и техника радиосвязи. — 2003. — P. 112—119.
8. Архипкин А. Турбокоды - мощные алгоритмы для современных систем связи  (рус.) (Журнал. Беспроводные технологии) (2006). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
9. Варгаузин В., Протопопов Л. Турбокоды и итеративное декодирование: принципы, свойства, применение  (рус.) (2000). Дата обращения: 21 ноября 2008. Архивировано 4 марта 2016 года.
10. Moon, Todd K. Error correction coding: mathematical methods and algorithms. — John Wiley & Sons, 2005. — page 612.

См. также

• Код Рида — Соломона
• LDPC
• Полярные коды
• Код Боуза — Чоудхури — Хоквингема