Free Books
   Free Books    Mathematics of the DFT  

Importance of Generalized Complex Sinusoids

As a preview of things to come, note that one signal $ y(\cdot)$4.15 is projected onto another signal $ x(\cdot)$ using an inner product. The inner product $ \left<y,x\right>$ computes the coefficient of projection4.16 of $ y$ onto $ x$. If $ x_k(n) = e^{j\omega_k n T}, n=0,1,2,\ldots,N-1$ (a sampled, unit-amplitude, zero-phase, complex sinusoid), then the inner product computes the Discrete Fourier Transform (DFT), provided the frequencies are chosen to be $ \omega_k = 2\pi k f_s/N$. For the DFT, the inner product is specifically

$\displaystyle \left<y,x_k\right> \isdef \sum_{n=0}^{N-1}y(n)\overline{x_k(n)} ... ...^{N-1}y(n)e^{-j 2\pi n k/N} \isdef \hbox{\sc DFT}_k(y) \isdef Y(\omega_k). $

Another case of importance is the Discrete Time Fourier Transform (DTFT), which is like the DFT except that the transform accepts an infinite number of samples instead of only $ N$. In this case, frequency is continuous, and

$\displaystyle \left<y,x_\omega\right> = \sum_{n=0}^\infty y(n) e^{-j \omega n T} \isdef \hbox{\sc DTFT}_\omega(y). $

The DTFT is what you get in the limit as the number of samples in the DFT approaches infinity. The lower limit of summation remains zero because we are assuming all signals are zero for negative time (such signals are said to be causal). This means we are working with unilateral Fourier transforms. There are also corresponding bilateral transforms for which the lower summation limit is $ -\infty$. The DTFT is discussed further in §B.1. If, more generally, $ x(n) = z^n$ (a sampled complex sinusoid with exponential growth or decay), then the inner product becomes

$\displaystyle \left<y,x\right> = \sum_{n=0}^\infty y(n) z^{-n} $

and this is the definition of the $ z$ transform. It is a generalization of the DTFT: The DTFT equals the $ z$ transform evaluated on the unit circle in the $ z$ plane. In principle, the $ z$ transform can also be recovered from the DTFT by means of ``analytic continuation'' from the unit circle to the entire $ z$ plane (subject to mathematical disclaimers which are unnecessary in practical applications since they are always finite). Why have a $ z$ transform when it seems to contain no more information than the DTFT? It is useful to generalize from the unit circle (where the DFT and DTFT live) to the entire complex plane (the $ z$ transform's domain) for a number of reasons. First, it allows transformation of growing functions of time such as growing exponentials; the only limitation on growth is that it cannot be faster than exponential. Secondly, the $ z$ transform has a deeper algebraic structure over the complex plane as a whole than it does only over the unit circle. For example, the $ z$ transform of any finite signal is simply a polynomial in $ z$. As such, it can be fully characterized (up to a constant scale factor) by its zeros in the $ z$ plane. Similarly, the $ z$ transform of an exponential can be characterized to within a scale factor by a single point in the $ z$ plane (the point which generates the exponential); since the $ z$ transform goes to infinity at that point, it is called a pole of the transform. More generally, the $ z$ transform of any generalized complex sinusoid is simply a pole located at the point which generates the sinusoid. Poles and zeros are used extensively in the analysis of recursive digital filters. On the most general level, every finite-order, linear, time-invariant, discrete-time system is fully specified (up to a scale factor) by its poles and zeros in the $ z$ plane. This topic will be taken up in detail in Book II [68]. In the continuous-time case, we have the Fourier transform which projects $ y$ onto the continuous-time sinusoids defined by $ x(t)=e^{j\omega t}$, and the appropriate inner product is

$\displaystyle \left<y,x\right> = \int_{0}^{\infty} y(t) e^{-j\omega t} dt \isdef Y(\omega). $

Finally, the Laplace transform is the continuous-time counterpart of the $ z$ transform, and it projects signals onto exponentially growing or decaying complex sinusoids:

$\displaystyle \left<y,x\right> = \int_{0}^{\infty} y(t) e^{-s t} dt \isdef Y(s) $

The Fourier transform equals the Laplace transform evaluated along the ``$ j\omega$ axis'' in the $ s$ plane, i.e., along the line $ s=j\omega$, for which $ \sigma=0$. Also, the Laplace transform is obtainable from the Fourier transform via analytic continuation. The usefulness of the Laplace transform relative to the Fourier transform is exactly analogous to that of the $ z$ transform outlined above.
Next Section:
Comparing Analog and Digital Complex Planes
Previous Section:
Phasor and Carrier Components of Sinusoids