Reed-Solomon

Коды Рида — Соломона (Reed-Solomon codes, RS-коды) — это класс недвоичных циклических кодов, исправляющих ошибки, построенных на основе конечных полей (полей Галуа). Они относятся к помехоустойчивым кодам и позволяют обнаруживать и корректировать множественные пакетные ошибки в цифровых данных. Коды Рида — Соломона широко применяются в системах хранения данных (CD, DVD, Blu-ray), в цифровых телекоммуникациях (спутниковая связь, DSL), в системах массовой памяти (RAID 6) и в кодах коррекции ошибок для QR-кодов.

История

Коды Рида — Соломона были разработаны в 1960 году сотрудниками Массачусетского технологического института Ирвингом Ридом и Густавом Соломоном. Первоначальная работа была опубликована в статье «Polynomial Codes over Certain Finite Fields» в журнале Journal of the Society for Industrial and Applied Mathematics. В ней авторы предложили метод кодирования, основанный на представлении сообщения в виде коэффициентов многочлена, значения которого вычисляются в различных точках поля. Идея заключалась в том, что если многочлен степени \( k-1 \) задан своими значениями в \( n \) точках, то даже при искажении части этих значений исходный многочлен можно восстановить, если количество ошибок не превышает определённого порога.

В 1960-е годы коды оставались в основном теоретической конструкцией из-за сложности реализации декодирования. Практический прорыв произошёл в 1969 году, когда Элвин Берлекэмп предложил алгоритм факторизации многочленов для декодирования, а затем, совместно с Джеймсом Мэсси, разработал алгоритм Берлекэмпа — Мэсси, который стал основой для эффективного декодирования RS-кодов. В 1970-е годы были созданы первые аппаратные реализации, а с 1980-х годов коды Рида — Соломона стали стандартом в оптических носителях информации (компакт-диски, DVD) и в спутниковой связи.

Математические основы

Поле Галуа

Коды Рида — Соломона оперируют над конечным полем \( GF(q) \), где \( q = p^m \), \( p \) — простое число, \( m \) — натуральное число. Наиболее распространены двоичные поля \( GF(2^m) \), в которых каждый элемент поля представляется \( m \)-битным двоичным числом. Например, в стандартном RS-коде для компакт-дисков используется поле \( GF(2^8) \), где каждый символ кода — это 8-битный байт.

Принцип кодирования

Пусть исходное сообщение состоит из \( k \) символов поля \( GF(q) \). Эти символы интерпретируются как коэффициенты многочлена \( M(x) \) степени \( k-1 \): \[ M(x) = m_{k-1} x^{k-1} + m_{k-2} x^{k-2} + \dots + m_1 x + m_0. \] Кодовое слово длины \( n \) (\( n > k \)) формируется как набор значений этого многочлена в \( n \) различных ненулевых точках поля \( GF(q) \): \[ C = (M(\alpha^0), M(\alpha^1), M(\alpha^2), \dots, M(\alpha^{n-1})), \] где \( \alpha \) — примитивный элемент поля. Таким образом, кодовое слово содержит \( n \) символов, каждый из которых является элементом поля.

Параметры кода

Код Рида — Соломона обозначается как \( RS(n, k) \), где:

• \( n \) — длина кодового слова (количество символов);
• \( k \) — длина исходного сообщения (количество информационных символов);
• \( n - k \) — количество проверочных символов.

Максимальная исправляющая способность кода: код может исправить до \( t \) ошибочных символов, где \[ t = \left\lfloor \frac{n - k}{2} \right\rfloor. \] Например, код \( RS(255, 223) \) может исправить до 16 ошибочных символов.

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

По длине кодового слова

• Примитивные коды: длина \( n = q - 1 \), где \( q \) — размер поля. Например, \( RS(255, 223) \) в поле \( GF(256) \).
• Непримитивные коды: длина \( n < q - 1 \). Используются, когда требуется нестандартная длина кодового слова.

По типу поля

• Двоичные коды: работают в поле \( GF(2^m) \). Наиболее распространены, так как легко реализуются в цифровой логике.
• Недвоичные коды: работают в полях \( GF(p^m) \) с \( p > 2 \). Используются реже, обычно в специализированных системах.

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

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

Устройство и реализация

Кодер

