Arithmetic Circuits for DSP Applications E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 579

Veröffentlichungsjahr: 2017

Beschreibung

A comprehensive guide to the fundamental concepts and development, digital 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). The text covers the key concepts, developments, and applications for 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 arithmetic circuits for digital signal processing and covers the concepts, designs, and applications of different types of arithmetic circuits. 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 applications and reviews in depth the scope of arithmetic circuits and their applications.

Leseprobe

Contents

Cover

Series Page

Title Page

Copyright

Preface

About The Editors

Chapter 1: Basic Arithmetic Circuits

1.1 Introduction

1.2 Addition and Subtraction

1.3 Multiplication

1.4 Sum-of-Products Circuits

1.5 Squaring

1.6 Complex Multiplication

1.7 Special Functions

References

Chapter 2: Shift-Add Circuits for Constant Multiplications

2.1 Introduction

2.2 Representation of Constants

2.3 Single Constant Multiplication

2.4 Algorithms for Multiple Constant Multiplications

2.5 Optimization Schemes and Optimal Algorithms

2.6 Applications

2.7 Pitfalls and Scope for Future Work

2.8 Conclusions

References

Chapter 3: DA-Based Circuits for Inner-Product Computation

3.1 Introduction

3.2 Mathematical Foundation and Concepts

3.3 Techniques for Area Optimization of DA-Based Implementations

3.4 Techniques for Performance Optimization of DA-Based Implementations

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

3.6 Conclusion

References

Chapter 4: Table-Based Circuits for DSP Applications

4.1 Introduction

4.2 LUT Design for Implementation of Boolean Function

4.3 Lookup Table Design for Constant Multiplication

4.4 Evaluation of Elementary Arithmetic Functions

4.5 Applications

4.6 Summary

References

Chapter 5: CORDIC Circuits

5.1 Introduction

5.2 Basic CORDIC Techniques

5.3 Advanced CORDIC Algorithms and Architectures

5.4 Scaling, Quantization, and Accuracy Issues

5.5 Applications of CORDIC

5.6 Conclusions

References

Chapter 6: RNS-Based Arithmetic Circuits and Applications

6.1 Introduction

6.2 Modulo Addition and Subtraction

6.3 Modulo Multiplication and Modulo Squaring

6.4 Forward (binary to RNS) Conversion

6.5 RNS to Binary Conversion

6.6 Scaling and Base Extension

6.7 Magnitude Comparison and Sign Detection

6.8 Error Correction and Detection

6.9 Applications of RNS

References

Chapter 7: Logarithmic Number System

7.1 Introduction

7.2 Basics of LNS Representation

7.3 Fundamental Arithmetic Operations

7.4 Forward and Inverse Conversion

7.5 Complex Arithmetic in LNS

7.6 LNS Processors

7.7 LNS for Low-Power Dissipation

7.8 Applications

7.9 Conclusions

References

Chapter 8: Redundant Number System-Based Arithmetic Circuits

8.1 Introduction

8.2 Fundamentals of Redundant Number Systems

8.3 Redundant Number Systems

8.4 Basic Arithmetic Circuits for Redundant Number Systems

8.5 Binary to Redundant Conversion and the Reverse

8.6 Special Arithmetic Circuits for Redundant Number Systems

8.7 Applications

8.8 Summary and Further Reading

References

Index

End User License Agreement

List of Tables

Table 1.1

Table 1.2

Table 2.1

Table 2.2

Table 3.1

Table 4.1

Table 4.2

Table 4.3

Table 4.4

Table 4.5

Table 4.6

Table 4.7

Table 4.8

Table 5.1

Table 5.2

Table 5.3

Table 5.4

Table 7.1

Table 7.2

Table 7.3

Table 7.4

Table 7.5

Table 7.6

Table 7.7

Table 8.1

Table 8.2

Table 8.3

Table 8.4

Table 8.5

Table 8.6

