О многомерном аналоге алгоритма Кули-Тьюки
Автор: Старовойтов Андрей Владимирович
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Математика, механика, информатика
Статья в выпуске: 1 (27), 2010 года.
Бесплатный доступ
Представлено применение рекуррентных последовательностей ортогональных базисов на n -мерный случай для вывода формул варианта быстрого n -мерного преобразования Фурье, использующего 2п-1 / 2п × Nnlog2N комплексных умножений и nNnlog2N комплексных сложений, где N = 2s - число отсчетов по одной из осей
Пространство сигналов, последовательность ортогональных базисов, многомерное дискретное преобразование фурье
Короткий адрес: https://sciup.org/148176151
IDR: 148176151
Текст обзорной статьи О многомерном аналоге алгоритма Кули-Тьюки
Рекуррентные последовательности ортогональных базисов в пространстве сигналов хорошо изучены [1] и имеют многочисленные приложения, в том числе для получения формул быстрого преобразования Фурье.
В данной работе обобщение рекуррентных последовательностей ортогональных базисов на n -мерный случай применяется для вывода формул варианта быстрого n -мерного преобразования Фурье ( n БПФ), использую-
Определение 2 . Единичным n -мерным периодическим, с периодом N по каждой переменной, импульсом назовем сигнал 5 N такой, что 5 N ( j ) = 1, если каждая координата вектора j делится на N и 5 N ( j ) = 0 в противном случае.
Для единичного импульса справедливы следующие утверждения, вытекающие сразу из определения.
2 ”■ щего — 2
-
n
-N ” log2 N комплексных умножений и
-
1. 5 N (f,..., j ) = 5 N (Ш
-
2. 5 N (f,..., j ) = 5 N (f) ■ .
. -5 N ( j n );
nN” log2 N комплексных сложений, где N = 2 s - число отсчетов по одной из осей (известный в литературе, см., например [2]). Этот вариант n БПФ содержит меньшее число операций комплексного умножения, чем обычно применяемый, в котором многомерное преобразование Фурье осуществляется повторным применением одномерных БПФ (см., например, [3; 4]).
При построении n -мерных реккурентных последовательностей ортогональных базисов мы придерживаемся схемы изложения, предложенной в [1] для одномерного случая.
Пространство периодических n -мерных сигналов. Для полноты изложения мы приводим определения и основные утверждения из теории многомерных сигналов, которые будем использовать далее.
Определение 1 . При фиксированном N будем называть n -мерным периодическим сигналом периодическую, с периодом N по каждой переменной, комплекснозначную функцию целочисленного аргумента.
Вместе с операциями сложения двух сигналов x р x 2:
У ( j ) = x 1( j ) + x 2( j )
и умножения сигнала x на комплексное число с :
У(j ) = c ■x (j ), где x(j') - отсчет сигнала x в точке j е Z”, множество сигналов CN становится линейным комплексным пространством. Нулевым элементом в CN является сигнал O такой, что O( j) = 0 при всех j е Z”. Введем в CN скалярное произведение и норму:
|| x||= (x,xГ, где Bn (N) - множество целочисленных векторов из [0, N -1]”.
3. Для
x
е
C
N
справедливо равенство
x
(
j
) =
S
x
(
t
)
5
N
(
j
-
t
) 1
t е Bn
(
N
)
при любом
j е B
n
(
N
).
/2п
ix
m
Пусть
W
N
= exp(
N
-). Тогда справедлива
лемма 1
:
5
N
(
j ) =
^n;
S
^
^ t
)
,
N
t е Bn
(
N
)
* Работа поддержана грантом РФФИ 07-01 -00326.
где (
j
,
t
) - скалярное произведение векторов
j
и
t
.
Равенство (2) проверяется непосредственно.
Определение 3
.
n
-кратным дискретным преобразованием Фурье (ДПФ) называется отображение
F
N
: C
N
^
C
N
, сопоставляющее с сигналом
x
сигнал
X
со значениями
X
(
j
)=
S
x
(
t
)
w
Nj
)
,
j е B
”
(
N
).
t е Bn
(
N
)
Отметим, что для ДПФ справедлива формула обращения
x
(
t
S
X
(
j
)
■
)
N
j е Bn
(
N
)
и равенство Парсеваля: если
X
=
F
N
(
x
),
Y
=
F
N
(
y
), то
<
x
,
У
) =
N
<
X
,
Y
X
Рекуррентные последовательности ортогональных базисов.
Положим
N
= 2
s
,
N
v
= 2
s
-
v
,
Av
= 2
v
-
1
. Построим рекуррентную последовательность базисов
f
,
,
f
,...,
f
s
, где
f
t
-
t
-й базис, состоящий из
N
”
сигналов
f
t
(
k
),
k е Bn
(
N
). Значение сигнала
f
t
(
k
) в отсчете
j
= (f, -,
j
n
),
j е B
”
(
N
) будем обозначать, как
f
t
(
k
;
j
).
Обозначим через
B
”
(
N
) множество целочисленных векторов из [0,
N
v
-
1]
”
, а через
B
n
(
N
) множество целочисленных векторов из [0,
Av -
1]
”
. Определим последовательность ортогональных базисов следующим образом:
f
,
(
k
;
j
) =
5
N
(
j
-
k
)
=
= 5
N
(
jx
-
k
)
5
N
(
j
2
-
k
2M
N
(
j
-
k
„
),
k
,
j
g
В
ПN
)
;
fv
(
11
+°
1
A
v
+
P
1
A
v
+1
,
1
2
+°
2
A
v
+
+
P
2
A
v
+1
,
- 1
n
+C
n
A
v
+
P
n
A
v
J
=
n
1 1
E
^ ‘i+o l
A
v
)
=e-z w::.
т =0 т =0 1
n
X
f
v
-1(
1
1
+
2
A
v
P
1
+T
1
A
v
, ■ ■ ■ ,
l
n
+
2
A
v
P
n
+T
n
A
v
X
N
A
v
+1-
1
A
v
+1-
1 E-rev
v
(
qi)
= < E... Ewa=+1 f0(q1+P1Av+1,...,qn+PnAv+1), q1=0 qn =0 N
A
v
+1 -
1
A
v
+1 -
1
E
1i
rev
v
(
qi
)
E ... E wA=+1 f0(q‘+P1‘Av+1, ■■■, qn + P‘Av+1» = q1=0 qn=0 где p = ( P1, ■■■, Pn)g вП( N);1 = ( l1, ■■■, ln) g Bn2( N); Qi равно 0 или 1 при всех i = 1,..., n; v = 1,..., s. Для изучения свойств рекуррентной последовательности базисов полезно использовать понятие реверсной перестановки [1].
Пусть
j
- целое число из множества
J
= {0,1, ■■■,2
v
-
1} представимо в двоичной системе в виде
jv
-
12
v
'
+
...
+
j12
+
j
0 где
j
i
=0,1 для все
х
i
= 0,...,
v
-
1. Вектор (
jv
-
1,...,
j j
0)2 будем называть двоичным кодом числа
j
. Сопоставим c числом
j
число
j1
g
J
, которое задается двоичным кодом (
j
0
,
j
...,
j
v
-1
)
2
. Перестановка rev
v
(
j
) =
jx
множества
J
называется реверсной. Для реверсной перестановки справедливы равенства:
2rev
v
-1
(
q
) = rev
v
(
q
);
2rev
v
-1
(
q
)
+
1 = rev
v
(
A
v
+
q
X
(4)
A
v
+1 -
1
A
v
+1 -1A
v
+1 -
1
A
v
+1 -
1
E
1
i
rev
v
(
qi
)
-
1i
rev
v
(
qi
)
W
{=1
A
v
+1
×
x 5
N
(
q
1
-
q
‘+
(
P
1
-
P
‘
)
A
v
+1
, ■■■
,
q
n
-
q
n
+
(
P
n
-
P
n
)
A
v
+1
).
Аргументы единичного импульса
5
NN
по модулю не превосходят
N
-
1. При
Pt
=
P’
при некотором
t
аргу
менты отличны от нуля при всех
q
i
,
q
i
‘
g
0:
Av+
1
-
1,
i
= 1, ...,
N
, поскольку |
q
i
-
q
i
’
|
< A
v
+
1
-
1.
<
fv
(
k
),
fXk
j> =
0
при
P
j
+
P
‘J
.
Пусть
P
j
=
P
J
при всех
j
= 1,...,
n
, тогда
n
<
f
,
(
k
),
f
v
(
k
')
)
A
v
+1 - A
v
+1 -
E
(
1i" 1i
)rev
v
(
qi)
e
...
e
w
a
::.
q
1=
0
qn
=
0
Значит, Используя реверсную подстановку, легко показать, что
f
v
(
1
1
+
P
1
A
v
+1
,...,
l
n
+
P
n
A
v
+1
)
=
n
A
v
+1 ' A
v
+1 '
E
'i1™ v
(
qi
)
= E ... E w-A=+1 fi(q1+ P1Av+1, -> qn+PnAv+1X q1=0 qn =0 где P = ( P1,..., Pn) g Bn( N), 1 = ( 11,..., ln) g B2( N), v = 1,..., s . n
A
v
+1
1
A
v
+1
1
E
qi
=
E
...
E
w
A;
1
=
A
v
+1
...
A
v
+1
5
A
v
+
1 (
1
1
-
1
1
,...,
1
n
-
1
n
).
q
1=
0
qn
=
0
Из последней формулы заключаем, что скалярное произведение
{
fv
(
k
,
fv
(
k
')
)
отлично от нуля только при
Pj
=
P
‘j
,
1
i
=
1
/
при всех
i
,
j
= 1,...,
n
. В последнем случае ||
f
, (
k
1
,...,
k
n
)||=
A
v
+1
...
A
v
+1
=2
nv
при всех
k
1,...,
kn
= 0:
N
-
1. Теорема доказана.
Применение последовательности ортогональных ба-
В частности, при
v
=
s
имеем
N
-1
N
-1
f
s
(
1
;
j
) =
E
...
E
q
1=
0
qn =0
n
E
'i
rev
v
(
qi
-)
w
N
=
× n E?ev j
x5
N
(
j
-
q
1
,..., к
-
q
n
) =
w
N
=
0
Теорема 1
. При каждом
v
= 0,...,
s
система сигналов
f,
=
f
v
(
k
),
k
g
B
n
(
N
), ортогональна и ||
f
, (
k
)||
2
= 2
nv
.
Доказательство. Пусть
v
= 0 . Тогда
<
f
0
(
k
),
f
0
(
k
')
)
=
E
5
N
(
j
-
k
)
-5
N
(
j
-
k
').
j
g
B
n
(
N
)
Последняя сумма может быть отлична от нуля только в том случае, когда
k
=
k
‘
, а в остальных случаях она равна 1, и теорема доказана.
Пусть теперь
v
= 1,...,
s
. Возьмем
k
,
k
‘
g
Bn
(
N
), которые представим в следующем виде:
k = (k1,..., kn) = ( 11 + P1Av+1,..., 1n + PnAv+1X k‘ = (k1’,..., kn) = ( 1; + P’Av+1,..., 1n+ PnAv+1), где 1 = (11,..., 1n) и 1 ‘ = (11‘,..., 1’n) принадлежат Bn2(N), а P = (P1,..., Pn) и P‘ = (P‘,..., Pn) принадлежат Bn(N). Тогда
зисов к быстрому дискретному преобазованию Фурье.
Пусть
x
(
j
) =
x
(
j
;,...,
j
;)
g
C
N
,
j
g
B
n
(
N
). Сопоставим c сигналом
x
(
j
) сигнал
x
0(
j
) =
x
(rev
s
(
jx),
■■■,rev
s
(
j„
)) и разложим
x
0 (
j
) по базису
fv
:
x
0
=
E
x
v
(
k
)
fv
(
k
X (5)
2
k
g
B
n
(
N
)
где -2
nv
- нормирующий множитель. Домножим обе части равенства (5) скалярно на
fv
(
1
), для некоторого
1
g
Bn
(
N
). Тогда
<
x
0
,
f
v
(
1
)
)
=
x
v
(
1
),
x
v
(
k
)=
E
x
0(
j
)
fv
(
k
)
=
j
g
B
n
(
N
)
=
E
x
(
rev
s
(
j
1),
...
,r
ev
s
(
j
n
))
fv
(
k
;
j
)
j
g
B
n
(
N
)
и коэффициенты
x
v
(
k
) в (5) определены.
В частности, при
v
= 0 имеем из (1)
x
0(
k
)=
E
x
(rev
s
(
лх...,
j
g
B
n
(
N
)
r
ev
s
(
j
n
)
5
N
(
j
-
k
) =
x
(
rev
$
(
k
Д ..., rev
$
(
k
n
)).
(6)
Из рекуррентных соотношений (3) имеем:
x
v (
l
1
+ 5
1
A
v
+
P
1
A
v
+1
,
->
l
n
+5
n
A
v
+
P
n
A
V
+1
) =
=
(
x
0
,
fv
(
l
1
+ 5
1
A
V
+
P
1
A
V
+1
, ->
l
n
+ 5
n
A
V
+
P
n
A
v
+1»
=
n
1 1 2^
‘i+aiA v
)
= Z-2 WA=+1 x t, = 0 т = 0 1 n
X<
x
0
, L
-1(
l
1
+
2
A
v
P
1
+T
1
A
v
,
->
l
n
+
2
A
v
P
n
+ T
n
A
v
)
>
=(7)
n
1 1
Z
T
i
(
' i
'
v
)
=
2-2
w
i
',
x
v
-1
x
T1=
0
т
n =0 v
x( l1 + 2A vP1 +T1A v , -, ln + 2A vPn +T n A v )> где p = ( P1,..., Pn) e Bn (N), l = (/„..., ln) e B^( N), v = 1,..., 5,a a,,...,an равно0или 1. Так как xs (k) = x(k1,..., kn) = n
-
2
k
rev
5
(
ji)
= 2 x(rev5(Л)—^5(jn)) ■ WNi=0 = j e Bn (N)
=
2
x
(
j
)
WN
j
e
Bn
(
N
)
∑
kiji i
=0
=
X
(
k
),
где k e Bn (N), то коэффициенты x5 (k) определяют ком поненты спектра сигнала x на основном периоде.
Из (6) и (7) получаем реккурентную схему для вычисления спектра сигнала
x
e
C
nN
:
x
0(
k
) =
x
(rev
5
(
k
Д
-, rev
5
(
kn
));
x
v (
l
1
+ a
1
A
v
+
P
1
A
v
+1
, -,
l
n
+ a
n
A
v
+
Pn
A
v
+1
) =
n
1 1
2
:v a'
v
)
= 2-2 wa=+1 x т1=0 т n =0
x
x
v
-1(
l
1
+
2
A
v
P
1
+T
1
A
v
, -,
l
n
+
2
A
v
P
n
+ T
n
A
v
X где
P
= (
P
1
,...,
P
n
)
e
B
n
(
N
),
l
= (
l„
...,
ln
)
e
B
^(
N
),
v
= 1,...,
5
и
a
1
,...,
a
n
равны0 или 1.
Найдем теперь число операций комплексного сложения и умножения, необходимых для нахождения спектра сигнала по схеме (8). Лемма 2. При некотором r даны векторы t = (tp...,tr) и - = (-р..., -r), где ti,O, e 0,1. Тогдавы-числение всех значений некоторой функции s (o)=2f (t )(-1) Доказательство. Для доказательства применим индукцию по r. Пусть r = 2 . Тогда 1 1 S (g) = S (G1, a2) = 2 2 f (11,12) ■ (- 1)G1 t1 +O2 ‘2 = z1=012=0 = f (0,0) + f (1,0)(-1)G1+ +f (0,1)(-1)G2+ f (1,1)(-1)G1 +°2. Обозначим S1 (a) = S (0,0) = f (0,0) + f (1,0) + f (0,1) + f (1,1) = = (f (0,0) + f (1,0)) + (f (0,1) + f (1,1)) = S * + S 3*; S 2(a) = S (1,0) = f (0,0) - f (1,0) + f (0,1) - f (1,1) = = (f (0,0) - f (1,0)) + (f (0,1) - f (1,1)) = S 2 + S4; S 3(a) = S (0,0) = f (0,0) + f (1,0) - f (0,1) - f (1,1) = = (f (0,0) + f (1,0))-(f (0,1) + f (1,1)) = S* -S*; S1 (a) = S (0,0) = f (0,0) - f (1,0) - f (0,1) + f (1,1) = = (f (0,0) - f (1,0)) - (f (0,1) - f (1,1)) = s 2* - s4, где S* = f(0,0) + f(1,0); S* = f(0,0)- f(1,0); S3* = f (0,1) + f (1,1); S4= f (0,1) - f (1,1). Для вычисления S*, i = 1, 2, 3, 4 требуется применить четыре сложения (вычитания), а для вычисления всех значений S требуется восемь таких операций, и утверждение леммы верно. Пусть утверждение леммы верно при r = k, т. е. для произвольной функции g(t) все значения функции
