Коррекция ошибок

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

История

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

Первым практическим кодом коррекции ошибок стал код Хэмминга, предложенный Ричардом Хэммингом в 1950 году. Этот код позволял обнаруживать и исправлять одиночные ошибки в блоках данных. В 1960-х годах были разработаны циклические коды (коды БЧХ, коды Рида — Соломона), которые нашли широкое применение в системах хранения данных (компакт-диски, жёсткие диски) и спутниковой связи.

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

Классификация методов

Методы коррекции ошибок делятся на две основные категории в зависимости от подхода к исправлению:

Обнаружение ошибок с повторной передачей (ARQ — Automatic Repeat reQuest)

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

Упреждающая коррекция ошибок (FEC — Forward Error Correction)

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

Гибридные схемы (HARQ — Hybrid ARQ)

Сочетают элементы ARQ и FEC: приёмник сначала пытается исправить ошибки с помощью избыточности, а при неудаче запрашивает повторную передачу. Применяются в стандартах LTE и 5G.

Основные типы кодов коррекции ошибок

Блочные коды

Данные разбиваются на блоки фиксированной длины, к каждому блоку добавляется фиксированное число проверочных символов. К наиболее распространённым блочным кодам относятся:

• Код Хэмминга — исправляет одну ошибку в блоке. Минимальное кодовое расстояние d = 3.
• Код Рида — Соломона — работает с символами (байтами), исправляет пакеты ошибок (группы искажённых битов). Используется в компакт-дисках, QR-кодах, системах хранения RAID.
• Коды БЧХ (Боуза — Чоудхури — Хоквингема) — обобщение кодов Хэмминга, позволяют исправлять несколько ошибок.
• Коды LDPC — обеспечивают высокую эффективность при малой избыточности, применяются в Wi-Fi (802.11n/ac/ax), спутниковом телевидении DVB-S2.

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

Обрабатывают данные непрерывным потоком, используя регистры сдвига. Каждый выходной символ зависит от нескольких предыдущих входных символов. Декодирование выполняется алгоритмом Витерби (1967). Свёрточные коды применяются в сотовой связи (GSM, CDMA), спутниковой связи.

Турбокоды

Состоят из двух или более параллельно соединённых свёрточных кодеров, разделённых перемежителем. Декодирование выполняется итеративно с обменом «мягкими» решениями. Турбокоды обеспечивают высокую помехоустойчивость при умеренной сложности, используются в 3G/4G (UMTS, LTE).

Полярные коды

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

Применение

Системы хранения данных

• Жёсткие диски (HDD) и твердотельные накопители (SSD) используют коды LDPC и коды Рида — Соломона для коррекции ошибок чтения/записи.
• Оптические диски (CD, DVD, Blu-ray) применяют коды Рида — Соломона (Cross-Interleaved Reed-Solomon Code, CIRC).
• Оперативная память (ECC RAM) оснащается модулем коррекции ошибок (обычно код Хэмминга или SECDED — Single Error Correction, Double Error Detection), что критично для серверов и суперкомпьютеров.

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

• Спутниковая связь — коды свёрточные и Рида — Соломона, LDPC.
• Мобильная связь — турбокоды (3G, 4G), полярные коды (5G NR).
• Wi-Fi — LDPC (802.11n и новее).
• Цифровое телевидение (DVB-T2, DVB-S2) — LDPC и БЧХ.

Космическая техника

В системах связи с межпланетными станциями (NASA, ESA) используются коды с высокой избыточностью, способные исправлять множественные ошибки при экстремально низком отношении сигнал/шум. Например, код Рида — Соломона применялся в программе «Вояджер».

Криптография и защита информации

Коды коррекции ошибок используются в некоторых криптосистемах (криптосистема Мак-Элиса), а также в квантовой коррекции ошибок (коды Шора, стабилизаторные коды).

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

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

Декодирование сложных кодов (турбокоды, LDPC) требует значительных вычислительных ресурсов, что ограничивает их применение в устройствах с низким энергопотреблением. В системах реального времени задержка на декодирование может быть критичной.

Некоторые коды (например, коды Хэмминга) неэффективны при пакетных ошибках — групповых искажениях, характерных для радиоканалов с замираниями. Для борьбы с пакетными ошибками применяют перемежение (interleaving) — перестановку символов перед передачей.

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

• Принцип коррекции ошибок лежит в основе работы QR-кодов: код Рида — Соломона позволяет считать информацию даже при частичном повреждении изображения (до 30 % в зависимости от версии).
• В 1969 году код Рида — Соломона использовался для передачи фотографий с поверхности Луны в рамках программы «Аполлон».
• Квантовая коррекция ошибок — одна из ключевых проблем создания квантовых компьютеров: кубиты чрезвычайно чувствительны к шумам, и без эффективных кодов коррекции масштабирование квантовых систем невозможно.

Источники

• Шеннон К. Математическая теория связи. — 1948.
• Хэмминг Р. Коды, обнаруживающие и исправляющие ошибки. — 1950.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.
• Арыкан Э. Полярные коды: достижение пропускной способности канала. — 2009.
• ГОСТ Р 52070-2003. Коды помехоустойчивые. Термины и определения.