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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 110: Строка 110:
 
Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: <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>.<br />
 
Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: <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>.<br />
  
'''Таким образом, получили поле GF_{16}, то есть для двоичных 4-разрядных чисел.'''
+
'''Таким образом, получили поле <math>GF_{16}</math>, то есть для двоичных 4-разрядных чисел.'''

Версия 11:24, 19 мая 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-разрядных чисел.