On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes

详细信息    查看全文

• 作者：Joachim Rosenthal (1)
  Natalia Silberstein (2)
  Anna-Lena Trautmann (3)
  
• 关键词：Grassmannian ; Projective space ; Subspace codes ; Network coding ; List decoding ; 11T71 ; 14G50
• 刊名：Designs, Codes and Cryptography
• 出版年：2014
• 出版时间：November 2014
• 年：2014
• 卷：73
• 期：2
• 页码：393-416
• 全文大小：298 KB
• 参考文献：1. Bossert M., Gabidulin E.M.: One family of algebraic codes for network coding. In: Proceedings of the IEEE International Symposium on Information Theory, pp. 2863-866 (2009).
  2. Courtois N., Klimov A., Patarin J., Shamir A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Advances in cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Computer Science, vol. 1807, pp. 392-07. Springer (2000).
  3. Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226-41 (1978).
  4. Etzion T., Silberstein N.: Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams. IEEE Trans. Inf. Theory 55(7), 2909-919 (2009).
  5. Etzion T., Silberstein N.: Codes and designs related to lifted MRD codes. IEEE Trans. Inf. Theory 59(2), 1004-017 (2013).
  6. Etzion T., Vardy A.: Error-correcting codes in projective space. IEEE Trans. Inf. Theory 57(2), 1165-173 (2011).
  7. Gabidulin è.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3-6 (1985).
  8. Gadouleau M., Yan Z.: Constant-rank codes and their connection to constant-dimension codes. IEEE Trans. Inf. Theory 56(7), 3207-216 (2010).
  9. Guruswami V., Wang C.: Explicit rank-metric codes list-decodable with optimal redundancy, arXiv:1311.7084 [cs.IT] (2013).
  10. Guruswami V., Xing C.: List decoding Reed–Solomon, algebraic–geometric, and Gabidulin subcodes up to the singleton bound, electronic collloquium on computationl complexity. Report No. 146 (2012).
  11. Guruswami V., Narayanan S., Wang C.: List decoding subspace codes from insertions and deletions. In: Proceedings of Innovations in Theoretical Computer Science (ITCS 2012), pp. 183-89 (2012).
  12. Hodge W.V.D., Pedoe D.: Methods of Algebraic Geometry, vol. 2. Cambridge University Press, Cambridge (1952).
  13. Kipnis A., Shamir A.: Cryptanalysis of the HFE public key cryptosystem. In: Advances in Cryptology—CRYPTO-9, Santa Barbara. Lecture Notes in Computer Science, vol. 1666, pp. 19-0. Springer: Berlin (1999).
  14. Kleiman S.L., Laksov D.: Schubert calculus. Am. Math. Mon. 79, 1061-082 (1972).
  15. Kohnert A., Kurz S.: Construction of large constant-dimension codes with a prescribed minimum distance. Lecture Notes in Computer Science, vol. 5393, pp. 31-2. Springer: Berlin (2008).
  16. K?tter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579-591 (2008).
  17. Manganiello F.. Gorla E., Rosenthal J.: Spread codes and spread decoding in network coding. In: Proceedings of International Symposium on Information Theory, pp. 881-85, Toronto, ON, Canada (2008).
  18. Mahdavifar H., Vardy A.: Algebraic list-decoding on the operator channel. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 1193-197 (2010).
  19. Mahdavifar H., Vardy A.: List-decoding of subspace codes and rank-metric codes up to Singleton bound. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 1483-492 (2012).
  20. Procesi C.: A primer of invariant theory. Brandeis Lecture Notes, Brandeis University, 1982, Notes by G. Boffi
  21. Rosenthal J., Trautmann A.-L.: Decoding of subspace codes, a problem of schubert calculus over finite fields. Mathematical System Theory—Festschrift in Honor of Uwe Helmke on the Occasion of his Sixtieth Birthday, CreateSpace (2012).
  22. Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory, 37(2), 328-36 (1991).
  23. Silberstein N., Etzion T.: Enumerative coding for Grassmannian space. IEEE Trans. Inf. Theory, 57(1), 365-74 (2011).
  24. Silberstein N., Etzion T.: Large constant dimension codes and lexicodes. Adv. Math. Commun. 5(2), 177-89 (2011).
  25. Silva D., Kschischang F.R., K?tter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory, 54(9), 3951-967 (2008).
  26. Skachek V.: Recursive code construction for random networks. IEEE Trans. Inf. Theory 56(3), 1378-382 (2010).
  27. Thomae E., Wolf C.: Solving systems of multivariate quadratic equations over finite fields or: from relinearization to MutantXL, Cryptology ePrint Archive, Report 2010/596, 2010, http://eprint.iacr.org/.
  28. Trautmann A.-L., Manganiello F., Braun M., Rosenthal J.: Cyclic orbit codes. IEEE Trans. Inf. Theory 59(11), 7386-404 (2013).
  29. Trautmann A.-L.: Plücker embedding of cyclic orbit codes. In: Proceedings of the 20th International Symposium on Mathematical Theory of Networks and Systems—MTNS, Melbourne, pp. 1-5(2012).
  30. Trautmann A.-L., Silberstein N., Rosenthal J.: List decoding of lifted Gabidulin codes via the Plücker embedding. In: Preproceedings of the International Workshop on Coding and Cryptography (WCC), Bergen, Norway, pp. 539-49 (2013).
  31. Trautmann A.L.: Constructions, decoding and automorphisms of subspace codes. PhD thesis, University of Zurich, Switzerland (2013).
  32. Trautmann A.-L., Manganiello F., Rosenthal J.: Orbit codes—a new concept in the area of network coding. In: Proceedings of IEEE Information Theory Workshop (ITW), Dublin, Ireland, pp. 1- (2010).
  33. Trautmann A.-L., Rosenthal J.: New improvements on the Echelon–Ferrers construction. In: Proceedings of the International Symposium on Mathematical Theory of Networks and Systems, pp. 405-08 (2010).
  34. Wachter-Zeh A.: Bounds on list decoding Gabidulin codes. IEEE Trans. Inf. Theory, pp. 7268-277 (2013).
  35. Wachter-Zeh A., Zeh A.: Interpolation-based decoding of interleaved Gabidulin codes. In: Preproceedings of the International Workshop on Coding and Cryptography (WCC), Bergen, Norway, pp. 528-38 (2013).
  
