Турбо-коды

Турбо-коды — это класс высокоэффективных корректирующих кодов, используемых в цифровой связи и хранении данных для обнаружения и исправления ошибок, возникающих при передаче информации по каналам с шумами. Относятся к помехоустойчивым кодам с последовательным (каскадным) соединением двух или более компонентных кодов, разделённых перемежителем (интерливером). Турбо-коды позволяют приблизиться к пределу Шеннона — теоретической максимальной пропускной способности канала связи — при относительно низкой сложности декодирования, что стало революцией в теории кодирования в конце XX века.

История

Турбо-коды были впервые предложены в 1993 году группой французских исследователей: Клодом Берру, Аленом Главиё и Пуньей Тхитимаджшимой (работавшими в Telecom Bretagne, ныне IMT Atlantique). Результаты были представлены на конференции IEEE International Conference on Communications (ICC) в Женеве. Первоначально научное сообщество отнеслось к заявлению о достижении производительности в пределах 0,5 дБ от предела Шеннона скептически, однако последующие эксперименты подтвердили эффективность кода.

Название «турбо» происходит от сходства итеративного процесса декодирования с работой турбокомпрессора в двигателях внутреннего сгорания: на каждом цикле декодер использует выходные данные предыдущего цикла для улучшения оценки, что напоминает «подкачку» энергии. В 1994 году Берру и его коллеги опубликовали расширенную версию работы, заложившую основы теории турбо-кодов.

В 1998 году турбо-коды были стандартизированы для использования в спутниковой связи (DVB-RCS), а затем — в мобильных сетях третьего поколения (3G/UMTS) и четвёртого поколения (LTE). В 2000-х годах они были вытеснены в некоторых приложениях более новыми LDPC-кодами (Low-Density Parity-Check), но остаются востребованными в системах, где требуется низкая задержка или высокая надёжность.

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

Кодирование

Турбо-код строится на основе параллельного или последовательного соединения двух (или более) рекурсивных систематических свёрточных кодов (RSC — Recursive Systematic Convolutional). В типичной схеме параллельного турбо-кода:

1. Исходная информационная последовательность длины \( K \) подаётся на первый компонентный кодер, который формирует систематический выход (исходные биты) и проверочные биты.
2. Та же последовательность пропускается через перемежитель (интерливер), который переставляет биты в псевдослучайном порядке, и затем подаётся на второй компонентный кодер, формирующий вторую порцию проверочных бит.
3. На выходе получается кодовое слово длиной \( N \), состоящее из систематических бит и двух наборов проверочных бит, что даёт скорость кода \( R = K/N \).

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

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

Декодирование турбо-кодов является итеративным и основано на алгоритме «мягкого входа/мягкого выхода» (SISO — Soft Input / Soft Output). Наиболее распространённый алгоритм — MAP (Maximum A Posteriori), также известный как алгоритм Бала — Коке — Джелинека — Равива (BCJR). Процесс включает:

1. Первая итерация: первый декодер принимает систематические биты и проверочные биты от первого кодера, а также априорную информацию (обычно нулевую на старте). Он вычисляет апостериорные вероятности для каждого бита и выдаёт «внешнюю» (extrinsic) информацию — разность между апостериорной и априорной оценками.
2. Перемежение: внешняя информация первого декодера перемежается и подаётся как априорная информация на второй декодер.
3. Вторая итерация: второй декодер использует перемежённые систематические биты, проверочные биты от второго кодера и априорную информацию от первого декодера. Он вычисляет новую внешнюю информацию, которая после обратного перемежения возвращается на первый декодер.
4. Повторение: итерации повторяются (обычно 4–12 раз, в зависимости от требуемой точности и задержки). После завершения последней итерации принимается жёсткое решение (0 или 1) на основе апостериорных вероятностей.

Итеративное декодирование позволяет постепенно уточнять оценки, приближаясь к оптимальному решению.

Классификация

Турбо-коды классифицируются по нескольким признакам:

• По типу соединения: параллельные (PCCC — Parallel Concatenated Convolutional Codes), последовательные (SCCC — Serial Concatenated Convolutional Codes) и гибридные.
• По типу компонентных кодов: свёрточные (наиболее распространённые), блочные (турбо-произведения, TPC — Turbo Product Codes), а также коды на основе LDPC (иногда называемые турбо-LDPC).
• По скорости кода: фиксированные (например, 1/2, 1/3) или адаптивные (с помощью выкалывания — puncturing).
• По длине информационного блока: короткие (до 1000 бит), средние (1000–10000 бит) и длинные (более 10000 бит).

