JACODESMATH / ISSN 2148-838X J. Algebra Comb. Discrete Appl. 2(3) • 211-216 Received: 29 May 2015; Accepted: 29 August 2015 DOI 10.13069/jacodesmath.66269 Journal of Algebra Combinatorics Discrete Structures and Applications Some new quasi-twisted ternary linear codes∗ Research Article Rumen Daskalov1∗∗, Plamen Hristov1∗ ∗ ∗ 1. Department of Mathematics, Technical University of Gabrovo, Bulgaria Abstract: Let [n, k, d]q code be a linear code of length n, dimension k and minimum Hamming distance d over GF(q). One of the basic and most important problems in coding theory is to construct codes with best possible minimum distances. In this paper seven quasi-twisted ternary linear codes are constructed. These codes are new and improve the best known lower bounds on the minimum distance in [6]. 2010 MSC: 94B05, 94B65 Keywords: Ternary linear codes, Quasi-twisted codes 1. Introduction Let GF(q) denote the Galois field of q elements and let V (n,q) denote the vector space of all ordered n-tuples over GF(q). A q-ary linear code C of length n and dimension k, or an [n,k]q code, is a k- dimensional subspace of V (n,q). An inner product (x,y) of vectors x,y ∈ V (n,q) defines orthogonality in the space - two vectors are said to be orthogonal if their inner product is 0. The set of all vectors of V (n,q) orthogonal to all codewords from C is called the orthogonal code C⊥ to C. It is well-known that the code C⊥ is a linear [n,n−k]q code. A k ×n matrix G whose rows form a basis of C is called a generator matrix of C. The number of nonzero coordinates of a vector x ∈ V (n,q) is called its Hamming weight wt(x). The Hamming distance d(x,y) between two vectors is defined by d(x,y) = wt(x−y). The minimum distance of a linear code C is d(C) = min {d(x,y) | x,y ∈ C,x 6= y} = min {wt(c) | c ∈ C,c 6= 0}. A q-ary linear code of length n, dimension k and minimum distance d is said to be an [n,k,d]q code. Let Ai denote the number of codewords of C with weight i. The weight distribution of C is the list of numbers Ai. The weight distribution A0 = 1, Ad = α, . . . , An = γ is expressed as 01dα . . .nγ also. ∗ This work was partially supported by the Bulgarian Ministry of Education and Science under Contract in TU– Gabrovo. ∗∗ E-mail: daskalov@tugab.bg (Corresponding Author) ∗ ∗ ∗ E-mail: plhristov9@gmail.com 211 QT Ternary Linear Codes If C ⊆ C⊥, then the code C is called self-orthogonal. For a ternary linear code C the next theorem is well-known - every codeword of C has weight divisible by three if and only if C is self-orthogonal. A central problem in coding theory is that of optimizing one of the parameters n,k and d for given values of the other two and q-fixed. Two are the basic versions: Problem 1: Find dq(n,k), the largest value of d for which there exists an [n,k,d]q code. Problem 2: Find nq(k,d), the smallest value of n for which there exists an [n,k,d]q code. A code which achieves one of these two values is called d-optimal or n-optimal respectively. Both distance-optimal and length-optimal codes are called optimal codes. The problem of finding the parameters of the optimal codes is very difficult one (see [15], [9]) and has two aspects - one is the construction of new codes with better minimum distances and the other is to prove the nonexistence of codes with given parameters. It is entirely solved only for small finite fields and dimensions (see the following table and [10], [2], [6]). q 2 3 4 5,7,8,9 k ≤ 8 5 4 3 Many optimal linear codes are constructed when n−k is also small (see [6]). For the first aspect computer search is often used but it is well known fact that computing the minimum distance of a linear code is an NP-hard problem [16]. Since it is not possible to conduct exhaustive searches for linear codes with large dimension, a natural way is to focus our efforts on subclasses of linear codes, having rich mathematical structures. Quasi-twisted (QT) codes are known to have this structure and it has been shown in recent years that this subclass contains many new good linear codes [1,3-8,11-14]. Grassl [6] maintains a table with lower and upper bounds on minimum distances over small finite fields. For any n and k there are two numbers in the table - dl and du. The former, dl, is the best known minimum distance of an [n,k,d]q code constructed to date, whereas the latter, du, is the theoretical upper bound on the minimum distance of an [n,k]q code. When dl = du = d then the [n,k,d]q code is optimal. Many of the best-known codes in Grassl’s tables are QT codes. A code that attains a lower bound in the table is called a good code. A code that improves a lower bound in the table we will call a new code. Chen also maintains online tables of linear codes. Chen’s table [3] contains only good and best-known QC and QT codes (q ≤ 13). These two databases are updated when new codes are discovered. 2. Quasi-twisted codes A code C is said to be quasi-twisted if a constacyclic shift of a codeword by p positions results in another codeword. A constacyclic shift of an m-tuple (x0,x1, . . . ,xm−1) is the m-tuple (αxm−1,x0, . . . ,xm−2),α ∈ GF(q) \ {0}. The blocklength, n, of a QT code is a multiple of p, so that n = pm. A matrix B of the form B =   b0 b1 b2 · · · bm−2 bm−1 αbm−1 b0 b1 · · · bm−3 bm−2 αbm−2 αbm−1 b0 · · · bm−4 bm−3 ... ... ... ... ... αb1 αb2 αb3 · · · αbm−1 b0   , (1) where α ∈ GF(q)\{0} is called a twistulant matrix. A class of QT codes can be constructed from m×m twistulant matrices. In this case, the generator matrix, G , can be represented as G = [B1, B2, ... , Bp] , (2) 212 R. Daskalov, P. Hristov where Bi is a twistulant matrix [14]. The algebra of m×m twistulant matrices over GF(q) is isomorphic to the algebra of polynomials in the ring GF(q)[x]/(xm−α) if B is mapped onto the polynomial, b(x) = b0 +b1x+b2x2 +· · ·+bm−1xm−1, formed from the entries in the first row of B. The bi(x) associated with a QT code are called the defining polynomials. If the defining polynomials bi(x) contain a common factor which is also a factor of xm −α, then the QT code is called degenerate. The dimension k of the QT code is equal to the degree of h(x), where [14] h(x) = xm −α gcd{xm −α,b1(x),b2(x), · · · ,bp(x)} . (3) If the polynomial h(x) has degree m, the dimension of the code is m, and (2) is a generator matrix. If deg(h(x)) = k < m, a generator matrix for the code can be constructed by deleting m−k rows of (2). Let the defining polynomials of the code C be in the next form d1(x) = g(x), d2(x) = f2(x)g(x), · · · , dp(x) = fp(x)g(x), (4) where g(x)|(xm −α),g(x),fi(x) ∈ GF(q)[x]/(xm −α), (fi(x),(xm −α)/g(x)) = 1 and deg fi(x) < m− deg g(x) for all 1 ≤ i ≤ p. Then C is a degenerate QT code, which is a one-generator QT code and for this code n = mp, and k = m−deg g(x). A p -QT code over GF(q) of length n = pm can be viewed as a GF(q)[x]/(xm −α) submodule of (GF(q)[x]/(xm−α))p [14]. Then an r-generator QT code is spanned by r elements of (GF(q)[x]/(xm− α))p. A well-known result regarding the one-generator QT codes is given in the next theorem. Theorem 2.1. [14]: Let C be a one-generator QT code over GF(q) of length n = pm. Then, a generator g(x) ∈ (GF(q)[x]/(xm −α))p of C has the following form g(x) = (f1(x)g1(x),f2(x)g2(x), · · · ,fp(x)gp(x)) where gi(x)|(xm −1) and (fi(x),(xm −α)/gi(x)) = 1 for all 1 ≤ i ≤ p. In this paper seven new one-generator QT codes (p ≥ 2) are constructed, using an algebraic- combinatorial computer search similar to that in [14]. All constructed codes are self-orthogonal. 3. The new codes We have restricted our search to one-generator QT codes with a generator of the form (4). Example 3.1. Let q = 3, m = 52 and α = 2. The factorization of the polynomial x52 + 1 over GF(3) is x52 + 1 = 10∏ i=1 pi(x), where p1(x) = x 6 + x5 + 2x4 + 2x3 + x2 + 2x + 2 p6(x) = x 6 + x5 + 2x4 + 2x3 + 2 p2(x) = x 6 + 2x5 + 2x4 + x3 + x2 + x + 2 p7(x) = x 6 + 2x5 + 2x4 + x3 + 2 p3(x) = x 6 + 2x5 + 2x4 + 2x3 + x2 + x + 2 p8(x) = x 6 + 2x3 + x2 + x + 2 p4(x) = x 6 + x5 + 2x4 + x3 + x2 + 2x + 2 p9(x) = x 2 + x + 2 p5(x) = x 6 + x3 + x2 + 2x + 2 p10(x) = x 2 + 2x + 2. 213 QT Ternary Linear Codes Let the dimension k be 20. Then the degree of the polynomials g(x) have to be 32. There are 2. ( 8 3 ) = 112 possibilities to obtain a polynomial g(x) of degree 32. We check these possibilities consecutively, using non-exhaustive search. When g(x) = x32 + x31 + 2x30 + x28 + x27 + 2x26 + x25 + 2x24 + 2x23 + x22 +x19 + 2x17 + x15 + 2x14 + x13 + x12 + 2x11 + 2x9 + 2x9 + 2x9 + 1 and f2(x) = x 8 + x6 + 2x5 + 2x4 + x3 + 2x2 + x + 2, a good [104,20,45]3 quasi-twisted code is obtained. Afterwards, we search for f3(x) and f4(x) in succession. The polynomial f3(x) = x8 + x7 + x6 + x5 + 2x3 + x + 1 yields a new [156,20,75]3 code and the polynomial f4(x) = x8 + 2x2 + x + 1 leads to a new [208,20,105]3 code. We conducted a similar search for other lengths. The obtained new results are presented in the next theorem. Theorem 3.2. There exist self-orthogonal one-generator quasi-twisted codes (α = 2) with parameters: [156,14,84]3, [136,18,66]3, [156,18,78]3, [80,20,33]3 [156,20,75]3, [208,20,105]3, [164,24,75]3. Proof. The coefficients of the defining polynomials and the weight distributions of the codes are as follows: A [156,14,84]3 code (m = 52,p = 3): 2001001112200021222210122020112222120010000000000000, 1010111122102011212102201120021100000012122100000000, 1011020111220020110122112100022000222102122001000000; 01 844056 8717992 9060112 93173576 96384072 99661024 102904280 105963976 108789672 111484120 114233376 11781648 12020384 1233952 126624 129104 A [136,18,66]3 code (m = 34,p = 4): 1100212000222002100000000000000000,2012120222200201222012010000000000, 1110101101210221012212200010000000,1012120022211202011001001111100000; 01 664420 6956712 72332656 751654168 786230092 8118084804 8439732400 8766373440 9083286876 9377889716 9653790516 9927168584 1029809960 1052509268 108439892 11152496 1144284 117204 A [156,18,78]3 code (m = 52,p = 3): 2112221111101000202210102100010000100000000000000000, 2001021122201101100112210000012012000212211000000000, 1111210012122200102120211111102202002010200100000000; 01 789568 8152104 84304304 871384448 904931680 9313906776 9630902040 9953999712 10273411312 10577915448 10863630008 11139595816 11418649384 1176627296 1201732224 123321048 12643056 1294160 132104 A [80,20,33]3 code (m = 40,p = 2): 2001100012102210110010000000000000000000, 1202220122210221220201202022102010000000; 01 3318960 36359360 394063760 4230350480 45144118432 48436419120 51831804960 54979844960 57696755760 60288531648 6366176080 667894000 69437440 729440 214 R. Daskalov, P. Hristov A [156,20,75]3 code (m = 52,p = 3): 1000100110021121020100122121102110000000000000000000, 1221120201102202120000202210021101112110000000000000, 1102121020011222010112010002201010101012110000000000; 01 758216 7870200 81490568 842755480 8712400856 9044366920 93125212568 96278102448 99485583176 102661878672 105700633856 108572121472 111356398640 114168530440 11759392328 12015466360 1232948400 126387088 12933904 1322704 135104 A [208,20,105]3 code (m = 52,p = 4): 1000100110021121020100122121102110000000000000000000, 2121100002110110121022011010211200121001100000000000, 1102121102022101002111201220111021001112100000000000, 1120112100221020012120010010002221111021100000000000; 01 1056968 10836816 111225368 1141084720 1174490824 12015554344 12344887960 126109041296 129221353392 132374073232 135524057352 138608355904 141582839608 144458328208 147294288384 150153923432 15364968592 15621913224 1595855616 1621267136 165203736 16825792 1712392 174104 A [164,24,75]3 code (m = 82,p = 2): 1121222111221010212020202121202222202020222010112212212222100000000000000000000000, 2011121210102200210211202120010122002121000011212011011012000102010000000000000000; 01 7515744 78172200 811673128 8412794460 8779656112 90396419160 931584181452 965070823256 9912959375940 10226376357636 10542571391912 10854230847436 11154217062252 11442255118404 11725471036636 12011763022344 1234119948304 1261079104584 129208391028 13229038660 1352892960 138201720 14110988 144164 From the constructed codes, by trivial constructions as shortening, puncturing and extension, 29 im- provements on [6] are obtained. For example - from [80,20,33]3 code it follows that there exist [79,19,33]3, [78,19,32]3, [77,19,31]3, [79,20,32]3, [78,20,31]3 and [81,20,33]3 codes. References [1] R. Ackerman and N. Aydin, New quinary linear codes from quasi-twisted codes and their duals, Appl. Math. Lett., 24(4), 512–515, 2011. [2] S. Ball, Three-dimensional linear codes, Online table, http://www-ma4.upc.edu/∼simeon/. [3] E. Z. Chen, Database of quasi-twisted codes, available at http://moodle.tec.hkr.se/ chen/research/codes/searchqt.htm [4] E. Z. Chen, A new iterative computer search algorithm for good quasi-twisted codes, Des. Codes Cryptogr, 76(2), 307-323, 2014. [5] R. Daskalov and P. Hristov, New quasi-twisted degenerate ternary linear codes, IEEE Trans. Inform. Theory, 49(9), 2259–2263, 2003. [6] M. Grassl, Linear code bound, [electronic table; online], http://www.codetables.de. [7] P. P. Greenough and R. Hill, Optimal ternary quasi-cyclic codes, Des. Codes Cryptogr., 2(1), 81–91, 1992. [8] T. A. Gulliver and P. R. J. Ostergard, Improved bounds for ternary linear codes of dimension 7, IEEE Trans. Inform. Theory, 43, 1377–1388, 1997. [9] R. Hill, A first course in coding theory, Oxford Applied Mathematics and Computing Sciences Series, 1992. [10] T. Maruta, Griesmer bound for linear codes over finite fields, Online table, http://www.mi.s.osakafu- u.ac.jp/~maruta/griesmer.htm. [11] T. Maruta, M. Shinohara and M. Takenaka, Constructing linear codes from some orbits of projectiv- ities, Discrete Math., 308(5-6), 832–841, 2008. 215 ~ QT Ternary Linear Codes [12] E. Metodieva and N. Daskalova, Generating generalized necklaces and new quasi-cyclic codes, Prob- lemi Peredachi Informatsii, (submitted). [13] I. Siap, N. Aydin and D. Ray-Chaudhury, New ternary quasi-cyclic codes with better minimum distances, IEEE Trans. Inform. Theory, 46(4), 1554–1558, 2000. [14] I. Siap, N. Aydin and D. Ray-Chaudhury, The structure of 1-generator quasi-twisted codes and new linear codes, Des. Codes Cryptogr., 24, 313–326, 2001. [15] S. Dougherty, J. Kim and P. Solé, Open problems in coding theory, Contemporary Mathematics, 634, http://dx.doi.org/10.1090/conm/634/12692, 2015. [16] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory, 43, 1757–1766, 1997. 216 Introduction Quasi-twisted codes The new codes References