Các tín hiệu có thể được mô tả duy nhất bằng một biểu diễn toán học rõ ràng như là đồ thị, bảng dữ liệu. được gọi là tín hiệu xác định (deterministic signal). Từ “xác định” ý muốn nhấn mạnh là ta biết rõ và chắc chắn các giá trị của tín hiệu trong quá khứ, hiện tại và tương lai. | Chương V Có nhiều thuật toán FFT khác nhau bao gồm FFT phân chia theo thời gian và FFT phân chia theo tần số. Trong phần này ta tập trung vào thuật toán FFT cơ số 2 N 2 where i is an integer phân chia theo thời gian. Nguyên tắc của FFT Nguyên tắc cơ bản mà các thuật toán FFT đều dựa vào là phân chia DFT N mẫu thành các DFT nhỏ hơn một cách liên tục Với N 2i đầu tiên ta phân chia DFT N mẫu thành các DFT N mẫu sau đó phân chia DFT N mẫu thành DFT JN mẫu và cứ tiếp tục như thế cho đến khi được các DFT dài N 2. Việc tính DFT nhỏ hơn rõ ràng sẽ cần ít phép tính nhân và cộng phức hơn. Trước tiên chia x n thành các dãy con chẵn và lẻ X k 2 x n Wkn 2 x n Wkn neven nodd Đặt n 2m với n chẵn và n 2m 1 với n lẻ X k 2 x 2m W2m 2 x 2m 1 Wk 2m 1 m 0 m 0 2 x 2m Wm Wk2 x 2m 1 W m 0 m 0 X k Xe k WkXo k G k WkH k Xe k và Xo k là DFT N mẫu. Tiếp theo chia dãy con N mẫu là x 2m làm đôi bằng cách đặt m 2p Xe k 2 x 4p W W2k2 x 4p 2 W p 0 p 0 Thực hiện tương tự như vậy cho dãy con x 2m 1 Ví dụ N 8 Quá trình phân chia DFT 8 mẫu thành các DFT nhỏ hơn được minh họa trên lưu đồ. Đầu tiên chia x n thành 2 dãy con dãy thứ nhất là dãy chẵn x 0 x 2 x 4 x 6 và dãy thứ hai là dãy lẻ x 1 x 3 x 5 x 7 . Tiếp theo chia dãy chẵn thành 2 dãy con dãy thứ nhất là x 0 x 4 và dãy thứ hai là x 2 x 6 . Tương tự dãy lẻ được chia thành 2 dãy con là dãy x 1 x 5 và dãy x 3 x 7 . Các DFT 2 mẫu được tính đơn giản như sau G k 2g n Wnk 0 k 1 W e-J -1 n 0 G 0 g 0 g 1 g 0 g 1 chỉ cần phép cộng và trừ G 1 g 0 W04 g 1 W14 g 0 - g 1 - 108 - Chương V Figure Flow graph of the decimation-in-time decomposition of an v-point DFT computation into two A 2 -point DFT computations v 8 . - 109 - Chương V FFT cơ sở A Butterfly Lưu ý WN r N 2 WN N 2 WNr -1 WNr - WNr do đó có thể vẽ lại lưu đồ FFT đơn giản như sau - 110
