Informatics and Applications
2020, Volume 14, Issue 2, pp 80-85
STATISTICAL PROPERTIES OF BINARY NONAUTONOMOUS SHIFT REGISTERS WITH INTERNAL XOR
- S. Yu. Melnikov
- K. E. Samouylov
Abstract
The statistical and algebraic properties of binary nonautonomous shift registers and shift registers with internal XOR are compared, during which the state vector is summed with its one-step shift. The isomorphism of transition graphs of these automata is proved. It is shown that, with a Bernoulli random input, the stationary distribution of the register states with internal XOR is uniform. The form of the probability function of these registers is obtained. It is shown that, under certain conditions on the output function, registers with internal XOR are not Cesaro-hereditary. The authors show input sequences that possess the property of stability of the relative frequencies of arbitrary multigrams, while output sequences do not have this property
[+] References (8)
- Grusho, A. A., E.A. Primenko, and E. E. Timonina.
2009. Teoreticheskie osnovy komp'yuternoy bezopasnosti
[Theoretical foundations of computer security]. Moscow: Akademiya. 267 p.
- Golomb, S.W. 1981.Shift register sequences. Laguna Hills, CA: Aegean Park Press. 247p.
- Chen, W-K., ed. 2006. The VLSI handbook. 2nd ed. Chicago, IL: CRC Press. 2320 p.
- Sachkov, V. N. 2013. Kurs kombinatornogo analiza [Combinatorial analysis course]. Izhevsk: NITS RKHD. 336 p.
- Riordan, J. 1968. Combinatorial identities. New York, NY Wiley. 256 p.
- Liu, M. 1990. Homomorphisms and automorphisms of 2-D de Bruijn-good graphs. Discrete Math. 85(1):105-109.
- Melnikov, S. Yu., and K. E. Samouylov. 2018. The recognition of the output function of a finite automaton with random input. Distributed Computer and Communication
Networks: 21st Conference (International) Revised Selected Papers. Eds. V. M. Vishnevskiy and D. V. Kozyrev. Communications in computer and information science ser. Springer. 919:525-531.
- Melnikov, S. Yu. 2004. O pererabotke konechnymi av- tomatami chezarovskikh posledovatel'nostey [On the finite automa with Cesaro sequences input]. Lesnoy Vestnik [Forestry Bull.] 1(32):169-174.
[+] About this article
Title
STATISTICAL PROPERTIES OF BINARY NONAUTONOMOUS SHIFT REGISTERS WITH INTERNAL XOR
Journal
Informatics and Applications
2020, Volume 14, Issue 2, pp 80-85
Cover Date
2020-06-30
DOI
10.14357/19922264200211
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
random input automata; shift register; de Bruijn graph
Authors
S. Yu. Melnikov  and K. E. Samouylov
Author Affiliations
Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
|