Foundations of Digital Signal Processing: theory, algorithms and hardware design
An excellent introductory text, this book covers the basic theoretical, algorithmic and real-time aspects of digital signal processing (DSP). Detailed information is provided on off-line, real-time and DSP programming and the reader is effortlessly guided through advanced topics such as DSP hardware design, FIR and IIR filter design and difference equation manipulation.
Inspec keywords: signal processing
Other keywords: z-space; electrical system; signal sampling; z-transform; infinite impulse response filter; digital signal processing; adaptive filter; digital-to-analog conversion; analog-to-digital conversion; digital filter design; discrete Fourier property; hardware design; Fourier analysis; Laplace transform; Delphi; Laplace space; high-level computer programming; linear system toolbox
Subjects: Signal processing theory; Digital signal processing; Signal processing and detection
DSP involves manipulation of signals that have their origins in the analog world. Such signals may be produced for example, by video, audio, radio telemetry, radar, thermal, magnetic or ultrasonic sensor systems, to name but a few from a truly enormous range of devices and instruments. The point here is that the signals are originally analog and continuous in nature to start with. With digital signal processing, we can effectively re-write reality, because, just as the currency of our brains is thought, so too the currency of digital signal processing equipment is number. The DSP revolution is not just about fast hardware, although it is undeniably important. DSP is also about ideas and, more importantly, ideas about ideas.
Here we introduce linear systems and provide an account of the basic mathematical equipment that we need for DSP, together with how they are applied in certain practical circumstances. If you are already schooled in these areas, or are familiar with DSP, then the entire chapter can be skipped. If, however, you have forgotten how to differentiate, or have never used complex numbers before, then what follows is for you. These subjects are important because if you can master them then you will have little difficulty in coding DSP algorithms that can do some truly astonishing things. As the chapter title suggests, these are essential tools. We will not go into the proofs as to why they are true, but we will see why they are used, and when they are appropriate.
This is not a book about computer programming; dozens of excellent texts on this subject adorn the computing sections of most bookshops, so it is clear that for a complete story, many more pages are required than we can afford here. However, without some discussion of the matter, the whole subject of DSP becomes rather academic after all, DSP is only of real and practical value once the algorithms have been encoded in computer language form. In keeping with what was stated in the Preface, this book represents a single package solution, so here we are going to explore enough about high-level computer programming to enable us to perform even the most complex of DSP operations. What is a high-level computer language? The simple answer is that it is any language whose source code (what the programmer writes) needs to be compiled into binary form the object code before it can be executed by the processor. Thus, the source code is often represented as a series of quasi-English expressions that are relatively straightforward to understand from a human perspective. Such languages include BASIC, C, C++, FORTRAN, Pascal and Java, to name but a few. On a slightly more technical level, with high-level languages, a single instruction in the source code invariably corresponds to several or many instructions in the binary code.
This chapter discusses the analysis and modelling of simple electrical circuits comprising various arrangements of resistors, capacitors and inductors, since these are the fundamental building blocks of such systems.
In Chapter 2 the author stated that the impulse response is the most important feature of a linear system, because it characterises it completely. Later, in Chapter 4, we saw how differential equations and difference equations could be used to describe or derive the impulse and step responses of linear systems. However, as yet we have not shown how the impulse response may be used to replicate or predict the response of such systems to any input signal. This is where convolution enters our discussions. It is impossible to overstate the importance of this operation, because so many DSP algorithms exploit convolution in one form or another.
The key question is: how do we analyse the sound to determine exactly which frequencies are present in the waveform? A second question naturally leads on from this: given a range of frequencies, how do we generate a time-domain waveform? These questions are answered, respectively, by Fourier analysis and synthesis. It is impossible to overstate the importance of the Fourier transform (and by implication, the inverse Fourier transform) to DSP. It really does lie at its core, and without it DSP would simply not exist. It is then all the more extraordinary that for a long time, Fourier's ideas were not accepted as generally valid and that at least 15 years elapsed between his conceiving of the theorem and its publication. It states that any waveform may be decomposed into a series of sinusoids of ascending frequency, each with a particular magnitude and phase. It applies to both periodic and aperiodic signals, of which the latter are far the more common in nature and engineering. Be aware of the nomenclature in this regard; when analysing periodic waveforms, the Fourier series is applied. When analysing aperiodic signals, we apply the Fourier transform.
In this chapter, we will take a detailed look at some of the more important properties of the discrete Fourier transform (DFT), the different ways of representing spectra, and finally some of the key processing operations that are frequently implemented using a Fourier-based approach.
Both the Laplace transform and the z-transform are closely related to, respectively, the continuous Fourier transform and the discrete time Fourier transform. However, because they employ a complex frequency variable (s or z) rather than a purely imaginary one (jω), they are more general in scope. The Laplace transform is for example, ubiquitously employed for the analysis and design of electrical circuits such as filters and networks, and is ideally suited for the analysis of transient response phenomena (Hickmann, 1999). Similarly the z-transform is an indispensable tool for the design and analysis of digital filters, especially infinite impulse response (ΠR) filters, of which we will have much to say in this and later chapters.
In this chapter we have emphasised the overriding importance of the z-transform, poles and zeros and the z-transfer function in relation to the analysis, design and description of IIR filters. In contrast, although FIR filters may also be described using this technique, in practice we normally exploit other means to compute the coefficients of the impulse response. However, before we proceed to scrutinize in greater depth the general digital filter design problem, it would be enlightening if we first spent a little time studying how we actually sample the signals we wish to process.
This chapter has laid the foundations for good sampling practice, in that it has shown why it is necessary to sample band-limited signals at a rate which is above than given rate. In a complementary manner, it has also identified why sampling at great speed is unnecessary, being wasteful of bandwidth and storage space, thereby adding nothing useful to the information content of that same signal. The subtleties associated with the discrete and the digitised signal, and examined various means of analog to digital and digital to analog conversion. Finally, some methods that might be adopted when designing digital signal acquisition and transmission systems are also discussed. Armed with this knowledge, one can now move forward to consider the design of off-line and real-time DSP algorithms and systems hardware.
Design of FIR filters is predicated on a single question: given a desired frequency response, how do we obtain the (discrete) coefficients of its impulse response? There are several ways in which the coefficients may be obtained, and each method has its own merits and limitations. In this chapter, we shall study two of the most widely applied techniques, these being the window method and the frequency sampling method. It is fair to say that in practice the overwhelming majority of filters are computed using these two methods, since they are simple to implement, the algorithms are inherently stable, efficient and rapid and the resulting impulse response has excellent phase and frequency response characteristics.
In this chapter, we have by no means explored all the ways in which it is possible to design IIR filters. Neither, it should be stressed, have we discussed all the major analog families that are represented in digital form (such as the elliptic filter). We have, however, scrutinised some of the more widely adopted approaches, and, most importantly, considered the basic principles of IIR construction. Up to this point, we have gained a working knowledge of three very important classes of digital filter: Fourier, FIR and IIR types. Although the manner of their realisations differs, they all share a pivotal characteristic of linearity, in that their properties do not change over time. In the next chapter, we will look at the adaptive filter, which, as its name suggests, adapts its response according to the form of its input signals.
Our analysis of digital filters thus far has shown us that they can be designed with performances far exceeding those of linear analog types, respecting transition zone width, stop band attenuation and phase linearity. Moreover, the fact that it is possible to design real-time digital filters with arbitrary frequency response characteristics opens up new and almost undreamed of possibilities in both signal analysis and synthesis.
In this chapter, we will be introducing the Motorola DSP56309 digital signal processor, which is an advanced device capable of processing at 100 MMACS; it is a member of the DSP563xx family that includes processors with speeds ranging from 100 to 400 MMACS. We will then extend our discussions to learn how we can design real-time DSP hardware based around this device, using as a vehicle for our discussions an audio signal processor. Now a critic could argue that case studies of this kind very quickly become obsolete, because of the very rapid advances in this area of technology. Although it is true that new devices soon replace their forerunners, it is also a fact that the general operating protocols of DSP devices do not differ much from model to model.
We consider a simple but very useful and flexible real-time DSP system incorporating the DSP56309 as the core processor. Although quite straightforward in concept, the design is suitable for advanced stereophonic signal processing of audio bandwidth signals. This design utilises a dual channel audio codec, 256 kbytes of external flash memory for holding data or boot-up code and facilities for communicating directly with the serial interface of a PC. To keep the design as straightforward as possible, we have omitted external static random access memory (SRAM). This is not a problem here because the device's internal memory area is large enough to accommodate programs of considerable size and complexity. Because the system has both flash and a PC interface, it may operate either as a stand-alone processing environment or as a slave unit connected to a computer. A number of the control signals are tied to the power rail or ground by 15 kΩ resistors. This is because of the operating mode that has been selected for this system.
The purpose of this book was to establish the principles of digital signal processing, and to explain the steps by which these principles may be expressed in practical, realisable terms, for both off-line and real-time processing environments. For this reason, the treatment has emphasised the foundations of the discipline (hence the title). In this context, subjects that merit the greatest attention are linear systems, Fourier analysis, convolution, signal acquisition and filtering; the reader will judge whether or not the pedagogical objectives in exploring these themes have success fully been achieved. Although in Chapter 1 we commenced with a discourse on the nature and definitions of DSP and the many areas in which it is exploited, detailed coverage of application areas has been deliberately avoided for instance, we have not discussed how DSP is used for signal compression, decompression, voice band coding, musical technology and so on. To do so would have made the length of the book excessive; a proper account of each of these areas deserves a text in its own right. In this concluding chapter however, it would be appropriate to speculate on the future of DSP technology and how it will be applied over the coming years.
The theoretical framework and algorithmic realisation of the fast Fourier transform (FFT) was first established in workable form by Cooley and Tukey in 1965, although, as was stated in Chapter 6, several early pioneers in this area had made partial contributions to the technique. The development of the FFT was arguably the single most important contribution to DSP, enabling practical realisation of a vast number of algorithms that we now take for granted. Bearing in mind that there are many ways in which the FFT can be implemented, in this appendix we will examine briefly the radix-2 decimation-in-time fast Fourier transform (DIT FFT). The FFT is far more efficient than a directly implemented DFT, the number of calculations being propor tional to log2 N for the former, in comparison to iV2 for the latter, for an N-point data record. The mathematical treatment below has been compiled from a number of sources, including Ifeachor and Jervis (1993), Oppenheim and Shafer (1999), Lynn and Feurst (1998), Burrus and Parks (1985), Sohie and Chen (1993) and Ingle and Proakis (1991). With regard to the indexing problem, which appears later in the Appendix, I have extended the explanation provided by Ifeachor and Jervis to clarify the operation of my implementation of the radix-2 DIT FFT algorithm, which is available on the CD accompanying this book.
