Spectral Logic and Its Applications for the Design of Digital Devices

by Mark G. Karpovsky (College of Engineering, Boston University ); Radomir S. Stankovic; Jaakko T. Astola

• ISBN13: 9780470289211
• ISBN10: 047028921X
• Format: eBook
• Copyright: 2008-07-01
• 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.

Table of Contents

Preface

Acknowledgments

List Of Figures

List Of Tables

Acronyms.1. Logic Functions

Discrete Functions

Tabular Representations of Discrete Functions

Functional Expressions

Decision Diagrams for Discrete Functions

Spectral Representations of Logic Functions

Fixed-polarity ReedûMuller Expressions of Logic.Functions

Kronecker Expressions of Logic Functions

Circuit Implementation of Logic Functions

Spectral Transforms For Logic Functions

Algebraic Structures for Spectral Transforms

Fourier Series

Bases for Systems of Boolean Functions

Walsh Related Transforms

Bases for Systems of Multiple-Valued Functions

Properties of DiscreteWalsh andVilenkinûChrestenson Transforms

Autocorrelation and Cross-Correlation Functions

Harmonic Analysis over an Arbitrary Finite Abelian Group

Fourier Transform on Finite NonûAbelian Groups

Calculation Of Spectral Transforms

Calculation of Walsh Spectra

Calculation of the Haar Spectrum

Calculation of the VilenkinûChrestenson Spectrum

Calculation of the Generalized Haar Spectrum

Calculation of Autocorrelation Functions

Spectral Methods In Optimization Of Decision Diagrams

Reduction of Sizes of Decision Diagrams

Construction of Linearly Transformed Binary Decision Diagrams

Construction of Linearly Transformed Planar BDD

Spectral Interpretation of Decision Diagrams

Analysis And Optimization Of Logic Functions

Spectral Analysis of Boolean Functions

Analysis and Synthesis of Threshold Element Networks

Complexity of Logic Functions

Serial Decomposition of Systems of Switching Functions

Parallel Decomposition of Systems of Switching Functions

Spectral Methods In Synthesis Of Logic Networks

Spectral Methods of Synthesis of Combinatorial Devices

Spectral Methods for Synthesis of Incompletely Specified Functions

Spectral Methods of Synthesis of Multiple-Valued Functions

Spectral Synthesis of Digital Functions and Sequences Generators

Spectral Methods Of Synthesis Of Sequential Machines

Realization of Finite Automata by Spectral Methods

Assignment of States and Inputs for Completely Specified Automata

State Assignment for Incompletely Specified Automata

Some Special Cases of the Assignment Problem

Hardware Implementation Of Spectral Methods

Spectral Methods of Synthesis with ROM

Serial Implementation of Spectral Methods

Sequential Haar Networks

Complexity of Serial Realization by Haar Series

Parallel Realization of Spectral Methods of Synthesis

Complexity of Parallel Realization

Realization by Expansions over Finite Fields

Spectral Methods Of Analysis And Synthesis Of Reliable Devices

Spectral Methods for Analysis of Error Correcting Capabilities

Spectral Methods for Synthesis of Reliable Digital Devices

Correcting Capability of Sequential Machines

Synthesis of Fault-Tolerant Automata with Self-Error Correction

Comparison of Spectral and Classical Methods

Spectral Methods For Testing Of Digital Systems

Testing and Diagnosis by Verification of Walsh Coefficients

Functional Testing, Error Detection, and Correction by Linear Checks

Linear Checks for Processors

Linear Checks for Error Detection in Polynomial Computations

Construction of Optimal Linear Checks for Polynomial Computations

Implementations and Error-Detecting Capabilities of Linear Checks

Testing for Numerical Computations

Optimal Inequality Checks and Error-Correcting Codes

Error Detection in Computer Memories by Linear Checks

Location of Errors in ROMs by Two Orthogonal Inequality Checks

Detection and Location of Errors in Random-Access Memories

Examples Of Applications And Generalizations Of Spectral Methods On Logic Functions

Transforms Designed for Particular Applications

Wavelet Transforms

Fibonacci Transforms

Two-Dimensional Spectral Transforms

Application of the Walsh Transform in Broadband Radio

Appendix A

References

Index

Table of Contents provided by Publisher. All Rights Reserved.