ON THE BERLEKAMP — MASSEY ALGORITHM AND ITS APPLICATION FOR DECODING ALGORITHMS

Full Text

Введение

 

В технике один из наиболее распространенных методов генерации битовых последовательностей реализуется с помощью регистров сдвига с обратной линейной связью (Linear Feedback Shift Register – LFSR). Регистр сдвига с обратной связью (LFSR) — это регистр, который можно рассматривать как множество ячеек памяти, в каждой из которых записан один бит информации. На каждом шаге содержимое нескольких заранее определенных ячеек (отводов) пропускается через функцию обратной связи. Значение функции записывается в самую левую ячейку регистра, сдвигая все остальные его биты на одну позицию вправо. Выходом регистра на текущем шаге является «вытолкнутый» справа бит (рис. 1).

 

✲ an an−1

. . .

a2 a1 ✲

 

f1 f2 fn−1 fn

❄ ❄ ❄ ❄

an+1 = f1an + f2an−1 + . . . + fn−1a2 + fna1

 

Рис. 1. Регистр сдвига с обратной связью Fig. 1. Feedback shift register

 

Рассмотрим систему линейных уравнений над некоторым полем F относительно неизвестных

f1, . . . , fn:

 an an−1 . . . a2 a1

 an+1 an . . . a3 a2

  f1 

  f2 

 −an+1 

 −an+2 

 . . . . . . . . . . . . . . .   . . .  = 

. . .

 . (1)

   

a2n−1 a2n−2 . . . an+1 an fn

 

−a2n

У матрицы данной системы все диагонали, параллельные главной, имеют одинаковые элементы. Матрица такого вида называется диагонально-постоянной матрицей, или матрицей Тёплица. Решение данной системы уравнений методом Гаусса имеет сложность вычислений порядка n3. Такие системы практичнее решать с помощью алгоритма Берлекэмпа — Месси, который дает сложность вычислений порядка n2.

Алгебраические алгоритмы декодирования кодов БЧХ (в частности, кодов Рида — Соломона) можно разделить на два класса: синдромные и бессиндромные. Хорошо известные алгоритмы синдромного декодирования построены на основе алгоритма Питерсона — Горенстейна — Цирлера, алгоритма Берлекэмпа — Месси, алгоритма Сугиямы [1; 2]. К алгоритмам безсиндромного декодирования относится, например, алгоритм Гао [3]. Процесс синдромного декодирования можно разбить на четыре шага: 1) вычисление компонентов синдромного вектора на основе полученного вектора; 2) нахождение многочлена локаторов ошибок σ(x), который содержит информацию о позициях ошибок; 3) нахождение корней многочлена σ(x), по которым определяются позиции ошибок; 4) нахождение значений ошибок (для недвоичных кодов).

Второй этап декодирования является самым сложным. Многочлен локаторов ошибок σ(x) можно найти несколькими способами. Один из первых способов нахождения σ(x) — алгоритм Питерсона для двоичных кодов (на основе тождеств Ньютона) и Горенстейна — Цирлера для недвоичных кодов, который сводит данную задачу к решению системы из t линейных уравнений (например, с помощью метода Гаусса), где t — максимальное число ошибок, исправляемое кодом. Сложность такого декодирования пропорциональна t3. Берлекэмп, используя особенности матрицы коэффициентов системы уравнений, уменьшил сложность нахождения многочлена σ(x) до величины порядка t2. Месси сумел интерпретировать алгоритм Берлекэмпа как алгоритм построения рекуррентного фильтра, тем самым упростив и понимание алгоритма, и его реализацию. В окончательном виде этот алгоритм получил название алгоритма Берлекэмпа — Месси.

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

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

46Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

1. Алгоритм Берлекэмпа — Месси

Лучшим подходом к алгоритму Берлекэмпа — Месси является интерпретация матричного уравнения (1) как описания рекурсивного фильтра. Предположим, что вектор f = (f1, . . . , fn) известен. Последовательность a1, a2, . . . в этом случае называется линейной рекуррентной последовательностью, члены которой вычисляются с помощью уравнения

n

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

i=1

Изначально на элементы последовательности a1, a2, . . . каких-либо ограничений не накладывается. Произвольный LFSR можно задать многочленом f (x) обратных связей f (x) = 1 + f1x + . . . + fnxn и длиной L регистра. Заметим, что длина регистра может быть больше степени многочлена f (x), так как самые правые ячейки могут не включаться в обратную связь.

Для построения регистра сдвига нужно определить две величины: длину L регистра и многочлен f (x) обратных связей при условии deg f (x) ::: L. Обозначим эту пару через (L, f (x)). Данный LFSR должен порождать заданную последовательность a1, a2, . . . , a2n и иметь минимальную длину L.

Основная идея алгоритма Берлекэмпа — Месси состоит в следующем. Алгоритм построения LFSR минимальной длины является рекурсивным. Для каждого r = 2, 3, . . . , 2n он строит LFSR, порождающий последовательность a1, . . . , ar . LFSR минимальной длины, порождающий последовательность a1, . . . , ar , обозначим через (Lr, f (r)(x)). Такой регистр не обязательно должен определяться однозначно, так как возможно существование нескольких LFSR минимальной длины. К началу r-го шага имеется совокупность LFSR:

(L1, f (1)(x)), (L2, f (2)(x)), . . . , (Lr

−

 

1, f (r−1)(x)).

Алгоритм Берлекэмпа — Месси вычисляет новый LFSR (Lr, f (r)(x)) минимальной длины, генерирующий последовательность a1, . . . , ar . Для этого используется самый последний из вычисленных LFSR, в котором, при необходимости, модифицируются длина и весовые множители в отводах. На r-м

шаге алгоритма вычисляется элемент с номером r на выходе (r − 1)-го регистра сдвига:

Lr−1

