You\'re working as an engineer, and are tasked with calculating the output of a

Question

You're working as an engineer, and are tasked with calculating the output of a FIR filter h[n]. The length of the filter is L = 200. and the length of the input signal x[n] is N = 10,000. You decide that the most efficient way to compute the output (after some zero padding) is to take the DFT of h[n] take the DFT of x[n] multiply the DFTs together, and take the inverse DFT of the result. In order to have an identical output using the DFT method, and standard convolution, what is the minimum number of zeros you need to append to the end of x[n]? What is the total length of 'zero padded' version of x[n]? How many zeros do you need to append to h[n]? Assume the following approximate computational counts are exactly true - directly convoluting the signal requires exactly 2LN computations. a length N DFT or inverse DFT, requires N log N computations (where the log is base 2). multiplying two length N DFTs requires N operations. Calculate the number of operations required by direct convolution and by your DFT method. is your DFT method faster? a. No. Direct convolution is faster. b. The method is of indeterminable period. c. Yes. It's way faster.

Explanation / Answer

Solution :

Given length of input sequence x[n] = 10000

Given length of filter sequence h[n] = 100

hence the output sequence will be linear convolution of them resulting in length = 10000+100 -2 = 10098

so to make convolution result same :

pad x[n] with 100-1 = 99 zeros .............answer

pad h[n] with 10 000 -1 = 9999 zeros .............answer

so now zero padded x[n] has length = 10099 ...........answer

and h[n] has length as well = 10099 , which will capture all the output correctly !!

In our method :

let : P = L+N-1

output = ifft( fft(x,P) * fft(h,P) )

output = ifft( PlogP operations +P operations )

ouput = O(PlogP) complexity

while regular convolution:

output = x(P)*h(P)

output = O(2P*P) = O(P2) complexity.

so Yes , fft is faster.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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