Турбо-код

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

История

Концепция турбо-кодов была впервые предложена в 1993 году группой французских исследователей из Национальной школы телекоммуникаций (ENST) в Бресте: Клодом Берру, Аленом Главиё и Пьером Титмажма. Их работа «Near Shannon limit error-correcting coding and decoding: Turbo-codes» была представлена на конференции IEEE International Conference on Communications (ICC) в Женеве. Открытие вызвало значительный резонанс в научном сообществе, поскольку до этого считалось, что достижение предела Шеннона требует использования кодов с очень большой длиной блока, что делает декодирование практически нереализуемым. Турбо-коды продемонстрировали, что итеративное декодирование позволяет достичь близких к теоретическому пределу результатов при умеренной сложности.

Название «турбо» происходит от сходства принципа работы с турбонаддувом в двигателях внутреннего сгорания: процесс декодирования включает обратную связь, где один декодер использует информацию от другого для улучшения результатов, что напоминает рециркуляцию выхлопных газов. В 1994 году Берру, Главиё и Титмажма получили патент на турбо-коды, а в 1998 году — премию IEEE Information Theory Society за выдающийся вклад в теорию информации.

Первоначально турбо-коды применялись в спутниковой связи, где требовалась высокая помехоустойчивость при низких отношениях сигнал/шум. В 2000-х годах они были стандартизированы для ряда систем, включая мобильную связь третьего поколения (3G) и четвёртого поколения (4G LTE). В 2010-х годах турбо-коды начали вытесняться более новыми кодами с низкой плотностью проверок на чётность (LDPC-коды) и полярными кодами, однако остаются широко используемыми в существующих инфраструктурах.

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

Кодирование

Турбо-код строится на основе двух или более рекурсивных систематических свёрточных кодеров (RSC), соединённых параллельно или последовательно. Входная последовательность битов длины \(k\) подаётся на первый кодер, а также на перемежитель (interleaver), который переставляет биты в псевдослучайном порядке. Перемежённая последовательность подаётся на второй кодер. Выходные сигналы обоих кодеров, а также исходная систематическая последовательность (некодированные биты) объединяются в общий кодовый блок длины \(n\). Таким образом, скорость кода \(R = k/n\) может быть настроена путём выкалывания (puncturing) — удаления части битов для увеличения скорости.

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

Декодирование турбо-кодов является итеративным и основано на алгоритме максимальной апостериорной вероятности (MAP, также известный как алгоритм Бала-Кока-Джелинека-Равива, BCJR). Два декодера, соответствующих каждому из кодеров, обмениваются внешней информацией (extrinsic information) — мягкими решениями о вероятности каждого бита, не зависящими от собственных наблюдений декодера. Процесс повторяется несколько итераций (обычно от 4 до 12), после чего принимается окончательное жёсткое решение (0 или 1).

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

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

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

• По структуре кодеров:
• Параллельные турбо-коды (PCCC) — наиболее распространённый тип, где два кодера работают параллельно над одной последовательностью.
• Последовательные турбо-коды (SCCC) — один кодер обрабатывает выход другого, что может улучшить характеристики при очень низких отношениях сигнал/шум.
• Гибридные схемы — комбинация параллельных и последовательных структур.

• По типу компонентных кодов:
• Свёрточные турбо-коды — классический вариант на основе рекурсивных систематических свёрточных кодов.
• Блочные турбо-коды — используют блочные коды (например, коды Рида-Соломона или БЧХ) в качестве компонентных, часто с итеративным декодированием.
• Турбо-коды с низкой плотностью проверок на чётность (LDPC) — иногда рассматриваются как подкласс, хотя обычно выделяются отдельно.

• По длине блока:
• Короткие (до 1000 бит) — для приложений с низкой задержкой.
• Средние (1000–10000 бит) — для большинства систем связи.
• Длинные (более 10000 бит) — для спутниковой и глубокой космической связи.

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

Основные параметры турбо-кодов включают:

• Скорость кода \(R\) — отношение числа информационных битов к общему числу битов в кодовом блоке. Типичные значения: 1/2, 1/3, 2/3, 3/4.
• Длина блока \(k\) — число информационных битов. Влияет на задержку и сложность декодирования.
• Число итераций — определяет качество декодирования и вычислительные затраты.
• Перемежитель — тип и размер перемежителя (например, псевдослучайный, квадратичный, S-образный) влияет на эффективность кода.
• Пороговое отношение сигнал/шум — минимальное значение \(E_b/N_0\), при котором вероятность ошибки на бит (BER) падает ниже заданного уровня (например, \(10^{-5}\)).

Турбо-коды демонстрируют BER, близкую к пределу Шеннона, при умеренных длинах блоков (например, 1000–4000 бит). Для скорости 1/2 и длины блока 65536 бит они могут работать на расстоянии менее 0,5 дБ от предела Шеннона. Однако при коротких блоках (менее 100 бит) их эффективность снижается из-за эффекта «ошибки ошибки» (error floor) — резкого замедления снижения BER при высоких отношениях сигнал/шум.

Применение

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

• Мобильная связь:
• 3G (UMTS) — турбо-коды используются для каналов с высокой скоростью передачи данных (HSDPA, HSUPA).
• 4G LTE — турбо-коды применяются для каналов данных (PDSCH, PUSCH) с длиной блока до 6144 бит.
• 5G NR — в ранних версиях стандарта турбо-коды использовались для каналов управления, но впоследствии заменены полярными кодами и LDPC.

• Спутниковая связь:
• Стандарты DVB-S2 и DVB-S2X для цифрового телевидения и широкополосного доступа в интернет через спутник.
• Системы связи с глубоким космосом (NASA, ESA) — например, миссии «Кассини-Гюйгенс» и «Марсианский научный лаборатория».

• Беспроводные локальные сети:
• Стандарт IEEE 802.11n (Wi-Fi) — опционально использует турбо-коды для повышения помехоустойчивости.

• Хранение данных:
• Накопители на жёстких магнитных дисках (HDD) — турбо-коды применяются в каналах чтения для коррекции ошибок, вызванных шумами и межсимвольной интерференцией.
• Флэш-память NAND — в контроллерах SSD для повышения надёжности при многоуровневом хранении (MLC, TLC, QLC).

• Аудио- и видеокомпрессия:
• В системах цифрового радиовещания (DAB, DVB-T) для защиты сжатых потоков от ошибок.

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

• Турбо-коды стали первым классом кодов, которые практически достигли предела Шеннона, что ранее считалось невозможным для практических систем.
• Идея итеративного декодирования, лежащая в основе турбо-кодов, была независимо предложена в 1970-х годах для декодирования кодов с низкой плотностью проверок на чётность (LDPC), но не получила широкого распространения до появления турбо-кодов.
• В 2004 году турбо-коды были включены в стандарт космической связи CCSDS (Consultative Committee for Space Data Systems) для телеметрии и командных каналов.
• Алгоритм BCJR, используемый в декодерах турбо-кодов, был разработан в 1974 году, но его практическое применение стало возможным только с ростом вычислительных мощностей в 1990-х годах.

Критика и ограничения

Несмотря на высокую эффективность, турбо-коды имеют ряд недостатков:

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

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

Источники

• Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). «Near Shannon limit error-correcting coding and decoding: Turbo-codes». IEEE International Conference on Communications.
• 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.
• Sklar, B. (2001). «Digital Communications: Fundamentals and Applications». Prentice Hall.
• 3GPP TS 36.212: «Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding».
• CCSDS 131.0-B-3: «TM Synchronization and Channel Coding».