book

Understanding Digital Signal Processing, Second Edition

by Richard G. Lyons

March 2004

Intermediate to advanced

688 pages

16h 56m

English

Pearson

Read now

Unlock full access

Dedication
LEARNING DIGITAL SIGNAL PROCESSINGTHE JOURNEYCOMING ATTRACTIONSACKNOWLEDGMENTS
1.1. DISCRETE SEQUENCES AND THEIR NOTATION1.2. SIGNAL AMPLITUDE, MAGNITUDE, POWER1.3. SIGNAL PROCESSING OPERATIONAL SYMBOLS1.4. INTRODUCTION TO DISCRETE LINEAR TIME-INVARIANT SYSTEMS1.5. DISCRETE LINEAR SYSTEMS1.5.1. Example of a Linear System1.5.2. Example of a Nonlinear System1.6. TIME-INVARIANT SYSTEMS1.6.1. Example of a Time-Invariant System1.7. THE COMMUTATIVE PROPERTY OF LINEAR TIME-INVARIANT SYSTEMS1.8. ANALYZING LINEAR TIME-INVARIANT SYSTEMSREFERENCES
2.1. ALIASING: SIGNAL AMBIGUITY IN THE FREQUENCY DOMAIN2.2. SAMPLING LOW-PASS SIGNALS2.3. SAMPLING BANDPASS SIGNALS2.4. SPECTRAL INVERSION IN BANDPASS SAMPLINGREFERENCES
3.1. UNDERSTANDING THE DFT EQUATION3.1.1. DFT Example 13.2. DFT SYMMETRY3.3. DFT LINEARITY3.4. DFT MAGNITUDES3.5. DFT FREQUENCY AXIS3.6. DFT SHIFTING THEOREM3.6.1. DFT Example 23.7. INVERSE DFT3.8. DFT LEAKAGE3.9. WINDOWS3.10. DFT SCALLOPING LOSS3.11. DFT RESOLUTION, ZERO PADDING, AND FREQUENCY-DOMAIN SAMPLING3.12. DFT PROCESSING GAIN3.12.1. Processing Gain of a Single DFT3.12.2. Integration Gain Due to Averaging Multiple DFTs3.13. THE DFT OF RECTANGULAR FUNCTIONS3.13.1. DFT of a General Rectangular Function3.13.2. DFT of a Symmetrical Rectangular Function3.13.3. DFT of an All Ones Rectangular Function3.13.4. Time and Frequency Axes Associated with Rectangular Functions3.13.4.1. DFT Frequency Axis in Hz3.13.4.2. DFT Frequency Axis in Radians/Second3.13.4.3. DFT Frequency Axis Using a Normalized Angle Variable3.13.5. Alternate Form of the DFT of an All Ones Rectangular Function3.13.6. Inverse DFT of a General Rectangular Function3.13.7. Inverse DFT of a Symmetrical Rectangular Function3.14. THE DFT FREQUENCY RESPONSE TO A COMPLEX INPUT3.15. THE DFT FREQUENCY RESPONSE TO A REAL COSINE INPUT3.16. THE DFT SINGLE-BIN FREQUENCY RESPONSE TO A REAL COSINE INPUT3.17. INTERPRETING THE DFTREFERENCES
4.1. RELATIONSHIP OF THE FFT TO THE DFT4.2. HINTS ON USING FFTS IN PRACTICE4.2.1. Sample Fast Enough and Long Enough4.2.2. Manipulating the Time Data Prior to Transformation4.2.3. Enhancing FFT Results4.2.4. Interpreting FFT Results4.3. FFT SOFTWARE PROGRAMS4.4. DERIVATION OF THE RADIX-2 FFT ALGORITHM4.5. FFT INPUT/OUTPUT DATA INDEX BIT REVERSAL4.6. RADIX-2 FFT BUTTERFLY STRUCTURESREFERENCES