ar = − ∑ f (r−1)

 

i=1

i ar−i.

Если ∆r = 0, то полагаем (Lr, f (r)(x)) = (Lr

−

 

1, f (r−1)(x)) и завершаем этим самым r-й шаг алгоритма.

Если ∆r ̸= 0, то изменим весовые множители в LFSR по правилу

f (r)(x) = f (r−1)(x) +

( ∆r )

− ∆m

xr−mf (m−1)(x),

где число m удовлетворяет условию Lr−1 = Lr−2 = . . . = Lm > Lm−1.

n

Теорема 1 [4]. Пусть {(Lr, f (r)(x))}

 

r=1

— последовательность LFSR минимальной длины, таких,

что (Lr, f (r)(x)) генерирует последовательность a1, . . . , ar . Если для некоторого r, 2 ::: r ::: n, выполнено

f (r−1)(x) ̸= f (r)(x), то

Lr = max{Lr−1, r − Lr−1}.

Замечание 1. Пусть для некоторого r выполнено неравенство f (r−1)(x) ̸= f (r)(x). Тогда возможны два случая.

1. Lr > Lr−1. Тогда из теоремы 1 следует, что Lr = r − Lr−1 > Lr−1. Поэтому 2Lr−1 < r.

2. Lr = Lr−1. Тогда Lr−1 ;? r − Lr−1. Поэтому 2Lr−1 ;? r.

   Учтем данное замечание при описании алгоритма Берлекэмпа — Месси. В следующем алгоритме многочлен f (x) отвечает за многочлен LFSR (Lr, f (r)(x)), а многочлен b(x) — за многочлен LFSR

   (m−1)

   (Lm−1, f

   (x)).

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

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

    

   L

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

   i=1

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

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

   Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 47

    

   2. Цикл r := 1, . . . , n :

   L

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

i=1

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

2.3. Если ∆ ̸= 0:

2.3.1 buf (x) := f (x) − ∆ · x · b(x);

1. Если 2L < r: b(x) := ∆−1 · f (x),

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

2. Иначе (т. е. выполнено 2L ;? r): f (x) := buf (x),

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

Заметим, что в алгоритме 1 можно минимизировать число вычислений обратных элементов в поле

F , т. е. вычислений вида ∆−1. Для этого стоит лишь заметить, что если для некоторого унитарного

L

многочлена f (x) выполнено равенство ar + ∑ fiar−i = 0, то для любого δ ∈ F выполнено равенство

i=1

L

∑ f iar−i = 0, где f (x) = δ · f (x). Поэтому алгоритм 1 можно записать в следующем виде.

i=0

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

Вход: последовательность 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, δ := 1. 2. Цикл r := 1, . . . , n :

L

2.1. Определить ∆ := ∑ fiar−i;

i=0

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

2.3. Если ∆ ̸= 0:

2.3.1 buf (x) := δ · f (x) − ∆ · x · b(x);

1. Если 2L < r: b(x) := f (x), f (x) := buf (x),

   L := r − L,

   δ := ∆;

2. Иначе (т. е. выполнено 2L ;? r): f (x) := buf (x),

b(x) := x · b(x);

0

 

3. f (x) := f−1 · f (x).

 

2. Взаимосвязь алгоритма Берлекэмпа — Месси и обобщенного алгоритма Евклида

Приведенный алгоритм Берлекэмпа — Месси при определенном ограничении можно заменить на эквивалентный алгоритм на основе обобщенного алгоритма Евклида. Этот факт отражен в нескольких работах, например в [5; 6]. В данной работе приведем другое доказательство данной эквивалентности.

Алгоритм 2 (нахождение решения системы (1) с помощью обобщенного алгоритма Евклида).

Вход: последовательность a1, a2, . . . , a2n над некоторым полем F , для которой система (1) имеет решение.

Выход: многочлен f (x) степени ::: n, для которого f (0) = 1 и

n

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

i=1

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

48Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

2n

 

1. Определить r−1(x) = x

   2n

   , r0(x) = ∑ aix

   i=1

   i−1

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

2. Производится последовательность вычислений обобщенного алгоритма Евклида:

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

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

   i = 1, 2, . . . ,

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

   deg rj−1(x) ;? n, deg rj (x) ::: n − 1.

3. Определить f (x) = λvj (x), где константа λ ∈ F задается так, чтобы удовлетворялось условие

f (0) = 1.

 

Теорема 2. Если для последовательности a1, a2, . . . , a2n над некоторым полем F система (1) имеет решение, то алгоритм 2 всегда возвращает решение системы (1). Более того, если f1, . . . , fn — некоторое решение системы (1), f (x) = 1 + f1x + . . . + fnxn — соответствующий многочлен, f (x) — результат работы алгоритма 2, то f (x) делит f (x), т. е. из всех решений системы (1) многочлен f (x) имеет минимальную степень.

Доказательство. Пусть f1, . . . , fn — некоторое решение системы (1). Определим f0 = 1 и обозначим:

g0 = a1f0,

g1 = a2f0 + a1f1,

. . .

gn−1 = anf0 + an−1f1 + . . . + a1fn−1.

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

(3)

 

	a1	0	. . .	0	0	
 	a2 . . .	a1 . . .	. . . . . .	0 . . .	0 . . .	  

 

  f0 

 g0 

 g1 



 



 

 . . . 



 

f1

 

 an an−1 . . . a1 0



 

  



 



 

 gn−1 

 an+1 an . . . a2 a1

  . . .  = 

0  , (4)





 

 an+2 an+1 . . . a3 a2

    

  



 

0

 

fn

 

 



 



 

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

a2n a2n−1 . . . an+1 an



 



 

 . . . 

0

в которой система их последних n уравнений полностью совпадает с системой (1). Пусть

2n n

n−1

a(x) = ∑ aixi−1, f (x) = ∑ fixi, g(x) = ∑ gixi.

