ОБ АЛГОРИТМАХ ДЕКОДИРОВАНИЯ ОБОБЩЕННЫХ КОДОВ РИДА — СОЛОМОНА НА СЛУЧАЙ ОШИБОК И СТИРАНИЙ. II

Полный текст

Введение

Пусть α = (α0, α1, . . . , αn−1), где αi — различные элементы поля F = GF (q), y = (y0, y1, . . . , yn−1) — ненулевые (не обязательно различные) элементы из F . Тогда обобщенный код Рида — Соломона, обозначаемый GRSk (α, y), состоит из всех кодовых векторов вида

Рацеев С.М., Череватенко О.И. Об алгоритмах декодирования обобщенных кодов Рида — Соломона...

8 Ratseev S.M., Cherevatenko O.I. On decoding algorithms for generalized Reed — Solomon codes with errors...

 

u = (y0b(α0), y1b(α1), . . . , yn−1b(αn−1)), (1) где b(x) — информационные многочлены над полем F степени не выше k − 1.

В данной статье приводятся алгоритмы декодирования для обобщенных кодов РС на случай ошибок и стираний: декодирование на основе алгоритма Гао [1] и на основе алгоритма Берлекэмпа — Месси [2]. В работе [3] в алгоритме декодирования на основе метода Гао компоненты искаженного кодового вектора, содержащие стирания, удалялись. В приводимом ниже алгоритме значения данных компонент будут заменяться нулевыми значениями. Достоинство данного метода заключается в том, что многочлен m(x) не нужно пересчитывать в зависимости от позиций стертых символов. Матрицу

−

 

Вандермонда V в новом алгоритме пересчитывать тоже не нужно. Это значит, что, учитывая работу [4], при {α0, α1, . . . , αn 1} = GF (q)\{0} представленный алгоритм будет иметь сложность O(n(log n)2). Так

как в работе [3] алгоритм декодирования на основе алгоритма Берлекэмпа — Месси в явном виде не приводился, то для полноты картины этот алгоритм приводится в данной работе. Более того, приведем обоснование корректности его использования для случая ошибок и стираний. При этом, в отличие от кодов РС, в обобщенных кодах РС одна из компонент вектора α может быть нулевой, это нужно учитывать для алгоритма декодирования на основе алгоритма Берлекэмпа — Месси.

Напомним, что актуальность данных алгоритмов состоит в том, что они применимы для декодирования кодов Гоппы [5–8], которые лежат в основе некоторых перспективных постквантовых криптосистем [9; 10].

 

1. Декодирование ОРС-кодов на основе алгоритма Гао на случай ошибок и стираний

Предположим, что в канале связи действуют ошибки и стирания. Пусть после передачи кодового вектора u ∈ GRSk (α, y) на приемной стороне получен вектор v, в котором t ошибок и s стираний, причем

1 t t+1 t+s 1 =

 

d ;;: 2t + s + 1. Заменим в векторе v стертые символы, например, нулями. Получим при этом вектор v. Пусть ошибки произошли на позициях i , . . . , i , а стирания — на позициях i , . . . , i . Пусть X

= αi1 , . . . Xt = αit — неизвестные локаторы ошибок, Xt+1 = αit+1 , . . . , Xt+s = αit+s — известные локаторы стираний.

Определим многочлен:

m(x) = (x − α0)(x − α1) . . . (x − αn−1).

Также определим многочлен локаторов ошибок σ(x) и многочлен локаторов стираний ν(x) следующим образом:

 

Обозначим

σ(x) = (x − X1) . . . (x − Xt), ν(x) = (x − Xt+1) . . . (x − Xt+s).

 

σ(x) = 1.

Если

 

 

vi = yib(αi). Если vi ̸= ui, то на позиции i произошла ошибка или стирание, поэтому

i

 

σ(α ) = 0. Из этого следует, что

 

σ(αi)y−1vi = σ(αi)b(αi), i = 0, 1, . . . , n − 1.

