Свёрточный код

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

История

Концепция свёрточных кодов была впервые предложена американским математиком и инженером Питером Элиасом (Peter Elias) в 1955 году в его работе «Coding for Noisy Channels». Элиас, работавший в Массачусетском технологическом институте (MIT), обобщил идеи блочного кодирования на случай непрерывной последовательности, введя понятие рекуррентных (свёрточных) кодов. В 1960-х годах значительный вклад в развитие теории внёс Джеймс Мэсси (James Massey), который разработал алгоритм последовательного декодирования (алгоритм Фано) и предложил критерий минимального свободного расстояния для оценки эффективности кодов. В 1967 году Эндрю Витерби (Andrew Viterbi) опубликовал свой знаменитый алгоритм декодирования, который стал стандартным методом для практической реализации декодеров свёрточных кодов благодаря своей высокой производительности и оптимальности для каналов с аддитивным белым гауссовским шумом (АБГШ). В 1970-х годах свёрточные коды начали активно применяться в космической связи (например, в программах НАСА «Вояджер» и «Маринер»), а затем и в спутниковом телевидении, сотовой связи (стандарт GSM) и беспроводных сетях (Wi-Fi, IEEE 802.11).

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

Кодирование

Свёрточный кодер представляет собой конечный автомат, состоящий из регистра сдвига (памяти) и набора сумматоров по модулю 2 (XOR). Входной информационный поток битов последовательно подаётся на регистр сдвига. Каждый такт работы кодера сдвигает биты в регистре и вычисляет выходные символы как линейные комбинации (суммы по модулю 2) определённых ячеек регистра, задаваемых порождающими полиномами. Количество выходных символов на один входной бит определяет скорость кода R = k/n, где k — число входных битов за такт, а n — число выходных битов. Наиболее распространены коды со скоростью 1/2, 1/3, 2/3 и 3/4.

Пример: для кодера со скоростью 1/2, памятью m = 2 (регистр из 2 ячеек) и порождающими полиномами (7, 5) в восьмеричной записи (что соответствует двоичным 111 и 101) выходные биты вычисляются как:

• Выход 1: сумма текущего бита и двух предыдущих (полином 111).
• Выход 2: сумма текущего бита и предыдущего (полином 101).

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

Наиболее распространённым методом декодирования свёрточных кодов является алгоритм Витерби. Он основан на поиске наиболее вероятного пути в решётчатой диаграмме (trellis diagram), которая представляет все возможные состояния кодера. Алгоритм работает следующим образом:

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

Алгоритм Витерби обеспечивает декодирование по принципу максимального правдоподобия (ML) для каналов с АБГШ, но его сложность экспоненциально растёт с увеличением длины памяти кодера (числа состояний = 2^m). Для кодов с большой памятью (например, m > 10) применяют более сложные алгоритмы, такие как последовательное декодирование (алгоритм Фано) или алгоритм стека.

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

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

• По скорости: R = k/n, где k — число входных битов, n — число выходных битов. Скорость определяет избыточность кода: чем ниже скорость, тем выше корректирующая способность, но ниже пропускная способность.
• По длине памяти (constraint length): K = m + 1, где m — число ячеек регистра сдвига. Длина памяти определяет количество состояний кодера (2^m) и сложность декодирования.
• По типу порождающих полиномов: систематические (входная последовательность явно присутствует в выходном потоке) и несистематические.
• По типу завершения: с «хвостом» (tail-biting) — когда кодер начинается и заканчивается в одном и том же состоянии, и с принудительным обнулением (zero-tail) — когда в конце добавляются нулевые биты для обнуления регистра.
• По типу кода: рекурсивные систематические свёрточные коды (RSC), которые являются основой для турбо-кодов, и нерекурсивные несистематические (NSC).

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

Свободное расстояние

