Synthesis of Arithmetic Circuits

SYNTHESIS OF

ARITHMETIC CIRCUITS

FPGA, ASIC, and Embedded Systems

JEAN-PIERRE DESCHAMPS

University Rovira i Virgili

GÉRY JEAN ANTOINE BIOUL

National University of the Center of the Province of Buenos Aires

GUSTAVO D. SUTTER

University Autonoma of Madrid

A JOHN WILEY & SONS, INC., PUBLICATION

SYNTHESIS OF

ARITHMETIC CIRCUITS

SYNTHESIS OF

ARITHMETIC CIRCUITS

FPGA, ASIC, and Embedded Systems

JEAN-PIERRE DESCHAMPS

University Rovira i Virgili

GÉRY JEAN ANTOINE BIOUL

National University of the Center of the Province of Buenos Aires

GUSTAVO D. SUTTER

University Autonoma of Madrid

A JOHN WILEY & SONS, INC., PUBLICATION

#

Copyright 2006 by John Wiley & Sons, 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, 978-750-8400, fax 978-646-8600, 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, (201) 748-6011, fax (201) 748-6008

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 please contact our Customer Care Department

within the U.S. at 877-762-2974, outside the U.S. at 317-572-3993 or fax 317-572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print,

however, may not be available in electronic format.

Library of Congress Cataloging-in-Publication Data:

Deschamps, Jean-Pierre, 1945-

Synthesis of arithmetic circuits: FPGA, ASIC and embedded systems/Jean-Pierre Deschamps, Gery

Jean Antoine Bioul, Gustavo D. Sutter.

p. cm.

ISBN-13 978-0471-68783-2 (cloth)

ISBN-10 0-471-68783-9 (cloth)

1. Computer arithmetic and logic units. 2. Digital electronics. 3. Embedded computer systems.

I. Bioul, Gery Jean Antoine. II. Sutter, Gustavo D. III. Title.

TK7895.A65D47 2006

621.39’5 - - dc22 2005003237

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1 To Marc

CONTENTS

Preface xvii

About the Authors xix

1 Introduction 1

1.1 Number Representation, 1

1.2 Algorithms, 2

1.3 Hardware Platforms, 2

1.4 Hardware – Software Partitioning, 3

1.5 Software Generation, 3

1.6 Synthesis, 3

1.7 A First Example, 3

1.7.1 Specification, 3

1.7.2 Number Representation, 6

1.7.3 Algorithms, 6

1.7.4 Hardware Platform, 8

1.7.5 Hardware – Software Partitioning, 8

1.7.6 Program Generation, 9

1.7.7 Synthesis, 10

1.7.8 Prototype, 12

1.8 Bibliography, 14 vii

CONTENTS

viii

2 Mathematical Background 15

2.1 Number Theory, 15

2.1.1 Basic Definitions, 15

2.1.2 Euclidean Algorithms, 17

2.1.3 Congruences, 19

2.2 Algebra, 25

2.2.1 Groups, 25

2.2.2 Rings, 27

2.2.3 Fields, 27

2.2.4 Polynomial Rings, 27

2.2.5 Congruences of Polynomial, 32

2.3 Function Approximation, 35

2.4 Bibliography, 36

3 Number Representation 39

3.1 Natural Numbers, 39

3.1.1 Weighted Systems, 39

3.1.2 Residue Number System, 42

3.2 Integers, 42

3.2.1 Sign-Magnitude Representation, 42

3.2.2 Excess-E Representation, 43

B’s

3.2.3 Complement Representation, 44

3.2.4 Booth’s Encoding, 47

3.3 Real Numbers, 51

3.4 Bibliography, 54

4 Arithmetic Operations: Addition and Subtraction 55

4.1 Addition of Natural Numbers, 55

4.1.1 Basic Algorithm, 55

4.1.2 Faster Algorithms, 57

4.1.3 Long-Operand Addition, 66

4.1.4 Multioperand Addition, 67

