Discrete Fourier Transform and Discrete Systems
Taan S. ElAli · 2020
The discrete Fourier transform (DFT) is a computer program that can be used to transform the signal x ( n ) defined for n = 0, 1, …, N − 1, where N is the number of samples in x ( n ), to X ( k ), a set of N values defined for the frequency index k = 0, 1, …, N − 1. In other words, the DFT can be thought of as a system (a computer program) whose input is x ( n ) and whose output is X ( k ). The fast Fourier transform (FFT) is also a computer program used to implement the DFT in a much faster way. Yet to calculate the N values for k we will need N 2 multiplications. The goal is to reduce this number of multiplications. For that reason, the FFT, a fast way of computing the DFT, was developed in which the number of multiplications N 2 was reduced to N (log 2 N )/2 multiplications. Thus, if N = 1024, for example, it will take 10,48,576 multiplications using the DFT. Using the FFT, it will take 5120 multiplications, a drastic reduction in the number of multiplications. In this chapter, many applications of the DFT will be introduced. Applications related to circular convolution, linear convolution, approximation to the continuous Fourier transform, calculating Fourier series coefficients and average power, total energy in the signal, block filtering, and correlations will be discussed.