Скользящие теоретико-числовые преобразования Рейдера
5
а
(
)
(
)
(
)
(
)
1
1
1
1
2
,0
1
2 1
1
2
,1
1
2 1
,...,
2 2
... 2
,
,...,
2 2 2
... 2
.
m
m
m m
m
m
m
m m m
m
m
m
x
j i
x j
i
x
j i
x j
i
−
−
−
λ λ
−
−
−
λ λ
−
− = − − λ − − λ − λ
− = − − − λ − − λ − λ
(6)
Все операции в выражениях (4) и (5) выполняются по модулю
(
)
/2
2 1 .
N
+
Если в алгоритме (4)–(6) индекс
m
изменять от 1 до
n
–1, то с его
помощью можно описать полный алгоритм БТЧП. При этом выпол-
няемые на последнем уровне прореживания двухточечные ТЧП
Рейдера будут содержать только операции сложения и вычитания,
поскольку используемые в этом случае множители
( 1)
1 1
2
n
n n
i k
−
− −
сравнимы с
1
±
по модулю
(
)
/2
2 1
N
+
. Для вычисления спектра
необходимо
m
менять в обратном направлении от
n–
1 до 1. Тогда из
этого алгоритма будет получено описание итерационного процесса
вычисления искомого теоретико-числового спектра при начальных
данных, получаемых из соотношений (6) путем подстановки
1
m n
= −
.
Процесс вычисления спектра по полному статическому алго-
ритму БТЧП Рейдера полезно иллюстрировать графически с помо-
щью сигнального ориентированного графа. Такой граф имеет пря-
моугольный вид и содержит
(
)
1
n
+
вертикальных уровней по
N
уз-
лов в каждом уровне. Узлы на первом (крайнем слева) уровне
предназначены для хранения отсчетов сигналов, а узлы на послед-
нем служат для формирования значений вычисляемого спектра. Все
остальные узлы используются для вычисления промежуточных
спектров. В вычислительных узлах осуществляется операция сло-
жения двух операндов, которые поступают из других узлов по вет-
вям графа, причем без изменения знака по ветвям, обозначенным
сплошной линией, и с изменением знака на обратный по ветвям,
обозначенным пунктирной линией. Двоично-экспоненциальные
константы, на которые умножаются результаты вычисления в узлах,
указываются около этих узлов. Все вычислительные узлы имеют по
два входа и два выхода и по форме изображения напоминают ба-
бочку. Подобная «бабочка» является типовой операцией в БПФ Ку-
ли – Тьюки по основанию 2 для комплексного экспоненциального
базиса [7, 8].
Полный статический алгоритм БТЧП Рейдера потребует выпол-
нения вещественных сложений
б
А
и умножений
б
M
:
(
)
б
2
б
2
log ,
log 1 / 2,
А N N M N N
=
=
−
(7)
