American Institute of Mathematical Sciences

Advanced
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

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.
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.  Google Scholar

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

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

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

[5]

T. Etzion and A. Vardy, Error-correcting codes in projective space, in "Proceedings of International Symposium on Information Theory,'' (2008), 871-875. Google Scholar

[6]

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

[7]

W. Fulton, "Young Tableaux,'' Cambridge University Press, 1997.  Google Scholar

[8]

E. M. Gabidulin, Theory of codes with maximal rank distance, Probl. Inform. Transm., 21 (1985), 1-12.  Google Scholar

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

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

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

[12]

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

[13]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' 2nd edition, Cambridge University Press, 2001.  Google Scholar

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

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

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

[17]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382. doi: 10.1109/TIT.2009.2039163.  Google Scholar

[18]

R. P. Stanley, "Enumerative Combinatorics,'' Wadsworth, 1986. Google Scholar

[19]

A. J. Van Zanten, Lexicographic order and linearity, Des. Codes Crypt., 10 (1997), 85-97. doi: 10.1023/A:1008244404559.  Google Scholar

show all references

References:
[1]

G. E. Andrews and K. Eriksson, "Integer Partitions,'' Cambridge University Press, 2004.  Google Scholar

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

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

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

[5]

T. Etzion and A. Vardy, Error-correcting codes in projective space, in "Proceedings of International Symposium on Information Theory,'' (2008), 871-875. Google Scholar

[6]

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

[7]

W. Fulton, "Young Tableaux,'' Cambridge University Press, 1997.  Google Scholar

[8]

E. M. Gabidulin, Theory of codes with maximal rank distance, Probl. Inform. Transm., 21 (1985), 1-12.  Google Scholar

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

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

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

[12]

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

[13]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' 2nd edition, Cambridge University Press, 2001.  Google Scholar

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

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

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

[17]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382. doi: 10.1109/TIT.2009.2039163.  Google Scholar

[18]

R. P. Stanley, "Enumerative Combinatorics,'' Wadsworth, 1986. Google Scholar

[19]

A. J. Van Zanten, Lexicographic order and linearity, Des. Codes Crypt., 10 (1997), 85-97. doi: 10.1023/A:1008244404559.  Google Scholar

[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 & Continuous Dynamical Systems, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651
[8]

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
[9]

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, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963
[10]

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
[11]

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
[12]

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
[13]

Bachir Bar, Tewfik Sari. The operating diagram for a model of competition in a chemostat with an external lethal inhibitor. Discrete & Continuous Dynamical Systems - B, 2020, 25 (6) : 2093-2120. doi: 10.3934/dcdsb.2019203
[14]

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
[15]

Daniel Lear, David N. Reynolds, Roman Shvydkoy. Grassmannian reduction of cucker-smale systems and dynamical opinion games. Discrete & Continuous Dynamical Systems, 2021, 41 (12) : 5765-5787. doi: 10.3934/dcds.2021095
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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, 2018, 38 (4) : 1745-1776. doi: 10.3934/dcds.2018072

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (57)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy