Trellis¶

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

¶История

Метод решётчатого кодирования был впервые предложен в 1960-х годах в рамках развития теории свёрточных кодов. В 1967 году американский инженер Эндрю Витерби разработал алгоритм декодирования, названный его именем (алгоритм Витерби), который позволяет эффективно находить наиболее вероятный путь в решётке. Этот алгоритм стал основой для практического применения trellis-кодирования.

В 1982 году Готфрид Унгербёк, работавший в компании IBM, предложил метод решётчатого кодирования с модуляцией (Trellis Coded Modulation, TCM), который объединил кодирование и модуляцию в единый процесс. Это позволило значительно повысить помехоустойчивость передачи данных без расширения полосы частот. TCM стал стандартом в модемах для телефонных линий (например, стандарты V.32 и V.34) и в цифровом телевидении (DVB-T, ATSC).

¶Основные принципы

¶Решётка состояний

Trellis представляет собой граф, в котором каждый узел (состояние) соответствует определённой комбинации битов в регистре сдвига кодера. Вершины графа соединены рёбрами, каждое из которых соответствует переходу из одного состояния в другое при подаче на вход кодера очередного информационного бита. Рёбрам приписываются выходные символы, которые передаются в канал связи.

Пример: для свёрточного кодера с памятью 2 (два регистра) существует 4 состояния (00, 01, 10, 11). Каждое состояние имеет два возможных перехода (для входного бита 0 или 1), что образует решётку из 4 строк и множества столбцов, соответствующих временным тактам.

¶Кодирование

Процесс кодирования заключается в последовательном прохождении по решётке в соответствии с входными данными. Каждый информационный бит (или группа битов) вызывает переход из текущего состояния в следующее, при этом на выходе кодера формируется кодовое слово (обычно длиннее входного бита). Например, в свёрточном коде со скоростью 1/2 на каждый входной бит приходится два выходных бита.

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

Декодирование trellis-кода выполняется с помощью алгоритма Витерби, который находит в решётке путь с минимальной метрикой (например, минимальным расстоянием Хэмминга или Евклида). Алгоритм работает следующим образом:

1. Для каждого момента времени вычисляются метрики всех возможных путей, ведущих в каждое состояние.
2. Из всех путей, сходящихся в одно состояние, выбирается путь с наименьшей метрикой (выживший путь).
3. Процесс повторяется для всех тактов, после чего выполняется обратный проход для восстановления исходной последовательности.

Алгоритм Витерби гарантирует нахождение наиболее вероятной последовательности переданных данных при заданных принятых сигналах.

¶Виды trellis-кодирования

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

Свёрточные коды являются классическим примером trellis-кодирования. Они характеризуются памятью (количеством регистров сдвига) и скоростью (отношением числа входных битов к числу выходных). Свёрточные коды широко применяются в системах с низкой задержкой, таких как голосовая связь и спутниковая связь.

¶Решётчатое кодирование с модуляцией (TCM)

TCM объединяет свёрточное кодирование и модуляцию (например, QAM или PSK) в единый процесс. В TCM кодирование и модуляция оптимизируются совместно, что позволяет увеличить минимальное расстояние между сигнальными точками и, следовательно, повысить помехоустойчивость. TCM используется в модемах (V.32, V.34), цифровом телевидении (DVB-T, ATSC) и спутниковой связи.

¶Турбо-коды

Турбо-коды, предложенные в 1993 году, представляют собой параллельное или последовательное соединение двух свёрточных кодеров, разделённых перемежителем. Декодирование турбо-кодов выполняется итеративно с использованием модифицированного алгоритма Витерби или алгоритма MAP (Maximum A Posteriori). Турбо-коды обеспечивают производительность, близкую к теоретическому пределу Шеннона, и используются в стандартах мобильной связи (3G, 4G LTE) и спутниковой связи.

¶LDPC-коды

LDPC-коды (Low-Density Parity-Check) — это линейные блочные коды с разрежённой матрицей проверок на чётность. Хотя LDPC-коды не являются trellis-кодами в классическом смысле, их декодирование может быть представлено в виде решётки (фактор-графа) и выполняется с помощью алгоритма распространения доверия (Belief Propagation). LDPC-коды используются в стандартах 5G NR, Wi-Fi 6 (802.11ax) и цифровом телевидении DVB-S2.

¶Применение

¶Цифровая связь

Trellis-кодирование является основой для многих стандартов цифровой связи:

• Мобильная связь: в стандартах GSM, 3G (UMTS), 4G (LTE) используются свёрточные и турбо-коды.
• Спутниковая связь: в системах DVB-S и DVB-S2 применяются свёрточные коды и LDPC-коды.
• Цифровое телевидение: стандарты DVB-T, DVB-T2, ATSC и ISDB-T используют TCM и LDPC-коды.
• Модемы: стандарты V.32, V.34 и V.90 используют TCM для передачи данных по телефонным линиям.

¶Хранение данных

Trellis-кодирование применяется в системах хранения данных, таких как жёсткие диски и твердотельные накопители, для коррекции ошибок, вызванных дефектами поверхности или шумами считывания. В современных накопителях используются LDPC-коды и турбо-коды.

¶Квантовая связь

В квантовой связи trellis-кодирование используется для коррекции ошибок в квантовых каналах, где применяются квантовые свёрточные коды и квантовые LDPC-коды.

¶Преимущества и недостатки

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

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

¶Недостатки

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

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

• Алгоритм Витерби, разработанный для декодирования trellis-кодов, также используется в обработке речи (распознавание скрытых марковских моделей) и в биоинформатике (выравнивание последовательностей ДНК).
• Метод TCM позволил увеличить скорость передачи данных по телефонным линиям с 9,6 кбит/с (стандарт V.32) до 33,6 кбит/с (стандарт V.34) без расширения полосы частот.
• Турбо-коды, разработанные Клодом Берру и Аленом Главие, впервые позволили достичь производительности, отстоящей всего на 0,5 дБ от предела Шеннона, что считается революционным достижением в теории кодирования.

¶Источники

• В. В. Золотарев, Г. В. Овечкин. Помехоустойчивое кодирование. — М.: Горячая линия – Телеком, 2014.
• Дж. Г. Прокис. Цифровая связь. — М.: Радио и связь, 2000.
• Г. Унгербёк. Trellis Coded Modulation with Redundant Signal Sets. — IEEE Communications Magazine, 1987.
• Э. Витерби. Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. — IEEE Transactions on Information Theory, 1967.
• К. Берру, А. Главие. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes. — IEEE International Conference on Communications, 1993.