DFT Linear Filtering Computation MCQ Quiz – Objective Question with Answer for DFT Linear Filtering Computation

1. If the desired number of values of the DFT is less than log2N, a direct computation of the desired values is more efficient than the FFT algorithm.

A. True
B. False

To calculate an N point DFT using the FFT algorithm, we need to perform (N/2) log2N multiplications and N log2N additions.

But in some cases where the desired number of values of the DFT is less than log2N such a huge complexity is not required.

So, direct computation of the desired values is more efficient than the FFT algorithm.

2. What is the transform that is suitable for evaluating the z-transform of a set of data on a variety of contours in the z-plane?

A. Goertzel Algorithm
B. Fast Fourier transform
C. Chirp-z transform
D. None of the mentioned

Chirp-z transform algorithm is suitable for evaluating the z-transform of a set of data on a variety of contours in the z-plane. This algorithm is also formulated as linear filtering of a set of input data. As a consequence, the FFT algorithm can be used to compute the Chirp-z transform.

3. According to Goertzel Algorithm, if the computation of DFT is expressed as a linear filtering operation, then which of the following is true?

A. yk(n)=$$\sum_{m=0}^N x(m)W_N^{-k(n-m)}$$

B. yk(n)=$$\sum_{m=0}^{N+1} x(m)W_N^{-k(n-m)}$$

C. yk(n)=$$\sum_{m=0}^{N-1} x(m)W_N^{-k(n+m)}$$

D. yk(n)=$$\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}$$

Since WN-kN = 1, multiply the DFT by this factor. Thus

X(k)=WN-kN$$\sum_{m=0}^{N-1} x(m)W_N^{-km}=\sum_{m=0}^{N-1} x(m)W_N^{-k(N-m)}$$

The above equation is in the form of a convolution. Indeed, we can define a sequence yk(n) as

yk(n)=$$\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}$$

4. If yk(n) is the convolution of the finite duration input sequence x(n) of length N, then what is the impulse response of the filter?

A. WN-kn
B. WN-kn u(n)
C. WNkn u(n)
D. None of the mentioned

We know that yk(n)=$$\sum_{m=0}^{N-1} x(m)W_N^{-k(n-m)}$$

The above equation is of the form yk(n)=x(n)*hk(n)
Thus we obtain, hk(n)= WN-kn u(n).

5. What is the system function of the filter with impulse response hk(n)

A. $$\frac{1}{1-W_N^{-k} z^{-1}}$$

B. $$\frac{1}{1+W_N^{-k} z^{-1}}$$

C. $$\frac{1}{1-W_N^k z^{-1}}$$

D. $$\frac{1}{1+W_N^k z^{-1}}$$

We know that hk(n)= WN-kn u(n)

On applying z-transform on both sides, we get

Hk(z)=$$\frac{1}{1-W_N^{-k} z^{-1}}$$

6. What is the expression to compute yk(n) recursively?

A. yk(n)=WN-kyk(n+1)+x(n)
B. yk(n)=WN-kyk(n-1)+x(n)
C. yk(n)=WNkyk(n+1)+x(n)
D. None of the mentioned

We know that hk(n)=WN-kn u(n)=yk(n)/x(n)
=> yk(n)=WN-kyk(n-1)+x(n).

7. What is the equation to compute the values of the z-transform of x(n) at a set of points {zk}?

A. $$\sum_{n=0}^{N-1} x(n) z_k ^n$$, k=0,1,2…L-1

B. $$\sum_{n=0}^{N-1} x(n) z_{-k}^{-n}$$, k=0,1,2…L-1

C. $$\sum_{n=0}^{N-1} x(n) z_k^{-n}$$, k=0,1,2…L-1

D. None of the mentioned

According to the Chirp-z transform algorithm, if we wish to compute the values of the z-transform of x(n) at a set of points {zk}. Then,

X(zk)=$$\sum_{n=0}^{N-1} x(n) z_k^{-n}$$, k=0,1,2…L-1

8. If the contour is a circle of radius r and the zk are N equally spaced points, then what is the value of zk?

A. re-j2πkn/N
B. rejπkn/N
C. rej2πkn
D. rej2πkn/N

We know that, if the contour is a circle of radius r and the zk are N equally spaced points, then what is the value of zk is given by rej2πkn/N

9. How many multiplications are required to calculate X(k) by chirp-z transform if x(n) is of length N?

A. N-1
B. N
C. N+1
D. None of the mentioned

We know that yk(n)=WN-kyk(n-1)+x(n).Each iteration requires one multiplication and two additions. Consequently, for a real input sequence x(n), this algorithm requires N+1 real multiplications to yield not only X(k) but also, due to symmetry, the value of X(N-k).

10. If the contour on which the z-transform is evaluated is as shown below, then which of the given condition is true?

A. R0>1
B. R0<1
C. R0=1
D. None of the mentioned

From the definition of chirp z-transform, we know that V=R0e.

If R0>1, then the contour which is used to calculate z-transform is as shown below.

11. How many complex multiplications are needed to be performed to calculate chirp z-transform? (M=N+L-1)

A. log2M
B. Mlog2M
C. (M-1)log2M
D. Mlog2(M-1)

Since we will compute the convolution via the FFT, let us consider the circular convolution of the N point sequence g(n) with an M point section of h(n) where M>N.

In such a case, we know that the first N-1 points contain aliasing and that the remaining M-N+1 points are identical to the result that would be obtained from a linear convolution of h(n) with g(n).

In view of this, we should select a DFT of size M=L+N-1. Thus the total number of complex multiplications to be performed is Mlog2M.

12. The effect of round-off errors due to the multiplications performed in the DFT with fixed-point arithmetic is known as Quantization error.

A. True
B. False

Since DFT plays a very important role in many applications of DSP, it is very important for us to know the effect of quantization errors in its computation.

In particular, we shall consider the effect of round-off errors due to the multiplications performed in the DFT with fixed-point arithmetic.

13. What is the model that has been adopted for characterizing a round-off error in multiplication?

A. Multiplicative white noise model
B. Subtractive white noise model
D. None of the mentioned

The additive white noise model is the model that we use in the statistical analysis of round-off errors in IIR and FIR filters.

14. How many quantization errors are present in one complex-valued multiplication?

A. One
B. Two
C. Three
D. Four

We assume that the real and imaginary components of {x(n)} and {WNkn} are represented by ‘b’ bits. Consequently, the computation of product x(n).

WNkn requires four real multiplications. Each real multiplication is rounded from 2b bits to b bits and hence there are four quantization errors for each complex-valued multiplication.

15. What is the total number of quantization errors in the computation of single point DFT of a sequence of length N?

A. 2N
B. 4N
C. 8N
D. 12N

Since the computation of single point DFT of a sequence of length N involves N number of complex multiplications, it contains 4N number of quantization errors.

16. What is the range in which the quantization errors due to rounding off are uniformly distributed as random variables if Δ=2-b?

A. (0,Δ)
B. (-Δ,0)
C. (-Δ/2,Δ/2)
D. None of the mentioned

The Quantization errors due to rounding off are uniformly distributed random variables in the range (-Δ/2, Δ/2) if Δ=2-b. This is one of the assumptions that is made about the statistical properties of the quantization error.

17. The 4N quantization errors are mutually uncorrelated.

A. True
B. False

The 4N quantization errors are mutually uncorrelated. This is one of the assumptions that is made about the statistical properties of the quantization error.

18. The 4N quantization errors are correlated with the sequence {x(n)}.

A. True
B. False

According to one of the assumptions that is made about the statistical properties of the quantization error, the 4N quantization errors are uncorrelated with the sequence {x(n)}.

19. How is the variance of the quantization error related to the size of the DFT?

A. Equal
B. Inversely proportional
C. Square proportional
D. Proportional

We know that each of the quantization has a variance of Δ2/12=2-2b/12.

The variance of the quantization errors from the 4N multiplications is 4N. 2-2b/12=2-2b(N/3).

Thus the variance of the quantization error is directly proportional to the size of the DFT.

20. Every fourfold increase in the size N of the DFT requires an additional bit in computational precision to offset the additional quantization errors.

A. True
B. False

We know that the variance of the quantization errors is directly proportional to the size N of the DFT. So, every fourfold increase in the size N of the DFT requires an additional bit in computational precision to offset the additional quantization errors.

21. What is the variance of the output DFT coefficients |X(k)|?

A. $$\frac{1}{N}$$

B. $$\frac{1}{2N}$$

C. $$\frac{1}{3N}$$

D. $$\frac{1}{4N}$$

We know that the variance of the signal sequence is

(2/N)2/12=$$\frac{1}{3N^2}$$

Now the variance of the output DFT coefficients

|X(k)|=N.$$\frac{1}{3N^2} = \frac{1}{3N}$$.

22. What is the signal-to-noise ratio?

A. σX2.σq2
B. σX2/σq2
C. σX2+σq2
D. σX2-σq2

The signal-to-noise ratio of a signal, SNR is given by the ratio of the variance of the output DFT coefficients to the variance of the quantization errors.

23. How many number of bits are required to compute the DFT of a 1024 point sequence with an SNR of 30db?

A. 15
B. 10
C. 5
D. 20

The size of the sequence is N=210. Hence the SNR is10log10(σX22/σq2)=10 log1022b-20

For an SNR of 30db, we have

3(2b-20)=30=>b=15 bits.

Note that 15 bits are the precision for both addition and multiplication.

24. How many number of butterflies are required per output point in the FFT algorithm?

A. N
B. N+1
C. 2N
D. N-1