Пусть q=2 требуемая длина кода и минимальное расстояние Возьмем α - примитивный элемент поля GF(16) и - четыре подряд идущих степеней элемента α . Они принадлежат двум циклотомическим классам над полем GF(2), которыми соответствуют неприводимые полиномы Тогда полином имеет в качестве корней элементы и является порождающим полиномом БЧХ-кода с параметрами (15,7,5) .
Код Рида-Соломона
Коды Рида - Соломона являются важным частным случаем БЧХ-кода, корни порождающего полинома которого лежат в том же поле, над каким и строится код (m=1) Пусть α - элемент поля GF(q) порядка n. Если α - примитивный элемент, то его порядок равен q-1 то есть Тогда нормированный полином минимальной степени над полем корнями которого являются d-1 подряд идущих степеней элемента α , является порождающим полиномом кода Рида - Соломона над полем GF(q).
Где - некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается . Степень многочлена равна d-1 .
Длина полученного кода n , минимальное расстояние d (минимальное расстояние d линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код). Код содержит r= d – 1= проверочных символов, где обозначает степень полинома; число информационных символов k=n–r=n –d+ 1.
Таким образом d= n-k-1 и код Рида - Соломона является разделимым кодом с максимальным расстоянием .
Кодовый полином c(x) может быть получен из информационного полинома m(x),
Свойства
Код Рида - Соломона над GF(q) , исправляющий t ошибок, требует 2t проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной t и меньше. Согласно теореме о границе Рейгера, коды Рида - Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок.
Теорема (граница Рейгера ) . Каждый линейный блоковый код, исправляющий все пакеты длиной t и менее, должен содержать, по меньшей мере, 2t проверочных символов.
Исправление многократных ошибок
Код Рида - Соломона является одним из наиболее мощных кодов, исправляющих многократные пакеты ошибок. Применяется в каналах, где пакеты ошибок могут образовываться столь часто, что их уже нельзя исправлять с помощью кодов, исправляющих одиночные ошибки.
код Рида - Соломона над полем кодовым расстоянием можно рассматривать как код над полем GF(q) который может исправлять любую комбинацию ошибок, сосредоточенную в t или меньшем числе блоков из m символов. Наибольшее число блоков длины m , которые может затронуть пакет длины, где не превосходит поэтому код, который может исправить t блоков ошибок, всегда может исправить и любую комбинацию из p пакетов общей длины l , если
Пример построения:
16-ричный (15,11) код Рида - Соломона
Пусть t = 2,l 0 = 1. Тогда
g (x ) = (x − α)(x − α2)(x − α3)(x − α4) = x 4 + α13x 3 + α6x 2 + α3x + α10.
Степень g (x ) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
Кодирование
При операции кодирования информационный полином умножается на порождающий многочлен. Умножение исходного слова S длины k на неприводимый полином при систематическом кодировании можно выполнить следующим образом:
· К исходному слову приписываются 2t нулей, получается полином
· Этот полином делится на порождающий полином G , находится остаток R ,
· Этот остаток и будет корректирующим кодом Рида - Соломона, он приписывается к исходному блоку символов. Полученное кодовое слово
Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.
Декодирование
· Вычисляет синдром ошибки
· Строит полином ошибки
· Находит корни данного полинома
· Определяет характер ошибки
· Исправляет ошибки
Вычисление синдрома ошибки
Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.
Построение полинома ошибки
Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна 2t , что много меньше степени кодового слова n . Для получения соответствия между ошибкой и ее положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа - Месси, либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа - Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.
Нахождение корней
На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль - корни найдены.
Определение характера ошибки и ее исправление
По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Эта маска накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.
Выбор образующего многочлена в циклическом коде
Порождающим полиномом циклического (n, k ) кода C называется такой ненулевой полином:
из C , степень которого наименьшая и коэффициент при старшей степени 1
Теорема 1
Если C – циклический (n, k) код и его порождающий полином, тогда степень равна и каждое кодовое слово может быть единственным образом представлено в виде
где степень m(x) меньше или равнаk-1
Теорема 2
Порождающий полином циклического (n,k ) кода является делителем двучлена
Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель Степень выбранного полинома будет определять количество проверочных символов r, число информационных символов
Кодер (декодер) Витерби
Сущность метода.
Наилучшей схемой декодирования корректирующих кодов является декодирование методом максимального правдоподобия, когда декодер определяет набор условных вероятностей соответствующих всем возможным кодовым векторам и решение принимает в пользу кодового слова, соответствующего максимальному
Для двоичного симметричного канала без памяти (канала, в котором вероятности передачи 0 и 1, а также вероятности ошибок вида 0 -> 1 и 1 -> 0 одинаковы, ошибки в j -м и i -м символах кода независимы) декодер максимального правдоподобия сводится к декодеру минимального хеммингова расстояния. Последний вычисляет расстояние Хемминга между принятой последовательностью r и всеми возможными кодовыми векторами и выносит решение в пользу того вектора, который оказывается ближе к принятому. Естественно, что в общем случае такой декодер оказывается очень сложным и при больших размерах кодов n и k практически нереализуемым. Характерная структура сверточных кодов (повторяемость структуры за пределами окна длиной n ) позволяет создать вполне приемлемый по сложности декодер максимального правдоподобия.
Принцип работы декодера
На вход декодера поступает сегмент последовательности r длиной b , превышающей кодовую длину блока n . Назовем b окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной b ) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова принимается в качестве оценки информационного кадра декодированного слова. После этого в декодер вводится n 0 новых символов, а введенные ранее самые старые n 0символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путем и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путем.
Добрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона - теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области - но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.
Попробуем разобраться с тем, как это работает, начав с более интуитивных вещей. Для этого вернемся к нашей последней задаче. Напомним, что есть три произвольных целых числа, любые два из них могут быть потеряны, необходимо научиться восстанавливать потерянные числа по оставшимся. Для этого применим «алгебраический» подход.
Но прежде необходимо напомнить еще об одном важном моменте. Технологии восстановления данных неспроста называются методами избыточного кодирования. По исходным данным вычисляются некоторые «избыточные», которые потом позволяют восстановить потерянные. Не вдаваясь в подробности заметим, что эмпирическое правило такое - чем больше данных может быть потеряно, тем больше «избыточных» необходимо иметь. В нашем случае для восстановления двух чисел, нам придётся по некоторому алгоритму сконструировать два «избыточных». В общем случае, если нужно поддерживать потерю чисел, необходимо соответственно иметь избыточных.
Упомянутый выше «алгебраический» подход состоит в следующем. Составляется матрица специального вида размера . Первые три строки этой матрицы образуют единичную матрицу, а последние две - это некоторые числа, о выборе которых мы поговорим позднее. В англоязычной литературе эту матрицу обычно называют generator matrix , в русскоязычной встречается несколько названий, в этой статье будет использоваться - порождающая матрица. Умножим сконструированную матрицу на вектор, составленный из исходных чисел , и .
В результате умножения матрицы на вектор с данными получаем два «избыточных» числа, обозначенных на рисунке как и . Давайте посмотрим, как с помощью этих «избыточных» данных можно восстановить, к примеру, потерянные и .
Вычеркнем из порождающей матрицы строки, соответствующие «пропавшим» данным. В нашем случае соответствует первой строке, а – второй. Полученную матрицу умножим на вектор с данными, и в результате получим следующее уравнение:
Проблема лишь в том, что и мы потеряли, и они нам теперь неизвестны. Как мы можем их найти? Есть очень элегантное решение этой проблемы.
Вычеркнем соответствующие строки из порождающей матрицы и найдём обратную к ней. На рисунке эта обратная матрица обозначена как . Теперь домножим левую и правую части исходного уравнения на эту обратную матрицу:
Сокращая матрицы в левой части уравнения (произведение обратной и прямой матриц есть единичная матрица), и учитывая тот факт, что в правой части уравнения нет неизвестных параметров, получаем выражения для искомых и .
Собственно говоря, то, что мы сейчас проделали - основа всех типов кодов Рида-Соломона, применяемых в системах хранения данных. Процесс кодирования заключается в нахождении «избыточных» данных , , а процесс декодирования - в нахождении обратной матрицы и умножения её на вектор «сохранившихся» данных.
Нетрудно заметить, что рассмотренная схема может быть обобщена на произвольное количество «исходных» и «избыточных» данных. Другими словами, по исходным числам можно построить избыточных, причем всегда возможно восстановить потерю любых из чисел. В этом случае порождающая матрица будет иметь размер , а верхняя часть матрицы размером будет единичной.
Вернемся к вопросу о построении порождающей матрицы. Можем ли мы выбрать числа произвольным образом? Ответ – нет. Выбирать их нужно таким образом, чтобы вне зависимости от вычеркиваемых строк, матрица оставалась обратимой. К счастью, в математике давно известны типы матриц, обладающие нужным нам свойством. Например, матрица Коши . В этом случае сам метод кодирования часто называют методом Коши-Рида-Соломона (Cauchy-Reed-Solomon). Иногда, для этих же целей используют матрицу Вандермонда , и соответственно, метод носит название Вандермонда-Рида-Соломона (Vandermonde-Reed-Solomon).
Переходим к следующей проблеме. Для представления чисел в ЭВМ используется фиксированное число байтов. Соответственно, в наших алгоритмах мы не можем свободно оперировать произвольными рациональными, и тем более, вещественными числами. Мы просто не сможем реализовать такой алгоритм на ЭВМ. В нашем случае порождающая матрица состоит из целых чисел, но при обращении этой матрицы могут возникнуть рациональные числа, представлять которые в памяти ЭВМ проблематично. Вот мы и дошли до того места, когда на сцену выходят знаменитые поля Галуа.
Итак, что такое поля Галуа? Начнём опять с поясняющих примеров. Мы все привыкли оперировать (складывать, вычитать, умножать, делить и прочее) с числами – натуральными, рациональными, вещественными. Однако, вместо привычных чисел, мы можем начать рассматривать произвольные множества объектов (конечные и/или бесконечные) и вводить на этих множествах операции, аналогичные сложению, вычитанию и т.д. Собственно говоря, математические структуры типа групп, колец, полей - это множества, на которых введены определенные операции, причем, результаты этих операций снова принадлежат исходному множеству. Например, на множестве натуральных чисел, мы можем ввести стандартные операции сложения, вычитания и умножения. Результатом опять будет натуральное число. А вот с делением все хуже, при делении двух натуральных чисел результат может быть дробным числом.
Поле – это множество, на котором заданы операции сложения, вычитания, умножения и деления. Пример - поле рациональных чисел (дробей). Поле Галуа - конечное поле (множество, содержащее конечное количество элементов). Обычно поля Галуа обозначаются как , где - количество элементов в поле. Разработаны методы построения полей необходимой размерности (если это возможно). Конечным результатом подобных построений обычно являются таблицы сложения и умножения, которые двум элементам поля ставят в соответствие третий элемент поля.
Может возникнуть вопрос – как мы всё это будем использовать? При реализации алгоритмов на ЭВМ удобно работать с байтами. Наш алгоритм может принимать на входе байт исходных данных и вычислять по ним байт избыточных. В одном байте может содержаться 256 различных значений, поэтому, мы можем создать поле и рассчитывать избыточные байт, пользуясь арифметикой полей Галуа. Сам подход к кодированию/декодированию данных (построение порождающей матрицы, обращение матрицы, умножение матрицы на столбец) остаётся таким же, как и прежде.
Хорошо, мы в итоге научились по исходным байтам конструировать дополнительные байт, которые можно использовать при сбоях. Как это всё работает в реальных системах хранения? В реальных СХД обычно работают с блоками данных фиксированного размера (в разных системах этот размер варьируется от десятков мегабайт до гигабайтов). Этот фиксированный блок разбивается на фрагментов и по ним конструируются дополнительные фрагментов.
Процесс конструирования фрагментов происходит следующим образом. Берут по одному байту из каждого из исходных фрагментов по смещению 0. По этим данным генерируется K дополнительных байтов, каждый из который идет в соответствующие дополнительные фрагменты по смещению 0. Этот процесс повторяется для смещения – 1, 2, 3,… После того, как процедура кодирования закончена, фрагменты сохраняются на разные диски. Это можно изобразить следующим образом:
При выходе из строя одного или нескольких дисков, соответствующие потерянные фрагменты реконструируются и сохраняются на других дисках.
Теоретическая часть постепенно подходит к концу, будем надеяться, что базовый принцип кодирования и декодирования данных с использованием кодов Рида-Соломона теперь более или менее понятен. Если будет интерес к данной теме, то в следующих частях можно будет более подробно остановится на арифметике полей Галуа, реализациях алгоритма кодирования/декодирования на конкретных аппаратных платформах, поговорить про техники оптимизации.
Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации. Предупреждаю, что данный подход не будет рационален во многих случаях, но позволит реализовать помехоустойчивое кодирование данных с варьируемым процентом восстанавливаемой информации.
При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных. Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную: n - 10, количество информационных символов; f - 3, количество восстанавливаемых символов; g - 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2. Данные ходы компактнее кодов Хеминга на 1 символ.
Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m,такое поле называется расширенным. GF(p m) - обозначение поля Галуа.
Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 - 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.
Подробно информацию о арифметике полей Галуа я опубликовал на Хабрахабр . В этой же статье пойдет речь о применений полей Галуа для кодирования, декодирования информации кодами Рида-Соломона .
Для удобства подсчетов приведу 2 таблицы из статьи, посвященной полям Галуа.
Таблица умножения
Таблица степеней
Перед началом кодирования мы определились с необходимым полем GF(q), где q=p m . Длина кодовой последовательности должна быть q-1. Таким образом, в нашем случае с GF(8) кодовая последовательность состоит из 7 элементов. Дальше нужно выяснить какие элементы будут информационными, а какие проверочные (избыточные). В самом начале мы говорили о том, что количество избыточных символов должно быть в два раза больше, чем то количество ошибочных символов, которое мы хотим восстановить. Если необходимо исправить двукратную ошибку (t=2 - кратность ошибки), то, соответственно, следует использовать четыре проверочных символа. Применим это к нашему примеру: из семи элементов для исправления двукратной ошибки необходимы четыре избыточных, а значит три информационных. Кодовая последовательность выглядит следующим образом:
C=(c 0 , c 1 , c 2 , c 3 , c 4 , c 5 , c 6), где c 0 , c 1 , c 2 - информационные, c 3 , c 4 , c 5 , c 6 - проверочные.
Хочу обратить внимание на тот факт, что исправление двукратной ошибки в кодовой последовательности из семи элементов означает, что можно бороться с ошибкой, вероятность возникновения которой не больше чем р ош =2/7≈0,29. Если вероятность возникновения ошибки выше, то нужно увеличивать количество проверочных символов, иначе восстановить искаженную информацию все равно не получится.
Закодируем последовательность С=(4, 6, 7, 0, 0, 0, 0), четыре последних символа - проверочные, равны нулю.
Представим нашу последовательность в виде полинома:
С(x)=4∙x 0 +6∙x 1 +7∙x 2 +0∙x 3 +0∙x 4 +0∙x 5 +0∙x 6 =4+6∙x+7∙x 2
Кодирование осуществляется с помощью обратного дискретного преобразования Фурье (IDFT). Формула для кодирования: c j "=C(z j) , где z=2 - примитивный элемент поля.
c 0 "=C(2 0)=С(1)=4+6+7=5
c 1 "=C(2 1)=С(2)=4+6∙2+7∙4=4+7+1=2
c 2 "=C(2 2)=С(4)=4+6∙4+7∙6=4+5+4=5
c 3
"=C(2 3)=С(3)=4+6∙3+7∙5=4+1+6=3
c 4 "=C(2 4)=С(6)=4+6∙6+7∙2=4+2+5=3
c 5 "=C(2 5)=С(7)=4+6∙7+7∙3=4+4+2=2
c 6
"=C(2 6)=С(5)=4+6∙5+7∙7=4+3+3=4
Получили закодированную последовательность: C"=(5,2,5,3,3,2,4). В виде полинома: С(x)=5∙x 0 +2∙x 1 +5∙x 2 +3∙x 3 +3∙x 4 +2∙x 5 +4∙x 6 .
Формула для декодирования c j =C" (z -j) .
с 0 =C"(2 0)=C"(1)=5+2+5+3+3+2+4=4
с 1 =C" (2 -1)=C" (5)=5+2∙5+5∙7+3∙6+3∙3+2∙4+4∙2=5+1+6+1+5+3+3=6
с 2 =C" (2 -2)=C" (7)=⋯=7
с 3 =C" (2 -3)=C" (6)=⋯=0
с 4 =C" (2 -4)=C" (3)=⋯=0
с 5 =C" (2 -5)=C" (4)=⋯=0
с 6 =C" (2 -6)=C" (2)=⋯=0
При декодировании получили последовательность (4, 6, 7, 0, 0, 0, 0), которая соответствует исходной. Чтобы проверить не произошло ли искажение информации достаточно посмотреть на избыточные символы. Если они все еще равны нулю, то ошибки отсутствуют.
Ошибка представляет собой другую последовательность, которая суммируется с закодированной. Допустим вектор ошибка имеет вид: f" =(0, 0, 5, 0, 3, 0, 0), тогда кодовая последовательность с ошибкой:
C f "=C"+f"=(5,2,0,3,0,2,4)
Попробуем декодировать полученное кодовое слово: C f "=5∙x 0 +2∙x 1 +0∙x 2 +3∙x 3 +0∙x 4 +2∙x 5 +4∙x 6 =5+2∙x 1 +3∙x 3 +2∙x 5 +4∙x 6
C 0 f =C"(2 0)=C"(1)=5+2+0+3+0+2+4=2
c 0 f =C"(2 -1)=C"(5)=5+2∙5+3∙6+2∙4+4∙2=5+1+1=5
c 0 f =C"(2 -2)=C"(7)=5+2∙7+3∙2+2∙6+4∙4=5+5+6+7+6=7
c 0 f =C"(2 -3)=C"(6)=5+2∙6+3∙7+2∙5+4∙3=5+7+2+1+7=6
c 0 f =C"(2 -4)=C"(3)=5+2∙3+3∙4+2∙2+4∙6=5+6+7+4+5=5
c 0 f =C"(2 -5)=C"(4)=5+2∙4+3∙5+2∙3+4∙7=5+3+4+6+1=5
c 0 f =C"(2 -6)=C"(2)=5+2∙2+3∙3+2∙7+4∙5=5+4+5+5+2=3
C f =(2, 5, 7, 6, 5, 5, 3) - декодированная последовательность. Как видим, последние четыре элемента не равны нулю, что, собственно, и свидетельствует о наличии ошибки. Для исправления ошибки в первую очередь необходимо определить позиции искаженных символов. Для этого необходимо вычислить полином локаторов ошибок, корни которого и указывают на позиции ошибок. В матричном виде полином локаторов ошибок выглядит как L=. Так как в нашем примере мы хотим исправить ошибку кратности 2, то L=.
Выпишем последние четыре символа - синдром ошибки:
Из них сформируем матрицу и вектор-столбец, необходимый для вычисления L. В общем виде:
В нашем примере:
Вычислим M -1 , с учетом того, что мы работаем с арифметикой поля Галуа
На всякий случай можно проверить правильность вычислений:
Запишем L в виде полинома:
Вычислим корни полученного полинома простым перебором:
L(2 0)=L(1)=1+4+2=7
L(2 1)=L(2)=1+4∙2+2∙4=1
L(2 2)=L(4)=1+4∙4+2∙6=1+6+7=0
L(2 3)=L(3)=1+4∙3+2∙5=1+7+1=7
L(2 4)=L(6)=1+4∙6+2∙2=1+5+4=0
L(2 5)=L(7)=1+4∙7+2∙3=1+1+6=6
L(2 6)=L(5)=1+4∙5+2∙7=1+2+5=2
Получили, что ошибки присутствуют в c 2 " и c 4 ".
Теперь необходимо найти правильные значения. Для начала приведем L(x) к нормальному виду:
L(x)=1+4x+2x 2 |*5
Запишем вектор ошибки (последние 4 символа - значения синдрома). На местах информационных символов - знаки вопроса, их и необходимо вычислить.
Осуществим свертку для f 0 , f 1 , f 2 , а затем вычислим их значения:
Получили F=(6, 3, 0, 6, 5, 5, 3), так как ошибка суммировалась с закодированной последовательностью, то произведем операцию кодирования над F:
F(x)=6+3x+6x 3 +5x 4 +5x 5 +3x 6
Так как мы уже знаем позиции ошибок, то достаточно вычислить только f 2 "=F(2 2) и f 4 "=F(2 4) , все остальные будут равны нулю. Но для того чтобы точно в этом убедится честно посчитаем все значения:
f 0 "=F(2 0)=F(1)=6+3+6+5+5+3=0
f 1 "=F(2 1)=F(2)=6+3∙2+6∙3+5∙6+5∙7+3∙5=6+6+1+3+6+4=0
f 2 "=F(2 2)=F(4)=6+3∙4+6∙5+5∙2+5∙3+3∙7=6+7+3+1+4+2=5
f 3 "=F(2 3)=F(3)=6+3∙3+6∙4+5∙7+5∙2+3∙6=6+5+5+6+1+1=0
f 4 "=F(2 4)=F(6)=6+3∙6+6∙7+5∙4+5∙5+3∙3=6+1+4+2+7+5=3
f 5 "=F(2 5)=F(7)=6+3∙7+6∙2+5∙5+5∙6+3∙4=6+2+7+7+3+7=0
f 6 "=F(2 6)=F(5)=6+3∙5+6∙6+5∙3+5∙4+3∙2=6+4+2+4+2+6=0
Получили f" =(0, 0, 5, 0, 3, 0, 0). Сложим вектор ошибки с искаженной кодовой последовательностью:
C"=C f "+f"=(5,2,0,3,0,2,4)+(0,0,5,0,3,0,0)=(5,2,5,3,3,2,4)
В результате получили правильную закодированную последовательность, при декодировании которой получим правильные информационные символы.
Теги: | ||
Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 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 символа - синдром, который мы постоянно используем, два знака вопроса - на местах информационных символов, это маска ошибки) и обозначим каждый символ буквой:
Символы полинома локатора ошибки Г(z) = x2 + 5x + 4 обозначим так:
Перемножение полинома Г на матрицу Тёплица в предыдущем параграфе было, по сути, операцией циклической свертки: если расписать линейные уравнения, которые получаются из матричного, можно увидеть, что значения, которые берутся из синдрома (значения матрицы Тёплица), от уравнения к уравнению просто меняются местами, двигаясь последовательно в определенную сторону, а это и называется сверткой. Я специально разместил полиномы F и Г друг над другом в начале этого абзаца, чтобы можно было делать свертки (перемножать поэлементно в определенном порядке), двигая полиномы визуально. Раскрывая матричное уравнение из предыдущего параграфа и используя обозначения для полиномов F и Г, введенные только что:
Г0*F4 + Г1*F3 + Г2*F2 = 0
Г0*F5 + Г1*F4 + Г2*F3 = 0
Ранее свертка производилась только для синдрома, в методе Форни нужно сделать свертки для F0 и F1, а после найти их значения:
Г0*F3 + Г1*F2 + Г2*F1 = 0
Г0*F2 + Г1*F1 + Г2*F0 = 0
F0 = -Г0*F3 – Г1*F2 = 0
F1 = -Г0*F2 – Г1*F1 = 6
То есть F = (6,0,2,1,0,5). Проводим IDFT, так как ошибка суммировалась со словом, которое было в кодированном IDFT виде: f = (0,0,0,2,0,6).
Вычитаем ошибку f из полученного кодового слова cf: (4,1,0,4,5,5) - (0,0,0,2,0,6) = с(4,1,0,2,5,6)
Сделаем DFT для этого слова: с(4,1,0,2,5,6) => С=(3,1,0,0,0,0). А вот и наши символы 3 и 1, которые нужно было передать.
Также много устройств используют готовые таблицы ошибок, рассчитанные заранее. В условиях использования арифметики Галуа получается конечное количество возможных ошибок. Это свойство и используется для уменьшения количества расчетов. Здесь в случае, если синдром получается ненулевой, он просто сравнивается с таблицей возможных ошибочных синдромов.
Курс теории кодирования для многих часто является одним из самых сложных. Буду рад, если данная статья кому-нибудь поможет разобраться в данной теме быстрее.
Преимущество использования кодов Рида-Соломона заключается в том, что вероятность сохранения ошибок в декодированных данных обычно много меньше, чем вероятность ошибок, если коды Рида-Соломона не используются. Это часто называется выигрышем кодирования.
Пример . Пусть имеется цифровая телекоммуникационная система, работающая с BER (Bit Error Ratio ), равной 10 -9 , т.е. не более 1 из 10 9 бит передается с ошибкой. Такого результата можно достичь путем увеличения мощности передатчика или применением кодов Рида-Соломона (либо другого типа коррекции ошибок). Алгоритм Рида-Соломона позволяет системе достичь требуемого уровня BER с более низкой выходной мощностью передатчика.
Кодирование и декодирование Рида-Соломона может быть выполнено аппаратно или программно.
Коды Рида-Соломона базируются на специальном разделе математики – полях Галуа (GF) или конечных полях. Арифметические действия (+,-, x, / и т.д.) над элементами конечного поля дают результат, который также является элементом этого поля. Кодировщик или декодер РидаСоломона должны уметь выполнять эти арифметические операции. Эти операции для своей реализации требуют специального оборудования или специализированного программного обеспечения.
Кодовое слово Рида-Соломона формируется с привлечением специального полинома. Все корректные кодовые слова должны делиться без остатка на эти образующие полиномы . Общая форма образующего полинома имеет вид
g(x) = (x – a i)(x – a i+1)...(x – a i+2t)
а кодовое слово формируется с помощью операции
c(x) = g(x).i(x)
где g(x) является образующим полиномом , i(x) представляет собой информационный блок, c(x) – кодовое слово, называемое простым элементом поля.
Пример . Генератор для RS(255, 249)
g(x)= (x – a 0)(x – a 1)(x – a 2)(x – a 3)(x – a 4)(x – a 5) g(x)= x 6 + g 5 x 5 + g 3 x 3 + g 2 x 2 + g 1 x 1 + g 0
2t символов четности в кодовом слове Рида-Соломона определяются из следующего соотношения:
Ниже показана схема реализации кодировщика для версии RS(255,249) :
Каждый из 6 регистров содержит в себе символ (8 бит). Арифметические операторы выполняют сложение или умножение на символ как на элемент конечного поля.
Общая схема декодирования кодов Рида-Соломона показана ниже на рис. 4.7 .
Обозначения:
Полученное кодовое слово r(x) представляет собой исходное (переданное) кодовое слово c(x) плюс ошибки:
r(x) = c(x) + e(x)
Декодер Рида-Соломона пытается определить позицию и значение ошибки для t ошибок (или 2t потерь) и исправить ошибки и потери.
Вычисление синдрома похоже на вычисление четности . Кодовое слово Рида-Соломона имеет 2t синдромов , это зависит только от ошибок (а не передаваемых кодовых слов). Синдромы могут быть вычислены путем подстановки 2t корней образующего полинома g(x) в r(x) .
Это делается путем решения системы уравнений с t неизвестными. Существует несколько быстрых алгоритмов для решения этой задачи. Эти алгоритмы используют особенности структуры матрицы кодов РидаСоломона и сильно сокращают необходимую вычислительную мощность. Делается это в два этапа.
1. Определение полинома локации ошибок.
Это может быть сделано с помощью алгоритма Berlekamp-Massey или алгоритма Эвклида. Алгоритм Эвклида используется чаще на практике, так как его легче реализовать, однако алгоритм Berlekamp-Massey позволяет получить более эффективную реализацию оборудования и программ.
2. Нахождение корней этого полинома. Это делается с привлечением алгоритма поиска Chien.
Здесь также нужно решить систему уравнений с t неизвестными. Для решения используется быстрый алгоритм Forney.
Существует несколько коммерческих аппаратных реализаций. Имеется много разработанных интегральных схем, предназначенных для кодирования и декодирования кодов Рида-Соломона. Эти ИС допускают определенный уровень программирования (например RS(255, k) , где t может принимать значения от 1 до 16).
До недавнего времени программные реализации в "реальном времени" требовали слишком большой вычислительной мощности практически для всех кодов Рида-Соломона. Главной трудностью в программной реализации кодов Рида-Соломона являлось то, что процессоры общего назначения не поддерживают арифметические операции для поля Галуа. Однако оптимальное составление программ в сочетании с возросшей вычислительной мощностью позволяют получить вполне приемлемые результаты для относительно высоких скоростей передачи данных.