i=1

Система (4) эквивалентна сравнению

i=0

i=0

 

с условиями

a(x)f (x) ≡ g(x) (mod x2n) (5)

f (0) = 1, deg f (x) ::: n, deg g(x) ::: n − 1. (6)

Действительно, пусть выполнено сравнение (5) с условиями (6). Так как выполнено неравенство

deg g(x) ::: n−1, то коэффициенты многочлена a(x)f (x) при степенях xn, xn+1, . . . , x2n−1 равны нулю. Это

значит, что должны выполняться последние n уравнений системы (4). При этом первые n уравнений

системы (4) напрямую следуют из сравнения (5). Обратно, из системы (4) очевидным образом следует сравнение (5) с условиями (6).

2n

 

Применим к многочленам r−1(x) = x

обобщенный алгоритм Евклида:

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

ri−2(x) = ri−1(x)qi−1(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),

i = 1, 2, . . .

Тогда на каждом шаге алгоритма будем получать равенства

ui(x)x2n + vi(x)a(x) = ri(x),

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

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 49

из которых следуют сравнения vi(x)a(x) ≡ ri(x) (mod x2n). Так как

2n = deg r−1(x) > deg r0(x) > deg r1(x) > . . . ,

то для некоторого j будут выполнены неравенства

deg rj−1(x) ;? n, deg rj (x) ::: n − 1.

Поэтому индекс j определен однозначно. При этом

deg vj (x) = deg x2n − deg rj

−1(x) ::: 2n − n = n.

Следовательно, мы получили сравнение vj (x)a(x) ≡ rj (x) (mod x2n), где deg rj (x) ::: n − 1, deg vj (x) ::: n.

Покажем, что vj (0) ̸= 0. Для многочленов vj (x) и rj (x), а также для многочленов f (x), g(x) и

некоторого многочлена t(x) выполнены равенства

uj (x)x2n + vj (x)a(x) = rj (x), (7)

t(x)x2n + f (x)a(x) = g(x). (8)

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

f (x)uj (x)x2n + f (x)vj (x)a(x) = f (x)rj (x),

vj (x)t(x)x2n + vj (x)f (x)a(x) = vj (x)g(x). (9)

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

f (x)rj (x) ≡ vj (x)g(x) (mod x2n).

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

f (x)rj (x) = vj (x)g(x).

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

f (x)uj (x) = vj (x)t(x).

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

t(x)x2n + µ(x)vj (x)a(x) = g(x).

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

µ(x)uj (x)x2n + µ(x)vj (x)a(x) = µ(x)rj (x).

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

= µ(x)rj (x).

Таким образом, f (x) = µ(x)vj (x), g(x) = µ(x)rj (x). Так как f (0) = 1, то выполнено vj (0) ̸= 0. Определим f (x) = λvj (x), где константа λ ∈ F задается так, чтобы удовлетворялось условие f (0) = 1.

Тогда из λvj (x)a(x) ≡ λrj (x) (mod x2n), deg λvj (x) ::: n получаем, что f 1, . . . , f n — решение системы (1). При этом f (x) | f (x). D

Предложение 1. Пусть (L, f (x)) — результат работы алгоритма 1, которому на вход подавалась последовательность a1, . . . , an. Пусть

g0 = a1f0,

g1 = a2f0 + a1f1,

. . .

gL−1 = aLf0 + aL−1f1 + . . . + a1fL−1,

где f0 = 1. Тогда L = max{deg f (x), deg g(x) + 1}, где g(x) = g0 + g1x + . . . + gL−1x

 

L−1.

(10)

Доказательство. Очевидно, что L ;? max{deg f (x), deg g(x) + 1}. Предположим, что L >

> max{deg f (x), deg g(x) + 1}. В этом случае fL = 0 = gL−1. Из равенств (2) и fL = 0 следуют равенства

L−1

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

i=1

Из равенства gL−1 = 0, учитывая (10), получаем такое равенство:

aL + aL−1f1 + . . . + a1fL−1 = 0.

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

50Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

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

L−1

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

i=1

Это значит, что алгоритм 1 возвратил LFSR (L, f (x)) не минимальной длины, что противоречит тому, что алгоритм Берлекэмпа — Месси возвращает LFSR минимальной длины. D

Следующая теорема показывает, что в случае совместности системы (1) алгоритмы 1 и 2 эквивалентны.

Теорема 3. Пусть для последовательности a1, a2, . . . , a2n над некоторым полем F система (1) имеет решение. Пусть (L, f (x)) — результат работы алгоритма 1, которому на вход подается данная

последовательность,

f (x) — результат работы алгоритма 2. Тогда f (x) = f (x).

Доказательство. Пусть (L, f (x)) — результат работы алгоритма 1, g(x) — многочлен, вычисленный

g(x) = λrj (x) — результат работы алгоритма 2.

с помощью формул (10),

f (x) = λvj (x),

По предложению 1 выполнено равенство L = max{deg f (x), deg g(x) + 1}. По теореме 2 для некоторого

 

 

многочлена µ(x) ∈ F [x] выполнены равенства f (x) = µ(x)f (x), g(x) = µ(x)g(x). Обозначим L =

 

 

= max{deg f (x), deg g(x) + 1}. Тогда

L�

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

i=1

 

g(x) следует, что

Предположим, что deg µ(x) ;? 1. Тогда из неравенств deg f (x) > deg f (x), deg g(x) > deg

L < L, т. е. LFSR (L, f (x)) имеет не минимальную длину. Противоречие со свойством минимальности длины LFSR алгоритма Берлекэмпа — Месси.

Таким образом, µ(x) является многочленом нулевой степени. Так как f (0) = 1 = f (0), то µ(x) = 1.

D

Следствие 1. Алгоритм 2 возвращает LFSR (L, f (x)) минимальной длины L =

