Министерство образования и науки Российской Федерации Калужский филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» (КФ МГТУ им. Н.Э. Баумана)

ФАКУЛЬТЕТ	"Электроники, информатики и управления"
КАФЕДРА	"Компьютерные системы и сети"

Реферат

ДИСЦИПЛИНА:		"Системы передачи данных"
ТЕМА:	"Коды Рида-Соломона"
Выполнил: студент гр. ЭВМ-102			Рогацевич К.В _______________
Проверил:			Квашенников В. В. ______________________

Калуга, 2015 г.

Содержание

Введение………………………………………………………………………….4

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

Свойства ………………………………………………………………………….6

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

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

Кодирование……………………………………………………………………...8

Декодирование …………………………………………………………………..9

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

Построение полинома ошибки……………………………………………….....10

Нахождение корней……………………………………………………………...10

Определение характера ошибки и ее исправление……………………………10

Алгоритм Судана………………………………………………………………...11

Алгоритм Гао…………………………………………………………………….12

Удлинение кодов РС…………………………………………………………….14

Применение……………………………………………………………………....15

Запись и хранение информации ………………………………………………..15

Запись на CD-ROM……………………………………………………………....16

Беспроводная и мобильная связь……………………………………………….17

Примеры кодирования ………………………………………………………….17

16-ричный (15,11) код Рида — Соломона……………………………………...17

8-ричный (7,3) код Рида — Соломона………………………………………….17

Альтернативный метод кодирования 9-ричного (8,4) кода…………………...18

Примеры декодирования………………………………………………………..18

Заключение……………………………………………………………………….20

Список использованных источников…………………………………………...21

Введение

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

Код Рида — Соломона является частным случаем БЧХ-кода.

В настоящее время широко используется в системах восстановления данных с компакт-дисков, при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании.

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

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

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

Код, двойственный коду Рида — Соломона, есть также код Рида-Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом. Матрица порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы Pk * (n − k) отличен от нуля.

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

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

Код Рида — Соломона является одним из наиболее мощных кодов, исправляющих многократные пакеты ошибок. Применяется в каналах, где пакеты ошибок могут образовываться столь часто, что их уже нельзя исправлять с помощью кодов, исправляющих одиночные ошибки. (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(n)2).

Кодирование

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

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

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

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

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

Существует и другая процедура кодирования (более практичная и простая). Пусть - вектор информационных символов , а значит - информационный многочлен. Тогда вектор есть вектор кода Рида - Соломона, соответствующий информационному вектору a. Этот способ кодирования показывает, что для кода РС вообще не нужно знать порождающего многочлена и порождающей матрицы коды, достаточно знать разложение поля GF(q) по примитивному элементу α и размерность кода k (длина кода в этом случае определяется как n = q − 1). Все дело в том , что за разностью n − k полностью скрывается порождающий многочлен g(x) и кодовое расстояние.

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

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

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

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

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

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

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

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

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

Построение полинома ошибки

Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t, что много меньше степени кодового слова n. Для получения соответствия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.

Нахождение корней

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

Определение характера ошибки и ее исправление

По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Однако для кодов РС существует более простой способ отыскания характера ошибок. Как показано в [2] для кодов РС с произвольным множеством 2td последовательных нулей

где σ'(x) формальная производная по x многочлена локаторов ошибок σ(x) ,а

Далее после того как маска найдена , она накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.

Алгоритм Судана

В данное время стали применяться принципиально новые методы декодирования, например алгоритм предложенный в 1997 году Мадху Суданом [3]. Судан построил первый полиномиальный алгоритм, решающий задачу списочного декодирования PC-кодов, сформулированную для произвольных кодов Элайесом и Возенкрафтом еще в середине 1950-х годов. Алгоритм Судана оказался эффективным только для PC-кодов, имеющих скорость до 1/3, поэтому несколько позже Гурусвами и Судан модифицировали алгоритм Судана, сняв ограничение на скорость РС-кодов. Благодаря алгоритмам Судана и Гурусвами-Судана PC-коды нашли применение при решении многих прикладных задач, изначально далеких от теории кодирования, таких как предотвращение несанкционированного копирования компакт-дисков, самообучение систем и распознавание образов, построение односторонних функций для криптографических целей, криптоанализ некоторых блочных шифров. Отметим, что с каждым годом круг прикладных задач, решаемых с помощью списочного декодирования, интенсивно расширяется, вследствие чего возрастает и актуальность задачи улучшения характеристик существующих и построения новых алгоритмов списочного декодирования как PC-кодов, так и других помехоустойчивых кодов.

Пусть F_q – поле Галуа, С: F^k_q → Fⁿ_q – кодирующее отображение, (α₀, … , α_n-1) – опорное множество кода Рида-Соломона, у=(у₀, у₁…,у_n-1) –пришедшее по каналу слово.

Строится полином от двух переменных Q(x, y) степени D по переменной х и степени L, по переменной у, удовлетворяющей следующим условиям:

- Q(α_i, y_i) = 0, i = 0 … n-1

- Q(x, y) ≠ 0

Находятся все делители полинома Q(x, y) вида

у - р(х), deg p(x) < k

Параметры L и D определяются следующим образом: L = , D =

Алгоритм Гао

Рассмотрим классический код РС с параметрами

n = q - 1 и b = 1

1. Интерполяция

Берётся такой интерполяционный многочлен T(x), что:

T(α_i) = r_i; i 2 [0; n - 1]

где deg T(x) < n.

2. Вычисление наибольшего общего делителя

Решается система выражений c помощью расширенного алгоритма:

Получается единственная пара многочленов и .

