Методы обработки информации. Крюкова Л.К - 18 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

18
1.2. Быстрое преобразование Фурье [2]
Для ускорения вычислений ряд данных последовательно расщеп'
ляется сначала на два вспомогательных, затем на четыре и так до тех
пор, пока не остается ряд из одного, двух или трех членов.
Наилучшим выбором числа отсчетов является в данном случае
число, равное степени двух.
Пример: x
i
, i = 0, …, 11.
Создаем два ряда:
y
t
= x
0
, x
2
, x
4
, x
6
, x
8
, x
10
;
z
t
= x
1
, x
3
, x
5
, x
7
, x
9
, x
11
.
Затем ряды y
t
и z
t
расщепляем еще на два ряда каждый:
y
t
¢ = x
0
, x
4
, x
8
; y
t
² = x
2
, x
6
, x
10
;
z
t
¢ = x
1
, x
5
, x
9
. z
t
² = x
3
, x
7
, x
11
.
Для этих рядов легко найти преобразование Фурье по формулам дис'
кретного преобразования Фурье.
Например:
y
0
¢
(3)
= 1/3 (x
0
+ x
4
+ x
8
); y
1
¢
(3)
= А
1
(3)
– jB
1
(3)
,
где А
1
(3)
= 1/3 (x
0
cos2p/3 + x
4
cos4p/3 + x
8
cos6p/3);
B
1
(3)
= 1/3 (x
0
sin2p/3 + x
4
sin4p/3).
Аналогично получаем преобразования:
y
2
¢
(3)
, z
0
¢
(3)
, z
1
¢
(3)
, z
2
¢
(3)
;
y
0
²
(3)
, y
1
²
(3)
, y
2
²
(3)
, z
0
²
(3)
, z
1
²
(3)
, z
2
²
(3)
.
Из указанных преобразований формируем гармоники y
r
(6)
, z
r
(6)
, r =
0, 1,... 5; в соответствии с формулой БПФ:
x
r
(N)
= 1/2 exp[j(2pir/N)]y
r
(N/2)
+ 1/2 z
r
(N/2)
И
x
r+(N/2)
(N)
= –1/2 exp[j(2pir/N)]y
r
(N/2)
+ 1/2 z
r
(N/2)
для 0 £ r £ N/2–1.
Используя те же формулы, получим окончательно преобразование
x
r
(12)
, r = 0, 1,...11.

Страницы