Xử lý số tín hiệu
Chương 8: Biến đổi DFT và FFT
Các phép biến đổi Fourier
Miền thời gian Miền tần số
dt
tf
πj2
es(t)S(f)






dt
T
0
t
ωkj
es(t)
T
1
k
c



Periodic
(period T)
Discrete
Continuous

nk
π2
j
es[n]
N
1
k
c
~
Discrete
Discrete
DFS
DFSPeriodic
(period T)
ContinuousDTFT
Aperiodic
Discrete
DFT
DFT
nfπ2j
e
n
s[n]S(f)








j
es[n]
N
1
k
c
~
Chuỗi Fourier (Fourier series-FS)
 Tín hiệu x(t) tuần hoàn, chu kỳ T
p
, tần số F
0
= 1/T
p




k
tkFj
k
ectx
0
2
)(




p



 dfeFXtx
ftj

2
)(
   




 dtetxfX
ftj

2
X(ω)
ω
2π/τ-2π/τ
x(t)
-
τ/2
t
τ/2
Biến đổi Fourier của một số tín hiệu cơ bản
Biến đổi Fourier thời gian rời rạc
Discrete – Time Fourier Transform (DTFT)
 Tín hiệu x(n) rời rạc, không tuần hoàn
 


/2
)(
N
k
Nknj
k
ecnx

 





1
0
/2
1
N
n
Nknj
k
enx
N
c

Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
 Tín hiệu x(n) rời rạc, không tuần hoàn, chiều dài L hữu
h

N
x
p
(n)
N-1
n
L-1
n
|X
p
(k)|
k
0 N-N
X
p
(k) tuần hoàn chu kỳ N  Đặt X(k) = X
p
(k), k = 0, ,N-1
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
|X(k)|
k0 N-1
0 L-1 n
x(n)
DFT
Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L:
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
 
1, ,2,1,0 , )(

IDFT
DFT
 Tính trực tiếp DFT N – điểm của x(n):
T
ổng quát: X(k) và x(n) là số phức:
Tính tr
ực tiếp cần:
• 2N
2
phép tính hàm lượng giác
• 4N
2
phép nhân thực
• 4N(N-1) phép cộng thực
Giải thuật biến đổi Fourier nhanh
Fast Fourier Transform (FFT)
     










1
0
2

N
n
IRI
N
kn
nx
N
kn
nxkX

Chi phí tính
toán l
ớn
 Đặt

 Tính đối xứng:
 Tính tuần hoàn:
Giải thuật biến đổi Fourier nhanh
Fast Fourier Transform (FFT)
Nj
N
eW
/2



 




)1()0()1()0()0(
1
2
0
2
0
2
0
2
xxWxWxX
xxWxWxX


x(0)
x(1)
X(0)
X(1)
-1
1 Bướm
(Butterfly)
 Xét chuỗi x(n) có chiều dài N = 2
K
 Đặt g(n) = x(2n)  g(n) = {x(0), x(2), … }
 Đặt h(n) = x(2n + 1)  h(n) = {x(1), x(3), …}
 DFT N điểm của x(n):
 G(k), H(k) : DFT N/2 điểm của g(n), h(n)
Giải thuật FFT phân chia theo thời gian
(Decimation in time – DIT)
1
2

g(0)
g(N/2 -1)
g(1)
G(0)
G(N/2 -1)
G(1)
FFT N/2

điểm
FFT N/2
điểm
h(0)
h(N/2 -1)
h(1)
H(0)
H(N/2 -1)
H(1)
0
N
W
X(0)
1
N
W
X(1)
12/ N
N
W
X(N/2-1)
k =0

DFT


N
N
2
2
FFT
FFT


N log
N log
2
2
N
N
Ví dụ
 FFT 8 điểm phân chia theo thời gian
Ví dụ
 FFT 8 điểm phân chia theo thời gian
Ví dụ
 FFT 8 điểm phân chia theo thời gian
Ví dụ
 FFT 8 điểm phân chia theo thời gian
Ví dụ
 Thứ tự chuỗi x(n) trong pp Decimation – in - time
Số thứ tự Dạng nhị phân Đảo bit n
0 000 000 0
1 001 100 4

5
6
7
Ví dụ
 FFT 8 điểm phân chia theo tần số (Decimation in freq)
Ví dụ
 FFT 8 điểm phân chia theo tần số