Digital Signal Processing interview Questions2

  III – Fast Fourier Transform

1). Why FFT is needed?

Ans: The direct computation of DFT requires N²  complex multiplications and N(N-1) complex additions. Thus for reasonably large values of N (in order of 1000) direct evaluation of the DFT requires an inordinate amount of computation. By using FFT algorithms the number of computations can be reduced. For example, for an N-point DFT, the number of complex multiplications required using FFT is log₂N. If N=16, the number of complex multiplications required for direct evaluation of DFT is 256, where by using DFT only 32 multiplications are required.

2). How many multiplications and additions are required to compute N-point DFT using radix-2 FFT?

Ans: The number of multiplications and additions required to compute N-point DFT using radix-2 FFT are log₂N and Nlog₂N respectively.

3). What is the difference between DIT FFT and DIF FFT?

Ans: In DIT FFT, input is bit-reversal order but output is in normal order. Where as in case of DIF FFT, input is in normal order but output is in bit-reversal order.

4). What is the basic operation of DIT algorithm?

Ans: The basic operation of DIT algorithm is so called butterfly in which two inputs X_m(p) and X_m(q) are combined to give the outputs X_m+1(p) and X_m+1(q) via. The operation

                                       X_m+1(p) = X_m(p)+W_N^K X_m(q)

                                       X_m+1(q) = X_m(p)-W_N^KX_m(q)

where W_N^K is called twiddle factor.

5). What is the basic operation of DIF algorithm?

Ans: The basic operation of DIT algorithm is so called butterfly in which two inputs X_m(p) and X_m(q) are combined to give the outputs X_m+1(p) and X_m+1(q) via. The operation

                                       X_m+1(p) = X_m(p)+ X_m(q)

                                       X_m+1(q) = [X_m(p)- X_m(q)] W_N^K

where W_N^K is called twiddle factor.

6). What is the formula to calculate the IDFT using FFT?

Ans: x(n) =  

7). What are the applications of FFT algorithms?

Ans: The applications of FFT algorithms are linear filtering, correlation and spectrum analysis.

8). In FFT algorithms, the number of stages in the flow graph is M= log₂N

9). In butterfly diagram, each stage consists of       number of butterflies.

10). In DIT FFT algorithm, inputs/outputs for each butterfly are separated by   samples.

11). In DIT FFT algorithm, what is the formula for twiddle factor exponents?

Ans:   k =

12). In DIT FFT algorithm, the number of sets or sections of butterflies in each stage is  .

13). In DIT FFT algorithm, what is the formula for exponent repeat factor?

Ans:   

14). In DIF FFT algorithm, inputs/outputs for each butterfly are separated by   samples.

15). In DIF FFT algorithm, what is the formula for twiddle factor exponents?

Ans:   k =

16). In DIF FFT algorithm, the number of sets or sections of butterflies in each stage is  .

17). In DIF FFT algorithm, what is the formula for exponent repeat factor (ERF)?

Ans:   

18). In FFT algorithms, what is symmetry property?

Ans:   The symmetry property is:  = -

19). In FFT algorithms, what is periodicity property?

Ans:   = 

20). What is meant by radix-2 FFT?

Ans: The FFT algorithm is most efficient in calculating N-point DFT. If the number of output points N can be expressed as a power of 2, that is, N=, where M is an integer, then this algorithm is known as radix-2 FFT algorithm.

                                                IV – Realization of digital filter

1).  What is meant by region of convergence?

Ans: The region of convergence (ROC) of X(z) is the set of all values of z for which X(z) attains a finite value.

2). ROC of a causal signal is the exterior of a circle of same raidus r.

3). ROC of an anti causal signal is the interior of a circle of same radius r.

4). What is the time shifting property of the Z-transform?

Ans: If Z{x(n)}= X(z), then Z{x(n-k)}= X(z)                                                       

5). What is the scaling  property of the Z-transform?

Ans: If Z{x(n)}= X(z) ROC: , then z[] = X() ROC:

6). What is the time reversal  property of the Z-transform?

Ans: If z{x(n)}= X(z)   ROC:  then z{x(-n)} = X()   ROC:

7). State the initial value theorem and final value theorem.

Ans: Initial value theorem: If x(n) is causal, then x(0)=

         Final value theorem: If x(n) is causal, Z[x(n)]=X(z), where the ROC for X(z) includes, but is not necessarily confined to |z|>1and (z-1}X(z) has no poles on or outside the unit circle, then x() =

8). An LTI system with the system function H(z) is BIBO stable if and only if the ROC for H(z) contains  unit circle.

9). What are the properties of region of convergence?

Ans: 1). The ROC is a ring or disk in the z-plain centered at the region.

         2). The ROC cannot contain any poles.

         3). The ROC of an LTI stable system contains the unit circle.

         4). The ROC must be a connected region.

10). What is the Z-transform of a digital step?

Ans:

11). The Z-transform of a sequence x(n) is X(z), what is the Z-transform of nx(n)?

Ans: If z{x(n)}=X(z) then z{nx(n)}= -z

12). What are the different methods of evaluating inverse z-transform?

Ans: Long division method, partial fraction expansion method, residue method and convolution method.

13). How many number of additions, multiplications and memory locations are required to realize a system H(z) having M zeros and N poles in direct-form I realization (b) direct-form II realization?

Ans: The direct-form I realization requires M+N+1 multiplications, M+N additions and M+N+1 memory locations.

14). How many number of additions, multiplications and memory locations are required to realize a system H(z) having M zeros and N poles in direct-form II realization ?

Ans:  The direct-form II realization requires M+N+1 multiplications, M+N additions and the maximum of (M,N) memory locations.

15). What is the main advantages of direct-form II realization when compared to direct-form II realization?

Ans: In direct-form II realization, the number of locations required is less than that of direct-form I realization.

16). What is transposition theorem and transposed structure?

Ans: The transpose of a structure is defined by the following operations.

(i). Reverse the directions of all branches in the signal flow graph.

(ii). Interchange the input and outputs.

(iii). Reverse the roles of all nodes in the flow graph.

(iv). Summing points become branching points.

According to transposition theorem if we reverse the directions of all branch transmittance and interchange the input and output in the flow graph, the system function remains unchanged.

17). What is main disadvantage of direct-form realization?

Ans: The direct-form realization is extremely sensitive to parameter quantization. When the order of the system N is large, a small change in a filter coefficient due to parameter quantization, results in a large change in the location of the poles and zeros of the system.

18). What is the advantage of cascade realization?

Ans: Quantization errors can be minimized if we realize an LTI system in cascade form.

19). What is the general form of parallel form of IIR filter?

Ans:  A parallel form realization of an IIR system can be obtained by performing a partial fraction expansion of H(z).

                                 H(z) = C+ 

20). Define signal flow graph.

Ans: A signal flow graph is a graphical representation of the relationship between the variable of a set of linear difference equation.