Table 8.7

Table 8.8

Table 8.9

List of Illustrations

Figure 1.1

Figure 1.2

Figure 1.3

Figure 1.4

Figure 1.5

Figure 1.6

Figure 1.7

Figure 1.8

Figure 1.9

Figure 1.10

Figure 1.11

Figure 1.12

Figure 1.13

Figure 1.14

Figure 1.15

Figure 1.16

Figure 1.17

Figure 1.18

Figure 1.19

Figure 1.20

Figure 1.21

Figure 1.22

Figure 1.23

Figure 1.24

Figure 1.25

Figure 1.26

Figure 1.27

Figure 1.28

Figure 1.29

Figure 2.1

Figure 2.2

Figure 2.3

Figure 2.4

Figure 2.5

Figure 2.6

Figure 2.7

Figure 2.8

Figure 3.1

Figure 3.2

Figure 3.3

Figure 3.4

Figure 3.5

Figure 3.6

Figure 3.7

Figure 3.8

Figure 3.9

Figure 3.10

Figure 3.11

Figure 3.12

Figure 3.13

Figure 3.14

Figure 3.15

Figure 3.16

Figure 3.17

Figure 3.18

Figure 3.19

Figure 3.20

Figure 3.21

Figure 3.22

Figure 3.23

Figure 3.24

Figure 3.25

Figure 3.26

Figure 3.27

Figure 3.28

Figure 4.1

Figure 4.2

Figure 4.3

Figure 4.4

Figure 4.5

Figure 4.6

Figure 4.7

Figure 4.8

Figure 4.9

Figure 4.10

Figure 4.11

Figure 4.12

Figure 4.13

Figure 4.14

Figure 4.15

Figure 4.16

Figure 4.17

Figure 4.18

Figure 4.19

Figure 4.20

Figure 5.1

Figure 5.2

Figure 5.3

Figure 5.4

Figure 5.5

Figure 5.6

Figure 5.7

Figure 5.8

Figure 5.9

Figure 6.1

Figure 6.2

Figure 6.3

Figure 6.4

Figure 6.5

Figure 6.6

Figure 6.7

Figure 6.8

Figure 6.9

Figure 6.10

Figure 7.1

Figure 7.2

Figure 7.3

Figure 7.4

Figure 7.5

Figure 7.6

Figure 7.7

Figure 7.8

Figure 7.9

Figure 7.10

Figure 7.11

Figure 8.1

Figure 8.2

Figure 8.3

Figure 8.4

Figure 8.5

Figure 8.6

Figure 8.7

Figure 8.8

Figure 8.9

Figure 8.10

Figure 8.11

Figure 8.12

Figure 8.13

Figure 8.14

Figure 8.15

Figure 8.16

Figure 8.17

Figure 8.18

Figure 8.19

Figure 8.20

Figure 8.21

Figure 8.22

Figure 8.23

Figure 8.24

Figure 8.25

Figure 8.26

Figure 8.27

Figure 8.28

Figure 8.29

Figure 8.30

Figure 8.31

Guide

Cover

Table of Contents

Begin Reading

Chapter 1

Pages

i

ii

iii

iv

xiii

xiv

xv

xvi

xvii

xviii

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

IEEE Press445 Hoes LanePiscataway, NJ 08854

IEEE Press Editorial BoardTariq Samad, Editor in Chief

Giancarlo Fortino

Xiaoou Li

Ray Perez

Dmitry Goldgof

Andreas Molisch

Linda Shafer

Don Heirman

Saeid Nahavandi

Mohammad Shahidehpour

Ekram Hossain

Jeffrey Nanzer

ZidongWang

Arithmetic Circuits for DSP Applications

Edited by Pramod Kumar Meher and Thanos Stouraitis

Copyright © 2017 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats.Some content that appears in print may not be available in electronic formats.For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data is available.

ISBN:978-1-119-20677-4

Preface

