Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc

Trang 56 GV: Phạm Hùng Kim Khánh
Chương 4
BIẾN ĐỔI FOURIER RỜI RẠC (DFT)
4.1. Định nghĩa và tính chất
4.1.1. Định nghĩa
Biến đổi Fourier rời rạc (DTFT) của x(n) mô tả như sau:
X(e
j
) =




n
jn
e)n(x
(4.1)
Biến đổi Fourier rời rạc (DFT – Discrete Fourier Transform) N điểm của x(n)
mô tả như sau:
X(k) =




1N
0n
N/kn2j
e)n(x
(4.2)

N/kn2j
e)n(x
=




1L
0n
N/kn2j
e
=
 




1L
0n
n
N/k2j
e

X(k) =
N/k2j
N/kL2j
e1
e1






4.1.2. Tính chất của DFT N điểm
 Tuần hoàn:
Nếu x(n) và X(k) là một cặp biến đổi DFT N điểm thì:
x(n + N) = x(n) n (4.4)
X(k + N) = X(k) k (4.5)
 Tuyến tính:
Nếu:
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc

Trang 57 GV: Phạm Hùng Kim Khánh
x
1
(n)
 
NDFT
X
1
(k)
x
2
(n)
 
NDFT
X
2
(k)
thì: a

R
(k) =












1N
0n
IR
N
kn2
sin)n(x
N
kn2
cos)n(x
(4.7)
X
I
(k) =










1N
0k
IR
N
kn2
sin)k(X
N
kn2
cos)k(X
N
1
(4.9)
x
I
(n) =










X
R
(k) = X
R
(-k)
X
I
(k) = - X
I
(-k)
Hay: X(k) = X*(-k) (4.13)
Nếu x(n) là tín hiệu ảo, x
R
(n) = 0:
X
R
(k) = -X
R
(-k)
X
I
(k) = X
I
(-k)
Hay: X(k) = -X*(-k) (4.14)
 Tích chập vòng tròn:
Nếu:
x
1
(n)


1N
0m
21
Nmod)mn(x)m(x

 Đảo trên miền thời gian:
N
N
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc

Trang 58 GV: Phạm Hùng Kim Khánh
Nếu:
x(n)
 
NDFT
X(k)
thì: x
1
(N - n)
 
NDFT
X(N – k) (4.16)
 Dịch chuyển thời gian và dịch chuyển tần số:
Nếu:
x(n)
 
NDFT
X(k)
thì: x(n - 1)

và y(n)
 
NDFT
Y(k)
thì:
)l(r
xy
 
NDFT
X(k)Y*(k) (4.20)
trong đó:
)l(r
xy
=
 




1N
0m
Nmod)lm(*y)m(x

 Nhân:
Nếu:
x
1
(n)
 
NDFT

NDFT
X(k)
và y(n)
 
NDFT
Y(k)
thì:






1N
0k
1N
0n
)k(*Y)k(X
N
1
)n(*y)n(x
(4.22)
N
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc

Trang 59 GV: Phạm Hùng Kim Khánh
4.2. Biến đổi Fourier nhanh (FFT – Fast Fourier
Transform)
4.2.1. Tính toán DFT trực tiếp
Từ công thức định nghĩa DFT, ta có:

1N
0n
N
kn2
cos)n(x
(4.24)
X
I
(k) =





1N
0n
N
kn2
sin)n(x
(4.25)
|X(k)| =
)k(X)k(X
2
I
2
R

(4.26)

)k(X




1N
0n
kn
N
W)n(x
trong đó W
N
=
N/2j
e


X(k) =



1N
n
N/kn2j
e)n(x
chaün
+



1N
n

N/2j2
N
WeeeW 


(4.28) trở thành:
X(k) =



12/N
0n
nk
2/N
W)n2(x
+




12/N
0n
kn
2/N
k
N
W)1n2(xW

= F
1

Do F
1
(k) và F
2
(k) tuần hoàn nên: F
1
(k) = F
1
(k + N/2) và F
2
(k) = F
2
(k + N/2)
Hơn nữa:
     
k
N
jk
N
2/N
N/2j
k
N/2j
2/Nk
N/2j2/Nk
N
WeWeeeW 




(n) như sau:
v
11
(n) = f
1
(2n) (4.32)
v
12
(n) = f
1
(2n+1)
v
21
(n) = f
2
(2n)
v
22
(n) = f
2
(2n+1)
Quan hệ giữa DFT N/2 điểm và DFT N/4 điểm mô tả như sau:
F
1
(k) = V
11
(k) +
k
2/N
W

(k+N/4) = V
21
(k) -
k
2/N
W
V
22
(k)
trong đó V
ij
là biến đổi DFT N/4 điểm của v
ij
(n).
Quá trình biến đổi trên sẽ tiếp tục thực hiện cho đến DFT 2 điểm. Từ đó, ta
được bảng so sánh độ phức tạp tính toán khi thực hiện DFT trực tiếp với FFT như sau:

N Độ phức tạp của phép nhân trên
DFT
N
2
Độ phức tạp của phép nhân trên
FFT
(N/2)log
2
N
4
8
16
32