|
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(x1,…,xn)=x1⊕ψ(x2,…,xn) essentially depending on m variables, 3⩽m⩽n. We have obtained the following double-ended estimate for the
exponent of the mixing digraphs Γ(g) for nonlinear substitutions g∈R(n,m):
n+⌈n−1m−1⌉−1⩽expΓ(g)⩽Δ(D)+n+⌊(n−2)22⌋−1,
where D(g)={i1,…,im} is the set of indexes of essential variables of the shift register feedback function f, 1=i1<⋯<im⩽n, m⩽n; Δ(D)=max. 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
|
Statistics & downloads: |
Abstract page: | 218 | Full-text PDF : | 62 | References: | 33 |
|