UDC 519.17
1 Defense Intelligence Research Institute, Kyiv, Ukraine
 divan24@i.ua
|
2 Defense Intelligence Research Institute, Kyiv, Ukraine
rolex@i.ua
|
3 Defense Intelligence Research Institute, Kyiv, Ukraine
svs14@ukr.net
|
|
METHOD OF MODIFIED DEPTH GRAPH SEARCH FOR CONSTRUCTING
ALL POSSIBLE GRAY CODES OF A SPECIFIED LENGTH
Abstract. The problem of finding possible variants of the Gray code for the interpretation of time-frequency matrices,
which are used in the design of information transmission channels, is considered.
An undirected homogeneous incomplete circulant 4-degree graph is constructed. A method and algorithm for implementing a modified search in the graph are proposed, which can be used to construct all the Gray codes of a given length. A formula for calculating the number of variants of these codes is given.
Keywords: bitstream, time-frequency matrix, Gray code, undirected graph.
full text
REFERENCES
- Nikolaev S.N., Romanov A.N. Method for recognition of parameters of error-correcting block-cyclic codes by a generator polynomial. Cybernetics and Systems Analysis. 2021. Vol. 57, N 1. P. 146–154. https://doi.org/10.1007/s10559-021-00338-w .
- Yerokhin V.F., Roma O.M., Vasylenko S.V., Bezdrabko D.E. Mathematical model of interception of a single jump of a transmitter signal with a PPRF. Bulletin of NTUU "KPI". Radio equipment series. Radio equipment construction. 2016. N 64. P. 75–85. https://doi.org/10.20535/RADAP.2016.64.75-85.
- Mutze T., Nummenpalo J. Efficient computation of middle levels Gray codes. ACM Trans. Algorithms. 2018. Vol. 14, Iss. 2. Article 15. https://doi.org/10.1145/3170443.
- Beletsky A.Ya. Combinatorics of Gray codes [in Russian]. Kyiv: Izd. comp. "KVIC", 2003. 506 p.
- Warren H. Algorithmic tricks for programmers [Russian translation]. Moscow: OOO Dialectika-Williams, 2014. 512 p.
- Bitner J.R., Ehrlich G., Reingold E.M. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM. 1976. Vol. 19, N 9. P. 517–521. https://doi.org/10.1145/360336.360343.
- Ali Md.M., Islam M.N., Foysal A.B.M. Algorithms for generating binary reflected Gray code sequence: Time efficient approaches. Proc. 2009 International Conference on Future Computer and Communication (03–05 April 2009, Kuala Lumpar, Malaysia). Kuala Lumpar, 2009. P. 79–83. https://doi.org/10.1109/ICFCC.2009.41.
- Balakrishnan R., Ranganathan K. A Textbook of Graph Theory. New York: Springer New York, 2012. XIII, 292 p. https://doi.org/10.1007/978-1-4614-4529-6.
- Ashraf Iqbal M. Graph Theory and Algorithms. 2010. 522 p.