5.1. AN INTRODUCTION TO FINITE IMPULSE RESPONSE (FIR) FILTERS5.2. CONVOLUTION IN FIR FILTERS5.3. LOW-PASS FIR FILTER DESIGN5.3.1. Window Design Method5.3.2. Windows Used in FIR Filter Design5.4. BANDPASS FIR FILTER DESIGN5.5. HIGHPASS FIR FILTER DESIGN5.6. REMEZ EXCHANGE FIR FILTER DESIGN METHOD5.7. HALF-BAND FIR FILTERS5.8. PHASE RESPONSE OF FIR FILTERS5.9. A GENERIC DESCRIPTION OF DISCRETE CONVOLUTION5.9.1. Discrete Convolution in the Time Domain5.9.2. The Convolution Theorem5.9.3. Applying the Convolution TheoremREFERENCES
6.1. AN INTRODUCTION TO INFINITE IMPULSE RESPONSE FILTERS6.2. THE LAPLACE TRANSFORM6.2.1. Poles and Zeros on the s-Plane and Stability6.3. THE Z-TRANSFORM6.3.1. Poles and Zeros on the z–Plane and Stability6.3.2. Using the z-Transform to Analyze IIR Filters6.3.3. Alternate IIR Filter Structures6.4. IMPULSE INVARIANCE IIR FILTER DESIGN METHOD6.4.1. Impulse Invariance Design Method 1 Example6.4.2. Impulse Invariance Design Method 2 Example6.5. BILINEAR TRANSFORM IIR FILTER DESIGN METHOD6.5.1. Bilinear Transform Design Example6.6. OPTIMIZED IIR FILTER DESIGN METHOD6.7. PITFALLS IN BUILDING IIR FILTERS6.8. IMPROVING IIR FILTERS WITH CASCADED STRUCTURES6.8.1. Cascade and Parallel Filter Properties6.8.2. Cascading IIR Filters6.9. A BRIEF COMPARISON OF IIR AND FIR FILTERSREFERENCES
7.1. FREQUENCY SAMPLING FILTERS: THE LOST ART7.1.1. A Comb Filter and Complex Digital Resonator in Cascade7.1.2. Multisection Complex FSFs7.1.3. Ensuring FSF Stability7.1.4. Multisection Real-Valued FSFs7.1.5. Linear-Phase Multisection Real-Valued FSFs7.1.6. Where We've Been and Where We're Going with FSFs7.1.7. An Efficient Real-Valued FSF7.1.8. Modeling FSFs7.1.9. Improving Performance with Transition Band Coefficients7.1.10. Alternate FSF Structures7.1.11. The Merits of FSFs7.1.12. Type-IV FSF Example7.1.13. When to Use an FSF7.1.14. Designing FSFs7.1.15. FSF Summary7.2. INTERPOLATED LOWPASS FIR FILTERS7.2.1. Choosing the Optimum Expansion Factor M7.2.2. Estimating the Number of FIR Filter Taps7.2.3. Modeling IFIR Filter Performance7.2.4. IFIR Filter Implementation Issues7.2.5. IFIR Filter Design ExampleREFERENCES
8.1. WHY CARE ABOUT QUADRATURE SIGNALS?8.2. THE NOTATION OF COMPLEX NUMBERS8.3. REPRESENTING REAL SIGNALS USING COMPLEX PHASORS8.4. A FEW THOUGHTS ON NEGATIVE FREQUENCY8.5. QUADRATURE SIGNALS IN THE FREQUENCY DOMAIN8.6. BANDPASS QUADRATURE SIGNALS IN THE FREQUENCY DOMAIN8.7. COMPLEX DOWN-CONVERSION8.8. A COMPLEX DOWN-CONVERSION EXAMPLE8.9. AN ALTERNATE DOWN-CONVERSION METHODREFERENCES
9.1. HILBERT TRANSFORM DEFINITION9.2. WHY CARE ABOUT THE HILBERT TRANSFORM?9.3. IMPULSE RESPONSE OF A HILBERT TRANSFORMER9.4. DESIGNING A DISCRETE HILBERT TRANSFORMER9.4.1. Time-Domain Hilbert Transformation: FIR Filter Implementation9.4.2. Frequency-Domain Hilbert Transformation9.5. TIME-DOMAIN ANALYTIC SIGNAL GENERATION9.6. COMPARING ANALYTIC SIGNAL GENERATION METHODSREFERENCES
10.1. DECIMATION10.2. INTERPOLATION10.3. COMBINING DECIMATION AND INTERPOLATION10.4. POLYPHASE FILTERS10.5. CASCADED INTEGRATOR-COMB FILTERS10.5.1. Recursive Running Sum Filter10.5.2. CIC Filter Structures10.5.3. Improving CIC Attenuation10.5.4. CIC Filter Implementation Issues10.5.5. Compensation/Preconditioning FIR FiltersREFERENCES
11.1. COHERENT AVERAGING11.2. INCOHERENT AVERAGING11.3. AVERAGING MULTIPLE FAST FOURIER TRANSFORMS11.4. FILTERING ASPECTS OF TIME-DOMAIN AVERAGING11.5. EXPONENTIAL AVERAGINGREFERENCES
12.1. FIXED-POINT BINARY FORMATS12.1.1. Octal Numbers12.1.2. Hexadecimal Numbers12.1.3. Fractional Binary Numbers12.1.4. Sign-Magnitude Binary Format12.1.5. Two's Complement Format12.1.6. Offset Binary Format12.2. BINARY NUMBER PRECISION AND DYNAMIC RANGE12.3. EFFECTS OF FINITE FIXED-POINT BINARY WORD LENGTH12.3.1. A/D Converter Quantization Errors12.3.2. Data Overflow12.3.3. Truncation12.3.4. Data Rounding12.4. FLOATING-POINT BINARY FORMATS12.4.1. Floating-Point Dynamic Range12.5. BLOCK FLOATING-POINT BINARY FORMATREFERENCES
13.1. FREQUENCY TRANSLATION WITHOUT MULTIPLICATION13.1.1. Frequency Translation by fs/213.1.2. Frequency Translation by –fs/413.1.3. Filtering and Decimation after fs/4 Down-Conversion13.2. HIGH-SPEED VECTOR MAGNITUDE APPROXIMATION13.3. FREQUENCY-DOMAIN WINDOWING13.4. FAST MULTIPLICATION OF COMPLEX NUMBERS13.5. EFFICIENTLY PERFORMING THE FFT OF REAL SEQUENCES13.5.1. Performing Two N-Point Real FFTs13.5.2. Performing a 2N-Point Real FFT13.6. COMPUTING THE INVERSE FFT USING THE FORWARD FFT13.6.1. Inverse FFT Method 113.6.2. Inverse FFT Method 213.7. SIMPLIFIED FIR FILTER STRUCTURE13.8. REDUCING A/D CONVERTER QUANTIZATION NOISE13.8.1. Oversampling13.8.2. Dithering13.9. A/D CONVERTER TESTING TECHNIQUES13.9.1. Estimating A/D Quantization Noise with the FFT13.9.2. Detecting Missing Codes13.10. FAST FIR FILTERING USING THE FFT13.11. GENERATING NORMALLY DISTRIBUTED RANDOM DATA13.12. ZERO-PHASE FILTERING13.13. SHARPENED FIR FILTERS13.14. INTERPOLATING A BANDPASS SIGNAL13.15. SPECTRAL PEAK LOCATION ALGORITHM13.16. COMPUTING FFT TWIDDLE FACTORS13.17. SINGLE TONE DETECTION13.17.1. Goertzel Algorithm13.17.2. Goertzel Example13.17.3. Goertzel Advantages over the FFT13.18. THE SLIDING DFT13.18.1. The Sliding DFT Algorithm13.18.2. SDFT Stability13.18.3. SDFT Leakage Reduction13.18.4. A Little-Known SDFT Property13.19. THE ZOOM FFT13.20. A PRACTICAL SPECTRUM ANALYZER13.21. AN EFFICIENT ARCTANGENT APPROXIMATION13.22. FREQUENCY DEMODULATION ALGORITHMS13.23. DC REMOVAL13.23.1. Block-Data DC Removal13.23.2. Real-Time DC Removal13.23.3. Real-Time DC Removal with Quantization13.24. IMPROVING TRADITIONAL CIC FILTERS13.24.1. Nonrecursive CIC Filters13.24.2. Nonrecursive Prime Factor-R CIC Filters13.25. SMOOTHING IMPULSIVE NOISE13.26. EFFICIENT POLYNOMIAL EVALUATION13.27. DESIGNING VERY HIGH-ORDER FIR FILTERS13.28. TIME-DOMAIN INTERPOLATION USING THE FFT13.28.1. Computing Interpolated Real Signals13.28.2. Computing Interpolated Analytic Signals13.29. FREQUENCY TRANSLATION USING DECIMATION13.30. AUTOMATIC GAIN CONTROL (AGC)13.31. APPROXIMATE ENVELOPE DETECTION13.32. A QUADRATURE OSCILLATOR13.33. DUAL-MODE AVERAGINGREFERENCES
A.1. GRAPHICAL REPRESENTATION OF REAL AND COMPLEX NUMBERSA.2. ARITHMETIC REPRESENTATION OF COMPLEX NUMBERSA.3. ARITHMETIC OPERATIONS OF COMPLEX NUMBERSA.3.1. Addition and Subtraction of Complex NumbersA.3.2. Multiplication of Complex NumbersA.3.3. Conjugation of a Complex NumberA.3.4. Division of Complex NumbersA.3.5. Inverse of a Complex NumberA.3.6. Complex Numbers Raised to a PowerA.3.7. Roots of a Complex NumberA.3.8. Natural Logarithms of a Complex NumberA.3.9. Logarithm to the Base 10 of a Complex NumberA.3.10. Log to the Base 10 of a Complex Number Using Natural LogarithmsA.4. SOME PRACTICAL IMPLICATIONS OF USING COMPLEX NUMBERSREFERENCES
D.1. STATISTICAL MEASURESD.2. STANDARD DEVIATION, OR RMS, OF A CONTINUOUS SINEWAVED.3. THE MEAN AND VARIANCE OF RANDOM FUNCTIONSD.4. THE NORMAL PROBABILITY DENSITY FUNCTIONREFERENCES
E.1. USING LOGARITHMS TO DETERMINE RELATIVE SIGNAL POWERE.2. SOME USEFUL DECIBEL NUMBERSE.3. ABSOLUTE POWER USING DECIBELS
REFERENCES
G.1. FREQUENCY RESPONSE OF A COMB FILTERG.2. SINGLE COMPLEX FSF FREQUENCY RESPONSEG.3. MULTISECTION COMPLEX FSF PHASEG.4. MULTISECTION COMPLEX FSF FREQUENCY RESPONSEG.5. REAL FSF TRANSFER FUNCTIONG.6. TYPE-IV FSF FREQUENCY RESPONSE

Content preview from Understanding Digital Signal Processing, Second Edition

Chapter Four. The Fast Fourier Transform

Although the DFT is the most straightforward mathematical procedure for determining the frequency content of a time-domain sequence, it's terribly inefficient. As the number of points in the DFT is increased to hundreds, or thousands, the amount of necessary number crunching becomes excessive. In 1965 a paper was published by Cooley and Tukey describing a very efficient algorithm to implement the DFT[1]. That algorithm is now known as the fast Fourier transform (FFT).^[†] Before the advent of the FFT, thousand-point DFTs took so long to perform that their use was restricted to the larger research and university ...