A comprehensive guide to the fundamental concepts, designs, and implementation schemes, performance considerations, and applications of arithmetic circuits for DSP Arithmetic Circuits for DSP Applications is a complete resource on arithmetic circuits for digital signal processing (DSP). It covers the key concepts, designs and developments of different types of arithmetic circuits, which can be used for improving the efficiency of implementation of a multitude of DSP applications. Each chapter includes various applications of the respective class of arithmetic circuits along with information on the future scope of research. Written for students, engineers, and researchers in electrical and computer engineering, this comprehensive text offers a clear understanding of different types of arithmetic circuits used for digital signal processing applications. The text includes contributions from noted researchers on a wide range of topics, including a review of circuits used in implementing basic operations like additions and multiplications; distributed arithmetic as a technique for the multiplier-less implementation of inner products for DSP applications; discussions on look up table-based techniques and their key applications; CORDIC circuits for calculation of trigonometric, hyperbolic and logarithmic functions; real and complex multiplications, division, and square-root; solution of linear systems; eigenvalue estimation; singular value decomposition; QR factorization and many other functions through the use of simple shift-add operations; and much more. This book serves as a comprehensive resource, which describes the arithmetic circuits as fundamental building blocks for state-of-the-art DSP and reviews in - depth the scope of their 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.

Inhalt

Preface xiii

About the Editors xvii

1 Basic Arithmetic Circuits 1

Oscar Gustafsson and Lars Wanhammar

1.1 Introduction 1

1.2 Addition and Subtraction 1

1.2.1 Ripple-Carry Addition 2

1.2.2 Bit-Serial Addition and Subtraction 3

1.2.3 Digit-Serial Addition and Subtraction 4

1.3 Multiplication 4

1.3.1 Partial Product Generation 5

1.3.2 Avoiding Sign-Extension (the Baugh and Wooley Method) 6

1.3.3 Reducing the Number of Partial Products 6

1.3.4 Reducing the Number of Columns 8

1.3.5 Accumulation Structures 8

1.3.6 Serial/Parallel Multiplication 11

1.4 Sum-of-Products Circuits 15

1.4.1 SOP Computation 17

1.4.2 Linear-Phase FIR Filters 18

1.4.3 Polynomial Evaluation (Horner's Method) 18

1.4.4 Multiple-Wordlength SOP 18

1.5 Squaring 19

1.5.1 Parallel Squarers 19

1.5.2 Serial Squarers 21

1.5.3 Multiplication Through Squaring 23

1.6 Complex Multiplication 24

1.6.1 Complex Multiplication Using Real Multipliers 24

1.6.2 Lifting-Based Complex Multipliers 25

1.7 Special Functions 26

1.7.1 Square Root Computation 26

1.7.2 Polynomial and Piecewise Polynomial Approximations 28

2 Shift-Add Circuits for Constant Multiplications 33

Parmod Kumar Meher, C.-H. Chang, Oscar Gustafsson, A.P. Vinod, and M. Faust

2.1 Introduction 33

2.2 Representation of Constants 36

2.3 Single Constant Multiplication 40

2.3.1 Direct Simplification from a Given Number Representation 40

2.3.2 Simplification by Redundant Signed Digit Representation 41

2.3.3 Simplification by Adder Graph Approach 41

2.3.4 State of the Art in SCM 43

2.4 Algorithms for Multiple Constant Multiplications 43

2.4.1 MCM for FIR Digital Filter and Basic Considerations 43

2.4.2 The Adder Graph Approach 45

2.4.3 Common Subexpression Elimination Algorithms 49

2.4.4 Difference Algorithms 56

2.4.5 Reconfigurable and Time-MultiplexedMultiple Constant Multiplications 56

2.5 Optimization Schemes and Optimal Algorithms 58

2.5.1 Optimal Subexpression Sharing 58

2.5.2 Representation Independent Formulations 60

2.6 Applications 62

2.6.1 Implementation of FIR Digital Filters and Filter Banks 62

2.6.2 Implementation of Sinusoidal and Other Linear Transforms 63

2.6.3 Other Applications 63

2.7 Pitfalls and Scope for Future Work 64

2.7.1 Selection of Figure of Merit 64

2.7.2 Benchmark Suites for Algorithm Evaluation 65

2.7.3 FPGA-Oriented Design of Algorithms and Architectures 65

2.8 Conclusions 66

3 DA-Based Circuits for Inner-Product Computation 77

Mahesh Mehendale, Mohit Sharma, and Pramod Kumar Meher

3.1 Introduction 77

3.2 Mathematical Foundation and Concepts 78

3.3 Techniques for Area Optimization of DA-Based Implementations 81

3.3.1 Offset Binary Coding 81

3.3.2 Adder-Based DA 85

3.3.3 Coefficient Partitioning 85

3.3.4 Exploiting Coefficient Symmetry 87

3.3.5 LUT Implementation Optimization 88

3.3.6 Adder-Based DA Implementation with Single Adder 90

3.3.7 LUT Optimization for Fixed Coefficients 90

3.3.8 Inner-Product with Data and Coefficients Represented as Complex Numbers 92

3.4 Techniques for Performance Optimization of DA-Based Implementations 93

3.4.1 Two-Bits-at-a-Time (2-BAAT) Access 93

3.4.2 Coefficient Distribution over Data 93

3.4.3 RNS-Based Implementation 95

3.5 Techniques for Low Power and Reconfigurable Realization of DA-Based Implementations 98

3.5.1 Adder-Based DA with Fixed Coefficients 99

3.5.2 Eliminating Redundant LUT Accesses and Additions 100

3.5.3 Using Zero-Detection to Reduce LUT Access...