DSP - DFT Time Frequency Transform

We know that when $omega = 2pi K/N$ and $N ightarrow infty,omega$ becomes a continuous variable and pmits summation become $-infty$ to $+infty$.

Therefore,

Discrete Time Fourier Transform (DTFT)

We know that, $X(e^{jomega}) = sum_{n = -infty}^infty x(n)e^{-jomega n}$

Where, $X(e^{jomega})$ is continuous and periodic in ω and with period 2π.…eq(1)

Now,

$x_p(n) = sum_{k = 0}^{N-1}NC_ke^{j2 pi nk/N}$ … From Fourier series

$x_p(n) = frac{1}{2pi}sum_{k=0}^{N-1}NC_ke^{j2pi nk/N} imes frac{2pi}{N}$

ω becomes continuous and $frac{2pi}{N} ightarrow domega$, because of the reasons cited above.

$x(n) = frac{1}{2pi}int_{n = 0}^{2pi}X(e^{jomega})e^{jomega n}domega$…eq(2)

Inverse Discrete Time Fourier Transform

Symbopcally,

$x(n)Longleftrightarrow x(e^{jomega})$(The Fourier Transform pair)

Necessary and sufficient condition for existence of Discrete Time Fourier Transform for a non-periodic sequence x(n) is absolute summable.

i.e.$sum_{n = -infty}^infty|x(n)|<infty$

Properties of DTFT

Linearity : $a_1x_1(n)+a_2x_2(n)Leftrightarrow a_1X_1(e^{jomega})+a_2X_2(e^{jomega})$

Time shifting − $x(n-k)Leftrightarrow e^{-jomega k}.X(e^{jomega})$

Time Reversal − $x(-n)Leftrightarrow X(e^{-jomega})$

Frequency shifting − $e^{jomega _0n}x(n)Leftrightarrow X(e^{j(omega -omega _0)})$

Differentiation frequency domain − $nx(n) = jfrac{d}{domega}X(e^{jomega})$

Convolution − $x_1(n)*x_2(n)Leftrightarrow X_1(e^{jomega}) imes X_2(e^{jomega})$

Multippcation − $x_1(n) imes x_2(n)Leftrightarrow X_1(e^{jomega})*X_2(e^{jomega})$

Co-relation − $y_{x_1 imes x_2}(l)Leftrightarrow X_1(e^{jomega}) imes X_2(e^{jomega})$

