|
This article is cited in 1 scientific paper (total in 1 paper)
Theoretical Backgrounds of Applied Discrete Mathematics
Linear decomposition of Boolean functions into a sum or a product of components
A. V. Cheremushkin Technology Federal State Unitary Enterprise "Research Institute Kvant", Moscow, Russia
Abstract:
Let $f\colon\operatorname{GF}(2)^n\to\operatorname{GF}(2)$ be a Boolean function, $n\ge2$, and $\mathcal U_s$ be a set of Boolean functions $f$ of degree $\operatorname{deg}f\le s$. Here is a consideration of the disjunctive decomposition of $f$ into sum and products modulo $\mathcal U_s$ of Boolean functions after a linear substitution on arguments. The main result is the following: if all arguments of the functions $f(xA)$ under linear substitutions $A$ of the vector space $\operatorname{GF}(2)^n$ are essential modulo $\mathcal U_s$ and $f$ may be represented as disjunctive sum $f\equiv f_1\oplus\dots\oplus f_m\pmod{\mathcal U_s}$, where $m$ is maximal, then subsequent direct sum of subspaces $\operatorname{GF}(2)^n=V^{(1)}+\dots+V^{(m)}$ is unique and invariant under stabilizer group of the function $f$ in general linear group. The article contains analogous result describing sufficient uniqueness condition for disjunctive products $f\equiv f_1\dots f_m\pmod{\mathcal U_s}$, namely, every function $f_i$ has no affine multipliers and the set $\{a\in V_i\colon f_i(x\oplus a)\oplus f_i(x)\ \text{has affine multipliers}\}$ generates the whole subspace $V_i$, $i=1,\dots,m$. For instance, this class of functions contains a nondegenerated quadratic forms.
Keywords:
Boolean functions, disjunctive decomposition, disjunctive sum, disjunctive products, linear transformation.
Citation:
A. V. Cheremushkin, “Linear decomposition of Boolean functions into a sum or a product of components”, Prikl. Diskr. Mat., 2018, no. 40, 10–22
Linking options:
https://www.mathnet.ru/eng/pdm619 https://www.mathnet.ru/eng/pdm/y2018/i2/p10
|
Statistics & downloads: |
Abstract page: | 256 | Full-text PDF : | 96 | References: | 27 |
|