Tài liệu xử lý số liệu - chương 4
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 (884.2 KB, 17 trang )
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)
Biến đổi Fourier ngược (IDFT – Inverse DFT):
x(n) =
1N
0k
N/kn2j
e)k(X
N
1
(4.3)
VD: Xét tín hiệu:
x(n) =
khác0
Ln01
Biến đổi Fourier N điểm (N > L) của x(n) là:
X(k) =
1N
0n
N/kn2j
e)n(x
=
1L
0n
N/kn2j
e
=
1L
0n
n
N/k2j
e
X(k) =
N/k2j
N/kL2j
e1
e1
Mà: 1 – e
-jL
= 1 – cosL + jsinL = 2sin
2
L/2 + j2sinL/2cosL/2 = 2sinL/2(sinL/2 +
jcosL/2) = 2jsinL/2(cosL/2 – jsinL/2) = 2jsinL/2e
-jL/2
X(k) =
Nkj
NkLj
eNkj
eNkLj
/
/
)/sin(2
)/sin(2
=
N/)1L(kj
e
)N/ksin(
)N/kLsin(
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
1
x
1
(n) + a
2
x
2
(n)
NDFT
a
1
X
1
(k) + a
2
X
2
(k) (4.6)
Đối xứng:
Xét x(n) = x
R
(n) + jx
I
(n) và DFT N điểm X(k) = X
R
(k) + jX
I
(k) thì:
X
R
(k) =
1N
0n
IR
N
kn2
sin)n(x
N
kn2
cos)n(x
(4.7)
X
I
(k) =
1N
0n
IR
N
kn2
cos)n(x
N
kn2
sin)n(x
(4.8)
Và:
x
R
(n) =
1N
0k
IR
N
kn2
sin)k(X
N
kn2
cos)k(X
N
1
(4.9)
x
I
(n) =
1N
0k
IR
N
kn2
cos)k(X
N
kn2
sin)k(X
N
1
(4.10)
Nếu x(n) chẵn: x(n) = x(-n) thì
X(k) = X
R
(k) = X
R
(-k) (4.11)
Nếu x(n) lẻ: x(n) = -x(-n) thì
X(k) = jX
I
(k) = -jX
I
(-k) (4.12)
Nếu x(n) là tín hiệu thực, x
I
(n) = 0:
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)
NDFT
X
1
(k)
x
2
(n)
NDFT
X
2
(k)
thì: x
1
(n) x
2
(n)
NDFT
X
1
(k)X
2
(k) (4.15)
Trong đó: biểu diễn tích chập vòng trò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)
NDFT
X(k)
N/kl2j
e
(4.17)
và x(n)
N/kl2j
e
NDFT
X(k-l) (4.18)
Liên hiệp phức:
Nếu:
x(n)
NDFT
X(k)
thì: x*(n)
NDFT
X*(N - k) (4.19)
Tương quan:
Nếu:
x(n)
NDFT
X(k)
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
X
1
(k)
x
2
(n)
NDFT
X
2
(k)
thì: x
1
(n)x
2
(n)
NDFT
N
1
X
1
(k) X
2
(k) (4.21)
Định lý Paserval:
Nếu:
x(n)
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ó:
X(k) =
1N
0n
N
kn2
sinj
N
kn2
cos)n(x
(4.23)
Nếu x(n) là tín hiệu thực:
X
R
(k) =
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
)k(X
arctg)k(
R
I
(4.27)
Nếu x(n) là tín hiệu phức, các thành phần thực và ảo tính toán theo công thức
(4.7) và (4.8). Để thực hiện tính toán theo công thức này, đòi hỏi các phép toán sau:
- 2N
2
hàm lượng giác
- 4N
2
phép nhân số thực
- 4N(N – 1) phép cộng số thực.
4.2.2. Thuật toán FFT cơ số 2
4.2.2.1. Trên miền thời gian
Xét DFT N điểm, giả sử N = 2
v
(N là một lũy thừa của 2):
X(k) =
1N
0n
N/kn2j
e)n(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/kn2j
e)n(x
leû
=
12/N
0n
nk2
N
W)n2(x
+
12/N
0n
)1n2(k
N
W)1n2(x
(4.28)
Mà:
2/N
)2/N/(2jN/4j
2
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
(k) +
k
N
W
F
2
(k) (4.29)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 60 GV: Phạm Hùng Kim Khánh
Trong đó: F
1
(k) và F
2
(k) lần lượt là DFT N/2 điểm của f
1
(n) và f
2
(n) với f
1
(n) và
f
2
(n) mô tả như sau:
f
1
(n) = x(2n) (4.30)
f
2
(n) = x(2n+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ên:
X(k + N/2) = F
1
(k)
k
N
W
F
2
(k) (4.31)
F
1
(k) là DFT N/2 điểm nên cần N
2
/4 phép nhân trên số phức. Như vậy, khi dùng
DFT trực tiếp, ta phải cần tính toán cho N
2
phép nhân trên số phức còn khi sử dụng
FFT cơ số 2, ta cần 2(N
2
/4) + N/2 = N
2
/2 + N/2 phép nhân trên số phức.
Hình 4.1 – Sơ đồ biểu diễn bước thứ nhất trong thuật toán FFT cơ số 2
Xét DFT N/4 điểm xây dựng từ f
1
(n) và f
2
(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
V
12
(k) (4.33)
F
1
(k+N/4) = V
11
(k) -
k
2/N
W
V
12
(k)
F
2
(k) = V
21
(k) +
k
2/N
W
V
22
(k)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 61 GV: Phạm Hùng Kim Khánh
F
2
(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
64
128
256
512
1024
16
64
256
1024
4096
16384
65536
262144
1048576
4
12
32
80
192
448
1024
2304
5120
Sơ đồ mô tả cho FFT 8 điểm như sau:
Hình 4.2 – Sơ đồ thực hiện FFT 8 điểm
