|
Discrete Functions
On the decomposition of a vectorial Boolean function into a composition of two functions
G. M. Pintus Novosibirsk State University
Abstract:
In the paper, we prove that if a vectorial Boolean function $F$ in $n$ variables, $\deg(F)=d>2$, is decomposable, then the function $ F '= A_2 \circ F \circ A_1 $, where $ A_1, A_2 $ are arbitrary affine $ (n, n) $-permutations, is also decomposable; and if $F(x)=G(H(x))$, $\max\{\deg(F),\deg(H)\}=d'<d$, function $H$ is invertible and $ \deg (H ^ {- 1}) \leq d'$, then the function $ F^{''} = F + A_0 $ is decomposable for any affine function $A_0$. The construction of a decomposable vectorial Boolean function of the third degree in an arbitrary number of variables is presented. A computational experiment showed that all vectorial Boolean functions of the third degree in three variables are decomposable.
Keywords:
vectorial Boolean function, decomposition, threshold implementation.
Citation:
G. M. Pintus, “On the decomposition of a vectorial Boolean function into a composition of two functions”, Prikl. Diskr. Mat. Suppl., 2020, no. 13, 31–32
Linking options:
https://www.mathnet.ru/eng/pdma488 https://www.mathnet.ru/eng/pdma/y2020/i13/p31
|
|