Pull to refresh

Коды Рида-Соломона. Простой пример

Reading time 9 min
Views 119K
Гауссово котэБлагодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 25%. Восстановить при этом можно количество данных, равное половине избыточных. Если емкость диска 700 Мб, то, получается, теоретически можно восстановить до 87,5 Мб из 700. При этом нам не обязательно знать, какой именно символ передан с ошибкой. Также стоит отметить, что вместе с кодированием используется перемежевание, когда байты разных блоков перемешиваются в определенном порядке, что в результате позволяет читать диски с обширными повреждениями, локализированными близко друг к другу (например, глубокие царапины), так как после операции, обратной перемежеванию, обширное повреждение оборачивается единичными ошибками во множестве блоков кода, которые поддаются восстановлению.

Давайте возьмем простой пример и попробуем пройти весь путь – от кодирования до получения исходных данных на приемнике. Пусть нам нужно передать кодовое слово С, состоящее из двух чисел – 3 и 1 именно в такой последовательности, т.е. нам нужно передать вектор С=(3,1). Допустим, мы хотим исправить максимум две ошибки, не зная точно, где они могут появиться. Для этого нужно взять 2*2=4 избыточных символа. Запишем их нулями в нашем слове, т.е. С теперь равно (3,1,0,0,0,0). Далее необходимо немного разобраться с математическими особенностями.

Поля Галуа


Многие знают романтическую историю о молодом человеке, который прожил всего 20 лет и однажды ночью написал свою математическую теорию, а утром был убит на дуэли. Это Эварист Галуа. Также он несколько раз пытался поступить в университеты, однако экзаменаторы не понимали его решений, и он проваливал экзамены. Приходилось ему учиться самостоятельно. Ни Гаусс, ни Пуассон, которым он послал свои работы, также не поняли их, однако его теория отлично пригодилась в 60-х годах ХХ-го века, и активно используется в наше время как для теоретических вычислений в новых разделах математики, так и на практике.

Мы будем использовать довольно простые выводы, следующие из его теории групп. Основная идея – есть конечное (а не бесконечное) количество чисел, называемое полем, с помощью которых можно проводить все известные математические операции. Количество чисел в поле должно являться простым числом в любой натуральной степени, однако в случае простых кодов Рида-Соломона, рассматриваемых здесь, размерность поля — простое число в степени 1. В расширенных кодах Рида-Соломона степень более 1.
Например, для поля Галуа размерности 7, т.е. GF(7), все математические операции будут происходить с числами 0,1,2,3,4,5,6.
Пример сложения: 1+2=3; 4+5=9 mod 7=2. Сложение в полях Галуа представляет собой сложение по модулю. Вычитание и умножение также делается по модулю.
Пример деления: 5/6 = 30/36 = 30/(36 mod 7) = 30/1 = 30 = 30 mod 7 = 2.
Возведение степень происходит аналогично умножению.

Полезное свойство обнаруживается в полях Галуа при возведении в степень. Как можно заметить, если возвести в степень числа 3 либо 5 в выбранном поле Галуа GF(7), в строке присутствуют все элементы текущего поля Галуа кроме 0. Такие числа называются примитивными элементами. В кодах Рида-Соломона обычно используется самый большой примитивный элемент выбранного поля Галуа. Для GF(7) он равен 5.
Можно отметить, что числа в полях Галуа – это вместе с тем и абстракции, которые имеют более тесную связь между собой, чем привычные нам числа.

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


Как многие знают еще со школьного курса, интерполяция – это нахождение многочлена минимальной степени в данном наборе точек. Например, есть три точки и три значения какой-то функции в этих точках. Можно найти функцию, которая удовлетворяет таким входным данные. Например, это очень просто сделать с помощью преобразования Лагранжа. После того, как функция найдена, можно построить еще несколько точек, и эти точки будут связаны с тремя исходными точками. Формирование избыточных символов при кодировании – это операция, похожая на интерполяцию.

Обратное дискретное преобразование Фурье (IDFT)


