(l,s)−Extension of Linear Codes Axel Kohnert LehrstuhlMathematikII Universität Bayreuth 95440Bayreuth Deutschland 7 0 Abstract 0 2 We construct new linear codes with high minimum distance d. In at least 12 cases these n a codes improve the minimum distance of the previously known best linear codes for fixed J parameters n,k.Amongthesenewcodesthereisanoptimalternary[88,8,54]3 code. 7 1 We develop an algorithm, which starts with already good codes C, i.e. codes with high minimum distance d for given length n and dimension k over the field GF(q). The algo- ] T rithm is based on the new defined (l,s)−extension. This is a generalization of the well- I known method of adding a parity bit in the case of a binary linear code of odd minimum . s weight. (l,s)−extension tries to extend the generator matrix of C by adding l columns c [ with the property that at least s of the l letters added to each of the codewords of mini- mum weight in C are different from 0. If one finds such columns the minimum distance 1 v oftheextended code isd+sprovided thatthesecond smallest weight inC was≥ d+s. 2 The question whether such columns exist can be settled using a Diophantine system of 1 equations. 1 1 0 7 Keywords: finiteprojective geometry, codingtheory, linearcodes,minimumweight, 0 Diophantine systemofequations / s c : v i X r Introduction a The most prominent example of an extension of a linear code which increases the minimumweightistheuseofaparitybitinthecaseofabinarylinearcodeofodd minimum weight. There is a series of papers where the authors try to generalize thissituation. A code is called extendable, if it is possible to find an extension which also in- creasestheminimumdistance.ExtendabilitywasstudiedbyHillandLizak[11,12], Emailaddress:[email protected] (AxelKohnert). PreprintsubmittedtoElsevier February1,2008 vanEupenandLisonek[19],Simonis[18]andinrecentyearsbyMaruta[14,15,16,17]. A common theme of this work is the study of the weight distribution of a linear code C.Theauthors derivecertain conditionson theweight distributionwhich are sufficientfortheextendabilityofthecode. We generalize this situation, as we no longer search for only one-step-extensions. We try to increase the length of the codewords by l letters in a way such that the minimumdistanceincreaseby at least1.Wecall thisagood extension. This is different from previous work by Van Eupen and Lisonek [19] where they provethatincertainsituationsaternarycodeistwo-foldextendable,thissaysthatit ispossibletoincreasethelengthandalsotheminimumdistanceby2.Thesufficient conditionsensurethattheresultingcodeisself-orthogonal.Two-foldextendability was alsostudiedin[15]. Conceptsusedbutnotdefinedinthistextcanbefoundinanybookonlinearcodes (e.g. [1,2]). (l,s)−Extension Let C be a linear [n,k] code of minimumdistance d with generator matrix Γ. We q callthisan[n,k,d] code.C isconnectedtoitsgeneratormatrixΓviatherelation: q C = {vΓ : v ∈ GF(q)k}. (1) Let c1,...,cg be the codewords in C of minimum weight d. There are vectors v1,...,vg from GF(q)k such that ci = viΓ for all the minimumweight codewords ci. We call the set V := {v1,...,vg} ⊂ GF(q)k the minimum weight generator of thecodeC.WearelookingforanextensionofthegeneratormatrixΓbylcolumns in a way such that the corresponding extended code has minimum distance > d. For an increase in the minimum distance it is necessary that all minimum weight codewords in C are extended by at least one nonzero letter. This will be used to characterize agoodextension. The possible columns for the extension of the generator matrix are the non-zero vectorsofGF(q)k.Weareinterestedintheminimumweightoftheextendedcode, thereforeweareonlyinterestedinthezero/non-zeropropertyofthelettersaddedto thecodewords.Thispropertyisinvariantunderscalarmultiplicationofthepossible columnbya non-zeroelement fromGF(q), thereforewerestrict tocolumns γ1,...,γh (2) which are representatives of the one-dimensional subspaces of GF(q)k. In order to have canonical representatives the first non-zero entry of γ should be 1. The i numberhofpossiblecanonicalcolumnsis qk−1. q−1 Wehavetocheckwhethertheextensionbyapossiblecolumnincreasestheweight of the actual minimum weight codewords. Again like in the case of the columns 2 the minimum weight property is invariant under scalar multiplication by a non- zero element, therefore the number s of the minimum weight codewords in C is a multipleof(q−1)andwehavetocheckonlyt := s elementsfromtheminimum q−1 weightgenerator, which againarerepresentatives g1,...,gt (3) of certain one-dimensional subspaces of GF(q)k. Here we also use canonical rep- resentatives. For a systematicsearch by an algorithmdefine theintersectionmatrix D,which is a t×hmatrix with entries equal to 0 or 1. The rowsare labeled by thet canonical representatives g1,...,gt and the columns are labeled by the h possible canonical columnsγ1,...,γh . Theentries aredefined (h,idenotestheinnerproduct): 1 if hgi,γji =6 0 Di,j :=  . (4) 0 if hg ,γ i = 0 i j  An entry 1 at the position i,j says that there is a non-zero letter in the codeword c = g Γ′ at position m if a generator matrix Γ′ has γ as the m−th column. An i j entry 0says thatthisletteris0.Usingthiswehavethefollowingtheorem: Theorem 1 goodextension SupposeC isa linear[n,k,d] code. q There is a code C′ with minimum distance at least d+1 built by l−fold extension ofC,ifftherearelcolumnsofthematrixD,suchthatforeachrowofD thereisat leastonenon-zeroentryamongthel columns. PROOF. This equivalence is clear from the above description of the connection between thematrixD and theencodingofthecodewordsviamultiplicationwitha generatormatrix. Wecallsuchan[n+l,k] codeC′ withminimumdistance> dan(l,1)−extension q ofC.Weaddedlcolumnstoageneratormatrixandgotanincreaseoftheminimum ′ distanceofatleast1.ThegeneratormatrixofthecodeC isgivenbytheextension ofthegeneratormatrixofC bythecolumnscorrespondingtotheselectedlcolumns of the matrix D. In the case of a gap of size s between the minimumweight d and thesecondsmallestweightd+s ofC weget: Corollary2 (l,s)−Extension Let C be a linear [n,k,d] code with a second smallest weight d + s. We get an q [n+l,k] code C′ with minimum distance at least d+s built by l−fold extension q iffwecanfindamultisetofl columnsofthematrixD,suchthatforeachrowthere areata leasts non-zeroentriesamongthel columns. 3 Suchanextensioniscalledan(l,s)−extension.Inthiscorollarythemultisetinstead ofa set (likein theabovetheorem)is necessary as it is possiblethat severalcopies of the same column are added to the generator matrix. The simplest case of an (l,s)−extension is the addition of a parity bit in the case of a binary code of odd minimumweight.This isan (1,1)−extension. For computational purpose we now state the problem as a Diophantine system of (in)equalities. We statethis only for the case of an (l,1)-extension,a more general versionisalso possible. Corollary3 (l,1)−Extensionasa Diophantinesystemof inequalities Let C bea linear[n,k,d] code. q There is an (l,1)−extension of C iff there is a 0/1−solution x = (x1,...,xh)T of thefollowingsystem of(in)equalities: (1) x = l i P 1 . . (2) Dx ≥  ..        1   In alaststep thissystemis changed intoa Diophantinesystemofequations: Corollary4 (l,1)−Extensionasa Diophantinesystemof equations Let C bea linear[n,k,d] code. q Thereisan(l,1)−extensionofC iffthereisasolutionx|y := (x1,...,xh,y1,...,yh) (withx from{0,1},y from{0,...,l−1})oftheDiophantinesystemofequations: i i −1 1 ... 0 ... x D ...   = y ..   .. 0 . . −1 1 1...1...1...1 0...0...0...0 l From thevaluesoftheslack variablesy1,...,yh itis possibletoread offtheeffect ofthenewcolumnsontheminimumcodewordsoftheoriginalcodeC.Theweight of the q −1 codewords corresponding to the row-label g are increased by y +1. i i Usingthisinformationtogetherwiththeinformationonthesecondsmallestweight it is possible to derive the number of minimum weight codewords in the code C′. The typical case is as follows: there is a slack variable y = 0, this means that the i codewords in C′ corresponding to g are of weight d + 1. It may happen (this is i the even bettercase of an (l,s+1)−extension),that all slack variables are at least s > 0,andthedifferencebetweentheminimalweightinC andthesecondsmallest 4 weightis> s+1,thentheminimumdistanceofC′isatleastd+s+1,andagainthe numberofcodewordsofminimumweightcan bederivedas abovefromthevalues oftheslackvariables.Aboveresultsaresummarizedin thefollowingalgorithm Algorithm 1 (l,1)−extension Input:An [n,k,d] codeC with generatormatrixΓ, anda numberl > 0. q Step 1: compute the canonical representatives g1,...,gt from the minimal weight generator. Step 2:buildthematrixD. Step 3:trytofind asolution(x|y)of theDiophantinesystemof equations. Output: in the case of a solution (x|y) there is an [n + l,k] code with minimum q distance> d. Projective Geometry The connection between non-degenerate linear [n,k] codes and finite projective q geometry PG(k −1,q) is well known (e.g. [2] p. 249). The matrix D is a subma- trixofthepoint-hyperplaneincidencematrixoftheprojectivegeometry.Wegetthe matrix D from the original incidence matrix (points labeling the columns, hyper- planes labeling the rows) by taking only the hyperplanes orthogonal to the vectors from the canonical representatives of the minimum weight generator. Using this connectionMarutacharacterized the1−extendabilityoflinearcodes [14,17]using the intersection property between point and hyperplanes. This is equivalent to the study of the matrix D. For the more general case of (l,1)−extendability we get a generalization oftheseresultsand can restatetheabovetheorem interminologyof projective geometry. Denote by P the (multi-)set of points in PG(k −1,q) corre- spondingto thenon-degenerate[n,k,d] code. q Lemma 5 (l,1)−extensionin PG(k−1,q) A[n,k,d] code(withcorrespondingpoint-setP)canbeextendedtoan[n+l,k] q q with minimum distance > d, iff there is a set of l points in PG(k −1,q) such that theintersectionnumberbetween P andallthehyperplanescontainingatleastone ofthel pointsis< n−d. Working in finite projective geometries people restrict to projective codes, as in thiscaseit ispossibletowork withsetsofpointsinsteadofmultisets.Algorithm1 can be modified to generate only extensions which result to a projective code. For this remove the n columns of D corresponding to the points in the point-set P of the code C. Now a solutionof the corresponding Diophantinesystem of equations correspondsto aselectionofpointsdifferent fromthepointsalready inP. 5 Comparisonto otherMethods, Limits oftheAlgorithm The(l,s)−extensionisbasedonthewellknownextensionofageneratormatrixby one further column.But in general this does not increase theminimumdistance of thecode.Onefamousexceptionistheuseofaparitybit,whichisthesimplestcase of a (1,1)−extension. The more general (l,s)−extension characterizes in which cases ageneralization ofthisparity-bitmethodispossible. The (l,s)−extension is an ’inverse’ operation to the special puncturing described by Grassl and White in [10]. They remove l columns of a generator matrix in a way such that each codeword of minimum weight has an entry equal to zero in at least s columns of these l columns. Given this property together with a condition onthesecondsmallestweightthepuncturedcodehasminimumdistanced−l+s. A code C′ constructed by (l,s)−extension of a code C will give back C′ using special puncturing. This is the generalization of the well known pair (extension - puncturing)forlinearcodes. The typical case in which one may try to apply the (l,1)−extension is a sequence ofcodes oflengthsn,n+1,...,n+l wherethebest knownminimumdistanceis constant say d. This is a hint that the extension by a single column does not work forthecodesoflengthn,...,n−l+1,but(l,1)−extensionappliedtothecodeof length n may work. All the new examples in the final section were found starting withsuch asituation. The Diophantine system of equations can be solved quite effectively by Wasser- mann’s implementation of the LLL-algorithm [21]. Another method in the case of small l is the complete enumeration of all l−tuples of column indices. As this problemisacoveringproblemonemayhopetouseKnuth’sdancinglinksprogram [13].Thisonlysolvesexactcoverproblems,wealsotriedamodifiedversionwhich uses thefast originaldatastructureofthedancinglinksprogram. The size of the computational problem is given by the size of the matrix D. A linear code C, where we can apply algorithm 1 has about 5000 codewords. An exceptional situation is a code where the size of the minimum weight generator is small, i.e. the coefficient A of the weight enumerator w is small. The algorithm d C allowsto handleproblemsin thesame sizelikeotherproposed algorithms(e.g. Q- extension [4], special puncturing [10], descent method [3]) used for the search of codes withimprovedminimumdistanced forfixed parameters n,k,q. To apply (l,s)−extension to a code C, we need to know the minimum weight generatorofthecode.Itisknown[20]thatalreadythecomputationoftheminimum weight(whichislessinformation)isNP−hard.Thesameistrueifwewanttouse other ([11,14,16,17,19]) extendability results, where information about the weight enumeratorisnecessary. If we try (l,s)−extension on a code, constructed using the methods described in [5,6,7,8], we already got during this construction the representatives of the mini- mum weight generator. On the other hand codes which can be handled using this methodare in mostcases smallenough, and to computetheminimumweight gen- 6 erator using complete enumeration or more sophisticated algorithms based on ad- vanced methods for the computation of the minimum distance [1,10] is ’cheap’ compared tothetimenecessary torun algorithm1. An obvious generalization is to take into account not only the words of minimum weight d but also words with weight d+1,...,d+s. Building the corresponding intersection matrix together with the system of equations would allow to look for an (l,s)−extension(s > 1)in thecasewhere thereis nogap ofsizes between the twosmallestweights. Exampleand Results We found a new [82,8,49]q=3 code, which is a (2,1)−extension of a previously computed [80,8,48]3 code with 1320 codewords of minimum weight. The corre- spondingDiophantinesystemofequationshas(38−1)/2 = 3280variables(=pos- sible columns for extension) and 1320/2 = 760 equations. Among all possible pairs ofcolumnswefounda coveringpairofpossiblegeneratormatrixcolumns. Thisnewcodecanbeextendedtwiceusing(1,1)−extension,givingnew[83,8,50]3 and[84,8,51]3codes.Forthelastoneitwasagainpossibletoapply(2,1)−extension followed by an (1,1)−extension giving new [86,8,52]3 and [87,8,53]3 codes and a last (1,1)−extensionfinally ended at an optimal (no larger minimum distance is possibleforthesevaluesofn,k,q)[88,8,54]3 code.Thisisaself-orthogonalcode, butthelast twofoldextensionisnotcoveredby thetheorem[19]ofvanEupenand Lisonek,as therearecodewordsofweight2 mod3 inthe[86,8,52]3 code. Otherrecently foundcodes using(l,s)−extensionhavethefollowingparameters: [132,8,81]3,[197,6,142]4,[212,6,153]4,[227,6,165]4,[232,6,169]4,[242,6,177]4, [247,6,181]4. All these codes are improvements of Brouwers on-line table [9] of codes, where one can look up the largest known minimum distance for given triples of (n,k,q) together with the best known upper bound for the maximum possible minimum distance. References [1] A. BETTEN, M. BRAUN, H. FRIPERTINGER, A. KERBER, A. KOHNERT, AND A. WASSERMANN, Errorcorrecting codes, Springer, 2006. [2] J. BIERBRAUER, Introduction to coding theory., Discrete Mathematics and its Applications. BocaRaton,FL:Chapman&Hall/CRC.xxiii,390p.,2005. [3] I. BOUKLIEV, A method for construction of good linear codes and its application to ternary and quaternary codes. Optimal codes and related topics. Proceedings, international workshop, May 26 - June 1, 1995. Sozopol, Bulgaria. Shumen: Panorama.15-20(1995).,1995. 7 [4] I. BOUYUKLIEV AND J. SIMONIS, SomenewresultsonoptimalcodesoverF5.,Des. CodesCryptography, 30(2003), pp.97–111. [5] M. BRAUN, Construction of linear codes with large minimum distance, IEEE Transactions onInformation Theory,50(2004), pp.1687–1691. [6] M. BRAUN, A. KOHNERT, AND A. WASSERMANN, Construction of (n,r)-arcs in PG(2,q),Innovations inIncidence Geometry,1(2005), pp.133–141. [7] , Construction of (sometimes) optimal linear codes, Bayreuther Mathematische Schriften, 74(2005), pp.69–75. [8] , Optimal linear codes from matrix groups, IEEE Transactions on Information Theory,12(2005), pp.4247–4251. [9] A. BROUWER,Linearcodebounds. http://www.win.tue.nl/˜aeb/voorlincod.html. [10] M. GRASSL AND G. WHITE, New good linear codes by special puncturing, in ProceedingsInternationalSymposiumonInformationTheory,2004.ISIT2004,2004, p.454. [11] R.HILL,Anextensiontheoremforlinearcodes.,Des.CodesCryptography,17(1999), pp.151–157. [12] R. HILL AND P. LIZAK, Extensions of linear codes, in Proceedings International Symposium onInformation Theory,1995, 1995,p.345. [13] D. KNUTH, Dancing links, inMillenial Perspectives inComputer Science, J.Davies, B. Roscoe, and J. Woodcock, eds., Palgrave, Houndmills, Basingstoke, Hampshire, 2000, pp.187–214. [14] T. MARUTA, On the extendability of linear codes., Finite Fields Appl., 7 (2001), pp.350–354. [15] , A new extension theorem for linear codes., Finite Fields Appl., 10 (2004), pp.674–685. [16] ,Extendabilityofquaternarylinearcodes.,DiscreteMath.,293(2005),pp.195– 203. [17] , Extendability of ternary linear codes., Des. Codes Cryptography, 35 (2005), pp.175–190. [18] J. SIMONIS,Addingaparity-checkbit.,IEEETrans.Inf.Theory,46(2000),pp.1544– 1545. [19] M.VANEUPEN ANDP.LISONEˇK,Classificationofsomeoptimalternarylinearcodes ofsmalllength.,Des.CodesCryptography, 10(1997),pp.63–84. [20] A. VARDY, The intractability of computing the minimum distance of a code., IEEE Trans.Inf.Theory,43(1997), pp.1757–1766. [21] A. WASSERMANN, Finding simple t-designs withenumeration techniques., J.Comb. Des.,6(1998), pp.79–90. 8