Filtering of long data sequences

Overlap Add Method(OAM) and Overlap Save Method(OSM) are used to calculate linear convolution. These are especially efficient when the length of input sequence is large as is the case with practical real time systems. These are block processing techniques that means the input sequence is divided into blocks of suitable length and convolution of each block is found out. The output is then computed by adding the overlapping portion in OAM and discarding the overlapping portion in OSM. Output using both the techniques is same and this was verified through code.

Fast Fourier Transform

Number of computations required in DFT are large which is not suitable for real time systems. To overcome this problem we use Fast Fourier Transform(FFT). Radix-2 FFT was calculated according to the butterfly diagram  for N=4 and N=8. The computations required for FFT i.e. the number of real and complex multiplications and additions was found out through the code and verified with the formula. Thus FFT proved to be computationally efficient.

Discrete Fourier Transform

Discrete Fourier Transform is the frequency sampled version of DTFT. To calculate DFT, the input sequence was assumed to be periodic. DFT for input length N=4 and N=8 was calculated. Output of DFT is periodic and it repeats after N values.Using Inverse DFT the input sequence was verified. Magnitude spectrum for N=4 and N=8 was plotted. It was found that increasing the number of inputs through zero padding increases the resolution of the magnitude spectrum.

Convolution and Correlation

C programming was used to find  Convolution and Correlation of two causal input sequences. Convolution is used to find the response i.e. the output of a system while correlation gives the degree of similarity between two signals. Linear convolution is performed for non periodic signals while circular convolution is done for periodic signals. Aliasing effect (overlapping of values) was observed in Circular Convolution. Linear convolution using circular convolution was also performed. Similarity of a signal with itself, with a shifted version and scaled version of that signal was found.