INDEX

Ack signal, 284

Ada, 81

Adder, 272, 289

augmented full, 316

base-B, 294

base-B^s, 301, 302

B's complement, 350

carry-chain, 292, 294, 322

carry-lookahead, 310, 311, 317

carry-save, 335

carry-select, 303, 306, 307

carry-skip, 294–298, 323, 325, 327

decimal, 291

excess-E, 352

5-operand, 340

floating point, 527

FPGA implementation, 322

integers, 350

long-operand, 327

modulo m, 481

m-operand, 274

multioperand, 328–330

natural numbers, 289

pipelined, 282

ripple-carry, 289

self-timed, 285, 286

7-operand 1-bit, 339

sign-magnitude, 355

statistical approach, 348

termination detection, 346

Adder-subtractor, 344, 345

B's complement, 352

floating point, 537

Addition, 55

basic algorithm, 56

B's complement, 71

carry-chain, 56

carry-lookahead, 66

carry-save, 69

carry-save long multioperand, 70

excess-E, 78

floating point numbers, 515, 518

integer(s), 71

long multioperand, 70

long-operand, 66, 67

modulo m, 212

multioperand, 67

natural numbers, 55

parallel-prefix, 63

sign-magnitude, 79

Additive normalization, 468

algorithm, 2

Alignment, 527

circuit, 528

Application specific instruction set processors (ASIP), 246, 250

Application specific integrated circuits (ASIC), 2, 240, 252, 271

design flow, 255

full-custom, 252

gate array, 253

semicustom, 253

standard-cell based, 254

Array

carry-save, 334

multioperand addition, 331

ASIC, see Application specific integrated circuits

ASIP, see Application specific instruction set processors

Augmented full adder, 316

B's complement, 166

adder, 350

adder-subtracter, 352

addition, 72

multiplication, 91

numeration system, 44

overflow detection, 74

reduced numeration system, 46

sign change, 72, 73

sign extension, 77

subtraction, 74

subtractor, 350

Base conversion, 165

algorithm, 167

base-B to RNS, 173

BCD to binary, 169

binary to BCD, 171

binary to decimal, 168

CRT RNS to base-B, 178

decimal to binary, 168

hexadecimal example, 167

RNS to base-B, 177

Base converter, 447

base-B to RNS, 455, 456

BCD to binary, 449

binary to BCD, 452

CRT RNS to base-B, 456

general, 447, 448

nonrestoring BCD to binary, 449

RNS to base-B, 456

RNS to mixed-radix conversion, 462, 463

RNS to mixed-radix system, 458

shift-and-add BCD to binary, 450, 452

Baugh and Wooley, 93, 390

BCD, see Binary coded decimal

Bernoulli numbers, 36

Binary. See also Binary coded decimal BCD to, 449, 450

coded, 365

digit, 40

system, 6

to BCD, 452

Binary coded decimal (BCD), 40, 290, 365, 449, 450

to binary, 449, 450

binary to, 452

Bit, see Binary, digit

Booth

algorithm, 96

coded input, 402

coded signed digits, 397

coding, 166

decode, 397

encode, 397

encoding, 47

multiplier, 390

Booth-1, 390

Booth-2, 392

representation, 48

Booth-3, 395, 397

decoder cell, 398

Booth-r

decoder cell, 399

representation system, 48

signed-digit decoder cell, 400

Brent–Kung carry chain, 318

Carry procedure, 63

Carry chain, 295

adder, 292, 294, 322

Brent–Kung, 318

carry-lookahead, 314, 316

carry-select, 305

carry-skip, 295

cell, 292, 293

conditional, 303, 306

Ladner–Fisher, 322

Manchester, 293

prefix, 318, 321

Carry-generate function, 272, 285. See also Generate function

Carry-kill function, 285

Carry-lookahead, 66

adder, 310, 311, 317

carry chain, 314, 316

generator, 313, 314

procedure, 63, 66

Carry-propagate function, 272, 285. See also Propagate function

Carry-save, 388, 422, 428

array, 334, 369, 371

