Участник:Nikz — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
Строка 152: Строка 152:
 
== Декодирование Рида-Соломона ==
 
== Декодирование Рида-Соломона ==
 
Первым шагом необходимо выполнить деление полинома на порождающий полином <math>g(x)</math>. Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.<br />
 
Первым шагом необходимо выполнить деление полинома на порождающий полином <math>g(x)</math>. Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.<br />
−
В случае же присутствия ошибки придется выполнить следующие действия:<br />
+
Разделим закодированное сообщение на образующий полином: <math>\frac{12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4}{x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12}=0</math>,<br /> в этом можно убедиться, самостоятельно проделав операцию деления, согласно арифметике поля GF_{16}</math><br />
 +
Внесем ошибку в закодированное сообщение, полином ошибки <math>E(x)=14x^{4}</math><br />
 +
Разделим получившееся закодированное сообщение <math>C'(x)</math> на <math>g(x): r(x) = 14x + 14</math><br />
 +
В случае присутствия ошибки выполняем следующие действия:<br />
 
Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).<br />
 
Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).<br />
 
Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при <math>x^{4}</math>, то локатор этой ошибки равен <math>a^{4}</math>, если искажён коэффициент при <math>x^{7}</math> то локатор ошибки будет равен <math>a^{7}</math> и т.п. (а – примитивный член, т.е. в нашем случае a=2).
 
Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при <math>x^{4}</math>, то локатор этой ошибки равен <math>a^{4}</math>, если искажён коэффициент при <math>x^{7}</math> то локатор ошибки будет равен <math>a^{7}</math> и т.п. (а – примитивный член, т.е. в нашем случае a=2).
Строка 160: Строка 163:
 
Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.<br />
 
Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.<br />
 
Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x) = C(x) mod          g(x)</math>:    <math>S_i=e(a^{i})</math><br />
 
Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x) = C(x) mod          g(x)</math>:    <math>S_i=e(a^{i})</math><br />
 +
Для нашего примера:<br />
 +
<math>S(1) = 1;</math><br />
 +
<math>S(2) = 3;</math><br />
 
Между <math>L(x)</math> и <math>S(x)</math> существует соотношение<br />
 
Между <math>L(x)</math> и <math>S(x)</math> существует соотношение<br />
 
<math>L(x)S(x)=W(x)modx^{N-K}</math><br />
 
<math>L(x)S(x)=W(x)modx^{N-K}</math><br />
Строка 210: Строка 216:
 
<math>ML = V, \Rightarrow M^{-1}V</math>
 
<math>ML = V, \Rightarrow M^{-1}V</math>
 
Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид:<br />
 
Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид:<br />
−
<math> M = S_1</math>  , а вектор  <math>V = S_2; </math>  <math>  L(1) = S(2) / S(1)</math><br />
+
<math> M = S_1</math>  , а вектор  <math>V = S_2; </math>  <math>  L(1) = S(2) / S(1) = 3 / 1 = 3 </math><br />
 
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
 
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
 
Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.  
 
Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.  
 
После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. <br />
 
После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. <br />
 +
Для нашего примера многочлен локаторов <math>L(x) =1 + 3x </math> имеет корень \frac{1}{3}, а обратный к нему  <math> 3 = 2^{4}</math>, а значит позиция ошибки равна <math>x^{4}</math><br />
 
После нахождения позиции ошибки,займемся нахождением значением ошибки:<br />
 
После нахождения позиции ошибки,займемся нахождением значением ошибки:<br />
 
Воспользуемся определением синдромной функции:<br /> <br />
 
Воспользуемся определением синдромной функции:<br /> <br />
Строка 221: Строка 228:
 
<math>S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}</math>,<br />
 
<math>S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}</math>,<br />
 
<br /> где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки.<br /><br />
 
<br /> где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки.<br /><br />
−
Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1</math>
+
Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1 = 1 / 3 = 2^{0} / 2^{4} = 2^{11} = 14</math> - позиция ошибки.<br />Таким образом сформируем многочлен вычисленной ошибки <math>E'(x) = 14x^{4}</math>, который совпадает с заданным <math>E(x)</math><br />

Текущая версия на 18:35, 17 июня 2014

Пример коррекции ошибки с помощью кодов Рида - Соломона

Постановка задачи

В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Строка разбивает на блоки длиной 4 бита и каждый блок представляет собой элемент поля Галуа GF16. Необходимо отследить и исправить одиночную ошибку, внесённую в один из блоков.

Теоретические основы алгоритма

Поля Галуа

Операцию сложения определим как "исключающее ИЛИ" (XOR).Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:

