Exponents of mixing digraphs associated with one and two feedbacks shift registers

A. M. Koreneva

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 84-87

Résumé

Let $n>k\ge1$, $r>1$. Denote by $\operatorname{MAG}(n,r,k)$ a set of modified additive generators based on $k$-feedback shift registers of a length $n$ over the set $V_r$ of all the binary vectors of a length $r$. Let $g$ and $\mu$ be some permutations on $V_r$, $g$ modifies the feedback of a register in $\operatorname{MAG}(n,r,1)$, $g$ and $\mu$ modify feedbacks of a register in $\operatorname{MAG}(n,r,2)$. Let $\varphi^g$ and $\varphi^{g,\mu}$ be transformations of the vector space $(V_r)^n$ produced by these registers respectively, and $\Gamma(\varphi^g)$ and $\Gamma(\varphi^{g,\mu})$ be mixing digraphs associated with $\varphi^g$ and $\varphi^{g,\mu}$. This paper presents some results of analysing the exponent estimations for $\Gamma(\varphi^g)$ and $\Gamma(\varphi^{g,\mu})$. The value $\zeta=\exp\Gamma(\varphi^g)-\exp\Gamma(\varphi^{g,\mu})$ is positive for a large number of parameter values. It is shown that $\zeta\le\exp\Gamma(\varphi^g)/2$. The smallest value of $\exp\Gamma(\varphi^g)$ equals $n+1$ and the smallest value of $\exp\Gamma(\varphi^{g,\mu})$ equals $\lceil n/2\rceil+1$. This means that mixing properties of $\varphi^{g,\mu}$ can be improved up to 2 times compared to mixing properties of $\varphi^g$.

Détail

Keywords: mixing properties, modified additive generator, feedback shift register, exponent of digraph.