6.2 Lab 5: prelab  (Page 4/4)

Matlab simulation

Using your results from the previous part, simulate the two-stage multi-rate filter in MATLAB. Plot the frequencyresponse of each stage's filter using freqz and determine the overall frequency response of your multi-rate system to verify thatit meets the specifications. Since there is not a command for directly finding the frequency response plot of amulti-rate system in MATLAB, you will have to be a bit creative.

Additional questions (optional, but for your benefit)

• Does it make a difference in which order the two decimations are done in a two-stage implementation?
• Could / would you add additional stages? Why or why not?
• Are quantization effects more or less pronounced in the multi-stage implementation compared to a directimplementation? Why or why not?

Fourier-based filtering methods

It is possible to perform linear convolution quickly using the FFT. This idea allows for the efficient implementation of aFIR filter when the number of filter coefficients and the length of the input sequences are large.

Questions

• Read Lecture 49 of the ECE 310 Course Notes on "Block Convolution." This lecture provides an excellent overviewof two methods for efficiently performing convolution using the FFT: "Overlap and Add" and "Overlap and Save." For amore in depth treatment of these methods, refer to Discrete-Time Signal Processing by Alan Oppenheim and RonaldSchafer.
• Simulate both an (1) overlap and add and an (2) overlap and save filtering implementation in MATLAB. Yoursimulations should work for any choice of an FIR filter. The filter length M and block length L should be variableparameters.
• Verify that your simulated systems are working properly by comparing their performance with a direct FIRimplementation. Test using several FIR filter designs and appropriate test inputs.
• Derive expressions for the amount of computation (in terms of multiply accumulates) required per input sample forboth the overlap and add and overlap and save implementations. Plot the computation per sample as afunction of the input block length (for a particular filter size M) for both schemes. Is there a value of M for whichthe Direct FIR is always more efficient? Derive an expression for the optimal block size L in terms of thefilter length M for both implementations.
• In the DSP implementation, the input sequence is purely real. The values of the imaginary components are allset to zero. We can speed up the implementations further by exploiting the symmetry properties of the Fourier transform.These properties are stated as follows:
  $\mathrm{DFT}(\Re (x(n)))=\mathrm{Even}(X(\omega ))$
  $\mathrm{DFT}(j\Im (x(n)))=\mathrm{Odd}(X(\omega ))$
  Using these properties, determine how to get two FFT's for the price of one. Implement this scheme in MATLAB, andverify that the operation is correct.
• Design a FIR filter that meets the filter specification given in the filter specification . Lecture 38 of the ECE 310 notes on "Parks-McClellan" might be a good reference here. Design an efficient implementation of this filterusing the methods you explored above. The MATLAB commands remezord and remez may be of great help. Simulate this implementation in MATLAB, programming in such a way that you can easilyconvert your MATLAB simulation to assembly. Find the number of computations per input for your method.
• What are the benefits and trade-offs of using the Fourier-based method in terms of accuracy of the filterspecification, finite precision errors, and computational expense? Compare with the IIR and multi-rate filterimplementations.

Be prepared to show all the necessary plots and MATLAB simulations as well as answers to all of the questions posedabove to your T.A. as your prelab.

Implementation issues

Due to the limitations of the core file, it is not possible to take in more than 64 input samples from the A/D converterat a time (unless the core file is rewritten to accomplish this task). Therefore, when implementing a Fourier-basedfilter, you should use the C skeleton from Lab 4 to perform the FFT on a large block of samples. All of your filteringoperations (i.e., the multiplications of DFT samples, the additions of the overlap, the discarding of samples) andfunction calls must be performed in assembly. You will be graded on the number of cycles per input sample based on theportion of code in your assembly routine.

You should use the fft.asm routine provided in Lab 4 to perform the forward and reverse FFT's.You should study this file to determine how it works. If you need to change the length of the FFT, you will firstneed to change the relevant parameters in your assembly file (i.e., N , K_FFT_SIZE , K_LOGN , and other variables). You will also need to change the following parameters in the FFTfile:

K_TWID_TBL_SIZE is the size of the twiddle tables (how long should these be for a given FFTlength?) and K_TWID_IDX_3 is the amount by which the program increments through the twiddletable during at the third stage of the FFT. What is this increment for a given N ? Is fft.asm a decimation in time or decimation in frequency algorithm?

You will also need a modified twiddle table when you change the length of the FFT to use fft.asm as written. For a length 1024 FFT, the twiddle tables arelength 512 each. TWIDDLE1 is a table of sine values from zero to $\pi$ , and TWIDDLE2 is a table of cosine values from $\frac{\pi }{2}$ to $\frac{\mathrm{3\pi }}{2}$ . The support for the cosine and sine is different because fft.asm code uses the fact that $\sin -\theta =-\sin \theta$ when performing computations. If you want a length 64 FFT, you will need to ``decimate'' the twiddle table to length32, or in other words, only keep one out of every 16 lines in the twiddle tables and discard the rest. We will providea MATLAB function, edit_twiddle.m for this purpose. The function call in this example would be:

You should verify that the new twiddle tables you generate indeed have 32 elements. To perform an inverse FFT, you canuse the standard FFT algorithm and then appropriately scale and shift the outputs. Lecture 43 of the ECE 310 notes onthe Discrete Fourier Transform suggests how this may be done (Property 3 of ``Properties of the DFT'').