tailieunhanh - Lập Trình C# all Chap "NUMERICAL RECIPES IN C" part 150

Tham khảo tài liệu 'lập trình c# all chap "numerical recipes in c" part 150', công nghệ thông tin phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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
• thủ thuật lập trình
• tư liệu lập trình
• ngôn ngữ lập trình
• hướng dẫn lập trình
• kĩ năng lập trình
• kỹ thuật lập trình
• kỹ năng lập trình
• bí quyết lập trình
• phương pháp lập trình
• kĩ thuật lập trình
• AutoIT