Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780849334245 | 0849334241
Cover: Hardcover
Copyright: 12/22/2005

Rent

(Recommended)

$113.56

Term

Due

Price

Semester

Dec 13

$126.18

Quarter

Aug 21

$119.87

Short Term

Jul 26

$113.56

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping cart.
Buy Used

Usually Ships in 2-4 Business Days

$128.63
Buy New

Usually Ships in 3-5 Business Days

$172.39
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

$51.36

Decision diagram (DD) techniques are very popular in the electronic design automation (EDA) of integrated circuits, and for good reason. They can accurately simulate logic design, can show where to make reductions in complexity, and can be easily modified to model different scenarios.Presenting DD techniques from an applied perspective, Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook provides a comprehensive, up-to-date collection of DD techniques. Experts with more than forty years of combined experience in both industrial and academic settings demonstrate how to apply the techniques to full advantage with more than 400 examples and illustrations. Beginning with the fundamental theory, data structures, and logic underlying DD techniques, they explore a breadth of topics from arithmetic and word-level representations to spectral techniques and event-driven analysis. The book also includes abundant references to more detailed information and additional applications.Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook collects the theory, methods, and practical knowledge necessary to design more advanced circuits and places it at your fingertips in a single, concise reference.

Preface

xxv

I FUNDAMENTALS OF DECISION DIAGRAM TECHNIQUES

(238)

1 Introduction

(18)

1.1 Data structures for the representation of discrete functions

(6)

1.1.1 Switching theory

(3)

1.1.2 Multivalued functions

(1)

1.2 Decision tables

(1)

1.3 Graphical data structures

(1)

1.4 Spectral techniques

(5)

1.4.1 Group theory

(1)

1.4.2 Abstract Fourier analysis

(3)

1.4.3 Correlation analysis

(1)

1.5 Stochastic models and information theoretic measures

(2)

1.5.1 Stochastic models and probability

(1)

1.5.2 Information theoretical measures of logic functions and decision trees

(1)

1.6 CAD of micro- and nanoelectronic circuits

(1)

1.7 Further reading

(2)

2 Data Structures

(16)

2.1 Introduction

(1)

2.2 Truth tables

(1)

2.3 Algebraic representations

(2)

2.3.1 Algebraic structure

(1)

2.3.2 Matrix representation

(1)

2.4 AND-OR expressions

(2)

2.4.1 Sum-of-products expressions

(1)

2.4.2 Computing the SOP coefficients

(1)

2.4.3 Restoration

(1)

2.5 Relevance to other data structures

(5)

2.5.1 Dataflow graphs

(1)

2.5.2 Hypercube

(2)

2.5.3 Decision trees and diagrams

(1)

2.5.4 Direct acyclic graph

(1)

2.6 Relationship of data structures

(2)

2.7 Further reading

(3)

3 Graphical Data Structures

(42)

3.1 Introduction

(1)

3.2 Graphs

(5)

3.3 Decision trees

(9)

3.3.1 Tree-like graphs

(2)

3.3.2 H-trees

(1)

3.3.3 Definition of a decision tree

(4)

3.3.4 Definition of a binary decision diagram

(1)

3.3.5 Measures on decision trees and diagrams

(2)

3.4 Shape of decision diagrams

(8)

3.5 Embedding decision trees and diagrams into various topological structures

(2)

3.6 Examples with hierarchical FPGA configuration

(1)

3.7 Voronoi diagrams and Delaunay triangulations

(9)

3.7.1 Voronoi diagram

(5)

3.7.2 Delaunay tessellation

(2)

3.7.3 Decision diagrams and Delaunay tessellation

(1)

3.8 Further reading

(7)

4 AND-EXOR Expressions, Trees, and Diagrams

(40)

4.1 Introduction

(1)

4.2 Terminology and classification of AND-EXOR, expressions

(3)

4.3 Algebraic representation

(10)

4.3.1 Positive polarity Reed-Muller expressions

