リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「Geometric approach to the extendability of linear codes over finite fields」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。
リケラボ

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

Geometric approach to the extendability of linear codes over finite fields

苅田 仁 大阪府立大学 DOI:info:doi/10.24729/00017395

2021.05.11

概要

A q-ary linear code of length n with dimension k (an [n, k]q code) is a k-dimensional subspace of the n-dimensional row vector space over Fq, the field of q elements. An [n, k]q code with minimum distance d is called an [n, k, d]q code. For the parameters k,d,q, the problem to determine nq(k, d) the smallest possible length n for which an [n, k, d]q code exists is called the optimal linear codes problem (Hill, 1992).

For an [n, k, d]q code C with generator matrix G, C is l-extendable if there exist l vectors h1, · · · , hl ∈ Fk such that the extended matrix [G, hT, · · · , hT] generates an [n + l, k, d + l]q code C′. Especially when l = 1, C is called extendable and C′ is an extension of C. In general, it is not easy to see whether a given non-binary code is extendable or not. Theorems giving answers to this problem are called extension theorems. We give new extension theorems using the geometric method through projective geometry PG(k − 1, q). We give the following results.

In Chapter 1, we give backgrounds and aims as the introduction of this thesis.

In Chapter 2, we first introduce basic concepts of linear codes and well known theorems. Next, we give some results about extendability of linear codes, that is the main theme of our research. The conditions for the extendability introduced in this chapter use q-WS; the q-tuples computed by weight distribution. Finally, we explain the concepts of projective geometry over the field of order q and the way to associate with q-WS and generator matrix of a linear code.

In Chapter 3, we prove that [n, k, d] ternary linear codes with d ≡ −2 (mod 9), whose weights are congruent to 0, −1, −2 modulo 9 are extendable. As its application, we prove the non-existence of a [512, 6, 340]3 code.

In Chapters 4 and 5, we give new results on quaternary linear codes. Refering the results on odd sets in the projective space over the field of order 4, we give some conditions depending on the values of 4-WS for the extendability of quaternary linear codes and some examples applying the results. In Chapter 5, we prove the non-existence of some quaternary linear codes to determine n4(5, d) for some d, which some extension theorems for quaternary linear codes are applied to.

In Chapter 6, we give new results on generalized extension theorems for linear codes over the field of order q.

In Chapter 7, we give the updated tables of the values of nq(k, d) with Griesmer bound for q = 3, 4.

論文の公開元へ

関連論文

関連論文をもっと見る

参考文献

[1] J. Bierbrauer, Introduction to Coding Theory, Chapman & Hall/CRC, 2005.

[2] R.C. Bose, R.C. Burton, A characterization of flat spaces in a finite projective ge- ometry and the uniqueness of the Hamming and the MacDonald codes, J. Combin. Theory 1 (1966), 96-104.

[3] I. Bouyukliev, M. Grassl and Z. Varbanov, New bounds for n4(k, d) and classification of some optimal codes over GF(4), Discrete Math., 281, 43–66, 2004.

[4] R. Calderbank, W.M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc. 18(2) (1986) 97–122.

[5] E.J. Cheon, T. Maruta, A new extension theorem for 3-weight modulo q linear codes over Fq, Des. Codes Cryptogr. 52 (2009), 171–183.

[6] S. Dodunekov, I.N. Landgev, On the quaternary [11, 6, 5] and [12, 6, 6] codes, in: D. Gollmann (Ed.), Applications of Finite Fields, IMA Conference Series, Vol. 59, Clarendon Press, Oxford, 1996, 75–84.

[7] M. Grassl, Tables of linear codes and quantum codes (electronic table, online), http://www.codetables.de/.

[8] J.H. Griesmer, A bound for error-correcting codes, IBM J. Res. Develop. 4 (1960), 532-542.

