The Roots of DSP Telecommunications Audio Processing Echo Location Imaging Processing

Digital Signal Processing is one of the most powerful technologies that will shape science and engineering in the twenty-first century. Revolutionary changes have already been made in a broad range of fields: communications, medical imaging, radar & sonar, high fidelity music reproduction, and oil prospecting, to name just a few. Each of these areas has developed a deep DSP technology, with its own algorithms, mathematics, and specialized techniques. This combination of breath and depth makes it impossible for any one individual to master all of the DSP technology that has been developed. DSP education involves two tasks: learning general concepts that apply to the field as a whole, and learning specialized techniques for your particular area of interest. This chapter starts our journey into the world of Digital Signal Processing by describing the dramatic effect that DSP has made in several diverse fields. The revolution has begun.

Chapter 2. Statistics, Probability and Noise

Signal and Graph Terminology Mean and Standard Deviation Signal vs. Underlying Process The Histogram, Pmf and Pdf The Normal Distribution Digital Noise Generation Precision and Accuracy

Statistics and probability are used in Digital Signal Processing to characterize signals and the processes that generate them. For example, a primary use of DSP is to reduce interference, noise, and other undesirable components in acquired data. These may be an inherent part of the signal being measured, arise from imperfections in the data acquisition system, or be introduced as an unavoidable byproduct of some DSP operation. Statistics and probability allow these disruptive features to be measured and classified, the first step in developing strategies to remove the offending components. This chapter introduces the most important concepts in statistics and probability, with emphasis on how they apply to acquired signals.

Chapter 3. ADC and DAC

Quantization The Sampling Theorem Digital-to-Analog Conversion Analog Filters for Data Conversion Selecting the Antialias Filter Multirate Data Conversion Single Bit Data Conversion

Most of the signals directly encountered in science and engineering are continuous: light intensity that changes with distance; voltage that varies over time; a chemical reaction rate that depends on temperature, etc. Analog-to-Digital Conversion (ADC) and Digital-to-Analog Conversion (DAC) are the processes that allow digital computers to interact with these everyday signals. Digital information is different from its continuous counterpart in two important respects: it is sampled, and it is quantized. Both of these restrict how much information a digital signal can contain. This chapter is about information management: understanding what information you need to retain, and what information you can afford to lose. In turn, this dictates the selection of the sampling frequency, number of bits, and type of analog filtering needed for converting between the analog and digital realms.

Chapter 4. DSP Software

Computer Numbers Fixed Point (Integers) Floating Point (Real Numbers) Number Precision Execution Speed: Program Language Execution Speed: Hardware Execution Speed: Programming Tips

DSP applications are usually programmed in the same languages as other science and engineering tasks, such as: C, BASIC and assembly. The power and versatile of C makes it the language of choice for computer scientists and other professional programmers. On the other hand, the simplicity of BASIC makes it ideal for scientists and engineers who only occasionally visit the programming world. Regardless of the language you use, most of the important DSP software issues are buried far below in the realm of whirling ones and zeros. This includes such topics as: how numbers are represented by bit patterns, round-off error in computer arithmetic, the computational speed of different types of processors, etc. This chapter is about the things you can do at the high level to avoid being trampled by the low level internal workings of your computer.

Signals and Systems Requirements for Linearity Static Linearity and Sinusoidal Fidelity Examples of Linear & Nonlinear Systems Special Properties of Linearity Superposition: the Foundation of DSP Common Decompositions Alternatives to Linearity Summary of the key concepts

Most DSP techniques are based on a divide-and-conquer strategy called superposition. The signal being processed is broken into simple components, each component is processed individually, and the results reunited. This approach has the tremendous power of breaking a single complicated problem into many easy ones. Superposition can only be used with linear systems, a term meaning that certain mathematical rules apply. Fortunately, most of the applications encountered in science and engineering fall into this category. This chapter presents the foundation of DSP: what it means for a system to be linear, various ways for breaking signals into simpler components, and how superposition provides a variety of signal processing techniques.

Chapter 6. Convolution

The Delta Function and Impulse Response Convolution The Input Side Algorithm The Output Side Algorithm The Sum of Weighted Inputs

Convolution is a mathematical way of combining two signals to form a third signal. It is the single most important technique in Digital Signal Processing. Using the strategy of impulse decomposition, systems are described by a signal called the impulse response. Convolution is important because it relates the three signals of interest: the input signal, the output signal, and the impulse response. This chapter presents convolution from two different viewpoints, called the input side algorithm and the output side algorithm. Convolution provides the mathematical framework for DSP; there is nothing more important in this book.

