Турбо-код

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

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

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

История

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

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

Кодирование

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

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

Сначала на вход формирователя пакетов 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$, в зависимости от необходимой глубины перемежителя

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)$-м битом входного информационного блока. Деперемежитель осуществляет запись принятого бита по вычисленному адресу.

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

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

В отсутствие перфоратора (см. рис. 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]

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

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

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

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

Логарифмическое отношение правдоподобия (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.

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

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

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

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

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

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

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

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

Преимущества

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

Недостатки

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

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

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

Применение турбо-кодов

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

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

Примечания

1. ↑ Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое декодирование для цифровых систем передачи данных  (рус.). Архивировано из первоисточника 30 января 2012.
2. ↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit error-correcting coding and decoding: Turbo-codes  (англ.) (1993). Архивировано из первоисточника 30 января 2012.
3. ↑ Berrou C. Ten-year-old Turbo Codes are Entering Service  (англ.) (2003). Архивировано из первоисточника 30 января 2012.
4. ↑ Семенов Ю. А. Протоколы сетей X.25  (рус.). Архивировано из первоисточника 30 января 2012.
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). Архивировано из первоисточника 30 января 2012.
9. ↑ ^{1 2} Варгаузин В., Протопопов Л. Турбо-коды и итеративное декодирование: принципы, свойства, применение  (рус.) (2000). Архивировано из первоисточника 30 января 2012.
10. ↑ Moon, Todd K. Error correction coding: mathematical methods and algorithms. — John Wiley & Sons, 2005. — page 612.

См. также

• Обнаружение и исправление ошибок
• Код Рида — Соломона
• LDPC
• Код Боуза — Чоудхури — Хоквингема

Эта статья входит в число хороших статей русскоязычного раздела Википедии.