# 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: kfs/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

Complexity of DFT versus FFT
• The N-point DFT requires N2 multiplications and N2-1 additions to compute the discrete frequency spectrum.
• The complexity of the DFT is reduced using the FFT to N/2log2N multiplications and Nlog2N additions.
• For example if N=4096 the DFT requires 16,777,216 multiplications while the FFT requires 49,152 multiplications.