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

Full Text

• Введение

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

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

  GRSk (α, y) равно d = n − k + 1. Если n = q − 1, вектор y состоит из единиц и αi = αi, i = 0, 1, . . . , n − 1,

  где α — примитивный элемент поля F , то в этом случае получаем код Рида — Соломона (РС).

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

  18Ratseev S.M., Cherevatenko O.I. Decoding algorithms for generalized Reed-Solomon codes

   

  Заметим, что, в отличие от кодов РС, в обобщенных кодах РС одна из компонент вектора α может быть нулевой, что нужно учитывать для некоторых алгоритмов декодирования.

  Нам понадобится вид проверочной матрицы кода GRSk (α, y) (см., напр., [1]).

  Теорема 1. Код, дуальный GRSk (α, y)-коду, является GRSn−k (α, w)-кодом для некоторого векто- ра w, причем в качестве вектора w можно взять w = (w0, w1, . . . , wn−1), где

  1

  

  i

   

  wi = y ∏

  j̸=i(αi − αj )

  , i = 0, 1, . . . , n − 1.

   

  Из данной теоремы следует, что проверочная матрица H кода GRSk (α, y) равна порождающей мат- рице кода GRSn−k (α, w):

   1 1 . . . 1

    w0 0 . . . 0 

  H = 

  α0 α1 . . . αn−1

    0 w1 . . . 0

   . (2)

  

   

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

   

   

  

   

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

  αn−k−1

  n−k−1

  n−k−1

  0 α1 . . . αn−1

  Матрица H содержит n − k = d − 1 строк и n столбцов.

  0 0 . . . wn−1

  Для декодирования кодов Рида — Соломона на случай ошибок хорошо известны следующие алго-

  ритмы [1–3]: алгоритм Гао, алгоритм Сугиямы, алгоритм Берлекэмпа–Месси, алгоритм Питерсона — Горенстейна — Цирлера. В дополнение к этим алгоритмам можно добавить алгоритм поиска ошибок Форни. Для обобщенных кодов Рида — Соломона и кодов Гоппы подобные алгоритмы рассматривались в работах [4–6].

  Для декодирования кодов Гоппы хорошо известен алгоритм Паттерсона [7]. Этот алгоритм предла- гается для использования в криптосистеме Мак-Элиса [8; 9]. Но алгоритм Паттерсона применим только для двоичных кодов Гоппы и не применим для случая, когда в канале связи действуют ошибки и сти- рания. В работе [10] приводится алгоритм списочного декодирования двоичных кодов Гоппы. При этом такой вариант не применим для криптосистемы Мак-Элиса, так как для нее нужны алгоритмы одно- значного декодирования.

  В данной статье приводятся алгоритмы декодирования для обобщенных кодов РС на случай ошибок и стираний: декодирование на основе алгоритма Гао, на основе алгоритма Сугиямы, на основе алгорит- ма Берлекэмпа–Месси (алгоритма Питерсона — Горенстейна — Цирлера). Понятно, что любой из этих алгоритмов применим и для случая канала связи только с ошибками. Актуальность таких алгоритмов декодирования состоит в том, что все алгоритмы декодирования для обобщенных кодов РС можно при- менять для декодирования кодов Гоппы, при этом именно на основе кодов Гоппы строятся некоторые перспективные постквантовые криптосистемы [11].

   

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

  Предположим, что в канале связи действуют ошибки и стирания. Пусть кодовый вектор u ∈

  ∈ GRSk (α, y) получен на основе информационного вектора b с помощью правила (1), а после переда-

  чи вектора u на приемной стороне получен вектор v, в котором t ошибок и s стираний. Пусть S —

  k

   

  позиции стертых символов в векторе v. На основе векторов v, α, y составим соответствующие векто- ры v, β, z путем удаления всех компонент с номерами из множества S. Рассмотрим код GRS (β, z)

  �

  �

   

  длины n = n − s и размерности �k = k, который получается из кода GRSk (α, y) путем выкалывания ком-

  с k

   

  понент номерами из множества S. Для кодового расстояния кода GRS (β, z) выполнено равенство

  �

   

  d� = n − �k + 1 = n − s − k + 1. Если d � 2t + s + 1, то для кодового расстояния d� кода GRSk (β, z) выполнено

  неравенство

  �

   

  d� � 2t + 1. Тогда вектор v, в котором только ошибки, можно декодировать.

  Для описания алгоритма из данного параграфа будем следовать работам [2; 12]. На основе компонент вектора β определим многочлен:

  n

   

  m(x) = (x − β0)(x − β1) . . . (x − β −1).

  Пусть X1 = βi1 , . . . , Xt = βit — локаторы ошибок. В данном алгоритме многочлен локаторов ошибок запишем в виде:

  σ(x) = (x − X1) . . . (x − Xt).

   

  u — вектор, полученный из u путем

  Если ошибок не было, то будем полагать, что σ(x) = 1. Пусть �

  u ∈ GRSk (β, z). Так как n−k +1 = d � 2t+s+1,

   

  выкалывания компонент с номерами из S. Понятно, что �

  Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 3. С. 17–29

  Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29 19

  �

   

  то n − s � 2t + k � k, поэтому вектор u получен с помощью кодирования информационного многочлена

  k−1

  b(x) = b0 + b1x + . . . + bk−1x

  (на основе которого получен вектор u) с помощью правила:

  u = (z0b(β0), z1b(β1), . . . , zn−1b(βn−1)).

  �

   

  Из этого следует, что

  �

   

  vi ̸= ui, то на позиции i произошла ошибка, поэтому σ(βi) = 0.

  σ(βi)z−1vi = σ(βi)b(βi), i = 0, 1, . . . , n − 1.

  i � �

  Обозначим p(x) = σ(x)b(x). Тогда:

  σ(βi)z−1vi = p(βi), i = 0, 1, . . . , n − 1.

  i � �

  n−1, проходящий через точки

  Построим интерполяционный многочлен Лагранжа f (x) степени не выше �

  (β0, z−1v0), (β1, z−1v1),. . . , (βn

  1, z−1 vn

  1):

  0 � 1 �

  n

   

  − −1 � −

  f (βi) = z−1vi, i = 0, 1, . . . , n − 1, deg f (x) ::: n − 1.

   

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

  i � �

  �

   

  n − 1,

   

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

  σ(βi)f (βi) = p(βi), i = 0, 1, . . . , �

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

   

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

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

  s стираний и не более t ошибок при d � 2t + s + 1.

  1. Пусть S — позиции стертых символов в векторе v. На основе векторов v, α, y составить соот- ветствующие векторы v, β, z путем удаления всех компонент с номерами из множества S. После этого

     рассматриваетс

      

     вектор v � я как вектор, в котором только ошибки и который соответствует некоторому

     �

     �

      

     кодовому вектору кода GRSk (β, z) длины n = n − s и размерности �k = k. Определяется многочлен:

     n−1

      

      

     m(x) = ∏(x − βi).

     i=0

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

     f (βi) = z−1vi, i = 0, 1, . . . , n − 1.

     i � �

  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), для которого:

     

     j−1 � j

      

     deg r (x) � n + �k , deg r (x) <

     2

     �

      

     n + k

     

     � .

     2

     

     v (x)

      

  4. Деление. Информационный многочлен кода GRSk (β, z), соответствующий кодовому вектору u, ра- вен b(x) = rj (x) .

  j

   

  Теорема 2. Если в кодовом векторе произошло t ошибок и s стираний, причем d � 2t + s + 1, то алгоритм декодирования 1 всегда приводит к единственному решению, а именно к исходному инфор- мационному вектору b.

  v, в котором

   

  Доказательство. После применения к вектору v шага 1 алгоритма 1 получим вектор �

  v с помощью шагов 2-4 алгоритма 1 следует из

   

  только ошибки. Однозначность декодирования вектора �

  теоремы 1 работы [5]. D

  Пример 1. Рассмотрим обобщенный код РС над полем GF (11) с параметрами n = 9, k = 4, d = 6,

  α = (0, 1, . . . , 8), y = (2, 1, 3, 1, 4, 1, 5, 1, 6).

  Данный [9, 4, 6]-код GRS4(α, y) может исправлять до двух ошибок и одно стирание, либо одну ошибку и до трех стираний, либо до пяти стираний. Рассмотрим случай двух ошибок и одного стирания.

  Пусть b = (4, 2, 1, 7) — информационный вектор, который соответствует многочлену b(x) = 4 + 2x +

  + x2 + 7x3. После кодирования вектора b получаем кодовый вектор:

  u = (y0b(0), y1b(1), . . . , y8b(8)) = (8, 3, 6, 10, 1, 1, 10, 4, 8).

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

  20Ratseev S.M., Cherevatenko O.I. Decoding algorithms for generalized Reed-Solomon codes

   

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

  v = (1, 3, 6, 10, 9, 1, 10, ∗, 8),

  т. е. произошли две ошибки на 0-й и 4-й позициях (нумеруя с нуля) и одно стирание на 7-й позиции.

  1. Удалив в векторе v стертые символы, получим новый вектор:

     v = (1, 3, 6, 10, 9, 1, 10, 8),

     �

     в котором только две ошибки. Пусть β и z — векторы длины 8, которые получаются соответственно из векторов α и y путем удаления 7-й компоненты:

     β = (0, 1, 2, 3, 4, 5, 6, 8), z = (2, 1, 3, 1, 4, 1, 5, 6).

     Множество S позиций стертых символов равно S = {7}. Составляем многочлен m(x): m(x) = x(x − 1)(x − 2)(x − 3)(x − 4)(x − 5)(x − 6)(x − 8) =

     = 4x + 4x2 + 6x3 + 2x4 + 10x5 + 2x6 + 4x7 + x8.

     Ниже приведена матрица Вандермонда V на основе вектора β, обратная к ней матрица V −1 и диаго- нальная матрица Z на основе вектора z:

      

     	1	1	1	1	1	1	1	1			1	1	7	6	8	6	1	3	
     	0	1	2	3	4	5	6	8			0	10	9	2	7	10	4	3	
      	0	1	4	9	5	3	3	9	 	 	0	1	7	5	3	4	8	5	 
      	0	1	5	4	3	9	9	4	 	 	0	9	3	6	6	2	5	2	 
      	0	1	10	1	1	1	10	10	 	 	0	1	10	9	10	10	8	7	 
      	0	1	9	3	4	5	5	3	 	 	0	3	9	6	8	7	10	1	 
     	0	1	7	9	5	3	8	2			0	1	8	8	7	2	9	9

      

      0 1 8 5 9 4 7 6 

      0 7 2 2 6 3 10 3 

     V = 

      , V −1 =   ,

      

     Z = Diag(2, 1, 3, 1, 4, 1, 5, 6).

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

     �

      

     (f0, f1, . . . , f7) = vZ−1V −1

     = (6, 0, 10, 9, 6, 5, 1, 10),

     f (x) = 6 + 10x2 + 9x3 + 6x4 + 5x5 + x6 + 10x7.

  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) = 6 + 10x,

     r1(x) = 8 + 10x + 10x2 + 6x3 + 8x4 + 8x5 + x6,

     v1(x) = v−1(x) − q0(x)v0(x) = 5 + x,

     r0(x) = r1(x)q1(x) + r2(x), q1(x) = 9 + 10x,

     r2(x) = 6x + 7x2 + 9x3 + 6x4 + 7x5,

     v2(x) = v0(x) − q1(x)v1(x) = 7x + x2.

     �

      

     Так как (n + �k)/2 = 6, deg r1(x) = 6, deg r2(x) = 5, то после второго шага алгоритма Евклида останав- ливаемся.

  4. Деление:

  b(x) =

  r2(x)

  v2(x)

  = 4 + 2x + x2 + 7x3.

   

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

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

  Пусть t — максимальное число возможных ошибок при фиксированном числе стираний s в векторе v, d � 2t + s + 1, t = [(d − s − 1)/2]. Так как позиции стертых символов известны, то заменим эти символы в

  v как с вектором, содержащим

   

  векторе v, например, на нули и будем обращаться с полученным вектором �

  только ошибки. Пусть ошибки произошли на позициях i1, . . . , it, а стирания на позициях it+1, . . . , it+s. При этом известны только позиции it+1, . . . , it+s. После того как на данные позиции поместили нули, с

  Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 3. С. 17–29

  Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29 21

   

  какими-то позициями могли угадать (если в кодовом векторе там действительно стояли нули). Поэтому

  v = u + e, где e — вектор ошибок веса не более t + s.

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

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

   

  , . . . ) ×

  S = �

  1 t+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 + . . . + eit+s wit+s 

   ei1 wi1 αi1 + . . . + eit+s wit+s αit+s 

  =

   

  .

   

   . . . 

   n−k−1

  n−k−1 

  ei1 wi1 αi1 + . . . + eit+s wit+s αit+s

  Пусть X1 = αi1 , . . . Xt = αit — неизвестные локаторы ошибок, Xt+1 = αit+1 , . . . , Xt+s = αit+s — известные локаторы стираний, Y1 = ei1 , . . . , Yt+s = eit+s — значения ошибок. Обозначим Zj = Yj wij , j = 1, . . . , t + s. Тогда:

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

  S1 = Z1X1 + . . . + ZtXt + Zt+1Xt+1 + . . . + Zt+sZt+s,

  . . .

   

  (4)

  2t+s−1

  2t+s−1

  2t+s−1

  2t+s−1

  S2t+s−1 = Z1X1 + . . . + ZtXt + Zt+1Xt+1 + . . . + Zt+sXt+s .

  При этом из d = n − k + 1 � 2t + s + 1 следует, что n − k � 2t + s. Запишем синдромный многочлен в

  виде:

  2t+s−1

  2t+s−1 t+s

   t+s

  (2t+s−1 )

  S(x) =

   Zj Xi xi = Zj

   

  ∑ Sixi =

  ∑ ∑ ∑

  j

  ∑ (Xj x)i =

  i=0

  t+s

  i=0

  1 − (X x)2t+s

  j=1

  t+s Z

  j=1

  i=0

  t+s Zj X2t+s

   

  Полагая

  

  = ∑ Zj

  j=1

  j

  1 − Xj x

   

  t+s

  = ∑

  j=1

  j

  

  1 − Xj x

   

  t+s