Кодер RS-кода обычно реализуется как линейный регистр сдвига с обратной связью (LFSR). На вход подаются \( k \) информационных символов, затем вычисляются \( n - k \) проверочных символов путём деления многочлена сообщения на порождающий многочлен кода. Порождающий многочлен \( G(x) \) имеет степень \( n - k \) и строится как произведение \( (x - \alpha^i) \) для \( i \) от 1 до \( n - k \).

Декодер

Декодирование RS-кода включает несколько этапов:

1. Вычисление синдрома: по принятому кодовому слову вычисляются синдромы \( S_i \) — значения многочлена ошибок в точках \( \alpha^i \).
2. Построение многочлена локаторов ошибок: с помощью алгоритма Берлекэмпа — Мэсси или алгоритма Евклида находится многочлен, корни которого указывают на позиции ошибок.
3. Поиск корней: корни многочлена локаторов находятся методом Ченя (перебором всех возможных позиций).
4. Вычисление значений ошибок: по позициям ошибок и синдромам вычисляются их величины с помощью алгоритма Форни.
5. Исправление: из принятого слова вычитаются найденные ошибки.

Применение

Оптические носители информации

• Компакт-диски (CD): используется код \( RS(32, 28) \) с перемежением (Cross-Interleaved Reed-Solomon Code, CIRC). Позволяет исправлять до 2 ошибочных байтов на блок.
• DVD: применяется код \( RS(208, 192) \) с перемежением (RS-PC). Обеспечивает исправление до 8 ошибочных байтов.
• Blu-ray: используется код \( RS(248, 216) \) с перемежением (LDC — Long Distance Code). Корректирует до 16 ошибочных байтов.

Цифровые телекоммуникации

• Спутниковая связь: стандарт DVB-S использует код \( RS(255, 239) \) для защиты от ошибок в канале.
• DSL (ADSL, VDSL): применяется код \( RS(255, 239) \) для коррекции пакетных ошибок.
• WiMAX (IEEE 802.16): использует код \( RS(255, 239) \) в сочетании с свёрточным кодированием.

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

• RAID 6: в некоторых реализациях (например, Linux MD RAID) коды Рида — Соломона используются для восстановления данных при отказе двух дисков.
• Флэш-память (NAND): контроллеры SSD и USB-флешек применяют RS-коды для коррекции ошибок, вызванных износом ячеек.

QR-коды

В QR-кодах используются коды Рида — Соломона для коррекции ошибок. В зависимости от уровня коррекции (L, M, Q, H) может восстанавливаться от 7% до 30% повреждённых данных.

Космическая связь

Коды Рида — Соломона применялись в программе «Вояджер» (NASA) для передачи изображений с Юпитера и Сатурна. В настоящее время используются в стандарте CCSDS (Consultative Committee for Space Data Systems).

Достоинства и недостатки

Достоинства

• Высокая исправляющая способность: код может исправить до \( (n-k)/2 \) ошибочных символов.
• Эффективность против пакетных ошибок: так как ошибки искажают целые символы (байты), RS-коды хорошо справляются с длинными последовательностями битовых ошибок.
• Относительно простая аппаратная реализация на регистрах сдвига.

Недостатки

• Вычислительная сложность декодирования растёт квадратично с длиной кода \( n \).
• Для коротких кодов (малое \( n \)) эффективность падает.
• Необходимость точной синхронизации символов (знание границ кодовых слов).

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

• Коды Рида — Соломона являются частным случаем кодов БЧХ (Боуза — Чоудхури — Хоквингема) и одновременно подклассом кодов Гоппы.
• В 2003 году алгоритм декодирования RS-кодов был улучшен с использованием методов быстрого преобразования Фурье в конечных полях, что позволило снизить сложность с \( O(n^2) \) до \( O(n \log^2 n) \).
• Коды Рида — Соломона используются в системе глобального позиционирования GPS для защиты навигационных сообщений.

Источники

• Reed, I. S.; Solomon, G. (1960). «Polynomial Codes over Certain Finite Fields». Journal of the Society for Industrial and Applied Mathematics.
• Berlekamp, E. R. (1968). «Algebraic Coding Theory». McGraw-Hill.
• MacWilliams, F. J.; Sloane, N. J. A. (1977). «The Theory of Error-Correcting Codes». North-Holland.
• Wicker, S. B.; Bhargava, V. K. (1994). «Reed-Solomon Codes and Their Applications». IEEE Press.
• Стандарт CCSDS 131.0-B-3 (2017). «TM Synchronization and Channel Coding».