Bài giảng Biến đổi fourier rời rạc (dft)

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