Код Рида — Соломона
Код Рида — Соломона | |
---|---|
Назван в честь | Ирвинг Рид[вд] и Густав Соломон[вд] |
Тип |
|
Длина блока | |
Длина сообщения | |
Расстояние | |
Размер алфавита | для простого , часто |
Обозначение | |
Медиафайлы на Викискладе |
Коды Рида — Соломона (англ. Reed–Solomon codes) — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время широко используется в системах восстановления данных с
История
Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Массачусетского технологического института Ирвингом Ридом[англ.] и Густавом Соломоном[англ.]. Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом и Джэймсом Месси (алгоритм Берлекэмпа — Мэсси) и в 1977 году Давидом Мандельбаумом[англ.] (метод, использующий Алгоритм Евклида[1]). Первое применение код Рида — Соломона получил в 1982 году в серийном выпуске компакт-дисков.
Формальное описание
Коды Рида — Соломона являются важным частным случаем БЧХ-кода, корни порождающего полинома которого лежат в том же поле, над которым строится код (). Пусть — элемент поля , имеющий порядок . Если — примитивный элемент, то его порядок равен , то есть . Тогда нормированный полином минимальной степени над полем , корнями которого являются подряд идущих степеней элемента , является порождающим полиномом кода Рида — Соломона над полем :
где — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается . Степень многочлена равна .
Длина полученного кода , минимальное расстояние (является минимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код). Код содержит проверочных символов, где обозначает степень полинома; число информационных символов . Таким образом и код Рида — Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона).
Кодовый полином может быть получен из информационного полинома , , путём перемножения и :
Свойства
Код Рида — Соломона над , исправляющий ошибок, требует проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя дополнительных проверочных символов, исправляется ошибок (и менее).
Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной и менее, должен содержать, по меньшей мере, проверочных символов.
Код, двойственный коду Рида — Соломона, есть также код Рида — Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом.
Матрица порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы отличен от нуля.
При выкалывании или укорочении кода Рида — Соломона снова получается код Рида — Соломона. Выкалывание — операция, состоящая в удалении одного проверочного символа. Длина кода уменьшается на единицу, размерность сохраняется. Расстояние кода должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен. Укорочение — фиксируем произвольный столбец кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство.
Исправление многократных ошибок
Код Рида — Соломона является одним из наиболее мощных кодов, исправляющих многократные пакеты ошибок. Применяется в каналах, где пакеты ошибок могут образовываться столь часто, что их уже нельзя исправлять с помощью кодов, исправляющих одиночные ошибки.
Код Рида — Соломона над полем с кодовым расстоянием можно рассматривать как -код над полем , который может исправлять любую комбинацию ошибок, сосредоточенную в или меньшем числе блоков из m символов. Наибольшее число блоков длины , которые может затронуть пакет длины , где , не превосходит , поэтому код, который может исправить блоков ошибок, всегда может исправить и любую комбинацию из пакетов общей длины , если .
Практическая реализация
Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. [1], описание кодировщика).
При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа. Полученное закодированное слово полностью отличается от исходного и для извлечения информационного слова нужно выполнить операцию декодирования и уже потом можно проверить данные на содержание ошибок. Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.
При систематическом кодировании к информационному блоку из символов приписываются проверочных символов, при вычислении каждого проверочного символа используются все символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка .
Кодирование
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова длины на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
- К исходному слову приписываются нулей, получается полином .
- Этот полином делится на порождающий полином , находится остаток , , где — частное.
- Этот остаток и будет корректирующим кодом Рида — Соломона, он приписывается к исходному блоку символов. Полученное кодовое слово .
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Существует и другая процедура кодирования (более практичная и простая). Положим — примитивный элемент поля , и пусть — вектор информационных символов, а значит — информационный многочлен. Тогда вектор есть вектор кода Рида — Соломона, соответствующий информационному вектору . Этот способ кодирования показывает, что для кода РС вообще не нужно знать порождающего многочлена и порождающей матрицы кода, достаточно знать разложение поля по примитивному элементу и размерность кода (длина кода в этом случае определяется как ). Все дело в том, что за разностью полностью скрывается порождающий многочлен и кодовое расстояние.
Декодирование
Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:
- Вычисляет синдром ошибки
- Строит полином ошибки
- Находит корни данного полинома
- Определяет характер ошибки
- Исправляет ошибки
Вычисление синдрома ошибки
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Построение полинома ошибки
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна , что много меньше степени кодового слова . Для получения соответствия между ошибкой и её положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
Нахождение корней
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.
Определение характера ошибки и её исправление
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Однако для кодов РС существует более простой способ отыскания характера ошибок. Как показано в[2] для кодов РС с произвольным множеством последовательных нулей :
где формальная производная по многочлена локаторов ошибок , а
Далее после того как маска найдена, она накладывается на кодовое слово с помощью операции
Алгоритм Судана
В данное время стали применяться принципиально новые методы декодирования, например, алгоритм, предложенный в 1997 году Мадху Суданом[3].
Удлинение кодов РС
Удлинение кодов РС — это процедура, при которой увеличивается длина и расстояние кода (при этом код ещё находится на границе Синглтона и алфавит кода не изменяется), а количество информационных символов кода не изменяется[4]. Такая процедура увеличивает корректирующую способность кода. Рассмотрим удлинение кода РС на один символ. Пусть — вектор кода РС, порождающий многочлен которого есть . Пусть теперь . Покажем, что добавление к вектору символа увеличит его вес до , если . Многочлен, соответствующий вектору кода, можно расписать как , но тогда с учётом выражения для получим . , так как 1 не принадлежит списку корней порождающего многочлена. Но и , так как в этом случае , что увеличило бы расстояние кода вопреки условию, это значит что и вес кода увеличился, за счёт добавления нового символа . Новые параметры кода , удлиненный вектор . Проверочная матрица не удлиненного кода имеет вид
Тогда проверочная матрица, удлиненного на один символ РС кода будет
Применение
Сразу после появления (60-е годы XX века) коды Рида — Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях -е символы РС (их может быть несколько) кодируются внутренними сверточными кодами. На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ) . Такой декодер будет исправлять одиночные ошибки в q-ричных символах, когда же возникнут пакетные ошибки и некоторые пакеты q-ричных символов будут декодированы неправильно, тогда внешний декодер Рида — Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации ([5]).
В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря своей способности находить и исправлять многократные пакеты ошибок.
Запись и хранение информации
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти (
Запись на CD-ROM
Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Также ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD-дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность — примерно 25 % от исходной информации.
При записи на
Беспроводная и мобильная связь
Этот алгоритм кодирования используется при передаче данных по сетям
Примеры кодирования
16-ричный (15,11) код Рида — Соломона
Пусть . Тогда
Степень равна 4, и . Каждому элементу поля можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
8-ричный (7,3) код Рида — Соломона
Пусть . Тогда
Пусть информационный многочлен имеет вид:
Кодовое слово несистематического кода запишется в виде:
что представляет собой последовательность семи восьмеричных символов.
Альтернативный метод кодирования 9-ричного (8,4) кода Рида — Соломона
Построим поле Галуа по модулю многочлена . Пусть его корень, тогда , таблица поля имеет вид:
Пусть информационный многочлен , далее производя соответствующие вычисления над построенным полем получим:
В итоге построен вектор кода РС с параметрами . На этом кодирование закончено. Заметим, что при этом способе нам не потребовался порождающий многочлен кода[4].
Примеры декодирования
Пусть поле генерируется примитивным элементом, неприводимый многочлен которого . Тогда . Пусть . Тогда порождающий многочлен кода РС равен . Пусть теперь принят многочлен . Тогда . Тогда ключевая система уравнений получается в виде:
Теперь рассмотрим Евклидов алгоритм решения этой системы уравнений.
- Начальные условия:
Алгоритм останавливается, так как , отсюда следует, что
Далее полный перебор по алгоритму Чени выдает нам позиции ошибок, это . Потом по формуле получаем что
Таким образом декодированный вектор . Декодирование завершено, исправлены две ошибки[6].
Применение
- Код Рида — Соломона используется в некоторых прикладных программах в области хранения данных (например, в RAID 6).
См. также
- Конечное поле
- Обнаружение и исправление ошибок
- Циклический код
- Код Боуза — Чоудхури — Хоквингема
- Турбо-код
- Код Хэмминга
Примечания
- ↑ Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — С. 92—93. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
- ↑ Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
- ↑ Алгоритм Судана . Дата обращения: 24 декабря 2018. Архивировано 24 декабря 2018 года.
- ↑ 1 2 Сагалович, 2007, с. 212—213.
- ↑ М. Вернер. Основы кодирования. — Техносфера, 2004. — С. 268—269. — ISBN 5-94836-019-9.
- ↑ Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — С. 116—119. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
Литература
- Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.
- Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
- Берлекэмп Э. Алгебраическая теория кодирования = Algebraic Coding Theory. — М.: Мир, 1971. — С. 478.
- Егоров С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ. — Курск: КурскГТУ, 2008. — С. 252.
- Сагалович Ю. Л. Введение в алгебраические коды — М.: МФТИ, 2007. — 262 с. — ISBN 978-5-7417-0191-1
- Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
- М. Вернер. Основы кодирования. — Техносфера, 2004. — 288 с. — ISBN 5-94836-019-9.
- К. Касперски. Могущество кодов Рида — Соломона или информация, воскресшая из пепла // Системный администратор. — 2003. — № 8 (9).
Ссылки
- Помехоустойчивое кодирование в пакетных сетях (статья В. Варгаузина)
- Error Correcting Code (ECC)
- CD-R диски, технология изнутри
- Формат CD
- Коды Рида-Соломона
- wiki.linuxformat.ru/wiki/LXF134:par2 — использование par2, утилиты восстановления файлов методом Кода Рида-Соломона (рус.)