Spectral logic and its applications for the design of digital devices

Spectral techniques facilitate the design and testing

of today's increasingly complex digital devices

There is heightened interest in spectral techniques for the design of digital devices dictated by ever increasing demands on technology that often cannot be met by classical approaches. Spectral methods provide a uniform and consistent theoretic environment for recent achievements in this area, which appear divergent in many other approaches. Spectral Logic and Its Applications for the Design of Digital Devices gives readers a foundation for further exploration of abstract harmonic analysis over finite groups in the analysis, design, and testing of digital devices. After an introduction, this book provides the essential mathematical background for discussing spectral methods. It then delves into spectral logic and its applications, covering:
*

Walsh, Haar, arithmetic transform, Reed-Muller transform for binary-valued functions and Vilenkin-Chrestenson transform, generalized Haar, and other related transforms for multiple-valued functions
*

Polynomial expressions and decision diagram representations for switching and multiple-value functions
*

Spectral analysis of Boolean functions
*

Spectral synthesis and optimization of combinational and sequential devices
*

Spectral methods in analysis and synthesis of reliable devices
*

Spectral techniques for testing computer hardware

This is the authoritative reference for computer science and engineering professionals and researchers with an interest in spectral methods of representing discrete functions and related applications in the design and testing of digital devices. It is also an excellent text for graduate students in courses covering spectral logic and its applications.

Author Notes

Radomir S. Stankovic is Professor of Computer Logic Design at the Department of Computer Science at University of Nis, Serbia.

