КОДЫ РИДА-СОЛОМОНА


Коды Рида-Соломона (Reed-Solomon codes). Для составления обзора использованы не всегда именованные файлы (их несложно найти) из Интернет. Суть кодирования заключается в представлении данных и кодирующего слова полиномами, а сам процесс кодирования – произведением полиномов. Важно, чтобы эти произведения гарантированно различались между собой несколькими битами. Это создает почву для исправления ошибок, технология исправления состоит в вычислении кода ошибки в итоге формальных полиномиальных операций. Кодирующий многочлен выполняет функцию увеличения кодового расстояния между минимально различающимися друг с другом словами сообщения (рассеиватель), код является частным случаем БЧХ-кода, т.е. это типичный пример.

Статья 1960 года «Полиномиальные коды над некоторыми конечными полями» Ирвина Рида и Густава Соломона, начинается с определения кода как "отображение векторного пространства размерности m над конечным полем K на векторное пространство более высокой размерности над тем же самым полем". В 1960 году не было такого понятия, как быстрая цифровая электроника, – во всяком случае, она была не такого уровня, как сегодня. Одной из ключевых фигур, развивших подход, был Элвин Берлекэмп, профессор электротехники в Университете Калифорнии в Беркли, который изобрел эффективный алгоритм декодирования кода Рида-Соломона. Силу предложения – увеличить расстояние между словами – следовало еще научиться использовать (эффективно исправляя ошибки).



На момент предложения не было теории декодирования



К 1960 году теория кодов коррекции ошибок просуществовала всего около десяти лет. Основная теория надежной цифровой связи была сформулирована Клодом Шенноном в конце 1940-х годов. В то же самое время, Ричард Хемминг представил изящный подход к коррекции одиночных ошибок и обнаружению двойной ошибки. В течение 1950-х годов большое количество исследователей начало экспериментировать со множеством кодов коррекции ошибок. Но, по словам МакЭлиса, со своей статьей в журнале «SIAM» Рид и Соломон «сорвали куш». Они разработали подход, при котором добавляется несколько дополнительных бит к исходному сообщению.

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

Код Рида-Соломона в полиномиальной арифметике конечных полей Галуа задается парой чисел N, K, где N – общее количество символов, а K – некоторое полезное количество символов, остальные N–K символов представляют собой избыточный код, предназначенный для восстановления ошибок. Такой код будет иметь так называемое "расстояние Хэмминга" D=N–K+1. Расстояние Хэмминга является параметром кода и определяется как минимальное число различий между двумя различными кодовыми словами. В соответствии с теорией кодирования, код, имеющий расстояние Хемминга D=2t+1, позволяет восстанавливать t ошибок. Таким образом, если в наше кодовое слово случайно внести t=(N–K)/2 ошибок (т.е. просто произвольно заменить значения t символов любыми значениями), то окажется возможным обнаружить и исправить эти ошибки.

Порождающий многочлен Рида-Соломона: g(x) = П(i = 1..D–1) (x+ai) = (x+a1)(x+a2)…(x+aD–1), здесь a – примитивный член. Учтя, что операция сложения равносильна операции вычитания, a1, a2, ..., aD–1 – корни этого многочлена. Например, порождающий многочлен для случая N=15, K=9: g(x) = (x+2)(x+22)(x+23)(x+24)(x+25)(x+26) = x6+7x5+9x4+3x3+12x2+10x+12. Код позволяет исправить до трех ошибок: (15 – 9 ) / 2 = 3.

Исходное сообщение задается коэффициентами полинома p(x) степени K–1, имеющего K коэффициентов. Кодирование представляет собой произведение полиномов C(x)=p(x)*g(x), где p(x) – код сообщения. Существует вариант систематического кодирования с приравниванием коэффициентов кода передаваемого сообщения первым коэффициентам C(x). Для этого полином сообщения сдвигается на K коэффициентов влево p'(x) = p(x)*x(N–k) и к нему прибавляется остаток от деления на порождающий полином: C(x) = p'(x) + p'(x) mod g(x).

Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.

Невязка e(x)=C(x) mod g(x) = 0. Равенство нарушается, если аддитивная помеха не кратна порождающему полиному. Декодирование связано с построением пары вспомогательных многочленов: полином синдромного декодера S(x) и многочлен локаторов L(x). Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажен коэффициент при x4, локатор этой ошибки равен a4. Многочлен локаторов L(x) – это многочлен, корни которого (их можно найти перебором) обратны локаторам ошибок.

Коэффициенты многочлена синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен e(x) = C(x) mod g(x), или в сам многочлен сообщения C(x): Si = e(ai+1) или Si = C(ai+1). Между L(x) и S(x) существует соотношение L(x)*S(x) = W(x) mod xN–k, W(x) называется многочленом ошибок. Степень многочлена W(x) не может превышать u–1, где u – количество ошибок.

Максимальное количество ошибок, которые может исправить код Рида-Соломона, это (N–K)/2. Задаваясь этим значением, L(x)*S(x) = W(x) mod xN–k сводится к системе линейных алгебраических уравнений относительно коэффициентов полинома локаторов. Если матрица системы вырождена, степень понижается, понижается и размерность системы. Найти полином L(x) можно и другими методами, например, можно применить алгоритм Евклида поиска НОД или применить метод Берлекампа-Месси, который является наиболее эффективным.

Рид, ныне профессор электротехники в Университете Южной Калифорнии, по-прежнему работает над проблемами в теории кодирования. Соломон, недавно покинувший фирму «Хьюз эйркрафт компани», консультирует Лабораторию реактивного движения. Рид был в числе первых, кто увидел абстрактную алгебру в качестве основы для кодов, исправляющих ошибки. «Оглядываясь назад, это кажется очевидным» – рассказал он «SIAM news». Тем не менее, он добавил: «когда мы публиковали статью, теория кодирования не являлась предметом обсуждения». Оба автора понимали, что был достигнут хороший результат, но они не имели представления о том, какое влияние окажет их статья. Спустя три десятилетия мы его видим. Огромное множество применений, уже существующих и планируемых, решили вопрос практичности и значимости кодов Рида-Соломона. «Ясно, что они практичны, потому что теперь их использует каждый» – говорит Берлекэмп. Миллиарды долларов в современной технологии зависят от идей, основанных на оригинальной работе Рида и Соломона. Одним словом, «это была архиважная статья», как считает МакЭлис.

WIKI | БЧХ | Линейный код | Сверточный код | Турбо-код


Rambler's Top100