A MATLAB project: This project will emphasize the practical aspects of the use o

Question

A MATLAB project:

This project will emphasize the practical aspects of the use of the DFT and the FFT in digital signal processing. (lettering in bold are MATLAB functions)

1. Write a MATLAB function that implements a DFT using the DFT summation formula. Include a listing of your function.

2. The overhead associated with the loops and the calculation of the multipliers in a DFT is considerable in MATLAB. To eliminate this from the process, create a matrix F that can be used to multiply a column vector to perform a DFT: F = dftmtx(2^11);

Create a random sequence N = 211 points long. Perform a DFT by multiplying the sequence (as a column vector) by the DFT matrix. Report the time required for the DFT matrix multiply. Do not include the time required to create the DFT matrix. Use tic and toc or cputime to time this operation. (To get accurate timing, before you begin, create the output variable by doing something like

Xf = zeros(2^11,1);

Compare to the time required for calculating the DFT of the same sequence using the function you wrote.

3. Use fft to compute the DFT of the same sequence, and report the time. (Do the FFT in a loop 10,000 times and average the resulting time.)

4. Determine the time required to compute an FFT in MATLAB of a sequence with length 2 11 9. Explain why this takes longer than a length-211 FFT. Do you believe MATLAB is calculating this with a direct DFT? Why or why not?

5. If the time is proportional to N log2 N, find the scale factor A such that time T = AN log2 N for the case when N = 211. Using the same constant, what time is predicted for N = 212? Now, following the same procedure as described above in MATLAB, determine the time required for a length-212 FFT. Comparing this to the timing results predicted by the formula T = AN log2 N, does the time increase grow in proportion to the number of multiplies N log2 N as the length N goes from 211 to 212?

6. Write a MATLAB function that implements a linear convolution of two arbitrary input sequences of arbitrary length using power-of-two FFT’s. (The MATLAB fft function can be called with an optional argument that specifies the sequence length; specify a length that is equal to a power of two. nextpow2 may be helpful.) Include a listing of your function. Generate two sequences of length 212. (It doesn’t matter what they are.) Convolve the two sequences with your function and with conv. Compare the result to make sure they’re the same, and compare the time required to run them. (You may need to accumulate the time required for 1000 runs and then average.)

Explanation / Answer

1.

Code to copy:

function X = DFT(s)

N = length(s);

Xi = 0; X = 0;

for k = 1:N;

for n = 1:N;

Xi(n) = s(n)*exp(-j*2*pi*(n-1)*(k-1)/N);

end

X(k) = sum(Xi);

End

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.