Polynomial expansions of Boolean functions
type: Item
instance of: scholarly article
title: Polynomial expansions of Boolean functions
zbMATH Open document ID: 0816.94030
published in: Cybernetics and Systems Analysis
publication date: 1995-05-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 41A10
Mathematics Subject Classification ID: 94-02
zbMATH DE Number: 745990
zbMATH Keywords: mod-2 adders
zbMATH Keywords: discrete logic design
zbMATH Keywords: polynomial expansion
zbMATH Keywords: Boolean functions
zbMATH Keywords: survey
author: Sergeĭ Fedorovich Vinokurov
author: Nikolay A. Peryazev
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 745990