Spectral Logic and Its Applications for the Design of Digital Devices

by Karpovsky, Mark G.; Stankovic, Radomir S.; Astola, Jaakko T.

• ISBN13: 9780471731887
• ISBN10: 0471731889
• Edition: 1st
• Format: Hardcover
• Copyright: 2008-05-27
• Publisher: Wiley-Interscience

Summary

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 Biography

Mark G. Karpovsky, PhD, is Professor of Computer Engineering at the College of Engineering and Director of Reliable Computing Laboratory, both at Boston University. Dr. Karpovsky authored the classic reference Finite Orthogonal Series in the Design of Digital Devices (Wiley). He has published more than 150 research papers and several books on the design of reliable computer and communications networks.

Radomir S. Stankovic is Professor of Computer Logic Design at the Department of Computer Science at University of Ni, Serbia. He has been a visiting researcher/faculty member at Kyushu Institute of Technology, Japan, and Tampere University of Technology, Finland.

Jaakko T. Astola has held academic positions in mathematics, applied mathematics, and computer science. Since 1993, he has been Professor of Signal Processing at Tampere University, Finland, and Director of Tampere International Center for Signal Processing. He has published over 150 research papers and several books on signal processing.

Table of Contents

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