Polynomial expansions of Boolean functions
One of the basic stages in discrete logic design is the representation of Boolean functions by various formulas in a given basis. So far, the basis has predominantly consisted of elements realizing the functions of conjunction, disjunction, and negation. Recent advances in integrated circuits, however, have led to increased acceptance of components that include ``mod-2 adders as basis elements. This focuses the attention on polynomial expansion of Boolean functions. Our article reviews the results obtained in this direction. The polynomial expansion of Boolean functions, which is obtained from the Shannon expansion by replacing disjunction with ``mod-2 addition, and also the canonical forms based on this expansion (the polynomial perfect normal form and the Zhegalkin polynomial) are well known. Many publications deal with minimization of these forms and their mutual transformation. These forms, however, do not exhaust all the canonical forms of Boolean functions with external ``modulo-2 addition. Polynomial forms with elementary terms containing the implication function have been studied in [\textit{G. S. Avsarkisyan}, Avtomat. Vychislit. Tekhn. 1977, No. 1, 8-11 (1977; Zbl 0348.94044)]. Further studies of G. S. Avsarkisyan and the present authors have shown that a wide range of functions, not necessarily binary, may be used in elementary terms. In this survey, by polynomial expansions we mean representations of Boolean functions in the form of a many-place modulo-2 sum of some terms. The results are presented from general to particular. The survey does not consider issues of computational complexity of the expansion coefficients, minimization of canonical-form representation, and automatic construction of polynomial forms. These topics deserve a separate treatment.
- Polynomial expansions of Boolean functions in images of nonhomogeneous operators
- Structure of modulo-2 ring-sum canonical expansions for boolean functions
- Polynomial expansions of Boolean functions with respect to nondegenerate functions
- An expansion of Boolean function into a sum of products of subfunctions
- scientific article; zbMATH DE number 3959283
- Representation of Boolean functions by arithmetic polynomials
- Boolean polynomials and set functions
- Representation of Boolean functions by polynomial forms
- Polynomial expansions of Boolean functions with respect to nondegenerate functions
- scientific article; zbMATH DE number 5924797 (Why is no real title available?)
- The complexity of the representation of multiple-output Boolean functions
- Disjoint Boolean Products via Shannon's Expansion
- scientific article; zbMATH DE number 3959283 (Why is no real title available?)
- Structure of modulo-2 ring-sum canonical expansions for boolean functions
- An expansion of Boolean function into a sum of products of subfunctions
- scientific article; zbMATH DE number 2033418 (Why is no real title available?)
- scientific article; zbMATH DE number 2058395 (Why is no real title available?)
- Mahler's expansion and Boolean functions
- Criteria for a Boolean function to be a repetition-free in the pre-elementary bases of rank 3
- Polynomial expansions of Boolean functions in images of nonhomogeneous operators
- Complexity of Boolean functions in a class of canonical polarized polynomials
- Generalized polynomial forms of Boolean functions and design of multioutput logic circuits
This page was built for publication: Polynomial expansions of Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1842415)
