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

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

История

Коды были разработаны в 1960 году сотрудниками Массачусетского технологического института (MIT) Ирвингом Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon). Первоначальная работа была опубликована в статье «Polynomial Codes over Certain Finite Fields» в журнале Journal of the Society for Industrial and Applied Mathematics. В 1969 году Элвин Берлекэмп (Elwyn Berlekamp) и Джеймс Масси (James Massey) предложили эффективный алгоритм декодирования (алгоритм Берлекэмпа — Мэсси), что сделало практическое применение кодов РС экономически оправданным. В 1970-е годы коды начали использоваться в системах космической связи NASA (например, в программе «Вояджер»), а в 1980-х — в аудиоформате Compact Disc.

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

Поле Галуа

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

Порождающий многочлен

Код РС задаётся тремя параметрами:

• n — длина кодового слова (количество символов в блоке);
• k — количество информационных символов;
• t — максимальное количество ошибочных символов, которое код может гарантированно исправить.

Для кода РС выполняется соотношение: n = q — 1 (для примитивных кодов). Порождающий многочлен g(x) степени 2t строится как произведение минимальных многочленов поля:

\[ g(x) = (x — \alpha^1)(x — \alpha^2)\dots(x — \alpha^{2t}) \]

где α — примитивный элемент поля GF(q). Параметры кода связаны: n — k = 2t, то есть количество проверочных символов равно удвоенной исправляющей способности.

Основные характеристики

Исправляющая способность

Код Рида — Соломона с параметрами (n, k) может гарантированно исправить до t = (n — k)/2 ошибочных символов в любых позициях кодового слова. При этом если ошибки сконцентрированы в пакете (подряд идущие символы), код может исправить до n — k символов, но только в том случае, если позиции ошибок известны (стирания). В общем случае код РС является оптимальным по границе Синглтона: для любого линейного кода d_min ≤ n — k + 1, а для кодов РС это неравенство выполняется как равенство (d_min = n — k + 1).

Кодовое расстояние

Минимальное кодовое расстояние d_min для кода Рида — Соломона равно n — k + 1. Это означает, что любые два различных кодовых слова различаются не менее чем в d_min символах. Чем больше d_min, тем больше ошибок может обнаружить и исправить код.

Избыточность

Избыточность кода определяется отношением R = k/n. Чем ниже скорость кода R, тем выше помехоустойчивость, но тем больше служебных данных передаётся. На практике часто используют коды со скоростью от 0,5 до 0,9.

Алгоритмы кодирования и декодирования

Кодирование

Кодирование РС-кода выполняется систематическим способом: информационные символы остаются в явном виде, а проверочные символы вычисляются как остаток от деления многочлена информационного сообщения на порождающий многочлен. Алгоритм кодирования реализуется на регистрах сдвига с обратными связями (LFSR) и требует O(n) операций.

Декодирование

Декодирование РС-кодов — более сложная задача, чем кодирование. Основные этапы:

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

Современные реализации декодеров РС (например, на ПЛИС или в цифровых сигнальных процессорах) могут обрабатывать миллионы символов в секунду.

Применение

Накопители на оптических дисках

Коды Рида — Соломона являются основой систем коррекции ошибок в форматах CD (Cross-Interleaved Reed-Solomon Code, CIRC), DVD (RS-PC), Blu-ray и других. В CD используется два уровня кодирования: C1 (код (32,28)) и C2 (код (28,24)), что позволяет исправлять до 4000 последовательных битовых ошибок.

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

В системах хранения данных, таких как RAID 6, используется код Рида — Соломона для защиты от одновременного выхода из строя двух дисков. Данные разбиваются на блоки, и для каждой группы блоков вычисляются два проверочных блока (P и Q). В отличие от простого XOR (RAID 5), код РС позволяет восстановить данные при любых двух отказавших дисках.

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

Коды РС применяются в спутниковой связи (DVB-S, DVB-S2), в стандартах DSL (ADSL, VDSL), в системах WiMAX (IEEE 802.16) и в сотовой связи (как внешний код в турбокодах). Они особенно эффективны в каналах с пакетными ошибками, вызванными замираниями или помехами.

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

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

QR-коды

В QR-кодах (стандарт ISO/IEC 18004) используется код Рида — Соломона для коррекции ошибок. Уровень коррекции (L, M, Q, H) определяет количество избыточных символов: от 7% до 30% от общего объёма данных. Это позволяет считывать QR-коды даже при частичном повреждении изображения.

Разновидности и модификации

Укороченные коды

На практике часто используют укороченные коды РС, когда длина кодового слова n меньше, чем q — 1. Например, код (204, 188) в стандарте DVB-T — это укороченный вариант кода (255, 239). Укорочение не снижает корректирующую способность, но упрощает реализацию.

Расширенные коды

Расширенный код Рида — Соломона (Extended RS) добавляет один дополнительный символ (проверку на чётность), увеличивая n на 1. При этом минимальное расстояние увеличивается на 1, что позволяет исправлять дополнительную ошибку в некоторых случаях.

Каскадные схемы

Для достижения сверхвысокой помехоустойчивости коды РС часто комбинируют с другими кодами (например, свёрточными) в каскадных схемах. Внешний код (РС) исправляет пакетные ошибки, оставшиеся после внутреннего декодера.

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

Основным недостатком кодов Рида — Соломона является их чувствительность к длине кодового слова: при большом n возрастает сложность декодирования (особенно на этапе поиска локаторов). Кроме того, коды РС не являются оптимальными для каналов с независимыми (случайными) ошибками — в таких условиях лучше работают свёрточные коды или LDPC-коды. Для каналов с очень низким отношением сигнал/шум (например, глубокий космос) коды РС уступают по эффективности современным турбокодам и полярным кодам.

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

• Ирвинг Рид и Густав Соломон не публиковали алгоритма декодирования; первый практический декодер был разработан только через 9 лет после открытия кода.
• Код Рида — Соломона (255, 223) использовался в передатчиках «Вояджеров» и позволил получить первые детальные снимки внешних планет Солнечной системы.
• В стандарте Compact Disc код РС применяется в паре с перемежением (interleaving), что позволяет исправлять даже царапины длиной до 2 мм на поверхности диска.
• Коды РС являются частным случаем алгебраических геометрических кодов (кодов Гоппы), но их практическая значимость намного выше.

Источники

• 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.
• Wicker, S. B.; Bhargava, V. K. (1994). «Reed-Solomon Codes and Their Applications». IEEE Press.
• Peterson, W. W.; Weldon, E. J. (1972). «Error-Correcting Codes». MIT Press.
• ISO/IEC 18004:2015 «Information technology — Automatic identification and data capture techniques — QR Code bar code symbology specification».