multiplier, 368

reduction stage, 372, 381

sequential adder, 335

tree, 339, 342, 343, 378, 379

Carry-select adder, 303, 307

carry chain, 305

cell, 303

optimization, 307

Carry-skip adder, 294–297, 323, 325, 327

multiplexer, 324, 325

optimization, 298

Carry-stored form, 131

Chinese remainder theorem (CRT), 21, 177, 456

RNS to base-B, 456

Chopping, floating-point numbers, 524

CISC, see Complex instruction set computers

Clock skew, 282

Coefficient, leading, 27

Communication network, 241

Completion signal, see Done condition

Complex instruction set computers (CISC), 246

Complex programmable logic devise (CPLD), 256

Conditional carry chain, 303, 306

Congruence, 19

class, 20

modulo f (x), 32

modulo n, 19

of polynomials, 32

Control module, 241

Control unit, 274

Convergence, 407

methods, 165

Coordinate rotation digital computer (CORDIC), 165, 180, 193, 470, 471

basic rotation formulas, 195

pseudorotations, 193

sine and cosine procedure, 196

Coprocessor, 9

CORDIC, see Coordinate rotation digital computer

Cosine, see Sine and cosine

Cost in electronic design, 242

Counter(s), 381, 384

(5,5,4)-, 341

(7,3)-, 340

(p,k)-, 337

(p_r−1, p_r−2, …, p₀, k)-, 342

parallel, 337, 379

CPLD, see Complex programmable logic device

CRT, see Chinese remainder theorem

Cy.ch cell, see Carry-chain cell

Data flow graph, 277

Data path, 10, 240, 274

Decimal full adder, 291

Deg, see Degree

Degree, polynomial, 27

Difference, floating-point numbers, 517

Digit extension, 46, 47

Digit recurrence, 165, 407

algorithms, 109, 119

Digital signal processor (DSP), 2, 246, 249

Dissymmetric cells, 370

Distance, 51, 514

Divider

base-2 nonrestoring, 415

base-B, 421

base-B nonrestoring, 421

binary restoring, 408

carry-save basic cell, 429

carry-save SRT-2, 434

convergence, 439

floating-point, 542

FPGA, 434

Goldschmidt, 441, 444

integer, 411

Newton–Raphson, 439, 440, 444

nonrestoring, 416

normalized numbers, 419

on-the-fly conversion, 425

SRT, 424

SRT-2, 424

SRT-2 carry-save, 428, 430

SRT-2 carry-save in FPGA, 434

SRT-4, 435, 436

structure, 409

Division

base-2 nonrestoring algorithm, 121

base-2 step, 111

base-B nonrestoring, 148

base-B step, 111

floating-point numbers, 521

fundamental equation of, 110

integer(s), 16, 117

natural numbers, 110

nonrestoring base-B, 153

restoring, 7, 8

restoring algorithm, 121

restoring base-B, 116

SRT radix-2, 126

SRT radix-2 with stored-carry encoding, 131

SRT radix-4, 142, 145

Divisor, 15, 28

Done

condition, 284, 287

flag, 284

signal, 284

Dot

component, see Dot operator

diagram, 381

operation, 58

operator, 302, 310

procedure, 60, 62

DSP, see Digital signal processor

Embedded

processor, 248, 250

system, 1, 251, 268

Encoder

Booth, 397

stored-carry, 333, 338

Equivalence

class, 20, 32

relation, 32

Error

maximum, 51, 52, 53

maximum relative, 52, 53

relative, 51

Euclidean algorithm, 17

extended, 18, 22

extended for polynomials, 31

for polynomials, 28

Euler phi function, 24

Excess-E

adder, 352

addition, 78

representation, 43

sign change, 79

subtraction, 78

subtractor, 352

Excess-k, 166

Exponent, 182, 514

Exponential, 165, 180, 181, 463, 468

additive normalization, 188, 191

binary computation, 468

computation circuit, 469

convergence methods, 184

Exponentiation, 6

modulo m, 221, 494

Exponentiator, 10, 12

