Large constant dimension codes and lexicodes

Previous Article
Some connections between self-dual codes, combinatorial designs and secret sharing schemes
AMC Home
This Issue
Next Article
On $q$-analogs of Steiner systems and covering designs

May 2011, 5(2): 177-189. doi: 10.3934/amc.2011.5.177

Large constant dimension codes and lexicodes

Natalia Silberstein ^1, and Tuvi Etzion ^1,

1.	Computer Science Department, Technion - Israel Institute of Technology, Haifa, 32000, Israel

Received March 2010 Revised September 2010 Published May 2011

Abstract
Related Papers

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$_qⁿ 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.

Keywords: lexicode, Grassmannian, constant dimension code, Ferrers diagram..

Mathematics Subject Classification: Primary: 14M15, 94B60; Secondary: 94B6.

Citation: Natalia Silberstein, Tuvi Etzion. Large constant dimension codes and lexicodes. Advances in Mathematics of Communications, 2011, 5 (2) : 177-189. doi: 10.3934/amc.2011.5.177

References:

[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,'' 2^nd 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.

show all references

References:

[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,'' 2^nd 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.

[1]	Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147
[2]	Roland D. Barrolleta, Emilio Suárez-Canedo, Leo Storme, Peter Vandendriessche. On primitive constant dimension codes and a geometrical sunflower bound. Advances in Mathematics of Communications, 2017, 11 (4) : 757-765. doi: 10.3934/amc.2017055
[3]	Lisa Hernandez Lucas. Properties of sets of subspaces with constant intersection dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052
[4]	Sascha Kurz. The interplay of different metrics for the construction of constant dimension codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2021069
[5]	Denis S. Krotov, Patric R. J. Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013
[6]	Daniele Bartoli, Matteo Bonini, Massimo Giulietti. Constant dimension codes from Riemann-Roch spaces. Advances in Mathematics of Communications, 2017, 11 (4) : 705-713. doi: 10.3934/amc.2017051
[7]	Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Cone-fields without constant orbit core dimension. Discrete and Continuous Dynamical Systems, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651
[8]	Huimin Lao, Hao Chen. New constant dimension subspace codes from multilevel linkage construction. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022039
[9]	María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018
[10]	Guozhen Lu, Yunyan Yang. Sharp constant and extremal function for the improved Moser-Trudinger inequality involving $L^p$ norm in two dimension. Discrete and Continuous Dynamical Systems, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963
[11]	Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[12]	Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[13]	Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[14]	Bachir Bar, Tewfik Sari. The operating diagram for a model of competition in a chemostat with an external lethal inhibitor. Discrete and Continuous Dynamical Systems - B, 2020, 25 (6) : 2093-2120. doi: 10.3934/dcdsb.2019203
[15]	Satoshi Kosugi, Yoshihisa Morita, Shoji Yotsutani. A complete bifurcation diagram of the Ginzburg-Landau equation with periodic boundary conditions. Communications on Pure and Applied Analysis, 2005, 4 (3) : 665-682. doi: 10.3934/cpaa.2005.4.665
[16]	Daniel Lear, David N. Reynolds, Roman Shvydkoy. Grassmannian reduction of cucker-smale systems and dynamical opinion games. Discrete and Continuous Dynamical Systems, 2021, 41 (12) : 5765-5787. doi: 10.3934/dcds.2021095
[17]	Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022010
[18]	Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[19]	Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[20]	Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Natalia Silberstein Tuvi Etzion
on Google Scholar
Natalia Silberstein Tuvi Etzion

[Back to Top]