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

(1) take the DFT of h[n]

(2) take the DFT of x[n]

(3) multiply the DFTs together, and take the inverse DFT of the result.

a. 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]?

b. What is the total length of 'zero padded' version of x[n]?

c. How many zeros do you need to append to h[n]?

Explanation / Answer

Answer:

W.K.T,

Let the given values be,

Length of the filter sequence (L) = 200 & Length of the input sequence, N = 10,000.

Hint:

(From the given problem, we have two arrangements of length L & N, therefore the total length of output due to linear convolution is L+N-1. The dissimilarity between length(L) and length of L+N-1 are number of zeros to be append to length sequence(L) i.e N-1 and difference between length of N and length of L+N-1 is to be append to length sequence N i.e L-1 to make together the sequence equal to length L+N-1)

From the above hint,

Length of sequence due to the convolution over the above two is becomes by,

Linear convolution = 200 + 10000 -1 = 10,199.

Part a) Minimum number of zeros to be append in x[n] = 10199 – 10000 = 199

Part b) Total length of ‘zero padded’ version of x[n] = L+N-1 = 10199

Part c) Zeros to be append to h[n] = 10199 - 200 = 9999.

Let us consider one example:

x[n] is N=10000 samples(Larger) and h[n]=200 samples(smaller), so we can divide x[n]= 256 of length and append h[n]=56(zeros) to make it also 256.

Let us yield DFTs of all separate 256 sample of long parts is x[n] & with 256 samples of h[n], hence add them by add and save or add & overlap algorithm. Since we take 256 samples as 256 which is close to 200. For this case, need of 240 zeros to be append to x[n] to create the length of x[n] which is divisible by 256 (i.e., 40*256=10240, for that we need 10240-10000=240 zeros).

Form the above example, it will produce the same result. So that from the circular convolution formed due to padding & therefore taking DFT and IDFT processes yield a result is same as by linear convolution.

Note:

Reference Book: “A Self-Study Guide for Digital Signal Processing”, by Proakis – Refer Chapter No.5

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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