Effective computer methods for the calculation of Rademacher-Walsh spectrum for completely and incompletely specified Boolean functions

摘要

A theory has been developed to calculate the Rademacher-Walsh transform from a cube array specification of incompletely specified Boolean functions. The importance of representing Boolean functions as arrays of disjoint ON- and DC-cubes has been pointed out, and an efficient new algorithm to generate disjoint cubes from nondisjoint ones has been designed. The transform algorithm makes use of the properties of an array of disjoint cubes and allows the determination of the spectral coefficients in an independent way. The programs for both algorithms use advantages of C language to speed up the execution. The comparison of different versions of the algorithm has been carried out. The algorithm and its implementation provide the fastest and most comprehensive program (having many options) known to the authors for the calculation of the Rademacher-Walsh transform. It successfully overcomes all drawbacks in the calculation of the transform from the design automation system based on spectral method-the SPECSYS system from Drexel University, which uses fast Walsh transform.