Модулярная арифметика - Вклад участника [ru]

Участник:Nikz

2014-06-17T18:35:21Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

<math>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\|</math> 
<math>V=\quad\left\|\begin{array}{c}
S_{t} \\
S_{t+1} \\
S_{t+2} \\
\cdots \\
S_{2t-1} \\
\end{array}\right\|</math> 
<math>L=\quad\left\|\begin{array}{c}
L_{1} \\
L_{2} \\
L_{3} \\
\cdots \\
L_{t} \\
\end{array}\right\|</math> 
<math>ML = V, \Rightarrow M^{-1}V</math>
Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид: 
<math> M = S_1</math> , а вектор <math>V = S_2; </math> <math> L(1) = S(2) / S(1) = 3 / 1 = 3 </math> 
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.
После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. 
Для нашего примера многочлен локаторов <math>L(x) =1 + 3x </math> имеет корень \frac{1}{3}, а обратный к нему <math> 3 = 2^{4}</math>, а значит позиция ошибки равна <math>x^{4}</math> 
После нахождения позиции ошибки,займемся нахождением значением ошибки: 
Воспользуемся определением синдромной функции: 
<math>S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n</math>, 
<math>S(2) = r(\alpha) = e_1 L_1^{2} + e_2 L_2^{2} + ... + e_n L_n^{2}</math>, 
<math>...</math> 
<math>S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}</math>, 
 где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </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> - позиция ошибки. Таким образом сформируем многочлен вычисленной ошибки <math>E'(x) = 14x^{4}</math>, который совпадает с заданным <math>E(x)</math>

Участник:Nikz

2014-06-16T15:49:50Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

<math>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\|</math> 
<math>V=\quad\left\|\begin{array}{c}
S_{t} \\
S_{t+1} \\
S_{t+2} \\
\cdots \\
S_{2t-1} \\
\end{array}\right\|</math> 
<math>L=\quad\left\|\begin{array}{c}
L_{1} \\
L_{2} \\
L_{3} \\
\cdots \\
L_{t} \\
\end{array}\right\|</math> 
<math>ML = V, \Rightarrow M^{-1}V</math>
Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид: 
<math> M = S_1</math> , а вектор <math>V = S_2; </math> <math> L(1) = S(2) / S(1)</math> 
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.
После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. 
После нахождения позиции ошибки,займемся нахождением значением ошибки: 
Воспользуемся определением синдромной функции: 
<math>S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n</math>, 
<math>S(2) = r(\alpha) = e_1 L_1^{2} + e_2 L_2^{2} + ... + e_n L_n^{2}</math>, 
<math>...</math> 
<math>S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}</math>, 
 где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки. 
Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1</math>

Участник:Nikz

2014-06-16T15:21:51Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

<math>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\|</math> 
<math>V=\quad\left\|\begin{array}{c}
S_{t} \\
S_{t+1} \\
S_{t+2} \\
\cdots \\
S_{2t-1} \\
\end{array}\right\|</math> 
<math>L=\quad\left\|\begin{array}{c}
L_{1} \\
L_{2} \\
L_{3} \\
\cdots \\
L_{t} \\
\end{array}\right\|</math> 
<math>ML = V, \Rightarrow M^{-1}V</math>
Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид: 
<math> M = S_1</math> , а вектор <math>V = S_2; </math> <math> L(1) = S(2) / S(1)</math> 
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.
После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. 
После нахождения позиции ошибки,займемся нахождением значением ошибки: 
Воспользуемся определением синдромной функции: 
<math>S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n</math>, где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки. 
Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1</math>

Участник:Nikz

2014-06-15T16:47:24Z

NikZ:

Участник:Nikz

2014-06-15T15:59:38Z

NikZ:

Участник:Nikz

2014-06-15T14:19:26Z

NikZ:

Участник:Nikz

2014-06-15T14:03:11Z

NikZ:

Участник:Nikz

2014-06-13T18:31:02Z

NikZ:

Участник:Nikz

2014-05-19T11:24:35Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

Участник:Nikz

2014-05-19T11:24:00Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

Участник:Nikz

2014-05-19T11:23:15Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

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

Участник:Nikz

2014-05-19T11:22:12Z

NikZ:

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

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

<math> \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}
</math>

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

Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
# <math>1= 2^0=0001 </math>
# <math> 2^0*2=2^1=0010 _{mod 10011} = 2 = x^1 </math>
# <math> 2^1*2=2^2=0100 _{mod 10011} = 4 = x^2 </math>
# <math> 2^2*2=2^3=1000 _{mod 10011} = 8 = x^3 </math>
# <math> 2^3*2=2^4=10000 _{mod 10011} = 0011 = 3 = x+1 </math>
# <math> 2^4*2=2^5=100000 _{mod 10011} = 0110 = 6 = x^2+x </math>
и так далее. 
'''Составим таблицу умножения''' 

{| class="wikitable" border="1"
|-
! Степень
! Результат
|-
| 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
|}

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

Участник:Nikz

2014-05-19T11:13:48Z

NikZ:

Участник:Nikz

2014-05-19T10:15:57Z

NikZ:

Участник:Nikz

2014-05-19T10:00:54Z

NikZ:

Участник:Nikz

2014-05-19T09:33:20Z

NikZ: NikZ переименовал страницу Участник:Пример коррекции ошибки с помощью кодов Рида-Соломона в Участник:Nikz

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

2014-05-19T09:33:20Z

NikZ: NikZ переименовал страницу Участник:Пример коррекции ошибки с помощью кодов Рида-Соломона в Участник:Nikz

#перенаправление [[Участник:Nikz]]

Участник:Nikz

2014-05-19T09:32:01Z

NikZ:

Участник:Nikz

2014-05-19T09:31:08Z

NikZ: NikZ переименовал страницу Участник:NikZ в Участник:Пример коррекции ошибки с помощью кодов Рида-Соломона

Участник:NikZ

2014-05-19T09:31:08Z

NikZ: NikZ переименовал страницу Участник:NikZ в Участник:Пример коррекции ошибки с помощью кодов Рида-Соломона

#перенаправление [[Участник:Пример коррекции ошибки с помощью кодов Рида-Соломона]]

Участник:Nikz

2014-05-19T09:20:36Z

NikZ:

Участник:Nikz

2014-05-19T09:14:42Z

NikZ: Новая страница: «== Пример коррекции ошибки с помощью кодов Рида-Соломона ==»

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