Быстрый алгоритм нумерационного кодирования для основных задач теории информации
Аннотация
Предлагается быстрый алгоритм нумерационного кодирования для основных задач теории информации, таких как: 1) кодирование двоичных слов заданной длины с заданным количеством единиц и частный случай этой задачи, когда количество единиц в слове равно количеству нулей; 2) кодирование слов с ограничением на количество подряд идущих одинаковых символов. Эта задача имеет приложение в магнитной записи и некоторых других областях; 3) кодирование элементов грассманиана и кодирование слов языков Дика. Алгоритм является модификацией метода быстрой нумерации комбинаторных объектов, предложенного Б. Рябко. Предлагаемый нами алгоритм имеет меньшую вычислительную сложность, чем другие известные алгоритмы.
Список литературы
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.
Рецензия
Для цитирования:
Медведева Ю.С. Быстрый алгоритм нумерационного кодирования для основных задач теории информации. Вестник СибГУТИ. 2013;(4):83-105.
For citation:
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.)
Просмотров:
406
Послать статью по эл. почте 