DSP - DFT Time Frequency Transform

Advertisements

Previous Page
Next Page  

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

Therefore,

$$NC_k = X(\frac{2\pi}{N}k) = X(e^{j\omega}) = \displaystyle\sum\limits_{n = -\infty}^\infty x(n)e^{\frac{-j2\pi nk}{N}} = \displaystyle\sum\limits_{n = -\infty}^\infty x(n)e^{-j\omega n}$$

Discrete Time Fourier Transform (DTFT)

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

Where, $X(e^{j\omega})$ 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}{2\pi}\sum_{k=0}^{N-1}NC_ke^{j2\pi nk/N}\times \frac{2\pi}{N}$

ω becomes continuous and $\frac{2\pi}{N}\rightarrow d\omega$, because of the reasons cited above.

$x(n) = \frac{1}{2\pi}\int_{n = 0}^{2\pi}X(e^{j\omega})e^{j\omega n}d\omega$…eq(2)

Inverse Discrete Time Fourier Transform

Symbolically,

$x(n)\Longleftrightarrow x(e^{j\omega})$(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^{j\omega})+a_2X_2(e^{j\omega})$

  • Time shifting − $x(n-k)\Leftrightarrow e^{-j\omega k}.X(e^{j\omega})$

  • Time Reversal − $x(-n)\Leftrightarrow X(e^{-j\omega})$

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

  • Differentiation frequency domain − $nx(n) = j\frac{d}{d\omega}X(e^{j\omega})$

  • Convolution − $x_1(n)*x_2(n)\Leftrightarrow X_1(e^{j\omega})\times X_2(e^{j\omega})$

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

  • Co-relation − $y_{x_1\times x_2}(l)\Leftrightarrow X_1(e^{j\omega})\times X_2(e^{j\omega})$

  • 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^{-j\omega})$ ;

    $x^*(-n)\Leftrightarrow X^*(e^{j\omega})$ ;

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

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

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

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

  • Parseval’s theorem − $\sum_{-\infty}^\infty|x_1(n)|^2 = \frac{1}{2\pi}\int_{-\pi}^{\pi}|X_1(e^{j\omega})|^2d\omega$

Earlier, we studied sampling in frequency domain. With that basic knowledge, we sample $X(e^{j\omega})$ 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{2\pi}{N}k) = \displaystyle\sum\limits_{n = 0}^{N-1}x(n)e^{-\frac{j2\pi 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{j2\pi 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^{-j2\pi /N}$ . Its magnitude is always maintained at unity. Phase of $W_N = -2\pi /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^{r\pm N} = W_N^{r\pm 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= 1\angle 0$

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

Linear Transformation

Let us understand Linear Transformation −

We know that,

$DFT(k) = DFT[x(n)] = X(\frac{2\pi}{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 N2 complex multiplication and N(N-1) complex addition.

  • $x_N = \begin{bmatrix}x(0)\\x(1)\\.\\.\\x(N-1) \end{bmatrix}\quad N\quad point\quad vector\quad of\quad signal\quad x_N$

  • $X_N = \begin{bmatrix}X(0)\\X(1)\\.\\.\\X(N-1) \end{bmatrix}\quad N\quad point\quad vector\quad of\quad signal\quad 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_N\longmapsto$ 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_N\times W_N^* = N[I]_{N\times 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), & 0\leq n\leq N-1\\0 & Otherwise\end{cases}$$

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

    $x_p^\prime (n) = x(n-k,modulo\quad N)\equiv x((n-k))_N\quad;ex-if\quad k=2i.e\quad 2\quad unit\quad right\quad shift\quad and\quad N = 4,$

    Assumed clockwise direction as positive direction.

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

    $x\prime(0) = x((-2))_4 = x(2) = 4$

    $x\prime(1) = x((-1))_4 = x(3) = 3$

    $x\prime(2) = x((-2))_4 = x(0) = 1$

    $x\prime(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 1\leq n\leq 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 1\leq n\leq 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 0th sample. This is given as;

    $x((-n))_N = x(N-n),\quad 0\leq n\leq 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^{j2\pi lk/N}$

    • Circular frequency shift − $x(n)e^{j2\pi 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 and\quad 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)$;

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

    Advertisements