Турбокод

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

Задача перемежителя — преобразовать входную последовательность так, чтобы комбинации бит ${\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].

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

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

Рассмотрим информационный бит как бинарную переменную ${\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-коды.

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