Digital Signal Processing

Introduction

When we hear the word signal we may first think of a phenomenon that occurs continuously over time that carries some information. Most phenomena observed in nature are continuous in time, as for instance, our speech or heart beating, the temperature of the city where we live, the car speed during a given trip, the altitude of the airplane we are traveling in — these are typical continuous-time signals. Engineers are always devising ways to design systems, which are in principle continuous time, for measuring and interfering with these and other phenomena.

One should note that, although continuous-time signals pervade our daily life, there are also several signals which are originally discrete time, as, for example, the stock-market weekly financial indicators, the maximum and minimum daily temperatures in our cities, and the average lap speed of a racing car.

If an electrical or computer engineer has the task of designing systems to interact with natural phenomena, his/her first impulse is to convert some quantities from nature into electric signals through a transducer. Electric signals, which are represented by voltages or currents, have a continuous-time representation. Since digital technology constitutes an extremely powerful tool for information processing, it is natural to think of processing the electric signals generated using it. However, continuous-time signals cannot be processed using computer technology (digital machines), which are especially suited to deal with sequential computation involving numbers. Fortunately, this fact does not prevent the use of digital integrated circuits (which is the technology behind the computer technology revolution we witness today) in signal processing systems designs. This is because many signals taken from nature can be fully represented by their sampled versions, where the sampled signals coincide with the original continuous-time signals at some instants in time. If we know how fast the important information changes, we can always sample and convert continuous-time information into discrete-time information which, in turn can be converted into a sequence of numbers and transferred to a digital machine.

The main advantages of digital systems relative to analog systems are high reliability, suitability for modifying the system's characteristics, and low cost. These advantages motivated the digital implementation of many signal processing systems which used to be implemented with analog circuit technology. In addition, a number of new applications became viable once the very large scale integration (VLSI) technology was available. Usually in the VLSI implementation of a digital signal processing system the concern is to reduce power consumption and/or area, or to increase the circuit's speed in order to meet the demands of high-throughput applications.

Currently, a single digital integrated circuit may contain millions of logic gates operating at very high speeds, allowing very fast digital processors to be built at a reasonable cost. This technological development opened avenues to the introduction of powerful general-purpose computers which can be used to design and implement digital signal processing systems. In addition, it allowed the design of microprocessors with special features for signal processing, namely the digital signal processors (DSPs). As a consequence, there are several tools available to implement very complex digital signal processing systems. In practice, a digital signal processing system is implemented either by software on a general-purpose digital computer or DSP, or by using application-specific hardware, usually in the form of an integrated circuit.

For the reasons explained above, the field of digital signal processing has developed so fast in the last decades that it has been incorporated into the graduate and undergraduate programs of virtually all universities. This is confirmed by the number of good textbooks available in this area (Oppenheim & Schafer, 1975; Rabiner & Gold, 1975; Peled & Liu, 1985; Roberts & Mullis, 1987; Oppenheim & Schafer, 1989; Ifeachor & Jervis, 1993; Antoniou, 1993; Jackson, 1996; Proakis & Manolakis, 1996; Mitra, 1998, to mention just a few). The present book is aimed at equipping readers with tools that will enable them to design and analyze most digital signal processing systems. The building blocks for digital signal processing systems considered here are used to process signals which are discrete in time and in amplitude. The main tools emphasized in this text are:

Discrete-time signal representations.
Discrete transforms and their fast algorithms.
Design and implementation of digital filters.
Multirate systems, filter banks, and wavelets.
Implementation of digital signal processing systems.

Transforms and filters are the main parts of linear signal processing systems. Although the techniques we deal with are directly applicable to processing deterministic signals, many statistical signal processing methods employ similar building blocks in some way.

Digital signal processing is extremely useful in many areas. In the following, we enumerate a few of the disciplines where the topics covered by this book have found application.

