EFFECTIVE COMPUTER METHODS FOR THE CALCULATION OF RADEMACHER-WALSH SPECTRUM FOR COMPLETELY AND INCOMPLETELY SPECIFIED BOOLEAN FUNCTIONS

被引：51

作者：

FALKOWSKI, BJ ^{[1
]}

SCHAFER, I ^{[1
]}

PERKOWSKI, MA ^{[1
]}

机构：

[1] PORTLAND STATE UNIV,DEPT ELECT ENGN,PORTLAND,OR 97207

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1992年 / 11卷 / 10期

关键词：

ALGORITHMS; RADEMACHER-WALSH TRANSFORM; SPECTRAL COEFFICIENTS; LOGIC DESIGN; CUBE CALCULUS; ARRAY OF DISJOINT CUBES; SUM-OF-PRODUCTS EXPRESSION; COMPLETELY AND INCOMPLETELY SPECIFIED BOOLEAN FUNCTIONS; STANDARD TRIVIAL FUNCTIONS; ORTHOGONAL FUNCTIONS;

D O I：

10.1109/43.170986

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 presented algorithm and its implementation is the fastest and most comprehensive program (having many options) known to us for the calculation of Rademacher-Walsh transform. It successfully overcomes all drawbacks in the calculation of the transform from the design automation system based on spectral methods-the SPECSYS system from Drexel University that uses Fast Walsh Transform.

引用

页码：1207 / 1226

页数：20

共 53 条

[1]

BEAUCHAMP KC, 1984, APPLICATIONS WALSH R

[2]

BRAYTON RK, 1985, LOGIC MINIMIZATION A

[3] MULTIPLE VALUED BOOLEAN MINIMIZATION BASED ON GRAPH-COLORING [J].

CIESIELSKI, MJ ;

YANG, SY ;

PERKOWSKI, MA .

PROCEEDINGS - IEEE INTERNATIONAL CONFERENCE ON COMPUTER DESIGN : VLSI IN COMPUTERS & PROCESSORS, 1989, :262-265

[4] FAULT-DETECTION IN COMBINATIONAL-NETWORKS BY REED-MULLER TRANSFORMS [J].

DAMARLA, TR ;

KARPOVSKY, M .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (06) :788-797

[5]

Davio M., 1978, DISCRETE SWITCHING F

[6] METHOD FOR FINDING RADEMACHER-WALSH SPECTRAL COEFFICIENTS OF BOOLEAN FUNCTIONS [J].

DEBNATH, RC ;

KARMAKAR, AK .

INTERNATIONAL JOURNAL OF ELECTRONICS, 1986, 60 (02) :245-250

[7]

DETJENS E, 1990, COMPUTER DESIGN NOV, P124

[8]

DIETMAYER DL, 1978, LOGIC DESIGN DIGITAL

[9] APPLICATION OF RADEMACHER - WALSH TRANSFORM TO BOOLEAN FUNCTION CLASSIFICATION AND THRESHOLD LOGIC SYNTHESIS [J].

EDWARDS, CR .

IEEE TRANSACTIONS ON COMPUTERS, 1975, C 24 (01) :48-62

[10] SPECTRAL TESTING OF CIRCUIT REALIZATIONS BASED ON LINEARIZATIONS [J].

ERIS, E ;

MUZIO, JC .

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES, 1986, 133 (02) :73-78

← 1 2 3 4 5 6 →