# Discrete Fourier Transform

- The digital (sampled) version of the fourier transform. Any block size can be used. This technique involves long computations, and normally the Fast Fourier Transform is used instead due to its quicker computation.

- The discrete fourier transform of
*f*is - for
*n=0,1,.....,N-1*

- The inverse discrete fourier transform is
- for
*k=0,1,.....,N-1*

- The DFT transform is an exact one-to-one transform
- The DFT can only approximate the continuous Fourier Transform
- The DFT components correspond to N frequencies that are fs/N apart
- The DFT of a real-valued signal gives symmetric frequency components
- A fast algorithm, the FFT, is available for implementing the DFT
- The FFT has several applications in spectral analysis, speech analysis / synthesis, fast convolution, etc

**Frequency Resolution of the DFT**- The frequency resolution of the N point DFT is

- The DFT can resolve exactly only the frequencies falling exactly at: kf
_{s}/N. There is spectral leakage for components falling between the DFT bins - Typically we use an FFT that is as large as we can afford
- Zero-padding is often use to provide more resolution in the frequency components
- Zero padding is often combined with tapered windows

- The DFT can resolve exactly only the frequencies falling exactly at: kf

**Complexity of DFT versus FFT**- The N-point DFT requires N
^{2}multiplications and N^{2}-1 additions to compute the discrete frequency spectrum. - The complexity of the DFT is reduced using the FFT to N/2log
_{2}N multiplications and Nlog_{2}N additions. - For example if N=4096 the DFT requires 16,777,216 multiplications while the FFT requires 49,152 multiplications.

- The N-point DFT requires N

**See also: **Fast Fourier Transform, Fourier Analysis, Leakage, Windowing.

**Subjects: ** Analysis Computing Noise & Vibration Signal Processing