Overlap Add Method(OAM) and Overlap Save Method(OSM)

                   After realizing the usefulness of FFT algorithm, it is necessary to understand its implementation in practical systems for faster and smarter(less calculative) operation. In real-time environment the long and indefinite length signals (unlike FFT) . To ensure proper analysis two methods: Overlap Add Method(OAM) and Overlap Save Method(OSM) are used. In both these methods the samples are divided into groups of samples such that the output of convolution of each group and the system function will have length equal to 2^N where N is an integer. To evaluate OAM and OSM in time domain Linear and Circular Convolution is used respectively. At times circular convolution is faster and hence, OSM can perform better.

Fast Fourier Transform

                        After understanding the complications involved in computing DFT it is time to understand its faster version i.e. the Fast Fourier Transform(FFT) algorithm (i.e.it is not a mathematical concept, it is a way to reduce calculations used in DFT) . FFT is implemented using two algorithms namely Decimation in Time FFT(DITFFT) and Decimation in Frequency FFT(DIFFFT). Both these algorithms take the same time for execution as same number of assembly instructions(after conversion from C program) are same overall. In case of DITFFT, after accepting the input, the samples are re-arranged whereas in case of DIFFFT the samples are taken as it is, but the output is re-arranged. After implementation of both algorithms, the outputs, execution time and computations involved were exactly the same. 

Discrete Fourier Transform

             As part of the next practical, Discrete Fourier Transform(DFT) had to be implemented on both a PC and DSP. Using C programming and the in-built mathematical operations(primarily sine and cosine) the DFT output can be observed in the form of 2 arrays(A[k] real and B[k] imaginary) for displaying complex numbers. By using both the above mentioned hardware, a fast response was observed. DFT is preferred only for smaller length inputs. For high length inputs , the computations involved are very high and hence DFT is not preferred. Also the complex computations are more.

Discrete Convolution and Correlation

                      The operations involved in Convolution and Correlation are multiplication and addition. On executing a C programs on both PC and DSP the result is the same as that obtained theoretically. Here, mainly arrays are used as operands for these operations. The operations performed were Linear and Circular Convolution and Auto Correlation(of same and delayed input signal) and Cross Correlation. Convolution is used to find output of any system for any given input. The length of output signal is L+M-1, where L and M are lengths of input signals. Whereas, correlation is used to find the degree of similarity of input signals which can be obtained by the Correlation coefficients. Correlation coefficients are obtained by calculating the variance of the input signal.