Article Contents
Article Contents

# Large constant dimension codes and lexicodes

• Constant dimension codes, with a prescribed minimum distance, have found recently an application in network coding. All the codewords in such a code are subspaces of $\mathbb F$qn with a given dimension. A computer search for large constant dimension codes is usually inefficient since the search space domain is extremely large. Even so, we found that some constant dimension lexicodes are larger than other known codes. We show how to make the computer search more efficient. In this context we present a formula for the computation of the distance between two subspaces, not necessarily of the same dimension.
Mathematics Subject Classification: Primary: 14M15, 94B60; Secondary: 94B65.

 Citation:

•  [1] G. E. Andrews and K. Eriksson, "Integer Partitions,'' Cambridge University Press, 2004. [2] J. H. Conway and N. J. A. Sloane, Lexicographic codes: error-correcting codes from game theory, IEEE Trans. Inform. Theory, 32 (1986), 337-348.doi: 10.1109/TIT.1986.1057187. [3] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241.doi: 10.1016/0097-3165(78)90015-8. [4] T. Etzion and N. Silberstein, Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.doi: 10.1109/TIT.2009.2021376. [5] T. Etzion and A. Vardy, Error-correcting codes in projective space, in "Proceedings of International Symposium on Information Theory,'' (2008), 871-875. [6] T. Etzion and A. Vardy, On $q$-analogs for Steiner systems and covering designs, Adv. Math. Commun., 5 (2011), 161-176. [7] W. Fulton, "Young Tableaux,'' Cambridge University Press, 1997. [8] E. M. Gabidulin, Theory of codes with maximal rank distance, Probl. Inform. Transm., 21 (1985), 1-12. [9] M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes, IEEE Trans. Inform. Theory, 56 (2010), 3207-3216.doi: 10.1109/TIT.2010.2048447. [10] R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.doi: 10.1109/TIT.2008.926449. [11] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, Lecture Notes Comp. Sci., 5393 (2008), 31-42.doi: 10.1007/978-3-540-89994-5_4. [12] V. L. Levenshtein, A class of systematic codes, Soviet Math. Dokl., 1 (1960), 368-371. [13] J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' 2nd edition, Cambridge University Press, 2001. [14] R. M. Roth, Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inform. Theory, 37 (1991), 328-336.doi: 10.1109/18.75248. [15] N. Silberstein and T. Etzion, Enumerative coding for Grassmannian space, IEEE Trans. Inform. Theory, 57 (2011), 365-374.doi: 10.1109/TIT.2010.2090252. [16] D. Silva, F. R. Kschischang and R. Koetter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967.doi: 10.1109/TIT.2008.928291. [17] V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382.doi: 10.1109/TIT.2009.2039163. [18] R. P. Stanley, "Enumerative Combinatorics,'' Wadsworth, 1986. [19] A. J. Van Zanten, Lexicographic order and linearity, Des. Codes Crypt., 10 (1997), 85-97.doi: 10.1023/A:1008244404559.