Title :
On Minimal Modulo 2 Sums of Products for Switching Functions
Author :
Even, S. ; Kohavi, I. ; Paz, A.
Author_Institution :
Aiken Computation Laboratory at Harvard University, Cambridge, Mass.; Technion¿Israel Institute of Technology, Haifa, Israel.
Abstract :
The minimal number of terms required for representing any switching function as a modulo 2 sums of products is investigated, and an algorithm for obtaining economical realization is described. The main result is the following: every symmetric function of 2m+1 variables has a modulo 2 sum of products realization with at most 3m terms; but there are functions of n variables which require at least 2n/n log2 3 terms for sufficiently large n.
Keywords :
Algebra; Application software; Automata; Circuit theory; Eigenvalues and eigenfunctions; Galois fields; Minimization methods; Sequential circuits; Tree graphs; Vectors; Algorithm for economical realization; minimal modulo 2 forms; symmetric functions;
Journal_Title :
Electronic Computers, IEEE Transactions on
DOI :
10.1109/PGEC.1967.264777