Extended Booth, 359

Fermat's little theorem, 24, 33

Field, 27, 32

finite field operations, 211, 481

Field programmable gate array (FPGA), 2, 8, 82, 258, 271, 359, 366, 386, 387, 404, 434

arithmetic resources in Xilinx, 264

basic concepts, 258

configurable logic blocks (CLB), 262

generic design flow, 264

input/output blocks (IOB), 262

logic block, 260

look-up table (LUT), 259

programming methods, 258

Xilinx specifics, 260

Fixed-point numeration system, 51

Flag

done, 284

stat-done, 347

Floating-point numbers

adder, 527

adder–subtractor, 537

addition, 515, 518

arithmetic operations, 515

chopping, 524

difference, 517

divider, 542

division, 521

multiplication, 520

multiplier, 537

multiplier with stored-carry encoding, 541

normalization, 515, 523

normalization circuit, 530

overflow, 524

rounding, 515

rounding circuit, 530

rounding schemes, 524

square root, 522, 546

subtraction, 518

subtractor, 527

truncation, 524

underflow, 524

unit, 513

Floating-point numeration system, 51, 52, 513, 514

ANSI/IEEE, 44, 53

unbiased, 525

FPGA, see Field-programmable gate array

Frobenius numbers, 236

Full adder

augmented, 316

cell, 289

generalized, 370

decimal, 291

Full subtractor cell, 344

Function approximation, 35

Galois field, 33

operations, 222

Garner's algorithm, 22, 23, 180

Gate array, 2. See also Field programmable gate array; Integrated circuit

Gcd, see Greatest common divisor

Generalized full adder (GFA), 370

Generalized generate function, 58, 301

Generalized half adder (GHA), 370

Generalized Horner expansion (GHE), 184, 463, 466

Generate function, 56, 292, 293

generalized, 58, 301

Generator, 25, 26

GF(p)

inversion, 497

operations, 222

GF(pⁿ)

exponentiation, 510

inversion, 229, 230, 231, 233, 235

inverter, 504, 506

multiplier, 501

operations, 228

GFA, see Generalized full adder

GHA, see Generalized half adder

GHE, see Generalized Hörner expansion

Goldschmidt, 441, 444

algorithm, 109, 159

Greatest common divisor (gcd), 16, 17, 18, 28

Group, 25

Abelian, 26

commutative, 26

cyclic, 25, 26, 33

multiplicative, 24

Guard digits, 525

Half adder cell, 291

generalized, 370

Hardware description language, 267

Verilog, 267

VHDL, 267

Hardware platform, 2, 8, 239

Hash function, 4

HDL, see Hardware description language

Hexadecimal system, 6

Hörner, 166, 170, 181

expansion, 84, 360

generalized expansion, 184, 463, 466

scheme revisited, 183

IC, see Integrated circuit

Identity element

additive, 27

multiplicative, 27

Input/output modules, 241

Integrated circuit, 239–255

application specific, see ASIC

Integrated system

basic blocks, 240

cost, 242

design metrics, 241

performance metric, 244

Intellectual property (IP), 240

Inverse, multiplicative, 20

Inversion

Itoh–Tsujii algorithm, 231

in GF(p), 497

in GF(pⁿ) 229–231, 233, 235

in Z_p, 223

Inverter

GF(p), 497

GF(pⁿ), 504, 506

modulo p, 498

IP, see Intellectual property

Ladner–Fischer carry chain, 321, 322

Latchless pipelining technique, 282

Latency, 271, 281, 283

average, 284

Logarithm, 165, 180, 182, 463, 467

computation circuit, 468

convergence methods, 184

multiplicative normalization, 184, 187

Long-operand adder, 327

Look-up tables, 82, 165. See also Field programmable gate array, look up tables

LUT, see Look-up tables

MacLaurin expansion, 159

MacLaurin series, 35

Manchester carry chain, 293

Mantissa, 182

Market window, 244

Memory, 240

Mersenne, 458

Microcontroller, 2, 248

Microprocessor, 2, 247

