S
λ
(
pq
+
r
) =
p
−
1
X
δ
=0
p
λ
−
1
−
1
X
ν
=0
x
[
ν
+ (
δ
+
p
2
q
+
pr
)
p
λ
−
1
] =
=
p
−
1
X
δ
=0
S
λ
−
1
(
δ
+
p
2
q
+
pr
)
.
Это рекуррентное соотношение и задает алгоритм вычисления эле-
ментов
S
λ
(
b
)
.
Объединяя выражения (28) и (29), получаем общий алгоритм
БОПХ
X
(
μp
n
−
λ
+
m
) =
p
−
1
X
β
=0
S
λ
−
1
(
pm
+
β
)
W
−
μβ
p
,
μ
= 1
,
2
, . . . , p
−
1;
λ
= 1
,
2
. . . , n
;
m
= 0
,
1
, . . . , p
n
−
λ
−
1
,
S
λ
(
pq
+
r
) =
p
−
1
X
δ
=0
S
λ
−
1
(
δ
+
p
2
q
+
pr
)
,
r
= 0
,
1
, . . . , p
−
1;
q
= 0
,
1
, . . . , p
n
−
λ
−
1
−
1
,
(30)
представляющий собой содержащий
n
этапов итерационный процесс
с начальными условиями
S
0
(
pm
+
β
) =
x
(
pm
+
β
)
, β
= 0
,
1
, . . . , p
−
1;
m
= 0
,
1
, . . . , p
n
−
1
−
1
.
(31)
Нулевой спектральный коэффициент в этом случае равен
X
(0) =
S
n
(0) =
p
−
1
X
δ
=0
S
n
−
1
(
δ
)
.
(32)
Для выполнения алгоритма БОПХ (30)–(32) в общем случае необ-
ходимо затратить
A
Б
=
p
(
p
n
−
1) =
p
(
N
−
1)
,
M
Б
= (
p
−
1)(
p
n
−
1) = (
p
−
1)(
N
−
1)
(33)
комплексных сложений и умножений. Алгоритму БОПХ будет соот-
ветствовать сигнальный граф, содержащий
p
(
N
−
1)
вычислительных
узлов и имеющий усеченный трапецеидальный вид.
Пример 10.
Записать алгоритм БОПХ и построить его сигнальный
граф для
N
= 9
.
Решение
. В этом случае
N
= 3
2
и
n
= 2
, поэтому алгоритм БОПХ
будет содержать всего два этапа.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 2 65
