Турбокод
Ту́рбокод — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбокода является известный в теории кодирования термин — каскадный код (англ. concatenated code) (предложен Д. Форни в 1966 году).
Турбокод состоит из каскада параллельно соединённых систематических кодов. Эти составляющие называются компонентными кодами. В качестве компонентных кодов могут использоваться
Турбокоды были разработаны в
История
До момента возникновения турбокода был широко распространён метод каскадного кодирования, при котором данные кодировались сначала кодом Рида — Соломона, а затем свёрточным кодом. Он достаточно близко подходит к границе Шеннона и объединяет в себе блок коррекции ошибок, использующий код Рида — Соломона и блок свёрточных кодов, декодируемых с помощью алгоритма Витерби.
Турбокоды были предложены К. Берроу (C. Berrou), А. Главьё (A. Glavieux) и П. Ситимашимой (P. Thitimajshima) из (
Структура турбокода
правилами написания статей . |
Согласно
Особенностью турбокодов является параллельная структура, состоящая из рекурсивных систематических сверточных (RSC) кодов, работающих параллельно и использующих создание случайной версии сообщения. Параллельная структура использует два или больше кодов RSC, каждый с различным перемежителем. Цель перемежителя состоит в том, чтобы предложить каждому кодеру некоррелированную или случайную версию информации, в результате чего паритетные биты каждого RSC становятся независимыми.
В турбокодах блоки имеют длину порядка нескольких Кбит. Цель такой длины состоит в том, чтобы эффективно рандомизировать последовательность, идущую на второе кодирующее устройство. Чем длиннее размер блока, тем лучше его корреляция с сообщением первого кодера, то есть корреляция мала.
Существует несколько схем турбокодов:
- PCCC — в случае конкатенации параллельных сверточных кодов
- SCCC — схема с последовательным соединением сверточных кодов, коды SCCC имеют высокие характеристики при больших отношениях сигнал/шум
- TPC — турбокод-произведение, использует блочные коды вместо сверточных; два различных блочных кода (обычно коды Хемминга) соединены последовательно без промежуточного перемежителя. Так как два кода независимы и работают в рядах и колонках, что само по себе обеспечивает достаточно хорошую рандомизацию, то применение перемежителя не требуется.
Кодирование
На рис. 1 представлена общая структурная схема M-блочного турбокодера.
Сначала на вход формирователя пакетов PAD (англ. Packet Assembler/Disassembler) поступает блок данных длиной бит. В формирователе пакетов к данным прибавляется ещё дополнительных бит служебной информации, соответствующих используемому стандарту формирования пакета и включающих в себя символы его начала и окончания[4]. То есть получается пакет , состоящий из бит.
Далее последовательность бит поступает параллельно на ветвей, содержащих последовательно соединённые перемежитель и компонентный кодер. Таким образом, используется в качестве входных данных сразу всеми компонентными кодерами.
Перемежение в турбокодах
В перемежителях по псевдослучайному закону происходит перемешивание поступающих бит. В отличие от посимвольного прямоугольного перемежителя, используемого в кодах Рида-Соломона, в турбокодах используется перемежение отдельных бит, которое подобно случайным перестановкам. Причём впоследствии, при операциях декодирования этот закон перемежения будет считаться известным. Полученные последовательности поступают на входы кодеров.
Задача перемежителя — преобразовать входную последовательность так, чтобы комбинации бит , соответствующие
Перестановка для каждой указанной длины блока задается определенным переупорядочиванием целых чисел как предусмотрено следующим алгоритмом (ECSS-E-ST-50-01C)[5].
, где одному из следующих значений : , , , , в зависимости от необходимой глубины перемежителя
Следующие операции выполняются для значений от до , чтобы получить адреса перестановки . В уравнениях ниже, обозначает наибольшее целое число, меньше или равное , и обозначает одно из следующих четырёх простых чисел:
Интерпретация перестановки чисел такова, что -й бит, переданный перемежителем, является -м битом входного информационного блока. Перемежитель осуществляет запись принятого бита по вычисленному адресу.
Кодовая скорость
Кодовая скорость — отношение длины кодового блока на входе к длине преобразованного кодового блока на выходе кодера.
В отсутствие
Для увеличения кодовой скорости применяется выкалывание (перфорация) определённых проверочных битов выходной последовательности. Таким образом кодовая скорость возрастает до
, где , причём может быть дробным, если число оставшихся после перфорации проверочных бит не кратно .
Если учесть, что турбокоды оперируют с блоками большой длины c , то , и кодовая скорость равна
Из приведённых формул видно, что с помощью перфоратора, выкалывая разное число проверочных бит, возможно регулирование кодовой скорости. То есть можно построить кодер, адаптирующийся к каналу связи. При сильном зашумлении канала перфоратор выкалывает меньше бит, чем вызывает уменьшение кодовой скорости и рост помехоустойчивости кодера. Если же канал связи хорошего качества, то выкалывать можно большое число бит, вызывая рост скорости передачи информации[6].
Декодирование
При осуществлении декодирования с
В своей работе Берроу предлагает для использования в турбодекодерах алгоритм максимума апостериорной вероятности (англ. Maximum of A-posteriori Probability, MAP), также известный под названием алгоритма Бала (Bahl — Cocke — Jelinek — Raviv (BCJR)). Алгоритм Бала дает «мягкую» оценку достоверности декодированного бита. То есть предъявляет на выходе степень доверия результату декодирования. В противоположность «жёсткой» структуре, при которой на выходе декодера формируется лишь наиболее вероятное значение декодированного бита («0» или «1»), при вынесении «мягкого» решения используется более подробная дискретизация выходного сигнала, характеризующая вероятность корректного приема бита. Благодаря использованию «мягких» решений в турбодекодерах оказывается эффективным использование нескольких итераций декодирования. Апостериорная информация, полученная о кодовом слове на выходе первой итерации декодирования, поступает на вход блока следующей итерации и является для него уже априорной вероятностью. Такой подход позволяет улучшать качество декодирования от итерации к итерации. Таким образом, изменяя число итераций декодирования, можно адаптировать декодер к текущему состоянию канала передачи и достичь требуемой вероятности ошибки на бит[6].
Рассмотрим информационный бит как бинарную переменную , то есть — значение в момент времени . Его логарифмическое отношение правдоподобия (LLR) определено как логарифм отношения его основных вероятностей.
Эта метрика используется в большинстве систем исправления ошибок с помощью помехоустойчивого кодирования и называется логарифмическим отношением правдоподобия или LLR. Она немного лучше, чем линейная метрика, так как, например, логарифм облегчает обработку очень маленьких и очень больших значений. Если вероятности приёма «0» и «1» равны, метрика равна 0.
Одна итерация итеративного турбодекодера при двухкаскадном кодировании
На рис. 2 для простоты понимания представлен вариант схемы одной итерации турбодекодирования при двухкаскадном кодировании. Эта схема несложно
Декодер для одной итерации содержит каскадное соединение двух элементарных декодеров, каждый из которых, основываясь на критерии максимума апостериорной вероятности, выносит «мягкое» решение о переданном символе. На первый декодер первой итерации с выхода демодулятора поступают «мягкие» решения символов последовательностей и . Таким образом на выходе первого декодера появляется оценка информационного символа, которая после последующего перемежения попадает на вход второго декодера и является для него априорной информацией. Используя «мягкое» решение о последовательности , второй декодер формирует свою оценку[7]
Трёхитерационный турбодекодер при двухкаскадном кодировании
С выхода каждой итерации решение переходит на вход следующей. Организация работы трёхитерационного турбодекодера показана на рис. 3. От итерации к итерации происходит уточнение решения. При этом каждая итерация работает с «мягкими» оценками и на выход отдает также «мягкие». Поэтому такие схемы получили название декодеров с мягким входом и мягким выходом (англ. Soft Input Soft Output (SISO))[8]. Процесс декодирования прекращается либо после выполнения всех итераций, либо когда вероятность ошибки на бит достигнет требуемого значения. После декодирования из полученного «мягкого» решения производится окончательное «жёсткое»[7].
Преимущества и недостатки турбокодов
Преимущества
Среди всех практически используемых современных методов коррекции ошибок турбокоды и
Недостатки
Основной недостаток турбокодов — это относительно высокая сложность декодирования и большая задержка, которые делают их неудобными для некоторых применений. Но, например, для использования в спутниковых каналах этот недостаток не является определяющим, так как длина канала связи сама по себе вносит задержку, вызванную конечностью скорости света.
Ещё один важный недостаток турбокодов — сравнительно небольшое кодовое расстояние (то есть минимальное расстояние между двумя кодовыми словами в смысле выбранной
Хотя сложность используемых алгоритмов турбокодирования и недостаток открытого программного обеспечения препятствуют внедрению турбокодов, в настоящее время многие современные системы используют турбокоды.
Применение турбокодов
Компании
Турбокоды активно применяются в системах
Примечания
- ↑ Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Многопороговое декодирование для цифровых систем передачи данных . Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
- ↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit error-correcting coding and decoding: Turbo-codes (англ.) (1993). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
- ↑ Berrou C. Ten-year-old Turbo Codes are Entering Service (англ.) (2003). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
- ↑ Семенов Ю. А. Протоколы сетей X.25 . Дата обращения: 23 ноября 2008. Архивировано 13 октября 2011 года.
- ↑ ECSS-E-ST-50-01C (англ.). Архивировано 30 января 2012 года.
- ↑ 1 2 Зубарев Ю. Б., Кривошеев М. И., Красносельский И. Н. Цифровое телевизионное вещание. Основы, методы, системы. — М.: Научно-исследовательский институт радио (НИИР), 2001. — P. 112—120.
- ↑ 1 2 . Комаров С. В., Постников С. А., Левшин В. И., Дремачев Д. В., Артемьев Н. В. Применение турбокодов в мультимедийных системах связи третьего поколения : Сборник статей. Теория и техника радиосвязи. — 2003. — P. 112—119.
- ↑ 1 2 Архипкин А. Турбокоды - мощные алгоритмы для современных систем связи (Журнал. Беспроводные технологии) (2006). Дата обращения: 21 ноября 2008. Архивировано 30 января 2012 года.
- ↑ 1 2 Варгаузин В., Протопопов Л. Турбокоды и итеративное декодирование: принципы, свойства, применение (2000). Дата обращения: 21 ноября 2008. Архивировано 4 марта 2016 года.
- ↑ Moon, Todd K. Error correction coding: mathematical methods and algorithms. — John Wiley & Sons, 2005. — page 612.
См. также
Статья является кандидатом к лишению статуса хорошей с 10 февраля 2024 года |