Участник: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$.