• x2t+s ∑

j=1

j .

1 − Xj x

i

 

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

σ0 = 1,

�

 

t+s

 

i=1

 

i=0

σi �

t+s

i

 

ω(x) = ∑ Z ∏

�

(1 − Xj x),

i

 

Φ�(x) = ∑ ZiX2t+s

∏ (1 − Xj x),

i=1

1 j t+s, j̸=i

i=1

1 j t+s, j̸=i

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

 

Тогда

ω(x)

S(x) = �

�

− 2t+s �

 

Φ(x)

x .

σ(x)

�

 

σ(x) = ω(x) − x2t+sΦ�(x).

Данное выражение называют ключевым уравнением, которому можно придать иной вид:

2t+s

� ω(x) (mod x

). (5)

известных

 

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

 

t s

�

 

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

i=1

i=1

Введем в рассмотрение многочлен

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

Тогда ключевое уравнение (5) примет вид:

 

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

 

где

 

Рассмотрим сравнение

σ(x)S�(x) ≡ �

�

 

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

a(x)S�(x) ≡ b(x) (mod x2t+s) (8)

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

22Ratseev S.M., Cherevatenko O.I. Decoding algorithms for generalized Reed-Solomon codes

 

относительно неизвестных многочленов a(x), b(x) ∈ F [x] с условием