(5)

4.3.2 Fixed polarity

(2)

4.3.3 Linear Reed-Muller expressions

(2)

4.4 Graphical representation

(9)

4.4.1 Hyp er cub e representation

(1)

4.4.2 Decision trees using AND-EXOR, operations

(5)

4.4.3 Decision diagrams

100

(2)

4.5 Transeunt triangle representation

102

(1)

4.6 Triangle topology

102

(10)

4.6.1 Representation of a symmetric function

105

(2)

4.6.2 Measures of transeunt triangle structures

107

(2)

4.6.3 Transeunt triangles and decision trees

109

(2)

4.6.4 Using transeunt triangles for representation of multivalued functions

111

(1)

4.7 Further reading

112

(7)

5 Arithmetic Representations

119

(16)

5.1 Introduction

119

(1)

5.2 Algebraic description

120

(6)

5.2.1 General algebraic form

120

(1)

5.2.2 Computing the coefficients

120

(1)

5.2.3 Data flowgraphs

121

(1)

5.2.4 Restoration

122

(2)

5.2.5 Useful rules

124

(1)

5.2.6 Polarity

124

(2)

5.3 Graphical representations

126

(6)

5.3.1 Hypercube representation

126

(1)

5.3.2 Decision trees and diagrams

127

(2)

5.3.3 Structural properties

129

(3)

5.3.4 Decision diagram reduction

132

(1)

5.4 Further reading

132

(3)

6 Word - Level Representations

135

(22)

6.1 Introduction

135

(4)

6.2 Arithmetic word-level computation in matrix form

139

(6)

6.2.1 Application of direct and inverse arithmetic transforms to word-level expressions

139

(4)

6.2.2 Arithmetic word-level form in a given polarity

143

(1)

6.2.3 Taylor representation

144

(1)

6.3 Computing word-level expressions in the form of corteges

145

(9)

6.3.1 Algebra of corteges

145

(1)

6.3.2 Implementation of algebra of corteges

146

(6)

6.3.3 Orthogonal corteges

152

(2)

6.4 Further reading

154

(3)

7 Spectral Techniques

157

(22)

7.1 Introduction

157

(1)

7.2 Spectral transforms

158

(6)

7.2.1 Fourier transforms on finite groups

159

(1)

7.2.2 Discrete Walsh transform

160

(4)

7.3 Haar and related transforms

164

(3)

7.4 Computing spectral coefficients

167

(5)

7.4.1 Computing the Walsh coefficients

167

(1)

7.4.2 Computing the Haar coefficients

168

(4)

7.5 Discrete wavelet transforms

172

(1)

7.6 Further reading

172

(7)

8 Information - Theoretical Measures

179

(30)

8.1 Introduction

179

(1)

8.2 Information-theoretical measures

180

(8)

8.2.1 Quantity of information

180

(2)

8.2.2 Conditional entropy and relative information

182

(2)

8.2.3 Entropy of a variable and a function

184

(2)

8.2.4 Mutual information

186

(2)

8.3 Information measures of elementary switching function of two variables

188

(3)

8.4 Information-theoretical measures and symmetry

191

(5)

8.4.1 Entropy of distribution of values of logic function

193

(1)

8.4.2 Condition of symmetry over the distribution

194

(2)

8.5 Information and flexibility

196

(4)

8.5.1 Sets of pairs of functions to be distinguished

197

(1)

8.5.2 Concept of neighborhood of a, function in terms of information

198

(2)

8.6 Further reading

200

(9)

9 Event - Driven Analysis

209

(30)

9.1 Introduction

209

(1)

9.2 Formal definition of change in a binary system

210

(12)

9.2.1 Detection of change

210

(3)

9.2.2 Matrix model of change

213

(2)

9.2.3 Model for simultaneous change

215

(2)

9.2.4 Model of multiple change: k-ordered Boolean differences

217

(2)

9.2.5 Boolean difference with respect to a vector of variables in matrix form

