Участник:Nikz

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

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

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

Поля Галуа

Операцию сложения определим как «исключающее ИЛИ»(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-разрядных чисел.