\begin{matrix} *\underline{\begin{matrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ \end{matrix}}\\ +\underline{\begin{matrix} 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ \end{matrix}} \\ \begin{matrix} & 0 & 1 & 0 & 1 & 0 \\ \end{matrix} \\ \end{matrix}

Так можно умножать полиномы, в данном случае мы умножили: (x + 1) * (x^2 + x) = x^3 + x. Определим также операцию деления чисел(или полиномов) с остатком – по аналогичным правилам, например: \frac{110010}{101011}=011001 или \frac{x^5 + x^4 + x}{x^5 + x^3 + x + 1} = x^4 + x^3 + 1 Теперь построим поле из 16 элементов GF_{16} . Операцию сложения определена на XOR, Операция деления дополнена получением остатка по некоторому модулю. Выберем в качестве модуля неприводимый полином x^4+x+1 (10011) .

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом

  1. 1= 2^0=0001
  2. 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1
  3. 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2
  4. 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3
  5. 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1
  6. 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x

и так далее.
Составим таблицу умножения

Степень Результат
0 1 0001
1 2 0010
2 4 0100
3 8 1000
4 3 0011
5 6 0110
6 12 1100
7 11 1011
8 5 0101
9 10 1010
10 7 0111
11 14 1110
12 15 1111
13 13 1101
14 9 1001
15 1 0001

Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: 13*15=2^{13}*2^{12}=2^{25 mod 15}=2^{10}=7 . Можно проверить результат,разделив \frac{7}{13}=\frac{2^{10}}{2^{13}}=2^{-3 mod 15}=2^{12}=15 .

Таким образом, получили поле GF_{16}, то есть для двоичных 4-разрядных чисел.

Коды Рида - Соломона

При построении кода Рида-Соломона задается пара чисел N,K, где N-Общее количество символов, а К- «полезное» количество символов, N-K символов задают избыточный код, предназначенный для восстановления ошибок. Такой код Рида-Соломона будет иметь «расстояние Хемминга» D=N-K+1. В соответствии с теорией кодирования, код, имеющий расстояние Хемминга D=2t+1, позволяет восстанавливать t ошибок. Таким образом, если нам необходимо восстановить t ошибок, то общее количество символов сообщения N=K+2t. Сообщения при кодировании Рида-Соломона представляются полиномами. Исходное сообщение представляется как коэффициенты полинома p(x) степени K-1, имеющего K коэффициентов.
Порождающий многочлен Рида-Соломона,g(x), строится следующий образом: g(x)=(x+2)(x+2^{2})..(x+2^{ D-1 } ) , 2 - примитивный член поля. Нетрудно понять, что 2^{1},2^{2},..,2^{D-1} - корни этого многочлена.
Например, построим порождающий многочлен кода Рида-Соломона с N=15,K=9, способного исправлять до 3 ошибок (15-9)/2=3: g(x)=(x+2)(x+2^{2} )(x+2^{3} )(x+2^{4} )(x+2^{5} )(x+2^{6} )=x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12. (Возведение в степень и умножения выполнены над полем GF16 )!

Кодирование Рида-Соломона

Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается: Сначала полином сдвигается на N-K коэффициентов влево
p'(x)=p(x)x^{N-K} ,а потом вычисляется остаток от деления на порождающий полином и прибавляется к p'(x): C(x)=p'(x)+p'(x)mod g(x).
Для систематического кого очевидно, что K старших коэффициентов полученного кода C(x) содержат исходное сообщение. Это удобно при декодировании. Закодированное сообщение C(x) обладает очень важным свойством: оно без остатка делится на порождающий многочлен g(x).
Докажем это свойство:
Пусь r(x)-остаток от деления p'(x) на g(x).
Тогда,
p'(x)=g(x)u(x)+r(x)
Итак,
r(x)=p'(x)mod g(x)
Тогда
C(x)=p'(x)+p'(x)mod g(x)=g(x)u(x)+r(x)+r(x)
Вспомним, что в арифметике поля Галуа сложения являются одновременно и вычитанием, тогда r(x)+r(x)=0!Следовательно C(x) делится на g(x) без остатка.
Таким образом,
C(x) mod g(x)=0
В случае, если закодированное сообщение будет изменено, то это равенство будет нарушенным, не считая случая, когда ошибка окажется кратной g(x). Факт искажения можно рассматривать как прибавление к C(x) некоторого полинома ошибки E(x).
Пример:
Рассмотрим кодирование информации. Пусть наше сообщение такое: 12, 10, 12, 7
Полином сообщения получается такой: I(x)=12x^{3}+10x^{2}+12x+7
Умножаем на x^{2},получаем:
I'(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}
Делим на g(x) и получаем остаток: r(x)= x + 4
В итоге получается полином закодированного сообщения:
C(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4

Декодирование Рида-Соломона

Первым шагом необходимо выполнить деление полинома на порождающий полином g(x). Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.
Разделим закодированное сообщение на образующий полином: \frac{12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4}{x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12}=0,
в этом можно убедиться, самостоятельно проделав операцию деления, согласно арифметике поля GF_{16}</math>
Внесем ошибку в закодированное сообщение, полином ошибки E(x)=14x^{4}
Разделим получившееся закодированное сообщение C'(x) на g(x): r(x) = 14x + 14
В случае присутствия ошибки выполняем следующие действия:
Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).
Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при x^{4}, то локатор этой ошибки равен a^{4}, если искажён коэффициент при x^{7} то локатор ошибки будет равен a^{7} и т.п. (а – примитивный член, т.е. в нашем случае a=2). Многочлен локаторов L(x) – это многочлен, корни которого обратны локаторам ошибок. Таким образом, многочлен L(x) должен иметь вид
L(x)=(1+xX_1 )(1+xX_2)..(1+xX_i)
где X_1,X_2,..,X_i - локаторы ошибок
Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.
Для определения этого полинома сначала получают вспомогательный полином S(x), так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен r(x) = C(x) mod g(x): S_i=e(a^{i})
Для нашего примера:
S(1) = 1;
S(2) = 3;
Между L(x) и S(x) существует соотношение
L(x)S(x)=W(x)modx^{N-K}
W(x) называется многочленом ошибок. Степень многочлена W(x) не может превышать t-1, где t – количество ошибок, то есть в максимальном случае (N-K)/2-1
С учётом этого обстоятельства, а также учитывая, что свободный член L(x): L_0=1 (ведь L(x)=(1+xX_1 )(1+xX_2 )..(1+xX_i) ) можно составить систему линейных уравнений. W(x)=
L_0 S_0
(L_0 S_1+L_1 S_0 )X+
(L_0 S_2+L_1 S_1+L_2 S_0 ) X^2+
(L_0 S_3+L_1 S_2+L_2 S_1+L_3 S_0 ) X^3+
...
(L_0 S_{N-K-1}+L_1 S_{N-K-2}..L_{(N-K)/2} S_{(N-K)/2-1}X^{N-K-1}
Пусть t = (N-K)/2
Коэффициенты при степенях от 0 до t – 1 не равны нулю, при старших степенях должны быть нулевыми.
L_0 S_t+L_1 S_{t-1}+L_2 S_{t-2}+L_3 S_{t-3}...L_t S_0 = 0
L_0 S_{t+1}+L_1 S_t+L_2 S_{t-1}+L_3 S_{t-2}...L_t S_1 = 0
L_0 S_{t+2}+L_1 S_{t+1}+L_2 S_t+L_3 S_{t-1}...L_t S_2 = 0
\dots
L_0 S_{2t-1}+L_1 S_{2t-2}+L_2 S_{2t-3}+L_3 S_{2t-4}...L_t S_t = 0
Коэффициент L_0 известен, остальные необходимо найти, следовательно требуется составить t уравнений.
L_1 S_{t-1}+L_2 S_{t-2}+L_3 S_{t-3}...L_t S_0 = S_t
L_1 S_t+L_2 S_{t-1}+L_3 S_{t-2}...L_t S_1 = S_{t+1}
L_1 S_{t+1}+L_2 S_t+L_3 S_{t-1}...L_t S_2 = S_{t+2}
...
L_1 S_{2t-2}+L_2 S_{2t-3}+L_3 S_{2t-4}...L_t S_t = S_{2t-1}
В матричном виде:

M= \quad\left\|\begin{array}{ccccc} S_{t-1} & S_{t-2} & S_{t-3} & \cdots & S_0\\ S_{t} & S_{t-1} & S_{t-2} & \cdots & S_1\\ S_{t+1} & S_{t} & S_{t-1} & \cdots & S_2\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ S_{2t-2} & S_{2t-3} & S_{2t-4} & \cdots & S_t\\ \end{array}\right\|

V=\quad\left\|\begin{array}{c} S_{t} \\ S_{t+1} \\ S_{t+2} \\ \cdots \\ S_{2t-1} \\ \end{array}\right\|

L=\quad\left\|\begin{array}{c} L_{1} \\ L_{2} \\ L_{3} \\ \cdots \\ L_{t} \\ \end{array}\right\|

ML = V, \Rightarrow M^{-1}V Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид:
M = S_1 , а вектор V = S_2; L(1) = S(2) / S(1) = 3 / 1 = 3
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V. Обратная матрица получается так же, как и в обычной математике, например Жордановым методом. После того, как полином L(x) найден, следует найти его корни – они будут обратны к локаторам ошибок.
Для нашего примера многочлен локаторов L(x) =1 + 3x имеет корень \frac{1}{3}, а обратный к нему 3 = 2^{4}, а значит позиция ошибки равна x^{4}
После нахождения позиции ошибки,займемся нахождением значением ошибки:
Воспользуемся определением синдромной функции:

S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n,
S(2) = r(\alpha) = e_1 L_1^{2} + e_2 L_2^{2} + ... + e_n L_n^{2},
...
S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n},

где e_1,e_2,..,e_n - значение ошибки. L_1,L_2,..,L_n - позиция ошибки.

Для нашего кода RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1 = 1 / 3 = 2^{0} / 2^{4} = 2^{11} = 14 - позиция ошибки.
Таким образом сформируем многочлен вычисленной ошибки E'(x) = 14x^{4}, который совпадает с заданным E(x)

Источник — «https://vscripts.ru/w/index.php?title=Участник:Nikz&oldid=900»