Введение в численные методы. Дулов Е.Н. - 55 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

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
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

Страницы