Digital Signal Processing (DSP) has become increasingly indispensable in most of our daily activities. It enables modern communications, image and video creation, storage, processing and transmission, medical instrumentations and diagnostics, automobile functioning, military surveillance and target tracking operations, satellite and aerospace control, DNA analysis, the Internet, energy smart grids, a host of digital consumer products, and myriad other applications.

DSP's algorithms are heavily computation-intensive and many applications are real time, thus imposing very stringent performance requirements on the used devices. Depending on the application, these devices have to be optimized for speed, energy, power consumption, and/or area. Running these applications on the CPUs of general-purpose processors, as was mostly done up until the 1990s, usually does not meet their demanding requirements. It is often the case that dedicated processors, with customized arithmetic units, have to be designed by computer engineers well versed in computer arithmetic options.

Although computer arithmetic is one of the first fields of computer science and engineering, its growth has not stopped over the decades. It has often been demonstrated that it plays a most important role in the performance of digital systems, as it is closely related to the data representation schemes. Especially for DSP systems, its algorithms have a number of interesting characteristics, which can be exploited in the design of the arithmetic circuits, so that they can be implemented more efficiently, in terms of computation time, chip area, and power consumption. As we move well into the era of embedded systems and the Internet of everything, the arithmetic circuits, and particularly the ones for DSP applications, will retain and expand their significance of system on chip designs.

This book aims to give a comprehensive coverage of fundamental concepts and advantages for various classes of arithmetic circuits, their digital implementation schemes, performance considerations, and applications. It comes in the form of an edited volume, as leading researchers in various important classes of arithmetic circuits have presented the relevant state of the art, possible applications, and scope for future research.

Chapter 1 is devoted to circuits used in implementing basic operations, like additions and multiplications. The authors then move on to discussing the realization of more complex operations, such as sums of products, squaring, square roots, and complex multiplications. At the end of this chapter, they present circuits for special functions, as well as polynomial and piecewise polynomial approximations of nonlinear functions.

Multiplication is a common but costly arithmetic operation, in terms of silicon area, computation time, and power consumption. Many real-time applications utilize algorithms involving multiplications by constants. Chapter 2 is devoted to the presentation of the basic techniques for shift-add circuits for multiplications by constants, along with an overview of advanced optimization schemes and a brief sketch of application domains.

Computation of inner products of two vectors, particularly when one of the vectors is fixed and known a priori, is frequently encountered in DSP applications. Chapter 3 focuses on the use of distributed arithmetic (DA) as a technique for the multiplier-less implementation of inner products and their application in a host of different DSP operations and transforms. As DA is primarily a lookup table technique, it is also appropriate for FPGA implementations.

Chapter 4 continues with the discussion of lookup table (LUT)-based techniques, especially for the implementation of operations such as multiplications and divisions by a constant, exponentiations of constants, inversion, evaluation of squares and square roots of integers, as well as sinusoidal functions, sigmoid function, logarithms, antilogarithms. The chapter provides an overview of the key concepts, important developments, implementations, and applications of some popular LUT-based systems.

The calculation of trigonometric, hyperbolic, and logarithmic functions, real and complex multiplications, division, 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 is the focus of Chapter 5. It presents the COordinate Rotation DIgital Computer (CORDIC) technique, which has been utilized for applications in diverse areas, such as signal and image processing, communication systems, and robotics and 3D graphics, in addition to general scientific and technical computations.

Chapter 6 considers the use of the Residue Number Systems (RNS) as a means of data representation and its impact on the design of arithmetic circuits. The various design considerations, such as choice of modulus sets, algorithms for converting binary numbers to RNS and vice versa, multiplication, scaling, sign detection, and base extension operations are reviewed. Special attention is given to power-of-two-related modulus sets, in view of their computational advantages. Some applications of RNS in signal processing, communication systems, and cryptography are presented, in order to highlight the possible advantages as compared to conventional arithmetic-based implementations.

