Overlap Add and Overlap Save

There are 2 types of input signal x[n] and h[n]. In real time processing the size of input is very large. So performing convolution becomes a difficult task. To overcome this problem we have 2 methods viz-
1. Overlap Add method
2. Overlap Save method

In overlap add method first we calculate the value of L using the formula L=N-M+1 where N is the length of output signal M is the length of h[n] and L is the length of input signal. After this we decompose the signal x[n] into parts each of length L and then the convolution is done between these signals and h[n] individually and then we get the final output by shifting and adding the individual output signals.

In overlap save method we decompose the input signals into parts but in this the next decomposed signal is started with previous signal's saved values and the convolution is done individually and the output is all the values except the saved values.

That is these techniques are known as block processing techniques. 

Fast Fourier Transform

In real time processing we obviously can't use DFT because it is slow in processing due to lots of calculations. So we use FFT which is Fast Fourier Transform. An FFT is a way to compute same result more quickly : computing the DFT of N points in naïve way, if we go by the definition of DFT it will take N*N arithmetic operations while FFT can compute the same DFT in only NlogN operations. We implemented this using Cooley and Tukey's radix-2 DITFFT algorithm. DITFFT stands for Decimation In Time Fast Fourier Transform. Signal is decimated in time domain so as to reduce no. of calculations, reducing calculations means increase in speed. 

Discrete Fourier Transform

This was an experiment with lots of learning experience. In this experiment previous C programming concepts were also covered like function calling using call by value and call by reference method. DFT is the frequency domain representation of the original input sequence. DFT signal output is always periodic. Using DFT we can reduce approximation errors and also resolution of the spectrum can be increased. DFT results has high accuracy due to periodicity. So if your signal is not periodic it has to be assumed periodic to get better and accurate results.

The limitation of DFT is that it is slow for real time processing due to lots of real and complex calculations. So to overcome this problem we use FFT-Fast Fourier Transform. 

Convolution and Correlation

This was a great experience learning Convolution and Correlation. First we will talk about convolution. There are 2 types of convolution one is Linear and the other is Circular. In Linear Convolution the length of output signal is always sum of the length of the inputs minus one. Also if both the input signals are causal then resultant output is also causal. But in circular convolution the length of output signal is the length which is maximum between both the input signals. Also circular convolution gives aliased output.

Now we will talk about correlation. In correlation there are 2 types one is auto correlation and the other one is cross correlation. Auto correlation signal is always an even signal. Auto correlation of delayed input signal is same as auto correlation of original signal. Cross correlation of input signal with delayed input signal is same as advanced auto correlated signal. Correlation is used to find degree of similarity between 2 signals.