deg a(x) ::: t, deg b(x) ::: t + s − 1, a(0) = 1. (9)

Из (6) и (7) следует, что сравнение (8) с условием (9) имеет решение.

 

Теорема 3. 1. Многочлены a(x) и b(x) являются решением сравнения (8) с условием (9) тогда и только тогда, когда для некоторого многочлена µ(x) ∈ F [x] выполнены равенства a(x) = µ(x)σ(x), b(x) =

= µ(x)ω(x).

�

2. Многочлены σ(x) и ω(x) являются единственным решением сравнения (8) с условием (9) и усло- вием взаимной простоты. �

Доказательство. 1. Если a(x) = µ(x)σ(x), b(x) = µ(x)ω(x), то

�

�

 

a(x)S�(x) ≡ µ(x)σ(x)S�(x) ≡ µ(x)ω(x) ≡ b(x) (mod x2t+s).

Обратно, пусть a(x) и b(x) — некоторое решение сравнения (8) с условием (9). Рассмотрим два сравнения:

b(x) ≡ a(x)S�(x) (mod x2t+s),

�

 

ω(x) ≡ σ(x)S�(x) (mod x2t+s).

Умножив первое сравнение на σ(x), а второе на a(x), получим:

�

 

b(x)σ(x) ≡ a(x)σ(x)S�(x) ≡ ω(x)a(x) (mod x2t+s).

 

