sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-430Research ArticleСтатьиБыстрый алгоритм нумерационного кодирования для основных задач теории информацииFast algorithm of enumerative encoding for main problems of information theoryМедведеваЮ. С.MedvedevaYu. ..brainwashed@yandex.ruИВТ СО РАНRussian Federation2013261020220483105Copyright © Медведева Ю.С., 20222022Медведева Ю.С.Medvedeva Y...Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/430

Предлагается быстрый алгоритм нумерационного кодирования для основных задач теории информации, таких как: 1) кодирование двоичных слов заданной длины с заданным количеством единиц и частный случай этой задачи, когда количество единиц в слове равно количеству нулей; 2) кодирование слов с ограничением на количество подряд идущих одинаковых символов. Эта задача имеет приложение в магнитной записи и некоторых других областях; 3) кодирование элементов грассманиана и кодирование слов языков Дика. Алгоритм является модификацией метода быстрой нумерации комбинаторных объектов, предложенного Б. Рябко. Предлагаемый нами алгоритм имеет меньшую вычислительную сложность, чем другие известные алгоритмы.

We propose the algorithm of fast enumeration for main problems of coding theory. These problems are: 1) encoding of binary words with given number of ones and its special case when number of ones equals number of zeroes; 2) encoding of run-length-constrained words. This problem is of interest to magnetic recording and some other fields; 3) encoding of the Grassmannian space elements and encoding of the Dyck language words. We apply the modification of method of fast enumeration of combinatorial objects proposed by B. Ryabko to stated problems. Our algorithm has less computational complexity than other known algorithms do.

кодированиенумерационное кодированиетеория информацииencodingenumerative encodinginformation theoryReferencesBeenker G. F. M., Immink K. A. S. A generalized method for encoding and decoding runlength-limited binary sequences // IEEE Transactions on Information Theory. 1983. V. 29,  3. P. 751 754.Beenker G. F. M., Immink K. A. S. A generalized method for encoding and decoding runlength-limited binary sequences // IEEE Transactions on Information Theory. 1983. V. 29,  3. P. 751 754.Cover T. M. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. V. IT-19, . 1. P. 73 77.Cover T. M. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. V. IT-19, . 1. P. 73 77.Datta S. and McLaughlin S. W. An enumerative method for runlength-limited codes: permutation codes // IEEE Transactions on Information Theory. 1999. V. IT-45,  6. P. 2199 -2204.Datta S. and McLaughlin S. W. An enumerative method for runlength-limited codes: permutation codes // IEEE Transactions on Information Theory. 1999. V. IT-45,  6. P. 2199 -2204.F uhrer M. Faster integer multiplication // Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007). San Diego, California, USA. 2007. P. 57 -66.F uhrer M. Faster integer multiplication // Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007). San Diego, California, USA. 2007. P. 57 -66.Gadouleau M. and Yan Z. Constant-rank codes and their connection to constant-dimension codes // IEEE Transactions on Information Theory. 2010. V. IT-56. P. 3207 3216.Gadouleau M. and Yan Z. Constant-rank codes and their connection to constant-dimension codes // IEEE Transactions on Information Theory. 2010. V. IT-56. P. 3207 3216.Kautz W. Fibonacci codes for synchronization control // IEEE Transactions on Information Theory. 1965. V. 11,  2. P. 284 292.Kautz W. Fibonacci codes for synchronization control // IEEE Transactions on Information Theory. 1965. V. 11,  2. P. 284 292.Knuth D. E. Ef cient balanced codes // IEEE Transactions on Information Theory. 1986. V. IT-32. P. 51 53.Knuth D. E. Ef cient balanced codes // IEEE Transactions on Information Theory. 1986. V. IT-32. P. 51 53.Koetter R. and Kshcischang F. R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. 2008. V. 54,  8. P. 3579 3591.Koetter R. and Kshcischang F. R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. 2008. V. 54,  8. P. 3579 3591.Lint J. H., van and Wilson R. M. A Course in Combinatorics. Cambridge University Press, 2001 (second edition).Lint J. H., van and Wilson R. M. A Course in Combinatorics. Cambridge University Press, 2001 (second edition).Milenkovic O. and Vasic B. Permutation (d; k)-codes: ef cient enumerative coding and phrase length distribution shaping // IEEE Transactions on Information Theory. 2000. V. IT-46,  7. P. 2671 2675.Milenkovic O. and Vasic B. Permutation (d; k)-codes: ef cient enumerative coding and phrase length distribution shaping // IEEE Transactions on Information Theory. 2000. V. IT-46,  7. P. 2671 2675.Sch onhage A. and Strassen V. Schnelle Multiplikation grosser Zahlen // Computing. 1971. V. 7. P. 281 292.Sch onhage A. and Strassen V. Schnelle Multiplikation grosser Zahlen // Computing. 1971. V. 7. P. 281 292.Silberstein N. and Etzion T. Enumerative coding for Grassmannian space // IEEE Transactions on Information Theory. 2011. V. 57,  1. P. 365 374.Silberstein N. and Etzion T. Enumerative coding for Grassmannian space // IEEE Transactions on Information Theory. 2011. V. 57,  1. P. 365 374.Silberstein N. and Etzion T. Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams // IEEE Transactions on Information Theory. 2009. V. IT-55. P. 2909 2919.Silberstein N. and Etzion T. Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams // IEEE Transactions on Information Theory. 2009. V. IT-55. P. 2909 2919.Skachek V. Recursive code construction for random networks // IEEE Transactions on Information Theory. 2010. V. IT-56. P. 1378 1382.Skachek V. Recursive code construction for random networks // IEEE Transactions on Information Theory. 2010. V. IT-56. P. 1378 1382.Tang D. T., Bahl L. R. Block codes for a class of constrained noiseless channels // Information and Control. 1970. V. 17,  5. P. 436 461.Tang D. T., Bahl L. R. Block codes for a class of constrained noiseless channels // Information and Control. 1970. V. 17,  5. P. 436 461.Weber, J. H., Schouhamer Immink. Knuth’s balanced codes revisited // IEEE Transactions on Information Theory. 2010. V. 56. P. 1673 1679.Weber, J. H., Schouhamer Immink. Knuth’s balanced codes revisited // IEEE Transactions on Information Theory. 2010. V. 56. P. 1673 1679.Ахо А., Лам М., Сети P., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М.: Вильямс, 2008.Ахо А., Лам М., Сети P., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М.: Вильямс, 2008.Кричевский P. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.Кричевский P. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.Медведева Ю. С. Быстрая нумерация элементов грассманиана // Вычислительные технологии. 2013. Т. 18, № 3. С. 22-33.Медведева Ю. С. Быстрая нумерация элементов грассманиана // Вычислительные технологии. 2013. Т. 18, № 3. С. 22-33.Медведева Ю. С., Рябко Б. Я. Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц. //Проблемы передачи информ. 2010. Т. 46, № 4. С. 130-139.Медведева Ю. С., Рябко Б. Я. Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц. //Проблемы передачи информ. 2010. Т. 46, № 4. С. 130-139.Рейнольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.Рейнольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.Рябко Б. Я. Быстрая нумерация комбинаторных объектов. // Дискретная математика. 1998. Т. 10. №2. С. 101-119.Рябко Б. Я. Быстрая нумерация комбинаторных объектов. // Дискретная математика. 1998. Т. 10. №2. С. 101-119.Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004.Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004.

The authors declare that there are no conflicts of interest present.