Ключевой характеристикой свёрточного кода является свободное расстояние d_free — минимальное расстояние Хэмминга между двумя различными кодовыми последовательностями бесконечной длины. Чем больше d_free, тем больше ошибок может исправить код. Свободное расстояние зависит от порождающих полиномов и длины памяти. Для кода (7, 5) со скоростью 1/2 и памятью m = 2 свободное расстояние равно 5, что позволяет исправить до 2 ошибок на пути минимальной длины.

Спектр расстояний

Спектр расстояний (или спектр весов) показывает количество кодовых последовательностей с заданным расстоянием Хэмминга от нулевой последовательности. Он используется для оценки вероятности ошибки декодирования.

Вероятность ошибки

Для свёрточных кодов с декодированием по алгоритму Витерби вероятность битовой ошибки (BER) в канале с АБГШ аппроксимируется выражением: P_b ≈ (1/k) B_d_free Q(√(2 d_free R E_b/N_0)) где B_d_free — количество путей с расстоянием d_free, E_b/N_0 — отношение сигнал/шум на бит, Q(x)* — функция Гауссова интеграла ошибок.

Применение

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

• Космическая и спутниковая связь: Использовались в программах «Вояджер» (код со скоростью 1/2 и памятью 7), «Галилео», «Марс-рейнджер». В современных системах часто комбинируются с кодами Рида-Соломона (каскадные коды).
• Сотовая связь: В стандарте GSM (Global System for Mobile Communications) применяется свёрточный код со скоростью 1/2 для канала трафика. В стандарте UMTS (3G) используются свёрточные коды с памятью 9 и скоростями 1/2 и 1/3.
• Беспроводные сети: В стандарте IEEE 802.11 (Wi-Fi) для защиты данных используются свёрточные коды со скоростями 1/2, 2/3, 3/4 и 5/6, а также их сочетание с перемежением (interleaving).
• Цифровое телевидение: В стандартах DVB-T, DVB-S, DVB-C применяются свёрточные коды с различными скоростями (от 1/2 до 7/8) в сочетании с кодами Рида-Соломона.
• Хранение данных: В некоторых системах хранения (например, в RAID-массивах) и в технологии NAND-флеш памяти используются свёрточные коды для коррекции ошибок.
• Глубокий космос: В миссиях НАСА и Европейского космического агентства (ESA) применяются свёрточные коды с большим свободным расстоянием (например, код с памятью 15 и скоростью 1/6).

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

• Свёрточные коды являются основой для турбо-кодов (Turbo codes), которые были предложены в 1993 году Клодом Берру (Claude Berrou) и позволяют приблизиться к пределу Шеннона по пропускной способности канала. Турбо-коды состоят из двух параллельно соединённых рекурсивных систематических свёрточных кодов (RSC) с итеративным декодированием.
• Алгоритм Витерби, используемый для декодирования, также применяется в обработке речи (скрытые марковские модели) и в биоинформатике (выравнивание последовательностей ДНК).
• В 1970-х годах свёрточные коды с памятью 7 и скоростью 1/2 использовались в системе связи «Вояджер» для передачи изображений Юпитера и Сатурна. Благодаря кодированию удалось снизить вероятность ошибки с 10^-1 до 10^-5 при том же отношении сигнал/шум.
• В стандарте LTE (4G) для канала управления используется свёрточный код с памятью 9 и скоростью 1/3, а для канала данных — турбо-код.

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

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

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

Источники

• Elias, P. (1955). «Coding for Noisy Channels». IRE Convention Record, Part 4, pp. 37–46.
• Viterbi, A. J. (1967). «Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm». IEEE Transactions on Information Theory, 13(2), pp. 260–269.
• Forney, G. D. (1973). «The Viterbi Algorithm». Proceedings of the IEEE, 61(3), pp. 268–278.
• Lin, S., & Costello, D. J. (2004). «Error Control Coding: Fundamentals and Applications» (2nd ed.). Pearson Prentice Hall.
• Proakis, J. G., & Salehi, M. (2008). «Digital Communications» (5th ed.). McGraw-Hill.
• Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). «Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes». IEEE International Conference on Communications, pp. 1064–1070.