On Length of Boolean Functions of a Small Number of Variables in the Class of Pseudo-Polynomials

Abstract

Minimization of Boolean functions in their various representations is required in logic design of digital devices. EXOR sums (polynomial forms) are considered among other representations. An EXOR sum (a polynomial form) is an expression that is an EXOR sum of products of factors in a certain form. We can accentuate some classes of EXOR sums (of polynomial forms) such that Fixed Polarized Reed-Muller forms, FPRMs (polarized polynomial forms, PPFs), EXOR Sums of Products, ESOPs (polynomial normal forms, PNFs), EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs), etc. In series of works, minimization algorithms are devised, and bounds are obtained for the length of functions in these classes of EXOR sums. Herewith, there are different aspects in these researches, in particular, to obtain bounds of the length for the most complex functions of n variables for an arbitrary number n and to find the exact length for functions of a small number of variables. The present work is devoted to finding the exact length for functions of a small number of variables. EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs) for Boolean functions are considered in it. An EXOR Sum of Pseudo-Products, ESPP (a pseudo-polynomial form, PSPF) is an expression that is an EXOR sum of products of linear functions. The length of an ESPP is the number of its summands; the length of a function in the class of ESPPs is the smallest length among all ESPPs, representing this function. In the work, the complete classification by the length in the class of ESPPs is obtained for functions of four variables. The largest length and the average length in the class of ESPPs are found for functions of five variables.

Keywords

• boolean function
• zhegalkin polynomial
• exor sum of pseudo-products
• espp (pseudo-polynomial form, pspf)
• length
• classification by the length