Открыть сервис
Главная → Блог → Код Рида-Соломона

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

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

История

Коды Рида-Соломона были разработаны в 1960 году двумя сотрудниками Лаборатории Линкольна Массачусетского технологического института — Ирвингом Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon). Их работа «Polynomial Codes over Certain Finite Fields» была опубликована в Journal of the Society for Industrial and Applied Mathematics. Изначально коды не получили широкого практического применения из-за сложности реализации декодирования. Ситуация изменилась в 1968 году, когда Элвин Берлекэмп (Elwyn Berlekamp) предложил эффективный алгоритм декодирования, а затем в 1971 году Роберт Уэлч (Robert Welch) разработал более эффективный алгоритм Берлекэмпа — Уэлча. В 1970–1980-х годах, с развитием цифровой электроники и появлением недорогих интегральных схем, коды Рида-Соломона стали активно внедряться в системы записи и передачи данных.

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

Конечные поля Галуа

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

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

Исходное сообщение представляется в виде многочлена степени не выше \(k-1\) над \(GF(2^m)\):

\[ M(x) = c_{k-1}x^{k-1} + c_{k-2}x^{k-2} + \dots + c_0 \]

Кодовое слово длины \(n = 2^m - 1\) получается путём умножения информационного многочлена на порождающий многочлен \(g(x)\) степени \(n-k\):

\[ C(x) = M(x) \cdot g(x) \]

Порождающий многочлен строится как произведение \((x - \alpha^i)\) для \(i\) от 0 до \(n-k-1\), где \(\alpha\) — примитивный элемент поля Галуа. Альтернативный эквивалентный подход — систематическое кодирование, при котором информационные символы остаются неизменными, а к ним добавляются проверочные символы.

Параметры

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

Кодовое расстояние (минимальное расстояние Хэмминга) для кода RS\((n, k)\) равно \(d_{\min} = n - k + 1\). Это свойство делает коды Рида-Соломона оптимальными в смысле границы Синглтона: для кодов с исправлением ошибок максимально возможное количество исправляемых ошибок не превосходит \(\lfloor (d_{\min} - 1)/2 \rfloor\).

Корректирующая способность

Код RS\((n, k)\) способен исправлять до \(t = \lfloor (n - k)/2 \rfloor\) ошибок в символах (пакетов ошибок) или обнаруживать до \(d_{\min} - 1 = n - k\) ошибок. Каждая ошибка в символе означает искажение всех \(m\) битов этого символа, поэтому код эффективен против пакетных ошибок.

Виды и модификации

Укороченные и расширенные коды

В практических системах часто используются укороченные коды: исходный код длины \(n\) урезается до меньшей длины \(n' < n\) путём исключения части нулевых информационных символов. Расширенные коды имеют длину \(n = 2^m\) (добавляется один символ общей проверки на чётность). Например, в стандарте цифрового телевидения DVB-S используется код RS(204, 188), который является укороченным от RS(255, 239).

Свёрточные коды и каскадные схемы

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

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

Классический алгоритм Берлекэмпа — Уэлча

Декодирование кодов Рида-Соломона включает этапы:

  1. Вычисление синдрома ошибок.
  2. Нахождение многочлена локаторов ошибок (например, алгоритм Берлекэмпа — Мэсси или алгоритм Берлекэмпа — Уэлча).
  3. Нахождение корней многочлена локаторов (поиск Ченя).
  4. Вычисление значений ошибок (алгоритм Форни).
  5. Исправление ошибочных символов.

Современные алгоритмы

В настоящее время широко применяются алгоритмы декодирования с использованием быстрого преобразования Фурье над конечными полями (FFT-based decoding). Существуют также декодеры с фиксированной задержкой и декодеры с мягким решением (soft-decision decoding), повышающие эффективность в каналах с недвоичными модуляциями.

Применение

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

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

Коды QR и двухмерные штрихкоды

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

Спутниковая навигация

В системе глобального позиционирования GPS используется код Рида-Соломона в навигационных сообщениях для исправления ошибок в канале L2C.

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

В стандартах CCSDS (Consultative Committee for Space Data Systems) для телеуправления и телеизмерений применяются коды Рида-Соломона с параметрами RS(255, 223) и RS(63, 47).

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

Достоинства

Недостатки

Пример кода

Параметры: RS(15, 9) над полем \(GF(2^4)\) (m=4). Информационная часть: 9 символов (9 × 4 = 36 бит). Проверочных символов: 6. Код может исправлять до 3 ошибок в символах (t = (15-9)/2 = 3). Порождающий многочлен степени 6 строится на основе примитивного элемента \(\alpha\) поля \(GF(16)\). На практике такие малые длины используются только в учебных целях; реальное применение — RS(255, 223) или их укороченные версии.

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

См. также

Источники

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы