FAST FOURIER TRANSFORM (FFT)

An algorithm for fast computation of DFT is FFT(Fast Fourier Transform).The FFT algorithm divides the N-point DFT input signal into 2 parts-even and odd signal values of the input. The even signal values can be directly found out whereas the odd signal values is just multiplied by an appropriate twiddle factor which overall reduces the complex multiplications for FFT. This happens because the signal is divided into 2 parts, so the computation is carried out only for N/2 signal values. This increases the speed of computations and makes FFT faster than other algorithms.

DISCRETE FOURIER TRANSFORM (DFT)

Discrete Fourier Transform is carried out to overcome the limitation of Fourier series as well as DTFT. As length of signal increases, frequency spacing reduces, approximation error representation of spectrum decreases, resolution of spectrum increases, missing values in less point DFT are present in more point DFT. Ideally, the spectrum of DFT is discrete and also infinite but we calculate it only for one period of the signal values.For the same signal values with different periodic sequences,the output values of the bigger periodic sequences contains all the values of the output signal obtained from the smaller periodic sequences .Moreover,the values remain same for same period even if the number of samples increases.

OAM & OSM

           The aim of this experiment was to perform filtering of Long Data Sequence using Overlap Add Method and Overlap Save Method.We implemented the filtering of Long Input Sequence using Overlap Add / Overlap Save Algorithm.The Input Specifications were given as length of long data sequence and signal values and length of impulse response M and Signal values.

            We concluded that Overlap Add Method (OAM) and Overlap Save Method(OSM) are efficient methods to calculate the convolution between long length signal and finite impulse signal. Both the OAM and OSM require same amount of computations and hence memory.

                

Discrete Convolution and Correlation

In this experiment,we learned linear convolution,circular convolution and linear convolution using circular convolution. We used the mathematical formula of convolution and observed the results. The length of the input signal in linear convolution was L=4 and M=4, the length of the output signal is N=L+M-1,therefore N=4+4-1=7 (the length of output signal is 7). In circular convolution as we increase the   length of signal, zeros are added to the output signal. The length of the signal was N=max(L,M).In circular convolution we get aliased output.For linear convolution using circular convolution N>= L+M-1. Zero padding was observed.We studied aliasing effect.We also performed cross and auto correlation. The second case was having the same input but delayed. In auto correlation the value at the center is largest and the signal is symmetric.The application of correlation is to find the degree of similarity of two signals.