ω(x), из сравнения

Учитывая первые два неравенства из условия (9) для многочленов a(x), b(x), σ(x), �

≡

 

b(x)σ(x) ω(x)a(x) (mod x2t+s) следует равенство:

�

b(x)σ(x) = ω(x)a(x). (10)

�

 

|

 

При

 

ω(x)a(x) и σ(x) и ω(x) взаимно просты, то σ(x) a(x). Поэтому найдется многочлен µ(x), для которого a(x) = µ(x)σ(x). � этом из (10) следует, что:

b(x)

=

ω(x)

�

a(x)

 

σ(x)

 

= µ(x).

Таким образом, a(x) = µ(x)σ(x), b(x) = µ(x)ω(x).

решение

 

2. Пусть a(x) и b(x) — некоторое � сравнения (8) с условием (9), причем a(x) и b(x) взаимно

просты. Из пункта 1 следует, что для некоторого многочлена µ(x) выполнено a(x) = µ(x)σ(x), b(x) =

= µ(x)ω(x). В силу взаимной простоты a(x) и b(x) многочлен µ(x) должен являться константой. А в

�

D

 

силу условия σ(0) = a(0) = 1 эта константа равна единице, поэтому α(x) = σ(x), b(x) = ω(x).

�

Определим для обобщенного алгоритма Евклида следующие многочлены:

2t+s

r−1(x) = x

, r0(x) = S�(x),

u−1(x) = 1, u0(x) = 0, v−1(x) = 0, v0(x) = 1.

Произведем последовательность действий обобщенного алгоритма Евклида (i � 1):

ri−2(x) = ri−1(x)qi(x) + ri(x),

ui(x) = ui−2(x) − ui−1(x)qi−1(x),

vi(x) = vi−2(x) − vi−1(x)qi−1(x).

При этом будем получать такие равенства:

ui(x)x2t+s + vi(x)S�(x) = ri(x),

из которых следуют сравнения:

ri(x) ≡ vi(x)S�(x) (mod x2t+s).

Учитывая, что степени остатков ri(x) строго убывают, будем применять алгоритм Евклида до тех пор, пока не достигнем такого rj (x), что

deg rj−1(x) � t + s, deg rj (x) ::: t + s − 1. (11) Тогда в качестве a(x) и b(x) возьмем такие многочлены:

a(x) = λvj (x), b(x) = λrj (x), (12)

где константа λ ∈ F задается так, чтобы удовлетворялось условие a(0) = 1 (в теореме 4 приводится обоснование того, что vj (0) ̸= 0, поэтому такая константа существует). В этом случае:

b(x) ≡ λrj (x) ≡ λvj (x)S�(x) ≡ a(x)S�(x) (mod x2t+s),

Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 3. С. 17–29

Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29 23

deg b(x) = deg rj (x) ::: t + s − 1,

deg a(x) = deg vj (x) = deg x2t+s − deg rj

−1(x) ::: 2t + s − t − s = t.

Поэтому такой алгоритм приводит к решению a(x) и b(x) сравнения (8) с условием (9).

Теорема 4. Пусть vj (x) и rj (x) — многочлены из обобщенного алгоритма Евклида с условием (11).

�

 

Тогда найдется такая ненулевая константа λ ∈ F , для которой σ(x) = λvj (x), ω(x) = λrj (x).

Доказательство. Для многочленов vj (x) и rj (x), а также для многочленов σ(x) и ω(x) выполнены равенства: �

uj (x)x2t+s + vj (x)S�(x) = rj (x), (13)

�

 

Φ�(x)x2t+s + σ(x)S�(x) = ω(x). (14)

Домножив обе части первого равенства на σ(x), а второго — на vj (x), получим:

σ(x)uj (x)x2t+s + σ(x)vj (x)S�(x) = σ(x)rj (x),

ω

 

vj (x)Φ�(x)x2t+s + vj (x)σ(x)S�(x) = vj (x)�(x).

(15)

Из данных равенств следует сравнение:

 

ω(x) (mod x2t+s).

σ(x)rj (x) ≡ vj (x)�

Учитывая степени многочленов в данном сравнении, получаем равенство:

�

 

σ(x)rj (x) = vj (x)ω(x).

Поэтому из (15) с учетом последнего равенства следует такое равенство:

σ(x)uj (x) = vj (x)Φ�(x).

Из свойства взаимной простоты многочленов uj (x) и vj (x) следует, что vj (x) | σ(x), поэтому для неко- торого многочлена µ(x) выполнено σ(x) = µ(x)vj (x). Подставим это равенство в (14):

�

 

Φ�(x)x2t+s + µ(x)vj (x)S�(x) = ω(x).

Теперь домножим равенство (13) на µ(x):

µ(x)uj (x)x2t+s + µ(x)vj (x)S�(x) = µ(x)rj (x).

 

ω(x) =

Учитывая степени многочленов ω(x), µ(x) и rj (x), из последних двух равенств следует равенство �

= µ(x)rj (x).

ω(x) = µ(x)rj (x). Так как многочлены σ(x) и ω(x) взаимно просты, то многочлен µ(x) является ненулевой константой. � D

Замечание. Вернемся к вопросу о наличии в векторе α нулевой компоненты. В предыдущем алго- ритме этот факт не имел значения. Здесь же нужно это учитывать. Предположим, что αi = 0. Пусть на i-й позиции кодового вектора произошла ошибка. Так как X0 = αi = 0, то данный локатор ошибки не оказывает влияния на многочлен σ(x). С помощью данного многочлена можно найти только нену- левые локаторы ошибок и соответствующие им значения ошибок. Поэтому в самом конце следующего алгоритма после нахождения всех ошибок, соответствующих ненулевым локаторам, необходимо прове-

 