4.1.5 Long-Multioperand Addition, 70

4.2 Subtraction of Natural Numbers, 71

4.3 Integers, 71

B’s

4.3.1 Complement Addition, 71

B’s

4.3.2 Complement Sign Change, 72

B’s

4.3.3 Complement Subtraction, 74

CONTENTS ix

B’s

4.3.4 Complement Overflow Detection, 74

4.3.5 Excess-E Addition and Subtraction, 78

4.3.6 Sign – Magnitude Addition and Subtraction, 79

4.4 Bibliography, 80

5 Arithmetic Operations: Multiplication 81

5.1 Natural Numbers Multiplication, 82

5.1.1 Introduction, 82

5.1.2 Shift and Add Algorithms, 83

5.1.2.1 Shift and Add 1, 83

5.1.2.2 Shift and Add 2, 84

5.1.2.3 Extended Shift and Add Algorithm:

XY þ C þ D, 86

5.1.2.4 Cellular Shift and Add, 86

5.1.3 Long-Operand Algorithm, 90

5.2 Integers, 91

B’s

5.2.1 Complement Multiplication, 91

nþm

B B’s

5.2.1.1 Mod Complement Multiplication, 92

5.2.1.2 Signed Shift and Add, 93

B’s

5.2.1.3 Postcorrection Complement Multiplication, 93

5.2.2 Postcorrection 2’s Complement Multiplication, 96

5.2.3 Booth Multiplication for Binary Numbers, 97

5.2.3.1 Booth-r Algorithms, 97

Per Gelosia

5.2.3.2 Signed-Digit Algorithm, 98

5.2.4 Booth Multiplication for Base-B Numbers

B),