Обозначим

i

σ(x)b(x). Тогда

σ(αi)y−1vi = p(αi), i = 0, 1, . . . , n − 1.

i

Построим интерполяционный многочлен Лагранжа f (x) степени не выше n−1, проходящий через точки

(α0, y−1v0), (α1, y−1v1),. . . , (αn

1, y−1 vn

1):

0 1

− n−1 −

 

Тогда из равенств:

i

 

f (αi) = y−1vi, i = 0, 1, . . . , n − 1, deg f (x) ::: n − 1.

 

получаем сравнение:

p(αi), i = 0, 1, . . . , n − 1

 

p(x) (mod m(x)).

После обозначения f (x) = f (x)ν(x) данное сравнение приобретает вид

 

 

σ(x)f (x) ≡ p(x) (mod m(x)). (2)

Заметим, что

n − k − s

 

n + k + s

 

 

p(x) <

deg σ(x) :::

, deg

2

, (3)

2

Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 2. С. 7–15

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 2, pp. 7–15 9

 

так как

 

deg σ(x) ::: t :::

d − s − 1 =

2

n − k − s ,

2

 

 

deg p(x) = deg σ(x) + deg ν(x) + deg b(x) :::

:::

−

 

n − k − s + s + k 1 <

2

n + k + s

.

2

Алгоритм 1 (декодирование ОРС кодов методом Гао на случай ошибок и стираний). Вход: принятый вектор v.

Выход: исходный информационный вектор b, если в соответствующем кодовом векторе u произошло

s стираний и t ошибок при d ;;: 2t + s + 1.

1. Определяется t = [(d − s − 1)/2]. В векторе v все стирания заменяют нулями, получая тем

   позиций t+1 t+s

    

    

    

   самым вектор v. Вычисляются значения локаторов стираний Xt+1 = αit+1 , . . . , Xt+s = αit+s на основе известных стираний i , . . . , i . Также вычисляется многочлен локаторов стираний ν(x) =

   = (x − Xt+1) . . . (x − Xt+s).

2. Интерполяция. Строится интерполяционный многочлен f (x), для которого

   i

    

   f (αi) = y−1vi, i = 0, 1, . . . , n − 1.

   Вычисляется многочлен f (x) = f (x)ν(x).

3. Незаконченный обобщенный алгоритм Евклида. Пусть r−1(x) = m(x), r0(x) = f (x), v−1(x) = 0,

   v0(x) = 1. Производится последовательность действий обобщенного алгоритма Евклида:

   ri−2(x) = ri−1(x)qi−1(x) + ri(x), vi(x) = vi−2(x) − vi−1(x)qi−1(x), i ;;: 1,

   до тех пор, пока не достигается такого rj (x), для которого

   deg rj−1(x) ;;:

   n + k + s

   

   , deg rj (x) <

   2

   n + k + s

   

   . (4)

   2

   

   v (x)ν(x)

    

4. Деление. Информационный многочлен равен b(x) = rj (x) .

j

Теорема 1. Если в кодовом векторе произошло t ошибок и s стираний, причем d ;;: 2t + s +

+ 1, то алгоритм декодирования 1 всегда приводит к единственному решению, а именно к исходному информационному вектору b.

Доказательство. Пусть b(x) — исходный информационный многочлен, u(x) — кодовый многочлен, полученный с помощью формулы (1). Заметим, что для σ(x) и p(x) (истинные значения), которые

 

получены на основе исходных данных, сравнение (2) выполнено, причем b(x) = p(x)/(σ(x)ν(x)).

j j выполнено

 

Пусть с помощью алгоритма 1 получены значения r (x) и v (x), причем (4). Покажем, что rj (x) делится на vj (x)ν(x), причем rj (x)/(vj (x)ν(x)) = b(x). Домножив первое из приведенных ниже сравнений

 

 

σ(x)f (x) ≡ p(x) (mod m(x)),