3. Деление

Информационный многочлен:

M(x) =

Первый шаг алгоритма Гао может быть выполнен любым быстрым алгоритмом вычисления дискретного преобразования Фурье над конечным полем сложностью O(n(log n)²) операций. Второй шаг лучше всего реализовать с помощью алгоритма Мёнка с той же сложностью O(n(log n)²) операций. Деление же выполняется за O(n log n log log n) операций.

Если же применять алгоритм Гао к другим кодам (БЧХ, Гоппы или альтернативные коды), то необходимо добавить дополнительный 4-й шаг, восстанавливающий кодовое слово по информационному многочлену.

На текущий момент алгоритм Гао и его модификации являются самыми простыми для кодов с ограниченной длиной при любых реализациях

Удлинение кодов РС

Удлинение кодов РС - это процедура, при которой увеличивается длина и расстояние кода (при этом код находится на границе Синглота, и алфавит кода не меняется), а количество информационных символов кода не меняется[4]. Такая процедура увеличивает корректирующую способность кода. Рассмотрим удлинение кода РС на один символ. Пусть - это вектор кода РС, порождающий многочлен которого есть Пусть теперь . Покажем, что добавление к вектору символа увеличит его вес до d + 1,если . Многочлен, соответствующий вектору коду можно расписать как υ(x) = g(x) * z(x), но тогда с учётом выражения для cq − 1 получим υ(1) = g(1)z(1) = − cq − 1. , так как 1 не принадлежит списку корней порождающего многочлена. Но и , так как в этом случае (x − 1)g(x) | υ(x), что увеличило бы расстояние кода вопреки условию, это значит что и вес кода увеличился, за счёт добавления нового символа cq − 1. Новые параметры кода n1 = n + 1,k1 = k,d1 = d + 1, удлиненный вектор . Проверочная матрица не удлиненного кода имеет вид:

Тогда проверочная матрица, удлиненного на один символ РС кода будет:

Применение

Сразу после появления (60-ые годы 20-го века) коды Рида - Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях q-ые символы РС(их может быть несколько) кодируются внутренними сверточными кодами. На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ). Такой декодер будет исправлять одиночные ошибки в q-ичных символах, когда же возникнут пакетные ошибки и некоторые пакеты q-ичных символов будут декодированы неправильно, тогда внешний декодер Рида - Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации ([5]).

В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.

Запись и хранение информации

Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды.

Запись на CD-ROM

Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Так же ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность примерно 25 % от исходной информации.

При записи на аудиокомпакт-диски используется стандарт Red Book. Коррекция ошибок происходит на двух уровнях C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования осуществляется также перемешивание (перемежение) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.

Беспроводная и мобильная связь

Этот алгоритм кодирования используется при передаче данных по сетям WiMAX, в оптических линиях связи, в спутниковой и радиорелейной связи. Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.

Примеры кодирования

16-ричный (15,11) код Рида — Соломона

Пусть t = 2,l₀ = 1. Тогда:

g(x) = (x − α)(x − α²)(x − α³)(x − α⁴) = x⁴ + α¹³x³ + α⁶x² + α³x + α¹⁰

Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.

8-ричный (7,3) код Рида — Соломона

Пусть t = 2, l₀ = 4. Тогда:

g(x) = (x − α⁴)(x − α⁵)(x − α⁶)(x − α0) = x⁴ + α⁶x³ + α⁶x² + α³x + α

Пусть информационный многочлен имеет вид:

m(x) = α⁴x² + x + α³

Кодовое слово несистематического кода запишется в виде:

c(x) = m(x)g(x) = (α⁴x² + x + α³)(x⁴ + α⁶x³ + α⁶x² + α³x + α) = α⁴x⁶ + αx⁵ + α⁶x⁴ + 0x³ + 0x² + α⁵x + α⁴

что представляет собой последовательность семи восьмеричных символов.

Альтернативный метод кодирования 9-ричного (8,4) кода

Построим поле Галуа GF(32) по модулю многочлена x² + x + 2. Пусть α его корень, тогда α² + α + 2 = 0, таблица поля имеет вид:

Пусть информационный многочлен , далее производя соответствующие вычисления над построенным полем получим

В итоге построен вектор кода РС с параметрами . На этом кодирование законченно. Заметим, что при этом способе нам не потребовался проверочный многочлен кода[4].

Примеры декодирования

Пусть поле GF(23) генерируется примитивным элементом, неприводимый многочлен которого p(x) = x³ + x + 1. Тогда p(α) = α₃ + α + 1 = 0. Пусть b = 0, td = 2. Тогда порождающий многочлен кода РС равен g(x) = (x + 1)(x + α)(x + α²)(x + α³) = x⁴ + α²x³ + α⁵x² + α⁵x² + α⁶. Пусть теперь принят многочлен r(x) = αx² + α⁵x⁴. Тогда S1 = r(1) = α + α⁵ = α⁶, S2 = r(α) = α⁵,S3 = α, S4 = α. Тогда ключевая система уравнений получается в виде

Теперь рассмотрим Евклидов алгоритм решения этой системы уравнений.

Начальные условия:

Алгоритм останавливается, так как отсюда следует, что:

Далее полный перебор по алгоритму Чени выдает нам позиции ошибок, это . Потом по формуле ( * ) получаем что:

Таким образом декодированный вектор . Декодирование завершено, исправлены две ошибки[6].

Заключение

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

Есть множество разновидностей алгоритма в зависимости от областей применения, а также в зависимости от возраста каждой конкретной разновидности и от компании-разработчика. Чем алгоритм моложе, тем он сложнее.

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