ВУЗ:
Составители:
55
После небольших преобразований:
+
=
∑∑
−
=
+
−
=
12/
0
2/
2
12
2
12/
0
2/
2
2
2/
1
22/
1
2
1
N
k
N
nk
i
k
N
n
i
N
k
N
nk
i
kn
ef
N
e
ef
N
F
π
π
π
(9.10)
Каждая из сумм теперь соответствует самостоятельному ДПФ с вдвое меньшим
числом точек. Общее число арифметических операций при таком представлении
уменьшилось примерно вдвое.
Если
2/N
тоже четное число, то операцию разбиения каждой суммы на две
можно повторить. Наиболее выгодным для практической реализации будет случай
p
N 2=
, обычно именно он и подразумевается, когда говорят о быстром
преобразовании Фурье (БПФ). Рассмотрим практическую реализацию БПФ для
16=N
. Посмотрим как будут группироваться точки при каждом разбиении
{ }
k
f
на
четные и нечетные:
Таблица 1. Группировка узлов для быстрого преобразования Фурье.
0
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15
f
0
f
2
f
4
f
6
f
8
f
10
f
12
f
14
f
1
f
3
f
5
f
7
f
9
f
11
f
13
f
15
f
0
f
4
f
8
f
12
f
2
f
6
f
10
f
14
f
1
f
5
f
9
f
13
f
3
f
7
f
11
f
15
f
0
f
8
f
4
f
12
f
2
f
10
f
6
f
14
f
1
f
9
f
5
f
13
f
3
f
11
f
7
f
15
f
Введем
r
- новый индекс точки, который нумерует слева направо точки из
нижней строки таблицы. Последовательность
,...4,3,2,1,0=r
будет соответствовать
последовательности
,...10,2,12,4,8,0=k
. Заметим, что в бинарном представлении числа
r
и
k
будут «зеркальными», т.е. одно получается из другого перестановкой битов в
обратном порядке.
В итоге ДПФ по
16=N
точкам сводится к сумме восьми ДПФ по
2=N
точкам.
Двухточечное ДПФ:
( )
( )
10
1
0
2
2
1
2
1
2
1
ffefF
n
k
nk
i
kn
−+==
∑
=
π
,
1,0=n
(9.11)
Или
( )
100
2
1
ffF +=
,
( )
101
2
1
ffF −=
(9.12)
После небольших преобразований: n 2πi 1 1 N / 2−1 2πi nk e N 1 N / 2−1 2πi nk Fn = ∑ 2 N / 2 k =0 f 2k e N /2 + ∑ 2 N / 2 k =0 f 2 k +1e N /2 (9.10) Каждая из сумм теперь соответствует самостоятельному ДПФ с вдвое меньшим числом точек. Общее число арифметических операций при таком представлении уменьшилось примерно вдвое. Если N / 2 тоже четное число, то операцию разбиения каждой суммы на две можно повторить. Наиболее выгодным для практической реализации будет случай N = 2p , обычно именно он и подразумевается, когда говорят о быстром преобразовании Фурье (БПФ). Рассмотрим практическую реализацию БПФ для N = 16 . Посмотрим как будут группироваться точки при каждом разбиении { f k } на четные и нечетные: Таблица 1. Группировка узлов для быстрого преобразования Фурье. f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f0 f2 f4 f6 f8 f10 f12 f14 f1 f3 f5 f7 f9 f11 f13 f15 f0 f4 f8 f12 f2 f6 f10 f14 f1 f5 f9 f13 f3 f7 f11 f15 f0 f8 f4 f12 f2 f10 f6 f14 f1 f9 f5 f13 f3 f11 f7 f15 Введем r - новый индекс точки, который нумерует слева направо точки из нижней строки таблицы. Последовательность r = 0,1,2,3,4,... будет соответствовать последовательности k = 0,8,4,12,2,10,... . Заметим, что в бинарном представлении числа r и k будут «зеркальными», т.е. одно получается из другого перестановкой битов в обратном порядке. В итоге ДПФ по N = 16 точкам сводится к сумме восьми ДПФ по N = 2 точкам. Двухточечное ДПФ: ( ) nk 1 1 2πi Fn = ∑ f k e 2 = f 0 + (− 1) f1 , n = 0,1 1 n (9.11) 2 k =0 2 Или F0 = 1 ( f 0 + f1 ) , F1 = 1 ( f 0 − f1 ) (9.12) 2 2 55
Страницы
- « первая
- ‹ предыдущая
- …
- 53
- 54
- 55
- 56
- 57
- …
- следующая ›
- последняя »