Để sừ dụng thuật toán số điểm N phải thõa
Nếu không thõa đk trên, ta thêm một vài giá trị zero (điều này không làm ảnh
hưởng đến kết quả)
I. Thuật toán FFT cơ số 2 phân chia theo thời gian:
FFT cơ số 2 cho một tầng:
Các giá trị x(n) được ghi vào một mảng hai chiều như sau:
1
2
( ) : (0) (2) (4) ..... ( - 2)
( ) : (1) (3) (5)...... ( 1)
f n x x x x N
f n x x x x N -
Ta được hai dãy mới
gồm các giá trị của
với n chẵn
gồm các giá trị của
với n lẻ
Tính DFT- N/2 điểm cho
và
ta được:
1 1
/2
2 2
/2
( ) ( )
( ) ( )
DFT
N
DFT
N
f n F k
f n F k
¬ ¾ ¾®
¬ ¾ ¾®
Kết quả
1 2
1 2
( ) ( ) ( ) 0,1, 2... 1
2
( ) ( ) ( ) 0,1, 2... 1
2 2
k
N
k
N
N
X k F k W F k k
N N
X k F k W F k k
= + = -
+ = - = -
Với mỗi dãy
và
tiếp tục chia làm hai dãy con cho đến khi chỉ còn
tính DFT cho 2 điểm.
Mô hình cho N=8
Số tầng cần thực hiện
评论0