219

(1)

9.2.6 Symmetric properties of Boolean difference

220

(2)

9.3 Generating Reed Muller expressions with logic Taylor series

222

(1)

9.4 Computing Boolean differences on decision diagrams

222

(5)

9.4.1 Boolean difference and N-hypercube

223

(1)

9.4.2 Boolean difference, Davio tree, and N-hypercube

223

(4)

9.5 Models of logic networks in tennis of change

227

(4)

9.5.1 Event-driven analysis of switching function properties: dependence, sensitivity, and fault detection

227

(2)

9.5.2 Useful rules

229

(2)

9.6 Other logic differential operators

231

(4)

9.6.1 Models of directed changes in algebraic form

231

(8)

9.6.2 Arithmetic: analogs of Boolean differences and logic Taylor expansion

239

9.7 Further reading

235

(4)

II DECISION DIAGRAM TECHNIQUES FOR SWITCHING FUNCTIONS

239

(340)

10 Introduction

241

(20)

10.1 Genesis and evolution of decision diagrams

241

(3)

10.2 Various aspects of the construction of decision diagrams

244

(5)

10.3 Applications of decision diagrams

249

(3)

10.4 Implementation and technologies

252

(5)

10.5 Further reading

257

(4)

11 Classification of Decision Diagrams

261

(12)

11.1 Introduction

261

(2)

11.2 Classification of decision diagrams with respect to constant nodes

263

(2)

11.3 Classification of decision diagrams with respect to non-terminal nodes

265

(1)

11.4 Classification of decision diagrams with respect to decomposition rules

266

(1)

11.5 Classification of decision diagrams with respect to labels at the edges

267

(4)

11.6 Further reading

271

(2)

12 Variable Ordering in Decision Diagrams

273

(20)

12.1 Introduction

273

(2)

12.2 Adjacent variable interchange

275

(1)

12.3 Exact BDD minimization techniques

276

(1)

12.4 Problem specific ordering techniques

277

(2)

12.5 Dynamic variable ordering

279

(2)

12.5.1 Window permutation

279

(1)

12.5.2 Sifting

279

(2)

12.6 Advanced techniques

281

(4)

12.6.1 Symmetric variable and group sifting

281

(2)

12.6.2 Linear sifting

283

(1)

12.6.3 Window optimization

284

(1)

12.7 Path length

285

(1)

12.8 Reordering in BDD packages

286

(1)

12.9 Further reading

287

(6)

13 Spectral Decision Diagrams

293

(12)

13.1 The theoretical background of spectral interpretation of decision diagram techniques

293

(1)

13.2 Decision tree and spectrum of switching function

294

(2)

13.3 Bases of spectral transforms and decision diagrams

296

(1)

13.4 Fixed polarity spectral representations

296

(4)

13.5 Spectral decision diagram techniques

300

(3)

13.5.1 Decision diagrams as relations between algebraic and graphical data structures

302

(1)

13.5.2 Bit-level and word-level strategy

303

(1)

13.6 Further reading

303

(2)

14 Linearly Transformed Decision Diagrams

305

(24)

14.1 Introduction

305

(2)

14.1.1 Affine transforms

306

(1)

14.1.2 Linearly transformed decision diagrams

306

(1)

14.2 Manipulation of variables using affine transforms

307

(5)

14.2.1 Direct and inverse affine transforms

309

(2)

14.2.2 Affine transforms of the adjacent variables

311

(1)

14.3 Linearly transformed decision trees and diagrams

312

(5)

14.3.1 Affine transforms in decision trees

313

(1)

14.3.2 Affine transforms in decision diagrams

314

(3)

14.4 Examples of linear transform techniques

317

(2)

14.5 Further reading

319

(10)

15 Decision Diagrams for Arithmetic Circuits

329

(16)

15.1 Introduction

329

(1)

15.2 Binary adders

329

(4)

15.2.1 Full-adder

330

(1)

