×

On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes. (English) Zbl 1335.94022

Summary: 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'\neq 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.

MSC:

94A29 Source coding
94B35 Decoding
14G50 Applications to coding theory and cryptography of arithmetic geometry
94C99 Circuits, networks
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[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-2866 (2009). · Zbl 1190.94040
[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-407. Springer (2000). · Zbl 1082.94514
[3] Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226-241 (1978). · Zbl 0397.94012
[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-2919 (2009). · Zbl 1367.94414
[5] Etzion T., Silberstein N.: Codes and designs related to lifted MRD codes. IEEE Trans. Inf. Theory 59(2), 1004-1017 (2013). · Zbl 1364.94597
[6] Etzion T., Vardy A.: Error-correcting codes in projective space. IEEE Trans. Inf. Theory 57(2), 1165-1173 (2011). · Zbl 1366.94589
[7] Gabidulin È.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3-16 (1985). · Zbl 0585.94013
[8] Gadouleau M., Yan Z.: Constant-rank codes and their connection to constant-dimension codes. IEEE Trans. Inf. Theory 56(7), 3207-3216 (2010). · Zbl 1366.94591
[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). · Zbl 1293.94110
[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-189 (2012). · Zbl 1348.94103
[12] Hodge W.V.D., Pedoe D.: Methods of Algebraic Geometry, vol. 2. Cambridge University Press, Cambridge (1952). · Zbl 0048.14502
[13] Kipnis A., Shamir A.: Cryptanalysis of the HFE public key cryptosystem. In: Advances in Cryptology—CRYPTO’99, Santa Barbara. Lecture Notes in Computer Science, vol. 1666, pp. 19-30. Springer: Berlin (1999). · Zbl 0940.94012
[14] Kleiman S.L., Laksov D.: Schubert calculus. Am. Math. Mon. 79, 1061-1082 (1972). · Zbl 0272.14016
[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-42. Springer: Berlin (2008). · Zbl 1178.94239
[16] Kötter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579-3591 (2008). · Zbl 1318.94111
[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-885, 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-1197 (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-1492 (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-336 (1991). · Zbl 0721.94012
[23] Silberstein N., Etzion T.: Enumerative coding for Grassmannian space. IEEE Trans. Inf. Theory, 57(1), 365-374 (2011). · Zbl 1366.94261
[24] Silberstein N., Etzion T.: Large constant dimension codes and lexicodes. Adv. Math. Commun. 5(2), 177-189 (2011). · Zbl 1247.94068
[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-3967 (2008). · Zbl 1318.94119
[26] Skachek V.: Recursive code construction for random networks. IEEE Trans. Inf. Theory 56(3), 1378-1382 (2010). · Zbl 1366.94750
[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-7404 (2013). · Zbl 1364.94661
[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-15(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-549 (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-4 (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-408 (2010).
[34] Wachter-Zeh A.: Bounds on list decoding Gabidulin codes. IEEE Trans. Inf. Theory, pp. 7268-7277 (2013). · Zbl 1364.94731
[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-538 (2013). · Zbl 1335.94104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.