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

Therefore,

$$NC_k = X(frac{2pi}{N}k) = X(e^{jomega}) = displaystylesumlimits_{n = -infty}^infty x(n)e^{frac{-j2pi nk}{N}} = displaystylesumlimits_{n = -infty}^infty x(n)e^{-jomega n}$$

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}times frac{2pi}{N}$

ω becomes continuous and $frac{2pi}{N}rightarrow 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

Symbolically,

$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})times X_2(e^{jomega})$

• Multiplication − $x_1(n)times x_2(n)Leftrightarrow X_1(e^{jomega})*X_2(e^{jomega})$

• Co-relation − $y_{x_1times x_2}(l)Leftrightarrow X_1(e^{jomega})times 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$

Earlier, we studied sampling 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) = displaystylesumlimits_{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)

$therefore 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 multiplication and N(N-1) complex addition.

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

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

$begin{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 linear transformation

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

IDFT in Matrix form is given by

$$x_N = frac{1}{N}W_N^*X_N$$

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

Therefore, $W_N$ is a linear 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,

$$x_p^prime (n) = x_p(n-k) = sum_{l = -infty}^infty x(n-k-Nl)$$

The new finite sequence can be represented as

$$x_p^prime (n) = begin{cases}x_p^prime(n), & 0leq nleq N-1\0 & Otherwiseend{cases}$$

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 linear 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)$

• Multiplication of two sequence −

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

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

• Circular convolution − and multiplication 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 $bar Y_{xy}$ such that $bar 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)$;

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