<< Chapter < Page | Chapter >> Page > |
The discrete Fourier transform (DFT) is the primary transform used for numerical computation in digital signal processing. It is very widely used for spectrum analysis , fast convolution , and many other applications. The DFT transforms $N$ discrete-time samples to the same number of discrete frequency samples, and is defined as
The inverse DFT (IDFT) transforms $N$ discrete-frequency samples to the same number of discrete-time samples. The IDFT has a form very similar to the DFT,
Due to the $N$ -sample periodicity of the complex exponential basis functions $e^{i\frac{2\pi nk}{N}}$ in the DFT and IDFT, the resulting transforms are also periodic with $N$ samples.
$$X(k+N)=X(k)$$ $$x(n)=x(n+N)$$
A shift in time corresponds to a phase shift that is linear in frequency. Because of the periodicity induced by the DFT and IDFT, the shift is circular , or modulo $N$ samples.
$$\uf57b(x((n-m)\mod N), X(k)e^{-(i\frac{2\pi km}{N})})$$ The modulus operator $p\mod N$ means the remainder of $p$ when divided by $N$ . For example, $$9\mod 5=4$$ and $$-1\mod 5=4$$
$$\uf57b(x(-n\mod N)=x((N-n)\mod N), X((N-k)\mod N)=X(-k\mod N))$$ Note: time-reversal maps $\uf57b(0, 0)$ , $\uf57b(1, N-1)$ , $\uf57b(2, N-2)$ , etc. as illustrated in the figure below.
$$\uf57b(\overline{x(n)}, \overline{X(-k\mod N)})$$
Circular convolution is defined as $$\doteq ((x(n), h(n)), \sum_{m=0}^{N-1} x(m)x((n-m)\mod N))$$
Circular convolution of two discrete-time signals corresponds to multiplication of their DFTs: $$\uf57b((x(n), h(n)), X(k)H(k))$$
A similar property relates multiplication in time to circular convolution in frequency. $$\uf57b(x(n)h(n), \frac{1}{N}(X(k), H(k)))$$
Parseval's theorem relates the energy of a length- $N$ discrete-time signal (or one period) to the energy of its DFT. $$\sum_{n=0}^{N-1} \left|x(n)\right|^{2}=\frac{1}{N}\sum_{k=0}^{N-1} \left|X(k)\right|^{2}$$
The continuous-time Fourier transform , the DTFT , and DFT are all defined as transforms of complex-valueddata to complex-valued spectra. However, in practice signals are often real-valued.The DFT of a real-valued discrete-time signal has a special symmetry, in which the real part of the transform values are DFT even symmetric and the imaginary part is DFT odd symmetric , as illustrated in the equation and figure below.
$x(n)$ real $X(k)=\overline{X((N-k)\mod N)}$ (This implies $X(0)$ , $X(\frac{N}{2})$ are real-valued.)
Notification Switch
Would you like to follow the 'The dft, fft, and practical spectral analysis' conversation and receive update notifications?