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

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,'' 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.

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

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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2021, 41 (12) : 5765-5787. doi: 10.3934/dcds.2021095

[16]

Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022010

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

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

Other articles
by authors

[Back to Top]