Extension theorems for linear codes over finite fields. (English) Zbl 1264.94114
Let \(\mathcal{C}\) be an \([n,k,d]_q\) code, i.e., a \(k\)-dimensional vector subspace of \(\mathbb{F}_q^n\) with minimum (Hamming) distance \(d\).
Let \(G\) be a generator matrix of \(\mathcal{C}\). Then \(\mathcal{C}\) is called \((l,s)\)-extendible if there exist \(l\) vectors \(h_1,\dots,h_l\in \mathbb{F}_q^k\) such that the matrix \([G,h_1^T,\dots,h_l^T]\) is a generator matrix of an \([n+l,k,d+s]_q\) code.
In the paper, the author resumes some important theorems regarding the theory on extendible codes. In particular, some conditions to understand whether an \([n,k,d]_q\) code is extendible or not, based on geometric methods, are given.
The extension theorems could be applied to the optimal linear codes problem, i.e., to the problem to optimize one of the parameters \(n,k,d\), leaving the other two fixed.
Let \(G\) be a generator matrix of \(\mathcal{C}\). Then \(\mathcal{C}\) is called \((l,s)\)-extendible if there exist \(l\) vectors \(h_1,\dots,h_l\in \mathbb{F}_q^k\) such that the matrix \([G,h_1^T,\dots,h_l^T]\) is a generator matrix of an \([n+l,k,d+s]_q\) code.
In the paper, the author resumes some important theorems regarding the theory on extendible codes. In particular, some conditions to understand whether an \([n,k,d]_q\) code is extendible or not, based on geometric methods, are given.
The extension theorems could be applied to the optimal linear codes problem, i.e., to the problem to optimize one of the parameters \(n,k,d\), leaving the other two fixed.
Reviewer: Marco Calderini (Povo)
MSC:
| 94B05 | Linear codes (general theory) |
| 94B27 | Geometric methods (including applications of algebraic geometry) applied to coding theory |
References:
| [1] | Alderson T.L., Gács A.: On the maximality of linear codes. Des. Codes Cryptogr. 53, 59–68 (2009) · Zbl 1172.94642 · doi:10.1007/s10623-009-9293-z |
| [2] | Bierbrauer J.: Introduction to Coding Theory. Chapman & Hall, Dordrecht (2005) · Zbl 1060.94001 |
| [3] | Beutelspacher A.: Blocking sets and partial spreads in finite projective spaces. Geom. Dedicata 9, 425–449 (1980) · doi:10.1007/BF00181559 |
| [4] | Bose R.C., Burton R.C.: A characterization of flat spaces in a finite projective geometry and the uniqueness of the Hamming and the MacDonald codes. J. Combin. Theory 1, 96–104 (1966) · Zbl 0152.18106 · doi:10.1016/S0021-9800(66)80007-8 |
| [5] | Bouyukliev I., Simonis J.: Some new results for optimal ternary linear codes. IEEE Trans. Inf. Theory 48, 981–985 (2002) · Zbl 1061.94061 · doi:10.1109/18.992814 |
| [6] | Cheon E.J., Maruta T.: A new extension theorem for 3-weight modulo q linear codes over $${\(\backslash\)mathbb{F}_q}$$ . Des. Codes Cryptogr. 52, 171–183 (2009) · Zbl 1174.94034 · doi:10.1007/s10623-009-9275-1 |
| [7] | Daskalov, R., Metodieva, E.: Good quasi-cyclic binary and ternary codes. In: Proceedings of the 12th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Novosibirsk, Russia, pp. 98–102 (2010) |
| [8] | van Eupen M., Lisonêk P.: Classification of some optimal ternary linear codes of small length. Des. Codes Cryptogr. 10, 63–84 (1997) · Zbl 0869.94031 · doi:10.1023/A:1008292320488 |
| [9] | Grassl, M.: Tables of linear codes and quantum codes (electronic table, online). http://www.codetables.de |
| [10] | Hamada N.: A characterization of some [n, k, d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry. Discret. Math. 116, 229–268 (1993) · Zbl 0770.94006 · doi:10.1016/0012-365X(93)90404-H |
| [11] | Heim, U.: Blockierende Mengen in endlichen projektiven Räumen. Mitt. Math. Sem. Giessen 226 (1996) · Zbl 0859.51005 |
| [12] | Hill R.: Optimal linear codes. In: Mitchell, C (eds) Cryptography and Coding II, pp. 75–104. Oxford University Press, Oxford (1992) · Zbl 0742.94012 |
| [13] | Hill R.: An extension theorem for linear codes. Des. Codes Cryptogr. 17, 151–157 (1999) · Zbl 0957.94030 · doi:10.1023/A:1008319024396 |
| [14] | Hill R., Kolev E. et al.: A survey of recent results on optimal linear codes. In: Holroyd, F.C. (eds) Combinatorial Designs and their Applications, Res. Notes Math. vol. 403, pp. 127–152. Chapman & Hall, New York (1999) · Zbl 0916.94009 |
| [15] | Hill, R., Lizak, P.: Extensions of linear codes. Proc. IEEE Int. Symposium on Inform. Theory, pp. 345. Whistler, Canada (1995) · Zbl 0908.94028 |
| [16] | Hirschfeld J.W.P.: Projective Geometries over Finite Fields, 2nd edn. Clarendon Press, Oxford (1998) · Zbl 0899.51002 |
| [17] | Hirschfeld J.W.P., Storme L. et al.: The packing problem in statistics, coding theory, and finite projective spaces: update 2001. In: Blokhuis, A. (eds) Finite Geometries, Proceedings of the Fourth Isle of Thorns Conferenc, Developments in Mathematics, vol. 3, pp. 201–246. Kluwer, Dordrecht (2001) · Zbl 1025.51012 |
| [18] | Jones C., Matney A., Ward H.: Optimal four-dimensional codes over GF(8). Electron. J. Combin. 13, #R43 (2006) · Zbl 1165.94328 |
| [19] | Kanazawa R., Maruta T.: On optimal linear codes over $${\(\backslash\)mathbb F_8}$$ . Electron. J. Combin. 18, #P34 (2011) · Zbl 1221.94081 |
| [20] | Klein A.: On codes meeting the Griesmer bound. Discret. Math. 274, 289–297 (2004) · Zbl 1045.94022 · doi:10.1016/S0012-365X(03)00201-2 |
| [21] | Kohnert A.: (l, s)-extension of linear codes. Discret. Math. 309, 412–417 (2009) · Zbl 1158.94006 · doi:10.1016/j.disc.2007.12.028 |
| [22] | Landjev I.N. et al.: The geometric approach to linear codes. In: Blokhuis, A (eds) Finite Geometries, Proceedings of the Fourth Isle of Thorns Conference, Developments in Mathematics, vol. 3., pp. 247–256. Kluwer, Dordrecht (2001) · Zbl 1025.51010 |
| [23] | Landjev I., Rousseva A.: An extension theorem for arcs and linear codes. Probl. Inf. Transm. 42, 319–329 (2006) · Zbl 1237.94126 · doi:10.1134/S0032946006040041 |
| [24] | MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977) · Zbl 0369.94008 |
| [25] | Maruta T.: On the extendability of linear codes. Finite Fields Appl. 7, 350–354 (2001) · Zbl 1013.94024 · doi:10.1006/ffta.2001.0296 |
| [26] | Maruta T.: Extendability of linear codes over GF(q) with minimum distance d, gcd(d, q) = 1. Discret. Math. 266, 377–385 (2003) · Zbl 1024.94011 · doi:10.1016/S0012-365X(02)00820-8 |
| [27] | Maruta T.: A new extension theorem for linear codes. Finite Fields Appl. 10, 674–685 (2004) · Zbl 1075.11082 · doi:10.1016/j.ffa.2004.02.001 |
| [28] | Maruta T.: Extendability of ternary linear codes. Des. Codes Cryptogr. 35, 175–190 (2005) · Zbl 1126.94019 · doi:10.1007/s10623-005-6400-7 |
| [29] | Maruta T.: Extendability of quaternary linear codes. Discret. Math. 293, 195–203 (2005) · Zbl 1070.94025 · doi:10.1016/j.disc.2004.08.031 |
| [30] | Maruta, T.: Extendability of linear codes over $${\(\backslash\)mathbb{F}_q}$$ . In: Proceedings of the 11th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Pamporovo, Bulgaria, pp. 203–209 (2008) |
| [31] | Maruta, T.: Griesmer bound for linear codes over finite fields (electronic table). http://www.geocities.jp/mars39geo/griesmer.htm |
| [32] | Maruta T., Okamoto K.: Some improvements to the extendability of ternary linear codes. Finite Fields Appl. 13, 259–280 (2007) · Zbl 1176.94072 · doi:10.1016/j.ffa.2005.09.005 |
| [33] | Maruta, T., Okamoto, K. Extendability of 3-weight (mod q) linear codes over $${\(\backslash\)mathbb{F}_q}$$ . Finite Fields Appl. 15, 134–149 (2009) · Zbl 1181.94121 |
| [34] | Maruta T., Takeda M., Kawakami K.: New sufficient conditions for the extendability of quaternary linear codes. Finite Fields Appl. 14, 615–634 (2008) · Zbl 1175.94123 · doi:10.1016/j.ffa.2007.09.001 |
| [35] | Maruta, T., Yoshida, Y.: A generalized extension theorem for linear codes. Des. Codes Cryptogr. (in press) · Zbl 1235.94072 |
| [36] | Okamoto K.: Necessary and sufficient conditions for the extendability of ternary linear codes. Serdica J. Comput. 2, 331–348 (2009) · Zbl 1173.94448 |
| [37] | Simonis J.: Adding a parity check bit. IEEE Trans. Inf. Theory 46, 1544–1545 (2000) · Zbl 0997.94021 · doi:10.1109/18.850691 |
| [38] | Sloane N.J.A., Reddy S.M., Chen C.L.: New binary linear codes. IEEE Trans. Inf. Theory 18, 503–510 (1972) · Zbl 0243.94006 · doi:10.1109/TIT.1972.1054833 |
| [39] | Ward H.N.: Divisibility of codes meeting the Griesmer bound. J. Combin. Theory Ser. A 83, 79–93 (1998) · Zbl 0913.94026 · doi:10.1006/jcta.1997.2864 |
| [40] | Yoshida Y., Maruta T.: Ternary linear codes and quadrics. Electron. J. Combin. 16, #R9 (2009) · Zbl 1160.94016 |
| [41] | Yoshida Y., Maruta T.: An extension theorem for [n, k, d] q codes with gcd(d, q) = 2. Australas. J. Combin. 48, 117–131 (2010) · Zbl 1216.11108 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