Chapter 7. Properties of Convolution

Common Impulse Responses Mathematical Properties Correlation Speed Summary of the key concepts

A linear system's characteristics are completely specified by the system's impulse response, as governed by the mathematics of convolution. This is the basis of many signal processing techniques. For example: Digital filters are created by designing an appropriate impulse response. Enemy aircraft are detected with radar by analyzing a measured impulse response. Echo suppression in long distance telephone calls is accomplished by creating an impulse response that counteracts the impulse response of the reverberation. The list goes on and on. This chapter expands on the properties and usage of convolution in several areas. First, several common impulse responses are discussed. Second, methods are presented for dealing with cascade and parallel combinations of linear systems. Third, the technique of correlation is introduced. Forth, a nasty problem with convolution is examined, the computation time can be unacceptably long using conventional algorithms and computers.

Chapter 8. The Discrete Fourier Transform

The Family of Fourier Transforms Notation and Format of the DFT The Frequency Domain's Independent Variable DFT Basis Functions Synthesis, Calculating the Inverse DFT Analysis, Calculating the DFT Duality Polar Notation Polar Nuisances

Fourier analysis is a family of mathematical techniques, all based on decomposing signals into sinusoids. The discrete Fourier transform (DFT) is the family member used with digitized signals. This is the first of four chapters on the real DFT, a version of the discrete Fourier transform that uses real numbers to represent the input and output signals. The complex DFT, a more advanced technique that uses complex numbers, will be discussed in Chapter 29. In this chapter we look at the mathematics and algorithms of the Fourier decomposition, the heart of the DFT.

Chapter 9. Applications of the DFT

Spectral Analysis of Signals Frequency Response of Systems Convolution via the Frequency Domain

The Discrete Fourier Transform (DFT) is one of the most important tools in Digital Signal Processing. This chapter discusses three common ways it is used. First, the DFT can calculate a signal's frequency spectrum. This is a direct examination of information encoded in the frequency, phase, and amplitude of the component sinusoids. For example, human speech and hearing use signals with this type of encoding. Second, the DFT can find a system's frequency response from the system's impulse response, and vice versa. This allows systems to be analyzed in the frequency domain, just as convolution allows systems to be analyzed in the time domain. Third, the DFT can be used as an intermediate step in more elaborate signal processing techniques. The classic example of this is FFT convolution, an algorithm for convolving signals that is hundreds of times faster than conventional methods.

Chapter 10. Fourier Transform Properties

Linearity of the Fourier Transform Characteristics of the Phase Periodic Nature of the DFT Compression and Expansion Multiplying Signals (Amplitude Modulation) The Discrete Time Fourier Transform Parseval's Relation

The time and frequency domains are alternative ways of representing signals. The Fourier transform is the mathematical relationship between these two representations. If a signal is modified in one domain, it will also be changed in the other domain, although usually not in the same way. For example, it was shown in the last chapter that convolving time domain signals results in their frequency spectra being multiplied. Other mathematical operations, such as addition, scaling and shifting, also have a matching operation in the opposite domain. These relationships are called properties of the Fourier Transform, how a mathematical change in one domain results in a mathematical change in the other domain.

Chapter 11. Fourier Transform Pairs

Delta Function Pairs The Sinc Function Other Transform Pairs Gibbs Effect Harmonics Chirp Signals Summary of the key concepts

For every time domain waveform there is a corresponding frequency domain waveform, and vice versa. For example, a rectangular pulse in the time domain coincides with a sinc function in the frequency domain. Duality provides that the reverse is also true; a rectangular pulse in the frequency domain matches a sinc function in the time domain. Waveforms that correspond to each other in this manner are called Fourier transform pairs. Several common pairs are presented in this chapter.

Chapter 12. The Fast Fourier Transform

Real DFT Using the Complex DFT How the FFT Works FFT Programs Speed and Precision Comparisons Further Speed Increases

There are several ways to calculate the Discrete Fourier Transform (DFT), such as solving simultaneous linear equations or the correlation method described in Chapter 8. The Fast Fourier Transform (FFT) is another method for calculating the DFT. While it produces the same result as the other approaches, it is incredibly more efficient, often reducing the computation time by hundreds. This is the same improvement as flying in a jet aircraft versus walking! If the FFT were not available, many of the techniques described in this book would not be practical. While the FFT only requires a few dozen lines of code, it is one of the most complicated algorithms in DSP. But don't despair! You can easily use published FFT routines without fully understanding the internal workings.

Chapter 13. Continuous Signal Processing

The Delta Function Convolution The Fourier Transform The Fourier Series Summary of the key concepts

Continuous signal processing is a parallel field to DSP, and most of the techniques are nearly identical. For example, both DSP and continuous signal processing are based on linearity, decomposition, convolution and Fourier analysis. Since continuous signals cannot be directly represented in digital computers, don't expect to find computer programs in this chapter. Continuous signal processing is based on mathematics; signals are represented as equations, and systems change one equation into another. Just as the digital computer is the primary tool used in DSP, calculus is the primary tool used in continuous signal processing. These techniques have been used for centuries, long before computers were developed.

Filter Basics How Information is Represented in Signals Time Domain Parameters Frequency Domain Parameters High-Pass, Band-Pass and Band-Reject Filters

Digital filters are used for two general purposes: (1) separation of signals that have been combined, and (2) restoration of signals that have been distorted in some way. Analog (electronic) filters can be used for these same tasks; however, digital filters can achieve far superior results. The most popular digital filters are described and compared in the next seven chapters. This introductory chapter describes the parameters you want to look for when learning about each of these filters.

Chapter 15. Moving Average Filters

Implementation by Convolution Noise Reduction vs. Step Response Relatives of the Moving Average Filter Recursive Implementation Summary of the key concepts

The moving average is the most common filter in DSP, mainly because it is the easiest digital filter to understand and use. In spite of its simplicity, the moving average filter is optimal for a common task: reducing random noise while retaining a sharp step response. This makes it the premier filter for time domain encoded signals. However, the moving average is the worst filter for frequency domain encoded signals, with little ability to separate one band of frequencies from another. Relatives of the moving average filter include the Gaussian, Blackman, and multiple-pass moving average. These have slightly better performance in the frequency domain, at the expense of increased computation time.

Chapter 16. Windowed-Sinc Filters

Strategy of the Windowed-Sinc Designing the Filter Examples of Windowed-Sinc Filters Pushing it to the Limit Summary of the key concepts

Windowed-sinc filters are used to separate one band of frequencies from another. They are very stable, produce few surprises, and can be pushed to incredible performance levels. These exceptional frequency domain characteristics are obtained at the expense of poor performance in the time domain, including excessive ripple and overshoot in the step response. When carried out by standard convolution, windowed-sinc filters are easy to program, but slow to execute. Chapter 18 shows how the FFT can be used to dramatically improve the computational speed of these filters.

Chapter 17. Custom Filters

Arbitrary Frequency Response Deconvolution Optimal Filters

Most filters have one of the four standard frequency responses: low-pass, high-pass, band-pass or band-reject. This chapter presents a general method of designing digital filters with an arbitrary frequency response, tailored to the needs of your particular application. DSP excels in this area, solving problems that are far above the capabilities of analog electronics. Two important uses of custom filters are discussed in this chapter: deconvolution, a way of restoring signals that have undergone an unwanted convolution, and optimal filtering, the problem of separating signals with overlapping frequency spectra. This is DSP at its best.

Chapter 18. FFT Convolution

The Overlap-Add Method FFT Convolution Speed Improvements

This chapter presents two important DSP techniques, the overlap-add method, and FFT convolution. The overlap-add method is used to break long signals into smaller segments for easier processing. FFT convolution uses the overlap-add method together with the Fast Fourier Transform, allowing signals to be convolved by multiplying their frequency spectra. For filter kernels longer than about 64 points, FFT convolution is faster than standard convolution, while producing exactly the same result.

Chapter 19. Recursive Filters

The Recursive Method Single Pole Recursive Filters Narrow-band Filters Phase Response Using Integers

Recursive filters are an efficient way of achieving a long impulse response, without having to perform a long convolution. They execute very rapidly, but have less performance and flexibility than other digital filters. Recursive filters are also called Infinite Impulse Response (IIR) filters, since their impulse responses are composed of decaying exponentials. This distinguishes them from digital filters carried out by convolution, called Finite Impulse Response (FIR) filters. This chapter is an introduction to how recursive filters operate, and how simple members of the family can be designed. Chapters 20, 26 and 31 present more sophisticated design methods.

Chapter 20. Chebyshev Filters

The Chebyshev and Butterworth Responses Designing the Filter Step Response Overshoot Stability Summary of the key concepts

Chebyshev filters are used to separate one band of frequencies from another. Although they cannot match the performance of the windowed-sinc filter, they are more than adequate for many applications. The primary attribute of Chebyshev filters is their speed, typically more than an order of magnitude faster than the windowed-sinc. This is because they are carried out by recursion rather than convolution. The design of these filters is based on a mathematical technique called the z- transform, discussed in Chapter 31. This chapter presents the information needed to use Chebyshev filters without wading through a mire of advanced mathematics.

Chapter 21. Filter Comparison

Match #1: Analog vs. Digital Filters Match #2: Windowed-Sinc vs. Chebyshev Match #3: Moving Average vs. Single Pole

Decisions, decisions, decisions! With all these filters to choose from, how do you know which to use? This chapter is a head-to-head competition between filters; we'll select champions from each side and let them fight it out. In the first match, digital filters are pitted against analog filters to see which technology is best. In the second round, the windowed-sinc is matched against the Chebyshev to find the king of the frequency domain filters. In the final battle, the moving average fights the single pole filter for the time domain championship. Enough talk; let the competition begin!

Human Hearing Timbre Sound Quality vs. Data Rate High Fidelity Audio Companding Speech Synthesis and Recognition Nonlinear Audio Processing

Audio processing covers many diverse fields, all involved in presenting sound to human listeners. Three areas are prominent: (1) high fidelity music reproduction, such as in audio compact discs, (2) voice telecommunications, another name for telephone networks, and (3) synthetic speech, where computers generate and recognize human voice patterns. While these applications have different goals and problems, they are linked by a common umpire: the human ear. Digital Signal Processing has produced revolutionary changes in these and other areas of audio processing.

Chapter 23. Image Formation and Display

Digital Image Structure Cameras and Eyes Television Video Signals Other Image Acquisition and Display Brightness and Contrast Adjustments Grayscale Transforms Warping

Images are a description of how a parameter varies over a surface. For example, standard visual images result from light intensity variations across a two-dimensional plane. However, light is not the only parameter used in scientific imaging. For example, an image can be formed of the temperature of an integrated circuit, blood velocity in a patient's artery, x-ray emission from a distant galaxy, ground motion during an earthquake, etc. These exotic images are usually converted into conventional pictures (i.e., light images), so that they can be evaluated by the human eye. This first chapter on image processing describes how digital images are formed and presented to human observers.

Chapter 24. Linear Image Processing

Convolution 3 3 Edge Modification Convolution by Separability Illumination Flattening Fourier Image Analysis FFT Convolution Summary of the key concepts

Linear image processing is based on the same two techniques as conventional DSP: convolution and Fourier analysis. Convolution is the more important of these two, since images have their information encoded in the spatial domain rather than the frequency domain. Linear filtering can improve images in many ways: sharpening the edges of objects, reducing random noise, correcting for unequal illumination, deconvolution to correct for blur and motion, etc. These procedures are carried out by convolving the original image with an appropriate filter kernel, producing the filtered image. A serious problem with image convolution is the enormous number of calculations that need to be performed, often resulting in unacceptably long execution times. This chapter presents strategies for designing filter kernels for various image processing tasks. Two important techniques for reducing the execution time are also described: convolution by separability and FFT convolution.

Chapter 25. Special Imaging Techniques

Spatial Resolution Sample Spacing and Sampling Aperture Signal-to-Noise Ratio Morphological Image Processing Computed Tomography

This chapter presents four specific aspects of image processing. First, ways to characterize the spatial resolution are discussed. This describes the minimum size an object must be to be seen in an image. Second, the signal-to-noise ratio is examined, explaining how faint an object can be and still be detected. Third, morphological techniques are introduced. These are nonlinear operations used to manipulate binary images (where each pixel is either black or white). Fourth, the remarkable technique of computed tomography is described. This has revolutionized medical diagnosis by providing detailed images of the interior of the human body.

Chapter 26. Neural Networks (and more!)

Target Detection Neural Network Architecture Why Does it Work? Training the Neural Network Evaluating the Results Recursive Filter Design Summary of the key concepts

Traditional DSP is based on algorithms, changing data from one form to another through step-by-step procedures. Most of these techniques also need parameters to operate. For example: recursive filters use recursion coefficients, feature detection can be implemented by correlation and thresholds, an image display depends on the brightness and contrast settings, etc. Algorithms describe what is to be done, while parameters provide a benchmark to judge the data. The proper selection of parameters is often more important than the algorithm itself. Neural networks take this idea to the extreme by using very simple algorithms, but many highly optimized parameters. This is a revolutionary departure from the traditional mainstays of science and engineering: mathematical logic and theorizing followed by experimentation. Neural networks replace these problem solving strategies with trial & error, pragmatic solutions, and a "this works better than that" methodology. This chapter presents a variety of issues regarding parameter selection in both neural networks and more traditional DSP algorithms.

Chapter 27. Data Compression

Run-Length Encoding Huffman Encoding Delta Encoding LZW Compression JPEG (Transform Compression) MPEG Summary of the key concepts

Data transmission and storage cost money. The more information being dealt with, the more it costs. In spite of this, most digital data are not stored in the most compact form. Rather, they are stored in whatever way makes them easiest to use, such as: ASCII text from word processors, binary code that can be executed on a computer, individual samples from a data acquisition system, etc. Typically, these easy-to-use encoding methods require data files about twice as large as actually needed to represent the information. Data compression is the general term for the various algorithms and programs developed to address this problem. A compression program is used to convert data from an easy-to-use format to one optimized for compactness. Likewise, an uncompression program returns the information to its original form. We examine five techniques for data compression in this chapter. The first three are simple encoding techniques, called: run-length, Huffman, and delta encoding. The last two are elaborate procedures that have established themselves as industry standards: LZW and JPEG.

The Complex Number System Polar Notation Using Complex Numbers by Substitution Complex Representation of Sinusoids Complex Representation of Systems Electrical Circuit Analysis Summary of the key concepts

Complex numbers are an extension of the ordinary numbers used in everyday math. They have the unique property of representing and manipulating two variables as a single quantity. This fits very naturally with Fourier analysis, where the frequency domain is composed of two signals, the real and the imaginary parts. Complex numbers shorten the equations used in DSP, and enable techniques that are difficult or impossible with real numbers alone. For instance, the Fast Fourier Transform is based on complex numbers. Unfortunately, complex techniques are very mathematical, and it requires a great deal of study and practice to use them effectively. Many scientists and engineers regard complex techniques as the dividing line between DSP as a tool, and DSP as a career. In this chapter, we look at the mathematics of complex numbers, and elementary ways of using them in science and engineering. The following three chapters discuss important techniques based on complex numbers: the complex Fourier transform, the Laplace transform, and the z-transform. These complex transforms are the heart of theoretical DSP. Get ready, here comes the math!

Chapter 29. The Complex Fourier Transform

The Real DFT Mathematical Equivalence The Complex DFT The Family of Fourier Transforms Why the Complex Fourier Transform is Used

Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform, a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms. These complex transforms are the foundation of theoretical DSP.

Chapter 30. The Laplace Transform

The Nature of the s-Domain Probing the Impulse Response Analysis of Electric Circuits The Importance of Poles and Zeros Filter Design in the s-Domain

The two main techniques in signal processing, convolution and Fourier analysis, teach that a linear system can be completely understood from its impulse or frequency response. This is a very generalized approach, since the impulse and frequency responses can be of nearly any shape or form. In fact, it is too general for many applications in science and engineering. Many of the parameters in our universe interact through differential equations. For example, the voltage across an inductor is proportional to the derivative of the current through the device. Likewise, the force applied to a mass is proportional to the derivative of its velocity. Physics is filled with these kinds of relations. The frequency and impulse responses of these systems cannot be arbitrary, but must be consistent with the solution of these differential equations. This means that their impulse responses can only consist of exponentials and sinusoids. The Laplace transform is a technique for analyzing these special systems when the signals are continuous. The z- transform is a similar technique used in the discrete case.

Chapter 31. The z-Transform

The Nature of the z-Domain Analysis of Recursive Systems Cascade and Parallel Stages Spectral Inversion Gain Changes Chebyshev-Butterworth Filter Design Summary of the key concepts

Just as analog filters are designed using the Laplace transform, recursive digital filters are developed with a parallel technique called the z-transform. The overall strategy of these two transforms is the same: probe the impulse response with sinusoids and exponentials to find the system's poles and zeros. The Laplace transform deals with differential equations, the s-domain, and the s-plane. Correspondingly, the z-transform deals with difference equations, the z-domain, and the z-plane. However, the two techniques are not a mirror image of each other; the s-plane is arranged in a rectangular coordinate system, while the z-plane uses a polar format. Recursive digital filters are often designed by starting with one of the classic analog filters, such as the Butterworth, Chebyshev, or elliptic. A series of mathematical conversions are then used to obtain the desired digital filter. The z-transform provides the framework for this mathematics. The Chebyshev filter design program presented in Chapter 20 uses this approach, and is discussed in detail in this chapter.

Return to home page