Программа помехоустойчивого кодирования кодом рида соломона. Коды Рида-Соломона. Простой пример. Исправление ошибок методом Форни

05.04.2019

Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 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: c j =C(z j). То есть, находим значения функции С(z j), где j – элементы поля Галуа GF(7). Мы рассчитываем до j=N-2=7-2=5 степени. Посмотрев на таблицу степеней, можно догадаться, почему: в шестой степени значение снова 1, т.е. повторяется, вследствие чего потом невозможно было бы определить, в какую степень возводили – в 6ю или 0ю.
с 0 = С(z 0) = 3 + 1* z 0 = 3 + 1* 5 0 = 4
с 1 = С(z 1) = 3 + 1* z 1 = 8 = 1
с 2 = С(z 2) = 3 + 1* z 2 = 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).
C 0 = 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;
C 1 = 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;
C 2 = 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) => C f (2,1,2,1,0,5 ). Выделенные символы были бы нулями, если бы ошибки не было. Теперь видно, что ошибка была. В данном случае символы 2,1,0,5 называются синдромом ошибки.

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

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

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

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

Увеличиваем размерность. Предположим, что ошибки в позиции Г1 у нас нет. Тогда Г1 = 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 + 2x 2 . Корни с учетом степеней примитивного элемента, в которых результат получается 0:
Г(5 3) = 1 + 3*6 + 2*6 2 = 91 = 13*7 = 0.
Г(5 5) = 1 + 3*3 + 2*3 2 = 28 = 0.
Это означает, что ошибки в позициях 3 и 5.
Аналогично можно найти остальные значения, чтобы убедиться, что они не дадут нули:
Г=>г(z j) = (3,5,5,0,4,0). Как вы могли заметить, снова используется IDFT в GF(7).

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

На предыдущем этапе вычислялись позиции ошибок, теперь осталось найти верные значения. Полином, описывающий позиции ошибок: Г(z) = 1 + 3x + 2x 2 . Запишем его в нормализированном виде, умножив на 4 и воспользовавшись свойствами GF(7): Г(z) = x 2 + 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(2 m)), например кодирование байтов информации. Алгоритмы работы похожи на те, что разобраны в этой статье.
Есть множество разновидностей алгоритма в зависимости от областей применения, а также в зависимости от возраста каждой конкретной разновидности и от компании-разработчика. Чем алгоритм моложе, тем он сложнее.

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

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

Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации. Предупреждаю, что данный подход не будет рационален во многих случаях, но позволит реализовать помехоустойчивое кодирование данных с варьируемым процентом восстанавливаемой информации.

При работе с кодами Рида-Соломона процент избыточных символов в 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)

В результате получили правильную закодированную последовательность, при декодировании которой получим правильные информационные символы.

Теги:

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

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

Чтобы получить более детальное представление о кодах Рида-Соломона посмотрим, какое место они занимают в классификации корректирующих кодов (рис. 4.4).

Корректирующие коды разделяются на блочные и сверточные (непрерывные). Блочные коды основаны на перекодировании исходной кодовой комбинации (блока), содержащейk информационных символов, в передаваемую кодовую комбинацию, содержащуюn >k символов. Дополнительныер = n – k символов зависят только отk символов исходной кодовой комбинации. Следовательно, кодирование и декодирование осуществляются всегда в пределах одной кодовой комбинации (блока). В противоположность этому всверточных кодах кодирование и декодирование осуществляются непрерывно над последовательностью двоичных символов.

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

Следующая ступень классификации – систематические коды . Они отличаются тем, что в них проверочные символы формируются из информационных символов по определенным правилам, выражаемым математическими соотношениями. Например, каждый проверочный символх pj получается как линейная комбинация информационных символов

Рис. 4.4. Место кодов Рида-Соломона в классификации корректирующих кодов

где
– коэффициенты, принимающие значения 0 или 1;
. Соотношение для формирования контрольного бита проверки на четность является частным случаем.

Перейдем к более подробному знакомству с циклическими кодами .

В первую очередь введем запись кодовой комбинации или, как часто называют ее в литературе, кодового вектора в виде полинома. Пусть имеется кодовая комбинация a 0 a 1 a 2 ...a n –1 , гдеа 0 – младший разряд кода,a n –1 – старший разряд кода. Соответствующий ей полином имеет вид

где х – формальная переменная, вводимая только для получения записи кодовой комбинации в виде полинома.

Над полиномами, представляющими кодовые комбинации, определена математическая операция умножения. Особенность этой операции по сравнению с общепринятой заключается в том, что коэффициенты при х всех степеней суммируются по модулю 2, а показатели степених при перемножении суммируются по модулюn , поэтомух n = 1.

Далее введем понятие производящего полинома . Производящим полиномом порядка (n – k ) может быть полином со старшей степенью х , равной (n – k ), на который без остатка делится двучлен (1 + х n ). Разрешенные кодовые комбинации получаются перемножением полиномов порядка k – 1, выражающих исходные кодовые комбинации, на производящий полином.

