1.1 Discrete-time signals  (Page 4/10)

The convolution of a length $N$ sequence with a length $M$ sequence yields a length $N+M-1$ output sequence. The calculation of non-cyclic convolution by using cyclic convolution requires modifying the signals byappending zeros to them. This will be developed later.

Properties of the dft

The properties of the DFT are extremely important in applying it to signal analysis and to interpreting it. The main properties are given hereusing the notation that the DFT of a length- $N$ complex sequence $x\left(n\right)$ is $\mathcal{F}\left\{x\right(n\left)\right\}=C\left(k\right)$ .

1. Linear Operator: $\mathcal{F}\left\{x\right(n)+y(n\left)\right\}=\mathcal{F}\left\{x\right(n\left)\right\}+\mathcal{F}\left\{y\right(n\left)\right\}$
2. Unitary Operator: ${\mathbf{F}}^{-\mathbf{1}}=\frac{1}{N}{\mathbf{F}}^{\mathbf{T}}$
3. Periodic Spectrum: $C\left(k\right)=C(k+N)$
4. Periodic Extensions of $x\left(n\right)$ : $x\left(n\right)=x(n+N)$
5. Properties of Even and Odd Parts: $x\left(n\right)=u\left(n\right)+jv\left(n\right)$ and $C\left(k\right)=A\left(k\right)+jB\left(k\right)$

   $u$	$v$	$A$	$B$	$\left|C\right|$	$\theta$
   even	0	even	0	even	0
   odd	0	0	odd	even	$\pi /2$
   0	even	0	even	even	$\pi /2$
   0	odd	odd	0	even	0

6. Cyclic Convolution: $\mathcal{F}\left\{h\right(n)\circ x(n\left)\right\}=\mathcal{F}\left\{h\right(n\left)\right\}\mathcal{F}\left\{x\right(n\left)\right\}$
7. Multiplication: $\mathcal{F}\left\{h\right(n\left)x\right(n\left)\right\}=\mathcal{F}\left\{h\right(n\left)\right\}\circ \mathcal{F}\left\{x\right(n\left)\right\}$
8. Parseval: ${\sum }_{n=0}^{N-1}{\left|x\left(n\right)\right|}^2=\frac{1}{N}{\sum }_{k=0}^{N-1}{\left|C\left(k\right)\right|}^2$
9. Shift: $\mathcal{F}\left\{x(n-M)\right\}=C\left(k\right)e^{-j2\pi Mk/N}$
10. Modulate: $\mathcal{F}\left\{x\left(n\right)e^{j2\pi Kn/N}\right\}=C(k-K)$
11. Down Sample or Decimate: $\mathcal{F}\left\{x\left(Kn\right)\right\}=\frac{1}{K}{\sum }_{m=0}^{K-1}C(k+Lm)$ where $N=LK$
12. Up Sample or Stretch: If $x_s\left(2n\right)=x\left(n\right)$ for integer $n$ and zero otherwise,then $\mathcal{F}\left\{x_s\left(n\right)\right\}=C\left(k\right)$ , for $k=0,1,2,...,2N-1$
13. N Roots of Unity: ${\left(W_N^k\right)}^N=1$ for $k=0,1,2,...,N-1$
14. Orthogonality:
    $$\sum _{k=0}^{N-1}{e}^{-j2\pi mk/N}{e}^{j2\pi nk/N}=\left\{\begin{array}{cc}N\hfill & \text{if}n=m\hfill \\ 0\hfill & \text{if}n\ne m.\hfill \end{array}\right)$$
15. Diagonalization of Convolution: If cyclic convolution is expressed as a matrix operation by $\mathbf{y}=\mathbf{Hx}$ with $\mathbf{H}$ given by [link] , the DFT operator diagonalizes the convolution operator $\mathbf{H}$ , or ${\mathbf{F}}^{\mathbf{T}}\mathbf{HF}={\mathbf{H}}_{\mathbf{d}}$ where ${\mathbf{H}}_{\mathbf{d}}$ is a diagonal matrix with the $N$ values of the DFT of $h\left(n\right)$ on the diagonal. This is a matrix statement of Property 6 . Note the columns of $\mathbf{F}$ are the $N$ eigenvectors of $\mathbf{H}$ , independent of the values of $h\left(n\right)$ .

One can show that any “kernel" of a transform that would support cyclic, length-N convolution must be the N roots of unity. This says the DFT isthe only transform over the complex number field that will support convolution. However, if one considers various finite fields or rings, aninteresting transform, called the Number Theoretic Transform, can be defined and used because the roots of unity are simply two raised to apowers which is a simple word shift for certain binary number representations [link] , [link] .

Examples of the dft

It is very important to develop insight and intuition into the DFT or spectral characteristics of various standard signals. A few DFT's ofstandard signals together with the above properties will give a fairlylarge set of results. They will also aid in quickly obtaining the DFT of new signals. The discrete-time impulse $\delta \left(n\right)$ is defined by

The discrete-time pulse ${\sqcap }_M\left(n\right)$ is defined by

Several examples are:

• $DFT\left\{\delta \right(n\left)\right\}=1$ , The DFT of an impulse is a constant.
• $DFT\left\{1\right\}=N\delta \left(k\right)$ , The DFT of a constant is an impulse.
• $DFT\left\{e^{j2\pi Kn/N}\right\}=N\delta (k-K)$
• $DFT\{cos(2\pi Mn/N)=\frac{N}{2}[\delta (k-M)+\delta (k+M)]$
• $DFT\left\{{\sqcap }_M\left(n\right)\right\}=\frac{sin\left(\frac{\pi }{N}Mk\right)}{sin\left(\frac{\pi }{N}k\right)}$

These examples together with the properties can generate a still larger set of interesting and enlightening examples. Matlab can be used toexperiment with these results and to gain insight and intuition.

The discrete-time fourier transform

In addition to finite length signals, there are many practical problems where we must be able to analyze and process essentially infinitely longsequences. For continuous-time signals, the Fourier series is used for finite length signals and the Fourier transform or integral is used forinfinitely long signals. For discrete-time signals, we have the DFT for finite length signals and we now present the discrete-time Fouriertransform (DTFT) for infinitely long signals or signals that are longer than we want to specify [link] . The DTFT can be developed as an extension of the DFT as $N$ goes to infinity or the DTFT can be independently defined and then the DFT shown to be a special case of it.We will do the latter.