Размещено на http://www.allbest.ru/

Содержание

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

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

Коды Рида-Соломона являются важным частным случаем БЧХ-кода, корни порождающего полиномакоторого лежат в том же поле, над каким и строится код (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)

3. Свойства

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

Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной t и менее, должен содержать по меньшей мере 2t проверочных символов.

Исправление многократных ошибок

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

(qm ? 1,qm ? 1 ? 2t)

-код Рида-Соломона над полем с кодовым расстоянием

d = 2t + 1

можнорассматривать как

((qm ? 1)m,(qm ? 1 ? 2t)m)

-код над полем , который может исправлять любуюкомбинацию ошибок, сосредоточенную в t или меньшем числе блоков из m символов. Наибольшее числоблоков длины m, которые может затронуть пакет длины li, где

,

не превосходит ti, поэтому код, который может исправить t блоков ошибок, всегда может исправить и любую комбинацию из pпакетов общей длины l, если

.

4. Практическая реализация

Кодирование с помощью кода Рида-Соломона может быть реализовано двумя способами:систематическим и несистематическим (см. [1], описание кодировщика).

При несистематическом кодировании информационное слово умножается на некий неприводимый полиномв поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлеченияинформационного слова нужно выполнить операцию декодирования и уже потом можно проверить данныена содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечениеинформационных данных, при этом они могут быть без ошибок.

Структурасистематического кодовогослова Рида-Соломона

При систематическом кодировании к информационному блоку из k символов приписываются 2t проверочныхсимволов, при вычислении каждого проверочного символа используются все k символов исходного блока. Вэтом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержитошибок, но кодировщик/декодировщик должен выполнить k(n ? k) операций сложения и умножения длягенерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то самиоперации кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритмдекодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка lnn2.

При операции кодирования информационный полином умножается на порождающий многочлен. Умножениеисходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнитьследующим образом:

К исходному слову приписываются 2t нулей, получается полином

.

Этот полином делится на порождающий полином G, находится остаток R, где Q - частное.

,

Этот остаток и будет корректирующем кодом Рида-Соломона, он приписывается к исходному блокусимволов. Полученное кодовое слово

.

Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит изячеек памяти, в каждой из которых находится один элемент поля Галуа.

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

Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательновыполняет следующие действия:

· Вычисляет синдром ошибки

· Строит полином ошибки

· Находит корни данного полинома

· Определяет характер ошибки

· Исправляет ошибки

Вычисление синдрома ошибки