Циклические коды имеют следующее основное свойство. Если кодовая комбинация a 0 a 1 a 2 ...a n –1 является разрешенной, то получаемая из нее путем циклического сдвига кодовая комбинацияa n –1 a 0 a 1 ...a n –2 также является разрешенной в данном коде. При записи в виде полиномов операция циклического сдвига кодового слова сводится к умножению соответствующего полинома нах с учетом приведенных ранее правил выполнения операции умножения.

Циклический код с производящим полиномом
строится следующим образом.

1. Берутся полиномы
,
,
, ...,
.

2. Кодовые комбинации, соответствующие этим полиномам, записывают в виде строк матрицы G , называемойпроизводящей матрицей .

3. Формируется набор разрешенных кодовых комбинаций кода. В него входит нулевая кодовая комбинация, k кодовых комбинаций, указанных в п. 1, а также суммы их всевозможных сочетаний. Суммирование осуществляется поразрядно, причем каждый разряд суммируется по модулю 2 . Общее число полученных таким образом разрешенных кодовых комбинаций равно 2 k , что соответствует числу информационных разрядов кода.

Для построения декодера в первую очередь получают производящий полином
порядкаk для построенияисправляющей матрицы Н :

Строками исправляющей матрицы Н будут кодовые комбинации, определяемые полиномами
,
, ...,
, где
– это записанный в обратном порядке полином
. Исправляющая матрица имеетn столбцов иn – k строк.

При декодировании принятая кодовая комбинация a 0 a 1 a 2 ...a n –1 скалярно умножается на каждую строку исправляющей матрицы. Эта операция может быть записана в виде соотношения:

где h ji – элементыj -той строки матрицыН . Полученныеn – k чиселc j образуютисправляющий вектор илисиндром . Если ошибок нет, то всеc j = 0. Если же при передаче данной кодовой комбинации возникла ошибка, то некоторые из чиселc j не равны 0. По тому, какие именно элементы исправляющего вектора отличны от нуля, можно сделать вывод о том, в каких разрядах принятой кодовой комбинации есть ошибка и, следовательно, исправить эти ошибки.

Рассмотрим пример, часто встречающийся в литературе. Построим циклический код с n = 7;k = 4. Для этого представим двучлен 1 +х 7 в виде произведения :

В обычной алгебре это равенство, конечно, не выполняется, но если использовать для приведения подобных вместо обычного сложения операцию суммирования по модулю 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.

Различные виды циклических кодов получаются с помощью различных производящих полиномов. Существует развитая математическая теория этого вопроса . Среди большого количества циклических кодов к числу наиболее эффективных и широко используемых относятся коды Бозе-Чоудхури-Хоквингема (ВСН-коды – по первым буквам фамилий Bose,Chaudhuri,Hockwinhamили в русскоязычной записи БЧХ-коды), являющиесяобобщением кодов Хемминга на случай направления нескольких ошибок. Они образуют наилучший среди известных класснеслучайных кодов для каналов, в которых ошибки в последовательных символах возникают независимо. Например, БЧХ-код (63, 44), используемый в системе спутникового цифрового радиовещания, позволяет исправить 2 или 3 ошибки, обнаружить 4 или 5 ошибок на каждый блок из 63 символов. Относительная скорость такого кода равнаR = 44/63 = 0,698.

Одним из видов ВСН-кодов являются коды Рида-Соломона. Эти коды относятся к недвоичным кодам , так как символами в них могут быть многоразрядные двоичные числа, например, целые байты. В Европейском стандарте цифрового телевидения DVB используется код Рида-Соломона, записываемый как (204, 188, 8), где 188 – количество информационных байт в пакете транспортного потока MPEG-2, 204 – количество байт в пакете после добавления проверочных символов, 8 – минимальное кодовое расстояние между допустимыми кодовыми комбинациями. Таким образом, в качестве кодовых комбинаций берутся целые пакеты транспортного потока, содержащие 1888 = 1504 информационных бита, а добавляемые проверочные символы содержат 168 = 128 бит. Относительная скорость такого кода равна 0,92. Этот код Рида-Соломона позволяет эффективно исправлять до 8 принятых с ошибками байт в каждом транспортном пакете.

Отметим также, что используемый в цифровом телевизионном вещании код Рида-Соломона часто называют укороченным . Смысл этого термина состоит в следующем. Из теории кодов Рида-Соломона следует, что если символом кода является байт, то полная длина кодового слова должна составлять 255 байт (239 информационных и 16 проверочных). Однако, пакет транспортного потокаMPEG-2 содержит 188 байт. Чтобы согласовать размер пакета с параметрами кода, перед кодированием в начало каждого транспортного пакета добавляют 51 нулевой информационный байт, а после кодирования эти дополнительные нулевые байты отбрасывают.

В приемнике для каждого принятого транспортного пакета, содержащего 204 байта, вычисляются синдромы и находятся два полинома: «локатор», корни которого показывают положение ошибок, и «корректор» (evaluator), дающий значение ошибок. Ошибки корректируются, если это возможно. Если же коррекция невозможна (например, ошибочных байт более 8) данные в пакете не изменяются, а сам пакет помечается путем установки флага (первый бит после синхробайта), как содержащий неустранимые ошибки. В обоих случаях 16 избыточных байт удаляются, и после декодирования длина транспортного пакета становится равной 188 байт.

Пусть 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символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путем и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путем.