(Booth-r Algorithm in Base 102

5.3 Squaring, 104

5.3.1 Base-B Squaring, 104

5.3.1.1 Cellular Carry –Save Squaring Algorithm, 104

5.3.2 Base-2 Squaring, 106

5.4 Bibliography, 107

6 Arithmetic Operations: Division 109

6.1 Natural Numbers, 110

6.2 Integers, 117

6.2.1 General Algorithm, 117

6.2.2 Restoring Division Algorithm, 121

6.2.3 Base-2 Nonrestoring Division Algorithm, 121

6.2.4 SRT Radix-2 Division, 126

6.2.5 SRT Radix-2 Division with Stored-Carry Encoding, 131

P– D

6.2.6 Diagram, 139 CONTENTS

x 6.2.7 SRT-4 Division, 142

6.2.8 Base-B Nonrestoring Division Algorithm, 148

6.3 Convergence (Functional Iteration) Algorithms, 155

6.3.1 Introduction, 155

6.3.2 Newton –Raphson Iteration Technique, 155

6.3.3 MacLaurin Expansion—Goldschmidt’s Algorithm, 159

6.4 Bibliography, 161

7 Other Arithmetic Operations 165

7.1 Base Conversion, 165

7.2 Residue Number System Conversion, 173

7.2.1 Introduction, 173

7.2.2 Base-B to RNS Conversion, 173

7.2.3 RNS to Base-B Conversion, 177

7.3 Logarithmic, Exponential, and Trigonometric Functions, 180

7.3.1 Taylor – MacLaurin Series, 181

7.3.2 Polynomial Approximation, 183

7.3.3 Logarithm and Exponential Functions Approximation

by Convergence Methods, 184

7.3.3.1 Logarithm Function Approximation by

Multiplicative Normalization, 184

7.3.3.2 Exponential Function Approximation by

Additive Normalization, 188

7.3.4 Trigonometric Functions—CORDIC Algorithms, 194

7.4 Square Rooting, 198

7.4.1 Digit Recurrence Algorithm—Base-B Integers, 198

7.4.2 Restoring Binary Shift-and-Subtract Square Rooting

Algorithm, 202

7.4.3 Nonrestoring Binary Add-and-Subtract Square Rooting

Algorithm, 204

7.4.4 Convergence Method—Newton –Raphson, 208

7.5 Bibliography, 208

8 Finite Field Operations 211

Z

8.1 Operations in , 211

m

8.1.1 Addition, 212

8.1.2 Subtraction, 213

8.1.3 Multiplication, 213

8.1.3.1 Multiply and Reduce, 214

8.1.3.2 Modified Shift-and-Add Algorithm, 214

CONTENTS xi

8.1.3.3 Montgomery Multiplication, 216

8.1.3.4 Specific Ring, 220

8.1.4 Exponentiation, 221

GF(p),

8.2 Operations in 222

Z

8.3 Operations in [x]/f (x), 224

p

8.3.1 Addition and Subtraction, 224

8.3.2 Multiplication, 225

n

GF(p

8.4 Operations in ), 228

8.5 Bibliography, 236 f

Appendix 8.1 Computation of , 236

ki

9 Hardware Platforms 239

9.1 Design Methods for Electronic Systems, 239

9.1.1 Basic Blocks of Integrated Systems, 240

9.1.2 Recurring Topics in Electronic Design, 241

9.1.2.1 Design Challenge: Optimizing

Design Metrics, 241

9.1.2.2 Cost in Integrated Circuits, 242

9.1.2.3 Moore’s Law, 243

9.1.2.4 Time-to-Market, 243

9.1.2.5 Performance Metric, 244

9.1.2.6 The Power Dimension, 245

9.2 Instruction Set Processors, 245

9.2.1 Microprocessors, 247

9.2.2 Microcontrollers, 248

9.2.3 Embedded Processors Everywhere, 248

9.2.4 Digital Signal Processors, 249

9.2.5 Application-Specific Instruction Set Processors, 250

9.2.6 Programming Instruction Set Processors, 251

9.3 ASIC Designs, 252

9.3.1 Full-Custom ASIC, 252

9.3.2 Semicustom ASIC, 253

9.3.2.1 Gate-Array ASIC, 253

9.3.2.2 Standard-Cell-Based ASIC, 254

9.3.3 Design Flow in ASIC, 255

9.4 Programmable Logic, 256

9.4.1 Programmable Logic Devices (PLDs), 256

9.4.2 Field Programmable Gate Array (FPGA), 258

9.4.2.1 Why FPGA? A Short Historical Survey, 258

9.4.2.2 Basic FPGA Concepts, 258 CONTENTS

xii TM

9.4.3 Xilinx Specifics, 260

9.4.3.1 Configurable Logic Blocks (CLBs), 262

9.4.3.2 Input/Output Blocks (IOBs), 262

9.4.3.3 RAM Blocks, 262

9.4.3.4 Programmable Routing, 264

9.4.3.5 Arithmetic Resources in Xilinx FPGAs, 264

9.4.4 FPGA Generic Design Flow, 264

9.5 Hardware Description Languages (HDLs), 267

9.5.1 Today’s and Tomorrow’s HDLs, 267

9.6 Further Readings, 268

9.7 Bibliography, 268

10 Circuit Synthesis: General Principles 271

10.1 Resources, 272

10.2 Precedence Relation and Scheduling, 277

10.3 Pipeline, 281

10.4 Self-Timed Circuits, 282

10.5 Bibliography, 288

11 Adders and Subtractors 289

11.1 Natural Numbers, 289

11.1.1 Basic Adder (Ripple-Carry Adder), 289

11.1.2 Carry-Chain Adder, 292

11.1.3 Carry-Skip Adder, 294

11.1.4 Optimization of Carry-Skip Adders, 298

s

11.1.5 Base-B Adder, 301

11.1.6 Carry-Select Adder, 303

11.1.7 Optimization of Carry-Select Adders, 307

11.1.8 Carry-Lookahead Adders (CLAs), 310

11.1.9 Prefix Adders, 318

11.1.10 FPGA Implementation of Adders, 322

11.1.10.1 Carry-Chain Adders, 322

11.1.10.2 Carry-Skip Adders, 323

11.1.10.3 Experimental Results, 326

11.1.11 Long-Operand Adders, 327

11.1.12 Multioperand Adders, 328

11.1.12.1 Sequential Multioperand Adders, 328

11.1.12.2 Combinational Multioperand Adders, 330

CONTENTS xiii

11.1.12.3 Carry-Save Adders, 333

11.1.12.4 Parallel Counters, 337

11.1.13 Subtractors and Adder-Subtractors, 344

11.1.14 Termination Detection, 346

11.1.15 FPGA Implementation of the Termination Detection, 348

11.2 Integers, 350

B’s

11.2.1 Complement Adders and Subtractors, 350

11.2.2 Excess-E Adders and Subtractors, 352

11.2.3 Sign-Magnitude Adders and Subtractors, 355

11.3 Bibliography, 357

12 Multipliers 359

12.1 Natural Numbers, 360

12.1.1 Basic Multiplier, 360

12.1.2 Sequential Multipliers, 363

12.1.3 Cellular Multiplier Arrays, 363

12.1.3.1 Ripple-Carry Multiplier, 365

12.1.3.2 Carry-Save Multiplier, 368

12.1.3.3 Figures of Merit, 370

12.1.4 Multipliers Based on Dissymmetric

r s

B B Cells, 370

12.1.5 Multipliers Based on Multioperand Adders, 378

12.1.6 Per Gelosia Multiplication Arrays, 383

12.1.6.1 Introduction, 383

12.1.6.2 Adding Tree for Base-B Partial Products, 384

12.1.7 FPGA Implementation of Multipliers, 386

12.2 Integers, 388

B’s

12.2.1 Complement Multipliers, 388

12.2.2 Booth Multipliers, 390

12.2.2.1 Booth-1 Multiplier, 390

12.2.2.2 Booth-2 Multiplier, 392

12.2.2.3 Signed-Digit Multiplier, 397

12.2.3 FPGA Implementation of the Booth-1 Multiplier, 404

12.3 Bibliography, 406

13 Dividers 407

13.1 Natural Numbers, 407

13.2 Integers, 415

13.2.1 Base-2 Nonrestoring Divider, 415

13.2.2 Base-B Nonrestoring Divider, 421 CONTENTS

xiv 13.2.3 SRT Dividers, 424

13.2.3.1 SRT-2 Divider, 424

13.2.3.2 SRT-2 Divider with Carry-Save Computation

of the Remainder, 428

13.2.3.3 FPGA Implementation of the Carry-Save SRT-2

Divider, 434

13.2.4 SRT-4 Divider, 435

13.2.5 Convergence Dividers, 439

13.2.5.1 Newton– Raphson Divider, 439

13.2.5.2 Goldschmidt Divider, 441

13.2.5.3 Comparative Data Between Newton –Raphson

(NR) and Goldschmidt (G) Implementations, 444

13.3 Bibliography, 444

14 Other Arithmetic Operators 447

14.1 Base Conversion, 447

14.1.1 General Base Conversion, 447

14.1.2 BCD to Binary Converter, 449

p

14.1.2.1 Nonrestoring 2 Subtracting Implementation, 449

14.1.2.2 Shift-and-Add BCD to Binary Converter, 450

14.1.3 Binary to BCD Converter, 452

14.1.4 Base-B to RNS Converter, 455

14.1.5 CRT RNS to Base-B Converter, 456

14.1.6 RNS to Mixed-Radix System Converter, 458

14.2 Polynomial Computation Circuits, 463

14.3 Logarithm Operator, 467

14.4 Exponential Operator, 468

14.5 Sine and Cosine Operators, 470

14.6 Square Rooters, 472

14.6.1 Restoring Shift-and-Subtract Square Rooter (Naturals), 472

14.6.2 Nonrestoring Shift-and-Subtract Square Rooter

(Naturals), 475

14.6.3 Newton –Raphson Square Rooter (Naturals), 477

14.7 Bibliography, 479

15 Circuits for Finite Field Operations 481

Z

15.1 Operations in , 481

m

15.1.1 Adders and Subtractors, 481

15.1.2 Multiplication, 484

15.1.2.1 Multiply and Reduce, 484

CONTENTS xv

15.1.2.2 Shift and Add, 485

15.1.2.3 Montgomery Multiplication, 487

k 2c)

