Polynomial expansions of Boolean functions (Q1842415): Difference between revisions

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.