15.2.2 Ripple-carry adder

330

(1)

15.2.3 Binary-coded-decimal format

331

(2)

15.3 Multipliers

333

(3)

15.4 Word-level decision diagrams for arithmetic circuits

336

(4)

15.4.1 Spectral diagrams for representation of arithmetical circuits

336

(2)

15.4.2 Representation of adders by linear decision diagrams

338

(2)

15.5 Further reading

340

(5)

16 Edge - Valued Decision Diagrams

345

(12)

16.1 Introduction

345

(1)

16.2 Terminology and abbreviations of edge-valued decision trees and diagrams

346

(3)

16.3 Spectra] interpretation of edge-valued decision diagrams

349

(4)

16.3.1 Relationship of EVBDDs and Kronecker decision diagrams

352

(1)

16.3.2 Factored edge-valued BDDs

352

(1)

16.4 Binary moment diagrams

353

(1)

16.4.1 Binary moment decision diagrams-*BMDs

353

(1)

16.4.2 Arithmetic transform related decision diagrams

353

(1)

16.4.3 Kronecker binary moment diagrams

354

(1)

16.5 Further reading

354

(3)

17 Word - Level Decision Diagrams

357

(16)

17.1 Introduction

357

(1)

17.2 Multiteruiinal decision trees and diagrams

358

(2)

17.3 Spectral interpretation of word-level decision diagrams

360

(1)

17.4 Binary moment trees and diagrams

361

(5)

17.5 Haar spectral diagrams

366

(2)

17.6 Haar spectral transform decision trees

368

(1)

17.7 Other decision diagrams

369

(1)

17.8 Further reading

369

(4)

18 Minimization via Decision Diagrams

373

(18)

18.1 Introduction

373

(1)

18.2 Terminology

374

(4)

18.3 Minimization using hypercubes

378

(5)

18.4 Minimization of AND-EXOR expressions

383

(4)

18.5 Further reading

387

(4)

19 Decision Diagrams for Incompletely Specified Functions

391

(22)

19.1 Introduction

391

(1)

19.2 Representation of incompletely specified functions

392

(2)

19.3 Decision diagrams for incompletely specified logic functions

394

(5)

19.3.1 Safe BDD minimization

394

(3)

19.3.2 Kleene function and ternary decision diagrams

397

(2)

19.3.3 Manipulation of TDDs

399

(1)

19.4 Incompletely specified decision diagrams

399

(8)

19.4.1 Definition of the incompletely specified decision diagram

400

(1)

19.4.2 Manipulation of incompletely specified decision diagrams

400

(7)

19.5 Further reading

407

(6)

20 Probabilistic Decision Diagram Techniques

413

(16)

20.1 Introduction

413

(1)

20.2 BDD methods for computing output probability

414

(6)

20.2.1 A top-down approach

415

(1)

20.2.2 A bottom-up approach

416

(3)

20.2.3 Symbolic computation

419

(1)

20.3 Cross-correlation of functions

420

(6)

20.3.1 Recursive AND probability algorithm

422

(2)

20.3.2 Modification of an algorithm

424

(1)

20.3.3 Computing spectral coefficients

424

(2)

20.4 Further reading

426

(3)

21 Power Consumption Analysis using Decision Diagrams

429

(18)

21.1 Introduction

429

(2)

21.2 Switching activity

431

(2)

21.3 Decision diagrams for power consumption estimation

433

(8)

21.3.1 BDD for switching activity evaluation

434

(2)

21.3.2 Information measures on BDDs arid switching activity

436

(3)

21.3.3 Other decision diagrams for switching activity evaluation

439

(2)

21.4 Further reading

441

(6)

22 Formal Verification of Circuits

447

(18)

22.1 Introduction

447

(1)

22.2 Verification of combinational circuits

448

(5)

22.3 Verification using other types of diagrams

453

(5)

22.3.1 Word-level BDDs

455

(2)

22.3.2 Boolean expression diagrams

