Решётчатые коды

Решётчатые коды (англ. trellis codes, trellis coded modulation, TCM) — класс корректирующих кодов, используемых в цифровой связи для повышения помехоустойчивости передачи данных без расширения полосы частот. Решётчатые коды объединяют процессы кодирования и модуляции в единую процедуру, что позволяет увеличить минимальное евклидово расстояние между сигнальными точками на constellation diagram (сигнальном созвездии) при той же скорости передачи данных. Основополагающая работа по решётчатым кодам была опубликована Готфридом Унгербёком в 1982 году.

История

Идея совмещения кодирования и модуляции возникла как ответ на фундаментальное ограничение классических помехоустойчивых кодов (например, кодов Хэмминга или свёрточных кодов). Традиционно кодирование увеличивало избыточность, что требовало расширения полосы пропускания канала. В 1970-х годах исследователи, включая Джеймса Массей и Дэвида Форни, предложили методы модуляции с расширенным сигнальным пространством, но именно Унгербёк в 1982 году сформулировал принцип решётчатого кодирования как систематический метод.

В 1984 году Унгербёк опубликовал расширенную версию своей работы в журнале IEEE Transactions on Information Theory, где описал алгоритмы построения кодов для фазовой модуляции (PSK) и квадратурной амплитудной модуляции (QAM). К 1990-м годам решётчатые коды стали стандартом в спутниковой связи, цифровом телевидении (DVB-T, DVB-S) и модемах для телефонных линий (V.32, V.34).

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

Основная идея

Решётчатый код отображает последовательность информационных бит не непосредственно на сигнальные точки (как в обычной модуляции), а на последовательность переходов между состояниями конечного автомата, представленного решётчатой диаграммой (trellis diagram). Каждому переходу сопоставлена сигнальная точка из расширенного созвездия. Расширение созвездия (например, от 4-PSK к 8-PSK) компенсирует избыточность, вносимую кодированием, и не требует увеличения полосы.

Решётчатая диаграмма

Решётчатая диаграмма — это граф, где узлы представляют состояния кодера, а рёбра — возможные переходы между ними. Каждый переход соответствует подмножеству сигнальных точек. Например, для свёрточного кодера с памятью \( k \) число состояний равно \( 2^k \). Диаграмма развёрнута во времени: на каждом такте кодер переходит из текущего состояния в следующее, генерируя сигнальный символ.

Разделение на подмножества (set partitioning)

Ключевая техника Унгербёка — иерархическое разбиение сигнального созвездия на подмножества с увеличивающимся минимальным евклидовым расстоянием. Например, для 8-PSK:

• Первый уровень: всё созвездие (8 точек, расстояние \( d_1 \)).
• Второй уровень: два подмножества по 4 точки (\( d_2 > d_1 \)).
• Третий уровень: четыре подмножества по 2 точки (\( d_3 > d_2 \)).
• Четвёртый уровень: восемь подмножеств по 1 точке (\( d_4 = \infty \)).

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

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

Декодирование решётчатых кодов выполняется алгоритмом Витерби, который находит наиболее вероятный путь по решётчатой диаграмме на основе метрик евклидова расстояния между принятым сигналом и возможными сигнальными точками. Алгоритм использует принцип динамического программирования, что делает его эффективным для кодов с умеренной памятью (обычно до 8–10 состояний).

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

Решётчатые коды классифицируются по нескольким признакам:

По типу модуляции

• Коды для фазовой модуляции (PSK-TCM): используются в спутниковой связи (например, 8-PSK TCM).
• Коды для квадратурной амплитудной модуляции (QAM-TCM): применяются в цифровом телевидении и модемах (16-QAM, 64-QAM TCM).
• Коды для амплитудной модуляции (PAM-TCM): реже, в основном в проводных линиях.

По структуре кодера

