The frequency-domain analysis of signals and systems is efficient, in practice, due to the availability of fast algorithms for the computation of the DFT. While the DFT is defined for any length, practically efficient algorithms are available only for fast computation of the N-point DFT with N an integral power of 2. The algorithms are based on the classical divide-and-conquer strategy of developing fast algorithms. An N-point DFT is recursively decomposed into half-length DFTs, until the DFT becomes trivial. The DFTs of the smaller transforms are combined to form the DFT of the input data. The decomposition can start from the time-domain end or the frequency-domain end. The first type is called decimation-in-time (DIT) algorithms. The second type is called decimation-in-frequency (DIF) algorithms. These algorithms are developed assuming that the data is complex-valued. They can be tailored to suit real-valued data. A set of algorithms are derived and examples of computing the DFT are given.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Computation of the DFT

  • D. Sundararajan

摘要

The frequency-domain analysis of signals and systems is efficient, in practice, due to the availability of fast algorithms for the computation of the DFT. While the DFT is defined for any length, practically efficient algorithms are available only for fast computation of the N-point DFT with N an integral power of 2. The algorithms are based on the classical divide-and-conquer strategy of developing fast algorithms. An N-point DFT is recursively decomposed into half-length DFTs, until the DFT becomes trivial. The DFTs of the smaller transforms are combined to form the DFT of the input data. The decomposition can start from the time-domain end or the frequency-domain end. The first type is called decimation-in-time (DIT) algorithms. The second type is called decimation-in-frequency (DIF) algorithms. These algorithms are developed assuming that the data is complex-valued. They can be tailored to suit real-valued data. A set of algorithms are derived and examples of computing the DFT are given.