457

(1)

22.3.3 Non-canonical BDDs

458

(1)

22.4 Verification of sequential circuits

458

(2)

22.5 Further reading

460

(5)

23 Ternary Decision Diagrams

465

(16)

23.1 Terminology and abbreviations

465

(2)

23.2 Definition of ternary decision trees

467

(2)

23.3 EXOR ternary decision trees

469

(1)

23.4 Bit-level ternary decision trees

469

(2)

23.5 Word-level ternary decision trees

471

(2)

23.6 Arithmetic transform ternary decision diagrams

473

(1)

23.7 The relationships between arithmetic transform ternary decision diagrams and other decision trees

473

(1)

23.8 Ternary decision diagrams and differential operators for switching functions

474

(2)

23.9 Further reading

476

(5)

24 Information - Theoretical Measures in Decision Diagrams

481

(28)

24.1 Introduction

481

(1)

24.2 Information-theoretical measures

481

(3)

24.3 Information-theoretical measures in decision trees

484

(8)

24.3.1 Decision tree induction

484

24.3.2 Information-theoretical notation of switching function expansion

24.3.3 Optimization of variable ordering in a decision tree

188

(302)

24.3.4 Information measures in the N-hypercube

490

(2)

24.4 Information-theoretical measures in multivalued functions

492

(8)

24.4.1 Information notation of S expansion

493

(2)

24.4.2 Information notations of pD and nD expansion

495

(2)

24.4.3 Information criterion for decision tree design

497

(1)

24.4.4 Remarks on information-theoretical measures in decision diagrams

498

(2)

24.5 Ternary and pseudo-ternary decision trees

500

(3)

24.6 Entropy-based minimization using pseudo-ternary trees

503

(3)

24.7 Further reading

506

(3)

25 Decomposition Using Decision Diagrams

509

(36)

25.1 Introduction

509

(4)

25.1.1 Covering strategy

510

(1)

25.1.2 Decomposition strategy

511

(2)

25.2 Decomposition types

513

(5)

25.2.1 Shannon decomposition

513

(1)

25.2.2 Davio decomposition

514

(1)

25.2.3 Ashenhurst decomposition

514

(2)

25.2.4 Curtis decomposition

516

(1)

25.2.5 Bi-decomposition

516

(2)

25.3 Decomposition based on BDD structure

518

(8)

25.3.1 Multiplexer-based circuits

518

(1)

25.3.2 Disjoint Ashenhurst decomposition

519

(2)

25.3.3 Curtis decomposition

521

(2)

25.3.4 Bi-decomposition

523

(3)

25.4 Decomposition based on BDD operations

526

(10)

25.4.1 Incompletely specified functions

527

(1)

25.4.2 BBD based calculation of the m-fold minimum and m-fold maximum

528

(2)

25.4.3 OR-bi-decomposition and AND-bi-decomposition

530

(3)

25.4.4 EXOR-bi-decomposition

533

(1)

25.4.5 Weak OR- and AND-bi-decomposition

534

(2)

25.5 Further reading

536

(9)

26 Complexity of Decision Diagrams

545

(22)

26.1 Introduction

545

(1)

26.2 Specific functions

546

(3)

26.2.1 Basic logic functions

546

(2)

26.2.2 Adders

548

(1)

26.2.3 Multipliers and hidden weighted bit functions

548

(1)

26.3 Bounds

549

(3)

26.3.1 The general case

549

(1)

26.3.2 Totally-symmetric functions

550

(2)

26.3.3 Existence

552

(1)

26.4 Complemented edges

552

(2)

26.5 Path length

554

(7)

26.5.1 Symmetric variable nodes

554

(3)

26.5.2 Experimental results

557

(1)

26.5.3 Longest path length oriented techniques

557

(4)

26.6 Further reading

561

(6)

27 Programming of Decision Diagrams

567

(12)

27.1 Introduction

567

(1)

27.2 Representation of nodes

568

