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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
= Пример коррекции ошибки с помощью кодов Рида - Соломона =
 
== Постановка задачи ==
 
== Постановка задачи ==
 
В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Строка разбивает на блоки длиной 4 бита и каждый блок представляет собой элемент поля Галуа GF<sub>16</sub>. Необходимо отследить и исправить одиночную ошибку, внесённую в один из блоков.
 
В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Строка разбивает на блоки длиной 4 бита и каждый блок представляет собой элемент поля Галуа GF<sub>16</sub>. Необходимо отследить и исправить одиночную ошибку, внесённую в один из блоков.
Строка 4: Строка 5:
 
== Теоретические основы алгоритма ==
 
== Теоретические основы алгоритма ==
 
=== Поля Галуа ===
 
=== Поля Галуа ===
−
Операцию сложения определим как «исключающее ИЛИ»(XOR).Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
+
Операцию сложения определим как "исключающее ИЛИ" <math>(XOR)</math>.Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
 
    
 
    
 
<math> \begin{matrix} *\underline{\begin{matrix}
 
<math> \begin{matrix} *\underline{\begin{matrix}
Строка 111: Строка 112:
  
 
'''Таким образом, получили поле <math>GF_{16}</math>, то есть для двоичных 4-разрядных чисел.'''
 
'''Таким образом, получили поле <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> коэффициентов.<br />
 +
Порождающий многочлен Рида-Соломона,<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> - корни этого многочлена.<br>
 +
Например, построим порождающий многочлен кода Рида-Соломона с <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>.    ''(Возведение в степень и умножения выполнены над полем GF<sub>16</sub> )!''

Версия 18:31, 13 июня 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-разрядных чисел.

Коды Рида - Соломона

При построении кода Рида-Соломона задается пара чисел N,K, где N-Общее количество символов, а К- «полезное» количество символов, N-K символов задают избыточный код, предназначенный для восстановления ошибок. Такой код Рида-Соломона будет иметь «расстояние Хемминга» D=N-K+1. В соответствии с теорией кодирования, код, имеющий расстояние Хемминга D=2t+1, позволяет восстанавливать t ошибок. Таким образом, если нам необходимо восстановить t ошибок, то общее количество символов сообщения N=K+2t. Сообщения при кодировании Рида-Соломона представляются полиномами. Исходное сообщение представляется как коэффициенты полинома p(x) степени K-1, имеющего K коэффициентов.
Порождающий многочлен Рида-Соломона,g(x), строится следующий образом: g(x)=(x+2)(x+2^{2})..(x+2^{ D-1 } ) , 2 - примитивный член поля. Нетрудно понять, что 2^{1},2^{2},..,2^{D-1} - корни этого многочлена.
Например, построим порождающий многочлен кода Рида-Соломона с N=15,K=9, способного исправлять до 3 ошибок (15-9)/2=3: 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. (Возведение в степень и умножения выполнены над полем GF16 )!

Источник — «https://vscripts.ru/w/index.php?title=Участник:Nikz&oldid=893»