Турбокоды

Турбокоды — это класс высокоэффективных корректирующих кодов, используемых в цифровой связи и хранении данных для обнаружения и исправления ошибок, возникающих при передаче информации по зашумленным каналам. Они основаны на принципе параллельного каскадирования двух или более систематических сверточных кодов, разделенных перемежителем, и итеративном алгоритме декодирования с мягким решением, который называется декодированием с распространением доверия или алгоритмом BCJR (Бала—Коке—Джелинека—Равива). Турбокоды были впервые представлены в 1993 году группой французских исследователей (Клод Берру, Ален Главиё и Пунья Тхитимаджсима) и произвели революцию в теории кодирования, приблизившись к пределу Шеннона — теоретическому максимуму пропускной способности канала связи. Их название происходит от принципа работы турбонаддува в двигателях внутреннего сгорания, где обратная связь усиливает мощность; в декодере турбокода итерации между компонентными декодерами последовательно улучшают оценку переданных данных.

История

Предпосылки и открытие

До появления турбокодов основными методами помехоустойчивого кодирования были сверточные коды с декодированием по алгоритму Витерби и блоковые коды (например, коды Рида—Соломона или БЧХ). Однако все они имели ограничения: для достижения высокой надежности требовалась большая избыточность, что снижало скорость передачи. Теоретический предел Шеннона, установленный в 1948 году, казался недостижимым на практике. В 1993 году на Международной конференции по связи в Женеве Берру, Главиё и Тхитимаджсима представили работу «Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes», где описали новый метод, позволяющий работать на расстоянии до 0,5 дБ от предела Шеннона при умеренной сложности декодирования. Это вызвало огромный интерес и привело к бурному развитию теории итеративного декодирования.

Развитие и стандартизация

В 1990-е годы турбокоды были адаптированы для спутниковой связи (стандарт DVB-RCS) и мобильных сетей. В 2000-е годы они стали основой для канального кодирования в стандартах 3G (UMTS/WCDMA) и 4G (LTE), где используются турбокоды с длиной блока до 6144 бит. В 2010-е годы для 5G NR были разработаны низкоплотностные коды с проверкой на четность (LDPC), которые частично вытеснили турбокоды в каналах данных, но турбокоды остаются в управляющих каналах 5G. В системах глубокого космоса (например, миссия NASA «Mars Reconnaissance Orbiter») турбокоды применяются для обеспечения надежной связи на огромных расстояниях.

Принцип работы

Кодирование

Турбокодер состоит из двух или более компонентных кодеров (обычно рекурсивных систематических сверточных кодеров, RSC), работающих параллельно. Исходная последовательность битов (информационная часть) подается на первый кодер напрямую, а на второй — через перемежитель, который переставляет биты в псевдослучайном порядке. Каждый кодер генерирует проверочные биты (избыточность). На выходе передаются: исходные информационные биты (систематическая часть) и проверочные биты от обоих кодеров. Таким образом, кодовая скорость может быть, например, 1/3 (один информационный бит на три переданных). Для повышения скорости может использоваться выкалывание (puncturing) — удаление части проверочных битов.

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

Декодер турбокода — итеративный. Он состоит из двух компонентных декодеров, каждый из которых реализует алгоритм BCJR (также известный как алгоритм MAP — Maximum A Posteriori). На вход каждого декодера поступают: мягкие значения (логарифмические отношения правдоподобия, LLR) от демодулятора, а также априорная информация от другого декодера. Первый декодер обрабатывает принятую последовательность, используя априорные сведения (изначально равные нулю), и вычисляет внешнюю информацию (экстринсик) — прирост достоверности, который не зависит от собственных априорных данных. Эта внешняя информация после перемежения подается на второй декодер как априорная. Второй декодер, в свою очередь, вычисляет свою внешнюю информацию, которая после обратного перемежения возвращается к первому. Процесс повторяется несколько итераций (обычно 4–8), пока оценки не сойдутся к стабильному решению. После последней итерации принимается жесткое решение по знаку LLR (положительный — бит «1», отрицательный — «0»). Ключевое свойство — чем больше итераций, тем точнее декодирование, но растет задержка и вычислительная сложность.

Характеристики и особенности

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

