Filtering of Long Data Sequences

Practical signals are very long. Simple FFT and multiplication are not enough. So, we have to develop additional methods to filter or analyse such signals. Two of the standard methods used are Overlap Add Method (OAM) and Overlap Save Method (OSM). Both of these are block processing techniques. Meaning that the input sequence is divided into blocks and the operations are carried out on these blocks.

Using C programming, we implemented both the methods. A FIR filter was assumed, to which input was given. OAM uses linear convolution. In the program, FFT was used to calculate the linear convolution using circular convolution. In OSM, circular was calculated, again with the help of FFT. These blocks can then be processed in real time.

Fast Fourier Transform

Fast Fourier Transform or FFT is at the heart of any DSP system. Converting to frequency domain and then sampling was a challenge overcome using DFT. But in today's world of real time processing DFT is too slow. If we want to, say, analyse the vibrations of a railway track caused by a train, then, if the DFT algorithm is started when the train approaches the track, two other trains would pass by before analysis is complete.

This definitely won't do. So FFT, which as the name suggests is a fast algorithm, is used. We studied implementing Cooley and Tukey's Radix-2 DITFFT algorithm. DIT stands for Decimation In Time. The signal is decimated in time domain which helps to reduce the number of calculations. We observed that the number of complex multiplications reduced greatly. This contributes to the speed. And the input and output sequence orders are in a bit reversed manner. So this model is easy to expand to higher values of N and improve the computational efficiency of DSP systems.

Discrete Fourier Transform

Everyone has heard of Fourier Transform (FT). It's used to convert a signal from time domain to frequency domain. But what is Discrete Fourier Transform?

I don't mean Discrete Time Fourier Transform, where the integral for Continuous Time FT is replaced with a summation, for discrete time signals. Discrete Fourier Transform (DFT) is the sampled form of DTFT. Since nowadays, almost all systems are digital, we have to sample the continuous signal given by DTFT, to obtain a discretised version of it. The signal is sampled at integer multiples of (2π/N). This, we can then process in a digital system.

We implemented this transform using C programming for an 'N' point discrete time signal. The value of 'N' was taken as input from the user. Of course, this discretisation is at the cost of accuracy. But this error can be decreased by appending zeros at the end of the actual signal, which gives a larger value of N giving us a better spectrum. The reason for this increase in the accuracy is that DFT always gives periodic results. So even if your signal is not periodic, it has to be assumed periodic! If we expand the original time domain signal, the DFT output gets compressed and vice versa.

The only drawback is that it's too slow for real time processing. A computer or any processor will take a lot of time to perform N square complex multiplications and N(N-1) complex additions. Obviously, we don't practically use this. The solution: Fast Fourier Transform!

Convolution and Correlation

Convolution and correlation are integral parts of any digital signal processing system. With a pen and paper, it's pretty easy to calculate. But how do we actually implement this on a digital signal processor or a computer?

That's what we studied: the implementation of linear and circular convolution, linear convolution using circular convolution and auto and cross correlation using C programming.

We saw how complicated it gets to perform simple operations like zero padding using a programming language. We took the length of the signals as the initial inputs for convolution and then entered the signals. The result was displayed on the screen. For circular, the greater of the two lengths was entered and by zero padding the result was displayed. We also realised that circular convolution gave an aliased output.

For correlation, we tried combinations of a signal delayed by different amounts with auto correlation and found that it always gave the same output. If we try cross correlation of a signal with its delayed self, we get a result that is an advanced signal from the auto correlation output. Thus we understood the importance of using correlation to find the degree of similarity between two signals. An added point: the value of autocorrelation output signal for n=0 is always the energy of the signal.