Abstract:
Some properties of the output sequence of a finite-state generator $G=A_1\cdot A_2$, 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$, having the maximum period equal to $2^{n+m}$, are described. Let $z=z(1)\ldots z(2^{n+m})$ be the initial segment of the generator output sequence, $N=\text{wt}(z)$, and $i_1,\ldots,i_N$ — numbers of positions where $z$ contains ones. Then: 1) if $m\geq n$, then there exists a generator $G$ that outputs a sequence $z$ of any weight $N$, $0\leq N\leq 2^{n+m}$; 2) if, for given $m, n$ and any $N$, $0\leq N\leq 2^{n+m}$, there exists a generator $G$ that outputs a sequence $z$ of weight $N$, then $m\geq n-1$; 3) if $N=2^l$, $0<l<n$, then $i_1\equiv i_2\equiv\ldots\equiv i_N\pmod{2^n}$; 4) if $N<2^n$ and $N$ is prime, then either $i_1\equiv\ldots\equiv i_N\pmod{2^n}$, or all values $i_1,\ldots,i_N$ are pairwise distinct modulo $2^n$.
Keywords:finite-state generator, maximum period, sequence weight.
Fulltext:
PDF file (499 kB)