(1)

27.3 Representation of decision diagrams

568

(1)

27.4 Construction of decision diagrams

569

(4)

27.4.1 Unique table

572

(1)

27.4.2 Computed table

572

(1)

27.5 Construction of decision diagrams based on truth tables and variable ordering

573

(2)

27.6 Calculations with decision diagrams

575

(1)

27.7 Further reading

576

(3)

III DECISION DIAGRAM TECHNIQUES FOR MULTIVALUED FUNCTIONS

579

(90)

28 Introduction

581

(14)

28.1 Multivalued logic

581

(2)

28.2 Representation of multivalued functions

583

(1)

28.3 Spectral theory of multivalued functions

584

(2)

28.4 Multivalued decision trees and diagrams

586

(2)

28.5 Further reading

588

(7)

29 Multivalued Functions

595

(18)

29.1 Introduction

595

(1)

29.2 Multivalued functions

596

(1)

29.3 Multivalued logic

596

(6)

29.3.1 Operations of multivalued logic

597

(4)

29.3.2 Multivalued algebras

601

(1)

29.4 Galois fields

602

(4)

29.4.1 Galois fields GF(m)

602

(38)

29.4.2 Algebraic structure for Galois field representations

640

29.4.3 Galois field expansions

604

(2)

29.4.4 Partial Galois field transforms

606

(1)

29.5 Fault models based on the concept of change

606

(4)

29.6 Further reading

610

(3)

30 Spectral Transforms of Multivalued Functions

613

(22)

30.1 Introduction

611

(3)

30.2 Reed-Muller spectral transform

614

(8)

30.2.1 Direct and inverse Reed Muller transforms

611

(4)

30.2.2 Polarity

615

(7)

30.3 Arithmetic transform

622

(5)

30.3.1 Direct and inverse arithmetic transforms

699

30.3.2 Polarity

622

(2)

30.3.3 Word-level representation

624

(3)

30.4 Partial Reed-Muller-Fourier transforms

627

(1)

30.5 Relation of spectral representations

627

(2)

30.5.1 Families of spectral transforms

629

(1)

30.5.2 Information about the behavior of logic functions in terms of change

629

(1)

30.6 Further reading

629

(6)

31 Classification of Multivalued Decision Diagrams

635

(20)

31.1 Introduction

635

(1)

31.2 Background theory

636

(2)

31.3 Construction of EVDDs

638

(5)

31.3.1 Motivation

640

(1)

31.3.2 Algorithms

641

(1)

31.3.3 Complexity

641

(2)

31.3.4 Efficiency of EVDDs

643

(1)

31.4 Illustrative examples

643

(7)

31.5 Further reading

650

(5)

32 Event - Driven Analysis in Multivalued Systems

655

(14)

32.1 Introduction

655

(1)

32.2 Multivalued difference

656

(6)

32.3 Generation of Reed—Muller expressions

662

(4)

32.3.1 Logic Taylor expansion of a multivalued function

662

(1)

32.3.2 Computing Reed—Muller expressions

663

(1)

32.3.3 Computing Reed—Muller expressions in matrix form

663

(2)

32.3.4 N-hypercube representation

665

(1)

32.4 Further reading

666

(3)

IV SELECTED TOPICS OF DECISION DIAGRAM TECHNIQUES

669

(220)

33 Introduction

671

(14)

33.1 Relationship between decision diagrams and spatial structures

671

(7)

33.1.1 Embedding decision trees and diagrams into different topologies

672

(1)

33.1.2 Linear and multidimensional systolic arrays

673

(5)

33.2 Decision diagrams for reversible computation

678

(1)

33.3 Special types of decision diagrams and hybrid techniques

678

(2)

33.4 Developing of new decision diagrams

680

(1)

33.5 Further reading

680

(5)

34 Three - Dimensional Techniques

685

(34)

34.1 Introduction

685

(2)

34.2 Spatial structures

687

(2)

34.3 Hypercube data structure

