|
Theoretical Foundations of Applied Discrete Mathematics
On mixing digraphs of nonlinear substitutions for binary shift registers
V. S. Grigorievab a Financial University under the Government of the Russian Federation, Moscow
b "Positive Technologies", Moscow
Abstract:
In this paper, we research the class $R(n,m)$ of substitutions on $n$-dimensional vector space produced by the binary left-shift registers of the length $n$ with one feedback $f(x_1,\dots,x_n)=x_1\oplus\psi(x_2,\dots,x_n)$ essentially depending on $m$ variables, $3\le m\le n$. We have obtained the following double-ended estimate for the
exponent of the mixing digraphs $\Gamma(g)$ for nonlinear substitutions $g\in R(n,m)$:
$$
n+\left\lceil\frac{n-1}{m-1}\right\rceil-1\le\exp{\Gamma(g)}\le\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1,
$$
where $D(g)=\{i_1,\dots,i_m\}$ is the set of indexes of essential variables of the shift register feedback function $f$, $1=i_1<\dots<i_m\le n$, $m\le n$; $\Delta(D)=\max\{i_2-i_1,\dots,i_m-i_{m-1},n-i_m\}$. We have also obtained some upper-bound estimates for the sum and for the ratio of exponents of mixing digraphs of substitution $g\in R(n,m)$ and its inverse substitution $g^{-1}$:
\begin{gather*}
\exp{\Gamma(g)}+\exp{\Gamma(g^{-1})}\le2\left(\Delta(D)+\left\lfloor\frac{n^2}m\right\rfloor\right)+i_m,\\
\frac{\exp{\Gamma(g)}}{\exp{\Gamma(g^{-1})}}\le\frac{\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1}{n+\left\lceil\frac{n-1}{m-1}\right\rceil-1}.
\end{gather*}
Keywords:
mixing digraph approach, primitive digraph, exponent of graph, shift register, Frobenius number.
Citation:
V. S. Grigoriev, “On mixing digraphs of nonlinear substitutions for binary shift registers”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 6–9
Linking options:
https://www.mathnet.ru/eng/pdma384 https://www.mathnet.ru/eng/pdma/y2018/i11/p6
|
|