0
12kviews
Justify DFT as a linear transformation.
1 Answer
0
951views

The expression for DFT and IDFT can be given as,

$X(k)=∑\limits_{n=0}^{N-1}x(n).W_N^{kn }\\ x(n)=\dfrac 1N ∑\limits_{n=0}^{N-1}X(k).W_N^{-kn}$

where by definition,

$W_N=e^{-j 2π⁄N}$

Which is an N th root of unity.

the computation of each point of DFT can be accomplished by N complex multiplications and N-1 complex addition. Hence the N-point DFT values can be computed in a total of $N^2$ complex multiplication and N*(N-1) complex addition.

Suppose $X_N$ is the N point vector of the signal sequence x(n), n=0,1,…., N-1, then N- point vector of $X_N $ of frequency samples, and an $N×N$ matrix $W_N$ can be given as,

Matrix 123

With these definitions , the N-point DFT can be expressed as,

$X_N = W_{N×N} $

where, $W_ N$ is the matrix of the linear transformation and $W_N$ is symmetric matrix. If we assume that inverse of the $W_ N$ is exists then above eqn can be inverted by premultiplying both sides by $W_ N^{-1}$ Therefore we get

$X_n=W_ N^{-1}\times X_ N$ but according to definition of IDFT , this is the expression of IDFT Aslo, Above given IDFT equation can be expressed as

$X_n=\dfrac 1N W_ N^*.X_N$

Where $W_N^*$ denotes the complex conjugate of the , matrix $W_N$ . Comparing equations We can conclude that

$W_N^{-1}=\dfrac 1N W_N^*\\ W_N.W_N^*=N.I_N$

where .$I_N$ is the $N×N$ identity matrix. Hence DFT is linear transformation.

Please log in to add an answer.