(a)	Image processing: An image is essentially a space-domain signal, that is, it represents a variation of light intensity and color in space. Therefore, in order to process an image using an analog system, it has to be converted into a time-domain signal, using some form of scanning process. However, to process an image digitally, there is no need to perform this conversion, for it can be processed directly in the spatial domain, as a matrix of numbers. This lends the digital image processing techniques enormous power. In fact, in image processing, two-dimensional signal representation, filtering, and transforms play a central role (Jain, 1989).
(b)	Multimedia systems: Such systems deal with different kinds of information sources such as image, video, audio, and data. In such systems, the information is essentially represented in digital form. Therefore, it is crucial to remove redundancy from the information, allowing compression, and thus efficient transmission and storage (Jayant & Noll, 1984; Gersho & Gray, 1992; Bhaskaran & Konstantinides, 1997). The Internet is a good application example where information files are transferred in a compressed manner. Most of the compression standards for image use transforms and quantizers. The transforms, filter banks, and wavelets are very popular in compression applications because they are able to exploit the high correlation of signal sources such as audio, still images and video (Malvar, 1992; Fliege, 1994; Vetterli & Kovačević, 1995; Strang & Nguyen, 1996; Mallat, 1998).
(c)	Communication systems: In communication systems, the compression and coding of the information sources are also crucial, since by reducing the amount of data to be transmitted services can be provided at higher speed or to more users. In addition, channel coding, which consists of inserting redundancy in the signal to compensate for possible channel distortions, may also use special types of digital filtering (Stüber, 1996). Communication systems usually include fixed filters, as well as some self-designing filters for equalization and channel modeling which fall in the class of adaptive filtering systems (Diniz, 1997). Although these filters employ a statistical signal processing framework (Manolakis et al., 2000) to determine how their parameters should change, they also use some of the filter structures and in some cases the transforms introduced in this book. Many filtering concepts take part on modern multiuser communication systems employing coded division multiple access (CDMA) (Verdu, 1998). Wavelets, transforms, and filter banks also play a crucial role in the conception of orthogonal frequency division multiplexing (OFDM) (Akansu & Medley, 1999), which is used in digital audio and TV broadcasting.
(d)	Audio signal processing: In statistical signal processing the filters are designed based on observed signals, which might imply that we are estimating the parameters of the model governing these signals (Kailath et al., 2000). Such estimation techniques can be employed in digital audio restoration (Godsill & Rayner, 1998), where the resulting models can be used to restore lost information. However, these estimation models can be simplified and made more effective if we use some kind of sub-band processing with filter banks and transforms (Kahrs & Brandenburg, 1998). In the same field digital filters were found to be suitable for reverberation algorithms and as models for musical instruments (Kahrs & Brandenburg, 1998).

In addition to the above applications, digital signal processing is at the heart of modern developments in speech analysis and synthesis, mobile radio, sonar, radar, biomedical engineering, seismology, home appliances, and instrumentation, among others. These developments occurred in parallel with the advances in the technology of transmission, processing, recording, reproduction, and general treatment of signals through analog and digital electronics, as well as other means such as acoustics, mechanics, and optics.

We expect that with the digital signal processing tools described in this book, the reader will be able to proceed further, not only exploring and understanding some of the applications described above, but developing new ones as well.

1 Discrete-time systems

1.1 Introduction

Digital signal processing is the discipline that studies the rules governing the behavior of discrete signals, as well as the systems used to process them. It also deals with the issues involved in processing continuous signals using digital techniques. Digital signal processing pervades modern life. It has applications in compact disc players, computer tomography, geological processing, mobile phones, electronic toys, and many others.

In analog signal processing, we take a continuous signal, representing a continuously varying physical quantity, and pass it through a system that modifies this signal for a certain purpose. This modification is, in general, continuously variable by nature, that is, it can be described by differential equations.

Alternatively, in digital signal processing, we process sequences of numbers using some sort of digital hardware. We usually call these sequences of numbers digital or discrete-time signals.¹ The power of digital signal processing comes from the fact that, once a sequence of numbers is available to appropriate digital hardware we can carry out any form of numerical processing on them. For example, suppose we need to perform the following operation on a continuous-time signal:

This would be clearly very difficult to implement using analog hardware. However, if we sample the analog signal x(t) and convert it into a sequence of numbers x(n), it can be input to a digital computer, which can perform the above operation easily and reliably, generating a sequence of numbers y(n). If the continuous-time signal y(t) can be recovered from y(n), then the desired processing has been successfully performed.

This simple example highlights two important points. One is how powerful is digital signal processing. The other is that, if we want to process an analog signal using this sort of resource, we must have a way of converting a continuous-time signal into a discrete-time one, such that the continuous-time signal can be recovered from the discrete-time signal. However, it is important to note that very often discrete-time signals do not come from continuous-time signals, that is, they are originally discrete-time, and the results of their processing are only needed in digital form.