Preface	p. xv
Acknowledgments	p. xxv
List of Figures	p. xxvii
List of Tables	p. xxxiii
Acronyms	p. xxxix
1 Logic Functions	p. 1
1.1 Discrete Functions	p. 2
1.2 Tabular Representations of Discrete Functions	p. 3
1.3 Functional Expressions	p. 6
1.4 Decision Diagrams for Discrete Functions	p. 10
1.4.1 Decision Trees	p. 11
1.4.2 Decision Diagrams	p. 13
1.4.3 Decision Diagrams for Multiple-Valued Functions	p. 16
1.5 Spectral Representations of Logic Functions	p. 16
1.6 Fixed-polarity Reed-Muller Expressions of Logic Functions	p. 23
1.7 Kronecker Expressions of Logic Functions	p. 25
1.8 Circuit Implementation of Logic Functions	p. 27
2 Spectral Transforms for Logic Functions	p. 31
2.1 Algebraic Structures for Spectral Transforms	p. 32
2.2 Fourier Series	p. 34
2.3 Bases for Systems of Boolean Functions	p. 35
2.3.1 Basis Functions	p. 35
2.3.2 Walsh Functions	p. 36
2.3.2.1 Ordering of Walsh Functions	p. 40
2.3.2.2 Properties of Walsh Functions	p. 43
2.3.2.3 Hardware Implementations of Walsh Functions	p. 47
2.3.3 Haar Functions	p. 50
2.3.3.1 Ordering of Haar Functions	p. 51
2.3.3.2 Properties of Haar Functions	p. 55
2.3.3.3 Hardware Implementation of Haar Functions	p. 56
2.3.3.4 Hardware Implementation of the Inverse Haar Transform	p. 58
2.4 Walsh Related Transforms	p. 60
2.4.1 Arithmetic Transform	p. 61
2.4.2 Arithmetic Expressions from Walsh Expansions	p. 62
2.5 Bases for Systems of Multiple-Valued Functions	p. 65
2.5.1 Vilenkin-Chrestenson Functions and Their Properties	p. 66
2.5.2 Generalized Haar Functions	p. 70
2.6 Properties of Discrete Walsh and Vilenkin-Chrestenson Transforms	p. 71
2.7 Autocorrelation and Cross-Correlation Functions	p. 79
2.7.1 Definitions of Autocorrelation and Cross-Correlation Functions	p. 79
2.7.2 Relationships to the Walsh and Vilenkin-Chrestenson Transforms, the Wiener-Khinchin Theorem	p. 80
2.7.3 Properties of Correlation Functions	p. 82
2.7.4 Generalized Autocorrelation Functions	p. 84
2.8 Harmonic Analysis over an Arbitrary Finite Abelian Group	p. 85
2.8.1 Definition and Properties of the Fourier Transform on Finite Abelian Groups	p. 85
2.8.2 Construction of Group Characters	p. 89
2.8.3 Fourier-Galois Transforms	p. 94
2.9 Fourier Transform on Finite Non-Abelian Groups	p. 97
2.9.1 Representation of Finite Groups	p. 98
2.9.2 Fourier Transform on Finite Non-Abelian Groups	p. 101
3 Calculation of Spectral Transforms	p. 106
3.1 Calculation of Walsh Spectra	p. 106
3.1.1 Matrix Interpretation of the Fast Walsh Transform	p. 109
3.1.2 Decision Diagram Methods for Calculation of Spectral Transforms	p. 114
3.1.3 Calculation of the Walsh Spectrum Through BDD	p. 115
3.2 Calculation of the Haar Spectrum	p. 118
3.2.1 FFT-Like Algorithms for the Haar Transform	p. 118
3.2.2 Matrix Interpretation of the Fast Haar Transform	p. 121
3.2.3 Calculation of the Haar Spectrum Through BDD	p. 126
3.3 Calculation of the Vilenkin-Chrestenson Spectrum	p. 135
3.3.1 Matrix Interpretation of the Fast Vilenkin-Chrestenson Transform	p. 136
3.3.2 Calculation of the Vilenkin-Chrestenson Transform Through Decision Diagrams	p. 140
3.4 Calculation of the Generalized Haar Spectrum	p. 141
3.5 Calculation of Autocorrelation Functions	p. 142
3.5.1 Matrix Notation for the Wiener-Khinchin Theorem	p. 143
3.5.2 Wiener-Khinchin Theorem Over Decision Diagrams	p. 143
3.5.3 In-place Calculation of Autocorrelation Coefficients by Decision Diagrams	p. 148
4 Spectral Methods in Optimization of Decision Diagrams	p. 154
4.1 Reduction of Sizes of Decision Diagrams	p. 155
4.1.1 K-Procedure for Reduction of Sizes of Decision Diagrams	p. 156
4.1.2 Properties of the K-Procedure	p. 164
4.2 Construction of Linearly Transformed Binary Decision Diagrams	p. 169
4.2.1 Procedure for Construction of Linearly Transformed Binary Decision Diagrams	p. 171
4.2.2 Modified K-Procedure	p. 172
4.2.3 Computing Autocorrelation by Symbolic Manipulations	p. 172
4.2.4 Experimental Results on the Complexity of Linearly Transformed Binary Decision Diagrams	p. 173
4.3 Construction of Linearly Transformed Planar BDD	p. 177
4.3.1 Planar Decision Diagrams	p. 178
4.3.2 Construction of Planar LT-BDD by Walsh Coefficients	p. 181
4.3.3 Upper Bounds on the Number of Nodes in Planar BDDs	p. 185
4.3.4 Experimental Results for Complexity of Planar LT-BDDs	p. 187
4.4 Spectral Interpretation of Decision Diagrams	p. 188
4.4.1 Haar Spectral Transform Decision Diagrams	p. 192
4.4.2 Haar Transform Related Decision Diagrams	p. 197
5 Analysis and Optimization of Logic Functions	p. 200
5.1 Spectral Analysis of Boolean Functions	p. 200
5.1.1 Linear Functions	p. 201
5.1.2 Self-Dual and Anti-Self-Dual Functions	p. 203
5.1.3 Partially Self-Dual and Partially Anti-Self-Dual Functions	p. 204
5.1.4 Quadratic Forms, Functions with Flat Autocorrelation	p. 207
5.2 Analysis and Synthesis of Threshold Element Networks	p. 212
5.2.1 Threshold Elements	p. 212
5.2.2 Identification of Single Threshold Functions	p. 214
5.3 Complexity of Logic Functions	p. 222
5.3.1 Definition of Complexity of Systems of Switching Functions	p. 222
5.3.2 Complexity and the Number of Pairs of Neighboring Minterms	p. 225
5.3.3 Complexity Criteria for Multiple-Valued Functions	p. 227
5.4 Serial Decomposition of Systems of Switching Functions	p. 227
5.4.1 Spectral Methods and Complexity	p. 227
5.4.2 Linearization Relative to the Number of Essential Variables	p. 228
5.4.3 Linearization Relative to the Entropy-Based Complexity Criteria	p. 231
5.4.4 Linearization Relative to the Numbers of Neighboring Pairs of Minterms	p. 233
5.4.5 Classification of Switching Functions by Linearization	p. 237
5.4.6 Linearization of Multiple-Valued Functions Relative to the Number of Essential Variables	p. 239
5.4.7 Linearization for Multiple-Valued Functions Relative to the Entropy-Based Complexity Criteria	p. 242
5.5 Parallel Decomposition of Systems of Switching Functions	p. 244
5.5.1 Polynomial Approximation of Completely Specified Functions	p. 244
5.5.2 Additive Approximation Procedure	p. 249
5.5.3 Complexity Analysis of Polynomial Approximations	p. 250
5.5.4 Approximation Methods for Multiple-Valued Functions	p. 251
5.5.5 Estimation of the Number of Nonzero Coefficients	p. 255
6 Spectral Methods in Synthesis of Logic Networks	p. 261
6.1 Spectral Methods of Synthesis of Combinatorial Devices	p. 262
6.1.1 Spectral Representations of Systems of Logic Functions	p. 262
6.1.2 Spectral Methods for the Design of Combinatorial Devices	p. 264
6.1.3 Asymptotically Optimal Implementation of Systems of Linear Functions	p. 266
6.1.4 Walsh and Vilenkin-Chrestenson Bases for the Design of Combinatorial Networks	p. 270
6.1.5 Linear Transforms of Variables in Haar Expressions	p. 272
6.1.6 Synthesis with Haar Functions	p. 274
6.1.6.1 Minimization of the Number of Nonzero Haar Coefficients	p. 274
6.1.6.2 Determination of Optimal Linear Transform of Variables	p. 275
6.1.6.3 Efficiency of the Linearization Method	p. 283
6.2 Spectral Methods for Synthesis of Incompletely Specified Functions	p. 286
6.2.1 Synthesis of Incompletely Specified Switching Functions	p. 286
6.2.2 Synthesis of Incompletely Specified Functions by Haar Expressions	p. 286
6.3 Spectral Methods of Synthesis of Multiple-Valued Functions	p. 292
6.3.1 Multiple-Valued Functions	p. 292
6.3.2 Network Implementations of Multiple-Valued Functions	p. 292
6.3.3 Completion of Multiple-Valued Functions	p. 293
6.3.4 Complexity of Linear Multiple-Valued Networks	p. 293
6.3.5 Minimization of Numbers of Nonzero Coefficients in the Generalized Haar-Spectrum for Multiple-Valued Functions	p. 295
6.4 Spectral Synthesis of Digital Functions and Sequences Generators	p. 298
6.4.1 Function Generators	p. 298
6.4.2 Design Criteria for Digital Function Generators	p. 299
6.4.3 Hardware Complexity of Digital Function Generators	p. 300
6.4.4 Bounds for the Number of Coefficients in Walsh Expansions of Analytical Functions	p. 302
6.4.5 Implementation of Switching Functions Represented by Haar Series	p. 303
6.4.6 Spectral Methods for Synthesis of Sequence Generators	p. 304
7 Spectral Methods of Synthesis of Sequential Machines	p. 308
7.1 Realization of Finite Automata by Spectral Methods	p. 308
7.1.1 Finite Structural Automata	p. 308
7.1.2 Spectral Implementation of Excitation Functions	p. 311
7.2 Assignment of States and Inputs for Completely Specified Automata	p. 313
7.2.1 Optimization of the Assignments for Implementation of the Combinational Part by Using the Haar Basis	p. 315
7.2.2 Minimization of the Number of Highest Order Nonzero Coefficients	p. 320
7.2.3 Minimization of the Number of Lowest Order Nonzero Coefficients	p. 322
7.3 State Assignment for Incompletely Specified Automata	p. 333
7.3.1 Minimization of Higher Order Nonzero Coefficients in Representation of Incompletely Specified Automata	p. 333
7.3.2 Minimization of Lower Order Nonzero Coefficients in Spectral Representation of Incompletely Specified Automata	p. 338
7.4 Some Special Cases of the Assignment Problem	p. 342
7.4.1 Preliminary Remarks	p. 342
7.4.2 Autonomous Automata	p. 342
7.4.3 Assignment Problem for Automata with Fixed Encoding of Inputs or Internal States	p. 344
8 Hardware Implementation of Spectral Methods	p. 348
8.1 Spectral Methods of Synthesis with ROM	p. 349
8.2 Serial Implementation of Spectral Methods	p. 349
8.3 Sequential Haar Networks	p. 350
8.4 Complexity of Serial Realization by Haar Series	p. 352
8.4.1 Optimization of Sequential Spectral Networks	p. 356
8.5 Parallel Realization of Spectral Methods of Synthesis	p. 358
8.6 Complexity of Parallel Realization	p. 359
8.7 Realization by Expansions over Finite Fields	p. 362
9 Spectral Methods of Analysis and Synthesis of Reliable Devices	p. 370
9.1 Spectral Methods for Analysis of Error Correcting Capabilities	p. 370
9.1.1 Errors in Combinatorial Devices	p. 370
9.1.2 Analysis of Error-Correcting Capabilities	p. 371
9.1.3 Correction of Arithmetic Errors	p. 381
9.2 Spectral Methods for Synthesis of Reliable Digital Devices	p. 386
9.2.1 Reliable Systems for Transmission and Logic Processing	p. 386
9.2.2 Correction of Single Errors	p. 388
9.2.3 Correction of Burst Errors	p. 391
9.2.4 Correction of Errors with Different Costs	p. 393
9.2.5 Correction of Multiple Errors	p. 396
9.3 Correcting Capability of Sequential Machines	p. 399
9.3.1 Error Models for Finite Automata	p. 399
9.3.2 Computing an Expected Number of Corrected Errors	p. 400
9.3.2.1 Simplified Calculation of Characteristic Functions	p. 400
9.3.2.2 Calculation of Two-Dimensional Autocorrelation Functions	p. 404
9.3.3 Error-Correcting Capabilities of Linear Automata	p. 408
9.3.4 Error-Correcting Capability of Group Automata	p. 410
9.3.5 Error-Correcting Capabilities of Counting Automata	p. 411
9.4 Synthesis of Fault-Tolerant Automata with Self-Error Correction	p. 414
9.4.1 Fault-Tolerant Devices	p. 414
9.4.2 Spectral Implementation of Fault-Tolerant Automata	p. 415
9.4.3 Realization of Sequential Networks with Self-Error Correction	p. 416
9.5 Comparison of Spectral and Classical Methods	p. 419
10 Spectral Methods for Testing of Digital Systems	p. 422
10.1 Testing and Diagnosis by Verification of Walsh Coefficients	p. 423
10.1.1 Fault Models	p. 423
10.1.2 Conditions for Testability	p. 426
10.1.3 Conditions for Fault Diagnosis	p. 428
10.2 Functional Testing, Error Detection, and Correction by Linear Checks	p. 430
10.2.1 Introduction to Linear Checks	p. 430
10.2.2 Check Complexities of Linear Checks	p. 431
10.2.3 Spectral Methods for Construction of Optimal Linear Checks	p. 434
10.2.4 Hardware Implementations of Linear Checks	p. 440
10.2.5 Error-Detecting Capabilities of Linear Checks	p. 442
10.2.6 Detection and Correction of Errors by Systems of Orthogonal Linear Checks	p. 446
10.3 Linear Checks for Processors	p. 455
10.4 Linear Checks for Error Detection in Polynomial Computations	p. 457
10.5 Construction of Optimal Linear Checks for Polynomial Computations	p. 462
10.6 Implementations and Error-Detecting Capabilities of Linear Checks	p. 471
10.7 Testing for Numerical Computations	p. 474
10.7.1 Linear Inequality Checks for Numerical Computations	p. 474
10.7.2 Properties of Linear Inequality Checks	p. 475
10.7.3 Check Complexities for Positive (Negative) Functions	p. 479
10.8 Optimal Inequality Checks and Error-Correcting Codes	p. 480
10.8.1 Error Detection in Computation of Numerical Functions	p. 483
10.8.2 Estimations of the Probabilities of Error Detection for Inequality Checks	p. 487
10.8.3 Construction of Optimal Systems of Orthogonal Inequality Checks	p. 489
10.8.4 Error-Detecting and Error-Correcting Capabilities of Systems of Orthogonal Inequality Checks	p. 492
10.9 Error Detection in Computer Memories by Linear Checks	p. 498
10.9.1 Testing of Read-Only Memories	p. 498
10.9.2 Correction of Single and Double Errors in ROMs by Two Orthogonal Equality Checks	p. 499
10.10 Location of Errors in ROMs by Two Orthogonal Inequality Checks	p. 504
10.11 Detection and Location of Errors in Random-Access Memories	p. 507
11 Examples of Applications and Generalizations of Spectral Methods on Logic Functions	p. 512
11.1 Transforms Designed for Particular Applications	p. 513
11.1.1 Hybrid Transforms	p. 513
11.1.2 Hadamard-Haar Transform	p. 514
11.1.3 Slant Transform	p. 516
11.1.4 Parameterised Transforms	p. 518
11.2 Wavelet Transforms	p. 521
11.3 Fibonacci Transforms	p. 523
11.3.1 Fibonacci p-Numbers	p. 524
11.3.2 Fibonacci p-Codes	p. 525
11.3.3 Contracted Fibonacci p-Codes	p. 525
11.3.4 Fibonacci-Walsh Hadamard Transform	p. 527
11.3.5 Fibonacci-Haar Transform	p. 528
11.3.6 Fibonacci SOP-Expressions	p. 528
11.3.7 Fibonacci Reed-Muller Expressions	p. 529
11.4 Two-Dimensional Spectral Transforms	p. 530
11.4.1 Two-Dimensional Discrete Cosine Transform	p. 534
11.4.2 Related Applications of Spectral Methods in Image Processing	p. 536
11.5 Application of the Walsh Transform in Broadband Radio	p. 537
Appendix A	p. 541
References	p. 554
Index	p. 593

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents