Preface to First Edition ...................................... VII
Preface to Second Edition ...................................... XI
Preface to Third Edition ..................................... XIII
Preface to Fourth Edition ...................................... XV
1 Introduction ............................................... 1
1.1 Overview of Digital Signal Processing (DSP) ................ 1
1.2 FPGA Technology ............................................ 3
1.2.1 Classification by Granularity ....................... 3
1.2.2 Classification by Technology ........................ 6
1.2.3 Benchmark for FPLs .................................. 7
1.3 DSP Technology Requirements ............................... 12
1.3.1 FPGA and Programmable Signal Processors ............ 14
1.4 Design Implementation ..................................... 15
1.4.1 FPGA Structure ..................................... 20
1.4.2 The Altera EP4CE115F29C7 ........................... 23
1.4.3 Case Study: Frequency Synthesizer .................. 32
1.4.4 Design with Intellectual Property Cores ............ 40
Exercises ................................................. 47
2 Computer Arithmetic ....................................... 57
2.1 Introduction .............................................. 57
2.2 Number Representation ..................................... 58
2.2.1 Fixed-Point Numbers ................................ 58
2.2.2 Unconventional Fixed-Point Numbers ................. 61
2.2.3 Floating-Point Numbers ............................. 75
2.3 Binary Adders ............................................. 79
2.3.1 Pipelined Adders ................................... 81
2.3.2 Modulo Adders ...................................... 85
2.4 Binary Multipliers ........................................ 86
2.4.1 Multiplier Blocks ................................. 89
2.5 Binary Dividers ........................................... 93
2.5.1 Linear Convergence Division Algorithms ............. 95
2.5.2 Fast Divider Design ............................... 100
2.5.3 Array Divider ..................................... 105
2.6 Fixed-Point Arithmetic Implementation .................... 106
2.7 Floating-Point Arithmetic Implementation ................. 109
2.7.1 Fixed-Point to Floating-Point Format Conversion ... 110
2.7.2 Floating-Point to Fixed-Point Format Conversion ... 111
2.7.3 Floating-Point Multiplication ..................... 112
2.7.4 Floating-Point Addition ........................... 113
2.7.5 Floating-Point Division ........................... 115
2.7.6 Floating-Point Reciprocal ......................... 116
2.7.7 Floating-Point Operation Synthesis ................ 118
2.7.8 Floating-Point Synthesis Results .................. 122
2.8 Multiply-Accumulator (MAC) and Sum of Product (SOP) ...... 124
2.8.1 Distributed Arithmetic Fundamentals ............... 125
2.8.2 Signed DA Systems ................................. 129
2.8.3 Modified DA Solutions ............................. 130
2.9 Computation of Special Functions Using CORDIC ............ 131
2.9.1 CORDIC Architectures .............................. 135
2.10 Computation of Special Functions using MAC Calls ......... 141
2.10.1 Chebyshev Approximations .......................... 142
2.10.2 Trigonometric Function Approximation .............. 143
2.10.3 Exponential and Logarithmic Function
Approximation ..................................... 152
2.10.4 Square Root Function Approximation ................ 159
2.10 Fast Magnitude Approximation ............................. 165
Exercises ................................................ 168
3 Finite Impulse Response (FIR) Digital Filters ............ 179
3.1 Digital Filters .......................................... 179
3.2 FIR Theory ............................................... 180
3.2.1 FIR Filter with Transposed Structure .............. 181
3.2.2 Symmetry in FIR Filters ........................... 184
3.2.3 Linear-phase FIR Filters .......................... 185
3.3 Designing FIR Filters .................................... 187
3.3.1 Direct Window Design Method ....................... 187
3.3.2 Equiripple Design Method .......................... 190
3.4 Constant Coefficient FIR Design .......................... 192
3.4.1 Direct FIR Design ................................. 192
3.4.2 FIR Filter with Transposed Structure .............. 196
3.4.3 FIR Filters Using Distributed Arithmetic .......... 204
3.4.4 IP Core FIR Filter Design ......................... 215
3.4.9 Comparison of DA- and RAG-Based FIR Filters ....... 217
Exercises ................................................ 219
4 Infinite Impulse Response (IIR) Digital Filters .......... 225
4.1 IIR Theory ............................................... 228
4.2 IIR Coefficient Computation .............................. 231
4.2.1 Summary of Important IIR Design Attributes ........ 233
4.3 IIR Filter Implementation ................................ 234
4.3.1 Finite Wordlength Effects ......................... 238
4.3.2 Optimization of the Filter Gain Factor ............ 239
4.4 Fast IIR Filter .......................................... 240
4.4.1 Time-domain Interleaving .......................... 241
4.4.2 Clustered and Scattered Look-Ahead Pipelining ..... 243
4.4.3 IIR Decimator Design .............................. 246
4.4.4 Parallel Processing ............................... 246
4.4.5 IIR Design Using RNS .............................. 250
4.5 Narrow Band IIR Filter ................................... 250
4.5.1 Narrow Band Design Example ........................ 251
4.5.2 Cascade Second Order Systems Narrow Band Filter
Design ............................................ 259
4.5.3 Parallel Second Order Systems Narrow Band Filter
Design ............................................ 263
4.5.4 Lattice Design of Narrow Band IIR Filter .......... 271
4.5.5 Wave Digital Filter Design of Narrow Band IIR
Filter ............................................ 280
4.6 All-Pass Filter Design of Narrow Band IIR Filter ......... 287
4.6.1 All-Pass Wave Digital Filter Design of Narrow
Band IIR Filter ................................... 289
4.6.2 All-Pass Lattice Design of Narrow Band IIR
Filter ............................................ 293
4.6.3 All-Pass Direct Form Design of Narrow Band
Filter ............................................ 294
4.6.4 All-Pass Cascade BiQuad of Narrow Band Filter ..... 295
4.6.5 All-Pass Parallel BiQuad of Narrow Band Filter .... 295
Exercises ................................................ 299
5 Multirate Signal Processing .............................. 305
5.1 Decimation and Interpolation ............................. 305
5.1.1 Noble Identities .................................. 306
5.1.2 Sampling Rate Conversion by Rational Factor ....... 308
5.2 Polyphase Decomposition .................................. 309
5.2.1 Recursive IIR Decimator ........................... 314
5.2.2 Fast-running FIR Filter ........................... 315
5.3 Hogenauer CIC Filters .................................... 317
5.3.1 Single-Stage CIC Case Study ....................... 317
5.3.2 Multistage CIC Filter Theory ...................... 320
5.3.3 Amplitude and Aliasing Distortion ................. 325
5.3.4 Hogenauer Pruning Theory .......................... 328
5.3.5 CIC RNS Design .................................... 333
5.3.6 CIC Compensation Filter Design .................... 334
5.4 Multistage Decimator ..................................... 337
5.4.1 Multistage Decimator Design Using Goodman-Carey
Half-Band Filters ................................. 338
5.5 Frequency-Sampling Filters as Bandpass Decimators ........ 341
5.6 Design of Arbitrary Sampling Rate Converters ............. 345
5.6.1 Fractional Delay Rate Change ...................... 349
5.6.2 Polynomial Fractional Delay Design ................ 356
5.6.3 B-Spline-Based Fractional Rate Changer ............ 362
5.6.4 MOMS Fractional Rate Changer ...................... 366
5.7 Filter Banks ............................................. 374
5.7.1 Uniform DFT Filter Bank ........................... 375
5.7.2 Two-channel Filter Banks .......................... 379
5.8 Wavelets ................................................. 395
5.8.1 The Discrete Wavelet Transformation ............... 398
5.8.2 Discrete Wavelet Transformation Applications ...... 402
Exercises ................................................ 411
6 Fourier Transforms ....................................... 417
6.1 The Discrete Fourier Transform Algorithms ................ 418
6.1.1 Fourier Transform Approximations Using the DFT .... 418
6.1.2 Properties of the DFT ............................. 420
6.1.3 The Goertzel Algorithm ............................ 423
6.1.4 The Bluestein Chirp-.г Transform .................. 424
6.1.5 The Rader Algorithm ............................... 427
6.1.6 The Winograd DFT Algorithm ........................ 434
6.2 The Fast Fourier Transform (FFT) Algorithms .............. 436
6.2.1 The Cooley-Tukey FFT Algorithm .................... 437
6.2.2 The Good-Thomas FFT Algorithm ..................... 449
6.2.3 The Winograd FFT Algorithm ........................ 451
6.2.4 Comparison of DFT and FFT Algorithms .............. 455
6.2.5 IP Core FFT Design ................................ 456
6.3 Fourier-Related Transforms ............................... 461
6.3.1 Computing the DCT Using the DFT ................... 462
6.3.2 Fast Direct DCT Implementation .................... 463
Exercises ................................................ 465
7 Communication Systems .................................... 475
7.1 Error Control and Cryptography ........................... 475
7.1.1 Basic Concepts from Coding Theory ................. 476
7.1.2 Block Codes ....................................... 482
7.1.3 Convolutional Codes ............................... 485
7.1.4 Cryptography Algorithms for FPGAs ................. 494
7.2 Modulation and Demodulation .............................. 509
7.2.1 Basic Modulation Concepts ......................... 510
7.2.2 Incoherent Demodulation ........................... 515
7.2.3 Coherent Demodulation ............................. 521
Exercises ................................................ 529
8 Adaptive Systems ......................................... 533
8.1 Application of Adaptive Systems .......................... 534
8.1.1 Interference Cancellation ......................... 534
8.1.2 Prediction ........................................ 535
8.1.3 Inverse Modeling .................................. 535
8.1.4 System Identification ............................. 536
8.2 Optimum Estimation Techniques ............................ 537
8.2.1 The Optimum Wiener Estimation ..................... 540
8.3 The Widrow-Hoff Least Mean Square Algorithm .............. 544
8.3.1 Learning Curves ................................... 551
8.3.2 Normalized LMS (NLMS) ............................. 554
8.4 Transform Domain LMS Algorithms .......................... 555
8.4.1 Fast-Convolution Techniques ....................... 556
8.4.2 Using Orthogonal Transforms ....................... 557
8.5 Implementation of the LMS Algorithm ...................... 561
8.5.1 Quantization Effects .............................. 561
8.5.2 FPGA Design of the LMS Algorithm .................. 561
8.5.3 Pipelined LMS Filters ............................. 565
8.5.4 Transposed Form LMS Filter ........................ 567
8.5.5 Design of DLMS Algorithms ......................... 568
8.5.6 LMS Designs using SIGNUM Function ................. 572
8.6 Recursive Least Square Algorithms ........................ 575
8.6.1 RLS with Finite Memory ............................ 578
8.6.2 Fast RLS Kalman Implementation .................... 581
8.6.3 The Fast a Posteriori Kalman RLS Algorithm ........ 586
8.7 Comparison of LMS and RLS Parameters ..................... 587
8.8 Principle Component Analysis (PCA) ....................... 589
8.8.1 Principle Component Analysis Computation .......... 591
8.8.2 Implementation of Sanger's GHA PCA ................ 595
8.9 Independent Component Analysis (ICA) ..................... 601
8.9.1 Whitening and Orthogonalization ................... 603
8.9.2 Independent Component Analysis Algorithm .......... 604
8.9.3 Implementation of the EASI ICA Algorithm .......... 605
8.9.4 Alternative BSS Algorithms ........................ 610
8.10 Coding of Speech and Audio Signals ....................... 612
8.10.1 A- and μ-Law Coding ............................... 612
8.10.2 Linear and Adaptive PCM Coding .................... 617
8.10.3 Coding by Modeling: The LPC-10e Method ............ 623
8.10.4 MPEG Audio Coding Methods ......................... 624
Exercises ................................................ 626
9 Microprocessor Design .................................... 631
9.1 History of Microprocessors ............................... 631
9.1.1 Brief History of General-Purpose Microprocessors .. 632
9.1.2 Brief History of RISC Microprocessors ............. 634
9.1.3 Brief History of PDSPs ............................ 635
9.2 Instruction Set Design ................................... 638
9.2.1 Addressing Modes .................................. 638
9.2.2 Data Flow: Zero-, One-, Two- or Three-Address
Design ............................................ 646
9.2.3 Register File and Memory Architecture ............. 652
9.2.4 Operation Support ................................. 656
9.2.5 Next Operation Location ........................... 659
9.3 Software Tools ........................................... 660
9.3.1 Lexical Analysis .................................. 661
9.3.2 Parser Development ................................ 672
9.4 FPGA Microprocessor Cores ................................ 682
9.4.1 Hardcore Microprocessors .......................... 683
9.4.2 Softcore Microprocessors .......................... 689
9.5 Case Studies ............................................. 700
9.5.1 T-RISC Stack Microprocessors ...................... 700
9.5.2 LISA Wavelet Processor Design ..................... 706
9.5.3 Nios Custom Instruction Design .................... 721
Exercises ................................................ 728
10 Image and Video Processing ................................ 739
10.1 Overview on Image and Video Processing ................... 740
10.1.1 Image Format ...................................... 741
10.1.2 Basic Image Processing Operation .................. 746
10.2 Case Study 1: Edge Detection in HDL ...................... 748
10.2.1 2D HDL Filter Design .............................. 751
10.2.2 Imaging System Design ............................. 753
10.2.3 Putting the VGA Edge Detection System Together .... 757
10.3 Case Study 2: Median Filter Using an Image Processing
Li-brary ................................................. 769
10.3.1 The Median Filter ................................. 770
10.3.2 Median Filter in HDL .............................. 772
10.3.3 Nios Median Filtering Image Processing System ..... 775
10.3.4 Median Filter in SW ............................... 777
10.4 Motion Detection ......................................... 782
10.4.1 Motion Detection .................................. 782
10.4.2 ME Co-processor Design ............................ 785
10.4.3 Video Compression Standards ....................... 788
Exercises ................................................ 791
Appendix A. Verilog Code of Design Examples ................... 795
Appendix В. Design Examples Synthesis Results ................. 879
Appendix C. VHDL and Verilog Coding Keywords .................. 883
Appendix D. CD-ROM Content .................................... 885
Appendix E. Glossary .......................................... 895
References .................................................... 903
Index ......................................................... 923
|
