Our project involved an exploration of the world of digital signal processors, more commonly known as DSP’s.  We obtained a TMS320C5410 Evaluation Module (EVM) and used TI Code Composer as our development environment.  Our goal was to program the DSP to allow us to filter signals in real-time.  The handy DSP function library provided with the C5410 allowed us to avoid reinventing the wheel and instead use the signal processing functions provided. 

 

Tri-Buffer Setup:  In order to allow for real-time processing of our input signal, we initially implemented a three buffer “circular pipeline” algorithm.  Each buffer is of equal length.  One buffer is used to store the input audio stream.    Once this buffer is full, it moves to the next stage of the pipeline – we take the fft of the data, apply some sort of filter to the transformed data and then ifft the result to get back a usable signal.  In the final stage of the pipeline, the filtered data in the buffer is transmitted.  The following table summarizes the operation of our circular pipeline:

 

Time Unit	Buffer 1 Operation	Buffer 2 Operation	Buffer 3 Operation
1	Receive	-	-
2	FFT/Filter/IFFT	Receive	-
3	Transmit	FFT/Filter/IFFT	Receive
4	Receive	Transmit	FFT/Filter/IFFT
5	FFT/Filter/IFFT	Receive	Transmit
6	Transmit	FFT/Filter/IFFT	Receive
7	Receive	Transmit	FFT/Filter/IFFT

 

A time unit is equal to (length of a buffer / the number of interrupts per second) seconds

 

The simplicity and elegance of this algorithm belies an unfortunate shortcoming.  There is no overlap in data between buffers.  In essence, we applied non-overlapping rectangular windows to our input data stream.  When we transform this data to the frequency domain, oscillations will appear in the spectrum, making it difficult to ascertain the signal’s spectrum at an instance in time. 

 

Our previous algorithm treated our infinitely long input signal as a series of disparate segments of finite length.  After we finish operating on each segment, we must reconnect it with other segments; there will be distortions at the connection points.  A cursory inspection of the problem would lead one to believe that we should simply store the entire input signal, take its fft and then operate on it.  However, we are implicitly assuming that the input signal is infinitely long and so this method is not possible.  Thus we must divide the input sequence into a series of finite length segments, calculate the convolution between each segment and the impulse response sequence and then connect the convolution results without any distortions at the connection points between each individual segment.  We are assuming that FIR filters will be developed, so the length of the impulse response is finite.  Only the input data signal is of infinite length.

 

To this end, we implemented a different algorithm – Overlap Save Block Convolution.  This method requires that the input blocks overlap; we chose to let our input blocks overlap by half of our buffer length.  We then circularly convolve the input blocks with the impulse response (equivalent to multiplying the fft of the input and the fft of the impulse response and then taking the ifft of the result).  There will now be redundancy in data (because input blocks overlap) and we will discard the circular artifacts in our output.  This method will reduce the oscillations in the frequency domain, but is also much more computationally expensive. The overlap between blocks of data means we are operating on all of our data points twice.

 

A step-by-step description of the algorithm:

1. Place a block of N data points into the [N…2N-1] positions of a buffer of length 2N.  This is the data we are interested in filtering.
2. Place the previous N data points in the [0…N-1] positions of the buffer.  This data is present to allow us to reconnect our data blocks with distortion at the connection points.
3. Perform an out of place complex bit reversal on the data buffer, placing the result in a temporary storage location in memory. 
4. Calculate the fast fourier transform of the data buffer. 
5. Apply the filter to the data buffer.
6. Perform an out of place complex bit reversal on the data buffer, placing the result back in its original memory location. 
7. Calculate the inverse fast fourier transform of the data buffer. 
8. The first N points of data in the buffer are now ready to be transmitted.  The last N points of data in the buffer contain “circular artifacts” and can be ignored.

 

An out of place complex bit reversal is performed because it is less computationally expensive than an in place complex bit reversal.  The tradeoff is that more memory is required, but memory is not a constraint in our implementation for N <= 128 data points.  Also, the N data points placed in the front half of the buffer that we transform and filter have already been operated upon.  In the previous iteration of the algorithm, they were placed in the second half of the data buffer, to allow the fourier transform to work properly on the preceding N data points.