• 作者单位：Joachim Rosenthal (1)
  Natalia Silberstein (2)
  Anna-Lena Trautmann (3)
  
  1. Institute of Mathematics, University of Zurich, Zurich, Switzerland
  2. Department of Computer Science, Technion—Israel Institute of Technology, Haifa, Israel
  3. Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC, Australia
  
• ISSN：1573-7586

文摘

The finite Grassmannian \(\mathcal {G}_{q}(k,n)\) is defined as the set of all \(k\) -dimensional subspaces of the ambient space \(\mathbb {F}_{q}^{n}\) . Subsets of the finite Grassmannian are called constant dimension codes and have recently found an application in random network coding. In this setting codewords from \(\mathcal {G}_{q}(k,n)\) are sent through a network channel and, since errors may occur during transmission, the received words can possibly lie in \(\mathcal {G}_{q}(k',n)\) , where \(k'\ne k\) . In this paper, we study the balls in \(\mathcal {G}_{q}(k,n)\) with center that is not necessarily in \(\mathcal {G}_{q}(k,n)\) . We describe the balls with respect to two different metrics, namely the subspace and the injection metric. Moreover, we use two different techniques for describing these balls, one is the Plücker embedding of \(\mathcal {G}_{q}(k,n)\) , and the second one is a rational parametrization of the matrix representation of the codewords. With these results, we consider the problem of list decoding a certain family of constant dimension codes, called lifted Gabidulin codes. We describe a way of representing these codes by linear equations in either the matrix representation or a subset of the Plücker coordinates. The union of these equations and the linear and bilinear equations which arise from the description of the ball of a given radius provides an explicit description of the list of codewords with distance less than or equal to the given radius from the received word.