= max{deg vj (x), deg rj (x) + 1}.

 

1. Алгоритм Берлекэмпа — Месси в случае поля характеристики два

   Хорошо известно следующее утверждение (см., напр., [1]).

   i

    

   Теорема 4. Пусть F — поле характеристики два, a1, a2, . . . , a2n ∈ F , a2i = a2 для любого i = 1, . . . , n−

   — 1. Пусть (L, f (x)) — LFSR, построенный для последовательности a1, a2, . . . , a2n−1, причем L ::: n − 1.

   Тогда следующие условия эквивалентны:

   L

   1. a2n = ∑ fia2n−i, т. е. элемент a2n можно получить с помощью LFSR (L, f (x));

i=1

n

 

2) a2n = a2 .

Следствие 2. Пусть F — поле характеристики два, a1, a2, . . . , a2n ∈ F , для которой система (1)

i

 

имеет решение, причем a2i = a2

для любого i = 1, . . . , n. Если к данной последовательности применить

алгоритм Берлекэмпа — Месси, то ∆2i = 0 для любого i = 1, . . . , n.

Следствие 2 показывает, что для указанной последовательности a1, a2, . . . , a2n в алгоритме Берлекэмпа — Месси достаточно рассматривать только итерации с нечетными номерами, что ускоряет алгоритм 1. Этот момент отражен в следующем алгоритме.

Алгоритм 3 (алгоритм Берлекэмпа — Месси для случая char F = 2).

Вход: последовательность a1, a2, . . . , a2n ∈ F , char F = 2, для которой система (1) имеет решение,

i

 

причем a2i = a2

для любого i = 1, . . . , n.

Выход: LFSR (L, f (x)) минимальной длины L, для которого

 

L

aj = ∑ fiaj

i=1

 

−i, j = L + 1, L + 2, . . . , 2n. (11)

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

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 51

 

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

1. Если a1 = 0, то b(x) := x.

2. Иначе (т. е. если a1 ̸= 0) :

1

 

f (x) := 1 + a1 · x, b(x) := a−1, L := 1.

4. Цикл i := 2, . . . , n :

1. Определить r := 2i − 1;

   L

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

i=1

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

4.4. Если ∆ ̸= 0 :

1. Если 2L < r:

   buf (x) := f (x) + ∆ · x2 · b(x),

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

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

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

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

 

4. Декодирование кодов БЧХ и кодов Рида — Соломона с использованием алгоритма Берлекэмпа — Месси

Кодом Боуза — Чоудхури — Хоквингема (БЧХ) над полем GF (q) называется такой циклический

код длины n, порождающий многочлен g(x) наименьшей степени которого имеет своими корнями последовательность идущих подряд степеней некоторого произвольного элемента α ∈ GF (qm) :

: αb, αb+1, . . . , αb+δ−2, где b — некоторое неотрицательное целое число, δ ;? 2, причем