15.1.2.4 Modulo (B Reduction, 490

15.1.2.5 Exponentiation, 494

GF(p),

15.2 Inversion in 497

Z

15.3 Operations in [x]/f (x), 500

p n

GF(p ), 504

15.4 Inversion in

15.5 Bibliography, 510

16 Floating-Point Unit 513

16.1 Floating-Point System Definition, 513

16.2 Arithmetic Operations, 515

16.2.1 Addition of Positive Numbers, 515

16.2.2 Difference of Positive Numbers, 517

16.2.3 Addition and Subtraction, 518

16.2.4 Multiplication, 520

16.2.5 Division, 521

16.2.6 Square Root, 522

16.3 Rounding Schemes, 524

16.4 Guard Digits, 525

16.5 Adder-Subtractor, 527

16.5.1 Alignment, 527

16.5.2 Additions, 529

16.5.3 Normalization, 530

16.5.4 Rounding, 530

16.6 Multiplier, 537

16.7 Divider, 542

16.8 Square Root, 546

16.9 Comments, 548

16.10 Bibliography, 548

Index 549

PREFACE

From the beginnings of digital electronic science, the synthesis of circuits carrying

out arithmetic operations has been a central topic. As a matter of fact, it is an activity

directly related to computer development. From then on, a well-known technical dis-

cipline was born: computer arithmetic. Traditionally, the study of arithmetic circuits

has been oriented toward applications to general-purpose computers, which provide

the most important applications of digital circuits. However, the electronic market

share corresponding to specific systems (embedded systems) is significant. It is

important to point out that the huge business volume that corresponds to general-

purpose computers (personal computers, servers, main frames) is distributed

among a relatively reduced number of different models. Therefore the number of

designers involved in general-purpose computer development is not as big as it

might seem and is much less than the number of engineers dedicated to production

and sales. The case of embedded systems is different. Embedded systems are circuits

designed for specific applications (special-purpose devices), so a great diversity of

products exist in the market, and the design effort per fabricated unit can be a lot

bigger than in the case of general-purpose computers. In consequence, the design

of specific computers is an activity in which numerous engineers are involved, in

all type of companies—even small ones—within numerous countries.

In this book methods and examples for synthesis of arithmetic circuits are described

with an emphasis somewhat different from the classic texts on computer arithmetic.

It is not limited to the description of the arithmetic units of computers.

. Descriptions of computation algorithms are presented in a section apart from

. the one dedicated to their materialization or implementation by digital circuits.

The development of an embedded system is an operation of hardware– software

codesign for which it is not known beforehand what tasks will be executed by a

microprocessor and what other tasks by specific coprocessors. For this reason, it

xvii

xviii PREFACE

appeared useful to describe the algorithms in an independent manner, without

any assumption on subsequent executions by an existent processor (software) or

by a new customized circuit (hardware).

A special, although not exclusive, importance has been given to user program-

. mable devices (field programmable devices such as FPGAs), especially to the

families Spartan II and Virtex. Those devices are very commonly used for the

realization of specific systems, mainly in the case of small series and proto-

types. The particular architecture of those components leads the designer to

use synthesis techniques somewhat different from the ones applied for ASICs

(application-specific integrated circuits) for which standard cell libraries exist.

In what concern circuits description, logic schemes are presented, sometimes

. with some VHDL models, in such a way that the corresponding circuits can

easily be simulated and synthesized.

After an introductory c