Spectral techniques : principles and applications in digital logic

Abstract

During the past three decades, the field of digital spectral logic theory has been born and its boundaries continuously extended. In this thesis work, principles and applications of spectral techniques in digital logic are considered. Analysis of Boolean symmetries, identification of various types of decomposition and the existence of Strict Avalanche Criterion (SAC) in Walsh and Reed-Muller domain have been analyzed. An efficient method to calculate modified Sign Walsh Transform is also presented. A new algorithm is given that converts a reduced representation of Boolean functions in the form of disjoint cubes to Sign Walsh spectra. Since the known algorithms that generate Sign Walsh spectra always start from the truth table of Boolean functions, the method presented computes faster with a smaller computer memory. The method is especially efficient for such Boolean functions that are described by only few disjoint cubes. The method to calculate the sign Walsh spectrum of Boolean functions directly from its corresponding Binary Decision Diagram is also shown. During calculation it is possible to generate either the full Sign Walsh spectrum or some selected coefficients. The algorithm is especially advantageous for the Boolean functions that are presented by compact decision diagrams.