Участник:Nikz — различия между версиями
NikZ (обсуждение | вклад) |
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).Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
Так можно умножать полиномы, в данном случае мы умножили:
.
Определим также операцию деления чисел(или полиномов) с остатком – по аналогичным правилам, например:
или 
Теперь построим поле из 16 элементов 
. Операцию сложения определена на XOR, Операция деления дополнена получением остатка по некоторому модулю.
Выберем в качестве модуля неприводимый полином 
.
Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
и так далее.
Составим таблицу умножения
| Степень | Результат | |
|---|---|---|
| 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 |
Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: 
. Можно проверить результат,разделив 
.
Таким образом, получили поле , то есть для двоичных 4-разрядных чисел.