Modulation theorem − $x(n)cos omega _0n = frac{1}{2}[X_1(e^{j(omega +omega _0})*X_2(e^{jw})$

Symmetry −$x^*(n)Leftrightarrow X^*(e^{-jomega})$ ;

$x^*(-n)Leftrightarrow X^*(e^{jomega})$ ;

$Real[x(n)]Leftrightarrow X_{even}(e^{jomega})$ ;

$Imag[x(n)]Leftrightarrow X_{odd}(e^{jomega})$ ;

$x_{even}(n)Leftrightarrow Real[x(e^{jomega})]$ ;

$x_{odd}(n)Leftrightarrow Imag[x(e^{jomega})]$ ;

Parseval’s theorem − $sum_{-infty}^infty|x_1(n)|^2 = frac{1}{2pi}int_{-pi}^{pi}|X_1(e^{jomega})|^2domega$

Earper, we studied samppng in frequency domain. With that basic knowledge, we sample $X(e^{jomega})$ in frequency domain, so that a convenient digital analysis can be done from that sampled data. Hence, DFT is sampled in both time and frequency domain. With the assumption $x(n) = x_p(n)$

Hence, DFT is given by −

$X(k) = DFT[x(n)] = X(frac{2pi}{N}k) = displaystylesumpmits_{n = 0}^{N-1}x(n)e^{-frac{j2pi nk}{N}}$,k=0,1,….,N−1…eq(3)

And IDFT is given by −

$X(n) = IDFT[X(k)] = frac{1}{N}sum_{k = 0}^{N-1}X(k)e^{frac{j2pi nk}{N}}$,n=0,1,….,N−1…eq(4)

$ herefore x(n)Leftrightarrow X(k)$

Twiddle Factor

It is denoted as $W_N$ and defined as $W_N = e^{-j2pi /N}$ . Its magnitude is always maintained at unity. Phase of $W_N = -2pi /N$ . It is a vector on unit circle and is used for computational convenience. Mathematically, it can be shown as −

$W_N^r = W_N^{rpm N} = W_N^{rpm 2N} = ...$

It is function of r and period N.

Consider N = 8, r = 0,1,2,3,….14,15,16,….

$Longleftrightarrow W_8^0 = W_8^8 = W_8^{16} = ... = ... = W_8^{32} = ... =1= 1angle 0$

$W_8^1 = W_8^9 = W_8^{17} = ... = ... = W_8^{33} = ... =frac{1}{sqrt 2}= jfrac{1}{sqrt 2} = 1angle-frac{pi}{4}$

Linear Transformation

Let us understand Linear Transformation −

We know that,

$DFT(k) = DFT[x(n)] = X(frac{2pi}{N}k) = sum_{n = 0}^{N-1}x(n).W_n^{-nk};quad k = 0,1,….,N−1$

$x(n) = IDFT[X(k)] = frac{1}{N}sum_{k = 0}^{N-1}X(k).W_N^{-nk};quad n = 0,1,….,N−1$

Note − Computation of DFT can be performed with N² complex multippcation and N(N-1) complex addition.

$x_N = egin{bmatrix}x(0)\x(1)\.\.\x(N-1) end{bmatrix}quad Nquad pointquad vectorquad ofquad signalquad x_N$

$X_N = egin{bmatrix}X(0)\X(1)\.\.\X(N-1) end{bmatrix}quad Nquad pointquad vectorquad ofquad signalquad X_N$

$egin{bmatrix}1 & 1 & 1 & ... & ... & 1\1 & W_N & W_N^2 & ... & ... & W_N^{N-1}\. & W_N^2 & W_N^4 & ... & ... & W_N^{2(N-1)}\.\1 & W_N^{N-1} & W_N^{2(N-1)} & ... & ... & W_N^{(N-1)(N-1)} end{bmatrix}$

N - point DFT in matrix term is given by - $X_N = W_Nx_N$

$W_Nlongmapsto$ Matrix of pnear transformation

$Now,quad x_N = W_N^{-1}X_N$

IDFT in Matrix form is given by

Comparing both the expressions of $x_N,quad W_N^{-1} = frac{1}{N}W_N^*$ and $W_N imes W_N^* = N[I]_{N imes N}$

Therefore, $W_N$ is a pnear transformation matrix, an orthogonal (unitary) matrix.

From periodic property of $W_N$ and from its symmetric property, it can be concluded that, $W_N^{k+N/2} = -W_N^k$

Circular Symmetry

N-point DFT of a finite duration x(n) of length N≤L, is equivalent to the N-point DFT of periodic extension of x(n), i.e. $x_p(n)$ of period N. and $x_p(n) = sum_{l = -infty}^infty x(n-Nl)$ . Now, if we shift the sequence, which is a periodic sequence by k units to the right, another periodic sequence is obtained. This is known as Circular shift and this is given by,

The new finite sequence can be represented as

Example − Let x(n)= {1,2,4,3}, N = 4,

$x_p^prime (n) = x(n-k,moduloquad N)equiv x((n-k))_Nquad;ex-ifquad k=2i.equad 2quad unitquad rightquad shiftquad andquad N = 4,$

Assumed clockwise direction as positive direction.

We got, $xprime(n) = x((n-2))_4$

$xprime(0) = x((-2))_4 = x(2) = 4$

$xprime(1) = x((-1))_4 = x(3) = 3$

$xprime(2) = x((-2))_4 = x(0) = 1$

$xprime(3) = x((1))_4 = x(1) = 2$

Conclusion − Circular shift of N-point sequence is equivalent to a pnear shift of its periodic extension and vice versa.

Circularly even sequence − $x(N-n) = x(n),quad 1leq nleq N-1$

$i.e.x_p(n) = x_p(-n) = x_p(N-n)$

Conjugate even −$x_p(n) = x_p^*(N-n)$

Circularly odd sequence − $x(N-n) = -x(n),quad 1leq nleq N-1$

$i.e.x_p(n) = -x_p(-n) = -x_p(N-n)$

Conjugate odd − $x_p(n) = -x_p^*(N-n)$

Now, $x_p(n) = x_{pe}+x_{po}(n)$, where,

$x_{pe}(n) = frac{1}{2}[x_p(n)+x_p^*(N-n)]$

$x_{po}(n) = frac{1}{2}[x_p(n)-x_p^*(N-n)]$

For any real signal x(n),$X(k) = X^*(N-k)$

$X_R(k) = X_R(N-k)$

$X_l(k) = -X_l(N-k)$

$angle X(k) = -angle X(N-K)$

Time reversal − reversing sample about the 0^th sample. This is given as;

$x((-n))_N = x(N-n),quad 0leq nleq N-1$

Time reversal is plotting samples of sequence, in clockwise direction i.e. assumed negative direction.

Some Other Important Properties

Other important IDFT properties $x(n)longleftrightarrow X(k)$

Time reversal − $x((-n))_N = x(N-n)longleftrightarrow X((-k))_N = X(N-k)$

Circular time shift − $x((n-l))_N longleftrightarrow X(k)e^{j2pi lk/N}$

Circular frequency shift − $x(n)e^{j2pi ln/N} longleftrightarrow X((k-l))_N$

Complex conjugate properties −

$x^*(n)longleftrightarrow X^*((-k))_N = X^*(N-k)quad and$

$x^*((-n))_N = x^*(N-n)longleftrightarrow X^*(-k)$

Multippcation of two sequence −

$x_1(n)longleftrightarrow X_1(k)quad andquad x_2(n)longleftrightarrow X_2(k)$

$ herefore x_1(n)x_2(n)longleftrightarrow X_1(k)quadⓃ X_2(k)$

Circular convolution − and multippcation of two DFT

$x_1(k)quad Ⓝ x_2(k) =sum_{k = 0}^{N-1}x_1(n).x_2((m-n))_n,quad m = 0,1,2,... .,N-1 $

$x_1(k)quad Ⓝ x_2(k)longleftrightarrow X_1(k).X_2(k)$

Circular correlation − If $x(n)longleftrightarrow X(k)$ and $y(n)longleftrightarrow Y(k)$ , then there exists a cross correlation sequence denoted as $ar Y_{xy}$ such that $ar Y_{xy}(l) = sum_{n = 0}^{N-1}x(n)y^*((n-l))_N = X(k).Y^*(k)$

Parseval’s Theorem − If $x(n)longleftrightarrow X(k)$ and $y(n)longleftrightarrow Y(k)$;

$displaystylesumpmits_{n = 0}^{N-1}x(n)y^*(n) = frac{1}{N}displaystylesumpmits_{n =0}^{N-1}X(k).Y^*(k)$