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

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 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

2 Mathematical background

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

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
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

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
4.3.1 Complement Addition, 71
4.3.2 Complement Sign Change, 72
4.3.3 Complement Subtraction, 74
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

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
5.2.1 Complement Multiplication, 91
5.2.1.1 Mod Complement Multiplication, 92
5.2.1.2 Signed Shift and Add, 93
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, Booth-r Algorithm in Base 10, 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

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
6.2.6 P– D Diagram, 139
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

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

8.1 Operations in Z, 211
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
8.1.3.3 Montgomery Multiplication, 216
8.1.3.4 Specific Ring, 220
8.1.4 Exponentiation, 221
8.2 Operations in GF(p), 222
8.3 Operations in Z[x]/f (x), 224
8.3.1 Addition and Subtraction, 224
8.3.2 Multiplication, 225
8.4 Operations in GF(p), 228
8.5 Bibliography, 236
Appendix 8.1 Computation of f, 236

9 Hardware platforms

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
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

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

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
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
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
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

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 Dissymmetricr sB 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
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

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
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

14.1 Base Conversion, 447
14.1.1 General Base Conversion, 447
14.1.2 BCD to Binary Converter, 449
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

15.1 Operations in Z, 481
15.1.1 Adders and Subtractors, 481
15.1.2 Multiplication, 484
15.1.2.1 Multiply and Reduce, 484
15.1.2.2 Shift and Add, 485
15.1.2.3 Montgomery Multiplication, 487
15.1.2.4 Modulo (B Reduction, 490
15.1.2.5 Exponentiation, 494
15.2 Inversion in GF(p), 497
15.3 Operations in Z[x]/f (x), 500
15.4 Inversion in GF(p), 504
15.5 Bibliography, 510

16 Floating-point unit

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 discipline 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 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 programmable 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 prototypes. 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