{ ord(α), δ > 2,

n = ord(αb), δ = 2,

где ord — порядок элемента. Из данного определения следует, что длина кода n делит число qm − 1

(порядок мультипликативной группы поля GF (qm)).

Кодом Рида — Соломона (РС) называется код БЧХ над полем GF (q), q > 2, который имеет длину

q−1. Из данного определения следует, что при δ > 2 выполнены такие условия: α ∈ GF (q) и α является

примитивным элементом поля GF (q). Также из этого определения следует, что порождающий многочлен

кода РС имеет вид

g(x) = (x − αb)(x − αb+1) . . . (x − αb+δ−2),

т. е. коэффициенты данного многочлена принадлежат полю GF (q). Хорошо известно, что коды РС являются МДР-кодами, т. е. кодами с максимально достижимым расстоянием (d = n − k + 1).

Рассмотрим случай, когда в канале связи действуют ошибки и стирания. Заметим, что в полученных ниже алгоритмах достаточно положить s = 0 (число стираний), чтобы рассматривать случай только ошибок.

Пусть A — [n, k, d−n−k + 1]-код РС над полем GF (q), d — кодовое расстояние, u ∈ A — переданный

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

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

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

 

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

 

 

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

 

 

S0 = v(α) = Y1X1 + . . . + YmXm + Ym+1Xm+1 + . . . + Ym+sXm+s,

v(α2) = Y1X2 + . . . + YmX2

+ Ym+1X2

+ . . . + Ym+sX2 ,

S1 =

. . .

1

 

v(α2t+s

m

 

2t+s

m+1

 

2t+s

 

2t+s

m+s

 

2t+s

S2t+s−1 =

) = Y1X1 + . . . + YmXm + Ym+1Xm+1 + . . . + Ym+sXm+s .

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

52Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

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

2t+s−1

2t+s−1 m+s

 m+s

(2t+s−1 )

S(x) =

 Yj Xi+1 xi = Yj Xj

 

∑ Sixi =

∑ ∑ ∑

j

∑ (Xjx)i =

i=0

i=0

j=1

j=1

i=0

 

m+s

1 − (X x)2t+s

m+s Y X

m+s Yj X2t+s+1

= ∑ Yj Xj j = ∑

j j − x2t+s ∑ j .

 

Полагая

j=1

1 − Xjx

 

m+s

j=1

1 − Xjx

 

m+s

j=1

1 − Xjx

i

 

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

= 1,

 

m+s

 

i=1

 

i=0

σi σ0

 

m+s

 

 

ω(x) = ∑ YiXi ∏

(1 − Xjx),

i

 

Φ (x) = ∑ YiX2t+s+1

∏ (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) = ω(x) − x2t+sΦ (x).

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

2t+s

ω(x) (mod x

). (12)

известных

 

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

m s

 

 

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

i=1

 

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

i=1

 

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

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

 

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

 

где

 

Пусть

σ(x)S (x) ≡

 

 

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

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.

 

 

Так как в сравнении (13) 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

 . (15)



 

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

 

 



 



 

  . . .  



 

. . . 

S s+2t−2

S s+2t−3 . . .

S s+2t−m−1 σm

−S s+2t−1

Будем искать решение данной системы с помощью алгоритма Берлекэмпа — Месси.

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

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 53

 

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

S s,

лок

 

S s+1,. . . , S s+2t−1, то на выходе алгоритма будет верное значение многочлена локаторов ошибок σ(x). Доказательство. Пусть σ(x) — многочлен, полученный после применения алгоритма 1. Так как коэффициенты многочлена аторов ошибок σ(x) являются решением системы (15), то в теореме 1

будет выполнено неравенство L ::: m. Удалив в системе (15) 2t − 2m последних уравнений, получим

новую систему с квадратной матрицей системы порядка m. Из теоремы 5 работы [7] следует, что данная

матрица невырождена, поэтому полученная новая система имеет единственное решение. Это значит, что

D

 

σ(x) = σ(x) и L = m.

 

 

Учитывая теорему 5, получаем следующий алгоритм декодирования кодов РС (кодов БЧХ).

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

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

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

   самым вектор

   v(αi+1), i =

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

   = 0, 1, . . . , 2t + s − 1. Если они все равны нулю, то возвращается вектор

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

   многочлена

   S (x) (если s = 0, то S (x) = S(x)).

    

2. На вход алгоритма 1 подается последовательность

   S s,

   S s+1,. . . ,

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

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

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

4. Определяется множество M = {1, . . . , l} ∪ {t + 1, . . . , t + s}. По формулам Форни

X−1ω(X−1)

Yj =

j j

, j ∈ M, (16)

∏

i∈M\{j}

j

 

(1 − XiX−1)

ω(x) ≡ σ(x)S (x) (mod x2t+s), находятся значения ошибок Yj , j ∈ M . У вектора из ij -го символа,

где v

Xj = αij , вычитается значение Yj , j ∈ M . При этом получается кодовый вектор u.

Пример 1. Рассмотрим расширение поля GF (2) ⊂ GF (24). Пусть поле GF (24) строится на основе примитивного многочлена p(x) = x4 + x + 1, α — примитивный элемент поля GF (24):

 

α0 =	1	=	1000,	α1 =	α	=	0100,
α2 = α2 = 0010, α3 = α3 =							0001,

 

 

α10 = α12 = α14 =

α4 =	1	+α
α6 =
α8 =	1

 

α2

+α2

 

	=	1100,	α5 =		α	+α2		=	0110,
+α3	=	0011,	α7 =	1	+α		+α3	=	1101,
	=	1010,	α9 =		α		+α3	=	0101,

 

1	+α	+α2		=	1110,
1	+α	+α2	+α3	=	1111,
1			+α3	=	1001,

 

	α	+α2	+α3	=	0111,
1		+α2	+α3	=	1011,
1				=	1000.

 

α11 = α13 = α15 =

 

Рассмотрим код Рида — Соломона с параметрами n = 15, k = 7, d = 9. В этом случае код может исправить четыре и менее ошибок, либо три и менее ошибок и два и менее стираний, либо две и менее ошибок и четыре и менее стираний, либо одну ошибку и шесть и менее стираний, либо восемь и менее стираний.

Рассмотрим случай возможности исправления до двух ошибок и до четырех стираний. Пусть на приемном конце получен вектор

v = ( α7, α10, α, 1, α12, α12, α5, ∗, α2, ∗, ∗, α6, ∗, α3, 1 ) ,

в котором не более двух ошибок и четыре стирания. Применим алгоритм декодирования 4.

1. Полагаем s = 4, t = [(d − s − 1)/2] = 2. В данном случае нам известно, что

   X3 = α7, X4 = α9, X5 = α10, X6 = α12.

   Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

   54Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

    

   Поэтому

   ν(x) = (1 − α7x)(1 − α9x)(1 − α10x)(1 − α12x) =

   = 1 + α14x + x2 + α3x3 + α8x4.

   Заменим в векторе v ∗ на 0:

   v = ( α7, α10, α, 1, α12, α12, α5, 0, α2, 0, 0, α6, 0, α3, 1 ) .

    

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

    

   v(α) = α8, S1 = v(α2) = α5, S2 = v(α3) = α4,

   S0 =

   v(α4) = α7, S4 = v(α5) = α4, S5 = v(α6) = α11,

   S3 =

   v(α7) = α7, S7 = v(α8) = α9.

   S6 =

   Поэтому синдромный многочлен имеет такой вид:

    

   Тогда

   S(x) = α8 + α5x + α4x2 + α7x3 + α4x4 + α11x5 + α7x6 + α9x7.

    

   S (x) = S(x)ν(x) = S 0 + S 1x + . . . + S 11x11 =

   = α8 + α13x + α8x2 + α7x3 + α7x4 + α7x5 + α10x6 + αx7 + α3x8 + α11x9 + α11x10 + α2x11.

2. На вход алгоритма 1 подаем последовательность вычислений

   S 4 = α7,

   S 5 = α7,

   S 6 = α10,

   S 7 = α. После

    

   получаем σ(x) = 1 + α2x + α6x2.

   r ∆ σ(x) b(x) L

   0 1 1 0

   1 α7 1 + α7x α8 1

   2 α 1 + x α8x 1

   1 + x + α14x2	α9 + α9x	2
   1 + α2x + α6x2	α9x + α9x2	2

    

   3 α6

   4 α14

3. Корнями многочлена локаторов ошибок σ(x) являются x1 = α14, x2 = α10, поэтому X1 = α, X2 = α5.

4. После того как все локаторы ошибок известны, можно воспользоваться формулой Форни для кодов

РС

X−1ω(X−1)

Yi =

i i

, i = 1, 2, . . . , t + s,

где

∏

1 j t+s, j̸=i

i

 

(1 − Xj X−1)

 

 

ω(x) ≡ σ(x)S (x) ≡

≡ α8 + α9x + α13x2 + α12x3 + α3x4 + α6x5 (mod x8).

Находим значения ошибок: Y1 = α6, Y2 = α, Y3 = 0, Y4 = α6, Y5 = α10, Y6 = α11. Таким образом:

e = ( 0, α6, 0, 0, 0, α, 0, 0, 0, α6, α10, 0, α11, 0, 0 ) ,

u = v − e = ( α7, α7, α, 1, α12, α13, α5, 0, α2, α6, α10, α6, α11, α3, 1 ) .

 

1. Декодирование двоичных кодов БЧХ с использованием алгоритма Берлекэмпа — Месси

   В данном параграфе рассмотрим случай только ошибок для возможности применения алгоритма 3.

   На основе алгоритмов 3 и 4 получаем следующий алгоритм декодирования.

   Алгоритм 5 (декодирование двоичного кода БЧХ на основе алгоритма Берлекэмпа — Месси). Вход: полученный вектор v.

   Выход: исходный кодовый вектор u, если произошло не более [(d − 1)/2] ошибок.

   1. Определяется t = [(d − 1)/2]. Находятся компоненты S0, S1, . . . , S2t−1 синдромного вектора: Si =

      = v(αi+1), i = 0, 1, . . . , 2t − 1. Если синдромный вектор нулевой, то алгоритм завершается и

      возвращается u = v.

   2. Для последовательности S0, S1, . . . , S2t−1 с помощью алгоритма 3 находится многочлен локаторов ошибок σ(x). Пусть l = deg σ(x).

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

      Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 55

       

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

      У вектора v из символа с номером ij , Xj = αij , вычитается 1, j = 1, . . . , l. Тем самым получается вектор u.

       

      Пример 2. Пусть поле GF (24) порождается примитивным многочленом p(x) = x4 + x + 1 (см. пример 1), код БЧХ длины n = 15 порождается многочленом:

      g(x) = 1 + x + x2 + x4 + x5 + x8 + x10.

      В данном случае k = 15 − 10 = 5. Подряд идущици корнями многочлена g(x) будут:

      α, α2, α3, α4, α5, α6.

      Поэтому конструктивное расстояние данного кода равно d = 7, т. е. код гарантированно может исправлять до трех ошибок.

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

      v = ( 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0 ) ,

      в котором не более трех ошибок. Данный вектор соответствует многочлену

      v(x) = 1 + x + x4 + x7 + x8 + x10 + x12 + x13.

      Вычисляем

       

      S0 = v(α) = 1 + α + α4 + α7 + α8 + α10 + α12 + α13 = α7, S2 = v(α3) = 1 + α3 + α12 + α6 + α9 + 1 + α6 + α9 = α10, S4 = v(α5) = 1 + α5 + α5 + α5 + α10 + α5 + 1 + α5 = 1, S1 = S2 = α14, S3 = S2 = α13, S5 = S2 = α5.

      0 1 2

      Применим к этой последовательности алгоритм 3

       

      r	∆	σ(x)	b(x)	L
      0		1	1	0
      1	α7	1 + α7x	α8	1
      3	α7	1 + α7x + x2 α8 + x		2
      5	0	1 + α7x + x2 α8x2 + x3		2

      Поэтому многочлен локаторов ошибок имеет вид

      σ(x) = 1 + α7x + x2.

      Находим корни многочлена σ(x): x1 = α14, x2 = α. Поэтому

      X1 = x−1 = α, X2 = x−1 = α14,

      1 2

      e = ( 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ) ,

      u = v − e = ( 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 ) .

       

2. Декодирование обобщенных кодов Рида — Соломона с использованием алгоритма Берлекэмпа — Месси

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

Пусть α = (α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)), (17) где b(x) — информационные многочлены над полем F степени не выше k − 1. Кодовое расстояние кода

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

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

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

56Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

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

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

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

1 m стирания

 

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

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

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

, . . . ) ×

S =

1 m+s

 

 1	1	. . .	1	 	w0	0	. . .	0
×  α0	α1	. . .	αn−1	 	0	w1	. . .	0
 . . .  αn−k−1 0	. . . αn−k−1 1	. . . . . .	. . .     αn−k−1 n−1		. . . 0	. . . 0	. . . . . .	. . . wn−1

 

T



,

 





 

Sj = Z1Xj + . . . + ZmXj

+ Zm+1Xj

+ . . . + Zm+sZj ,

1 m

j = 0, 1, . . . , 2t + s − 1,

m+1

m+s

многочлен

 

 

 

где X1 = αi1 ,. . . , Xm = αim — неизвестные локаторы ошибок, Xm+1 = αim+1 ,. . . , Xm+s = αim+s — известные локаторы стираний, Y1 = ei1 , . . . , Ym+s = eim+s — значения ошибок в векторе v, Zj = Yjwij , j = 1, . . . , m+s. Пусть σ(x) — это многочлен неизвестных локаторов ошибок, ν(x) — известных локаторов стираний. Полагая

2t+s−1 m s

S(x) =

∑ Sixi,

S (x) = S(x)ν(x),

 

 

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

i=0

 

m+s

i=1

m+s

i=1

i

 

ω(x) = ∑ Z ∏

 

(1 − Xjx),

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) ≡ ω(x) (mod x2t+s), (18)

 

 

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

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.

 

 

Так как в сравнении (18) 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

 . (20)



 

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

 

 



 



 

  . . .  



 

. . . 

S s+2t−2

S s+2t−3 . . .

S s+2t−m−1 σm

−S s+2t−1

 

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

S s,

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

Доказательство аналогично доказательству теоремы 5. D

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

Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 57

 

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