689

(5)

34.4 Assembling of hypercubes

694

(2)

34.5 N-hypercube definition

696

(6)

34.5.1 Extension of a hypercube

696

(1)

34.5.2 Degree of freedom and rotation

697

(1)

34.5.3 Coordinate description

698

(4)

34.5.4 N-hypercube design for n > 3 dimensions

702

(1)

34.6 Embedding a binary decision tree into an N-hypercube

702

(5)

34.7 Spatial topological measurements

707

(3)

34.8 Embedding decision diagrams into incomplete N-hypercubes

710

(1)

34.8.1 Incomplete N-hypercubes

710

(1)

34.8.2 Embedding technique

710

(1)

34.9 Further reading

711

(8)

35 Decision Diagrams in Reversible Logic

719

(22)

35.1 Introduction

719

(1)

35.2 Reversible and quantum circuits

720

(9)

35.2.1 Reversible circuits

720

(3)

35.2.2 Quantum circuits

723

(6)

35.3 Decision diagram techniques

729

(8)

35.3.1 Representing matrices as decision diagrams

731

(3)

35.3.2 Matrix operations using decision diagrams

734

(3)

35.4 Further reading

737

(4)

36 Decision Diagrams on Quaternion Groups

741

(16)

36.1 Terminology

742

(1)

36.2 Introduction

743

(1)

36.3 Group-theoretic approach to decision diagrams

744

(4)

36.3.1 Decision diagrams for LUT FPGAs design

745

(1)

36.3.2 Spectral interpretation

746

(2)

36.4 Decision diagrams on quaternion group

748

(11)

36.4.1 Fourier transform on Q2

748

(1)

36.4.2 Decision diagrams on finite non-Abelian groups

749

(1)

30.4.3 Decision diagrams on non-Abelian groups with pre-processing

750

(1)

36.4.4 Advantages of non-Abelian groups in optimization of decision diagrams

751

(8)

36.5 Further reading

759

37 Linear Word - Level Decision Diagrams

757

(32)

37.1 Introduction

757

(1)

37.2 Linearization

757

(1)

37.3 Linear arithmetic expressions

758

(5)

37.3.1 Grouping

758

(2)

37.3.2 Computing the coefficients in the linear expression

760

(1)

37.3.3 Weight assignment

761

(1)

37.3.4 Masking

762

(1)

37.4 Linear arithmetic expressions of elementary functions

763

(4)

37.4.1 Functions of two and three variables

764

(1)

37.4.2 AND, OR, and EXOR functions of n variables

765

(1)

37.4.3 "Garbage" functions

766

(1)

37.5 Linear decision diagrams

767

(2)

37.6 Representation of a circuit level by linear word-level expression

769

(3)

37.7 Linear decision diagrams for circuit representation

772

(1)

37.8 Linear word-level expressions of multivalued functions

773

(9)

37.8.1 Approach to linearization

774

(1)

37.8.2 Algorithm for linearization of multivalued functions

775

(2)

37.8.3 Manipulation of the linear model

777

(2)

37.8.4 Library of linear models of multivalued gates

779

(1)

37.8.5 Representation of a multilevel, multivalued circuit

780

(1)

37.8.6 Linear decision diagrams

780

(2)

37.8.7 Remarks on computing details

782

(1)

37.9 Linear nonarithmetic word-level representation of multivalued functions

782

(2)

37.9.1 Linear word-level for MAX expressions

782

(2)

37.9.2 Network representation by linear models

784

(1)

37.10 Further reading

784

(5)

38 Fibonacci Decision Diagrams

789

(20)

38.1 Introduction

789

(1)

38.2 Terminology and abbreviations for Fibonacci decision trees and diagrams

790

(4)

38.3 Generalized Fibonacci numbers and codes

794

(1)

38.3.1 Fibonacci p-numbers

794

(1)

38.3.2 Fibonacci p-codes

794

(1)

38.4 Fibonacci decision trees