[9] N. Hamada, A characterization of some [n, k, d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry, Discrete Math. 116 (1993), 229-268.

[10] R. Hill, A First Course in Coding Theory, Clarendon Press, Oxford, 1986.

[11] R. Hill, Optimal linear codes, in: C. Mitchell, ed., Cryptography and Coding II (Oxford Univ. Press, Oxford, 1992) 75–104.

[12] R. Hill, An extension theorem for linear codes, Des. Codes Cryptogr. 17 (1999) 151– 157.

[13] J.W.P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford, 1985.

[14] J.W.P. Hirschfeld, Projective geometries over finite fields 2nd ed., Clarendon Press, Oxford, 1998.

[15] J.W.P. Hirschfeld and J.A. Thas, General Galois Geometries, Clarendon Press, Ox- ford, 1991.

[16] C.M. Jones, Optimal ternary linear codes, Dissertation, Salford University, 2000.

[17] A. Kohnert, (l, s)-extension of linear codes, Discrete Math., 309 (2009) 412-417.

[18] K. Kumegawa, T. Okazaki, T. Maruta, On the minimum length of linear codes over the field of 9 elements, Electronic J. Combin. 24(1) (2017), #P1.50.

[19] I.N. Landjev, T. Maruta, On the minimum length of quaternary linear codes of di- mension five, Discrete Math. 202 (1999) 145–161.

[20] I. Landgev, T. Maruta, R. Hill, On the nonexistence of quaternary [51, 4, 37] codes, Finite Fields Appl. 2 (1996) 96–110.

[21] I. Landgev, A. Rousseva, The nonexistence of some optimal arcs in PG(4, 4), in Proc. 6nd Intern. Workshop on Optimal Codes and Related Topics, Varna, Bulgaria, 2009, 139–144.

[22] I. Landjev, A. Rousseva, L. Storme, On the extendability of quasidivisible Griesmer arcs, Des. Codes Cryptogr. 79 (2016) 535–547.

[23] F. J. MacWilliams, N.J.A. Sloane, The theory of error-correcting codes, 2nd reprint. Amsterdam - New York - Oxford: North-Holland, 1983.

[24] T. Maruta, The nonexistence of [116, 5, 85]4 codes and [187, 5, 139]4 codes, in Proc. 2nd Intern. Workshop on Optimal Codes and Related Topics, Sozopol, Bulgaria, 1998, 168–174.

[25] T. Maruta, On the nonexistence of q-ary linear codes of dimension five, Des. Codes Cryptogr. 22 (2001) 165–177.

[26] T. Maruta, On the extendability of linear codes, Finite Fields and Their Appl. 7 (2001) 350–354.

[27] T. Maruta, Extendability of linear codes over GF(q) with minimum distance d, gcd(d, q) = 1, Discrete Math. 266 (2003) 377–385.

[28] T. Maruta, A new extension theorem for linear codes, Finite Fields and Their Appl. 10 (2004) 674–685.

[29] T. Maruta, Extendability of quaternary linear codes, Discrete Math. 293/1-3 (2005) 195–203.

[30] T. Maruta, Extendability of ternary linear codes, Des. Codes Cryptogr. 35 (2005) 175–190.

[31] T. Maruta, Extendability of linear codes over Fq, Proc. 11th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Pamporovo, Bulgaria, 2008, 203–209.

[32] T. Maruta, Extension theorems for linear codes over finite fields, J. Geometry 101 (2011), 173–183.

[33] T. Maruta, K. Okamoto, Geometric conditions for the extendability of ternary linear codes, in: Ø. Ytrehus (Ed.), Coding and Cryptography, Lecture Notes in Computer Science 3969, Springer-Verlag, 2006, pp. 85–99.

[34] T. Maruta, Y.Oya, On the minimum length of ternary linear codes, Des. Codes Cryptogr. 68 (2013), 407―425.

[35] T. Maruta, K. Okamoto, Some improvements to the extendability of ternary linear codes, Finite Fields and Their Appl. 13 (2007) 259–280.

[36] T. Maruta, K. Okamoto, Extendability of 3-weight (mod q) linear codes over Fq, Finite Fields and Their Appl. 15 (2009), pp. 134–149.

[37] T. Maruta, M. Takeda, K. Kawakami, New sufficient conditions for the extendability of quaternary linear codes, Finite Fields and Their Appl. 14 (2008), pp. 615–634.

[38] T. Maruta, Griesmer bound for linear codes over finite fields, http://mi-s.osakafu-u.ac.jp/˜maruta/griesmer/.

[39] K. Okamoto, Necessary and sufficient conditions for the extendability of ternary linear codes, Serdica Journal of Computing 2 (2009), 331–348.

[40] A. Rousseva, I. Landjev, The geometric approach to the existence of some quaternary Griesmer codes, Des. Codes Cryptogr. 88 (2020) 1925–1940.

[41] J. Simonis, Adding a parity check bit, IEEE Trans. Inform. Theory 46 (2000) 1544– 1545.

[42] M. Takenaka, K. Okamoto, T. Maruta, On optimal non-projective ternary linear codes, Discrete Math. 308 (2008) 842–854.

[43] T. Tanaka, T. Maruta, A characterization of some odd sets in projective space of order 4 and the extendability of quaternary linear codes, J. Geometry 105 (2014) 79–86.

[44] H.N. Ward, Divisibility of codes meeting the Griesmer bound, J. Combin. Theory Ser. A 83, no.1 (1998) 79–93.

[45] Y. Yoshida, T. Maruta, On the (2, 1)-extendability of ternary linear codes, Proc. 11th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Pamporovo, Bulgaria, 2008, 305–311.

[46] Y. Yoshida, T. Maruta, An extension theorem for [n, k, d]q codes with gcd(d, q) = 2, Australas. J. Combin. 48 (2010), 117–131.

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文
を
一発検索！

この論文の関連論文を見る