ON DECODING ALGORITHMS FOR GENERALIZED REED — SOLOMON CODES WITH ERRORS AND ERASURES. II

Full Text

Введение

Пусть α = (α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.

    

   Заключение

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

About the authors

S. M. Ratseev

Ulyanovsk State University

Author for correspondence.
Email: ratseevsm@mail.ru
ORCID iD: 0000-0003-4995-9418

Doctor of Physical and Mathematical Sciences, associate professor, Department of Information Security and Control Theory

42, Lev Tolstoy Street, Ulyanovsk, 432017, Russian Federation.

O. I. Cherevatenko

Ulyanovsk State University of Education

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

Candidate of Physical and Mathematical Sciences, associate professor, Department of Higher Mathematics

Russian Federation, 4/5, Lenin Square, Ulyanovsk, 432063, Russian Federation.

References

Supplementary files