Вход: принятый вектор 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) (если s = 0, то S (x) = S(x)).

    

2. На вход алгоритма 1 подается последовательность

   S s,

   S s+1,. . . ,

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

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

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 , например, с помощью формул Форни для ОРС кодов:

      ω(X−1)

      

      Zj = j

      , j ∈ M. (21)

      ∏

      i∈M\{j}

      j

       

      (1 − XiX−1)

       

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

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

       

       

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

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

      p p i векторе

       

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

      p

       

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

       

   2. Если условие 4.1 не выполнено, то пусть:

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

 

 

По формуле (21) находятся значения Zj , затем значения ошибок Yj = Zj/wij , j ∈ M . У вектора v из ij -го символа, Xj = αij , вычитается значение Yj , j ∈ M . При этом получается

вектор u.

 

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

 

 

 

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

 

7. Декодирование кодов Гоппы с использованием алгоритма Берлекэмпа — Месси

Определение кода Гоппы опирается на два объекта: многочлен G(x) с коэффициентами из поля

−

 

GF (qm), который называется многочленом Гоппы; подмножество L = {α0, α1, . . . , αn

1} элементов поля

GF (qm), таких, что G(αi) ̸= 0 для всех αi ∈ L. Код Гоппы Γ(L, G) состоит из всех векторов u =

= (u0, u1, . . . , un−1) с компонентами из GF (q), для которых

u

 

n−1

Ru = ∑ i

≡ 0 (mod G(x)).

i=0

x − αi

Если G(x) неприводим, то код Γ(L, G) называется неприводимым кодом Гоппы. Множество L называется множеством нумераторов позиций кодового слова. Имеют место следующие оценки параметров для кодов Гоппы (см., напр., [9]).

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

58Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

Теорема 7. Параметры [n, k, d]-кода Γ(L, G) над полем GF (q), где L ⊆ GF (qm), связаны соотношением

n = |L|, k ;? n − mr, r = deg G(x), d ;? r + 1.

Нам понадобится следующее утверждение (см., напр., [1]).

Теорема 8. Код Γ(L, G) представляет собой ограничение кода GRSn−r (L, y) на подполе F = GF (q):

n

Γ(L, G) = GRSn−r (L, y) ∩ F

, где r = deg G(x), y = (y0, y1, . . . , yn−1),

1

yi = G(αi) ∏

αi − αj

, i = 0, 1, . . . , n − 1. (22)

j̸=i

 

Следствие 3. Проверочная матрица кода GRSn−r (L, y), который задает код Γ(L, G), имеет вид

 1 1 . . . 1

  G(α0)−1 0 . . . 0 

1

 α0 α1 . . . αn−1  

0 G(α1)−

. . . 0 



 

 

 

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



 

. . . . . . . . . . . .  ,

αr−1

r−1

r−1 −1

0 α1 . . . αn−1

0 0 . . . G(αn−1)

т. е. совпадает с проверочной матрицей кода Γ(L, G).

Таким образом, код Γ(L, G) можно задать с помощью обобщенного кода Рида — Соломона.

Пусть код Γ(L, G) является двоичным. Если G(x) не имеет кратных корней, то код Γ(L, G) называется сепарабельным кодом Гоппы. Пусть G(x) — полный квадрат некоторого многочлена над GF (2m) наименьшей степени, делящийся на G(x). В случае сепарабельного кода G(x) = G2(x). Для минимального расстояния сепарабельного кода Γ(L, G) верна оценка d ;? 2r + 1 и выполнено равенство Γ(L, G) = Γ(L, G) (см., напр., [9]). Эти факты позволяют строить сепарабельный код Γ(L, G) = Γ(L, G), а некоторые алгоритмы декодирования кодов Гоппы применять относительно кода GRSn−2r (α, y), r =

= deg G(x).

Пусть [n, k, d]-код Γ(L, G) задается на основе ОРС кода: Γ(L, G) = GRSn−r (L, y) ∩ F

n, F = GF (q),

r = deg G(x), k = n − r — размерность кода GRSn−r (L, y) длины n, H — проверочная матрица кода

GRSn−r (L, y). Пусть d, d — кодовые расстояния кодов Γ(L, G) и GRSn−r (L, y) соответственно. Так как

d ;? r + 1,

d = n − k + 1 = r + 1, то если в кодовом векторе u ∈ Γ(L, G) произошло t ошибок и s

стираний, причем r ;? 2t + s, то для его декодирования можно применять алгоритмы декодирования

для ОРС-кодов.

Если же код Γ(L, G) двоичный и сепарабельный, то Γ(L, G) = GRSn−2r (L, y) ∩ F

n, F = GF (2), k =

= n − 2r — размерность кода GRSn−2r (L, y), H — проверочная матрица кода GRSn−2r (L, y). Также

−

 

d ;? 2r + 1, Γ(L, G2) ⊆ GRSn

2r (L, y),

d = 2r + 1, поэтому в этом случае алгоритмы декодирования для

ОРС-кодов можно применять для декодирования вектора u, в котором t ошибок и s стираний, причем

2r ;? 2t + s.

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

Вход: принятый вектор v.

Выход: исходный кодовый вектор u, в котором произошло s стираний и не более t ошибок, если r ;? 2t + s, r = deg G(x), u ∈ Γ(L, G) ⊆ GRSn−r (L, y) (для двоичного сепарабельного кода 2r ;? 2t + s, u ∈ Γ(L, G) ⊆ GRSn−2r (L, y)).

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

   T

    

    

   S0, S1, . . . , S2t+s−1 синдромного вектора vH

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

    

   . Если они все равны нулю, то возвращается вектор

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

   многочлена

   S (x) (если s = 0, то S (x) = S(x)).

