Пример коррекции ошибки с помощью кодов Рида-Соломона

Пример коррекции ошибки с помощью кодов Рида-Соломона

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

В данной статье разбирается пример работы алгоритма коррекции ошибки для 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-разрядных чисел.

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

При построении кода Рида-Соломона задается пара чисел 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$. (Возведение в степень и умножения выполнены над полем GF₁₆ )!

Кодирование Рида-Соломона

Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается: Сначала полином сдвигается на $N-K$ коэффициентов влево
$p'(x)=p(x)x^{N-K}$ ,а потом вычисляется остаток от деления на порождающий полином и прибавляется к $p'(x)$: $C(x)=p'(x)+p'(x)mod g(x)$.
Для систематического кого очевидно, что $K$ старших коэффициентов полученного кода $C(x)$ содержат исходное сообщение. Это удобно при декодировании. Закодированное сообщение $C(x)$ обладает очень важным свойством: оно без остатка делится на порождающий многочлен $g(x)$.
Докажем это свойство:
Пусь $r(x)$-остаток от деления $p'(x)$ на $g(x)$.
Тогда,
$p'(x)=g(x)u(x)+r(x)$
Итак,
$r(x)=p'(x)mod g(x)$
Тогда
$C(x)=p'(x)+p'(x)mod g(x)=g(x)u(x)+r(x)+r(x)$
Вспомним, что в арифметике поля Галуа сложения являются одновременно и вычитанием, тогда $r(x)+r(x)=0$!Следовательно $C(x)$ делится на $g(x)$ без остатка.
Таким образом,
$C(x) mod g(x)=0$
В случае, если закодированное сообщение будет изменено, то это равенство будет нарушенным, не считая случая, когда ошибка окажется кратной $g(x)$. Факт искажения можно рассматривать как прибавление к $C(x)$ некоторого полинома ошибки $E(x)$.
Пример:
Рассмотрим кодирование информации. Пусть наше сообщение такое: $12, 10, 12, 7$
Полином сообщения получается такой: $I(x)=12x^{3}+10x^{2}+12x+7$
Умножаем на $x^{2}$,получаем:
$I'(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}$
Делим на $g(x)$ и получаем остаток: $r(x)= x + 4$
В итоге получается полином закодированного сообщения:
$C(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4$

Декодирование Рида-Соломона

Первым шагом необходимо выполнить деление полинома на порождающий полином $g(x)$. Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.
Разделим закодированное сообщение на образующий полином: $\frac{12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4}{x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12}=0$,
в этом можно убедиться, самостоятельно проделав операцию деления, согласно арифметике поля GF_{16}</math>
Внесем ошибку в закодированное сообщение, полином ошибки $E(x)=14x^{4}$
Разделим получившееся закодированное сообщение $C'(x)$ на $g(x): r(x) = 14x + 14$
В случае присутствия ошибки выполняем следующие действия:
Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).
Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при $x^{4}$, то локатор этой ошибки равен $a^{4}$, если искажён коэффициент при $x^{7}$ то локатор ошибки будет равен $a^{7}$ и т.п. (а – примитивный член, т.е. в нашем случае a=2). Многочлен локаторов $L(x)$ – это многочлен, корни которого обратны локаторам ошибок. Таким образом, многочлен $L(x)$ должен иметь вид
$L(x)=(1+xX_1 )(1+xX_2)..(1+xX_i)$
где $X_1,X_2,..,X_i$ - локаторы ошибок
Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.
Для определения этого полинома сначала получают вспомогательный полином $S(x)$, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен $r(x) = C(x) mod g(x)$: $S_i=e(a^{i})$
Для нашего примера:
$S(1) = 1;$
$S(2) = 3;$
Между $L(x)$ и $S(x)$ существует соотношение
$L(x)S(x)=W(x)modx^{N-K}$
$W(x)$ называется многочленом ошибок. Степень многочлена $W(x)$ не может превышать $t-1$, где $t$ – количество ошибок, то есть в максимальном случае $(N-K)/2-1$
С учётом этого обстоятельства, а также учитывая, что свободный член $L(x): L_0=1$ (ведь $L(x)=(1+xX_1 )(1+xX_2 )..(1+xX_i) )$ можно составить систему линейных уравнений. $W(x)=$
$L_0 S_0$
$(L_0 S_1+L_1 S_0 )X+$
$(L_0 S_2+L_1 S_1+L_2 S_0 ) X^2+$
$(L_0 S_3+L_1 S_2+L_2 S_1+L_3 S_0 ) X^3+$
$...$
$(L_0 S_{N-K-1}+L_1 S_{N-K-2}..L_{(N-K)/2} S_{(N-K)/2-1}X^{N-K-1}$
Пусть $t = (N-K)/2$
Коэффициенты при степенях от 0 до t – 1 не равны нулю, при старших степенях должны быть нулевыми.
$L_0 S_t+L_1 S_{t-1}+L_2 S_{t-2}+L_3 S_{t-3}...L_t S_0 = 0$
$L_0 S_{t+1}+L_1 S_t+L_2 S_{t-1}+L_3 S_{t-2}...L_t S_1 = 0$
$L_0 S_{t+2}+L_1 S_{t+1}+L_2 S_t+L_3 S_{t-1}...L_t S_2 = 0$
$\dots$
$L_0 S_{2t-1}+L_1 S_{2t-2}+L_2 S_{2t-3}+L_3 S_{2t-4}...L_t S_t = 0$
Коэффициент $L_0$ известен, остальные необходимо найти, следовательно требуется составить t уравнений.
$L_1 S_{t-1}+L_2 S_{t-2}+L_3 S_{t-3}...L_t S_0 = S_t$
$L_1 S_t+L_2 S_{t-1}+L_3 S_{t-2}...L_t S_1 = S_{t+1}$
$L_1 S_{t+1}+L_2 S_t+L_3 S_{t-1}...L_t S_2 = S_{t+2}$
$...$
$L_1 S_{2t-2}+L_2 S_{2t-3}+L_3 S_{2t-4}...L_t S_t = S_{2t-1}$
В матричном виде:

$M= \quad\left\|\begin{array}{ccccc} S_{t-1} & S_{t-2} & S_{t-3} & \cdots & S_0\\ S_{t} & S_{t-1} & S_{t-2} & \cdots & S_1\\ S_{t+1} & S_{t} & S_{t-1} & \cdots & S_2\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ S_{2t-2} & S_{2t-3} & S_{2t-4} & \cdots & S_t\\ \end{array}\right\|$

$V=\quad\left\|\begin{array}{c} S_{t} \\ S_{t+1} \\ S_{t+2} \\ \cdots \\ S_{2t-1} \\ \end{array}\right\|$

$L=\quad\left\|\begin{array}{c} L_{1} \\ L_{2} \\ L_{3} \\ \cdots \\ L_{t} \\ \end{array}\right\|$

$ML = V, \Rightarrow M^{-1}V$ Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид:
$M = S_1$ , а вектор $V = S_2;$ $L(1) = S(2) / S(1) = 3 / 1 = 3$
Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V. Обратная матрица получается так же, как и в обычной математике, например Жордановым методом. После того, как полином $L(x)$ найден, следует найти его корни – они будут обратны к локаторам ошибок.
Для нашего примера многочлен локаторов $L(x) =1 + 3x$ имеет корень \frac{1}{3}, а обратный к нему $3 = 2^{4}$, а значит позиция ошибки равна $x^{4}$
После нахождения позиции ошибки,займемся нахождением значением ошибки:
Воспользуемся определением синдромной функции:

$S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n$,
$S(2) = r(\alpha) = e_1 L_1^{2} + e_2 L_2^{2} + ... + e_n L_n^{2}$,
$...$
$S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}$,

где $e_1,e_2,..,e_n -$значение ошибки. $L_1,L_2,..,L_n -$позиция ошибки.

Для нашего кода $RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1 = 1 / 3 = 2^{0} / 2^{4} = 2^{11} = 14$ - позиция ошибки.
Таким образом сформируем многочлен вычисленной ошибки $E'(x) = 14x^{4}$, который совпадает с заданным $E(x)$