Характеристики

Производительность

Турбо-коды обеспечивают очень низкую вероятность ошибки на бит (BER — Bit Error Rate) при умеренном отношении сигнал/шум (SNR). Для длинных блоков (например, 65536 бит) и 10–12 итераций декодирования они могут работать на расстоянии менее 0,5 дБ от предела Шеннона. Однако при коротких блоках (менее 100 бит) их эффективность снижается из-за эффекта «ошибко-пол» (error floor) — резкого замедления снижения BER при высоком SNR.

Сложность

Сложность кодирования линейна по длине блока (\( O(N) \)). Сложность декодирования пропорциональна числу итераций и длине блока: \( O(I \cdot N \cdot 2^m) \), где \( I \) — число итераций, \( m \) — память компонентного кодера. Для типичных параметров (память 3–4, 8 итераций) сложность приемлема для аппаратной реализации на ПЛИС или специализированных микросхемах.

Задержка

Итеративное декодирование вносит задержку, пропорциональную числу итераций и длине блока. В системах реального времени (например, голосовая связь) это ограничение может быть критичным, поэтому для таких приложений используют короткие блоки и малое число итераций.

Применение

Турбо-коды нашли широкое применение в различных областях цифровой связи и хранения данных:

• Мобильная связь: стандарты 3G (UMTS/WCDMA), 4G (LTE), а также некоторые режимы 5G NR (New Radio) — для каналов управления и данных.
• Спутниковая связь: стандарты DVB-RCS (Return Channel via Satellite), CCSDS (Consultative Committee for Space Data Systems) для космических аппаратов.
• Беспроводные локальные сети: стандарт IEEE 802.16 (WiMAX) — опционально.
• Цифровое телевидение: DVB-T2, DVB-S2 — в сочетании с LDPC-кодами.
• Хранение данных: в жёстких дисках (HDD) и твердотельных накопителях (SSD) для коррекции ошибок чтения/записи, особенно в NAND-флеш-памяти с многоуровневыми ячейками (MLC, TLC).
• Глубокий космос: миссии NASA и ESA (например, Mars Reconnaissance Orbiter) используют турбо-коды для надёжной передачи данных с больших расстояний.

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

• LDPC-коды: в настоящее время более популярны для длинных блоков (например, в 5G NR и DVB-S2X), так как обеспечивают более низкую сложность декодирования при высоких скоростях и меньший «error floor». Однако турбо-коды проще в реализации для коротких блоков и имеют меньшую задержку.
• Свёрточные коды: классические свёрточные коды (с декодированием по алгоритму Витерби) значительно уступают турбо-кодам по производительности, но требуют меньше вычислительных ресурсов и не имеют итеративной задержки.
• Коды Рида — Соломона: используются для коррекции пакетных ошибок, но неэффективны при случайных ошибках; турбо-коды часто комбинируют с ними в каскадных схемах.

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

• Открытие турбо-кодов в 1993 году считается одним из важнейших прорывов в теории кодирования с 1948 года (когда Клод Шеннон опубликовал свою работу «Математическая теория связи»).
• В 1998 году Клод Берру получил премию IEEE Richard W. Hamming Medal за вклад в теорию кодирования.
• Первоначально турбо-коды были запатентованы, что привело к длительным судебным разбирательствам между компаниями Qualcomm и Broadcom в 2000-х годах.
• В 2010-х годах турбо-коды были частично вытеснены LDPC-кодами в стандартах 5G NR, но остаются обязательными для обратной совместимости с 4G LTE.

Источники

• Berrou C., Glavieux A., Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbo-codes // IEEE International Conference on Communications (ICC). — 1993.
• Berrou C., Glavieux A. Near optimum error correcting coding and decoding: Turbo-codes // IEEE Transactions on Communications. — 1996. — Vol. 44, No. 10.
• Viterbi A. J. An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes // IEEE Journal on Selected Areas in Communications. — 1998. — Vol. 16, No. 2.
• 3GPP TS 25.212: Multiplexing and channel coding (FDD) — Release 15.
• CCSDS 131.0-B-3: TM Synchronization and Channel Coding — Blue Book. — 2017.
• Moon T. K. Error Correction Coding: Mathematical Methods and Algorithms. — Wiley, 2005.