Bài giảng Xử lý tín hiệu số: Chương 6 - TS. Đinh Đức Anh Vũ

dce

2011

Chương 6

Giải thuật cho biến đổi Fourier
(FFT)
BK
TP.HCM

©2011, TS. Đinh Đ ức Anh Vũ

dce

2011

Nội dung
Tính
DFT & IDFT

Tính
trực tiếp

Biến đổi
WN

Lọc
tuyến tính

Chia-Trị

Cơ số 2

Cơ số 4

DSP – Giải thuật cho Biến đổi Fourier

Tách cơ số

Goertzel

Chirp-z

©2011, Đinh Đức Anh Vũ

2

dce

2011

DFT & IDFT
•

Tính DFT: xác định chuỗi N giá trị phức {X(k)} khi biết trước chuỗi {x(n)}
chiều dài N
N −1

DFT

X (k ) = ∑ x(n)WNkn

0 ≤ k ≤ N −1

IDFT

1
x ( n) =
N

0 ≤ n ≤ N −1

n =0
N −1

− kn
X
k
W
(
)
∑
N
k =0

– Giải thuật tính DFT cũng được áp dụng cho việc tính IDFT

•

Tính trực tiếp
– N2 phép nhân phức
– N(N-1) phép cộng phức
→ Độ phức tạp : O(N2)

•

Biến đổi WN
–
–
–
–

2N2 phép tính lượng giác
4N2 phép nhân số thực
4N(N-1) phép cộng số thực
Một số phép toán chỉ số
và địa chỉ để nạp x(n)

DSP – Giải thuật cho Biến đổi Fourier

N −1

2πkn
2πkn
 X R (k ) = ∑ [ xR (n) cos( N ) + xI (n) sin( N )]

n =0

N −1
 X (k ) = − [ x (n) sin( 2πkn ) − x (n) cos( 2πkn )]
∑
R
I
N
N
 I
n =0

Giải thuật tính DFT tối ưu mỗi phép toán
theo những cách khác nhau

Doi xung

WNk + N /2 = −WNk

Tuan hoan

WNk + N = WNk
©2011, Đinh Đức Anh Vũ

3

dce

2011

Phương pháp chia-trị (1)
•
•

Nguyên tắc: phân rã nhỏ việc tính DFT N điểm thành việc tính các DFT kích thước
nhỏ hơn → các giải thuật FFT
Phương pháp
– Giả sử N=L.M
– Lưu trữ x(n) vào mảng 2 chiều L × M (l: chỉ số hàng, m: chỉ số cột)

n→

0

1

2

…

N-1

x(0)

x(1)

x(2)

…

x(N-1)

– Cách lưu trữ

• Theo dòng n = Ml + m
• Theo cột n = l + mL

l
m

0

1

…

M-1

0

x(0,0)

x(0,1)

…

x(0,M-1)

1

x(1,0)

x(1,1)

…

x(1,M-1)

2

x(2,0)

x(2,1)

…

x(2,M-1)

…

…

…

…

x(L-1,0)

x(L-1,1)

…

x(L-1,M-1)

L-1

– Tương tự, các giá trị DFT X(k) tính được cũng sẽ được lưu trữ trong ma trận L × M
(p: chỉ số hàng, q: chỉ số cột)
• Theo dòng k = Mp + q
• Theo cột k = p + qL

DSP – Giải thuật cho Biến đổi Fourier

©2011, Đinh Đức Anh Vũ

4

dce

2011

Phương pháp chia-trị (2)
N −1

X (k ) = ∑ x(n)WNkn

0 ≤ k ≤ N −1

n =0

Với:

M −1 L −1

x(n)
X(k)

X ( p, q ) = ∑∑ x(l , m)WN( Mp + q )( mL +l )

: theo cột
: theo hàng

m =0 l =0

WN( Mp + q )( mL +l ) = WNMLmpWNmLqWNMplWNlq
 lq  M −1
mq  
X ( p, q ) = ∑ WN  ∑ x(l , m)WM  WLlp
l =0 
 m =0

L −1

1
2
3

DFT M điểm
F(l,q)
G(l,q)
DFT L điểm
X(p,q)

DSP – Giải thuật cho Biến đổi Fourier

WNNmp = 1
WNmqL = WNmq/ L = WMmq
WNMpl = WNpl/ M = WLpl

(1): Tính L DFT M điểm
Nhân phức : LM2
Cộng phức : LM(M-1)

(2): Tính G(l,q)
Nhân phức : LM

(3): Tính X(p,q)
Nhân phức : ML2
Cộng phức : ML(L-1)

 Độ phức tạp
Nhân phức : N(M+L+1)
Cộng phức : N(M+L-2)
©2011, Đinh Đức Anh Vũ

5