Mixed numeration system, 178

Mixed-radix, 459

unsigned digit system, 178

Modulo (B^k-c) reduction, 490

Modulo m

adder, 481

addition, 212

exponentiation, 221, 494

multiplier, 484. See also Modulo m multiplication

reduction, 220

subtraction, 213

subtractor, 481

Modulo m multiplication, 213

Montgomery product, 216, 218

multioperand, 220

multiply and reduce, 214, 484

shift and add, 214, 485

Modulo p inverter, 498

Montgomery product, 211, 216, 218, 487

multioperand, 220

Moore's law, 243

Multioperand, 384

adder combinational, 330

adder sequential, 328, 329

adders, 378

addition array, 331

addition basic algorithm, 67

addition tree, 332

Multiplexer carry-skip, 324, 325

Multiplicand, 360

Multiplication

array, 359, 363

Booth, 96

Booth for base-B numbers, 102

Booth-r, 97

B's complement, 91

cellular carry-save, 88

cellular ripple-carry, 86

cellular shift and add, 86

dissymmetric cell, 370

extended shift and add, 86

floating point numbers, 520

Hörner shift and add, 84

integer(s), 91

long-operand, 90

mod B^n+m B's complement, 92

modulo m, 7, 213

Montgomery product, 211

natural, 7

natural numbers, 82

Per Gelosia, 359, 383

Per Gelosia signed-digit, 98

polynomials, 227

post-correction 2's complement, 96

post-correction B's complement, 93, 389

shift and add, 83

signed shift and add, 93

Multiplicative normalization, 467

Multiplicator, 360

Multiplier

base-B, 361

based on multioperand adders, 378

Booth, 390

Booth-1, 390, 404

Booth-2, 392

Booth-3, 395

Booth-r, 395

B's complement, 388

carry-save, 368, 388

cellular, 363

floating point, 537

FPGA implementation, 386, 387, 404

modulo m Montgomery, 487

modulo m, 484

ripple-carry, 360, 365, 367

sequential, 363

Newton–Raphson, 109, 155, 180, 208, 439, 444, 477

convergence graph, 156

Nonrecurring engineering cost (NRE), 242, 252

Normalization

additive, 468

circuit, 530

exponential additive, 188, 191

floating point numbers, 515, 523

multiplicative, 467

NRE, see Nonrecurring engineering cost

Number

integer, 15, 42

natural, 15, 39

representation, 1, 6

Number representation system(s), 39

positional, 40

weighted, 39

Number theory, 15

Numeration system

base-B, 40

binary, 40

decimal, 40

fixed-point, 51

hexadecimal, 40

mixed-radix, 22, 40

octal, 40

Order of an element, 25, 26

Overflow

detection, 74

floating-point, 524

Parallel (3,2)-counter, 337

Parallel counter, 379

Partial remainder–divisor plot diagram, see P-D diagram

Partitioning hardware–software, 3, 8

P-D diagram, 139, 140

Pentium bug, 148

Per Gelosia, 98, 383, 401

ϕ(n), 24

PicoBlaze, 8, 9, 12

Pipeline, 281, 283

latchless technique, 282

(p,k)-counter, 378

PLD, see Programmable logic device

Polynomial, 27

approximation, 180, 183

computation, 463

constant, 27

irreducible, 28

monic, 28

multiplication, 227

zero, 27

0-degree, 33

Power consumption, 242, 245

Precedence graph, 277

relation, 277

scheduled, 278

Precision

absolute, 51

relative, 51

Prefix carry chain, 318

Prescaling, 185

Prime, 16

relatively, 16, 24

Primitive element, 25

Private key, 5

Processor, 245. See also Application specific instruction set processors; Complex instruction set computers; Digital signal processor; Reduced instruction set computer; Very long instruction word

embedded, 248, 250

general-purpose (GPP), 246

harvard architecture, 246

microcontroller, 2, 248

microprocessor, 2, 247

programming instruction-set, 251

superscalar, 247

von Neumann architecture, 246

Product, modular, 8

