On mixing digraphs of nonlinear substitutions for binary shift registers

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₁,... ,x_n) = x₁ ф ^(x₂,... ,x_n) essentially depending on m variables, 3 ^ m ^ n. We have obtained the following double-ended estimate for the exponent of the mixing digraphs r(g) for nonlinear substitutions g £ R(n, m): - 1 ^ exp r(g) ^ A(D) + n + (n - 2)² n - 1 m1 1 n + where D = {i₁,...,i_m} is the set of indexes of essential variables of the shift register feedback function f, 1 = i₁ < ... < i_m ^ n, m ^ n; A(D) = max{i₂ - i₁,..., 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 £ R(n,m) and its inverse substitution g^-1: _n2 m A(D) + n + (n - - 2)² 2 _ -1 n+ n - 1" -1 m - 1 exp r(g) + exp r(g^-1) ^ 2 ^A(D) + + im ^exp ^r(g^{) ex}p^r(g^-1)

Keywords

Authors

References