Код с исправлением ошибок

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

История

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

В 1950 году Ричард Хэмминг, работавший в Bell Labs, создал первый практический код, способный исправлять одиночные ошибки, — код Хэмминга. Легенда гласит, что Хэмминга раздражали сбои в работе перфокарточного компьютера, из-за которых программа останавливалась при любой ошибке, и он решил разработать способ, позволяющий машине продолжать работу, автоматически исправляя неполадки. Коды Хэмминга до сих пор широко применяются в оперативной памяти (ECC-память) и простых системах связи.

В последующие десятилетия были разработаны более мощные классы кодов: циклические коды (включая коды Боуза — Чоудхури — Хоквингема, или БЧХ), свёрточные коды, каскадные коды. В 1993 году Клод Берру и Ален Главио представили турбокоды, которые вплотную приблизились к теоретическому пределу Шеннона. В начале 2000-х годов были открыты LDPC-коды (коды с малой плотностью проверок на чётность), которые также обеспечивают высокую эффективность и используются в современных стандартах связи, таких как Wi-Fi (802.11n/ac/ax), DVB-S2, 5G NR.

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

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

Процесс кодирования заключается в преобразовании блока из k информационных символов в блок из n символов (n > k), где n — длина кодового слова, а (n − k) — число проверочных символов. Отношение R = k/n называется скоростью кода. Чем выше скорость, тем меньше избыточность, но ниже помехоустойчивость.

Декодирование может выполняться несколькими методами:

• Жёсткое декодирование — принимается решение о каждом символе (0 или 1), и затем по этим решениям вычисляется наиболее вероятное кодовое слово.
• Мягкое декодирование — используется аналоговая информация о степени уверенности в каждом принятом символе, что позволяет существенно повысить эффективность (применяется в турбокодах и LDPC).

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

Коды с исправлением ошибок делятся на несколько основных категорий.

По типу обрабатываемых данных

• Блочные коды — данные разбиваются на блоки фиксированной длины, каждый блок кодируется независимо. Примеры: коды Хэмминга, БЧХ, Рида — Соломона, LDPC.
• Свёрточные коды — кодирование выполняется непрерывно над скользящим окном данных; текущий выходной символ зависит не только от текущего информационного, но и от нескольких предыдущих. Декодируются обычно алгоритмом Витерби.

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

• Коды, исправляющие одиночные ошибки (например, код Хэмминга (7,4) исправляет одну ошибку в блоке из 7 бит).
• Коды, исправляющие пакеты ошибок — предназначены для каналов, где ошибки возникают группами (например, коды Рида — Соломона, используемые в CD/DVD и QR-кодах).
• Коды, исправляющие множественные случайные ошибки (БЧХ, LDPC, турбокоды).

По линейности

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

Примеры распространённых кодов

Код Хэмминга (7,4)

Классический линейный блочный код, где на каждые 4 информационных бита добавляется 3 проверочных. Кодовое расстояние d = 3, что позволяет исправлять одну ошибку или обнаруживать две. Используется в ECC-памяти (Error-Correcting Code memory) для серверов и критичных систем.

Код Рида — Соломона

Недвоичный циклический код, работающий с символами (обычно байтами). Способен исправлять пакеты ошибок. Применяется в:

• хранении данных (CD, DVD, Blu-ray, QR-коды);
• спутниковой и цифровой связи (DVB);
• системах массового хранения (RAID-массивы уровня 6).

LDPC-коды (Low-Density Parity-Check)

Линейные блочные коды с разрежённой матрицей проверок на чётность. Обеспечивают производительность, близкую к пределу Шеннона, при относительно низкой сложности декодирования (итеративный алгоритм распространения доверия). Используются в:

• стандартах Wi-Fi (802.11n/ac/ax);
• спутниковом телевидении (DVB-S2, DVB-T2);
• сотовой связи 5G NR;
• Ethernet 10GBASE-T.

Турбокоды

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

• мобильной связи 3G/4G (UMTS, LTE);
• спутниковой связи (DVB-RCS);
• глубоком космосе (NASA).

Применение

Корректирующие коды используются повсеместно, где возможны искажения данных:

• Цифровая связь (сотовая, спутниковая, Wi-Fi, Bluetooth) — для борьбы с шумами и помехами в радиоканале.
• Хранение данных (жёсткие диски, SSD, оптические диски, флеш-память) — для компенсации дефектов носителя и старения ячеек.
• Оперативная память — ECC-память в серверах и рабочих станциях исправляет одиночные битовые ошибки, вызванные космическими частицами или деградацией.
• Космическая связь — из-за огромных расстояний и слабого сигнала используются мощные коды (например, свёрточные + код Рида — Соломона в миссиях NASA).
• QR-коды и штрихкоды — позволяют считывать информацию даже при частичном повреждении изображения.
• Цифровое телевидение (DVB-T, DVB-S) — обеспечивает устойчивый приём в условиях помех.

Ограничения и критика

Несмотря на эффективность, корректирующие коды не являются панацеей:

• Внесение избыточности снижает полезную скорость передачи данных (эффективная скорость = R × скорость канала).
• Увеличение корректирующей способности требует более длинных кодовых блоков, что вносит задержку (latency) — неприемлемо для приложений реального времени (голосовая связь, видеоконференции).
• Некоторые коды (например, турбокоды) требуют сложных итеративных декодеров, что увеличивает энергопотребление и стоимость оборудования.
• При превышении корректирующей способности (например, более 1 ошибки в блоке для кода Хэмминга) декодер может либо выдать неверное кодовое слово, либо сообщить о неисправимой ошибке — в любом случае данные будут потеряны.

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

Источники

• Шеннон К. Математическая теория связи (1948).
• Хэмминг Р. Коды, обнаруживающие и исправляющие ошибки (1950).
• Берру К., Главио А. Турбокоды: новый класс мощных корректирующих кодов (1993).
• Галлагер Р. Коды с малой плотностью проверок на чётность (1962, переоткрыты в 1990-х).
• Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки (1977).