Помехоустойчивое кодирование

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

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

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

Ключевым понятием является кодовое расстояние (расстояние Хэмминга) — минимальное количество позиций, в которых различаются любые два различных кодовых слова. Чем больше кодовое расстояние, тем больше ошибок способен обнаружить или исправить код. Способность кода к исправлению ошибок определяется его минимальным расстоянием \( d \). Если \( d = 2t + 1 \), код гарантированно исправляет \( t \) ошибок в одном кодовом слове. Если \( d = t + 1 \), код гарантированно обнаруживает \( t \) ошибок.

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

Помехоустойчивые коды делятся на несколько основных категорий по различным признакам.

По способу обработки информации

• Блочные коды: Исходное сообщение разбивается на блоки фиксированной длины \( k \). Каждый блок кодируется независимо в кодовое слово длины \( n \) (\( n > k \)). Примеры: коды Хэмминга, коды Рида — Соломона, коды БЧХ (Боуза — Чоудхури — Хоквингема), коды Голея.
• Свёрточные коды: Кодирование осуществляется непрерывно, без разбиения на блоки. Выходные символы зависят не только от текущего информационного символа, но и от нескольких предыдущих, хранящихся в регистре сдвига. Свёрточные коды часто описываются с помощью решётчатых диаграмм и декодируются алгоритмом Витерби.

По характеру избыточности

• Систематические коды: В кодовом слове информационные символы явно присутствуют в неизменном виде, а проверочные символы добавляются к ним. Это упрощает извлечение информации. Большинство практических кодов (например, Рида — Соломона, Хэмминга) являются систематическими.
• Несистематические коды: Информационные символы в явном виде в кодовом слове не сохраняются; всё слово представляет собой результат некоторого преобразования.

По типу исправляемых ошибок

• Коды, исправляющие независимые ошибки: Предназначены для каналов, где ошибки возникают случайно и не зависят друг от друга (например, в каналах с аддитивным белым гауссовским шумом).
• Коды, исправляющие пакеты ошибок: Разработаны для каналов, где искажения затрагивают последовательные биты (например, из-за замираний в радиоканале или царапин на компакт-диске). Примеры: коды Рида — Соломона, коды Файра.
• Каскадные коды: Состоят из двух и более уровней кодирования. Внутренний код (обычно свёрточный или короткий блочный) исправляет отдельные ошибки, а внешний код (например, Рида — Соломона) исправляет пакеты ошибок, оставшиеся после декодирования внутреннего кода. Широко применяются в спутниковой связи и стандартах цифрового телевидения (DVB).

История развития

Первые теоретические основы помехоустойчивого кодирования были заложены Клодом Шенноном в его работе «Математическая теория связи» (1948). Шеннон доказал, что при скорости передачи, меньшей пропускной способности канала, существует код, позволяющий сделать вероятность ошибки сколь угодно малой. Однако он не указал, как построить такой код.

В 1950 году Ричард Хэмминг предложил первый практический код, исправляющий одиночные ошибки (код Хэмминга). В 1954 году Марсель Голе описал совершенный код (код Голея), исправляющий три ошибки. В 1959–1960 годах были разработаны коды БЧХ, обобщающие коды Хэмминга на случай исправления нескольких ошибок. В 1960 году Ирвинг Рид и Густав Соломон предложили коды Рида — Соломона, ставшие одними из самых популярных для исправления пакетов ошибок.

В 1955 году Питер Элайес ввёл понятие свёрточных кодов, а в 1967 году Эндрю Витерби разработал эффективный алгоритм их декодирования. В 1970-х годах началось активное применение помехоустойчивого кодирования в космической связи (программа «Вояджер» использовала каскадный код из свёрточного и кода Рида — Соломона).

Современный этап (с 1993 года) связан с открытием турбокодов (Клод Берру) и кодов с низкой плотностью проверок на чётность (LDPC), впервые предложенных Робертом Галлагером в 1963 году, но забытых на несколько десятилетий. Эти коды позволяют приблизиться к пределу Шеннона с высокой вычислительной эффективностью.

Применение

Помехоустойчивое кодирование является неотъемлемой частью практически всех современных цифровых систем передачи и хранения данных.

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

• Сотовая связь: В стандартах 3G, 4G (LTE) и 5G используются турбокоды и LDPC-коды для обеспечения надёжной передачи данных в условиях многолучевого распространения и помех.
• Спутниковая и космическая связь: Для передачи сигналов с зондов, находящихся за миллиарды километров от Земли, применяются каскадные коды и LDPC-коды. Например, в системе связи марсохода «Perseverance» используется LDPC-код.
• Цифровое телевидение и радиовещание: Стандарты DVB-T/T2, DVB-S/S2, ATSC и ISDB-T включают свёрточные коды и коды Рида — Соломона для защиты от помех в эфире.

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

• Жёсткие диски (HDD) и твердотельные накопители (SSD): Используются коды Рида — Соломона и LDPC-коды для исправления ошибок, возникающих из-за дефектов поверхности, сбоев чтения/записи или старения ячеек памяти.
• Оптические диски (CD, DVD, Blu-ray): Применяются каскадные коды Рида — Соломона (Cross-Interleaved Reed-Solomon Code, CIRC), позволяющие восстанавливать данные даже при наличии царапин или загрязнений на диске.
• RAID-массивы: Используют избыточные коды (например, коды Рида — Соломона) для восстановления данных при отказе одного или нескольких дисков.

Вычислительная техника

• Память ECC (Error-Correcting Code): В серверах и некоторых потребительских системах оперативная память использует коды Хэмминга или более сложные коды для автоматического исправления однобитовых ошибок и обнаружения двубитовых.
• Кэш-память процессоров: Некоторые процессоры (например, в архитектуре x86-64) применяют коды Хэмминга для защиты кэш-линий от сбоев.

Критерии эффективности

Выбор конкретного помехоустойчивого кода определяется компромиссом между несколькими параметрами:

• Избыточность: Отношение числа проверочных символов к общему числу символов в кодовом слове \( (n-k)/n \). Чем выше избыточность, тем больше служебных данных передаётся, что снижает полезную скорость.
• Корректирующая способность: Максимальное количество ошибок, которое код может гарантированно исправить.
• Сложность кодирования и декодирования: Определяет требования к вычислительным ресурсам и энергопотреблению. Например, декодирование LDPC-кодов требует итеративных алгоритмов, но может быть эффективно реализовано на специализированных микросхемах.
• Задержка: Время, необходимое для кодирования и декодирования блока данных. Для потоковых приложений (голосовая связь, видеоконференции) критична малая задержка.

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

• Код Голея (23,12) является совершенным кодом, то есть его шары радиуса 3 целиком покрывают всё пространство кодовых слов, не пересекаясь. Таких кодов существует очень мало.
• Коды Рида — Соломона широко используются в QR-кодах. Благодаря им, повреждённый или частично закрытый QR-код может быть успешно считан.
• В 2009 году NASA сообщило, что использование LDPC-кодов в системе связи с марсоходом «Opportunity» позволило увеличить скорость передачи данных в 2–3 раза по сравнению с предыдущими миссиями.

Источники

• Шеннон К. Математическая теория связи.
• Хэмминг Р. В. Коды, обнаруживающие и исправляющие ошибки.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования.
• Прокис Дж. Цифровая связь.
• Стандарты 3GPP (LTE, 5G NR).
• Стандарты DVB (Digital Video Broadcasting).