This article is cited in 1 paper

Discrete Functions

On the construction of invertible vector Boolean functions

I. A. Pankratova, P. R. Garchukova

Tomsk State University

Abstract: The following construction of a vector Boolean function is considered: $G(x)=\big(f(x),f(\pi(x)),f(\pi^2(x)),\ldots,f(\pi^{n-1}(x))\big)$, where $\pi(i)=i\bmod n+1$, $f$ is a $n$-dimensional Boolean function. An algorithm for constructing such a function with the invertibility property has been proposed; its completeness and correctness have been proven; the number $t(n)$ of invertible functions of type $G$ has been calculated: $t(n)=\prod\limits_{d|n}p(d)! d^{p(d)}$, where $p(d)$ is the number of binary Lyndon words of length $d$. If $\pi$ is an arbitrary full-cycle substitution (not necessarily a cyclic shift), then the number of invertible functions of type $G$ is $(n-1)!$ times greater.

Keywords: vector Boolean functions, invertible functions, cyclically equivalent vectors, Lyndon words.

UDC: 519.7

DOI: 10.17223/2226308X/17/10