Arithmetic Circuits for DSP Applications

PRAMOD KUMAR MEHER is an independent hardware consultant. Previously he was a Senior Research Scientist with the School of Computer Science and Engineering at Nanyang Technological University, Singapore. He has contributed nearly 250 research papers including more than 75 papers in IEEE Transactions in the area of circuits and systems. He has served as Associate Editor for IEEE Transactions on Circuits and Systems and IEEE Transactions on Very Large Scale Integration (VLSI) Systems. Currently, he serves as an Associate Editor for the IEEE Transactions on Circuits and Systems for Video Technology and Journal of Circuits, Systems, and Signal Processing. THANOS STOURAITIS is a Professor of the Electrical and Computer Engineering Department at Khalifa University, UAE. He has previously served on the faculty of the University of Florida, Ohio State University, New York University, University of British Columbia, and University of Patras. He was named an IEEE Fellow for contributions in high performance digital signal processing architectures and computer arithmetic, and is a Past President of the IEEE Circuits & Systems Society.

• Preface xiiiAbout the Editors xvii1 Basic Arithmetic Circuits 1Oscar Gustafsson and Lars Wanhammar1.1 Introduction 11.2 Addition and Subtraction 11.2.1 Ripple-Carry Addition 21.2.2 Bit-Serial Addition and Subtraction 31.2.3 Digit-Serial Addition and Subtraction 41.3 Multiplication 41.3.1 Partial Product Generation 51.3.2 Avoiding Sign-Extension (the Baugh and Wooley Method) 61.3.3 Reducing the Number of Partial Products 61.3.4 Reducing the Number of Columns 81.3.5 Accumulation Structures 81.3.6 Serial/Parallel Multiplication 111.4 Sum-of-Products Circuits 151.4.1 SOP Computation 171.4.2 Linear-Phase FIR Filters 181.4.3 Polynomial Evaluation (Horner's Method) 181.4.4 Multiple-Wordlength SOP 181.5 Squaring 191.5.1 Parallel Squarers 191.5.2 Serial Squarers 211.5.3 Multiplication Through Squaring 231.6 Complex Multiplication 241.6.1 Complex Multiplication Using Real Multipliers 241.6.2 Lifting-Based Complex Multipliers 251.7 Special Functions 261.7.1 Square Root Computation 261.7.2 Polynomial and Piecewise Polynomial Approximations 282 Shift-Add Circuits for Constant Multiplications 33Parmod Kumar Meher, C.-H. Chang, Oscar Gustafsson, A.P. Vinod, and M. Faust2.1 Introduction 332.2 Representation of Constants 362.3 Single Constant Multiplication 402.3.1 Direct Simplification from a Given Number Representation 402.3.2 Simplification by Redundant Signed Digit Representation 412.3.3 Simplification by Adder Graph Approach 412.3.4 State of the Art in SCM 432.4 Algorithms for Multiple Constant Multiplications 432.4.1 MCM for FIR Digital Filter and Basic Considerations 432.4.2 The Adder Graph Approach 452.4.3 Common Subexpression Elimination Algorithms 492.4.4 Difference Algorithms 562.4.5 Reconfigurable and Time-MultiplexedMultiple Constant Multiplications 562.5 Optimization Schemes and Optimal Algorithms 582.5.1 Optimal Subexpression Sharing 582.5.2 Representation Independent Formulations 602.6 Applications 622.6.1 Implementation of FIR Digital Filters and Filter Banks 622.6.2 Implementation of Sinusoidal and Other Linear Transforms 632.6.3 Other Applications 632.7 Pitfalls and Scope for Future Work 642.7.1 Selection of Figure of Merit 642.7.2 Benchmark Suites for Algorithm Evaluation 652.7.3 FPGA-Oriented Design of Algorithms and Architectures 652.8 Conclusions 663 DA-Based Circuits for Inner-Product Computation 77Mahesh Mehendale, Mohit Sharma, and Pramod Kumar Meher3.1 Introduction 773.2 Mathematical Foundation and Concepts 783.3 Techniques for Area Optimization of DA-Based Implementations 813.3.1 Offset Binary Coding 813.3.2 Adder-Based DA 853.3.3 Coefficient Partitioning 853.3.4 Exploiting Coefficient Symmetry 873.3.5 LUT Implementation Optimization 883.3.6 Adder-Based DA Implementation with Single Adder 903.3.7 LUT Optimization for Fixed Coefficients 903.3.8 Inner-Product with Data and Coefficients Represented as Complex Numbers 923.4 Techniques for Performance Optimization of DA-Based Implementations 933.4.1 Two-Bits-at-a-Time (2-BAAT) Access 933.4.2 Coefficient Distribution over Data 933.4.3 RNS-Based Implementation 953.5 Techniques for Low Power and Reconfigurable Realization of DA-Based Implementations 983.5.1 Adder-Based DA with Fixed Coefficients 993.5.2 Eliminating Redundant LUT Accesses and Additions 1003.5.3 Using Zero-Detection to Reduce LUT Accesses and Additions 1023.5.4 Nega-Binary Coding for Reducing Input Toggles and LUT Look-Ups 1033.5.5 Accuracy versus Power Tradeoff 1073.5.6 Reconfigurable DA-Based Implementations 1083.6 Conclusion 1084 Table-Based Circuits for DSP Applications 113Pramod Kumar Meher and Shen-Fu Hsiao4.1 Introduction 1134.2 LUT Design for Implementation of Boolean Function 1154.3 Lookup Table Design for Constant Multiplication 1174.3.1 Lookup Table Optimizations for Constant Multiplication 1174.3.2 Implementation of LUT-Multiplier using APC for L = 5 1224.3.3 Implementation of Optimized LUT using OMS Technique 1234.3.4 Optimized LUT Design for Signed and Unsigned Operands 1244.3.5 Input Operand Decomposition for Large InputWidth 1264.4 Evaluation of Elementary Arithmetic Functions 1274.4.1 Piecewise Polynomial Approximation (PPA) Approach for Function Evaluation 1284.4.2 Table-Addition (TA) Approach for Function Evaluation 1314.5 Applications 1344.5.1 LUT-Based Implementation of Cyclic Convolution and Orthogonal Transforms 1354.5.2 LUT-Based Evaluation of Reciprocals and Division Operation 1364.5.3 LUT-Based Design for Evaluation of Sigmoid Function 1384.6 Summary 1435 CORDIC Circuits 149Pramod Kumar Meher, Javier Valls, Tso-Bing Juang, K. Sridharan, and Koushik Maharatna5.1 Introduction 1495.2 Basic CORDIC Techniques 1515.2.1 The CORDIC Algorithm 1515.2.2 Generalization of the CORDIC Algorithm 1545.2.3 Multidimensional CORDIC 1555.3 Advanced CORDIC Algorithms and Architectures 1565.3.1 High-Radix CORDIC Algorithm 1575.3.2 Angle Recoding Methods 1585.3.3 Hybrid or Coarse-Fine Rotation CORDIC 1615.3.4 Redundant Number-Based CORDIC Implementation 1645.3.5 Pipelined CORDIC Architecture 1665.3.6 Differential CORDIC Algorithm 1675.4 Scaling, Quantization, and Accuracy Issues 1685.4.1 Implementation of Mixed-Scaling Rotation 1685.4.2 Low-Complexity Scaling 1695.4.3 Quantization and Numerical Accuracy 1705.4.4 Area-Delay-Accuracy Trade-off 1705.5 Applications of CORDIC 1725.5.1 Matrix Computation 1725.5.2 Signal Processing and Image Processing Applications 1735.5.3 Applications to Communication 1745.5.4 Applications of CORDIC to Robotics and Graphics 1765.6 Conclusions 1786 RNS-Based Arithmetic Circuits and Applications 186P.V. Ananda Mohan6.1 Introduction 1866.2 Modulo Addition and Subtraction 1896.2.1 Modulo (2n− 1) Adders 1896.2.2 Modulo (2n + 1) Adders 1916.3 Modulo Multiplication and Modulo Squaring 1936.3.1 Multipliers for General Moduli 1946.3.2 Multipliers mod (2n − 1) 1956.3.3 Multipliers mod (2n + 1) 1966.3.4 Modulo Squarers 1996.4 Forward (binary to RNS) Conversion 2006.5 RNS to Binary Conversion 2036.5.1 CRT-Based RNS to Binary Conversion 2036.5.2 Mixed Radix Conversion 2066.5.3 RNS to Binary conversion using New CRT 2076.5.4 RNS to Binary conversion using Core Function 2086.6 Scaling and Base Extension 2106.7 Magnitude Comparison and Sign Detection 2136.8 Error Correction and Detection 2146.9 Applications of RNS 2166.9.1 FIR Filters 2166.9.2 RNS in Cryptography 2186.9.3 RNS in Digital Communication Systems 2257 Logarithmic Number System 237Vassilis Paliouras and Thanos Stouraitis7.1 Introduction 2377.1.1 The Logarithmic Number System 2377.1.2 Organization of the Chapter 2377.2 Basics of LNS Representation 2387.2.1 LNS and Equivalence to Linear Representation 2387.3 Fundamental Arithmetic Operations 2407.3.1 Multiplication, Division, Roots, and Powers 2407.3.2 Addition and Subtraction 2417.4 Forward and Inverse Conversion 2497.5 Complex Arithmetic in LNS 2507.6 LNS Processors 2517.6.1 A VLIW LNS Processor 2527.7 LNS for Low-Power Dissipation 2577.7.1 Impact of LNS Encoding on Signal Activity 2587.7.2 Power Dissipation and LNS Architecture 2617.8 Applications 2657.8.1 Signal Processing and Communications 2657.8.2 Video Processing 2677.8.3 Graphics 2687.9 Conclusions 2688 Redundant Number System-Based Arithmetic Circuits 273G. Jaberipur8.1 Introduction 2738.1.1 Introductory Definitions and Examples 2748.2 Fundamentals of Redundant Number Systems 2788.2.1 Redundant Digit Sets 2788.3 Redundant Number Systems 2808.3.1 Constant Time Addition 2818.3.2 Carry-Save Addition 2838.3.3 Borrow Free Subtraction 2858.4 Basic Arithmetic Circuits for Redundant Number Systems 2878.4.1 Circuit Realization of Carry-Free Adders 2878.4.2 Fast Maximally Redundant Carry-Free Adders 2888.4.3 Carry-Free Addition of Symmetric Maximally Redundant Numbers 2908.4.4 Addition and Subtraction of Stored-Carry Encoded Redundant Operands 2928.5 Binary to Redundant Conversion and the Reverse 2978.5.1 Binary to MRSD Conversion and the Reverse 2978.5.2 Binary to Stored Unibit Conversion and the Reverse 2988.6 Special Arithmetic Circuits for Redundant Number Systems 2998.6.1 Radix-2h MRSD Arithmetic Shifts 2998.6.2 Stored Unibit Arithmetic Shifts 3008.6.3 Apparent Overflow 3038.7 Applications 3038.7.1 Redundant Representation of Partial Products 3058.7.2 Recoding the Multiplier to a Redundant Representation 3058.7.3 Use of Redundant Number Systems in Digit Recurrence Algorithms 3068.7.4 Transcendental Functions and Redundant Number Systems 3068.7.5 RDNS and Fused Multiply-Add Operation 3078.7.6 RDNS and Floating Point Arithmetic 3078.7.7 RDNS and RNS Arithmetic 3088.8 Summary and Further Reading 308Index 313