Programmable logic, 256. See also Field programmable gate array

Programmable logic device (PLD), 256

Propagate function, 56, 292

generalized, 58, 301

Prototype, 12

Prototyping board, 8

Q-select, 143

Quotient, 16, 28, 110

Quotient-digit

nonredundant, 148

redundant, 149

Range

of positive numbers, 52

of represented numbers, 52

relative, 53

Rate, sample, 281

Reciprocal computation, 157

Reduced instruction set computer (RISC), 245, 248

Redundant

base-B coding, 166

set of digits, 50

systems, 166

Remainder, 16, 28, 110

carry-stored representation, 132

Req signal, 284

Residue number system (RNS), 39, 42, 173, 455, 458

to mixed-radix, 458

representation, 42

Residues modulo m_i, 173

Resource

computation, 272

connection, 272

memory, 272

Ring, 27

commutative, 32

finite, 211

polynomial, 27, 211

Ripple-carry

adder, 289, 360

array, 366, 372

B-ary adder, 384

multioperand adders, 378

multiplier, 360, 365

RISC, see Reduced instruction set computer

RNS, see Residue number system

Robertson diagram, 119, 139

Rounding

circuit, 530

floating-point numbers, 515

schemes, 524

Sample rate, 281

Scheduling, 277

SDFA, see Signed-digit, full adder

Self-timed

adder, 285

circuit, 282

pipelined circuit, 284

Self-timing, 282

Semigroup, 26

Sign bit extension, 46

Signed systems, 166

Signed-digit, 166

counter, 402

full adder, 402

multiplier, 397

representation, 47

Significand, 514

Sign-magnitude, 166

adder, 355

addition, 79

representation, 42

subtraction, 79

subtractor, 355

Sine and cosine, 470

CORDIC algorithm, 471

SOC, see System-on-chip

Spartan, 8, 260–263

Square root, 104

base-2, 106

base-B, 104

cellular carry-save, 104

floating-point, 522, 546

Square rooter, 472

Newton–Raphson, 477

nn-restoring shift-and-subtract, 475

restoring shift-and-subtract, 472

Square rooting, 165, 198

convergence method, 208

digit recurrence, 198

integer in base-B, 200

Newton-Raphson, 208

nonrestoring binary add-and-subtract, 204

restoring binary shift-and-subtract, 202

Standard cell, 2

Start signal, 284

Stat-done flag, 347, 349

Statistical approach, 348

Sticky bit, 527

Stored-carry encoder, 68, 333

(5,2)-, 342

(5,2)-, 341

(7,3)-, 338, 340

(p,k)-, 338

form, 68, 69

Subfield, 33

Subtraction, 55

B's complement, 74

excess-E, 78

floating-point numbers, 518

modulo m, 213

natural numbers, 71, 344

sign magnitude, 79

Subtractor, 289, 344

B's complement, 350

excess-E, 352

floating-point, 527

modulo m, 481

ripple-carry, 344

sign-magnitude, 355

Synthesis, 3, 10, 14, 271

System-on-chip (SOC), 2. See also Embedded systems

Taylor expansion, 35

Taylor series, 35

Taylor-MacLaurin, 165, 180, 183

expansions, 109, 155

series, 181

Termination detection, 346

FPGA implementation, 348

Throughput, 271, 283

average, 284

Time-to-market, 243

Tree

carry-save, 339, 342, 343

multioperand addition, 332

Wallace/Dadda, 378

Trigonometric, 165, 182, 193, 463

functions, 180

Truncation, floating-point numbers, 524

Ulp, see Unit in the least significant position

Underflow, floating-point, 524

Unit in the least significant position (ulp), 51, 52, 109

Verilog, 267

Very long instruction word (VLIW), 246

VHDL, 267

Virtex, 260–265

VLIW, see Very long instruction word

Wallace/Dadda tree, 378

Z_n, 24

Z_p

inversion, 223

operations, 222

Z_p [x]/f(x)

adder, 500

addition, 224

multiplication, 225

operations, 224, 500

subtraction, 224

subtractor, 500