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

Помогите с программной реализацией сабжа, исходником или алгоритмом в любом виде. Заранее благодарен.

Выдержка из старого доклада....

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

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

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

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

Если кодируемая информация i описывается набором (блоком) из k символов, то этому набору, или слову можно поставить в соответствие информационный многочлен

i(x)=ik-1xk-1+ik-2xk-2+...+i1x1+i0.

Так как цель кодирования - исправление ошибок, достигаемое благодаря введению избыточности, то каждому информационному слову должно соответствовать кодовое слово c=(cn-1, cn-2, ..., c1, c0) большей длины с добавленной избыточностью в виде дополнительных символов. Это кодовое слово также можно записать в виде многочлена

c(x)=cn-1xn-1+cn-2xn-2+...+c1x+c0.

В соответствии с теорией циклических кодов образование кодовых слов производится с помощью порождающего многочлена, степень которого равна числу дополнительных (проверочных) символов:

g(x)=gn-kxn-k+gn-k-1xn-k-1+...+g1x+g0.

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

Передаваемый по каналу связи или записываемый на магнитный носитель кодовый блок может претерпеть искажения, например, из-за шумов. Это можно в общем виде описать добавлением к кодовому блоку набора ошибок e, которому соответствует многочлен e(x)=en-1xn-1+en-2xn-2+...+e1x+e0. Принятому или воспроизведенному набору символов соответствует таким образом многочлен v(x)=c(x)+e(x). Найдя остаток от деления принятого многочлена v(x) на порождающий g(x), можно понять, были ли на самом деле ошибки. Если остаток равен нулю, значит принятое слово является кодовым и ошибок не было. Если остаток не равен нулю, то при передаче были ошибки. Остаток от деления дает многочлен, зависящий только от многочлена ошибки. Его называют синдромным многочленом. Cиндром - это совокупность симптомов, характеризующих заболевание. Синдромный многочлен s(x) зависит только от конфигурации ошибок, т.е. является синдромом, или описанием ошибок. Если число ошибок не превышает заданный предел t, то между e(x) и s(x) существует однозначное соответствие и с помощью определенных вычислений можно найти коэффициенты многочлена ошибок по синдромному многочлену. Таким образом можно восстановить переданный кодовый многочлен: c(x)=v(x)-e(x). Разделив c(x) на g(x), можно найти и информационный многочлен.

Помимо кодирования по правилу c(x)=i(x)g(x) существует так называемое систематическое правило кодирования, при котором k старших коэффициентов кодового слова устанавливаются равными коэффициентам информационного многочлена:

c(x)=ik-1xn-1+ik-2xn-2+...+i0 xn-k+

pn-k-1xn-k-1+...+p1x+p0.

(n-k) младших коэффициентов кодового слова p, часто называемых проверочными, подбираются такими, чтобы c(x) делился бы на g(x) без остатка. Это будет так, если соответствующий проверочный многочлен p(x)=pn-k-1xn-k-1+...+p1x+p0 рассчитывается как p(x)=-R[(xn-ki(x)):g(x)]. Систематическое правило кодирования дает кодовые слова, более удобные на практике, т.к. информационные слова в явном виде размещаются в k старших разрядах кодовых слов. Итак, если набор из символов образует блок информации i, кодируемой с целью обнаружения и исправления ошибок, то кодирование означает формирование блока c, который приобрел некоторую избыточность в виде дополнительных проверочных символов p. Эта избыточность имеет строго дозированную величину в соответствии с заданной степенью помехозащищенности (числом допустимых ошибок t). Промежуточные вычисления выполняются по правилам действий с многочленами.

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

- нахождение синдромного многочлена;

- вычисление многочлена ошибок s(x) по найденному синдромному многочлену (ошибки нет, если s(x)=0);

- восстановление переданного кодового многочлена;

- определение переданного блока информации по старшим коэффициентам восстановленного кодового многочлена.

В описанных выше процедурах блоки символов передаваемой и принимаемой информации представляют собой наборы значений некоторых сигналов. В видеотехнических приложениях вычисления должны выполняться над символами, которыми являются отсчеты видеосигнала. При 8 разрядах на отсчет символы образованы числами в диапазоне от 0 до 255, при 10 разрядах на отсчет определены 1024 символа в виде чисел от 0 до 1023. Таким образом, информационные слова представляют собой блоки из числовых значений отсчетов видеосигнала. Кодирование предполагает вычисления по правилам действий над многочленами, с коэффициентами которых надо выполнять действия сложения, вычитания, умножения и деления, причем эти вычисления не должны сопровождаться какими-либо округлениями промежуточных результатов (даже при делении), чтобы не вносить неопределенность. Поскольку это невозможно, то все вычисления надо делать так, чтобы и промежуточные, и конечные результаты не выходили за пределы этих множеств из 256 или 1024 чисел. Для этого надо использовать особую алгебру, правила вычислений которой отличаются от общеизвестных. Множества символов, для которых существует такая алгебра, называют полями Галуа.

Простейшее поле Галуа содержит 2 символа, которые можно складывать, вычитать, умножать и делить по следующим правилам: 0+0=0, 0+1=1, 1+1=0, 0-0=0, 1-1=0, 1-0=1, 0-1=1, 0*1=0, 1*1=1, 0/1=0, 1/1=1. Множество символов образует поле Галуа только в том случае, если число элементов равно целой степени простого числа. Для множеств из 256 и 1024 символов поля Галуа существуют. Они и их арифметика могут быть построены из простого поля из 2 элементов с помощью специальных многочленов. Формулы многочленов, порождающих поля Галуа, являются важной составной частью стандартов, описывающих системы защиты от ошибок, например, в цифровых видеомагнитофонах. Разумеется, в стандартах приводятся также описания порождающих многочленов кода и другие данные, относящиеся к кодированию. Современная микроэлектроника позволяет создавать интегральные схемы, способные выполнять описанные выше достаточно сложные вычисления, что создает условия для широкого применения мощных алгоритмов кодирования, исправляющего ошибки, при передаче и записи сигналов в цифровых видеосистемах.

Забыл ссылы по теме
http://www.matlab.ru/communication/book2/4/encode.asp MathLAB
http://www.625-net.ru/archive/0897/6.htm журнал 625 - net

Спасибо. Попробую реализовать.

GrAnd - молодец! доступнейшим образом все изложил!

GrAnd, может статеку в Журнал отправишь? Уж оч хороша

Господа некрофилы, уберите свои вилы...

Теме уже три года.