In this chapter, we study the basic concepts of the theory of discrete-time signals and systems. We emphasize the treatment of discrete-time systems as separate entities from continuous-time systems. We first define discrete-time signals and, based on this, we define discrete-time systems, highlighting the properties of an important subset of these systems, namely, linearity and time invariance, as well as their description by discrete-time convolutions. We then study their time-domain response by characterizing them using difference equations. We close the chapter with Nyquist's sampling theorem, which tells us how to generate, from a continuous-time signal, a discrete-time signal from which the continuous-time signal can be completely recovered. Nyquist's sampling theorem forms the basis of the digital processing of continuous-time signals.

1.2 Discrete-time signals

A discrete-time signal is one that can be represented by a sequence of numbers. For example, the sequence

{x(n), n Î Z}

(1.2)

where Z is the set of integer numbers, can represent a discrete-time signal where each number x(n) corresponds to the amplitude of the signal at an instant nT. Since n is an integer, T represents the interval between two consecutive points at which the signal is defined. It is important to note that T is not necessarily a time unit. For example, if x(n) represents the temperature at sensors placed uniformly along a metal rod, then T is a length unit.

In this text, we usually represent a discrete-time signal using the notation in equation (1.2), where x(n) is referred to as the nth sample of the signal. An alternative notation, used in many texts, is to represent the signal as

{x(nT), n Î Z}

(1.3)

where the time interval between samples is explicitly shown, that is, x(nT) is the sample at time nT. Note that, using the notation in equation (1.2), a discrete-time signal whose adjacent samples are 0.03 seconds apart would be represented as

. . . x(0), x(1), x(2), x(3), x(4), . . .

(1.4)

whereas, using equation (1.3), it would be represented as

. . . x(0), x(0.03), x(0.06), x(0.09), x(0.12), . . .

(1.5)

Figure 1.1 General representation of a discrete-time signal.

The graphical representation of a general discrete-time signal is shown in Figure 1.1. In what follows, we describe some of the most important discrete-time signals.

Unit impulse: See Figure 1.2a

Delayed unit impulse: See Figure 1.2b

Unit step: See Figure 1.2c

Cosine function:

x(n) = cos(wn)

(1.9)

The angular frequency of this sinusoid is w rad/sample and its frequency is cycles/sample. For example, in Figure 1.2d, the cosine function has angular frequency rad/sample. This means that it completes one cycle, that equals 2p radians, in 16 samples. If the sample separation represents time, w can be given in rad/(time unit).

Real exponential function: See Figure 1.2e

x(n) = e^an

(1.10)

Figure 1.2 Basic discrete-time functions. (a) Unit impulse; (b) delayed unit impulse; (c) unit step; (d) cosine function with w = rad/sample; (e) real exponential function with a = 0.2; (f) unit ramp.

Unit ramp: See Figure 1.2f

By examining Figure 1.2b–f, we notice that any discrete-time signal is equivalent to a sum of shifted impulses multiplied by a constant, that is, the impulse shifted by k samples is multiplied by x(k). This can also be deduced from the definition of a shifted impulse in equation (1.7). For example, the unit step u(n) in equation (1.8) can also be expressed as

Likewise, any discrete-time signal x(n) can be expressed as

An important class of discrete-time signals or sequences is that of periodic sequences. A periodic sequence x(n) is periodic if and only if there is an integer N ¹ 0

Figure 1.3 Representation of a discrete-time system.

such that x(n) = x(n + N) for all n. In such a case, N is called the period of the sequence. Note that, using this definition and referring to equation (1.9), the period of the cosine function is an integer N such that

cos(wx(n) = cos(wx(n +N)) "n Î Z

(1.14)

This happens only if there is k Î Z such that w N = 2p k, or equivalently

Therefore, we notice that not all discrete cosine sequences are periodic. For example, if w = the cosine sequence is not periodic. An example of a periodic cosine sequence with period equal to 16 samples is given in Figure 1.2d.

1.3 Discrete-time systems

A discrete-time system maps an input sequence x(n) to an output sequence y (n), such that

where the operator represents a discrete-time system, as shown in Figure 1.3. Depending on the properties of , the discrete-time system can be classified in several ways, the most basic ones being either linear or nonlinear, time invariant or time variant, causal or noncausal. These classifications will be discussed in what follows.