• Свёрточные решётчатые коды: классические коды Унгербёка на основе свёрточных кодеров с памятью.
• Решётчатые коды на основе блочных кодов: например, коды на основе кодов Рида — Соломона или LDPC, но с решётчатой структурой.
• Многомерные решётчатые коды: используют сигнальные созвездия в пространстве размерности >2 (например, 4D-TCM в модемах V.34).

По числу состояний

• Малочисленные (4–16 состояний): простые реализации, низкая задержка.
• Средние (32–128 состояний): баланс между сложностью и выигрышем.
• Многочисленные (256 и более): высокий выигрыш, но сложность декодирования растёт экспоненциально.

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

Асимптотический выигрыш кодирования (coding gain)

Основной параметр решётчатых кодов — асимптотический выигрыш по отношению к некодированной модуляции той же спектральной эффективности. Для 8-PSK TCM с 4 состояниями выигрыш составляет около 3 дБ, для 16-QAM TCM с 8 состояниями — до 4 дБ. Теоретический предел для решётчатых кодов — 6–7 дБ при большой сложности.

Спектральная эффективность

Решётчатые коды не расширяют полосу, так как избыточность компенсируется расширением созвездия. Например, код со скоростью 2/3 на 8-PSK передаёт 2 бита на символ — столько же, сколько некодированная 4-PSK, но с лучшей помехоустойчивостью.

Задержка

Задержка кодирования и декодирования пропорциональна длине пути в решётке (обычно 10–20 символов) и незначительна для большинства приложений.

Применение

Решётчатые коды широко используются в системах связи, где важна экономия полосы частот:

• Цифровое телевидение: стандарты DVB-T (наземное), DVB-S (спутниковое), DVB-C (кабельное) используют TCM с QAM-модуляцией.
• Спутниковая связь: коды Унгербёка с 8-PSK и 16-QAM применяются в системах VSAT и спутникового интернета.
• Телефонные модемы: стандарты V.32 (9600 бит/с), V.34 (33 600 бит/с) основаны на многомерных решётчатых кодах.
• Беспроводные сети: в стандарте IEEE 802.11a/g (Wi-Fi) используется свёрточное кодирование с решётчатой модуляцией для OFDM.
• Глубокий космос: в миссиях NASA (например, «Вояджер») применялись решётчатые коды для связи с Землёй.

Преимущества и ограничения

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

• Высокая помехоустойчивость без расширения полосы.
• Относительно простая реализация декодера Витерби для кодов с небольшим числом состояний.
• Хорошо сочетается с перемежением и турбо-кодами.

Ограничения

• Экспоненциальный рост сложности декодирования с увеличением числа состояний (для 256 состояний требуется 256 метрик на такт).
• Чувствительность к фазовым шумам и нелинейностям канала.
• Меньший выигрыш по сравнению с турбо-кодами или LDPC-кодами при очень низких отношениях сигнал/шум.

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

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

• Первая коммерческая реализация решётчатых кодов была в модеме Codex 2680 (1984 год), который работал на скорости 19 200 бит/с по телефонным линиям.
• Готфрид Унгербёк получил премию IEEE Richard W. Hamming Medal (1994) и Marconi Prize (1998) за вклад в теорию кодирования.
• В 1990-х годах решётчатые коды были вытеснены турбо-кодами в спутниковой связи, но остаются стандартом в цифровом телевидении из-за простоты реализации.

Источники

• Ungerboeck G. Channel coding with multilevel/phase signals // IEEE Transactions on Information Theory. — 1982. — Vol. 28, № 1. — P. 55–67.
• Ungerboeck G. Trellis-coded modulation with redundant signal sets. Part I: Introduction // IEEE Communications Magazine. — 1987. — Vol. 25, № 2. — P. 5–11.
• Biglieri E., Divsalar D., McLane P., Simon M. Introduction to Trellis-Coded Modulation with Applications. — Macmillan, 1991.
• Proakis J., Salehi M. Digital Communications. — 5th ed. — McGraw-Hill, 2007. — Chapter 8.
• Viterbi A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE Transactions on Information Theory. — 1967. — Vol. 13, № 2. — P. 260–269.