Finite-state generators with maximal period

E. S. Prudnikov

Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 152-154

Résumé

The periodic properties of a two-stage finite-state generator $G=A_1\cdot A_2$ are studied, where $A_1=(\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous), $A_2 = (\mathbb{F}_2,\mathbb{F}_2^m,\mathbb{F}_2,g_2,f_2)$, $n,m\geq 1$. Some necessary conditions for such a generator with the maximum period are formulated, namely: 1) the output sequence of $A_1$ is purely periodic and the period length is $2^n$; 2) the function $f_1$ has an odd weigth; 3) substitutions $g(0,\cdot)$ and $g(1,\cdot)$ have different parities. Some sufficient conditions have been also formulated, for example, the function $g_2(u,y)$ must be injective in $u$ and the weigth of the function $f_2$ must be odd. A method for constructing a generator having maximum period has been proposed.

Détail

Keywords: finite-state generator, maximum period
Mots-clés : substitutions.