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:- 2N2hàm lượng giác- 4N2phép nhân số thực- 4N(N – 1) phép cộng số thực.
17 trang |
Chia sẻ: haohao89 | Lượt xem: 3880 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Bài giảng Biến đổi fourier rời rạc (dft), để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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
jne)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/kn2je)n(x
(4.2)
Biến đổi Fourier ngược (IDFT – Inverse DFT):
x(n) =
1N
0k
N/kn2je)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/kn2je)n(x
=
1L
0n
N/kn2je
=
1L
0n
nN/k2je
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(kje
)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
x1(n) NDFT X1(k)
x2(n) NDFT X2(k)
thì: a1x1(n) + a2x2(n) NDFT a1X1(k) + a2X2(k) (4.6)
Đối xứng:
Xét x(n) = xR(n) + jxI(n) và DFT N điểm X(k) = XR(k) + jXI(k) thì:
XR(k) =
1N
0n
IR
N
kn2
sin)n(x
N
kn2
cos)n(x
(4.7)
XI(k) =
1N
0n
IR
N
kn2
cos)n(x
N
kn2
sin)n(x
(4.8)
Và:
xR(n) =
1N
0k
IR
N
kn2
sin)k(X
N
kn2
cos)k(X
N
1 (4.9)
xI(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) = XR(k) = XR(-k) (4.11)
Nếu x(n) lẻ: x(n) = -x(-n) thì
X(k) = jXI(k) = -jXI(-k) (4.12)
Nếu x(n) là tín hiệu thực, xI(n) = 0:
XR(k) = XR(-k)
XI(k) = - XI(-k)
Hay: X(k) = X*(-k) (4.13)
Nếu x(n) là tín hiệu ảo, xR(n) = 0:
XR(k) = -XR(-k)
XI(k) = XI(-k)
Hay: X(k) = -X*(-k) (4.14)
Tích chập vòng tròn:
Nếu:
x1(n) NDFT X1(k)
x2(n) NDFT X2(k)
thì: x1(n) x2(n) NDFT X1(k)X2(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ì: x1(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/kl2je (4.17)
và x(n)
N/kl2je 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:
x1(n) NDFT X1(k)
x2(n) NDFT X2(k)
thì: x1(n)x2(n) NDFT
N
1 X1(k) X2(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:
XR(k) =
1N
0n N
kn2
cos)n(x
(4.24)
XI(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:
- 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.
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 = 2v (N là một lũy thừa của 2):
X(k) =
1N
0n
N/kn2je)n(x
=
1N
0n
kn
N
W)n(x
trong đó WN = N/2je
X(k) =
1N
n
N/kn2je)n(x
chaün
+
1N
n
N/kn2je)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/4j2N/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
= F1(k) + k
N
W
F2(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 đó: F1(k) và F2(k) lần lượt là DFT N/2 điểm của f1(n) và f2(n) với f1(n) và
f2(n) mô tả như sau:
f1(n) = x(2n) (4.30)
f2(n) = x(2n+1)
Do F1(k) và F2(k) tuần hoàn nên: F1(k) = F1(k + N/2) và F2(k) = F2(k + N/2)
Hơn nữa:
k
N
jk
N
2/NN/2jkN/2j2/NkN/2j2/Nk
N
WeWeeeW
Nên:
X(k + N/2) = F1(k) k
N
W
F2(k) (4.31)
F1(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 N2 phép nhân trên số phức còn khi sử dụng
FFT cơ số 2, ta cần 2(N2/4) + N/2 = N2/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ừ f1(n) và f2(n) như sau:
v11(n) = f1(2n) (4.32)
v12(n) = f1(2n+1)
v21(n) = f2(2n)
v22(n) = f2(2n+1)
Quan hệ giữa DFT N/2 điểm và DFT N/4 điểm mô tả như sau:
F1(k) = V11(k) + k
2/NW
V12(k) (4.33)
F1(k+N/4) = V11(k) - k
2/NW
V12(k)
F2(k) = V21(k) + k
2/NW
V22(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
F2(k+N/4) = V21(k) -
k
2/NW
V22(k)
trong đó Vij là biến đổi DFT N/4 điểm của vij(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)log2N
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
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 62 GV: Phạm Hùng Kim Khánh
Hình 4.3 – Thuật toán thực hiện cho FFT 8 điểm
Thuật toán thực hiện DFT trên được xây dựng dựa cơ sở theo sơ đồ hình bướm
sau:
Hình 4.3 – Tính toán cho sơ đồ hình bướm cơ sở của thuật toán FFT
4.2.2.2. Trên miền tần số
Xét DFT N điểm:
X(k) =
1N
0n
kn
N
W)n(x
=
12/N
0n
kn
N
W)n(x
+
1N
2/Nn
kn
N
W)n(x
X(k) =
12/N
0n
kn
N
W)n(x
+
12/N
0n
kn
N
2/kN
N
W)2/Nn(xW
(4.34)
Trong đó:
kjkN2/kN2j2/kN
N
)1(eeW
a
b
A = a + W'Nb
B = a - W'Nb
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 63 GV: Phạm Hùng Kim Khánh
X(k) =
12/N
0n
kn
N
k W)2/Nn(x)1()n(x
(4.35)
X(2k) =
12/N
0n
kn2
N
W)2/Nn(x)n(x
=
12/N
0n
kn
2/N
W)2/Nn(x)n(x
(4.36)
X(2k+1) =
12/N
0n
n
N
kn2
N
WW)2/Nn(x)n(x
=
12/N
0n
kn
2/N
n
N
WW)2/Nn(x)n(x
(4.37)
Ta định nghĩa hai chuỗi N/2 điểm g1(n) và g2(n) như sau:
g1(n) = x(n) + x(n + N/2)
g2(n) = n
N
W)2/Nn(x)n(x
(4.38)
Khi đó:
X(2k) =
12/N
0n
kn
2/N1
W)n(g
X(2k+1) =
12/N
0n
kn
2/N2
W)n(g
(4.39)
Như vậy, việc tính toán DFT N điểm có thể thực hiện thông qua DFT N/2 điểm
của 2 chuỗi g1 và g2. Quá trình tính toán mô tả như sau:
Hình 4.4 – Bước thứ nhất của thuật toán FFT trên miền tần số
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 64 GV: Phạm Hùng Kim Khánh
Các sơ đồ thực hiện cho thuật toán FFT trên miền tần số mô tả như sau:
Hình 4.5 – Thuật toán FFT 8 điểm trên miền tần số
Hình 4.6 - Tính toán cho sơ đồ hình bướm cơ sở của thuật toán FFT trên miền tần số
4.2.3. Thuật toán FFT cơ số 4
4.2.3.1. Trên miền thời gian
Xét DFT N điểm có N là lũy thừa của 4 (N = 4v), ta có thể dùng thuật toán FFT
cơ số 2 để thực hiện tính toán DFT. Tuy nhiên, quá trình tính toán sẽ hiệu quả hơn nếu
sử dụng thuật toán cơ số 4 được mô tả như sau đây.
Ta có:
X(p,q) = 𝑊𝑁
𝑙𝑞𝐹(𝑙, 𝑞) 3𝑙=0 𝑊4
𝑙𝑝
, p = 0, 1, 2, 3 (4.40)
trong đó:
a
b
A = a + b
B = (a – b)W'Nb
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 65 GV: Phạm Hùng Kim Khánh
F(l,q) = 𝑥(𝑙,𝑚)𝑊𝑁/4
𝑚𝑞
𝑁
4
−1
𝑚=0 ,
𝑙 = 0, 1, 2, 3
𝑞 = 0,1,… ,
𝑁
4
− 1
(4.41)
và: x(l,m) = x(4m + l) (4.42)
X(p,q) = X(
𝑁
4
p + q) (4.43)
Từ đó, quá trình thực hiện DFT N điểm có thể thông qua thực hiện 4 DFT N/4
điểm. Biểu thức thực hiện mô tả như sau:
𝑋(0, 𝑞)
𝑋(1, 𝑞)
𝑋(2, 𝑞)
𝑋(3, 𝑞)
=
1 1 1 1
1 −𝑗 −1 𝑗
1 −1 1 −1
1 𝑗 −1 −𝑗
𝑊𝑁
0𝐹(0, 𝑞)
𝑊𝑁
𝑞𝐹(1, 𝑞)
𝑊𝑁
2𝑞𝐹(2, 𝑞)
𝑊𝑁
3𝑞𝐹(3, 𝑞)
(4.44)
Sơ đồ mô tả quá trình thực hiện:
Hình 4.7 - Tính toán cho sơ đồ hình bướm cơ sở của thuật toán FFT cơ số 4
Để giảm lượng phép toán trên số phức, biểu thức (4.44) có thể biểu diễn ở dạng
sau:
𝑋(0, 𝑞)
𝑋(1, 𝑞)
𝑋(2, 𝑞)
𝑋(3, 𝑞)
=
1 0 1 0
0 1 0 −𝑗
1 0 −1 0
0 1 0 𝑗
1 0 1 0
1 0 −1 0
0 1 0 1
0 1 0 −1
𝑊𝑁
0𝐹(0, 𝑞)
𝑊𝑁
𝑞𝐹(1, 𝑞)
𝑊𝑁
2𝑞𝐹(2, 𝑞)
𝑊𝑁
3𝑞𝐹(3, 𝑞)
(4.45)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 66 GV: Phạm Hùng Kim Khánh
Sơ đồ thực hiện của DFT 16 điểm:
Hình 4.8 – Sơ đồ thực hiện của DFT 16 điểm dùng thuật toán cơ số 4
4.2.3.2. Trên miền tần số
X(p,q) = 𝐺(𝑙, 𝑞)
𝑁
4
−1
𝑙=0 𝑊𝑁/4
𝑙𝑝
(4.46)
Trong đó:
G(l,q) = 𝑊𝑁
𝑙𝑞𝐹(𝑙, 𝑞) (4.47)
F(l,q) = 𝑥(𝑙,𝑚)𝑊4
𝑚𝑞3
𝑚=0 ,
𝑞 = 0, 1, 2, 3
𝑙 = 0,1,… ,
𝑁
4
− 1
(4.48)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 67 GV: Phạm Hùng Kim Khánh
Hình 4.9 - Sơ đồ thực hiện của DFT 16 điểm dùng thuật toán cơ số 4 trên miền tần số
4.2.4. Ứng dụng của thuật toán FFT
Tính toán nhân chập vòng tròn
Dựa vào tính chất nhân chập vòng tròn, ta có mô hình như sau:
Hình 4.10
VD: Tính nhân chập vòng tròn N điểm của x1(n) = x2(n) =
khác0
1Nn01
X1(k) = X2(k) =
1N
0n
kn
N
W.1
=
N/)1N(kje
)N/ksin(
)N/kNsin(
= kjN/kj ee
)N/ksin(
)ksin(
FFT
FFT
IDFT
x(n)
y(n) Y(k)
X(k)
V(k) = X(k)Y(k)
v(n)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 68 GV: Phạm Hùng Kim Khánh
X1(k) = X2(k) =
khác0
0kN
V(k) =
khác0
0kN 2
v(n) =
1N
0k
N/kn2je)k(V
N
1 =
khác0
1Nn0N
Tính toán DFT của hai chuỗi thực
Xét 2 chuỗi x1(n), x2(n) là 2 chuỗi thực có chiều dài N và x(n) là chuỗi phức
định nghĩa như sau:
x(n) = x1(n) + jx2(n) (0 ≤ n < N) (4.49)
Biểu diễn x1(n) và x2(n) theo x(n) như sau:
x1(n) =
𝑥 𝑛 +𝑥∗(𝑛)
2
(4.50)
x2(n) =
𝑥 𝑛 −𝑥∗(𝑛)
𝑗2
Do tính chất tuyến tính của DFT:
X(k) = X1(k) + jX2(k) (4.51)
X1(k) =
𝐷𝐹𝑇 𝑥 𝑛 +𝐷𝐹𝑇[𝑥∗ 𝑛 ]
2
X2(k) =
𝐷𝐹𝑇 𝑥 𝑛 −𝐷𝐹𝑇[𝑥∗ 𝑛 ]
𝑗2
Mà DFT[X*(n)] = X*(N – k) nên:
X1(k) = [X(k) + X*(N – k)]/2 (4.52)
X2(k) = [X(k) – X*(N – k)]/j2
Như vậy, DFT của hai chuỗi thực có thể tính toán thông qua DFT của chuỗi
phức x(n).
Tính toán DFT 2N điểm của chuỗi thực
Xét y(n) là chuỗi 2N điểm, ta định nghĩa;
x1(n) = y(2n) (4.53)
x2(n) = y(2n + 1)
Xét chuỗi x(n) = x1(n) + jx2(n), theo (4.52):
X1(k) = [X(k) + X*(N – k)]/2
X2(k) = [X(k) – X*(N – k)]/j2
Ứng dụng thuật toán FFT trên miền thời gian, ta được:
Y(k) = 𝑦 2𝑛 𝑊2𝑁
2𝑛𝑘𝑁−1
𝑛=0 + 𝑦 2𝑛 + 1 𝑊2𝑁
(2𝑛+1)𝑘𝑁−1
𝑛=0
= 𝑥1 𝑛 𝑊𝑁
𝑛𝑘𝑁−1
𝑛=0 + W2N
k 𝑥2(𝑛)𝑊𝑁
𝑛𝑘𝑁−1
𝑛=0 (4.54)
Tương tự, ta tính được:
Y(k) = X1(k) + W2N
k X2(k) (k = 0, 1, …, N – 1) (4.55)
Y(k + N) = X1(k) - W2N
k X2(k) (k = 0, 1, …, N – 1)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 69 GV: Phạm Hùng Kim Khánh
4.3. Tính toán FFT dùng xấp xỉ lọc tuyến tính
Thuật toán Goertzel thực hiện dựa trên khai triển tuần hoàn hệ số pha 𝑊𝑁
𝑘 . Do
𝑊𝑁
−𝑘𝑁 = 1 nên:
X(k) = 𝑊𝑁
−𝑘𝑁 𝑥 𝑛 𝑊𝑁
𝑘𝑛𝑁−1
𝑛=0 = 𝑥 𝑛 𝑊𝑁
−𝑘(𝑁−𝑛)𝑁−1
𝑛=0 (4.56)
Ta xét chuỗi yk(m):
yk(m) = 𝑥 𝑛 𝑊𝑁
𝑘(𝑚−𝑛)𝑁−1
𝑛=0 (4.57)
Chuỗi yk(m) chính là tích chập giữa x(n) và 𝑊𝑁
−𝑘𝑛𝑢(𝑛). Đây chính là một mạch
lọc với đáp ứng xung h(n) = 𝑊𝑁
−𝑘𝑛𝑢(𝑛). Từ đó:
X(k) = 𝑦𝑘(𝑚) 𝑚=𝑁 (4.58)
Mạch lọc với đáp ứng xung h(n) có hàm hệ thống là:
H(z) =
1
1−𝑊𝑁
−𝑘𝑧−1
(4.59)
Mạch lọc này có một điểm cực trên đường tròn đơn vị tại zp = 𝑊𝑁
−𝑘 = 𝑒𝑗𝑘2𝜋/𝑁 .
Như vậy, X(k) chính là ngõ ra của mạch lọc tại thời điểm N và toàn bộ DFT của x(n)
có thể tính toán bằng cách đưa qua một khối gồm các bộ lọc đơn cực song song với tần
số tương ứng với tần số của DFT (k = k2π/N).
Từ (4.57), ta xác định phương trình sai phân như sau:
yk(n) = 𝑊𝑁
−𝑘yk(n – 1) + x(n), yk(-1) = 0 (4.60)
Hàm hệ thống của phương trình sai phân là:
H(z) =
1−𝑊𝑁
𝑘𝑧−1
1−2𝑐𝑜𝑠
2𝜋𝑘
𝑁
𝑧−1+𝑧−2
(4.61)
Dạng trực tiếp loại 2 của hệ thống mô tả bằng phương trình sai phân sau:
vk(n) = 2𝑐𝑜𝑠
2𝑘𝜋
𝑁
𝑣𝑘 𝑛 − 1 − 𝑣𝑘 𝑛 − 2 + 𝑥(𝑛) (4.62)
yk(n) = vk(n) – 𝑊𝑁
𝑘vk(n – 1) (4.63)
với điều kiện đầu vk(-1) = vk(-2) = 0.
Hình 4.11
z
-1
z
-1
x(n) y(n)
−𝑊𝑁
𝑘 2𝑐𝑜𝑠
2𝑘𝜋
𝑁
-1
vk(n)
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 70 GV: Phạm Hùng Kim Khánh
4.4. Ảnh hưởng của quá trình lượng tử đến DFT
4.4.1. Lỗi lượng tử khi dùng DFT
Xét tín hiệu hữu hạn phức x(n) có biến đổi DFT – N điểm là X(k)
X(k) =
1
0
1
0
/2 )()(
N
n
k
N
N
n
Nknj Wnxenx
(4.64)
Giả sử phần thực vào phần ảo của x(n) được biểu diễn bằng b bit. Theo (4.64),
một giá trị 𝑥 𝑛 𝑊𝑁
𝑘𝑛 bao gồm 4 phép nhân số thực. Do đó, mỗi phép nhân số phức sẽ
xảy ra 4 lỗi lượng tử. Trong quá trình tính toán DFT, mỗi giá trị X(k) bao gồm N phép
nhân số phức nên tổng cộng sẽ có 4N lỗi lượng tử.
Để tính toán phương sai của lỗi lượng tử, ta giả sử:
- Lỗi lượng tử do quá trình làm tròn là biến ngẫu nhiên phân bố đều trong
khoảng (-/2,/2) với = 2-b.
- 4N lỗi lượng tử không tương quan với nhau.
- 4N lỗi lượng tử không tương quan với x(n).
Mỗi lỗi lượng tử có phương sai:
𝜎𝑒
2 =
∆2
12
=
2−2𝑏
12
(4.65)
Phương sai của 4N phép nhân là:
𝜎𝑞
2 = 4𝑁𝜎𝑒
2 =
𝑁
3
2−2𝑏 (4.66)
Như vậy, phương sai của 4N phép nhân tỉ lệ thuận với kích thước N của DFT.
Trong trường hợp N là lũy thừa của 2 (N = 2𝜗 ):
𝜎𝑞
2 =
2
−2(𝑏−
𝜗
2
)
3
(4.67)
Ngoài ra, để tránh hiện tượng tràn, cần phải thực hiện co tín hiệu ngõ vào. Theo
(4.64), ta thấy rằng:
𝑋(𝑘) ≤ x(n) N−1n=0 (4.68)
Giả sử phạm vi của tín hiệu trong khoảng (-1,1), ta cần có:
x(n) N−1n=0 < 1 (4.69)
Và giả sử rằng tín hiệu ngõ vào x(n) được co trong khoảng (-1,1), nghĩa là
𝑥(𝑛) < 1,∀𝑛. Để thỏa mãn (4.69), mỗi điểm trong x(n) phải được chia với N.
4.4.2. Lỗi lượng tử khi dùng thuật toán FFT
Ở phần trên, ta đã khảo sát quá trình tính toán DFT bằng thuật toán FFT. Trong
FFT, số lượng phép nhân thực hiện ít hơn so với tính toán trực tiếp nên lỗi lượng tử
trong FFT cũng ít hơn.
Xét trường hợp FFT cơ số 2 với N = 8 (hình 4.12). Ta thấy rằng một sơ đồ hình
bướm có 1 phép nhân số phức, nghĩa là có 4 phép nhân số thực. Khi bỏ qua các phép
toán không đáng kể ứng với các hệ số ±1, các sơ đồ bướm ảnh hưởng đến quá trình
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 71 GV: Phạm Hùng Kim Khánh
tính toán FFT bao gồm: N/2 sơ đồ tại tầng 1, N/4 tại tầng 2, N/8 tại tầng 3, … Như
vậy, số lượng sơ đồ bướm ứng với mỗi ngõ ra là:
2𝜗−1 + 2𝜗−2 +⋯+ 1 = 2𝜗 − 1 = 𝑁 − 1 (4.70)
Hình 4.12 – Sơ đồ thực hiện FFT cơ số 2 trên miền thời gian với N = 8
Sơ đồ thực hiện của X(3) mô tả như hình vẽ 4.13. Lỗi lượng tử sẽ được truyền
từ mỗi sơ đồ bướm tới ngõ ra của thuật toán. Giả sử rằng lỗi lượng tử của mỗi sơ đồ
bướm không tương quan với các sơ đồ khác. Từ đó, mỗi ngõ ra của thuật toán FFT có
4(N – 1) lỗi lượng tử. Phương sai của lỗi lượng tử tổng cộng là:
𝜎𝑞
2 = 4(𝑁 − 1)
∆2
12
≈
𝑁
3
2−2𝑏 (4.71)
Ta thấy kết quả này tương đương với phương pháp tính DFT trực tiếp. Điều này
xảy ra là do thuật toán FFT không giảm số lượng phép nhân của một ngõ ra mà chỉ tận
dụng tính tuần hoàn của 𝑊𝑁
𝑘 làm giảm số lượng tính toán của toàn bộ N ngõ ra.
Tầng 1 Tầng 2 Tầng 3
Xử lý số tín hiệu Chương 4: Biến đổi Fourier rời rạc
Trang 72 GV: Phạm Hùng Kim Khánh
Hình 4.13 – Sơ đồ bướm của X(3) với N = 8