Преобразование Фурье, наряду с теорией групп Галуа – это еще одна вершина математической мысли, которая в сегодняшнее время используется во множестве областей. Некоторые даже считают, что преобразование Фурье описывает один из фундаментальных законов Вселенной. Основная суть: любой непериодический сигнал конечной протяженности можно представить в виде суммы синусоид разных частот и фаз, потом по ним можно заново построить исходный сигнал. Однако это не единственное описание. Числа в полях Галуа напоминают упомянутые разные частоты синусоид, так что преобразование Фурье можно использовать и для них.
Дискретное преобразование Фурье – это формула преобразования Фурье для дискретных значений. Преобразование имеет два направления – прямое и обратное. Обратное преобразование проще математически, поэтому давайте закодируем рассматриваемое слово С=(3,1,0,0,0,0) с помощью него. Первые два символа – информация, последние четыре – избыточные и всегда равны 0.
Запишем кодовое слово С в виде полинома: С=3*х0+1*х1 + 0*х2 +… = 3+х. Как поле Галуа возьмем упомянутое GF(7), где примитивный элемент = 5. Делая IDFT, находятся значения полинома С для примитивного элемента z разных степеней. Формула IDFT: cj=C(zj). То есть, находим значения функции С(zj), где j – элементы поля Галуа GF(7). Мы рассчитываем до j=N-2=7-2=5 степени. Посмотрев на таблицу степеней, можно догадаться, почему: в шестой степени значение снова 1, т.е. повторяется, вследствие чего потом невозможно было бы определить, в какую степень возводили – в 6ю или 0ю.
с0 = С(z0) = 3 + 1* z0 = 3 + 1* 50 = 4
с1 = С(z1) = 3 + 1* z1 = 8 = 1
с2 = С(z2) = 3 + 1* z2 = 0

Таким образом С(3,1,0,0,0,0) => с(4,1,0,2,5,6).

Мы передаем слово с(4,1,0,2,5,6).

Ошибка


Ошибка представляет собой еще одно слово, которое суммируется с передаваемым. Например, ошибка f=(0,0,0,2,0,6). Если сделать с + f, то получим сf(4,1,0,4,5,5).

Прямое преобразование Фурье (DFT). Декодирование. Синдром


На приемнике мы получили слово с+f = сf(4,1,0,4,5,5). Как проверить, были ли ошибки при передаче? Известно, что мы кодировали информацию с помощью IDFT в GF(7). DFT (дискретное преобразование Фурье) – это преобразование, обратное IDFT. Проделав его, можно получить исходную информацию и четыре нуля (т.е. С(3,1,0,0,0,0)), в случае, если ошибок не было. Если же ошибки были, то вместо этих четырех нулей будут другие цифры. Проделаем DFT для сf и проверим, есть ли ошибки. Формула DFT: Сk=N-1*c(z-kj). По-прежнему используется примитивный элемент z=5 поля GF(7).
C0 = c(5-0*j)/6 = (4*5-0*0 + 1*5-1*0 + 0*5-2*0 + 4*5-3*0 + 5*5-4*0 + 5*5-5*0)/6 = (4 + 1 + 4 + 0 + 5 + 5)/6 = 19/6 = 5/6 = 30/36 = 30 = 2;
C1 = c(5-1*j)/6 = (4*5-0*1 + 1*5-1*1 + 0*5-2*1 + 4*5-3*1 + 5*5-4*1 + 5*5-5*1)/6 = (4 + 3/15 + 24/750 + 20/2500 + 25/15625)/6 = (4 + 3 + 24 + 20 + 25)/6 = 76/6 = 456/36 = 456 = 1;
C2 = c(5-2*j)/6 = (4*5-0*2 + 1*5-1*2 + 0*5-2*2 + 4*5-3*2 + 5*5-4*2 + 5*5-5*2)/6 = (4 + 2 + 4 + 10 + 20)/6 = 40/6 = 240/36 = 240 = 2;

сf(4,1,0,4,5,5) => Cf(2,1,2,1,0,5). Выделенные символы были бы нулями, если бы ошибки не было. Теперь видно, что ошибка была. В данном случае символы 2,1,0,5 называются синдромом ошибки.

Алгоритм Берлекампа-Месси для вычисления позиции ошибки


Чтобы исправить ошибку, нужно знать, какие именно символы были переданы с ошибкой. На этом этапе вычисляется, где находятся ошибочные символы, сколько было ошибок, а также можно ли исправить такое количество ошибок.
Алгоритм Берлекампа-Месси занимается поиском полинома, который, при перемножении на специальную матрицу, подготовленную из чисел синдрома (пример далее), отдаст нулевой вектор. Доказательство алгоритма показывает, что корни этого полинома содержат информацию о позиции символов с ошибками в полученном кодовом слове.
Так как максимальное количество ошибок для рассматриваемого случая может быть 2, напишем формулу искомого полинома в матричном виде для двух ошибок (полином степени 2): Г = [1 Г1 Г2].
Теперь запишем синдром (2,1,0,5) в формате матрицы Тёплица. Если вы посмотрите на синдром и на полученную матрицу, вы сразу заметите принцип создания такой матрицы. Размерность матрицы обусловлена полиномом Г, обозначенным выше.

