Полиномиальные коды(коды Рида-Маллера). Кодирование и декодирование

 

 

 

Для четвёртой  матрицы     

 

1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0
0	0	1	-1	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	1	-1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	-1	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	-1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0
0	0	0	0	0	0	0	0	0	0	1	-1	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	1	-1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	-1	-1

 

Перемножаем вектор y’ на каждую из матриц в результате получаем вектор (2,2,2,10,−2,−2,−2,6,−2,−2,−2,6,2,2,2,−6).

Его наибольшая по модулю компонента 10 -третья при нумерации с нуля. Следовательно, ближайшим кодовым словом будет третья строка двоичной матрицы Адамара (опять же при нумерации с 0), то есть вектор y = 1001100110011001. А исходное слово восстановится по компонентам так: x0 = 1(= y0) , x1 = 0(= y8 ⊕ 1), x2 = 0(= y4 ⊕ 1), x3 = 1(= y2 ⊕ 1), x4 = 1(= y1 ⊕ 1), то есть x = 10011.

 

 

 

 

 

 

 

 

 

 

 

§ 2 Алгоритм II декодирования кода Рида-Маллера .

 

Чтобы декодировать вектор y, полученный из вектора x по правилу , надо решить систему уравнений относительно x. Для G = Gr,m  эта система имеет вид

[N] = x[I(r)] G[I(r),N],(*)

где G[I(r),N]-порождающая матрица , x[I(r)] -вектор сообщения размерности k, [N]-закодированное сообщение x[I(r)], а I(r) = I0 ∪ I1 ∪ ··· ∪ Ir — множество индексов строк матрицы G и вектора x, N = {0,1,...,2m − 1} — множество индексов столбцов матрицы G.

Так как по определению I(r) = I(r − 1) ∪ Ir, то систему (*) можно представить в виде

y[N] = x[I(r − 1)] G[I(r − 1),N] + x[Ir] G[Ir,N].

При решении системы уравнений (*) вначале определяют компоненты x[Ir].  Определения каждой компоненты xi = x[i], i ∈ Ir, получается — как именно, будет показано ниже — набор из 2m−r независимых соотношений вида xi = βj, где каждое βj вычисляется как некоторая линейная функция от компонент вектора y. Если все значения βj, j ∈ 1 … 2m−r, равны между собой, то их общее значение, естественно, и будет искомым значением xi. Но из-за возможных ошибок вектор y может не быть кодовым словом и не удовлетворять (*), тогда среди βj могут быть и нули, и единицы. В связи с этим решение принимается по мажоритарному принципу: если единиц среди βj больше, чем нулей, то присваиваем xi =1, если наоборот, то xi =0. Будет обнаружено до 2m−r − 1 ошибок (сообщать об ошибке будем тогда, когда не все βj одинаковы) и исправлено до 2m−r−1 −1 ошибок (исправления корректны, когда число искажённых символов меньше, чем неискажённых). После того, как x[Ir] определены, их значения подставляют в решаемую систему уравнений (*) и приходят к системе y(r−1)[N] = x[I(r − 1)] G[I(r − 1),N],

где y(r−1)[N] = y[N] x[Ir] G[Ir,N]. Заметим, что G[Ir,N] = Gr(m). В этой системе тоже определяют старшие компоненты, теперь это x[Ir−1], и вновь понижают число уравнений и неизвестных системы. Наконец, приходят к равенству y(0) = x[0]G[0,N] = x0 G0(m), которое определяет x0 = x[0] по мажоритарному принципу.

 

 

Пример .  Задан код    с характеристиками  
=11         

Дано сообщение S=() , закодируем его. Для этого  перемножим вектор S на порождающую матрицу G.Где G имеет вид

	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1
	0	0	0	0	0	0	0	0	0	0	1	1	0	0	1	1
	0	0	0	0	0	0	0	0	0	1	0	1	0	1	0	1
	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	1
	0	0	0	0	0	1	0	1	0	0	0	0	0	1	0	1
	0	0	0	1	0	0	0	1	0	0	0	1	0	0	0	1

SG=

Получаем вектор)

Декодируем принятое слово = 1100 000101111000, зная, что был использован код RM(2,4). Заметим, что код с такими параметрами с гарантией исправит ошибку только в одном бите.

Получаем для компонент искомого вектора x наборы значений

с сообщения S

Для этого  выпишем вектор =( с индексами в двоичном счислении

 

 

)

 

 

 

 

…..

 

 

 

 

 

 

Для того чтобы найти  заменяем значения 3

Выписываем векторы

, )

 

 

 

 

 

Равенства для получаем аналогично

В  табличном виде эти равенства выглядят так

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

 

 

В результате получаем значения

• для a12 : 0,0,1,0;

• для a13 : 0,1,1,1;

• для a14 : 1,0,1,1;

• для a23 : 1,0,0,0;

• для a24 : 0,1,1,1;

• для a34 : 0,1,1,1.

По мажоритарному принципу полагаем a12 = 0, a13 = 1, a14 = 1, a23 = 0, a24 = 0, a34 = 1.

Строим для определения остальных компонент вектор

= +(011001) G2(4) =

= (1100 000101111000)+(0 1 1 0 0 1)

 

Получаем = (1101000000001111).

 Решаем систему SG = относительно S = (a0,a1,a2,a3,a4) с матрицей G = G1,4.

 Для выпишем вектор  

 

 

 

 

 

 

…..

 

 

 

 

 

 

 

 

 

 

 

Для того чтобы найти  выписываем вектор , переставляя значения 3  

)

 

 

 

 

 

 

 

 

 

 

Аналогично определяем

 

Ниже эти равенства приведены в табличном виде

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

 

 

    

      •   для a1 :  1,1,0, 1,1, 1,1, 1,

      •   для a2 :  1;1;0; 1;1; 1;1; 1,

      •   для a3 :  1;0;0; 0;0; 0;0; 0,

      •   для a4 :  0;1;0; 0;0; 0;0; 0.

      По мажоритарному  принципу  принимаем   a1  =  1, a 2  =  1, a 3  =  0, a 4  =  0.

Для   определения оставшейся компоненты вектора S вычисляем вектор

 

   =  +  (1    1   0   0) G  (4) =

    =  +  +  1    1   0   0    =

                                            

    = 1101 00000000 1111+0000 11110000 1111 = 1101 1111 11111111:

 

      Имеем  для а0 шестнадцать равенств

 

                                                      a0 =  [j ];  j   ∈0, … ,15;

                                                                     

 

 следовательно a0 =  1.

Таким образом

 

                    S = ( a0, a1, a 2, a3, a4, a 12, a13,a 14, a23, a24)  = 1110  0011 001

 

 

 

 

 

 

 

 

 
  

 

 

 

 

ЛИТЕРАТУРА

1. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

16

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

3. Питерсон У., Уэлдон Э. Коды, исправляющие  ошибки. М.: Мир, 1976.

4. Логачёв О. А., Сальников А. А., Ященко  В. В. Булевы функции в теории  кодирования и криптологии. М.: МЦНМО, 2004.

5. Кузнецов Ю. В., Шкарин С. А. Коды Рида–Маллера (обзор публикаций) //Математические вопросы кибернетики. 1996. Вып. 6. С. 5–50.

6. Сидельников В. М. Теория кодирования. М.: Физматлит, 2008.

7. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.