УДК 519.17
С.М. НІКОЛАЄВ
Науково-дослідний інститут воєнної розвідки, Київ, Україна, 
divan24@i.ua
О.М. РОМАНОВ
Науково-дослідний інститут воєнної розвідки, Київ, Україна, rolex@i.ua
А.М. НИЩУК
Науково-дослідний інститут воєнної розвідки, Київ, Україна, svs14@ukr.net
МЕТОД МОДИФІКОВАНОГО ПОШУКУ У ГРАФІ
ВГЛИБ ДЛЯ ПОБУДОВИ ВСІХ МОЖЛИВИХ
КОДІВ ГРЕЯ ЗАДАНОЇ ДОВЖИНИ
Анотація. Розглянуто задачу пошуку можливих варіантів коду Грея для інтерпретації частотно-часових матриць, які застосовуються під час проєктування каналів передавання інформації. Побудовано неорієнтований однорідний неповний циркулянтний граф 4-го степеня. Запропоновано метод і алгоритм реалізації модифікованого пошуку у графі, за допомогою якого можна побудувати всі коди Грея заданої довжини. Наведено формулу для обчислення кількості варіантів цих кодів.
Ключові слова: бітовий потік, частотно-часова матриця, код Грея, неорієнтований граф.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 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 .
- Єрохін В.Ф., Рома О.М., Василенко С.В., Бездрабко Д.Є. Математична модель перехоплення одиничного стрибка сигналу передавача з ППРЧ. Вісник НТУУ «КПІ». Серія Радіотехніка. Радіоапаратобудування. 2016. № 64. С. 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.
- Белецкий А.Я. Комбинаторика кодов Грея. Киев: Изд. комп. «КВІЦ», 2003. 506 с.
- Уоррен Г. Алгоритмические трюки для программистов. Москва: ООО Диалектика-Вильямс, 2014. 512 с.
- 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.
