Ch
Ch
ương 4
ương 4
:
:
BI
BI
ỂU DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONG
ỂU DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONG
MIỀN TẦN SỐ RỜI RẠC
MIỀN TẦN SỐ RỜI RẠC
4.1 KHÁI NiỆM DFT
4.2 BIẾN ĐỔI FOURIER RỜI RẠC (DFT)
4.3 CÁC TÍNH CHẤT DFT
4.4 BiẾN ĐỔI FOURIER NHANH (FFT)

4.1 KHÁI NiỆM DFT
4.1 KHÁI NiỆM DFT
X(ω) có các hạn chế khi xử lý trên thiết bị, máy tính:


Tần số ω liên tục


Ế
N
N
ĐỔI
ĐỔI
FOURIER RỜI RẠC - DFT
FOURIER RỜI RẠC - DFT

DFT của x(n) có độ dài N định nghĩa:





−≤≤
=
∑
−
=
−
: 0
10:)(
)(
1
0
2
k
Nkenx
kX
N

=
∑
−
=
: 0
10:)(
)(
1
0
k
NkWnx
kX
N
n
kn
N
còn lại
N
j
N
eW
π
2
−
=

W
N
tuần hòan với độ dài N:


: 0
10:)(
1
)(
1
0
2
n
NnekX
N
nx
N
k
kn
N
j
π
còn lại







−≤≤=
−≤≤=
∑
∑
−

Ví dụ 4.2.1: Tìm DFT của dãy:
{ }
4,3,2,1 )(
↑
=
nx
∑
=
=
3
0
4
)()(
n
kn
WnxkX
jWWjeW
j
=−=−==
−
3
4
2
4
4
2
1
4
;1;
π

4
2
4
3
0
2
4
−=+++==
∑
=
WxWxWxxWnxX
n
n
22)3()2()1()0()()3(
9
4
6
4
3
4
3
0
3
4
jWxWxWxxWnxX
n
n
−−=+++==
∑
=

)()(
N
DFT
N
kXnx
 →←

Nếu:
)()(
0
0 N
kn
N
DFT
N
kXWnnx
 →←−

Thì:
Với:
(n)rect)(
~
)(
N00 NN
nnxnnx
−=−
gọi là dịch vòng của
x(n)
N
đi n

3
2
1
a)
n
x(n-2)
0 1 2 3 4 5
4
3
2
1
n
x(n+3)
-3 -2 -1 0
4
3
2
1

b)
x(n)
n
0 1 2 3
4
3
2
1

NN
kXkXnxnx )()()()(
2121
 →←⊗

Nếu:

Thì:
N
D F T
N
kXnx )()(
22
 →←
∑
−
=
−=⊗
1
0
2121
)()()()(
N
m
NNNN
mnxmxnxnx
Với:
Chập vòng 2 dãy
x
1

Ví dụ 4.3.1: Tìm chập vòng 2 dãy
30:)()()()()(
3
0
4241424143
≤≤−=⊗=
∑
=
nmnxmxnxnxnx
m
4},max{4,3
2121
==⇒==
NNNNN

Đổi biến n->m:

Xác định x
2
(-m)
4
:

Chọn độ dài N:

m
0 1 2 3
4
3
2
1
)()(
~
)(
4242
nrectmxmx −=−
m
0 1 2 3
4
3
2
1
)()(
~
)(
4242
nrectmxmx −=−


Xác định x
2
(n-m) là dịch vòng của x

2
(3-m)
4
m
0 1 2 3
4
3
2
1
x
2
(-m)
4

30:)()()(
3
0
424143
≤≤−=
∑
=
nmnxmxnx
m

n=0:

Nhân các mẫu

0
424143
=−=
∑
=
m
mxmxx

n=3:
25)3()()3(
3
0
424143
=−=
∑
=
m
mxmxx
Vậy:

4.4 BiẾN ĐỔI FOURIER NHANH FFT
4.4 BiẾN ĐỔI FOURIER NHANH FFT
4.4.1 KHÁI NiỆM BiẾN ĐỔI FOURIER NHANH FFT

Vào những năm thập kỷ 60, khi công nghệ vi xử lý phát
triển chưa mạnh thì thời gian xử lý phép tóan DFT trên
máy tương đối chậm, do số phép nhân phức tương đối

4.4.2 THUẬT TOÁN FFT CƠ SỐ 2
a. THUẬT TÓAN FFT CƠ SỐ 2 PHÂN THEO THỜI GIAN

Thuật tóan dựa trên sự phân chia dãy vào x(n) thành các
dãy nhỏ, do biến n biểu thị cho trục thời gian nên gọi là
phân chia theo thời gian.
∑
−
=
=
1
0
)()(
N
n
kn
N
WnxkX
∑∑
−
=
−
=
+=
1
3,5...,1n
1
2,4...,0n
)()(
N

Giả thiết dãy x(n) có độ dài N=2
M
, nếu không có dạng lũy
thừa 2 thì thêm vài mẫu 0 vào sau dãy x(n).


X
0
(k) – DFT của N/2 điểm ứng với chỉ số n chẵn

X
1
(k) – DFT của N/2 điểm ứng với chỉ số n lẽ
∑
−
=
=
1)2/(
0r
2/0
)2()(
N
kr
N
WrxkX
∑
−

2/
)12(.)2()(
N
kr
N
k
N
N
kr
N
WrxWWrxkX
kr
N
kr
N
j
rk
N
j
rk
N
WeeW
2/
2/
2
2
2
2
===
π