Organization of Structural Means for Generating Sequences of Pseudorandom Equiprobable Binary Sets
DOI:
https://doi.org/10.31861/sisiot2025.2.02016Keywords:
GL-models, fault-tolerant multiprocessor systems, generatorsAbstract
The paper presents the results of research and development of structural methods for hardware generation of pseudorandom equiprobable binary sequences. The features and limitations of existing approaches to the synthesis of pseudorandom sequence generators are analyzed, particularly those associated with fixed probability distributions or predetermined set cardinality. A new structural generation method based on cascade dichotomic decomposition of the number of possible combinations in the output sequence is proposed. This approach enables the formation of a complete set of equiprobable binary patterns of a given bit length while reducing hardware complexity. An algorithm for constructing the generator has been developed, which includes the formation of the decomposition tree, the synthesis and minimization of combinational circuits implementing parity functions, and the determination of transition probabilities between the vertices of the decomposition graph. The algorithm is presented in a formalized form, allowing for simplified implementation and analysis. It is shown that the proposed method allows calculating transition probabilities through simple ratios between decomposition components, significantly simplifying the circuit implementation of the generator. The proposed generator structure provides the formation of equiprobable pseudorandom sets regardless of the set’s cardinality. It is proven that the performance of such a generator depends not on the size of set N but on its binary logarithm, i.e., the bit width m of the generated code. The practical implementation of the method is illustrated by an example for, including the calculation of probabilities and construction of parity functions. The obtained results can be applied in the design of high-performance systems for digital device testing, modeling tools for fault-tolerant multiprocessor systems, and random data generators in digital computing technology.
Downloads
References
I. V. Maidanyuk, K. V. Morozov, E. R. Potapova, and A. V. Shuryga, “On one property of a GL-model with a minimum number of lost edges,” Scientific Bulletin of Chernivtsi University. Series: Computer Systems and Components, vol. 1, no. 2, pp. 31–34, 2010.
K. V. Morozov, E. R. Potapova, and N. K. Kichigin, “GL-model of a hierarchical system with processors at all hierarchy levels,” Proceedings of the All-Ukrainian Scientific and Practical Conference, pp. 35–37, 2016.
E. R. Potapova, A. V. Shuryga, and I. V. Maidanyuk, “On one method for modifying the edge functions of a GL-model,” Information-Control Systems in Railway Transport, no. 4, p. 48, 2012.
I. A. Yermolenko, “Method for constructing GL-models for consecutive-k-within-m-out-of-n systems,” Computer-Integrated Technologies: Education, Science, Production, no. 61, pp. 6–11, 2025, doi: 10.36910/6775-2524-0560-2025-61-01.
F. Panneton, P. L’Ecuyer, and M. Matsumoto, “Improved long-period generators based on linear recurrences modulo 2,” ACM Transactions on Mathematical Software, vol. 32, no. 1, pp. 1–16, 2006.
S. Sánchez, R. Criado, and C. Vega, “A generator of pseudo-random number sequences with a very long period,” Mathematical and Computer Modelling, vol. 42, nos. 7–8, pp. 809–816, 2005, doi: 10.1016/j.mcm.2005.09.009.
V. A. Romankevich and I. V. Maidanyuk, “Structural method for forming binary pseudorandom vectors of a given weight,” Upravlyayushchiye Sistemy i Mashin, no. 5, pp. 28–33, 58, 2011.
A. M. Romankevich, I. V. Maidanyuk, and V. A. Romankevich, “On the formation of control functions for a generator of binary vector sequences,” Radio Electronic and Computer Systems, no. 6, pp. 157–163, 2014.
V. V. Grol, V. A. Romankevich, E. R. Potapova, and S. M. Moravedge, “Structural method of generating pseudorandom sequences of a special type,” Radio Electronic and Computer Systems, no. 5, pp. 230–236, 2010.
R. P. Brent, “Some long-period random number generators using shifts and xors,” The Proceedings of ANZIAM, vol. 48, pp. C188–C202, 2006.
R. Al Shboul and V. A. Romankevich, “Structural means generating pseudorandom sequences of fixed-weight binary patterns,” International Journal of Computer Science & Network Security, vol. 17, no. 10, pp. 62–66, 2017.
Published
Issue
Section
License
Copyright (c) 2025 Security of Infocommunication Systems and Internet of Things
This work is licensed under a Creative Commons Attribution 4.0 International License.