ак

 

рить, была ли еще одна ошибка на i-й позиции. Пусть u — вектор, в котором исправлены все ошибки в векторе v, соответствующие ненулевым локаторам. Т �как i-й столбец матрицы H имеет только одно

�

ненулевое значение на первой позиции, равное wi, то необходимо найти значение Z0, равное скалярно- му произведению вектора u на первую строку матрицы H. Если Z0 = 0, то на i-й позиции ошибок не

случае 0 0 i

 

было. В противном �значение ошибки на i-й позиции равно Y = Z w−1.

i

 

Пусть теперь на i-й позиции произошло стирание. Тогда значение ошибки равно Y0 = Z0w−1.

Алгоритм 2 (декодирование ОРС кодов на основе алгоритма Сугиямы на случай ошибок и стира- ний).

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

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

   вектор �

    

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

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

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

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

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

   24Ratseev S.M., Cherevatenko O.I. Decoding algorithms for generalized Reed-Solomon codes

    

2. Пусть r−1(x) = x

   2t+s

   , r0(x) = S�(x), v−1(x) = 0, v0(x) = 1. С помощью обобщенного алгоритма

   Евклида производится последовательность вычислений (i � 1):

   ri−2(x) = ri−1(x)qi−1(x) + ri(x),

   vi(x) = vi−2(x) − vi−1(x)qi−1(x).

   Процесс прекращается, как только для некоторого rj (x) будет выполнено:

   deg rj−1(x) � t + s, deg rj (x) ::: t + s − 1. (16)

   Тогда:

    

   �

    

   σ(x) = λvj (x), ω(x) = λrj (x),

   где константа λ ∈ F задается так, чтобы удовлетворялось условие σ(0) = 1. Пусть l = deg σ(x).

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

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

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

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

      — множество индексов локаторов ошибок и стираний без учета индекса p. Находятся Zj , j ∈ M , на- пример, с помощью алгоритма Форни для обобщенных кодов РС:

      j

       

      ω(X−1)

      

      Zj = ∏ �

      −1 , j ∈ M. (17)

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

       

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

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

      j ∈ i

       

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

      ненулевые). p

       

      = 0 (в противном случае все локаторы стираний были бы � Вычисляется значение Z , равное

      скалярному произведению вектора u на первую строку матрицы H. Вычисляется значение ошибки Yp =

      p i i p

       

      = Z /w . Осталось в векторе u из �-го символа вычесть Y .

      �

      j ij j �

       

      �

       

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

�

 

Если αi = 0 для некоторого i, то вычисляется значение Z0, равное скалярному произведению векто- ра u на первую строку матрицы H. Если Z0 ̸= 0, то вычисляется значение ошибки Y0 = Z0/wi. Осталось

0

 

в векторе u из i-го символа вычесть Y .

�

Пример 2. Продолжим рассмотрение примера 1, в котором рассматривался код GRS4(α, y). Порож- дающая и проверочная матрицы кода GRS4(α, y), учитывая теорему 1, будут иметь вид:

2	1	3	1	4	1	5	1	6
0	1	6	3	5	5	8	7	4
0	1	1	9	9	3	4	5	10
0	1	2	5	3	4	2	2	3

 

10	5	7	2	9	2	2	5	7	
0	5	3	6	3	10	1	2	1
0	5	6	7	1	6	6	3	8	 
0	5	1	10	4	8	3	10	9	 
0	5	2	8	5	7	7	4	6

 





G = 



 

 , H =  ,

  

  



 

 

где первая строка матрицы H совпадает с вектором w.

Пусть на приемном конце получен тот же вектор v = (1, 3, 6, 10, 9, 1, 10, ∗, 8). Применим алгоритм

декодирования 2.

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

   v = (1, 3, 6, 10, 9, 1, 10, 0, 8).

   �

   Находим синдромный вектор (S0, S1, S2, S3, S4) =

    

   vHT = (4, 5, 7, 3, 2). Вычисляем известные локаторы

   �

   стираний: X3 = α7 = 7. Поэтому

   S�(x) = S(x)ν(x) = (4 + 5x + 7x2 + 3x3 + 2x4)(1 − 7x) =

   = 4 + 10x + 5x2 + 9x3 + 3x4 + 8x5.

   Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 3. С. 17–29

   Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29 25

    

   −1 0 � −1 0

    

2. Определяем r (x) = x5, r (x) = S(x), v (x) = 0, v (x) = 1. Выполняем неполный алгоритм Евклида:

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

   r1(x) = 5 + 7x + 9x2 + 3x3 + x4,

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

   r0(x) = r1(x)q1(x) + r2(x), q1(x) = 1 + 8x,

   r2(x) = 10 + 7x + 6x2,

   v2(x) = v0(x) − q1(x)v1(x) = 8 + x.

   Так как t + s = 3, deg r1(x) = 4, deg r2(x) < 3, то после второго шага останавливаемся. Тогда

   �

    

   σ(x) = λv2(x), ω(x) = λr2(x).

   При λ = 7 получаем σ(0) = 1, поэтому:

   σ(x) = 1 + 7x, ω(x) = 4 + 5x + 9x2.

   �

   1

    

3. Корнем многочлена σ(x) является x1 = 3, поэтому X1 = x−1 = 4 = α4. Это значит, что ошибка произошла на 4-й позиции. Итак, на 4-й позиции вектора v точно имеется ошибка, а на позиции 7,

   лями

    

   возможно, есть ошибки (после замены стертых символов ну � мы могли поставить некоторые символы

   верно).

4. Так как среди локаторов стираний нет нулевых, то попадаем в пункт 4.2 алгоритма 2. Находим значения ошибок:

ω(X−1)

Z1 = � 1

= 6, Y1 = Z1w−1 = 8,

1

 

(1 − X3X−1) 4

ω(X−1)

Z3 = � 3

= 2, Y3 = Z3w−1 = 7.

3

 

(1 − X1X−1) 7

Вычитая из 4-й и 7-й позиций в векторе v соответственно значения 8 и 7, получаем вектор:

�

u = (1, 3, 6, 10, 1, 1, 10, 4, 8).

�

Осталось проверить, была ли ошибка на 0-й позиции, которая соответствует элементу α0 = 0. Вычис- ляя скалярное произведение вектора u на первую строку матрицы H, получаем Z0 = 7. Это означает,

со 0 0 0

 

что на 0-й позиции имеется ошибка � значением Y = Z w−1 = 4. Окончательно:

−

 

u = u (4, 0, 0, 0, 0, 0, 0) = (8, 3, 6, 10, 1, 1, 10, 4, 8).

�

 

3. Декодирование ОРС кодов на основе алгоритма Берлекэмпа — Месси (алгоритма Питерсона — Горенстейна — Цирлера)

Продолжим рассмотрение сравнения (6). Пусть d � 2t + s + 1,

−

 

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

2t+s−1 s

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

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

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

i = 1, . . . , s.

�

 

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

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

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

уравнений:

 σ0S�s+t + σ1S�s+t−1 + . . . + σtS�s = 0,

 σ0S�s+t+1 + σ1S�s+t + . . . + σtS�s+1 = 0,

. . .

− − −

 

 σ0S�s+2t 1 + σ1S�s+2t 2 + . . . + σtS�s+t 1 = 0.

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

 S�s

S�s+1 . . .

S�s+t−1   σt 

 −S�s+t 

 S�s+1

S�s+2 . . .

S�s+t

  σt−1

 = 

−S�s+t+1

 . (18)



 

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

 

 



 



 

  . . .  



 

. . . 

S�s+t−1

S�s+t . . .

S�s+2t−2 σ1

−S�s+2t−1

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

26Ratseev S.M., Cherevatenko O.I. Decoding algorithms for generalized Reed-Solomon codes

 

Обозначим матрицу этой системы через M (t, s). Выясним, в каком случае эта система разрешима.

Лемма. Для любого j = 0, 1, . . . , 2t − 2 выполнено равенство:

t s

k

 

S�s+j = ∑ Zk Xj ∏(Xk − Xt+i).

k=1

i=1

Доказательство. Пусть, как и ранее, νi = (−1)iσi(Xt+1, . . . , Xt+s) — элементарный симметрический многочлен от Xt+1, . . . , Xt+s. Обозначим σi = σi(Xt+1, . . . , Xt+s). Учитывая определение многочлена S�(x) и равенство:

 

получаем:

s

−

 

∑(−1)s−iσs

i=0

k

 

iXi =

{ 0, t + 1 ::: k ::: t + s,

∏s

 

i=1(Xk − Xt+i), k ̸∈ {t + 1, . . . , t + s},

s s t+s

S�s+j = ∑ Sj+iνs−i = ∑ ∑ Zk X

j+i k

(−1)

s−i

σs−i =

 

t+s

i=0

s

i=0 k=1

t s

= ∑ Zk Xj ∑ Xi (−1)s−iσs

i = ∑ Z Xj ∑ Xi (−1)s−iσs i =

 

k=1

k k

i=0

t

— k

k=1

s

k k −

i=0

k

 

= ∑ Zk Xj ∏(Xk − Xt+i).

k=1

i=1

D

Теорема 5. Пусть произошло s стираний. Матрица M (t, s) невырождена тогда и только тогда, когда произошло t ошибок.

Доказательство. Обозначим через A, B, C следующие квадратные матрицы порядка t:

 1 1 . . . 1 

 Z1 0 . . . 0 

A = 

X1 X2 . . . Xt

 , B = 

0 Z2 . . . 0  ,

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

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



Xt−1

t−1

  

t−1

 

 ∏s

1 X2 . . . Xt

0 0 . . . Zt





 

C = 



i=1(X1 − Xt+i) 0 . . . 0

0 ∏s

 

.

 

i=1(X2 − Xt+i) . . . 0 



 

. . . . . . . . . . . . 

i=1

 

0 0 . . . ∏s

(Xt − Xt+i)

Покажем, что M (t, s) = ABCAT . По лемме элемент матрицы M (t, s) с индексами i и j равен:

t

i+j−2

 

(M (t, s))ij = S�s+i+j−2 = ∑ Zk Xk

s

∏(Xk − Xt+l).

 

Учитывая, что

k=1

l=1

 

s

j

 

(A)ij = Xi−1, (BC)ij = δij Zi ∏(Xi − Xt+k ),

k=1

где δij — символ Кронекера, найдем элемент с соответствующими индексами матрицы ABCAT :

t t t

(ABCAT )ij = ∑ (ABC)im(AT )mj = ∑ ∑ Aik (BC)kmAjm =

m=1

t t s

m=1 k=1

t s

= ∑ ∑ Xi−1

∏(X − X

)Xj−1 = ∑ Z Xi+j−2 ∏(X − X ).

 

m=1 k=1

k δkmZk

k

l=1

t+l m

k k

k=1

k

l=1

t+l

Следовательно, M (t, s) = ABCAT .

Если произошло t ошибок, то все X1, . . . , Xt+s различные, а все Z1, . . . , Zt отличны от нуля, поэтому определитель матрицы ABCAT отличен от нуля. Если произошло менее чем t ошибок, то хотя бы один диагональный элемент матрицы B равен нулю, поэтому матрица ABCAT будет вырожденной. D

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

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

Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 3. С. 17–29

Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 3, pp. 17–29 27

 

Выход: исходный кодовый вектор u, если d � 2t + s + 1.

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

   вектор �

    

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

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

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

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

2. Определяется h := t.

   Цикл: пока |M (h, s)| = 0, переопределить h := h − 1.

   Если h > 0, то находятся σ1, . . . , σh — решение системы (18). Это можно сделать с помощью ал- горитма Берлекэмпа — Месси (или методом Гаусса). После этого составляется многочлен σ(x). Пусть l = deg σ(x).

3. Отыскиваются 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 , например, с помощью формул Форни (17). После этого находятся значения ошибок

      �

       

      Yj = Zj /wij , j ∈ M . У вектора v из ij -го символа, Xj = αij , вычитается значение Yj , j ∈ M . При

      для i p

       

      этом получается вектор u. Пусть некоторого i выполнено α = 0. Вычисляется значение Z , равное

      �

      скалярному произведению вектора u на первую строку матрицы H. Вычисляется значение ошибки Yp =

      p i i p

       

      = Z /w . Осталось в векторе u из �-го символа вычесть Y .

      �

      j ij j �

       

      �

       

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

�

 

0

 

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

�

 

Пример 3. Продолжим рассматривать примеры 1 и 2. Пусть на приемной стороне получен все тот же вектор 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. Составляем матрицу системы (18):

( S�1

S�2

=

 

.

 

10	5	−9
5	9	−3

 

S�2 −S�3 ) ( )

S�3 −S�4

Так как определитель матрицы M (2, 1) ненулевой, то из данной системы находим σ1 = 7, σ2 = 0. Поэтому σ(x) = 1 + 7x. После этого осталось повторить шаги 3 и 4 предыдущего примера. Только проверять, была ли ошибка на 0-й позиции, не нужно, так как факт ее наличия следует из неравенств

deg σ(x) < 2, |M (2, 1)| ̸= 0.

 

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: chai@pisem.net
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