vj (x)f (x) ≡ rj (x) (mod m(x))

на vj (x), а второе — на σ(x), получим

 

 

vj (x)p(x) ≡ σ(x)rj (x) (mod m(x)). (5) Оценим сверху степени многочленов из левой и правой частей данного сравнения. Учитывая неравенства

1. и (4), получаем

    

   Так как

   deg σ(x)rj (x) <

   n − k − s +

   2

   n + k + s

   = n.

   2

   n + k + s

    

   n − k − s

   deg vj (x) = deg m(x) − deg rj−1(x) ::: n − 2 = 2 ,

   то

   j

    

   deg v (x)p(x) <

    

   n − k − s +

   2

   n + k + s

   2

   = n.

   Следовательно, из сравнения (5) получаем равенство

   vj (x)

    

   p(x) = σ(x)rj (x).

   Так как

    

   p(x) = σ(x)ν(x)b(x), то rj (x) = vj (x)ν(x)b(x). D

   Пример 1. Рассмотрим обобщенный код Рида — Соломона над полем GF (7) с параметрами n = 7, k = 3, d = 5, α = (0, 1, 2, 3, 4, 5, 6), y = (2, 1, 3, 1, 4, 1, 5). Так как d = 5, то данный код может исправлять либо до двух ошибок, либо одну ошибку и до двух стираний, либо до четырех стираний.

   Рацеев С.М., Череватенко О.И. Об алгоритмах декодирования обобщенных кодов Рида — Соломона...

   10Ratseev S.M., Cherevatenko O.I. On decoding algorithms for generalized Reed — Solomon codes with errors...

    

   Так как вектор α содержит все элементы поля GF (7), то m(x) = x7 − x. Ниже приведена матрица Вандермонда V на основе вектора α, обратная к ней матрица V −1 и диагональная матрица Y на основе

   вектора y:

    

   		1	1	1	1	1	1	1			1	0	0	0	0	0	6	
   		0	1	2	3	4	5	6			0	6	6	6	6	6	6	
   	 	0	1	4	2	2	4	1	 	 	0	3	5	6	3	5	6	 
   V =  		0	1	1	6	1	6	6	 , V −1 =   		0	2	3	1	5	4	6	 , 
   	 	0	1	2	4	4	2	1	 	 	0	5	3	6	5	3	6	 
   	 	0	1	4	5	2	3	6	 	 	0	4	5	1	3	2	6	 
   		0	1	1	1	1	1	1			0	1	6	1	6	1	6

   Y = Diag(2, 1, 3, 1, 4, 1, 5).

   Заметим, что первые k = 3 строки матрицы V Y образуют порождающую матрицу G нашего кода.

   Рассмотрим случай одной ошибки и двух стираний. Пусть b = (3, 5, 2) — информационный вектор, который соответствует многочлену b(x) = 3 + 5x + 2x2. После кодирования вектора b получаем кодовый вектор (который можно получить несколькими способами):

   u = (y0b(0), y1b(1), . . . , y6b(6)) = bG =

   = (b0, b1, b2, 0, 0, 0, 0)V Y = (6, 3, 0, 1, 3, 1, 0).

   Пусть на приемном конце получен вектор

   v = (∗, 3, 5, 1, ∗, 1, 0),

   т. е. произошли два стирания и одна ошибка.

   Применим алгоритм декодирования 1.

   1. Полагаем s = 2, t = [(d − s − 1)/2] = 1. Заменив в векторе v стертые символы нулями, получаем

      v = (0, 3, 5, 1, 0, 1, 0). Также вычисляем многочлен локаторов стираний ν(x) = (x − 0)(x − 4) = 3x + x2.

   2. Интерполяция. Вычисляем коэффициенты многочлена f (x) = f

      + f x + . . . + f x6:

       

       

      (f0, f1, . . . , f6) = vY −1V −1

      0 1 6

      = (0, 1, 4, 2, 3, 2, 5),

      f (x) = x + 4x2 + 2x3 + 3x4 + 2x5 + 5x6.

      Вычисляем f (x) = f (x)ν(x) = 3x2 + 6x3 + 3x4 + 4x5 + 2x6 + 3x7 + 5x8.

   3. Незаконченный обобщенный алгоритм Евклида. Полагаем r−1(x) = m(x), r0(x) = f (x), v−1(x) = 0,

      v0(x) = 1. Применяем обобщенный алгоритм Евклида:

      r−1(x) = r0(x)q0(x) + r1(x), q0(x) = 0,

      r1(x) = 6x + x7,

      v1(x) = v−1(x) − v0(x)q0(x) = 0,

      r0(x) = r1(x)q1(x) + r2(x), q1(x) = 3 + 5x,

      r2(x) = 3x + x2 + 6x3 + 3x4 + 4x5 + 2x6,

      v2(x) = v0(x) − v1(x)q1(x) = 1,

      r1(x) = r2(x)q2(x) + r3(x), q2(x) = 6 + 4x,

      r3(x) = 2x + 3x2 + 2x3 + 6x5,

      v3(x) = v1(x) − v2(x)q2(x) = 1 + 3x.

      После третьего шага процесс останавливается, так как deg r2(x) = 6, deg r3(x) = 5, причем (n+k +s)/2 =

      = 6.

   4. Деление. Исходный информационный многочлен равен

   r3(x)

   b(x) =

   v3(x)ν(x)

   = 3 + 5x + 2x2.

    

   2. Декодирование ОРС-кодов на основе алгоритма Берлекэмпа — Месси

   Пусть v — полученный на приемной стороне вектор, в котором могут быть ошибки и стирания. Пусть t — максимальное число возможных ошибок при фиксированном числе стираний s в векторе

   v, d ;;: 2t + s + 1, t = [(d − s − 1)/2], m — реальное число ошибок, m ::: t. Так как позиции стертых

   Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 2. С. 7–15

   Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 2, pp. 7–15 11

    

   1 m стирания m+1 m+s

    

   символов известны, то заменим эти символы в векторе v, например на нули, и будем обращаться с полученным вектором v как с вектором, содержащим только ошибки. Пусть ошибки произошли на позициях i , . . . , i , а — на позициях i , . . . , i . При этом известны только позиции im+1, . . . , im+s. После того как на данные позиции поместили нули, с какими-то позициями могли угадать (если в кодовом векторе там действительно стояли нули). Поэтому v = u + e, где e — вектор ошибок веса не более m + s.

   Вычисляя синдромный вектор, получаем:

   vHT = eHT = ( . . . , ei , . . . , ei

   , . . . ) ×

   S =

   1 m+s

    

   T

    1 1 . . . 1

     w0 0 . . . 0 

   × 

   α0 α1 . . . αn−1

     0 w1 . . . 0

    =

   

    

    . . . . . . . . . . . .

    

    

   

    

     . . . . . . . . . . . . 

   αn−k−1

   n−k−1

   n−k−1

   0 α1 . . . αn−1

   0 0 . . . wn−1

   T

    ei1 wi1 + . . . + eim+s wim+s 

    ei1 wi1 αi1 + . . . + eim+s wim+s αim+s 

   =

    

   .

    

    . . . 

    n−k−1

   n−k−1 

   ei1 wi1 αi1 + . . . + eim+s wim+s αim+s

   Z = Y w , j = 1, . . . , m + s. Тогда

    

   Пусть X1 = αi1 , . . . Xm = αim — неизвестные локаторы ошибок, Xm+1 = αim+1 , . . . , Xm+s = αim+s — известные локаторы стираний, Y1 = ei1 , . . . , Ym+s = eim+s — значения ошибок в векторе v. Обозначим

   j j ij

   S0 = Z1 + . . . + Zm + Zm+1 + . . . + Zm+s,

   S1 = Z1X1 + . . . + ZmXm + Zm+1Xm+1 + . . . + Zm+sZm+s,

   . . .

   2t+s−1

   2t+s−1

   2t+s−1

   2t+s−1

   S2t+s−1 = Z1X1 + . . . + ZmXm + Zm+1Xm+1 + . . . + Zm+sXm+s .

   Запишем синдромный многочлен в виде

   2t+s−1

   2t+s−1 m+s

    m+s

   (2t+s−1 )

   S(x) =

    Zj Xi xi = Zj

    

   ∑ Sixi =

   ∑ ∑ ∑

   j

   ∑ (Xjx)i =

   i=0

    

   m+s

   i=0

   1 − (X x)2t+s

   j=1

    

   m+s Z

   j=1

   i=0

    

   m+s Zj X2t+s

    

   Полагая

   

   = ∑ Zj

   j=1

   j

   1 − Xjx

    

   m+s

   = ∑

   j=1

   j

   

   1 − Xjx

    

   m+s

   — x2t+s ∑

   j=1

   j .

   

   1 − Xjx

   i

    

   σ(x) = ∏ (1 − Xix) = ∑ x ,

   σ0 = 1,

    

   i=1

   σi

   i=0

   m+s

   i

    

   ω(x) = ∑ Z ∏

    

   (1 − Xjx),

   m+s

   i

    

   Φ (x) = ∑ ZiX2t+s

   ∏ (1 − Xjx),

   i=1

   1 j m+s, j̸=i

   i=1

   1 j m+s, j̸=i

   после приведения всех дробей к общему знаменателю получим

    

   Тогда

   ω(x)

   

   S(x) =

    

   − 2t+s

    

   Φ(x)

   

   x .

   σ(x)

   ω(x) (mod x

   2t+s).

   известных

    

   Заметим, что σ(x) = σ(x)ν(x), где σ(x) — это многочлен неизвестных локаторов ошибок, ν(x) — многочлен локаторов стираний:

   m s

    

    

   σ(x) = ∏(1 − Xix) ∏(1 − Xm+ix) = σ(x)ν(x).

   i=1

    

   Введем в рассмотрение многочлен Тогда ключевое уравнение примет вид

   i=1

   S (x) = S(x)ν(x) — модифицированный синдромный многочлен.

    

   ω(x) (mod x2t+s), (6)

    

   где

   σ(x)S (x) ≡

    

    

   deg σ(x) ::: m, deg ω(x) ::: m + s − 1, σ(0) = 1. (7)

   Рацеев С.М., Череватенко О.И. Об алгоритмах декодирования обобщенных кодов Рида — Соломона...

   12Ratseev S.M., Cherevatenko O.I. On decoding algorithms for generalized Reed — Solomon codes with errors...

    

   Пусть

    

   S (x) = S 0 + S 1x + . . . + S 2t+2s−1x

   2t+s−1

   2t+2s−1 =

   s

   = S(x)ν(x) = (S0 + S1x + . . . + S2t+s−1x

   )(ν0 + ν1x + . . . + νsx ),

   где ν0 = 1, νi = (−1)iσi(Xm+1, . . . , Xm+s) — элементарный симметрический многочлен от

   Xm+1, . . . , Xm+s, i = 1, . . . , s.

    

    

   Так как в сравнении (6) deg ω(x) ::: m + s − 1, deg S (x) ::: 2t + 2s − 1, deg σ(x) ::: m, то необходимым

   условием выполнения данного сравнения является тот факт, что коэффициенты многочлена σ(x)S (x)

   при степенях j = m + s, m + s + 1, . . . , 2t + s− 1 равны нулю. Поэтому получаем такую систему линейных

   уравнений:

    σ0S s+m + σ1S s+m−1 + . . . + σmS s = 0,

    σ0S s+m+1 + σ1S s+m + . . . + σmS s+1 = 0,

   . . .

   − − − −

    

    σ0S s+2t 1 + σ1S s+2t 2 + . . . + σmS s+2t m 1 = 0.

   Так как σ0 = 1, то данная система в матричной форме примет такой вид:

    S s+m−1

   S s+m−2 . . .

   S s

     σ1 

    −S s+m 

    S s+m

   S s+m−1 . . .

   S s+1

     σ2

    =  −S s+m+1

    . (8)

   

    

    . . . . . . . . . . . .

    

    

   

    

   

    

     . . .  

   

    

   . . . 

   S s+2t−2

   S s+2t−3 . . .

   S s+2t−m−1 σm

   −S s+2t−1

   Для нахождения решения системы (8) применим следующий алгоритм.

   Алгоритм 2 (алгоритм Берлекэмпа — Месси)

   Вход: последовательность a1, . . . , an над некоторым полем. Выход: LFSR (L, f (x)) минимальной длины L, для которого

   L

   −aj = ∑ fiaj−i, j = L + 1, L + 2, . . . , n.

   i=1

   1. Определить r := 0, f (x) := 1, b(x) := 1, L := 0. 2. Цикл r := 1, . . . , n

   L

   1. Определить ∆ := ar + ∑ fiar−i.

   i=1

   2.2. Если ∆ = 0, то b(x) := x · b(x).

   2.3. Если ∆ ̸= 0 :

   1. Если 2L < r:

      buf (x) := f (x) − ∆ · x · b(x),

      b(x) := ∆−1 · f (x),

      f (x) := buf (x), L := r − L.

   2. Иначе (т. е. выполнено 2L ;;: r): f (x) := f (x) − ∆ · x · b(x),

   b(x) := x · b(x).

   Теорема 2. Пусть d ;;: 2t + s + 1. Если на вход алгоритма 2 подать последовательность S s, S s+1,. . . ,

   S s+2t−1, то на выходе алгоритма будет верное значение многочлена локаторов ошибок σ(x).

   лок

    

   Доказательство. Пусть σ(x) — многочлен, полученный после применения алгоритма 2. Так как

   коэффициенты многочлена аторов ошибок σ(x) являются решением системы (8), то по свойству алгоритма Берлекэмпа — Месси L ::: m. Удалив в системе (8) 2t − 2m последних уравнений, получим

   D

    

   новую систему с квадратной матрицей системы порядка m. Из теоремы 5 работы [3] следует, что данная матрица невырождена, поэтому полученная новая система имеет единственное решение. Это значит, что σ(x) = σ(x) и L = m.

    

   Алгоритм 3 (декодирование ОРС-кодов на основе алгоритма Берлекэмпа — Месси на случай ошибок и стираний).

   Вход: принятый вектор v, в котором s стираний и не более t ошибок. Выход: исходный кодовый вектор u, если d ;;: 2t + s + 1.

   1. Определяется t = [(d−s− 1)/2]. В векторе v все стирания заменяются нулями, получая тем самым

      вектор

       

      v и процедура окончена.

      vHT . Если они все равны нулю,

      то возвращается вектор

      Вестник Самарского университета. Естественнонаучная серия. 2021. Том 27, № 2. С. 7–15

      Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 2, pp. 7–15 13

       

      Вычисляются значения локаторов стираний Xt+1 = αit+1 , . . . , Xt+s = αit+s на основе известных позиций стираний it+1, . . . , it+s. Вычисляются коэффициенты модифицированного синдромного многочлена S (x).

   2. На вход алгоритма 2 подается последовательность алгоритма получается многочлен σ(x). Пусть l = deg σ(x).

      S s,

      S s+1,. . . ,

      S s+2t−1. На выходе данного

   3. Если l > 0, то отыскиваются l корней многочлена σ(x) последовательной подстановкой в него ненулевых элементов поля F . При этом локаторы ошибок — это величины, обратные корням многочлена σ(x).

   4. При вычислении значений ошибок выполняется один из следующих пунктов.

      1. Если среди локаторов стираний Xt+1, . . . , Xt+s имеется нулевое значение (в противном случае переходим в пункт 4.2), скажем, Xp = 0, то пусть

         M = {1, . . . , l} ∪ {t + 1, . . . , t + s}\{p}.

         Находятся Zj , j ∈ M , например, с помощью алгоритма Форни для обобщенных кодов РС:

         j

          

         ω(X−1)

         

         Zj = ∏

         −1 , j ∈ M. (9)

         i∈M\{j}(1 − XiXj )

          

         v из ij -го символа, Xj = αij ,

         После этого находятся значения ошибок Yj = Zj/wij , j ∈ M . У вектора

          

          

         вычитается значение Yj , j ∈ M . При этом получается вектор u. Пусть для некоторого i выполнено

         αi = 0. Вычисляется значение Zp, равное скалярному произведению вектора u на первую строку

         p p i -го p

          

         матрицы H. Вычисляется значение ошибки Y = Z /w . Осталось в векторе u из i символа вычесть Y .

          

         j ij j

          

          

          

      2. Если условие 4.1 не выполнено, то пусть M = {1, . . . , l} ∪ {t + 1, . . . , t + s}. По формуле (9) находятся значения Zj , затем значения ошибок Yj = Zj/wij , j ∈ M . У вектора v из ij -го символа, X = α , вычитается значение Y , j ∈ M . При этом получается вектор u.

   0

    

   Если αi = 0 для некоторого i и deg σ(x) < L, то вычисляется значение Z0, равное скалярному произведению вектора u на первую строку матрицы H, а затем вычисляется значение ошибки Y =

    

    

    

   = Z0/wi. Осталось в векторе u из i-го символа вычесть Y0.

   ∗

    

   Пример 2. Продолжим рассматривать пример 3 работы [3]. Пусть на приемной стороне получен тот же вектор v = (1, 3, 6, 10, 9, 1, 10, , 8). После замены стертых символов нулями получаем вектор v =

    

   = (1, 3, 6, 10, 9, 1, 10, 0, 8). Компоненты синдромного вектора

   S равны:

   S = (4, 10, 5, 9, 3, 8). Определяем

   s = 1, t = [(d − s − 1)/2] = 2. Поэтому на вход алгоритма 2 передаем значения

   S 4 = 3. Получаем

   S 1 = 10,

   S 2 = 5,

   S 3 = 9,

    

   r	∆	f (x)	b(x)	L
   0		1	1	0
   1	10	1 + x	10	1
   2	4	1 + 5x	10x	1
   3	1	1 + 5x + x2	1 + 5x	2
   4	9	1 + 7x	x + 5x2	2

   Следовательно, σ(x) = 1 + 7x.

    

   Заключение

   В данной статье приводится еще одна модификация алгоритма Гао и алгоритма Берлекэмпа — Месси. Первый из данных алгоритмов относится к алгоритмам бессиндромного декодирования, второй — к алгоритмам синдромного декодирования. Актуальность данных алгоритмов состоит в том, что они применимы для декодирования кодов Гоппы, которые лежат в основе некоторых перспективных постквантовых криптосистем.

Об авторах

С. М. Рацеев

Ульяновский государственный университет

Автор, ответственный за переписку.
Email: ratseevsm@mail.ru
ORCID iD: 0000-0003-4995-9418

доктор физико-математических наук, доцент, профессор кафедры информационной безопасности и теории управления

432017, Российская Федерация, г. Ульяновск, ул. Льва Толстого, 42.

О. И. Череватенко

Ульяновский государственный педагогический университет имени И.Н. Ульянова

Email: choi2008@mail.ru
ORCID iD: 0000-0003-3931-9425

кандидат физико-математических наук, доцент, доцент кафедры высшей математики

Россия, 432071, Российская Федерация, г. Ульяновск, площадь Ленина, 4/5.

Список литературы

Дополнительные файлы