8-900-374-94-44
Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 25%. Восстановить при этом можно количество данных, равное половине избыточных. Если емкость диска 700 Мб, то, получается, теоретически можно восстановить до 87,5 Мб из 700. При этом нам не обязательно знать, какой именно символ передан с ошибкой. Также стоит отметить, что вместе с кодированием используется перемежевание, когда байты разных блоков перемешиваются в определенном порядке, что в результате позволяет читать диски с обширными повреждениями, локализированными близко друг к другу (например, глубокие царапины), так как после операции, обратной перемежеванию, обширное повреждение оборачивается единичными ошибками во множестве блоков кода, которые поддаются восстановлению.Давайте возьмем простой пример и попробуем пройти весь путь – от кодирования до получения исходных данных на приемнике. Пусть нам нужно передать кодовое слово С, состоящее из двух чисел – 3 и 1 именно в такой последовательности, т.е. нам нужно передать вектор С=(3,1). Допустим, мы хотим исправить максимум две ошибки, не зная точно, где они могут появиться. Для этого нужно взять 2*2=4 избыточных символа. Запишем их нулями в нашем слове, т.е. С теперь равно (3,1,0,0,0,0). Далее необходимо немного разобраться с математическими особенностями.
Мы передаем слово с(4,1,0,2,5,6).
Запишем вектор ошибки F (последние 4 символа — синдром, который мы постоянно используем, два знака вопроса — на местах информационных символов, это маска ошибки) и обозначим каждый символ буквой:
Также много устройств используют готовые таблицы ошибок, рассчитанные заранее. В условиях использования арифметики Галуа получается конечное количество возможных ошибок. Это свойство и используется для уменьшения количества расчетов. Здесь в случае, если синдром получается ненулевой, он просто сравнивается с таблицей возможных ошибочных синдромов.
Курс теории кодирования для многих часто является одним из самых сложных. Буду рад, если данная статья кому-нибудь поможет разобраться в данной теме быстрее.
habr.com
Долгое время главным игроком в сфере безопасного хранения данных оставалась технология RAID. Подобные классические решения, наряду с известными плюсами, обладают и определёнными ограничениями. К ним можно отнести:
На данный момент наша команда занимается разработкой системы хранения данных TATLIN. По архитектуре системы мы планируем написать отдельную серию статей, тут лишь скажем, что в какой-то момент времени перед нами встала задача реализации собственной системы надёжного хранения данных. После изучения вопроса мы решили остановиться на проверенных временем кодах Рида-Соломона. Существуют готовые библиотеки (например, ISA-L от Intel или Jerasure авторства James S. Plank). В них реализованы соответствующие процедуры кодирования/декодирования. Но учитывая, что наша аппаратная платформа построена на базе архитектуры OpenPOWER, а вся логика системы реализована как модуль ядра ОС Linux, — было принято решение делать свою реализацию, оптимизированную под особенности нашей системы.
В этой первой статье я попытаюсь объяснить, о чем идет речь, когда говорят о кодах Рида-Соломона в контексте систем хранения данных. Начнем с простых примеров, которые позволят лучше уяснить сущность решаемых проблем.
Немного усложним задачу. Предположим, что исходных чисел не два, а три — , и . Как и прежде, нужен алгоритм, позволяющий справиться с потерей одного из исходных чисел. Легко заметить, что ничто не мешает снова использовать битовую операцию «Исключающее «ИЛИ»», . Для восстановления можно воспользоваться равенством .
Усложним задачу ещё немного. Как и прежде, имеется три числа , и , а вот потерять, в этот раз, мы можем не одно, а любые два из них. Очевидно, что просто использовать операцию «Исключающее «ИЛИ» уже не получится. Как же восстанавливать потерянные числа?
Попробуем разобраться с тем, как это работает, начав с более интуитивных вещей. Для этого вернемся к нашей последней задаче. Напомним, что есть три произвольных целых числа, любые два из них могут быть потеряны, необходимо научиться восстанавливать потерянные числа по оставшимся. Для этого применим «алгебраический» подход.
Но прежде необходимо напомнить еще об одном важном моменте. Технологии восстановления данных неспроста называются методами избыточного кодирования. По исходным данным вычисляются некоторые «избыточные», которые потом позволяют восстановить потерянные. Не вдаваясь в подробности заметим, что эмпирическое правило такое — чем больше данных может быть потеряно, тем больше «избыточных» необходимо иметь. В нашем случае для восстановления двух чисел, нам придётся по некоторому алгоритму сконструировать два «избыточных». В общем случае, если нужно поддерживать потерю чисел, необходимо соответственно иметь избыточных.
Упомянутый выше «алгебраический» подход состоит в следующем. Составляется матрица специального вида размера . Первые три строки этой матрицы образуют единичную матрицу, а последние две — это некоторые числа, о выборе которых мы поговорим позднее. В англоязычной литературе эту матрицу обычно называют generator matrix, в русскоязычной встречается несколько названий, в этой статье будет использоваться — порождающая матрица. Умножим сконструированную матрицу на вектор, составленный из исходных чисел , и .
В результате умножения матрицы на вектор с данными получаем два «избыточных» числа, обозначенных на рисунке как и . Давайте посмотрим, как с помощью этих «избыточных» данных можно восстановить, к примеру, потерянные и .
Вычеркнем из порождающей матрицы строки, соответствующие «пропавшим» данным. В нашем случае соответствует первой строке, а – второй. Полученную матрицу умножим на вектор с данными, и в результате получим следующее уравнение:
Проблема лишь в том, что и мы потеряли, и они нам теперь неизвестны. Как мы можем их найти? Есть очень элегантное решение этой проблемы.
Вычеркнем соответствующие строки из порождающей матрицы и найдём обратную к ней. На рисунке эта обратная матрица обозначена как . Теперь домножим левую и правую части исходного уравнения на эту обратную матрицу:
Сокращая матрицы в левой части уравнения (произведение обратной и прямой матриц есть единичная матрица), и учитывая тот факт, что в правой части уравнения нет неизвестных параметров, получаем выражения для искомых и .
Собственно говоря, то, что мы сейчас проделали — основа всех типов кодов Рида-Соломона, применяемых в системах хранения данных. Процесс кодирования заключается в нахождении «избыточных» данных , , а процесс декодирования — в нахождении обратной матрицы и умножения её на вектор «сохранившихся» данных.
Нетрудно заметить, что рассмотренная схема может быть обобщена на произвольное количество «исходных» и «избыточных» данных. Другими словами, по исходным числам можно построить избыточных, причем всегда возможно восстановить потерю любых из чисел. В этом случае порождающая матрица будет иметь размер , а верхняя часть матрицы размером будет единичной.
Вернемся к вопросу о построении порождающей матрицы. Можем ли мы выбрать числа произвольным образом? Ответ – нет. Выбирать их нужно таким образом, чтобы вне зависимости от вычеркиваемых строк, матрица оставалась обратимой. К счастью, в математике давно известны типы матриц, обладающие нужным нам свойством. Например, матрица Коши. В этом случае сам метод кодирования часто называют методом Коши-Рида-Соломона (Cauchy-Reed-Solomon). Иногда, для этих же целей используют матрицу Вандермонда, и соответственно, метод носит название Вандермонда-Рида-Соломона (Vandermonde-Reed-Solomon).
Переходим к следующей проблеме. Для представления чисел в ЭВМ используется фиксированное число байтов. Соответственно, в наших алгоритмах мы не можем свободно оперировать произвольными рациональными, и тем более, вещественными числами. Мы просто не сможем реализовать такой алгоритм на ЭВМ. В нашем случае порождающая матрица состоит из целых чисел, но при обращении этой матрицы могут возникнуть рациональные числа, представлять которые в памяти ЭВМ проблематично. Вот мы и дошли до того места, когда на сцену выходят знаменитые поля Галуа.
Поле – это множество, на котором заданы операции сложения, вычитания, умножения и деления. Пример — поле рациональных чисел (дробей). Поле Галуа — конечное поле (множество, содержащее конечное количество элементов). Обычно поля Галуа обозначаются как , где — количество элементов в поле. Разработаны методы построения полей необходимой размерности (если это возможно). Конечным результатом подобных построений обычно являются таблицы сложения и умножения, которые двум элементам поля ставят в соответствие третий элемент поля.
Может возникнуть вопрос – как мы всё это будем использовать? При реализации алгоритмов на ЭВМ удобно работать с байтами. Наш алгоритм может принимать на входе байт исходных данных и вычислять по ним байт избыточных. В одном байте может содержаться 256 различных значений, поэтому, мы можем создать поле и рассчитывать избыточные байт, пользуясь арифметикой полей Галуа. Сам подход к кодированию/декодированию данных (построение порождающей матрицы, обращение матрицы, умножение матрицы на столбец) остаётся таким же, как и прежде.
Хорошо, мы в итоге научились по исходным байтам конструировать дополнительные байт, которые можно использовать при сбоях. Как это всё работает в реальных системах хранения? В реальных СХД обычно работают с блоками данных фиксированного размера (в разных системах этот размер варьируется от десятков мегабайт до гигабайтов). Этот фиксированный блок разбивается на фрагментов и по ним конструируются дополнительные фрагментов.
Процесс конструирования фрагментов происходит следующим образом. Берут по одному байту из каждого из исходных фрагментов по смещению 0. По этим данным генерируется K дополнительных байтов, каждый из который идет в соответствующие дополнительные фрагменты по смещению 0. Этот процесс повторяется для смещения – 1, 2, 3,… После того, как процедура кодирования закончена, фрагменты сохраняются на разные диски. Это можно изобразить следующим образом:
При выходе из строя одного или нескольких дисков, соответствующие потерянные фрагменты реконструируются и сохраняются на других дисках.
Теоретическая часть постепенно подходит к концу, будем надеяться, что базовый принцип кодирования и декодирования данных с использованием кодов Рида-Соломона теперь более или менее понятен. Если будет интерес к данной теме, то в следующих частях можно будет более подробно остановится на арифметике полей Галуа, реализациях алгоритма кодирования/декодирования на конкретных аппаратных платформах, поговорить про техники оптимизации.
UPD. Вынесенный из комментариев список литературы по теме (спасибо
whitedruid):
— «Алгебраическая теория кодирования», Берлекэмп Э., 1971.
— «Теория кодов, исправляющих ошибки», Мак-Вильямс Ф., Слоэн Н.Дж., 1979.
— «Теория и практика кодов, контролирующих ошибки.», 1986.
— «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение», Морелос-Сарагоса Р., 2005.
— «Кодирование с исправлением ошибок в системах цифровой связи», Кларк Дж., Кейн Дж., 1987.
— «Упаковки шаров, решетки и группы.», Конвей Дж.Н., Слоэн Н.Дж.А., 1990.
whitedruid: Книгу «Упаковка шаров, решетки и группы» сам прочёл относительно недавно — очень понравилось!
— «Введение в алгебраические коды» — лекции преподавателя МФТИ Юрия Львовича Сагаловича, оформленные в виде книги.
— «Коды Рида-Соломона с точки зрения обывателя» — написано простым языком.
— «Коды, исправляющие ошибки» — кратко, понятно и с картинками 🙂
— «Заметки по теории кодирования», А. Ромащенко, А. Румянцев, А. Шень, 2011 год. — своего рода «шпаргалка» — кратко, ёмко, однако требует некоторого уровня подготовки.
— Также нельзя обойти стороной семинары по «Теории кодирования», которые регулярно организуются сотрудниками «Институт проблем передачи информации им. А.А. Харкевича Российской академии наук», г. Москва. Далее — по ссылкам — можно найти много интересного по темам, связанным с математической теорией кодирования, поднимаются актуальные вопросы в рамках дисциплины. Например, про последовательное декодирование полярных и расширенных кодов Рида-Соломона. В поисковых же системах можно найти уже статьи автора.
habr.com
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.
Код Рида — Соломона был изобретён в 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)
Код Рида — Соломона над , исправляющий 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, если .
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. [1], описание кодировщика).
При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.
Структура систематического кодового слова Рида — СоломонаПри систематическом кодировании к информационному блоку из k символов приписываются 2t проверочных символов, при вычислении каждого проверочного символа используются все k символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить k(n − k) операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка O(ln(n2)).
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t, что много меньше степени кодового слова n. Для получения соответствия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Эта маска накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.
В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды.
Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Так же ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.
При записи на цифровые аудиокомпакт-диски (Compact Disc Digital Audio — CD-DA) используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.
Этот алгоритм кодирования используется при передаче данных по сетям WiMAX, в оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.
Пусть t = 2,l0 = 1. Тогда
g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10
.
Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
Пусть t = 2,l0 = 4. Тогда
g(x) = (x − α4)(x − α5)(x − α6)(x − α0) = x4 + α6x3 + α6x2 + α3x + α
.
Пусть информационный многочлен имеет вид
m(x) = α4x2 + x + α3
.
Кодовое слово несистематического кода запишется в виде
c(x) = m(x)g(x) = (α4x2 + x + α3)(x4 + α6x3 + α6x2 + α3x + α) = α4x6 + αx5 + α6x4 + 0x3 + 0x2 + α5x + α4
что представляет собой последовательность семи восьмеричных символов.
dic.academic.ru
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.
Код Рида — Соломона был изобретён в 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)
Код Рида — Соломона над , исправляющий 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, если .
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. [1], описание кодировщика).
При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.
Структура систематического кодового слова Рида — Соломона
При систематическом кодировании к информационному блоку из k символов приписываются 2t проверочных символов, при вычислении каждого проверочного символа используются все k символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить k(n − k) операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка lnn2.
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t, что много меньше степени кодового слова n. Для получения соответсвия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Эта маска накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.
В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (
Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Так же ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.
При записи на цифровые аудиокомпакт-диски (Compact Disc Digital Audio — CD-DA) используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответсвенно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символа является фатальной ошибкой, не могут быть исправлены.
Этот алгоритм кодирования используется при передаче данных по сетям оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.
Пусть t = 2,l0 = 1. Тогда
g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10
.
Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
Пусть t = 2,l0 = 4. Тогда
g(x) = (x − α4)(x − α5)(x − α6)(x − α0) = x4 + α6x3 + α6x2 + α3x + α
.
Пусть информационный многочлен имеет вид
m(x) = α4x2 + x + α3
.
Кодовое слово несистематического кода запишется в виде
c(x) = m(x)g(x) = (α4x2 + x + α3)(x4 + α6x3 + α6x2 + α3x + α) = α4x6 + αx5 + α6x4 + 0x3 + 0x2 + α5x + α4
что представляет собой последовательность семи восьмеричных символов.
Wikimedia Foundation. 2010.
dic.academic.ru
В современных системах цифрового телевидения для обеспечения помехоустойчивой передачи цифровых телевизионных сигналов по радиоканалу используются наиболее совершенные коды Рида-Соломона(Reed-Solomon),требующие добавления двух проверочных символов в расчете на одну исправляемую ошибку. Коды Рида-Соломона обладают высокими корректирующими свойствами, для них разработаны относительно простые и конструктивные методы кодирования. Коды Рида-Соломона не являются двоичными. Это надо понимать в том смысле, что символами кодовых слов являются не двоичные знаки, а элементы множества чисел, состоящего более чем из двух знаков (хотя, конечно, при передаче каждый символ заменяется соответствующей двоичной комбинацией).
Коды Рида-Соломона, относящиеся к классу циклических кодов, образуют подгруппублоковых кодов. Они получаются из любой разрешенной комбинации путем циклического сдвига ее разрядов. Кодирование и декодирование, обнаруживающее и исправляющее ошибки, – это вычислительные процедуры, которые для циклических кодов удобно выполнять как действия с многочленами и реализацию в виде цифровых устройств на базе регистров сдвига с обратными связями.
Чтобы получить более детальное представление о кодах Рида-Соломона посмотрим, какое место они занимают в классификации корректирующих кодов (рис. 4.4).
Корректирующие коды разделяются на блочные и сверточные (непрерывные). Блочные кодыоснованы на перекодировании исходной кодовой комбинации (блока), содержащейkинформационных символов, в передаваемую кодовую комбинацию, содержащуюn>kсимволов. Дополнительныер = n – kсимволов зависят только отkсимволов исходной кодовой комбинации. Следовательно, кодирование и декодирование осуществляются всегда в пределах одной кодовой комбинации (блока). В противоположность этому всверточных кодахкодирование и декодирование осуществляются непрерывно над последовательностью двоичных символов.
Блочные коды бывают разделимые и неразделимые. В разделимых кодахможно в каждой кодовой комбинации указать, какие символы являются информационными, а какие проверочными. Внеразделимых кодахтакая возможность отсутствует.
Следующая ступень классификации – систематические коды. Они отличаются тем, что в них проверочные символы формируются из информационных символов по определенным правилам, выражаемым математическими соотношениями. Например, каждый проверочный символхpjполучается как линейная комбинация информационных символов
Рис. 4.4.Место кодов Рида-Соломона в классификации корректирующих кодов
,
где 
– коэффициенты, принимающие значения
0 или 1;.
Соотношение для формирования
контрольного бита проверки на четность
является частным случаем .
Перейдем к более подробному знакомству с циклическими кодами.
В первую очередь введем запись кодовой комбинации или, как часто называют ее в литературе, кодового вектора в виде полинома. Пусть имеется кодовая комбинация a0a1a2…an–1, гдеа0– младший разряд кода,an–1– старший разряд кода. Соответствующий ей полином имеет вид
,
где х– формальная переменная, вводимая только для получения записи кодовой комбинации в виде полинома.
Над полиномами, представляющими кодовые комбинации, определена математическая операция умножения. Особенность этой операции по сравнению с общепринятой заключается в том, что коэффициенты при хвсех степеней суммируются по модулю 2, а показатели степенихпри перемножении суммируются по модулюn, поэтомухn= 1.
Далее введем понятие производящего полинома. Производящим полиномом порядка (n – k) может быть полином со старшей степенью х, равной (n – k), на который без остатка делится двучлен (1 + хn). Разрешенные кодовые комбинации получаются перемножением полиномов порядка k – 1, выражающих исходные кодовые комбинации, на производящий полином.
Циклические коды имеют следующее основное свойство. Если кодовая комбинация a0a1a2…an–1является разрешенной, то получаемая из нее путем циклического сдвига кодовая комбинацияan–1a0a1…an–2также является разрешенной в данном коде. При записи в виде полиномов операция циклического сдвига кодового слова сводится к умножению соответствующего полинома нахс учетом приведенных ранее правил выполнения операции умножения.
Циклический код
с производящим полиномом 
строится следующим образом.
1. Берутся
полиномы 
,
,
,
…,
.
2. Кодовые комбинации, соответствующие этим полиномам, записывают в виде строк матрицы G, называемойпроизводящей матрицей.
3. Формируется набор разрешенных кодовых комбинаций кода. В него входит нулевая кодовая комбинация, k кодовых комбинаций, указанных в п. 1, а также суммы их всевозможных сочетаний. Суммирование осуществляется поразрядно, причем каждый разряд суммируется по модулю 2. Общее число полученных таким образом разрешенных кодовых комбинаций равно 2k, что соответствует числу информационных разрядов кода.
Для построения
декодера в первую очередь получают
производящий полином 
порядкаkдля построенияисправляющей матрицыН:
.
Строками исправляющей
матрицы Нбудут кодовые комбинации,
определяемые полиномами
,
,
…,,
где
– это записанный в обратном порядке
полином
.
Исправляющая матрица имеетnстолбцов иn – kстрок.
При декодировании принятая кодовая комбинация a0a1a2…an–1скалярно умножается на каждую строку исправляющей матрицы. Эта операция может быть записана в виде соотношения:
,
где hji– элементыj-той строки матрицыН. Полученныеn – kчиселcjобразуютисправляющий векторилисиндром. Если ошибок нет, то всеcj= 0. Если же при передаче данной кодовой комбинации возникла ошибка, то некоторые из чиселcjне равны 0. По тому, какие именно элементы исправляющего вектора отличны от нуля, можно сделать вывод о том, в каких разрядах принятой кодовой комбинации есть ошибка и, следовательно, исправить эти ошибки.
Рассмотрим пример, часто встречающийся в литературе. Построим циклический код с n= 7;k= 4. Для этого представим двучлен 1 +х7в виде произведения [4]:
.
В обычной алгебре это равенство, конечно, не выполняется, но если использовать для приведения подобных вместо обычного сложения операцию суммирования по модулю 2, а при сложении показателей степеней – операцию суммирования по модулю 7, то равенство окажется справедливым.
В качестве производящего многочлена возьмем 1 + х+х3. Умножаем его нах,х2их3и получаем многочленых+х2+х4;х2+х3+х5;х3+х4+х6. Затем записываем производящую матрицуG, причем в каждой строке матрицы младший разряд кодовой комбинации расположен первым слева.
.
Далее формируем набор из 15 допустимых кодовых комбинаций: 00000000, 1101000, 0110100, 0011010, 0001101, 1011100, 0101110, 0010111, 1000110, 0100011, 1111111, 1010001, 1000110, 0100011, 1001011. В этих записях младшие биты слева, а старшие – справа.
Перемножив первые два сомножителя в , получаем производящий многочлен для исправляющей матрицы: 1 + х+х+х4. Затем умножаем его нахих2и получаем еще две строки этой матрицы, которая в результате имеет такой вид (в отличие от матрицыGздесь младшие разряды соответствующих полиномов расположены справа):
.
Пусть принята кодовая комбинация 0001101, входящая в набор допустимых. Найдем скалярные произведения этой кодовой комбинации со всеми строками матрицы Н:
Пусть теперь принята кодовая комбинация 0001100, в которой последний (старший) бит содержит ошибку. Скалярные произведения принятой кодовой комбинации на строки исправляющей матрицы имеют вид:
Таким образом, получен синдром (1, 0, 0). Если ошибка оказывается в другом бите кодовой комбинации, то получается другой синдром.
Одним из важных достоинств циклических кодов является возможность построения кодирующих и декодирующих устройств в виде сдвиговых регистров с обратными связями через сумматоры по модулю 2.
Различные виды циклических кодов получаются с помощью различных производящих полиномов. Существует развитая математическая теория этого вопроса [15]. Среди большого количества циклических кодов к числу наиболее эффективных и широко используемых относятся коды Бозе-Чоудхури-Хоквингема (ВСН-коды – по первым буквам фамилий Bose,Chaudhuri,Hockwinhamили в русскоязычной записи БЧХ-коды), являющиесяобобщением кодов Хеммингана случай направления нескольких ошибок. Они образуют наилучший среди известных класснеслучайных кодовдля каналов, в которых ошибки в последовательных символах возникают независимо. Например, БЧХ-код (63, 44), используемый в системе спутникового цифрового радиовещания, позволяет исправить 2 или 3 ошибки, обнаружить 4 или 5 ошибок на каждый блок из 63 символов. Относительная скорость такого кода равнаR= 44/63 = 0,698.
Одним из видов ВСН-кодов являются коды Рида-Соломона. Эти коды относятся к недвоичным кодам, так как символами в них могут быть многоразрядные двоичные числа, например, целые байты. В Европейском стандарте цифрового телевидения DVB используется код Рида-Соломона, записываемый как (204, 188, 8), где 188 – количество информационных байт в пакете транспортного потока MPEG-2, 204 – количество байт в пакете после добавления проверочных символов, 8 – минимальное кодовое расстояние между допустимыми кодовыми комбинациями. Таким образом, в качестве кодовых комбинаций берутся целые пакеты транспортного потока, содержащие 1888 = 1504 информационных бита, а добавляемые проверочные символы содержат 168 = 128 бит. Относительная скорость такого кода равна 0,92. Этот код Рида-Соломона позволяет эффективно исправлять до 8 принятых с ошибками байт в каждом транспортном пакете.
Отметим также, что используемый в цифровом телевизионном вещании код Рида-Соломона часто называют укороченным. Смысл этого термина состоит в следующем. Из теории кодов Рида-Соломона следует, что если символом кода является байт, то полная длина кодового слова должна составлять 255 байт (239 информационных и 16 проверочных). Однако, пакет транспортного потокаMPEG-2 содержит 188 байт. Чтобы согласовать размер пакета с параметрами кода, перед кодированием в начало каждого транспортного пакета добавляют 51 нулевой информационный байт, а после кодирования эти дополнительные нулевые байты отбрасывают.
В приемнике для каждого принятого транспортного пакета, содержащего 204 байта, вычисляются синдромы и находятся два полинома: «локатор», корни которого показывают положение ошибок, и «корректор» (evaluator), дающий значение ошибок. Ошибки корректируются, если это возможно. Если же коррекция невозможна (например, ошибочных байт более 8) данные в пакете не изменяются, а сам пакет помечается путем установки флага (первый бит после синхробайта), как содержащий неустранимые ошибки. В обоих случаях 16 избыточных байт удаляются, и после декодирования длина транспортного пакета становится равной 188 байт.
studfiles.net
Коды Рида — Соломона (англ. Reed–Solomon codes) — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.
Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Массачуссетского технологического института Ирвином Ридом (англ.) и Густавом Соломоном (англ.). Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом (англ.) и Джэймсом Месси (алгоритм Берлекэмпа — Мэсси) и в 1977 году Давидом Мандельбаумом (англ.) (метод, использующий Алгоритм Евклида[1]). Первое применение код Рида — Соломона получил в 1982 году в серийном выпуске компакт-дисков.
Коды Рида — Соломона являются важным частным случаем БЧХ-кода, корни порождающего полинома которого лежат в том же поле, над которым строится код (). Пусть — элемент поля порядка . Если — примитивный элемент, то его порядок равен , то есть . Тогда нормированный полином минимальной степени над полем , корнями которого являются подряд идущих степеней элемента , является порождающим полиномом кода Рида — Соломона над полем :
где — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается . Степень многочлена равна .
Длина полученного кода , минимальное расстояние (минимальное расстояние d линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код). Код содержит проверочных символов, где обозначает степень полинома; число информационных символов . Таким образом и код Рида — Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона).
Кодовый полином может быть получен из информационного полинома , , путем перемножения и :
Код Рида — Соломона над , исправляющий ошибок, требует проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя дополнительных проверочных символов исправляется ошибок (и менее).
Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной и менее, должен содержать, по меньшей мере, проверочных символов.
Код, двойственный коду Рида — Соломона, есть также код Рида — Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом.
Матрица порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы отличен от нуля.
При выкалывании или укорочении кода Рида — Соломона снова получается код Рида — Соломона. Выкалывание — операция, состоящая в удалении одного проверочного символа. Длина кода уменьшается на единицу, размерность сохраняется. Расстояние кода должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен.Укорочение — фиксируем произвольный столбец кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство.
Код Рида — Соломона является одним из наиболее мощных кодов, исправляющих многократные пакеты ошибок. Применяется в каналах, где пакеты ошибок могут образовываться столь часто, что их уже нельзя исправлять с помощью кодов, исправляющих одиночные ошибки.
-код Рида — Соломона над полем с кодовым расстоянием можно рассматривать как -код над полем , который может исправлять любую комбинацию ошибок, сосредоточенную в или меньшем числе блоков из m символов. Наибольшее число блоков длины , которые может затронуть пакет длины , где , не превосходит , поэтому код, который может исправить блоков ошибок, всегда может исправить и любую комбинацию из пакетов общей длины , если .
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. [1], описание кодировщика).
При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.
При систематическом кодировании к информационному блоку из символов приписываются проверочных символов, при вычислении каждого проверочного символа используются все символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка .
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова длины на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Существует и другая процедура кодирования (более практичная и простая). Положим — примитивный элемент поля , и пусть — вектор информационных символов, а значит — информационный многочлен. Тогда вектор есть вектор кода Рида — Соломона, соответствующий информационному вектору . Этот способ кодирования показывает, что для кода РС вообще не нужно знать порождающего многочлена и порождающей матрицы кода, достаточно знать разложение поля по примитивному элементу и размерность кода (длина кода в этом случае определяется как ). Все дело в том, что за разностью полностью скрывается порождающий многочлен и кодовое расстояние.
Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна , что много меньше степени кодового слова . Для получения соответствия между ошибкой и её положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Однако для кодов РС существует более простой способ отыскания характера ошибок. Как показано в[2] для кодов РС с произвольным множеством последовательных нулей
где формальная производная по многочлена локаторов ошибок ,а
Далее после того как маска найдена, она накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.
В данное время стали применяться принципиально новые методы декодирования, например, алгоритм, предложенный в 1997 году Мадху Суданом[3].
Удлинение кодов РС — это процедура, при которой увеличивается длина и расстояние кода (при этом код ещё находится на границе Синглтона и алфавит кода не изменяется), а количество информационных символов кода не изменяется[4]. Такая процедура увеличивает корректирующую способность кода. Рассмотрим удлинение кода РС на один символ. Пусть — вектор кода РС, порождающий многочлен которого есть . Пусть теперь . Покажем, что добавление к вектору символа увеличит его вес до ,если . Многочлен, соответствующий вектору кода, можно расписать как , но тогда с учётом выражения для получим . , так как 1 не принадлежит списку корней порождающего многочлена. Но и , так как в этом случае ,что увеличило бы расстояние кода вопреки условию, это значит что и вес кода увеличился, за счёт добавления нового символа . Новые параметры кода , удлиненный вектор . Проверочная матрица не удлиненного кода имеет вид
Тогда проверочная матрица, удлиненного на один символ РС кода будет
Сразу после появления (60-е годы 20-го века) коды Рида — Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях -е символы РС (их может быть несколько) кодируются внутренними сверточными кодами. На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ) . Такой декодер будет исправлять одиночные ошибки в q-ичных символах, когда же возникнут пакетные ошибки и некоторые пакеты q-ичных символов будут декодированы неправильно, тогда внешний декодер Рида — Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации ([5]).
В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды.
Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Также ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.
При записи на аудиокомпакт-диски используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях, C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа, соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.
Этот алгоритм кодирования используется при передаче данных по сетям WiMAX, в оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.
Пусть . Тогда
.Степень равна 4, и . Каждому элементу поля можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
Пусть . Тогда
.Пусть информационный многочлен имеет вид
.Кодовое слово несистематического кода запишется в виде
что представляет собой последовательность семи восьмеричных символов.
Построим поле Галуа по модулю многочлена .Пусть его корень, тогда , таблица поля имеет вид:
Пусть информационный многочлен , далее производя соответствующие вычисления над построенным полем получим
В итоге построен вектор кода РС с параметрами .На этом кодирование законченно. Заметим, что при этом способе нам не потребовался порождающий многочлен кода[4].
Пусть поле генерируется примитивным элементом, неприводимый многочлен которого . Тогда . Пусть . Тогда порождающий многочлен кода РС равен . Пусть теперь принят многочлен . Тогда . Тогда ключевая система уравнений получается в виде
Теперь рассмотрим Евклидов алгоритм решения этой системы уравнений.
Алгоритм останавливается, так как отсюда следует, что
Далее полный перебор по алгоритму Чени выдает нам позиции ошибок, это .Потом по формуле получаем что
Таким образом декодированный вектор . Декодирование завершено, исправлены две ошибки[6].
wp.wiki-wiki.ru
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.
Код Рида — Соломона был изобретён в 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)
Код Рида — Соломона над , исправляющий 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, если .
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. [1], описание кодировщика).
При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.
Структура систематического кодового слова Рида — Соломона
При систематическом кодировании к информационному блоку из k символов приписываются 2t проверочных символов, при вычислении каждого проверочного символа используются все k символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить k(n − k) операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка lnn2.
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t, что много меньше степени кодового слова n. Для получения соответсвия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Эта маска накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.
В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (
Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Так же ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.
При записи на цифровые аудиокомпакт-диски (Compact Disc Digital Audio — CD-DA) используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответсвенно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символа является фатальной ошибкой, не могут быть исправлены.
Этот алгоритм кодирования используется при передаче данных по сетям оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.
Пусть t = 2,l0 = 1. Тогда
g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10
.
Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
Пусть t = 2,l0 = 4. Тогда
g(x) = (x − α4)(x − α5)(x − α6)(x − α0) = x4 + α6x3 + α6x2 + α3x + α
.
Пусть информационный многочлен имеет вид
m(x) = α4x2 + x + α3
.
Кодовое слово несистематического кода запишется в виде
c(x) = m(x)g(x) = (α4x2 + x + α3)(x4 + α6x3 + α6x2 + α3x + α) = α4x6 + αx5 + α6x4 + 0x3 + 0x2 + α5x + α4
что представляет собой последовательность семи восьмеричных символов.
Wikimedia Foundation. 2010.
dic.academic.ru