The representation of data as logarithms has been long used, as a means to simplify particular arithmetic operations and utilize improved numerical properties, even before the modern digital computer era. The Logarithmic Number System (LNS) is a formalization of the logarithmic representation of the data in a digital system and it can be conceived as a generalization of the floating-point representation. It is the focus of Chapter 7, which discusses the implementations of basic operations in logarithmic arithmetic circuits, presents forward and inverse conversion schemes, the implementation of complex arithmetic, and finally discusses the impact of logarithmic arithmetic on power dissipation and presents several applications amenable to LNS processing.

Chapter 8 deals with the implementation of arithmetic when other redundant number systems (RDNS) are used for data representation. For a radix-r RDNS, each digit can assume more than γ values. The extra digit values allow for constant time and carry-free addition and subtraction. In this chapter, RDNS is formally defined, its carry-free property is analyzed, and the algorithms and circuits for the corresponding add, subtract, and special functions are provided.

The primary readership for this edited volume will be senior undergraduate and graduate students in computer science, computer engineering, and electrical and electronics engineering. It may be used as a textbook for courses on embedded systems, signal processing, and IC design, as well as a reference book. Practicing engineers or researchers in academia will also find it very handy and useful. The prerequisites required for a complete understanding of the book include fundamentals of digital logic and a basic ability in mathematics.

The editors would like to thank all chapter authors for their valuable contributions.

Nanyang Technological University Singapore

Pramod K. Meher

Khalifa University UAE University of Patras Greece

Thanos Stouraitis

About The Editors

Pramod Kumar Meher received the B.Sc. (Honours) and M.Sc. degrees in physics, and the Ph.D. degree in science from Sambalpur University, India, in 1976, 1978, and 1996, respectively. Currently, he is a Senior Research Scientist with Nanyang Technological University, Singapore. Previously, he was a Professor of Computer Applications with Utkal University, India, from 1997 to 2002, and a Reader in electronics with Berhampur University, India, from 1993 to 1997. His research interest includes design of dedicated and reconfigurable architectures for computation-intensive algorithms pertaining to signal, image and video processing, communication, bioinformatics, and intelligent computing. He has contributed more than 200 technical papers to various reputed journals and conference proceedings. Dr Meher has served as a speaker for the Distinguished Lecturer Program (DLP) of IEEE Circuits Systems Society during 2011 and 2012, Associate Editor of the IEEE Transactions on Circuits And Systems-II: Express Briefs during 2008–2011, the IEEE Transactions on Circuits And Systems-I: Regular Papers during 2012–2013, and the IEEE Transactions on Very Large Scale Integration (VLSI) Systems during 2009–2014. Currently, he is serving as Associate Editor for the IEEE Transactions on Circuits and Systems for Video Technology and Journal of Circuits, Systems, and Signal Processing. Dr Meher is a Senior Member of IEEE and Fellow of the Institution of Electronics and Telecommunication Engineers, India. He was the recipient of the Samanta Chandrasekhar Award for excellence in research in engineering and technology for 1999.

Thanos Stouraitis, an IEEE Fellow for his “contributions in digital signal processing architectures and computer arithmetic,” is currently Professor and Chair of the ECE department of Khalifa University, UAE (on leave from the University of Patras, Greece). He has served on the faculties of University of Florida, Ohio State University, Polytechnic University (NYU), and University of British Columbia. His research interests include cryptography, computer arithmetic, signal/image processing systems, and optimal processor design. He has coauthored over 180 technical papers, holds one patent on DSP processor design, and has authored several book chapters and books. He has been serving as an Editor or/and Guest Editor for numerous technical journals. He served as General Chair, TPC Chair, and Symposium Chair for many international conferences, like ISCAS, SiPS, and ICECS. He received the IEEE Circuits and Systems Society Guillemin-Cauer Award. He has served IEEE in many ways, including as CAS Society President, 2012–2013.