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ố
2.5
2
1.5
1
T
0.5
(cid:0)
0
(cid:0) (cid:0) (cid:0)
0
1
2
3
4
5
6
7
8
s(t)
tωkje
dt
kc
(cid:0)
time, t
1 T
0
Discrete FSFS Periodic (period T)
2.5
tfπj2
Continuous (cid:0)
2
(cid:0) (cid:0)
1.5
S(f)
s(t)
e
dt
(cid:0) (cid:0) (cid:0) Aperiodic Continuous
1
FTFT (cid:0) (cid:0)
0.5
0
0
2
4
6
8
10
12
time, t
2.5
1N
(cid:0) (cid:0)
2
j
1.5
nkπ2 N
s[n]
e
(cid:0) (cid:0) (cid:0)
1
kc~
1 N
Discrete
0.5
0n
DFSDFS (cid:0)
0
0
1
2
3
4
5
6
7
8
Periodic (period T)
time, tk
S(f)
s[n]
nfπ2je
(cid:0) (cid:0) (cid:0) Discrete (cid:0) (cid:0) (cid:0)
2.5
DTFT Continuous (cid:0) (cid:0) (cid:0)
2
n
1.5
Aperiodic
1
(cid:0) (cid:0)
0.5
1N
j
0
nkπ2 N
(cid:0) (cid:0)
0
2
10
12
4
6
8
s[n]
e
kc~
(cid:0) DFTDFT
time, tk
1 N
0n
Discrete (cid:0)
Chuỗi Fourier (Fourier series-FS)
Tín hiệu x(t) tuần hoàn, chu kỳ Tp , tần số F0 = 1/Tp
(cid:0)
j
t
2
kF 0
(cid:0) (cid:0)
tx )(
k ec
(cid:0) (cid:0)
(cid:0)
(cid:0) (cid:0) (cid:0)
j
t
2
kF 0
c
dt
etx )(
k
k 1 T
p
pT
(cid:0) (cid:0) (cid:0)
X(f) x(t)
τ
f
-F0
F0
t 0 Tp -Tp
Biến đổi Fourier (Fourier transform-FT)
Tín hiệu x(t) không tuần hoàn
j
ft
(cid:0)2
(cid:0) (cid:0)
eFX
df
tx )(
(cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
(cid:0) (cid:0)
j
ft
(cid:0)2
fX
etx
dt
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
X(ω)
x(t)
ω
t -τ/2 τ/2
-2π/τ 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
(cid:0) nj
(cid:0)
(cid:0)
X
d
e
nx )(
(cid:0)
1 (cid:0) 22
(cid:0) (cid:0) (cid:0) (cid:0)
(cid:0)
(cid:0) (cid:0)
(cid:0)
X
njenx
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
n
(cid:0) (cid:0) (cid:0)
Chuỗi Fourier rời rạc Discrete Fourier Sequence (DFS)
Tín hiệu x(n) rời rạc, tuần hoàn với chu kỳ N
N
1
(cid:0)
j
2
Nkn /
(cid:0)
nx )(
kec
(cid:0) (cid:0)
0
(cid:0)
1
(cid:0)
(cid:0)
j
2
Nkn /
c
enx
k
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
k 1 N N
n
0
(cid:0)
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 Biến đổi DTFT cho phổ liên tục X(ω)
|X(ω)| x(n)
0 L-1 n -π π ω
Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT)
Lặp lại tín hiệu x(n) với chu kỳ N ≥ L Tín hiệu xp(n)
tuần hoàn chu kỳ N
xp(n)
N N-1 0 L-1 n n
Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT)
xp(n) tuần hoàn chu kỳ N Tính DFS của xp(n) Xp(k)
xp(n)
L-1
N-1
N
0
n
n
|Xp(k)|
-N 0 N k
Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT)
Xp(k) tuần hoàn chu kỳ N Đặt X(k) = Xp(k), k = 0,..,N-1
x(n)
0
L-1
n
DFT
|X(k)|
0 N-1 k
Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT)
Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L:
L
1
(cid:0)
j
2
Nkn /
enx
N
kX )(
k ,
,...,2,1,0
1
(cid:0) DFT (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
n
0
(cid:0)
N
1
(cid:0)
j
2
Nkn /
(cid:0)
nx
ekX
N
n ,
,...,2,1,0
1
IDFT (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1 N
k
0
(cid:0)
Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT)
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:
N
1
(cid:0) 2
(cid:0) 2
(cid:0) (cid:0) (cid:0)
cos
sin
kX R
nx R
nx I
n
0
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
N
1
kn N (cid:0) 2
kn N (cid:0) 2
(cid:0) (cid:0) (cid:0)
sin
cos
kX I
nx R
nx I
kn N
kn N
n
0
Tính trực tiếp cần:
•
2N2 phép tính hàm lượng giác
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
Chi phí tính toán lớn
• 4N2 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)
j
N
/2(cid:0)
(cid:0)
Đặt
(cid:0)
eW N
N
1
(cid:0)
kX
nk NWnx )(
(cid:0) (cid:0) (cid:0) (cid:0)
n
0
(cid:0)
2/
(cid:0)
Tính đối xứng:
k N
(cid:0) (cid:0)
(cid:0)
(cid:0)
W
Nk W M Nk W Tính tuần hoàn: M
W k N
Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT)
Xét chuỗi x(n) = {x(0), x(1)} FFT 2 điểm của x(n):
X
x
)0(
xWxWx )0(
)1(
)0(
)1(
0 2
0 2
(cid:0) (cid:0) (cid:0) (cid:0)
x
xWxWx )0(
)1(
)0(
)1(
0 2
1 2
= 1)
X )1( (Lưu ý: W2
(cid:0) (cid:0) (cid:0) (cid:0)
X(0) x(0)
1 Bướm (Butterfly)
X(1) x(1) -1
Giải thuật FFT phân chia theo thời gian (Decimation in time – DIT)
Xét chuỗi x(n) có chiều dài N = 2K
Đặ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):
kX )(
kHWkG )(
)(
k ,
,...,1,0
1
k N
N 2
(cid:0) (cid:0) (cid:0) (cid:0)
k
(cid:0)
W
N
kX )(
kG (
)
kH (
k ) ,
,...,
1
N 2 N
N 2
N 2
N 2
G(k), H(k) : DFT N/2 điểm của g(n), h(n)
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
Giải thuật FFT phân chia theo thời gian
g(0) G(0) X(0)
0 NW 1 NW
g(1) G(1) X(1)
FFT N/2 điểm k =0 N/2 -1
(cid:0)N
12/
NW
0
g(N/2 -1) G(N/2 -1) X(N/2-1)
1
h(0) H(0) X(N/2)
NW(cid:0) NW(cid:0)
h(1) H(1) X(N/2 + 1) k = N/2
N - 1 FFT N/2 điểm
12/
N NW
(cid:0) (cid:0) h(N/2 -1) H(N/2 -1) X(N – 1)
Chi phí tính toán
So với tính trực tiếp: chi phí tính toán thấp hơn
2 0 0 0
1 5 0 0
DFT DFT (cid:0)
N N22
1 0 0 0
(cid:0)
FFT FFT (cid:0)
N log22NN N log
s n o i t a r e p O
5 0 0
0
f o r e b m u N
0
1 0
4 0
3 0 2 0 Num b e r o f s a m ple s , N
(cid:0)
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ự Số thứ tự Số thứ tự Số thứ tự Dạng nhị phân Dạng nhị phân Dạng nhị phân Đảo bit Đảo bit n
0 0 0 0 000 000 000 000 000 0
1 1 1 1 001 001 001 100 100 4
2 2 2 2 010 010 010 010 010 2
3 3 3 3 011 011 011 110 110 6
4 4 4 4 100 100 100 001 001 1
5 5 5 5 101 101 101 101 101 5
6 6 6 6 110 110 110 011 011 3
7 7 7 7 111 111 111 111 111 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ố
Ví dụ
FFT 8 điểm phân chia theo tần số
