Введение, История, Формальное описание - Исправление ошибок с помощью кода Рида-Соломона

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

Код Рида-Соломона является частным случаем БЧХ-кода.

В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.

История

Код Рида-Соломона был изобретен в 1960 году сотрудниками лаборатории Линкольна Массачуссетскоготехнологического института Ирвином Ридом (англ.) и Густавом Соломоном (англ.). Идея использования этогокода была представлена в статье "Polynomial Codes over Certain Finite Fields". Первое применение код Рида-Соломона получил в 1982 году в серийном выпуске компакт-дисков. Эффективный алгоритмдекодирования был предложен в 1969 году Элвином Берлекэмпом (англ.) и Джэймсом Месси (англ.)

Формальное описание

Коды Рида-Соломона являются важным частным случаем БЧХ-кода, корни порождающего полиномакоторого лежат в том же поле, над каким и строится код (M = 1). Пусть б - элемент поля порядка. Если б - Примитивный элемент, то его порядок равен Q ? 1, то есть

Тогда нормированный полином G(X) минимальной степени надполем, корнями которого являются D ? 1 подряд идущих степеней элемента б, является порождающим полиномом кода Рида-Соломона над полем :

Где L0 - некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается L0 = 1. Степень многочлена равна D ? 1.

Длина полученного кода N, минимальное расстояние D (минимальное расстояние d линейного кода являетсяминимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код). Код содержит

R = D ?1 = deg(G(X))

Проверочных символов, где deg() обозначает степень полинома; число информационныхсимволов

K = N ? R = N ? D + 1

Таким образом

И код Рида-Соломона являетсяРазделимым Кодом С Максимальным Расстоянием (является оптимальным в смысле границы Синглтона).

Кодовый полином C(X) может быть получен из информационного полинома M(X),

,

Путем перемножения M(X) и G(X):

C(X) = M(X)G(X)

Похожие статьи




Введение, История, Формальное описание - Исправление ошибок с помощью кода Рида-Соломона

Предыдущая | Следующая