Инд. авторы:	Медведева Ю.С.
Заглавие:	Быстрая нумерация элементов грассманиана
Библ. ссылка:	Медведева Ю.С. Быстрая нумерация элементов грассманиана // Вычислительные технологии. - 2013. - Т.18. - № 3. - С.22-33. - ISSN 1560-7534. - EISSN 2313-691X.
Внешние системы:	РИНЦ: 20133556;
Реферат:	eng: The Grassmannian G q(n,k) is the set of all k-dimensional subspaces of vector space F n q. The coding of elements of Grassmannian was considered in many papers and has the application in network coding. We present the advanced algorithm of the enumerative coding of the elements of the Grassmannian, which has less computational complexity than other known algorithms of coding of Grassmannian elements do. rus: Грассманиан G q(n, k) — множество всех k-мерных подпространств векторного пространства F n q над конечным полем размера q. Задача кодирования элементов грассманиана рассматривалась во многих работах и находит применение в сетевом кодировании. В настоящей работе предлагается нумерационный метод кодирования элементов грассманиана, превосходящий по скорости методы кодирования элементов грассманиана, известные ранее.
Ключевые слова:	теория информации; быстрое кодирование; нумерационное кодирование; кодирование; Information theory; Coding;
Издано:	2013
Физ. характеристика:	с.22-33
Цитирование:	1. Knuth D.E. Subspaces, subsets and partitions // J. of Combinat. Theory. 1971. Vol. 10. P. 178-189. 2. Thomas S. Designs over finite fields // Geometriae Dedicata. 1987. Vol. 21. P. 237-242. 3. Martin W.J, Zhu X.J. Anticodes for the Grassman and biliniar forms graphs // Designs, Codes and Crypt. 1995. Vol. 6. P. 72-79. 4. Tomas S. Designs and partial geometries over finite fields// Geometriae Dedicata. 1996. Vol. 63. P. 247-253. 5. Ahlswede R., Aydinian H.K, Khachatrian L.H. On perfect codes and related concepts // Designs, Codes and Crypt. 2001. Vol. 22. P. 221-237. 6. Schwartz M., Etzion T. Codes and anticodes in the Grassman graph // J. of Combinat. Theory. Ser. A. 2002. Vol. 97. P. 27-42. 7. Braun M., Kerber A, Laue R. Systematic construction of q-analogs of t - (v, k, A)-designs // Designs, Codes and Crypt. 2005. Vol. 34. P. 55-70. 8. Koetter R, Kshcischang F.R. Coding for errors and erasures in random network coding // IEEE Trans. Inform. Theory. 2008. Vol. 54, No. 8. P. 3579-3591. 9. Xia S.T, Fu F.W. Johnson type bounds on constant dimension codes // Designs, Codes and Crypt. 2009. Vol. 50. P. 163-172. 10. Etzion T, Vardy A. Error-correcting codes in projective space // Proc. Intern. Symp. on Inform. Theory. Toronto, 2008. P. 871-875. 11. Manganiello F., Gorla E., Rosenthal J. Spread codes and spread decoding in network coding // Proc. Intern. Symp. on Inform. Theory. Toronto, 2008. P. 881-885. 12. Silva D., Kschischang F.R, Koetter R. A rank-metric approach to error control in random network coding // IEEE Trans. on Inform. Theory. 2008. Vol. IT-54. P. 3951-3967. 13. Silva D., Kschischang F.R. On metric for error correction in network coding // Ibid. 2009. Vol. IT-54. P. 5479-5490. 14. Gadouleau M., Yan Z. Constant-rank codes and their connection to constant-dimension codes // Ibid. 2010. Vol. IT-56. P. 3207-3216. 15. Gadouleau M., Yan Z. On the decoder error probability of bounded rank distance decoders for maximum rank distance codes // Ibid. 2008. Vol. IT-54. P. 3202-3206. 16. Gadouleau M., Yan Z. Construction and Covering Properties of Constant-Dimension Codes. http://arxiv.org/abs/0903.2675 17. Etzion T, Silberstein N. Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams // IEEE Trans. Inform. Theory. 2009. Vol. IT-55. P. 2909-2919. 18. Kohnert A., Kurz S. Construction of large constant dimension codes with a prescribed minimum distance // Lecture Notes Comput. Sci. 2008. Vol. 5393. P. 31-42. 19. Skachek V. Recursive code construction for random networks // IEEE Trans. Inform. Theory. 2010. Vol. IT-56. P. 1378-1382. 20. Silberstein N, Etzion T. Enumerative Coding for Grassmannian Space. http://arxiv.org/abs/0911.3256 21. Fuerer M. Faster integer multiplication // Proc. of the Thirty-Ninth Annual ACM Symp. on Theory of Comput. San Diego, California, USA. 2007. 22. Ryabko B.Ya. The fast enumeration of combinatorial objects // Discrete Math. and Appl. 1998. Vol. 10, No. 2. 23. Van Lint J.H, Wilson R.M. A Course in Combinatorics. Cambridge Univ. Press, 2001. 24. Cover T.M. Enumerative source encoding // IEEE Trans. Inform. Theory. 1973. Vol. IT-19, No. 1. P. 73-77. 25. Etzion T, Silberstein N. Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams // Ibid. 2009. Vol. IT-55. P. 2909-2919. 26. Knuth D.E. The Art of Computer Programming. Seminumerical Algorithms. Third Ed. Addison-Wesley, 1997. Vol. 2. 27. Ахо A.В., Лам М.С., Сети Р., Ульман Дж.Д. Компиляторы. Принципы, технологии и инструментарий. М.: Вильямс, 2008.