Overlap Add Method & Overlap Save Method

For a larger valued sequence, we need to decompose the input signal as it is not possible to implement the data together at the same time. Hence, it is necessary to decompose the input signal into multiple finite signals to perform various operations. 

Thus for FFT, faster algorithms are used viz. Overlap add Method and Overlap Save Method.

In OAM, overlapping occurs but the overlapped portion is added to get the required output sequence. Whereas, in OSM overlapping occurs too but the overlapped portion is discarded. As we use convolution to find the output, decomposing helps in finding a more accurate output.

Also, OAM & OSM are equally fast methods to find the output of the FFT based input.

Fast Fourier Transform

FFT is a faster and efficient computational method for DFT. Fast Fourier transform reduces the number of computations required considerably when compared with DFT.

The signal is divided into 2 parts; the real and imaginary parts are calculated separately. The result is displayed as Z=X+IY i.e. Z= (real)+i(imaginary).
Thus, for a 4 point signal, two stages will be required which are executed using separate array multiplications.
FFT is used for parallel processing as it improves efficiency.

Discrete Fourier Transform

Discrete Fourier Transform is used to convert a Time domain signal into a Frequency domain signal. We used C programming language to implement the code.

We used arrays to store the values of coefficients of input signal. The real and imaginary parts of the output were computed independently and their values were stored in two different arrays.

By comparing the two DFTs (4 point and 8 point), it was found that the 8 point DFT was more accurate. So as N in N-point DFT increases the magnitude spectrum gets more closer to the actual spectrum which involves infinite length of x[n]. Thus, output of DFT is periodic.

Discrete Convolution & Correlation

The aim of this experiment was to study basic signal processing computations like Convolution and Correlation. Convolution is a mathematical way of combining two signals to form a third signal. We also need to know the basics of C programming.

The length of output of convolution y(n) was found to be one less than the length of the two input signals x(n) & h(n) by varying the length of one signal, keeping the other constant. 
Thus, the length N=L+M-1 (where N = Length of y(n), L = Length of x(n) & M = Length of h(n)). We also found that circular convolution gives aliased output i.e. the last few values get mixed (added) with the first.

For auto and cross correlation, we chose two signals; an input signal and its delayed input. Thus, correlation is used to fins similarity between two signals.

Also, zero padding is used in both convolution and correlation to get the required signal for processing.