• Близость к пределу Шеннона: при длине блока 65536 бит и кодовой скорости 1/2 турбокоды могут работать на расстоянии менее 0,5 дБ от теоретического предела.
• Масштабируемость: увеличение длины блока и числа итераций улучшает корректирующую способность, но требует больше ресурсов.
• Гибкость: кодовую скорость и длину блока можно адаптировать под конкретный канал (например, с помощью выкалывания).

Недостатки

• Высокая задержка декодирования: итеративный процесс требует времени, что критично для приложений реального времени (например, голосовая связь).
• Эффект «ошибки пола» (error floor): при очень низких отношениях сигнал/шум кривая вероятности ошибки перестает быстро падать и выходит на плато. Это связано с тем, что некоторые комбинации ошибок не могут быть исправлены даже при многих итерациях. Для борьбы с этим применяют внешние коды (например, код Рида—Соломона) или более длинные перемежители.
• Чувствительность к длине блока: короткие блоки (менее 100 бит) работают хуже, чем длинные, из-за недостаточной рандомизации перемежения.

Применение

Мобильная связь

Турбокоды являются обязательным элементом канального кодирования в стандартах 3G (UMTS) и 4G (LTE). В LTE используются турбокоды с длиной блока до 6144 бит и кодовыми скоростями от 1/3 до 5/6. В 5G NR турбокоды применяются в каналах управления (например, физический канал управления восходящей линии связи, PUCCH), в то время как для каналов данных используются LDPC-коды.

Спутниковая и космическая связь

Стандарты DVB-S2 (спутниковое телевидение) и DVB-RCS (обратный канал) включают турбокоды. В системах связи с космическими аппаратами (например, миссии NASA и ESA) турбокоды обеспечивают надежную передачу на расстояния в миллионы километров при крайне низких отношениях сигнал/шум.

Беспроводные локальные сети и другие стандарты

Турбокоды используются в стандарте IEEE 802.16 (WiMAX) и в некоторых системах цифрового радиовещания (DAB). В проводных системах (например, DSL) они применяются реже из-за меньшей зашумленности канала.

Сравнение с другими кодами

Сверточные коды

Классические сверточные коды с декодированием Витерби проще в реализации и имеют меньшую задержку, но значительно уступают турбокодам по корректирующей способности (отставание от предела Шеннона составляет 2–3 дБ).

LDPC-коды

Низкоплотностные коды с проверкой на четность (LDPC) также приближаются к пределу Шеннона и имеют более низкий «ошибка пола» при больших длинах блока. Они быстрее декодируются (используют разреженные матрицы) и лучше подходят для каналов с высокой скоростью (например, 5G NR, Wi-Fi 6). Однако турбокоды проще в реализации для коротких блоков и имеют более предсказуемое поведение при малом числе итераций.

Коды Рида—Соломона

Эти блоковые коды эффективны против пакетов ошибок (burst errors), но не могут достичь предела Шеннона и требуют большей избыточности. Их часто комбинируют с турбокодами (каскадные схемы) для снижения «ошибка пола».

Интересные факты

• Название «турбокод» было предложено Клодом Берру из-за аналогии с турбонаддувом: итерации в декодере «раскручивают» достоверность оценок, подобно тому, как турбина нагнетает воздух в двигатель.
• За открытие турбокодов Берру, Главиё и Тхитимаджсима получили несколько престижных наград, включая премию Маркони в 2005 году и медаль Ричарда Хэмминга в 2007 году.
• Первоначально статья 1993 года была встречена скептически, так как многие специалисты считали, что итеративное декодирование не может быть стабильным. Однако последующие эксперименты подтвердили работоспособность метода.
• Турбокоды стали первыми практическими кодами, которые достигли расстояния менее 1 дБ от предела Шеннона, что стимулировало развитие теории итеративного декодирования и возродило интерес к LDPC-кодам, которые были открыты ещё в 1960-х годах, но забыты.

Источники

• Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. Proceedings of the IEEE International Conference on Communications, 1064–1070.
• Viterbi, A. J. (1998). An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes. IEEE Journal on Selected Areas in Communications, 16(2), 260–264.
• 3GPP TS 36.212: Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding.
• 3GPP TS 38.212: NR; Multiplexing and channel coding.
• Lin, S., & Costello, D. J. (2004). Error Control Coding (2nd ed.). Pearson Prentice Hall.
• Richardson, T., & Urbanke, R. (2008). Modern Coding Theory. Cambridge University Press.