TAILIEUCHUNG - Fast Fourier Transform part 3

The discrete form of Parseval’s theorem is There are also discrete analogs to the convolution and correlation theorems (equations and ), but we shall defer them to § and §, respectively. | 504 Chapter 12. Fast Fourier Transform The discrete form of Parseval s theorem is N-1 N-1 h I2 H. k 0 n 0 There are also discrete analogs to the convolution and correlation theorems equations and but we shall defer them to and respectively. CITED REFERENCES AND FURTHER READING Brigham . 1974 The Fast Fourier Transform Englewood Cliffs NJ Prentice-Hall . Elliott . and Rao . 1982 Fast Transforms Algorithms Analyses Applications New York Academic Press . Fast Fourier Transform FFT How much computation is involved in computing the discrete Fourier transform of N points For many years until the mid-1960s the standard answer was this Define W as the complex number W e i N Then can be written as N-1 H X Wnkhk k 0 In other words the vector of hk s is multiplied by a matrix whose n k th element is the constant W to the power n x k. The matrix multiplication produces a vector result whose components are the Hn s. This matrix multiplication evidently requires N2 complex multiplications plus a smaller number of operations to generate the required powers of W. So the discrete Fourier transform appears to be an O N2 process. These appearances are deceiving The discrete Fourier transform can in fact be computed in O N log2 N operations with an algorithm called the fast Fourier transform or FFT. The difference between N log2 N and N2 is immense. With N 106 for example it is the difference between roughly 30 seconds of CPU time and 2 weeks of CPU time on a microsecond cycle time computer. The existence of an FFT algorithm became generally known only in the mid-1960s from the work of . Cooley and . Tukey. Retrospectively we now know see 1 that efficient methods for computing the DFT had been independently discovered and in some cases implemented by as many as a dozen individuals starting with Gauss in 1805 One rediscovery of the FFT that of Danielson and Lanczos in 1942 provides one of the clearest .

• Kỹ thuật lập trình
• tư liệu
• tài liệu lập trình
• thủ thuật lập trình
• ngôn ngữ C#
• ngôn ngữ lập trình
• thành phần cấu tạo vật liệu
• phân loại vật liệu compozit
• công nghệ chế tạo vật liệu compozit
• sản phẩm chế tạo từ vật liệu compozit
• phương hướng phát triển
• Tài liệu điện tử
• Vật liệu điện tử
• Linh kiện điện tử
• Vật liệu linh kiện
• Mạch điện tử
• Đề tài nghiên cứu khoa học
• Tổng hợp
• đặc trưng vật liệu nano
• Vật liệu nano cacbon
• Nano cacbon từ vỏ cua
• Xử lý môi trường
• Bài giảng Y học
• Alcaloid và Dược liệu chứa alcaloid
• Phân lập alc từ dược liệu
• Phân loại alcaloid
• Tính chất lý hóa
• Cấu trúc hóa học
• Tự động học
• Điều khiển học
• Điều khiển tự động
• Lý thuyết hệ thống
• Tài liệu tự động hóa