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

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

История

Коды были разработаны в 1960 году сотрудниками Массачусетского технологического института Ирвингом Ридом и Гюставом Соломоном. В своей работе «Polynomial Codes over Certain Finite Fields» они предложили метод кодирования, основанный на интерполяции многочленов над конечными полями. Первоначально алгоритм декодирования был неэффективен для практического применения, однако в 1969 году Элвин Берлекэмп и Джеймс Мэсси разработали алгоритм (алгоритм Берлекэмпа — Мэсси), который позволил декодировать коды за полиномиальное время. В 1970-х годах коды Рида-Соломона начали внедряться в системы связи NASA (например, в программе «Вояджер»), а затем стали стандартом для цифрового телевидения (DVB), спутниковой связи и оптических носителей.

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

Коды Рида-Соломона задаются параметрами (n, k, d), где:

n — длина кодового слова (количество символов),
k — количество информационных символов,
d — минимальное кодовое расстояние (d = n − k + 1).

Коды строятся над конечным полем GF(q), где q — степень простого числа (обычно q = 2^m, например, GF(256) для m=8). Каждый символ кода представляет собой элемент поля Галуа, то есть m-битное число. Код способен исправлять до t = (n − k)/2 ошибок или до n − k стираний (выпадений).

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

Информационное сообщение представляется в виде многочлена степени не выше k−1: \[ I(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{k-1} x^{k-1} \] где коэффициенты a_i — элементы поля GF(q). Кодовое слово получается путём вычисления значений этого многочлена в n различных точках поля (обычно используются степени примитивного элемента поля). Таким образом, кодовое слово — это последовательность из n символов-значений многочлена.

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

Декодирование основано на поиске многочлена ошибок и исправлении повреждённых символов. Основные этапы:

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

Если число ошибок не превышает t, код гарантированно восстанавливает исходные данные.

Классификация и виды

По длине кода

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

По типу применения

Коды с исправлением ошибок: стандартные коды Рида-Соломона, исправляющие произвольные ошибки.
Коды с исправлением стираний: если позиции потерянных символов известны, код может восстановить до n − k стираний.
Коды с каскадным кодированием: часто используются в паре с внутренним кодом (например, свёрточным) для повышения помехоустойчивости.

По способу реализации

Аппаратные кодеки: реализованы на ПЛИС или специализированных микросхемах (например, в контроллерах NAND-флеш).
Программные реализации: используются в библиотеках (например, в пакетах для обработки сигналов).

Применение

Цифровая связь и телевидение

Спутниковая связь: коды Рида-Соломона применяются в стандартах DVB-S и DVB-S2 для защиты от помех.
Цифровое телевидение: стандарты DVB-T, DVB-C, ATSC используют коды Рида-Соломона (204, 188) для исправления ошибок в транспортном потоке MPEG-TS.
Сотовая связь: в системах 4G/5G коды Рида-Соломона используются в каналах управления и для передачи служебной информации.

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

Оптические носители: CD, DVD, Blu-ray применяют коды Рида-Соломона для защиты от царапин и загрязнений. Например, в CD используется код (28, 24) с перекрестным перемежением (CIRC).
Массивы RAID: в системах RAID 6 (например, RAID-ZFS) коды Рида-Соломона позволяют восстанавливать данные при отказе двух дисков.
Флеш-память: NAND-флеш (SSD, USB-накопители) использует коды Рида-Соломона для коррекции ошибок, вызванных износом ячеек.

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

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

Штрихкоды и QR-коды

QR-коды: используют коды Рида-Соломона для восстановления данных при повреждении изображения (например, до 30% площади кода).
Data Matrix: аналогично применяет коды Рида-Соломона для маркировки товаров.

Характеристики и ограничения

Преимущества

Высокая эффективность исправления пакетов ошибок (до n − k символов подряд).
Гарантированное исправление любого числа ошибок, не превышающего t.
Возможность работы с различными размерами символов (от 2 до 16 бит и более).
Хорошая совместимость с каскадными схемами.

Недостатки

Низкая скорость декодирования при больших длинах кода (алгоритмы имеют сложность O(n^2) или O(n log^2 n)).
Чувствительность к ошибкам, превышающим исправляющую способность (ложное декодирование).
Требование к синхронизации символов (необходимо знать границы кодовых слов).

Примеры параметров

Применение	Параметры (n, k)	Поле GF	Исправляющая способность
CD (CIRC)	(28, 24)	GF(2^8)	до 2 ошибок
DVD	(208, 192)	GF(2^8)	до 8 ошибок
DVB-T	(204, 188)	GF(2^8)	до 8 ошибок
QR-код	(26, 16)	GF(2^8)	до 5 ошибок
RAID 6	(n, n-2)	GF(2^8)	до 2 отказов дисков

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

Коды Рида-Соломона являются частным случаем кодов БЧХ (Боуза — Чоудхури — Хоквингема) и одновременно оптимальными по границе Синглтона (d = n − k + 1).
В 1967 году Роберт Галлагер доказал, что коды Рида-Соломона являются максимально разделимыми (MDS-кодами).
В системах хранения данных (например, в файловой системе ZFS) коды Рида-Соломона используются для реализации RAID-Z с произвольным числом дисков.
В 2010-х годах появились варианты кодов Рида-Соломона с низкой плотностью проверок (LDPC-подобные), но они не получили массового распространения.

Источники

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. (1995). «Error Control Systems for Digital Communication and Storage». Prentice Hall.
ГОСТ Р 55689-2013 «Защита информации. Коды Рида-Соломона. Основные параметры».

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

На главную BFOmetr →