Уравнение, которое нужно решить:

Элементы под знаками вопроса не влияют на результат. Необходимо найти Г1 и Г2, они отвечают за позиции ошибок. Мы постепенно будем увеличивать размерность, с которой работаем. Начинаем с 1 и с нижнего левого края матрицы (отмечено зеленым) при минимальной размерности 1х1.

Увеличиваем размерность. Предположим, что ошибки в позиции Г1 у нас нет. Тогда Г1 = 0.

Мы должны получить [0 0] справа, или, как минимум, один 0 на первом месте, чтобы повысить размерность вычислений, однако на первом месте стоит 1. Мы можем подобрать такое значение для Г1 (которое сейчас 0), чтобы справа получить необходимый 0. Процесс подбора значения Г1 в алгоритме оптимизирован. Запишем два уравнения, рассмотренных ваше, еще раз, а также выведем третье уравнение, которым вычисляется Г1. Цветами показано, что куда идет.

Т.е. Г1 = 3. Напоминаю, что подсчет идет в GF(7). Также стоит отметить, что значение Г1 временное. Во время расчетов Г2 оно может поменяться. Считаем заново правую часть:

Получили 0 справа, теперь повышаем размерность. Предполагаем по аналогии, что Г2 = 0. Используем найденный Г1=3.

Первым делом вместо тройки справа нужно получить 0. Действия соответствуют предыдущим. Далее подбор значения Г2.

Запишем новое значение Г2=2 в основное уравнение и опять попробуем найти значения справа:

Задача на данном шаге была получить только первый ноль, однако волей случая второй элемент матрицы также оказался нулем, т.е. задача решена. Если бы он не был нулем, мы бы еще раз делали подбор значений (на этот раз и для Г1, и для Г2), повысив размерность подбора. Если вы заинтересовались данным алгоритмом, вот еще два примера.
Итак, Г1 = 3, Г2 = 2. Ненулевые значения для Г1 и Г2 показывает, что было 2 ошибки. Запишем матрицу Г в виде полинома: Г(z) = 1 + 3x + 2x2. Корни с учетом степеней примитивного элемента, в которых результат получается 0:
Г(53) = 1 + 3*6 + 2*62 = 91 = 13*7 = 0.
Г(55) = 1 + 3*3 + 2*32 = 28 = 0.
Это означает, что ошибки в позициях 3 и 5.
Аналогично можно найти остальные значения, чтобы убедиться, что они не дадут нули:
Г=>г(zj) = (3,5,5,0,4,0). Как вы могли заметить, снова используется IDFT в GF(7).

Исправление ошибок методом Форни


На предыдущем этапе вычислялись позиции ошибок, теперь осталось найти верные значения. Полином, описывающий позиции ошибок: Г(z) = 1 + 3x + 2x2. Запишем его в нормализированном виде, умножив на 4 и воспользовавшись свойствами GF(7): Г(z) = x2 + 5x + 4.
Метод Форни основан на интерполяции Лагранжа и использует полиномы, которыми мы оперировали в алгоритме Берлекампа-Месси.
В методе дополнительно рассчитываются те символы, которые стоят на местах, не относящихся к синдрому. Это те позиции, которые соответствуют реальным значениям, однако для них рассчитываются другие значения, которые получаются из свертки синдрома ошибки и полинома Г. Эти вычисленные новые значения вместе с синдромом формируют маску ошибки. Далее выполняется IDFT и результат представляет собой непосредственно ошибку, которая ранее суммировалась с передаваемым кодовым словом. Она вычитается из полученного слова и мы получаем первоначальное переданное слово. Затем выполняем DFT для переданного кодового слова и получаем, наконец, информацию. Далее — как это происходит в контексте рассматриваемого примера.

Запишем вектор ошибки 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, которые нужно было передать.

Заключение


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

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

Курс теории кодирования для многих часто является одним из самых сложных. Буду рад, если данная статья кому-нибудь поможет разобраться в данной теме быстрее.
Tags:
Hubs:
+86
Comments 32
Comments Comments 32

Articles