2. На вход алгоритма 1 подается последовательность

   S s,

   S s+1,. . . ,

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

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

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

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

   Vestnik of Samara University. Natural Science Series. 2021, vol. 27, no. 1, pp. 44–61 59

    

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

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

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

       

       

      — множество индексов локаторов ошибок и стираний без учета индекса p. Находятся Zj , j ∈ M , например, с помощью алгоритма Форни (21) для обобщенных кодов РС. После этого находятся значения ошибок Yj = Zj G(Xj ), j ∈ M . У вектора v из ij -го символа, Xj =

      p

       

      ij j ∈

       

      i стираний

       

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

       

      p

       

      матрицы H. Вычисляется значение ошибки Yp = ZpG(αi). Осталось в векторе u из i-го символа вычесть Y .

      j ij j

       

       

       

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

0

 

0 0 i алось

 

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

 

 

Пример 3. Рассмотрим расширение поля GF (2) ⊂ GF (24), где поле GF (24) строится на основе примитивного многочлена p(x) = x4 + x + 1 и рассматривалось в примере 1. Пусть L = GF (24) =

= {0, 1, α, α2, . . . , α14}, G(x) = x2 + x + α3. Так как след элемента α3 в поле GF (24) не равен нулю, то

многочлен G(x) в этом поле не имеет корней. Поэтому из неприводимости G(x) над GF (24) следует,

что код Γ(L, G) является сепарабельным, поэтому он может исправлять до двух ошибок, либо одну ошибку и до двух стираний, либо до четырех стираний. Проверочная матрица H кода Γ(L, G) примет такой вид:

( G(0)−1 G(1)−1 G(α)−1 . . . G(α14)−1 )

H = 0G(0)−1 1G(1)−1 αG(α)−1 . . . α14G(α14)−1 =

( α12 α12 α4 α3 α9 α4 α α8 α6 α3 α6 α α2 α2 α8 α9 )

= 0 α12 α5 α5 α12 α8 α6 α14 α13 α11 1 α11 α13 α14 α6 α8 =

 

 

	1	1	1	0	0	1	0	1	0	0	0	0	0	0	1	0 
	1	1	1	0	1	1	1	0	0	0	0	1	0	0	0	1 
 	1	1	0	0	0	0	0	1	1	0	1	0	1	1	1	0  
 	1	1	0	1	1	0	0	0	1	1	1	0	0	0	0	1   .
 	0	1	0	0	1	1	0	1	1	0	1	0	1	1	0	1	 
 	0	1	1	1	1	0	0	0	0	1	0	1	0	0	0	0	 
 	0	1	1	1	1	1	1	0	1	1	0	1	1	0	1	1	 
	0	1	0	0	1	0	1	1	1	1	0	1	1	1	1	0

 

=

 

Так как все строки матрицы H линейно независимы, то n − k = 8, k = 8. Выписав построчно

	1	0	1	1	0	1	1	1	0	0	0	0	0	0	0	0	
	1	0	0	1	0	1	0	0	1	1	0	0	0	0	0	0	
 	1	1	1	0	0	1	0	0	1	0	1	0	0	0	0	0	 
 	0	1	0	1	1	1	0	0	1	0	0	1	0	0	0	0	  .
 	0	0	1	0	1	1	1	0	1	0	0	0	1	0	0	0	 
 	0	1	0	0	1	1	1	0	0	0	0	0	0	1	0	0	 
 	1	0	1	0	1	1	0	0	0	0	0	0	0	0	1	0	 
	1	1	0	1	0	0	1	0	0	0	0	0	0	0	0	1

 

фундаментальную систему решений системы однородных линейных уравнений HX = O, находим порождающую матрицу кода Γ(L, G):

 

G =

 

В данном случае Γ(L, G) ⊆ GRS12(L, y), при этом проверочная матрица H кода GRS12(L, y),

учитывая следствие 3, имеет вид

 α9 α9 α8 α6 α3 α8 α2 α α12 α6 α12 α2 α4 α4 α α3 

H = 

0 α9 α9

α8 α6

α12 α7

α7 α4

α14 α6

α12

1 α α14

2

 

α  .



 



 

 0 α9 α10 α10 α9 α α12 α13 α11 α7 1 α7 α11 α13 α12 α 

0 α9 α11 α12 α12 α5 α2 α4 α3 1 α9 α2 α7 α10 α10 1

Рацеев С.М., Лавриненко А.Д., Степанова Е.А. Об алгоритме Берлекэмпа — Месси и его применении...

60Ratseev S.M., Lavrinenko A.D., Stepanova E.A. On the Berlekamp — Massey algorithm and its application...

 

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

v = (1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1),

в котором до двух ошибок (как видно, стирающих символов в принятом векторе нет).

Для декодирования принятого вектора применим алгоритм 7.

T

1. Определяем s = 0, t = deg G(x) = 2. Находим синдромный вектор S = vH =

   = ( α9, α9, α10, α6 ) .

2. Применяя к данной последовательности алгоритм Берлекэмпа — Месси 1, получаем σ(x) = 1 +

   + α2x + α9x2.

3. Корнями многочлена σ(x) являются x1 = α12, x2 = α9, поэтому X1 = x−1 = α3 = α4, X2 = x−1 =

   1 2

   = α6 = α7. Следовательно, ошибки произошли на 4-й и 7-й позициях.

4. Так как код двоичный, то исходный кодовый вектор равен:

u = (1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1),

при этом длина LFSR совпадает с deg σ(x), поэтому на позиции с номером 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.

A. D. Lavrinenko

Ulyanovsk State University

Email: anutalavrinenko@gmail.com
ORCID iD: 0000-0003-3652-1097

student of the Department of Information Security and Control Theory

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

E. A. Stepanova

Ulyanovsk State University

Email: kate_stepanova@bk.ru
ORCID iD: 0000-0003-0276-1615

student of the Department of Information Security and Control Theory

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

References

Supplementary files