т.е. спектр Хаара легко вычисляется через элементы
S
λ
−
1
(2
m
)
и
S
λ
−
1
(2
m
+ 1)
. Для получения полного алгоритма быстрого преобразо-
вания Хаара (БПХ) остается только найти способ простого определе-
ния самих этих элементов.
В соответствии с выражением (23) элемент
S
λ
(
b
)
на
λ
-м шаге вы-
числений равен
S
λ
(
b
) =
2
λ
−
1
X
α
=0
x
(
α
+
b
∙
2
λ
) =
2
λ
−
1
−
1
X
α
=0
x
(
α
+ 2
b
∙
2
λ
−
1
)+
+
2
λ
−
1
−
1
X
β
=0
x
[
β
+ (2
b
+ 1)
∙
2
λ
−
1
] =
S
λ
−
1
(2
b
) +
S
λ
−
1
(2
b
+ 1)
.
Это соотношение позволяет рекурсивно вычислять все значения эле-
ментов
S
λ
(
b
)
с
λ
= 1
,
2
, . . . , n
при начальных значениях
S
0
(
b
) =
x
(
b
)
,
получаемых из общей формулы (23) при
λ
= 1
и
α
= 0
.
Объединяя результаты, приходим к выводу, что полный спектр Ха-
ара может быть вычислен за
n
этапов рекуррентного решения уравне-
ний
X
(2
n
−
λ
+
m
) =
S
λ
−
1
(2
m
)
−
S
λ
−
1
(2
m
+ 1)
,
S
λ
(
m
) =
S
λ
−
1
(2
m
) +
S
λ
−
1
(2
m
+ 1)
,
λ
= 1
,
2
, . . . , n
;
m
= 0
,
1
, . . . ,
2
n
−
λ
−
1
(24)
при начальных условиях
S
0
(2
m
) =
x
(2
m
)
, S
0
(2
m
+ 1) =
x
(2
m
+ 1)
.
(25)
Нулевой спектральный коэффициент Хаара
X
(0)
при этом будет равен
нулевому значению элемента
S
λ
(0)
на последнем шаге, т.е.
X
(0) =
S
n
(0) =
S
n
−
1
(0) +
S
n
−
1
(1)
.
(26)
Число операций алгебраического сложения, которое необходимо
проводить по этому алгоритму, составляет
A
Б
= 2(2
n
−
1) = 2(
N
−
1)
,
что более чем в
0
,
5 log
2
N
раз меньше по сравнению с числом таких
операций в прямом алгоритме ДПХ. Алгоритм БПХ (24)–(26) можно
проиллюстрировать соответствующим сигнальным графом, содержа-
щим
2(
N
−
1)
вычислительных узлов, в которых выполняются опера-
ции алгебраического сложения, и имеющим усеченный трапецеидаль-
ный вид.
Пример 9.
Записать алгоритм БПХ и построить его сигнальный
граф для
N
= 8
.
62 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 2
