Fast algorithm of enumerative encoding for main problems of information theory
Abstract
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.
References
1. 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.
2. Cover T. M. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. V. IT-19, . 1. P. 73 77.
3. 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.
4. 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.
5. 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.
6. Kautz W. Fibonacci codes for synchronization control // IEEE Transactions on Information Theory. 1965. V. 11, 2. P. 284 292.
7. Knuth D. E. Ef cient balanced codes // IEEE Transactions on Information Theory. 1986. V. IT-32. P. 51 53.
8. 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.
9. Lint J. H., van and Wilson R. M. A Course in Combinatorics. Cambridge University Press, 2001 (second edition).
10. 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.
11. Sch onhage A. and Strassen V. Schnelle Multiplikation grosser Zahlen // Computing. 1971. V. 7. P. 281 292.
12. Silberstein N. and Etzion T. Enumerative coding for Grassmannian space // IEEE Transactions on Information Theory. 2011. V. 57, 1. P. 365 374.
13. 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.
14. Skachek V. Recursive code construction for random networks // IEEE Transactions on Information Theory. 2010. V. IT-56. P. 1378 1382.
15. 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.
16. Weber, J. H., Schouhamer Immink. Knuth’s balanced codes revisited // IEEE Transactions on Information Theory. 2010. V. 56. P. 1673 1679.
17. Ахо А., Лам М., Сети P., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М.: Вильямс, 2008.
18. Кричевский P. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.
19. Медведева Ю. С. Быстрая нумерация элементов грассманиана // Вычислительные технологии. 2013. Т. 18, № 3. С. 22-33.
20. Медведева Ю. С., Рябко Б. Я. Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц. //Проблемы передачи информ. 2010. Т. 46, № 4. С. 130-139.
21. Рейнольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
22. Рябко Б. Я. Быстрая нумерация комбинаторных объектов. // Дискретная математика. 1998. Т. 10. №2. С. 101-119.
23. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004.
Review
For citations:
Medvedeva Yu... Fast algorithm of enumerative encoding for main problems of information theory. The Herald of the Siberian State University of Telecommunications and Information Science. 2013;(4):83-105. (In Russ.)
Views:
405
Email this article 