Конструктивный подход к перечислению спектров кодов Грея в булевых кубах малых размерностей

Малых, Александр Евгеньевич; Пережогин, Алексей Львович; Malykh, Alexander Evgenievich; Perezhogin, Aleksey Lyvovich

Главная
→
Периодические издания
→
Вестник НГУ. Серия: Информационные технологии
→
Том 15 (2017)
→
IT Выпуск 4 (2017)
→
Просмотр элемента

dc.contributor.author	Малых, Александр Евгеньевич	ru_RU
dc.contributor.author	Пережогин, Алексей Львович	ru_RU
dc.contributor.author	Malykh, Alexander Evgenievich	en
dc.contributor.author	Perezhogin, Aleksey Lyvovich	en
dc.creator	Новосибирский государственный университет	ru_RU
dc.creator	ООО НЦИТ «УНИПРО»	ru_RU
dc.creator	Институт математики им. С. Л. Соболева СО РАН	ru_RU
dc.creator	Novosibirsk State University	en
dc.creator	Ltd. UNIPRO	en
dc.creator	Institute of Mathematics SB RAS	en
dc.date.accessioned	2018-01-15T12:03:51Z
dc.date.available	2018-01-15T12:03:51Z
dc.date.issued	2017-12
dc.identifier.citation	Малых А. Е., Пережогин А. Л. Конструктивный подход к перечислению спектров кодов Грея в булевых кубах малых размерностей // Вестн. НГУ. Серия: Информационные технологии. 2017. Т. 15, № 4. С. 32–42. DOI 10.25205/1818-7900-2017-15-4-32-42. ISSN 1818-7900.	ru_RU
dc.identifier.citation	Malykh A. E., Perezhogin A. L. Constructive Approach to Enumerating the Spectra of Gray Codes in Boolean Cubes of Small Dimension. Vestnik NSU. Series: Information Technologies, 2017, vol. 15, no. 4, p. 32–42. DOI 10.25205/1818-7900-2017-15-4-32-42. ISSN 1818-7900. (In Russ.)	en
dc.identifier.issn	1818-7900
dc.identifier.other	DOI 10.25205/1818-7900-2017-15-4-32-42
dc.identifier.uri	https://lib.nsu.ru/xmlui/handle/nsu/13494
dc.description.abstract	Спектром n-разрядного кода Грея называется набор из количеств изменений соответствующей позиции при переходе к следующему кодовому слову. Исследуются множества спектров кодов Грея, порождаемых различными известными конструкциями. Перечислены все спектры 7- и 8-разрядных кодов Грея.	ru_RU
dc.description.abstract	The spectrum of the n-bit Gray code is a set of the number of changes in the corresponding position in the transition to the next codeword. Spectra sets of Gray codes generated by various known constructions are investigated. All the spectra of 7- and 8-bit Gray codes are enumerated.	en
dc.language.iso	ru	ru_RU
dc.publisher	Новосибирский государственный университет
dc.subject	код Грея	ru_RU
dc.subject	гамильтонов цикл	ru_RU
dc.subject	булев куб	ru_RU
dc.subject	Gray code	en
dc.subject	Hamiltonian cycle	en
dc.subject	Boolean cube	en
dc.title	Конструктивный подход к перечислению спектров кодов Грея в булевых кубах малых размерностей	ru_RU
dc.title.alternative	Constructive Approach to Enumerating the Spectra of Gray Codes in Boolean Cubes of Small Dimension	en
dc.type	Article	ru_RU
dc.description.reference	1. Gilbert E. N. Gray codes and paths on the n-cube // Bell System Tech. J. 1958. Vol. 37. No. 3. P. 815–826. 2. Savage C. D. A survey of combinatorial Gray codes // SIAM Rev. 1996. Vol. 39. No. 4. P. 605–629. 3. Adam A. Truth functions and the problem of their realization by two-terminal graphs. Budapest: Academiai Kiado, 1968. 4. Bhat G. S., Savage C. D. Balanced Gray codes // Electron. J. Comb. 1996. Vol. 3. Research Paper 25. 5. Suparta I. N. A simple proof for the existence of exponentially balanced Gray codes // Electron. J. Comb. 2005. Vol. 12. Note 19. 6. Евдокимов А. А. О нумерации подмножеств конечного множества // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. тр. / Ин-т математики СО АН СССР, Новосибирск. 1980. Вып. 34. C. 8–26. 7. Goddyn L., Lawrence G. M., Nemeth E. Gray codes with optimized run lengths // Util. Math. 1988. Vol. 34. P. 179–192. 8. Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs // Electron. J. Comb. 2003. Vol. 10. R27. 9. Быков И. С. О локально равномерных кодах Грея // Дискрет. анализ и исслед. опер. 2016. Т. 23, № 1. С. 51–64. 10. Быков И. С., Пережогин А. Л. О дистанционных кодах Грея // Дискрет. анализ и исслед. опер. 2017. Т. 24, № 2. С. 5–17. 11. Knuth D. E. The art of computer programming. Addison; Wesley, New-Jersey, 2009. Vol. 4. 944 p. 12. Пархоменко П. П. Классификация гамильтоновых циклов в двоичных гиперкубах // Автоматика и телемеханика. 2001. № 6. С. 136–150. 13. Dejter I. J., Delgado A. A. Classes of Hamilton cycles in the 5-cube // J. Comb. Math. Comb. Comput. 2007. Vol. 61. Р. 81–95. 14. Chebiryak Yu., Kroening D. Towards a classification of Hamiltonian cycles in the 6-cube // J. Satisf., Boolean Model. Comput. 2008. Vol. 4. No. 1. P. 57–74. 15. Потапов В. Н. Построение гамильтоновых циклов с заданным спектром направлений рёбер в булевом n-мерном кубе // Дискрет. анализ и исслед. опер. 2012. Т. 19, № 2. С. 75–83. 16. Ramras M. A new method of generating Hamiltonian cycles on the n-cube // Discrete Mathematics. 1990. Vol. 85. Issue 3. P. 329–331. 17. Dixon E., Goodman S. On the number of Hamiltonian circuits in the n-cube // Proc. Amer. Math. Soc. 1975. Vol. 50. P. 500–504. 18. Douglas R. G. Bounds on the number of Hamiltonian circuits in the n-cube // Discrete Math. 1977. Vol. 17, No. 2. P. 143–146. 19. Mollard M. Un nouvel encadrement du nombre de cycles hamiltoniens du n-cube // European J. Combinatorics. 1988. Vol. 9. No. 1. P. 49–52.	ru_RU
dc.description.reference	1. Gilbert E. N. Gray codes and paths on the n-cube. Bell System Tech. J., 1958, vol. 37, no. 3, p. 815–826. 2. Savage C. D. A survey of combinatorial Gray codes. SIAM Rev., 1996, vol. 39, no. 4, p. 605–629. 3. Adam A. Truth functions and the problem of their realization by two-terminal graphs. Budapest, Academiai Kiado, 1968. 4. Bhat G. S., Savage C. D. Balanced Gray codes. Electron. J. Comb., 1996, vol. 3, research paper 25. 5. Suparta I. N. A simple proof for the existence of exponentially balanced Gray codes. Electron. J. Comb., 2005, vol. 12, note 19. 6. Evdokimov A. A. On enumeration of subsets of a finite set. Methods of Discrete Analysis for Solving Combinatorial Problems, 34, Novosibirsk, Izd. Inst. Mat., 1980, p. 8–26 (In Russ.). 7. Goddyn L., Lawrence G. M., Nemeth E. Gray codes with optimized run lengths. Util. Math., 1988, vol. 34, p. 179–192. 8. Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs. Electron. J. Comb., 2003, vol. 10, R27. 9. Bykov I. S. On locally balanced Gray codes. J. Appl. Ind. Math., 2016, vol. 10, issue 1, p. 78–85. 10. Bykov S., Perezhogin A. L. On distance Gray codes. J. Appl. Ind. Math., 2016, vol. 11, issue 2, p. 185–192. 11. Knuth D. E. The art of computer programming, vol. 4. Addison, Wesley, New-Jersey, 2009, 944 pp. 12. Parkhomenko P. P. Classification of the Hamiltonian Cycles in Binary Hypercubes. Automation and Remote Control, 2001, vol. 62, no. 6, p. 978–991. 13. Dejter I. J., Delgado A. A. Classes of Hamilton cycles in the 5-cube. J. Comb. Math. Comb. Comput., 2007, vol. 61, p. 81–95. 14. Chebiryak Yu., Kroening D. Towards a classification of Hamiltonian cycles in the 6-cube. J. Satisf., Boolean Model. Comput., 2008, vol. 4, no. 1, p. 57–74. 15. Potapov V. N. Construction of Hamiltonian cycles with a given spectrum of edge directions in an n-dimensional Boolean cube. J. Appl. Ind. Math., 2012, vol. 6, issue 3, p. 339–345. 16. Ramras M. A new method of generating Hamiltonian cycles on the n-cube. Discrete Math., 1990, vol. 85, issue 3, p. 329–331. 17. Dixon E., Goodman S. On the number of Hamiltonian circuits in the n-cube. Proc. Amer. Math. Soc., 1975, vol. 50, p. 500–504. 18. Douglas R. G. Bounds on the number of Hamiltonian circuits in the n-cube. Discrete Math., 1977, vol. 17, no. 2, p. 143–146. 19. Mollard M. Un nouvel encadrement du nombre de cycles hamiltoniens du n-cube. European J. Combinatorics, 1988, vol. 9, no. 1, p. 49–52.	en
dc.subject.udc	519.174.2
dc.relation.ispartofvolume	15
dc.relation.ispartofnumber	4
dc.relation.ispartofpages	32-42