1.1 Discrete-time signals  (Page 3/10)

Extensions of x(n)

Although the finite length signal $x\left(n\right)$ is defined only over the interval $\{0\le n\le (N-1\left)\right\}$ , the IDFT of $C\left(k\right)$ can be evaluated outside this interval to give well defined values. Indeed,this process gives the periodic property 4. There are two ways of formulating this phenomenon. One is to periodically extend $x\left(n\right)$ to $-\infty$ and $+\infty$ and work with this new signal. A second more general way is evaluate all indices $n$ and $k$ modulo $N$ . Rather than considering the periodic extension of $x\left(n\right)$ on the line of integers, the finite length line is formed into a circle or aline around a cylinder so that after counting to $N-1$ , the next number is zero, not a periodic replication of it. The periodicextension is easier to visualize initially and is more commonly used for the definition of the DFT, but the evaluation of the indices byresidue reduction modulo $N$ is a more general definition and can be better utilized to develop efficient algorithms for calculating theDFT [link] .

Since the indices are evaluated only over the basic interval, any values could be assigned $x\left(n\right)$ outside that interval. The periodic extension is the choice most consistent with the other properties ofthe transform, however, it could be assigned to zero [link] . An interesting possibility is to artificially create a length $2N$ sequence by appending $x(-n)$ to the end of $x\left(n\right)$ . This would remove the discontinuities of periodic extensions of this new length $2N$ signal and perhaps give a more accurate measure of the frequency content of the signal with no artifacts caused by “endeffects". Indeed, this modification of the DFT gives what is called the discrete cosine transform (DCT) [link] . We will assume the implicit periodic extensions to $x\left(n\right)$ with no special notation unless this characteristic is important, then we will use thenotation $\tilde{x}\left(n\right)$ .

Convolution

Convolution is an important operation in signal processing that is in some ways more complicated in discrete-time signal processingthan in continuous-time signal processing and in other ways easier. The basic input-output relation for a discrete-time system is givenby so-called linear or non-cyclic convolution defined and denoted by

where $x\left(n\right)$ is the perhaps infinitely long input discrete-time signal, $h\left(n\right)$ is the perhaps infinitely long impulse response of the system, and $y\left(n\right)$ is the output. The DFT is, however, intimately related to cyclic convolution, not non-cyclic convolution. Cyclic convolution is definedand denoted by

where either all of the indices or independent integer variables are evaluated modulo $N$ or all of the signals are periodically extended outside their length $N$ domains.

This cyclic (sometimes called circular) convolution can be expressed as a matrix operation by converting the signal $h\left(n\right)$ into a matrix operator as

The cyclic convolution can then be written in matrix notation as

where $\mathbf{X}$ and $\mathbf{Y}$ are column matrices or vectors of the input and output values respectively.

Because non-cyclic convolution is often what you want to do and cyclic convolution is what is related to the powerful DFT, we want to develop away of doing non-cyclic convolution by doing cyclic convolution.