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

Полный текст

• Введение

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

 

Об авторах

С. М. Рацеев

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

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

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

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

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

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

Email: chai@pisem.net
ORCID iD: 0000-0003-3931-9425

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

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

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

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