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

Large constant dimension codes and lexicodes

1. 

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

Received  March 2010 Revised  September 2010 Published  May 2011

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.
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. 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. 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. doi: 10.1109/TIT.2009.2021376.

[5]

T. Etzion and A. Vardy, Error-correcting codes in projective space,, in, (2008), 871.

[6]

T. Etzion and A. Vardy, On $q$-analogs for Steiner systems and covering designs,, Adv. Math. Commun., 5 (2011), 161.

[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.

[9]

M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes,, IEEE Trans. Inform. Theory, 56 (2010), 3207. 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. 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. doi: 10.1007/978-3-540-89994-5_4.

[12]

V. L. Levenshtein, A class of systematic codes,, Soviet Math. Dokl., 1 (1960), 368.

[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. doi: 10.1109/18.75248.

[15]

N. Silberstein and T. Etzion, Enumerative coding for Grassmannian space,, IEEE Trans. Inform. Theory, 57 (2011), 365. 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. doi: 10.1109/TIT.2008.928291.

[17]

V. Skachek, Recursive code construction for random networks,, IEEE Trans. Inform. Theory, 56 (2010), 1378. 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. 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. 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. 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. doi: 10.1109/TIT.2009.2021376.

[5]

T. Etzion and A. Vardy, Error-correcting codes in projective space,, in, (2008), 871.

[6]

T. Etzion and A. Vardy, On $q$-analogs for Steiner systems and covering designs,, Adv. Math. Commun., 5 (2011), 161.

[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.

[9]

M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes,, IEEE Trans. Inform. Theory, 56 (2010), 3207. 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. 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. doi: 10.1007/978-3-540-89994-5_4.

[12]

V. L. Levenshtein, A class of systematic codes,, Soviet Math. Dokl., 1 (1960), 368.

[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. doi: 10.1109/18.75248.

[15]

N. Silberstein and T. Etzion, Enumerative coding for Grassmannian space,, IEEE Trans. Inform. Theory, 57 (2011), 365. 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. doi: 10.1109/TIT.2008.928291.

[17]

V. Skachek, Recursive code construction for random networks,, IEEE Trans. Inform. Theory, 56 (2010), 1378. 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. 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]

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

[4]

Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Cone-fields without constant orbit core dimension. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651

[5]

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

[6]

Guozhen Lu, Yunyan Yang. Sharp constant and extremal function for the improved Moser-Trudinger inequality involving $L^p$ norm in two dimension. Discrete & Continuous Dynamical Systems - A, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963

[7]

Satoshi Kosugi, Yoshihisa Morita, Shoji Yotsutani. A complete bifurcation diagram of the Ginzburg-Landau equation with periodic boundary conditions. Communications on Pure & Applied Analysis, 2005, 4 (3) : 665-682. doi: 10.3934/cpaa.2005.4.665

[8]

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

[9]

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

[10]

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

[11]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[12]

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

[13]

Rafael Labarca, Solange Aranzubia. A formula for the boundary of chaos in the lexicographical scenario and applications to the bifurcation diagram of the standard two parameter family of quadratic increasing-increasing Lorenz maps. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1745-1776. doi: 10.3934/dcds.2018072

[14]

Lluís Alsedà, Michał Misiurewicz. Semiconjugacy to a map of a constant slope. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3403-3413. doi: 10.3934/dcdsb.2015.20.3403

[15]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[16]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[17]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261

[18]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[19]

Misha Bialy. On Totally integrable magnetic billiards on constant curvature surface. Electronic Research Announcements, 2012, 19: 112-119. doi: 10.3934/era.2012.19.112

[20]

Vishal Vasan, Katie Oliveras. Pressure beneath a traveling wave with constant vorticity. Discrete & Continuous Dynamical Systems - A, 2014, 34 (8) : 3219-3239. doi: 10.3934/dcds.2014.34.3219

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]