ABSTRACT
The discrete Fourier transform (DFT) that transforms one function into another is called the frequency domain representation; it requires a discrete input function whose nonzero real or complex values are finite. Unlike the discrete-time Fourier transform (DIFT), the DFT only evaluates enough frequency components to reconstruct the finite segment that was analyzed. The DFT is used in processing information (data) stored in computers, and in signal processing and related fields where the frequencies in a signal are analyzed. An efficient computation of the DFT is provided by a fast Fourier transform (FFT) algorithm. Although DFT refers to a mathematical transformation while FFT refers to a specific family of algorithms for computing DFTs, the FFT algorithms commonly used to compute DFTs often mean DFT in common terminology, which has now become confusing by taking FFT as synonymous with DFT. For more details, see Kythe and Scha¨ferkotter [2005: 299 ff]. The DFT is defined as follows: Let a sequence of n nonzero complex numbers {x0, . . . , xn−1} be transformed into a sequence of m complex numbers {X0, . . . , Xm−1} by the formula
Xj = n−1∑ k=0
xk e −2pijk i/m for 0 ≤ j ≤ m− 1; i =
√
−1, (D.1)
where
xk = 1
m
Xj e 2pikj i/m for 0 ≤ k ≤ n− 1. (D.2)
Formula (D.1) is known as the DFT analysis equation and its inverse (D.2) the DFT synthesis equation, or the inverse discrete Fourier transform (IDFT). The DFT pair can be represented as
−→ Xj and Xj IDFT
−→ xk. (D.3)
k by
xk =
2 k = 0,
3 k = 1,
−1 k = 2,
1 k = 3.
