Скользящие теоретико-числовые преобразования Рейдера
9
c
2(
1)
A N
= −
,
c
2
1 log
M N
N
= − −
(10)
и хранения
c
2
(log 1) / 2
Q N N
=
−
значений промежуточных спектров с предыдущих шагов скольже-
ния. Сравнение зависимостей (7) и (10) показывает, что учет резуль-
татов предыдущих расчетов позволяет в скользящих БТЧП Рейдера
более чем в
n
/2 раз сократить число сложений и
( 1) / 2
n
−
раз — чис-
ло умножений.
Полученные скользящие алгоритмы БТЧП являются рекуррент-
ными, но нерекурсивными алгоритмами. Поэтому в них не накапли-
ваются погрешности округлений, а на текущем шаге кроме текущего
спектра вычисляются значения промежуточных спектров, которые
необходимы для функционирования алгоритма на последующих ша-
гах скольжения. Эти алгоритмы также целесообразно иллюстриро-
вать графически в виде сигнальных графов, которые при этом будут
содержать меньшее число узлов и поэтому иметь не прямоугольный,
а усеченный, трапецеидальный вид.
Пример 2.
Записать скользящий БТЧП Рейдера для
8
N
=
, дать
его графическую иллюстрацию и оценить сложность.
Решение.
Поскольку
3
n
=
, то алгоритм (9) будет иметь два уров-
ня прореживания. На втором уровне
2
(
2),
0, 1
m k
= =
:
2
(1)
(2)
(2)
2
2
2
2 2
( )
( ) 2
( ) (mod17),
k
j
j
j
X k X k
X k
−
≡
+
2
(1)
(2)
(2)
2
2
2
2 2
(
2)
( ) 2
( ) (mod17),
k
j
j
j
X k
X k
X k
−
+ ≡
−
2
(2)
2
( ) ( ) ( 1) ( 4) (mod17).
k
j
X k x j
x j
= + −
−
На первом уровне
(
)
1
1,
0, 1, 2, 3 :
m k
= =
1
(0)
(1)
(1)
1
1
1
1 1
( )
( )
( ) 2
( ) (mod17),
k
j
j
j
j
X k X k X k
X k
−
=
≡
+
1
(0)
(1)
(1)
1
1
1
1 1
(
4)
(
4)
( ) 2
( ) (mod17).
k
j
j
j
j
X k
X k
X k
X k
−
+ =
+ ≡
−
Сигнальный граф алгоритма изображен на рис. 2. Он содержит 4 уз-
ла, в которых выполняются умножения на константы 2, 4, 8, и 14 уз-
лов с операциями сложения. Для его реализации необходимо сохра-
нить 8 дополнительных данных в виде промежуточных спектров
(1)
(1)
1
2
1
2
( ),
( )
j
j
X k X k
−
−
и
(2)
2 1
( )
j
X k
−
. Промежуточные спектры
(2)
2 1
( )
j
X k
−
не
используются на текущем шаге, но потребуются на следующем
( 1)
j
+
-м шаге скольжения.
