RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2019 Issue 12, Pages 29–31 (Mi pdma423)

Theoretical Foundations of Applied Discrete Mathematics

Exact formula for exponent of mixing digraph of feedback shift register

V. M. Fomichevabc, Ya. E. Avezovad

a National Engineering Physics Institute "MEPhI", Moscow
b Financial University under the Government of the Russian Federation, Moscow
c Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow
d АО «Позитив Текнолоджиз»

Abstract: Let $g$ be a binary $n$-stage nonlinear shift register with feedback $f(x_0,\ldots,x_{n-1})$ and $\Gamma(g)$ denotes a mixing digraph of transformation $g$. By $d_m$ we denote the greatest number of essential variable of $f$. For primitive digraph $\Gamma(g)$, we obtain the exact formulas for exponent of $\Gamma(g)$ for $d_m\in\{n-1,n-2\}$ and of local exponents $\gamma_{u,v}$ for $0\leq u,v<n$.

Keywords: local primitivity of digraph, mixing digraph, primitive digraph, shift register, digraph exponent.

UDC: 519.1

DOI: 10.17223/2226308X/12/8



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024