Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII Preface to Second Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XI Preface to Third Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIII 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 FPGA and Programmable Signal Processors . . . . . . . . . 12 1.4 Design Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.1 FPGA Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4.2 The Altera EP2C35F672C6 . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4.3 Case Study: Frequency Synthesizer . . . . . . . . . . . . . . . . . 29 1.4.4 Design with Intellectual Property Cores . . . . . . . . . . . . . 35 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2. Computer Arithmetic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2 Number Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.1 Fixed-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.2 Unconventional Fixed-Point Numbers . . . . . . . . . . . . . . . 57 2.2.3 Floating-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.3 Binary Adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.3.1 Pipelined Adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.3.2 Modulo Adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.4 Binary Multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.4.1 Multiplier Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.5 Binary Dividers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2.5.1 Linear Convergence Division Algorithms . . . . . . . . . . . . 93 2.5.2 Fast Divider Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 2.5.3 Array Divider . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 2.6 Floating-Point Arithmetic Implementation . . . . . . . . . . . . . . . . . 104 2.6.1 Fixed-point to Floating-Point Format Conversion . . . . . 105 2.6.2 Floating-Point to Fixed-Point Format Conversion. . . . . 106 2.6.3 Floating-Point Multiplication . . . . . . . . . . . . . . . . . . . . . . 107 2.6.4 Floating-Point Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 2.6.5 Floating-Point Division . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 2.6.6 Floating-Point Reciprocal . . . . . . . . . . . . . . . . . . . . . . . . . 112 2.6.7 Floating-Point Synthesis Results . . . . . . . . . . . . . . . . . . . 114 2.7 Multiply-Accumulator (MAC) and Sum of Product (SOP) . . 114 2.7.1 Distributed Arithmetic Fundamentals . . . . . . . . . . . . . . . 115 2.7.2 Signed DA Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 2.7.3 Modified DA Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 2.8 Computation of Special Functions Using CORDIC . . . . . . . . . . 120 2.8.1 CORDIC Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 2.9 Computation of Special Functions using MAC Calls . . . . . . . . . 130 2.9.1 Chebyshev Approximations . . . . . . . . . . . . . . . . . . . . . . . . 131 2.9.2 Trigonometric Function Approximation . . . . . . . . . . . . . 132 2.9.3 Exponential and Logarithmic Function Approximation 141 2.9.4 Square Root Function Approximation . . . . . . . . . . . . . . . 148 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 3. Finite Impulse Response (FIR) Digital Filters . . . . . . . . . . . . 165 3.1 Digital Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 3.2 FIR Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 3.2.1 FIR Filter with Transposed Structure . . . . . . . . . . . . . . . 167 3.2.2 Symmetry in FIR Filters . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.2.3 Linear-phase FIR Filters . . . . . . . . . . . . . . . . . . . . . . . . . . 171 3.3 Designing FIR Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.3.1 Direct Window Design Method. . . . . . . . . . . . . . . . . . . . . 173 3.3.2 Equiripple Design Method . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.4 Constant Coefficient FIR Design . . . . . . . . . . . . . . . . . . . . . . . . . 177 3.4.1 Direct FIR Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 3.4.2 FIR Filter with Transposed Structure . . . . . . . . . . . . . . . 182 3.4.3 FIR Filters Using Distributed Arithmetic . . . . . . . . . . . . 189 3.4.4 IP Core FIR Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . 204 3.4.5 Comparison of DA- and RAG-Based FIR Filters . . . . . 207 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 4. Infinite Impulse Response (IIR) Digital Filters . . . . . . . . . . . 215 4.1 IIR Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 4.2 IIR Coefficient Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 4.2.1 Summary of Important IIR Design Attributes . . . . . . . . 223 4.3 IIR Filter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 4.3.1 Finite Wordlength Effects . . . . . . . . . . . . . . . . . . . . . . . . . 228 4.3.2 Optimization of the Filter Gain Factor . . . . . . . . . . . . . . 229 4.4 Fast IIR Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 4.4.1 Time-domain Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . 230 4.4.2 Clustered and Scattered Look-Ahead Pipelining . . . . . . 233 4.4.3 IIR Decimator Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 4.4.4 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 4.4.5 IIR Design Using RNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 5. Multirate Signal Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 5.1 Decimation and Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 5.1.1 Noble Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 5.1.2 Sampling Rate Conversion by Rational Factor . . . . . . . . 248 5.2 Polyphase Decomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.2.1 Recursive IIR Decimator . . . . . . . . . . . . . . . . . . . . . . . . . . 254 5.2.2 Fast-running FIR Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 5.3 Hogenauer CIC Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 5.3.1 Single-Stage CIC Case Study . . . . . . . . . . . . . . . . . . . . . . 257 5.3.2 Multistage CIC Filter Theory . . . . . . . . . . . . . . . . . . . . . . 259 5.3.3 Amplitude and Aliasing Distortion . . . . . . . . . . . . . . . . . 264 5.3.4 Hogenauer Pruning Theory . . . . . . . . . . . . . . . . . . . . . . . . 266 5.3.5 CIC RNS Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 5.4 Multistage Decimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 5.4.1 Multistage Decimator Design Using Goodman–Carey Half-band Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 5.5 Frequency-Sampling Filters as Bandpass Decimators . . . . . . . . 277 5.6 Design of Arbitrary Sampling Rate Converters . . . . . . . . . . . . . 280 5.6.1 Fractional Delay Rate Change . . . . . . . . . . . . . . . . . . . . . 284 5.6.2 Polynomial Fractional Delay Design . . . . . . . . . . . . . . . . 290 5.6.3 B-Spline-Based Fractional Rate Changer . . . . . . . . . . . . 296 5.6.4 MOMS Fractional Rate Changer . . . . . . . . . . . . . . . . . . . 301 5.7 Filter Banks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 5.7.1 Uniform DFT Filter Bank . . . . . . . . . . . . . . . . . . . . . . . . . 309 5.7.2 Two-channel Filter Banks . . . . . . . . . . . . . . . . . . . . . . . . . 313 5.8 Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 5.8.1 The Discrete Wavelet Transformation . . . . . . . . . . . . . . . 332 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 6. Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 6.1 The Discrete Fourier Transform Algorithms . . . . . . . . . . . . . . . . 344 6.1.1 Fourier Transform Approximations Using the DFT . . . 344 6.1.2 Properties of the DFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 6.1.3 The Goertzel Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 349 6.1.4 The Bluestein Chirp-z Transform. . . . . . . . . . . . . . . . . . . 350 6.1.5 The Rader Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 6.1.6 The Winograd DFT Algorithm. . . . . . . . . . . . . . . . . . . . . 359 6.2 The Fast Fourier Transform (FFT) Algorithms . . . . . . . . . . . . . 361 6.2.1 The Cooley–Tukey FFT Algorithm . . . . . . . . . . . . . . . . . 363 6.2.2 The Good–Thomas FFT Algorithm. . . . . . . . . . . . . . . . . 373 6.2.3 The Winograd FFT Algorithm . . . . . . . . . . . . . . . . . . . . . 375 6.2.4 Comparison of DFT and FFT Algorithms . . . . . . . . . . . 379 6.2.5 IP Core FFT Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 6.3 Fourier-Related Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 6.3.1 Computing the DCT Using the DFT. . . . . . . . . . . . . . . . 387 6.3.2 Fast Direct DCT Implementation . . . . . . . . . . . . . . . . . . 388 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 7. Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 7.1 Rectangular and Number Theoretic Transforms (NTTs) . . . . . 401 7.1.1 Arithmetic Modulo 2b ± 1 . . . . . . . . . . . . . . . . . . . . . . . . . 403 7.1.2 Efficient Convolutions Using NTTs . . . . . . . . . . . . . . . . . 405 7.1.3 Fast Convolution Using NTTs . . . . . . . . . . . . . . . . . . . . . 405 7.1.4 Multidimensional Index Maps . . . . . . . . . . . . . . . . . . . . . . 409 7.1.5 Computing the DFT Matrix with NTTs . . . . . . . . . . . . . 411 7.1.6 Index Maps for NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 7.1.7 Using Rectangular Transforms to Compute the DFT . . 416 7.2 Error Control and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . 418 7.2.1 Basic Concepts from Coding Theory . . . . . . . . . . . . . . . . 419 7.2.2 Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 7.2.3 Convolutional Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 7.2.4 Cryptography Algorithms for FPGAs . . . . . . . . . . . . . . . 436 7.3 Modulation and Demodulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 7.3.1 Basic Modulation Concepts . . . . . . . . . . . . . . . . . . . . . . . . 453 7.3.2 Incoherent Demodulation . . . . . . . . . . . . . . . . . . . . . . . . . 457 7.3.3 Coherent Demodulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 8. Adaptive Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 8.1 Application of Adaptive Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 8.1.1 Interference Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . 478 8.1.2 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 8.1.3 Inverse Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 8.1.4 Identification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480 8.2 Optimum Estimation Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 481 8.2.1 The Optimum Wiener Estimation . . . . . . . . . . . . . . . . . . 482 8.3 The Widrow–Hoff Least Mean Square Algorithm . . . . . . . . . . . 486 8.3.1 Learning Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 8.3.2 Normalized LMS (NLMS) . . . . . . . . . . . . . . . . . . . . . . . . . 496 8.4 Transform Domain LMS Algorithms . . . . . . . . . . . . . . . . . . . . . . 498 8.4.1 Fast-Convolution Techniques . . . . . . . . . . . . . . . . . . . . . . . 498 8.4.2 Using Orthogonal Transforms . . . . . . . . . . . . . . . . . . . . . . 500 8.5 Implementation of the LMS Algorithm . . . . . . . . . . . . . . . . . . . . 503 8.5.1 Quantization Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504 8.5.2 FPGA Design of the LMS Algorithm . . . . . . . . . . . . . . . 504 8.5.3 Pipelined LMS Filters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 8.5.4 Transposed Form LMS Filter . . . . . . . . . . . . . . . . . . . . . . 510 8.5.5 Design of DLMS Algorithms . . . . . . . . . . . . . . . . . . . . . . . 511 8.5.6 LMS Designs using SIGNUM Function . . . . . . . . . . . . . . 515 8.6 Recursive Least Square Algorithms . . . . . . . . . . . . . . . . . . . . . . . 518 8.6.1 RLS with Finite Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 521 8.6.2 Fast RLS Kalman Implementation . . . . . . . . . . . . . . . . . . 524 8.6.3 The Fast a Posteriori Kalman RLS Algorithm. . . . . . . . 529 8.7 Comparison of LMS and RLS Parameters . . . . . . . . . . . . . . . . . 530 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 9. Microprocessor Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 9.1 History of Microprocessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 9.1.1 Brief History of General-Purpose Microprocessors . . . . 538 9.1.2 Brief History of RISC Microprocessors . . . . . . . . . . . . . . 540 9.1.3 Brief History of PDSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 9.2 Instruction Set Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 9.2.1 Addressing Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 9.2.2 Data Flow: Zero-,One-, Two- or Three-Address Design 552 9.2.3 Register File and Memory Architecture . . . . . . . . . . . . . 558 9.2.4 Operation Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562 9.2.5 Next Operation Location . . . . . . . . . . . . . . . . . . . . . . . . . . 565 9.3 Software Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566 9.3.1 Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 9.3.2 Parser Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 9.4 FPGA Microprocessor Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 9.4.1 Hardcore Microprocessors . . . . . . . . . . . . . . . . . . . . . . . . . 589 9.4.2 Softcore Microprocessors . . . . . . . . . . . . . . . . . . . . . . . . . . 594 9.5 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605 9.5.1 T-RISC Stack Microprocessors . . . . . . . . . . . . . . . . . . . . . 605 9.5.2 LISA Wavelet Processor Design . . . . . . . . . . . . . . . . . . . . 610 9.5.3 Nios FFT Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 A. Verilog Source Code 2001 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661 B. HDL" onclick="tagshow(event)" class="t_tag">VHDL and Verilog Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729 B.1 List of Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731 B.2 Library of Parameterized Modules (LPM) . . . . . . . . . . . . . . . . . 733 B.2.1 The Parameterized Flip-Flop Megafunction (lpm ff) . . 733 B.2.2 The Adder/Subtractor Megafunction . . . . . . . . . . . . . . . 737 B.2.3 The Parameterized Multiplier Megafunction (lpm mult) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741 B.2.4 The Parameterized ROM Megafunction (lpm rom) . . . 746 B.2.5 The Parameterized Divider Megafunction (lpm divide) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749 B.2.6 The Parameterized RAM Megafunction (lpm ram dq) 751 C. Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755 D. CD-ROM File: “1readme.ps” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769