795

(7)

38.4.1 Binary decision trees and multiterminal binary decision trees

795

(4)

38.4.2 Properties of Fibonacci decision diagrams

799

(3)

38.5 Fibonacci decision trees and contracted Fibonacci p-codes

802

(1)

38.6 Spectral Fibonacci decision diagrams

803

(2)

38.7 Further reading

805

(4)

39 Techniques of Computing via Taylor - Like Expansions

809

(36)

39.1 Terminology

810

(2)

39.1.1 Additive structure of spectral coefficients

810

(1)

39.1.2 Multiplicative structure of spectral coefficients

811

(1)

39.1.3 Relationship of polynomial-like representations

811

(1)

39.2 Computing Reed–Muller expressions

812

(10)

39.2.1 Cube-based logic Taylor computing

815

(4)

39.2.2 Properties of Boolean difference in cube notation

819

(1)

39.2.3 Numerical example

820

(1)

39.2.4 Matrix form of logic Taylor expansion

820

(1)

39.2.5 Computing logic Taylor expansion by decision diagram

821

(1)

39.3 Computing arithmetic expressions via arithmetic Taylor expansion

822

(7)

39.3.1 Arithmetic analog of logic Taylor expansion

822

(4)

39.3.2 Cube based arithmetic spectrum computing

826

(1)

39.3.3 Properties of arithmetic differences in cube notation

826

(1)

39.3.4 Matrix form of arithmetic Taylor expansion

827

(2)

39.3.5 Computing arithmetic Taylor expansion by decision diagram

829

(1)

39.4 Computing Walsh expressions via Taylor expansion

829

(10)

39.4.1 Matrix form of Walsh differences

829

(4)

39.4.2 Walsh differences in symbolic form

833

(2)

39.4.3 Properties of Walsh differences in cube notation

835

(2)

39.4.4 Computing Taylor expansion by decision diagram

837

(2)

39.5 Further reading

839

(6)

40 Developing New Decision Diagrams

845

(22)

40.1 Introduction

845

(1)

40.2 Spectral tools for generation of decision diagrams

845

(12)

40.2.1 Approaches to the construction of decision diagrams

846

(2)

40.2.2 The spectral approach

848

(1)

40.2.3 Basic theorems

848

(2)

40.2.4 Decision diagram and the spectrum of a switching function

850

(7)

40.3 Group theoretic approach to designing decision diagrams

857

(3)

40.3.1 Basic theorems

858

(1)

40.3.2 Group-theoretic approach and topology

858

(2)

40.4 Further reading

860

(7)

41 Historical Perspectives and Open Problems

867

(22)

41.1 Trends in decision diagram techniques

867

(1)

41.2 New design and optimization strategies

867

(7)

41.2.1 Bio-inspired strategies

869

(1)

41.2.2 Adaptive reconfiguration

870

(1)

41.2.3 Artificial intelligence

870

(1)

41.2.4 Neural networks

871

(1)

41.2.5 Flexibility

872

(1)

41.2.6 Probabilistic techniques and information-theoretical measures

873

(1)

41.3 Extension of the area of application

874

(1)

41.3.1 Implementation aspects

874

(1)

41.3.2 Topology and embedding properties

875

(1)

41.4 Nanocircuit design - a new frontier for decision diagrams

875

(1)

41.4.1 Modeling spatial dimensions

875

(1)

41.4.2 Modeling spatial computing structures

875

(1)

41.4.3 Modeling nanocomputing

876

(1)

41.5 Further reading

876

(13)

V APPENDIX

889

(26)

Appendix A: Algebraic Structures for the Fourier Transform on Finite Groups

891

(6)

Appendix B: Fourier Analysis on Groups

897

(10)

Appendix C: Discrete Walsh Functions

907

(6)

Appendix D: The Basic Operations for Ternary and Quaternary Logic

913

(2)

Index

915

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook

Summary

Table of Contents

Supplemental Materials