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

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

История

Концепция свёрточных кодов была впервые предложена Питером Элайесом в 1955 году в Массачусетском технологическом институте. В своей работе «Coding for Noisy Channels» он описал метод, при котором кодер использует регистр сдвига для хранения предыдущих битов, а выходные биты формируются как линейная комбинация содержимого регистра. Идея Элайеса заложила основу для теории свёрточного кодирования.

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

В 1970-х годах свёрточные коды начали активно применяться в космической связи, в частности, в программе NASA «Вояджер». В 1993 году Клод Берру и его коллеги представили турбокоды, которые представляют собой параллельную каскадную конструкцию из двух свёрточных кодеров, разделённых перемежителем. Турбокоды приблизились к теоретическому пределу Шеннона и произвели революцию в области помехоустойчивого кодирования.

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

Кодер

Кодер свёрточного кода строится на основе регистра сдвига с конечным числом ячеек памяти (K) и набора сумматоров по модулю 2 (XOR). Количество ячеек памяти определяет длину кодового ограничения (constraint length) — число бит, от которых зависит текущий выходной символ.

Процесс кодирования заключается в следующем:

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

Например, для кодера со скоростью 1/2 и длиной кодового ограничения K=3 (3 ячейки памяти) на каждый входной бит формируется два выходных бита. Порождающие полиномы (например, 7 и 5 в восьмеричной системе) определяют, какие ячейки участвуют в формировании каждого выходного бита.

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

Состояние кодера определяется содержимым регистра сдвига. Для кодера с K ячейками памяти существует 2^(K-1) возможных состояний. Переходы между состояниями при поступлении нового бита изображаются в виде решётчатой диаграммы (trellis diagram). Каждому переходу соответствует определённый выходной символ (кодовое слово). Решётчатая диаграмма является основой для алгоритма Витерби.

Декодер Витерби

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

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

Сложность алгоритма Витерби растёт экспоненциально с увеличением длины кодового ограничения, что ограничивает его применение для кодов с большим K.

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

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

По типу кодера

• Систематические коды: входная информационная последовательность явно присутствует в выходном потоке (один из выходных битов равен входному). Пример: код с обратной связью (RSC — Recursive Systematic Convolutional).
• Несистематические коды: входная последовательность не передаётся непосредственно. Большинство классических кодов (например, используемые в «Вояджере») являются несистематическими.

По скорости

• Высокоскоростные (R > 1/2): например, 2/3, 3/4, 7/8. Обеспечивают меньшую избыточность, но и меньшую корректирующую способность.
• Низкоскоростные (R < 1/2): например, 1/3, 1/4, 1/6. Обладают высокой избыточностью и лучшей помехоустойчивостью, но снижают эффективную скорость передачи.

По длине кодового ограничения

• Короткие (K = 3–5): простые в реализации, но с ограниченной корректирующей способностью.
• Средние (K = 6–9): наиболее распространённые в практических системах.
• Длинные (K > 10): сложные в декодировании, но обеспечивают высокую помехоустойчивость. Используются в космической связи.

По способу декодирования

• С жёстким решением: декодер принимает решение о значении каждого бита (0 или 1) на основе порога.
• С мягким решением: декодер использует аналоговую информацию о степени уверенности в принятом бите (например, 3-битное квантование). Обеспечивает выигрыш в 2–3 дБ по сравнению с жёстким решением.

Применение

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

• Космическая связь: коды с длиной ограничения K=7 и скоростью 1/2 использовались в миссиях NASA «Вояджер», «Галилео», «Марс-Патфайндер». В настоящее время применяются более сложные каскадные схемы.
• Спутниковая связь: стандарты DVB-S (Digital Video Broadcasting — Satellite) и DVB-S2 используют свёрточные коды в сочетании с кодами Рида-Соломона.
• Мобильная связь: в стандарте GSM для канала управления используется свёрточный код со скоростью 1/2 и длиной ограничения K=5. В 3G (UMTS) и 4G (LTE) применяются турбокоды, основанные на свёрточных кодах.
• Беспроводные сети: стандарты IEEE 802.11 (Wi-Fi) и IEEE 802.16 (WiMAX) используют свёрточные коды с различными скоростями и длинами ограничения.
• Цифровое телевидение: стандарты DVB-T (наземное), DVB-C (кабельное) и ATSC (американский стандарт) включают свёрточное кодирование.
• Хранение данных: в жёстких дисках и флеш-памяти (NAND) используются свёрточные коды для коррекции ошибок, особенно в SSD-накопителях с многоуровневыми ячейками (MLC, TLC).

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

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

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

Недостатки

• Экспоненциальный рост сложности: сложность декодера Витерби растёт как 2^(K-1), что ограничивает длину кодового ограничения.
• Пакетная ошибка: при ошибке декодирования алгоритм Витерби может породить длинную последовательность ошибок (burst error).
• Необходимость синхронизации: для корректной работы требуется точная синхронизация кодера и декодера по состоянию регистра.
• Отсутствие гарантии обнаружения ошибок: в отличие от некоторых блочных кодов, свёрточные коды не гарантируют обнаружение всех ошибок.

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

• Алгоритм Витерби, разработанный для декодирования свёрточных кодов, нашёл применение в других областях, таких как обработка речи (скрытые марковские модели) и биоинформатика (выравнивание последовательностей ДНК).
• Свёрточные коды с обратной связью (RSC) являются основой турбокодов, которые в 1993 году приблизились к пределу Шеннона на 0,5 дБ.
• В 2009 году NASA использовало свёрточные коды с длиной ограничения K=15 для связи с зондом «Новые горизонты» (New Horizons), что позволило передавать данные с Плутона на расстояние более 5 миллиардов километров.
• Существуют перфорированные свёрточные коды (punctured convolutional codes), которые позволяют изменять скорость кода без изменения базового кодера, путём периодического удаления (выкалывания) некоторых выходных символов.

Источники

• Элайес П. «Coding for Noisy Channels» (1955)
• Витерби А. «Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm» (1967)
• Мэсси Дж. «Threshold Decoding» (1963)
• Берру К., Главие А., Титтимайяма П. «Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes» (1993)
• Прокис Дж. «Цифровая связь» (4-е издание, 2001)
• Скляр Б. «Цифровая связь. Теоретические основы и практическое применение» (2-е издание, 2003)