xử lý tín hiệu slide c4
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (377.28 KB, 17 trang )
CHƯƠNG 4: BIẾN ĐỔI
FOURIER RỜI RẠC
1. DFT (Discrete Fourier Transform)
2. FFT (Fast Fourier Transform)
Chương 4
1
DFT (Discrete Fourier Transform)
Định nghĩa
X ( ) =
− jn
x
(
n
)
e
n = −
DFT-N điểm
N −1
X (k ) = x(n)e − j 2kn / N
- Chuỗi x(n) có N giá trị
- k=0N-1
n =0
Biến đổi Fourier ngược (Inverse DFT)
1 N −1
x(n) = X (k )e j 2kn / N
N k =0
Chương 4
2
DFT (Discrete Fourier Transform)
1 0 n L
x ( n) =
khác
0
N −1
X ( k ) = x ( n )e
n =0
− j 2kn / N
L −1
= e
n =0
− j 2kn / N
= (e
L −1
)
− j 2k / N n
n =0
1 − e − j 2kL / N 2 j sin(kL / N )e − jkL / N sin(kL / N ) − jk ( L −1) / N
X (k ) =
=
=
e
− j 2k / N
− jk / N
1− e
2 j sin(k / N )e
sin(k / N )
1 – e-jL = 1 – cosL + jsinL = 2sin2L/2 + j2sinL/2cosL/2 = 2sin(L/2)(sin(L/2) + jcos(L/2))
= 2jsin(L/2)(cos(L/2) – jsin(L/2)) = 2jsin(L/2)e-jL/2
Chương 4
3
DFT (Discrete Fourier Transform)
Xác định DFT – 10 điểm của tín hiệu:
x(n) = sin
3
n (0 n 10)
5
x(n) = 1 + cos 2
3
n
10
(0 n 10)
Chương 4
4
FFT (Fast Fourier Transform)
DFT trực tiếp
2kn
2kn
X (k ) = x(n) cos
− j sin
N
N
n =0
2kn
2kn 2 hàm lượng giác
x(n) cos
− j sin
4 phép nhân số thực
N
N 2 phép cộng số thực
N −1
Một giá trị X(k) cần:
N giá trị X(k) cần:
2N hàm lượng giác
4N phép nhân số thực
4(N-1) phép cộng số thực
2N2 hàm lượng giác
4N2 phép nhân số thực
4N(N – 1) phép cộng số thực
Chương 4
5
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền thời gian
N −1
X ( k ) = x ( n )e
− j 2kn / N
n =0
N −1
= x(n)WNkn
n =0
WN = e-j2/N
WN2 = (e − j2 / N ) = e − j4 / N = e − j2 /( N / 2) = WN / 2
2
𝑁−1
𝑁−1
𝑋 𝑘 = 𝑥(𝑛)𝑊𝑁𝑘𝑛 + 𝑥(𝑛)𝑊𝑁𝑘𝑛
𝑛 𝑙ẻ
𝑛 𝑐ℎẵ𝑛
𝑁
2 −1
𝑁−1
n = 2m:
𝑁
2 −1
𝑁
2 −1
𝑥(𝑛)𝑊𝑁𝑘𝑛 = 𝑥(2𝑚)𝑊𝑁𝑘2𝑚 = 𝑥(2𝑚) 𝑊𝑁2
𝑛 𝑐ℎẵ𝑛
𝑁−1
𝑁 𝑚=0
2 −1
𝑚=0
𝑁
2 −1
𝑘𝑚
𝑘𝑚
= 𝑥(2𝑚)𝑊𝑁/2
𝑚=0
n = 2m+1: 𝑥(𝑛)𝑊 𝑘𝑛 = 𝑥(2𝑚 + 1)𝑊 𝑘(2𝑚+1) = 𝑊 𝑘 𝑥(2𝑚 + 1) 𝑊 2
𝑁
𝑁
𝑁
𝑁
𝑛 𝑙ẻ
𝑁
2 −1
𝑚=0
𝑘𝑚
= 𝑊𝑁𝑘 𝑥(2𝑚 + 1)𝑊𝑁/2
𝑚=0
𝑘𝑚
𝑚=0
Chương 4
6
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền thời gian
𝑁
2 −1
𝑁
2 −1
𝑘𝑛
𝑋 𝑘 = 𝑥 2𝑛 𝑊𝑁𝑘𝑛 + 𝑊𝑁𝑘 𝑥(2𝑛 + 1)𝑊𝑁/2
𝑛=0
2
𝑛=0
x(n) có N giá trị → x(2n) và x(2n + 1) có N/2 giá trị
DFT N điểm của x(n):
N −1
X (k ) = x(n)e − j 2kn / N
- Chuỗi x(n) có N giá trị
- k=0N-1
n =0
𝑁
2 −1
𝑁
2 −1
𝑥 2𝑛 𝑊𝑁𝑘𝑛 : DFT N/2 điểm
2
của x(2n)
𝑛=0
𝑘𝑛
𝑥(2𝑛 + 1)𝑊𝑁/2
: DFT N/2 điểm
của x(2n+1)
𝑛=0
Chương 4
7
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền thời gian
𝑋 𝑘 = 𝐹1 (𝑘) + 𝑊𝑁𝑘 𝐹2 (𝑘)
𝐹1 𝑘
𝑁
𝐷𝐹𝑇− đ𝑖ể𝑚
2
𝑓1 𝑛 = 𝑥(2𝑛)
k = 0 N/2 - 1
𝐹2 𝑘
𝑁
𝐷𝐹𝑇− đ𝑖ể𝑚
2
𝑓2 𝑛 = 𝑥(2𝑛 + 1)
𝑁
𝑁
𝑁
𝑁
𝑁
𝑘+ 2
𝑋 𝑘+
= 𝐹1 𝑘 +
+ 𝑊𝑁 𝐹2 𝑘 +
= 𝐹1 (𝑘) + 𝑊𝑁2 𝑊𝑁𝑘 𝐹2 (𝑘)
2
2
2
𝑁
𝑊𝑁2
=
𝑋 𝑘+
𝑁
−𝑗2𝜋/𝑁
2
𝑒
= 𝑒 −𝑗𝜋 = −1
𝑁
= 𝐹1 𝑘 − 𝑊𝑁𝑘 𝐹2 (𝑘)
2
Chương 4
8
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền thời gian
Cách tính DFT – N điểm của x(n):
Tính FFT – 4 điểm của x(n):
B1: xây dựng 2 chuỗi N/2 giá trị từ x(n)
f1(n) = x(2n)
f2(n) = x(2n + 1)
x(n) = {2, 2 – j, 2 + j, -1}
Tính FFT – 8 điểm của x(n):
B2: Tính DFT – N/2 điểm của f1 và f2
x(n) = {1,3,-1,-3,2,-3,-2,1}
B3: DFT – N điểm của x(n):
𝑋 𝑘 = 𝐹1 (𝑘) + 𝑊𝑁𝑘 𝐹2 (𝑘)
k = 0 N/2 - 1
𝑁
𝑋 𝑘+
= 𝐹1 𝑘 − 𝑊𝑁𝑘 𝐹2 (𝑘)
2
Chương 4
9
FFT cơ số 2 trên miền thời gian
a
A = a + W'Nb
b
W'N
x(n) = {2, 2 – j, 2 + j, -1}
-1
X(k) = {5,-1-4j,3+2j,1+2j}
2
4+j
2+j
W04
-j
-1
4+j+(1-j) = 5
-j -j(3-j) = -1-4j
1-j
2-j
W04=1
-1
3-j
W04
-1
B = a - W'Nb
W14=-j
-1
-1
Chương 4
4+j – (1-j) = 3 +2j
-j+j(3 – j) = 1 +2j
10
W18 =
W3
1
8
1
2
=−
−𝑗
1
2
2 W08=1
−𝑗
1
2
X(k) = {-2,2.54-j3.88,3+j,-4.54+j8.12,8,-4.54-j8.12,3-j,2.54+j3.88}
-1
-1
-1
0
-2 W 8=1 -1
-3
1 W08=1 -1
6
W08=1
-1
W28=-j
-1
-3
0
-2 W 8=1
W28=-j
-1
-1
Chương 4
3+j
3
-1+6j
0
-5 W 8=1
1+4j
1
-4
2.54 - 3.88j
-1-6j
-1
0
-2
3
3
3
-3 W08=1
x(n) = {1,-1,3,-3,2,-2,-3,1}
1
2
-1
1-4j
-4.54+8.12j
-1
8
W18
-1
-4.54-8.12j
W28=-j
-1
3-j
W38
-1
2.54+3.88j
11
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền tần số
N −1
X ( k ) = x ( n )e
− j 2kn / N
n =0
N −1
= x(n)WNkn
n =0
WN = e-j2/N
WNkN / 2 = (e − j 2 / N )
kN / 2
𝑁
2 −1
𝑁−1
= e − jk = (− 1)
k
𝑋 𝑘 = 𝑥(𝑛)𝑊𝑁𝑘𝑛 + 𝑥(𝑛)𝑊𝑁𝑘𝑛
𝑁
𝑛= 2
𝑛=0
n = m+N/2:
𝑁−1
𝑥(𝑛)𝑊𝑁𝑘𝑛
𝑁
𝑛= 2
𝑁
2 −1
= −1
𝑚=0
𝑁
2 −1
𝑁
2 −1
𝑚=0
𝑚=0
𝑁 𝑘(𝑚+𝑁2)
𝑁 𝑘𝑁2 𝑘𝑚
= 𝑥(𝑚 + )𝑊𝑁
= 𝑥(𝑚 + )𝑊𝑁 𝑊𝑁
2
2
𝑘 𝑥(𝑚
𝑁
+ ) 𝑊𝑁𝑘𝑚
2
Chương 4
12
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền tần số
WN2 = WN / 2
𝑁
−1
2
𝑁
−1
2
𝑛=0
𝑛=0
𝑁
𝑁
𝑋 𝑘 = 𝑥 𝑛 𝑊𝑁𝑘𝑛 + −1 𝑘 𝑥(𝑛 + ) 𝑊𝑁𝑘𝑛 = 𝑥 𝑛 + −1 𝑘 𝑥(𝑛 + ) 𝑊𝑁𝑘𝑛
2
2
𝑁
−1
2
𝑁
−1
2
𝑁
−1
2
𝑛=0
𝑛=0
𝑛=0
𝑁
𝑁
𝑘𝑛
𝑘𝑛
2𝑘𝑛
𝑋 2𝑘 = 𝑥 𝑛 + 𝑥(𝑛 + ) 𝑊𝑁 = 𝑥 𝑛 + 𝑥(𝑛 + ) 𝑊𝑁/2
= 𝑔1 (𝑛)𝑊𝑁/2
2
2
𝑁
2 −1
𝑁
2 −1
𝑛=0
𝑛=0
𝑁
𝑁
(2𝑘+1)𝑛
𝑘𝑛
𝑋 2𝑘 + 1 = 𝑥 𝑛 − 𝑥(𝑛 + ) 𝑊𝑁
= 𝑥 𝑛 − 𝑥(𝑛 + ) 𝑊𝑁𝑛 𝑊𝑁/2
2
2
𝑁
2 −1
𝑘𝑛
= 𝑔2 (𝑛)𝑊𝑁/2
𝑛=0
Chương 4
13
FFT (Fast Fourier Transform)
𝐺1 𝑘
𝐺2 𝑘
𝑁
𝐷𝐹𝑇− đ𝑖ể𝑚
2
𝑁
𝐷𝐹𝑇− đ𝑖ể𝑚
2
𝑁
𝑔1 𝑛 = 𝑥 𝑛 + 𝑥(𝑛 + )
2
𝑁
𝑔2 𝑛 = 𝑥 𝑛 − 𝑥(𝑛 + ) 𝑊𝑁𝑛
2
X(2k) = G1(k)
X(2k + 1) = G2(k)
k = 0 N/2 - 1
Chương 4
14
FFT (Fast Fourier Transform)
FFT cơ số 2 trên miền tần số
Tính FFT – 4 điểm của x(n):
Cách tính DFT – N điểm của x(n):
x(n) = {2 – j, 1 – j, 1 + j, -2}
B1: xây dựng 2 chuỗi N/2 giá trị từ x(n)
𝑁
𝑔1 𝑛 = 𝑥 𝑛 + 𝑥(𝑛 + )
2
𝑁
𝑔2 𝑛 = 𝑥 𝑛 − 𝑥(𝑛 + ) 𝑊𝑁𝑛
2
Tính FFT – 8 điểm của x(n):
x(n) = {1,3,-1,-3,2,-3,-2,1}
B2: Tính DFT – N/2 điểm của g1 và g2
B3: DFT – N điểm của x(n):
X(2k) = G1(k)
X(2k + 1) = G2(k)
k = 0 N/2 - 1
Chương 4
15
FFT cơ số 2 trên miền tần số
A=a+b
a
b
B = (a – b)W'N
W'N
-1
x(n) = {2 – j, 1 – j, 1 + j, -2}
2-j
3
1-j
-1-j
X(k) = {2-j,-5j,4+j,2+j}
2-j
-1
W04
1+j
-1
-2
-1
1-2j
-5j
W04
-1-3j
W14=-j
4+j
-1
W0
Chương 4
2+j
4
16
W18 =
W3
8
1
2
=−
−𝑗
1
2
x(n) = {1,-1,3,-3,2,-2,-3,1}
1
2
−𝑗
1
2
X(k) = {-2,2.54-j3.88,3+j,-4.54+j8.12,8,-4.54-j8.12,3-j,2.54+j3.88}
1
-1
3
-3
2
-2
-3
1
3
3
-3
-5
0
-1
W0
8=1
-1
W18
-1
W28=-j
-1
W3
8
-2
-1
-1
W08=1
j
3.54+2.12j
-1
-1
-1
-3.54+2.12j
3-j
2.54 3.88j
-1
W08=1
-1+6j
W28=-j
8
3+j
-1-6j
0.7-0.7j
2.83+2.83j
-1
3
W28=-j
-1
-6j
-2
-1
-4.54 8.12j
-4.54
+8.12j
2.54 -
