Spectral Logic and Its Applications for the Design of Digital Devices Book

Preface     xv
Acknowledgments     xxv
List of Figures     xxvii
List of Tables     xxxiii
Acronyms     xxxix
Logic Functions     1
Discrete Functions     2
Tabular Representations of Discrete Functions     3
Functional Expressions     6
Decision Diagrams for Discrete Functions     10
Decision Trees     11
Decision Diagrams     13
Decision Diagrams for Multiple-Valued Functions     16
Spectral Representations of Logic Functions     16
Fixed-polarity Reed-Muller Expressions of Logic Functions     23
Kronecker Expressions of Logic Functions     25
Circuit Implementation of Logic Functions     27
Spectral Transforms for Logic Functions     31
Algebraic Structures for Spectral Transforms     32
Fourier Series     34
Bases for Systems of Boolean Functions     35
Basis Functions     35
Walsh Functions     36
Ordering of Walsh Functions     40
Properties of Walsh Functions     43
Hardware Implementations of Walsh Functions     47
Haar Functions     50
Ordering of Haar Functions     51
Properties of Haar Functions     55
Hardware Implementation of Haar Functions     56
Hardware Implementation of the Inverse Haar Transform     58
Walsh Related Transforms     60
Arithmetic Transform     61
Arithmetic Expressions from Walsh Expansions     62
Bases for Systems of Multiple-Valued Functions     65
Vilenkin-Chrestenson Functions and Their Properties     66
Generalized Haar Functions     70
Properties of Discrete Walsh and Vilenkin-Chrestenson Transforms     71
Autocorrelation and Cross-Correlation Functions     79
Definitions of Autocorrelation and Cross-Correlation Functions     79
Relationships to the Walsh and Vilenkin-Chrestenson Transforms, the Wiener-Khinchin Theorem     80
Properties of Correlation Functions     82
Generalized Autocorrelation Functions     84
Harmonic Analysis over an Arbitrary Finite Abelian Group     85
Definition and Properties of the Fourier Transform on Finite Abelian Groups     85
Construction of Group Characters     89
Fourier-Galois Transforms     94
Fourier Transform on Finite Non-Abelian Groups     97
Representation of Finite Groups      98
Fourier Transform on Finite Non-Abelian Groups     101
Calculation of Spectral Transforms     106
Calculation of Walsh Spectra     106
Matrix Interpretation of the Fast Walsh Transform     109
Decision Diagram Methods for Calculation of Spectral Transforms     114
Calculation of the Walsh Spectrum Through BDD     115
Calculation of the Haar Spectrum     118
FFT-Like Algorithms for the Haar Transform     118
Matrix Interpretation of the Fast Haar Transform     121
Calculation of the Haar Spectrum Through BDD     126
Calculation of the Vilenkin-Chrestenson Spectrum     135
Matrix Interpretation of the Fast Vilenkin-Chrestenson Transform     136
Calculation of the Vilenkin-Chrestenson Transform Through Decision Diagrams     140
Calculation of the Generalized Haar Spectrum     141
Calculation of Autocorrelation Functions     142
Matrix Notation for the Wiener-Khinchin Theorem     143
Wiener-Khinchin Theorem Over Decision Diagrams     143
In-place Calculation of Autocorrelation Coefficients by Decision Diagrams     148
Spectral Methods in Optimization of Decision Diagrams     154
Reduction of Sizes of Decision Diagrams      155
K-Procedure for Reduction of Sizes of Decision Diagrams     156
Properties of the K-Procedure     164
Construction of Linearly Transformed Binary Decision Diagrams     169
Procedure for Construction of Linearly Transformed Binary Decision Diagrams     171
Modified K-Procedure     172
Computing Autocorrelation by Symbolic Manipulations     172
Experimental Results on the Complexity of Linearly Transformed Binary Decision Diagrams     173
Construction of Linearly Transformed Planar BDD     177
Planar Decision Diagrams     178
Construction of Planar LT-BDD by Walsh Coefficients     181
Upper Bounds on the Number of Nodes in Planar BDDs     185
Experimental Results for Complexity of Planar LT-BDDs     187
Spectral Interpretation of Decision Diagrams     188
Haar Spectral Transform Decision Diagrams     192
Haar Transform Related Decision Diagrams     197
Analysis and Optimization of Logic Functions     200
Spectral Analysis of Boolean Functions     200
Linear Functions     201
Self-Dual and Anti-Self-Dual Functions     203
Partially Self-Dual and Partially Anti-Self-Dual Functions     204
Quadratic Forms, Functions with Flat Autocorrelation      207
Analysis and Synthesis of Threshold Element Networks     212
Threshold Elements     212
Identification of Single Threshold Functions     214
Complexity of Logic Functions     222
Definition of Complexity of Systems of Switching Functions     222
Complexity and the Number of Pairs of Neighboring Minterms     225
Complexity Criteria for Multiple-Valued Functions     227
Serial Decomposition of Systems of Switching Functions     227
Spectral Methods and Complexity     227
Linearization Relative to the Number of Essential Variables     228
Linearization Relative to the Entropy-Based Complexity Criteria     231
Linearization Relative to the Numbers of Neighboring Pairs of Minterms     233
Classification of Switching Functions by Linearization     237
Linearization of Multiple-Valued Functions Relative to the Number of Essential Variables     239
Linearization for Multiple-Valued Functions Relative to the Entropy-Based Complexity Criteria     242
Parallel Decomposition of Systems of Switching Functions     244
Polynomial Approximation of Completely Specified Functions     244
Additive Approximation Procedure     249
Complexity Analysis of Polynomial Approximations      250
Approximation Methods for Multiple-Valued Functions     251
Estimation of the Number of Nonzero Coefficients     255
Spectral Methods in Synthesis of Logic Networks     261
Spectral Methods of Synthesis of Combinatorial Devices     262
Spectral Representations of Systems of Logic Functions     262
Spectral Methods for the Design of Combinatorial Devices     264
Asymptotically Optimal Implementation of Systems of Linear Functions     266
Walsh and Vilenkin-Chrestenson Bases for the Design of Combinatorial Networks     270
Linear Transforms of Variables in Haar Expressions     272
Synthesis with Haar Functions     274
Minimization of the Number of Nonzero Haar Coefficients     274
Determination of Optimal Linear Transform of Variables     275
Efficiency of the Linearization Method     283
Spectral Methods for Synthesis of Incompletely Specified Functions     286
Synthesis of Incompletely Specified Switching Functions     286
Synthesis of Incompletely Specified Functions by Haar Expressions     286
Spectral Methods of Synthesis of Multiple-Valued Functions     292
Multiple-Valued Functions     292
Network Implementations of Multiple-Valued Functions      292
Completion of Multiple-Valued Functions     293
Complexity of Linear Multiple-Valued Networks     293
Minimization of Numbers of Nonzero Coefficients in the Generalized Haar-Spectrum for Multiple-Valued Functions     295
Spectral Synthesis of Digital Functions and Sequences Generators     298
Function Generators     298
Design Criteria for Digital Function Generators     299
Hardware Complexity of Digital Function Generators     300
Bounds for the Number of Coefficients in Walsh Expansions of Analytical Functions     302
Implementation of Switching Functions Represented by Haar Series     303
Spectral Methods for Synthesis of Sequence Generators     304
Spectral Methods of Synthesis of Sequential Machines     308
Realization of Finite Automata by Spectral Methods     308
Finite Structural Automata     308
Spectral Implementation of Excitation Functions     311
Assignment of States and Inputs for Completely Specified Automata     313
Optimization of the Assignments for Implementation of the Combinational Part by Using the Haar Basis     315
Minimization of the Number of Highest Order Nonzero Coefficients     320
Minimization of the Number of Lowest Order Nonzero Coefficients     322
State Assignment for Incompletely Specified Automata     333
Minimization of Higher Order Nonzero Coefficients in Representation of Incompletely Specified Automata     333
Minimization of Lower Order Nonzero Coefficients in Spectral Representation of Incompletely Specified Automata     338
Some Special Cases of the Assignment Problem     342
Preliminary Remarks     342
Autonomous Automata     342
Assignment Problem for Automata with Fixed Encoding of Inputs or Internal States     344
Hardware Implementation of Spectral Methods     348
Spectral Methods of Synthesis with ROM     349
Serial Implementation of Spectral Methods     349
Sequential Haar Networks     350
Complexity of Serial Realization by Haar Series     352
Optimization of Sequential Spectral Networks     356
Parallel Realization of Spectral Methods of Synthesis     358
Complexity of Parallel Realization     359
Realization by Expansions over Finite Fields     362
Spectral Methods of Analysis and Synthesis of Reliable Devices     370
Spectral Methods for Analysis of Error Correcting Capabilities     370
Errors in Combinatorial Devices     370
Analysis of Error-Correcting Capabilities      371
Correction of Arithmetic Errors     381
Spectral Methods for Synthesis of Reliable Digital Devices     386
Reliable Systems for Transmission and Logic Processing     386
Correction of Single Errors     388
Correction of Burst Errors     391
Correction of Errors with Different Costs     393
Correction of Multiple Errors     396
Correcting Capability of Sequential Machines     399
Error Models for Finite Automata     399
Computing an Expected Number of Corrected Errors     400
Simplified Calculation of Characteristic Functions     400
Calculation of Two-Dimensional Autocorrelation Functions     404
Error-Correcting Capabilities of Linear Automata     408
Error-Correcting Capability of Group Automata     410
Error-Correcting Capabilities of Counting Automata     411
Synthesis of Fault-Tolerant Automata with Self-Error Correction     414
Fault-Tolerant Devices     414
Spectral Implementation of Fault-Tolerant Automata     415
Realization of Sequential Networks with Self-Error Correction     416
Comparison of Spectral and Classical Methods     419
Spectral Methods for Testing of Digital Systems     422
Testing and Diagnosis by Verification of Walsh Coefficients     423
Fault Models     423
Conditions for Testability     426
Conditions for Fault Diagnosis     428
Functional Testing, Error Detection, and Correction by Linear Checks     430
Introduction to Linear Checks     430
Check Complexities of Linear Checks     431
Spectral Methods for Construction of Optimal Linear Checks     434
Hardware Implementations of Linear Checks     440
Error-Detecting Capabilities of Linear Checks     442
Detection and Correction of Errors by Systems of Orthogonal Linear Checks     446
Linear Checks for Processors     455
Linear Checks for Error Detection in Polynomial Computations     457
Construction of Optimal Linear Checks for Polynomial Computations     462
Implementations and Error-Detecting Capabilities of Linear Checks     471
Testing for Numerical Computations     474
Linear Inequality Checks for Numerical Computations     474
Properties of Linear Inequality Checks     475
Check Complexities for Positive (Negative) Functions     479
Optimal Inequality Checks and Error-Correcting Codes     480
Error Detection in Computation of Numerical Functions      483
Estimations of the Probabilities of Error Detection for Inequality Checks     487
Construction of Optimal Systems of Orthogonal Inequality Checks     489
Error-Detecting and Error-Correcting Capabilities of Systems of Orthogonal Inequality Checks     492
Error Detection in Computer Memories by Linear Checks     498
Testing of Read-Only Memories     498
Correction of Single and Double Errors in ROMs by Two Orthogonal Equality Checks     499
Location of Errors in ROMs by Two Orthogonal Inequality Checks     504
Detection and Location of Errors in Random-Access Memories     507
Examples of Applications and Generalizations of Spectral Methods on Logic Functions     512
Transforms Designed for Particular Applications     513
Hybrid Transforms     513
Hadamard-Haar Transform     514
Slant Transform     516
Parameterised Transforms     518
Wavelet Transforms     521
Fibonacci Transforms     523
Fibonacci p-Numbers     524
Fibonacci p-Codes     525
Contracted Fibonacci p-Codes     525
Fibonacci-Walsh Hadamard Transform     527
Fibonacci-Haar Transform     528
Fibonacci SOP-Expressions      528
Fibonacci Reed-Muller Expressions     529
Two-Dimensional Spectral Transforms     530
Two-Dimensional Discrete Cosine Transform     534
Related Applications of Spectral Methods in Image Processing     536
Application of the Walsh Transform in Broadband Radio     537
Appendix A     541
References     554
Index     593