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

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

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

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

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.

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)}\)

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

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}}\)

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

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

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 re^j2πkn/N

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).

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

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

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.

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.

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

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).

WN^kn 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.

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.

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.

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

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)}.

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.

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.

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}\).

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.

The size of the sequence is N=210. Hence the SNR is10log₁₀(σX2²/σq²)=10 log₁₀2^2b-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.

We find that, in general, there are N/2 in the first stage of FFT, N/4 in the second stage, N/8 in the third state, and so on, until the last stage when there is only one. Consequently, the number of butterflies per output point is N-1.