[6],“Codes on graphs:Generalized state realizations,”IEEE Trans.Inform.Theory,submitted for publication.[7]T.Kasami,T.Takata,T.Fujiwara,and S.Lin,“On the optimum bit orderswith respect to the state complexity of trellis diagrams for binary linear codes,”IEEE rm.Theory,vol.39,pp.242–245,Jan.1993.[8]R.Kötter and A.Vardy,“Construction of minimal tail-biting trellises,”in Proc.IEEE Information Theory Workshop,Killarney,Ireland,June 1998,pp.72–74.[9] F.R.Kschischang and V.Sorokine,“On the trellis structure of blockcodes,”IEEE rm.Theory,vol.41,pp.1924–1937,Nov.1995.[10] fourcade and A.Vardy,“Optimal sectionalization of a trellis,”IEEE rm.Theory,vol.42,pp.689–703,May1996.[11] C.-C.Lu and S.-H.Huang,“On bit-level trellis complexity ofReed–Muller codes,”IEEE rm.Theory,vol.41,pp.2061–2064,Nov.1995.[12]R.J.McEliece,“On the BCJR trellis for linear block codes,”IEEErm.Theory,vol.42,pp.1072–1092,July1996.[13] D.J.Muder,“Minimal trellises for block codes,”IEEE rm.Theory,vol.34,pp.1049–1053,Sept.1988.[14]V.R.Sidorenko,“The Euler characteristic of the minimal code trellisis maximum,”rm.Transm.,vol.33,no.1,pp.87–93,Mar.1997.[15]G.Solomon and H.C.A.van Tilborg,“A connection between block andconvolutional codes,”SIAM J.Appl.Math.,vol.37,pp.358–369,Oct.1979.[16]R.M.Tanner,“A recursive approach to low complexity codes,”IEEErm.Theory,vol.IT-27,pp.533–547,Sept.1981.[17] A.Vardy,“Trellis structure of codes,”in Handbook of Coding Theory,V.S.Pless and W.C.Huffman,Eds.Amsterdam,The Netherlands: Elsevier,Dec.1998.[18] A.Vardy and F.R.Kschischang,“Proof of a conjecture of McEliece re-garding the expansion index of the minimal trellis,”IEEE rm.Theory,vol.42,pp.2027–2034,Nov.1996.[19]V.K.Wei,“Generalized Hamming weights for linear codes,”IEEErm.Theory,vol.37,pp.1412–1418,Sept.1991.[20]N.Wiberg,“Codes and decoding on general graphs,”Ph.D.dissertation,Dept.Elec.Eng.,Univ.Linköoping,Sweden,Apr.1996.[21]N.Wiberg,H.-A.Loeliger,and R.Kötter,“Codes and iterative decodingon general graphs,”Euro.Trans.Telecommun.,vol.6,pp.513–526,Sept.1995.Bounds on the State Complexity of Codes from the Hermitian Function Field and its SubfieldsYaron Shany and Yair Be’ery,Senior Member,IEEEAbstract—An upper bound on the minimal state complexity of codes from the Hermitian function field and some of its subfields is derived.Coor-dinate orderings under which the state complexity of the codes is not above the bound are specified.For the self-dual Hermitian code it is proved that the bound coincides with the minimal state complexity of the code.Finally, it is shown that Hermitian codes over fields of characteristic2admit a re-cursive twisted squaring construction.Index Terms—Geometric Goppa codes,Hermitian codes,minimal state complexity,trellises,twisted squaring construction.I.I NTRODUCTIONA trellis diagram can be regarded as an efficient representation of a code for the purpose of soft-decision decoding.Formally,a trellisManuscript received September29,1999;revised March9,2000.The authors are with the Department of Electrical Engineering–Systems, Tel-Aviv University,Ramat-Aviv69978,Israel(e-mail:shany@eng.tau.ac.il; ybeery@eng.tau.ac.il).Communicated by I.F.Blake,Associate Editor for Coding Theory. Publisher Item Identifier S0018-9448(00)05294-9.T=(V;E)of rank n is a finite-directed graph,with vertex set V and edge set E,in which every vertex is assigned a“depth”in the range f0;1;111;n g,and each edge connects a vertex at depth i01to one at depth i,1 i n.The class of vertices at depth i,0 i n,is de-noted by V i.We assume that each edge of T is labeled with an elementofq(i.e.,C is a k-dimensional subspaceofthat Hermitian codes over fields of characteristic 2admit a recursive twisted squaring construction [3],[2].II.G EOMETRIC G OPPA C ODES AND H ERMITIAN C ODESThis section contains a brief description of geometric Goppa codes in general,and codes from the Hermitian function field and some of its subfields in particular.A lower bound on the minimal state com-plexity of geometric Goppa codes is presented.We follow the nota-tion of Stichtenoth [14],and the reader is referred to [14]for the basic theory of algebraic function fields and a detailed description of geo-metric Goppa codes.Let F=K be an algebraic function field of genus g over a constant field K=F .For a divisor A of F=K we setL (A ):=f x 2F j (x ) 0A g [f 0gwhere (x )is the principal divisor of x .We denote by dim A and deg A the dimension of L (A )over K and the degree of A ,respectively.Let f P 1;P 2;111;P n g be a set of pairwise distinct places of degree 1in F=K ,and define the divisor D of F=K as D :=P 1+P 2+111+P n .Suppose that G is a divisor of F=K with supp G \supp D = ,where supp A stands for the support of the divisor A .The geometric Goppa code C L (D;G )associated with the divisors D and G is defined byC L (D;G ):=f (z (P 1);z (P 2);111;z (P n ))j z 2L (G )g1+12deg G 012d n=2e +1+12deg G 012b n=2ce f d e e cedi g di c e em e b e e g e e e e e e f e co d es dco d es fr cer b fi e d f e e fu c fi e d LetK=,and let F =K (x;y )be the function field defined byF =K (x;y )with y q +y =x a and a j q +1(see [14],[20]).When a =q +1,F=K is called the Hermitian function field over K .When a <q +1,F=K is isomorphic to a subfield of the Hermitian function field [14],[20],and is,therefore,referred to as a subfield of the Hermitian function field.The genus of F=K is g =(q 01)(a 01)=2,and there are exactly 1+q (1+a (q 01))places of degree one in F=K .Let P 1be the pole of xinK (x ).The places inf P 1g [f P j 2K g ,are exactly all the places of degree 1inFlying over P that contains (y 0 )[14].Thisplace is denoted by P ; .In fact,all places of degree one in F=K are exactlyf P ; j 2U; q + = ag [f Q 1gwhere Q 1is the common pole of x and yin2Uthe results of[13],it was mentioned in[20]that for the non-Hermitian case,there is an n2n diagonal matrix A=(a ij)with0=a ii2K,1 i n,such that the dual of C m is C n+2g020m A.Moreover,ifa 1mod p,where p is the characteristic of K,then the dual of C m is C n+2g020m.In order to give a description of C m similar to the one given in [19](where only the Hermitian case was considered),some additional definitions are required.Let D be the divisor of K(x)=K defined by D:=+ and a length-n0(n0being a positive integer)linear code C,defineC[l]:=;111;cn)2Cmam0jaqF are mapped to consecutiveindices,that is,for every P ; 2supp(D),it holds thatq(Ind(P )01)+1 Ind(P ; ) q(Ind(P )):Let6=( ij)be the n2n diagonal matrix defined by ii= ;1i n,if i=Ind(P ; )for some 2U.Define the matrixG m byG m:=G k(0)G k(1)6...Gk( )6:(3)Then it follows directly from the definition of the code C m and theabove described basis of L(mQ1)that if m<n,then G m is a gen-erator matrix of C m under a valid coordinate ordering[19].III.A N U PPER B OUND ON THE S TATE C OMPLEXITY OF THE C ODESIn this section,we use the generator matrix given in the previoussection to show that,for some values of m,when C m is under a validcoordinate ordering its state complexity is below the Wolf bound.Forthe self-dual Hermitian code C(q0q02)=2(q is a power of2),weshall see that an improvement of q2=4upon the Wolf bound is possible.Furthermore,for this case we shall see that q2=4is the maximum pos-sible improvement upon the Wolf bound over all coordinate orderingsof the code.Let C be an[n0;k;d]code,and let G be a minimal-span generatormatrix(MSGM)of C[7](i.e.,G is a generator matrix of C in whichthere are no two rows whose first nonzero entries are at the same index,and no two rows whose last nonzero entries are at the same index).Thens i;1 i n001;is equal to the number of active rows in G at indexi[5],[7],where s0;s1;111;snmin;if q j imin;otherwise(4)for i2f0;1;111;n g.Proof:Suppose that C is a length-n0(n0being a positive integer)linear code over afinite field K0,l2Note that for the cases where dim C m>n=2,the bound on the statecomplexity profile of C m is identical to the bound on the state com-plexity of C n+2g020m,where the latter can be obtained from Proposi-tion2.This follows from combining the fact that the state complexityprofiles of a linear code and its dual are identical[3],and the factthat there is a diagonal matrix A(in which every diagonal element isnonzero)such that C n+2g020m A is the dual of C m.(Observe thatthe state complexity profile of C n+2g020m A is identical to that ofC n+2g020m.)As a result of Proposition2,we have the following corollary.Corollary3:Let(s0;s1;111;s n)be as in Proposition2,and letm0:=q b n2qc.Then for m0 m n+2g020m0and q 4,wehave that max0 i n=q s iq is smaller than the Wolf bound by at leastjj=0(k(j)0(n=q0k(j)))where j m:=b(~m0m0)=a c,and~m:=min(m;n+2g020m).Proof:Let us first assume that m0 m b n=2c+g01.Underthis assumption dim C m b n=2c,and we can use(4).Sincedim C m=d n=2e +g 01 m n +2g 020m 0follows (as before)from the fact that the state complexity profiles of a linear code and its dual areidentical.(2j +1)a +12q(q +1)a 0t 40q2=2+g 01is smaller than that obtained in Corol-lary 4.This will be done using the DLP bound on the state complexityprofile,and will require some results concerning the GHW hierarchy of Hermitian codes.From this point on,we consider only the Hermi-tian case a =q +1.Let p r ;r 1;be the r th pole number [14]of Q 1.Then f p r j r 1g is the semigroup generated by q and q +1.For m <n =q 3,the Hermitian code C m is nonabundant [8],and we haved r (C m ) q 30m +p r ;1 r k;(5)where d r (C m )is the r th generalized Hamming weight [17]of C m and k :=dim C m [20,Footnote 2and Theorem 12],[8,Corollary 2and Lemma 2].For an integer l 0define I (l ):=f u j u as a pole number of Q 1;u l g .Lemma 5:For 1 i q 3and m <q 3,we havek i (C m ) I (i 0(q 30m ))where k i (C m )is the i th entry of the DLP [4]of C m .Proof:Recall that for a length-n linear code C we havek i (C )=jf d r (C )j d r (C ) i gj ;1 i n[4],where k i (C )is the i th entry of the DLP of C .The lemma then follows from(5).The main result of this section can now be stated.Theorem 7:Let q 4be a power of 2,and letm =q 3=2+g 01=q 3=2+q 2=20q=201:Then the minimal state complexity of the self-dual Hermitian code C m is exactly q 3=20q 2=4.The minimal state complexity is achieved when C m is arranged under a valid coordinate ordering.Proof:In view of Corollary 4,we only have to find a single index i;1 i q 3,for which the DLP bound on the state complexity profile of C m is q 3=20q 2=4.We choose i =q 3=20q=2.By Lemma 5and Remark 6we obtain that k i (C m )+k q 2In this section it is shown that Hermitian codes over fields of char-acteristic 2admit a recursive twisted squaring construction [3],[2].Upper bounds on the state complexity profile of linear codes admit-ting a twisted squaring construction were given in [2].Whereas the fact that some Hermitian codes admit a twisted squaring construction does not seem to contribute any knowledge regarding their trellis com-plexity beyond what is already given in Section III,it seems that the fact that these codes do admit such a construction is of interest.Let C be an [n;k;d ]code over the finite field K ,let I :=f 1;2;111;n g ,and let J :=f j 1;j 2;111;j j J j g be a subset of I:The projection of c =(c 1;c 2;111;c n )2C onto J is defined by c J :=(c j ;111;c jc 2C c J.The J -subcode of C ,C J ,is the subcode of C consistingof all codewords (c 1;c 2;111;c n )2C with c i =0for all i 2I n J ,where I n J stands for the complementary set of J in I .For 1 i !leq n we define i 0:=f 1;2;111;i g .Similarly,for 0 i n 01,i +stands for f i +1;i +2;111;n g .The code C is said to admit a twisted squaringconstruction if it is of even length,and both C (n=2)and (C (n=2)=(C (n=2)(see [2]for a detailed exposition of the subject).When C admits a twisted squaring construction,we say that C (n=2))(n=2)+,then the code C is said to admit a recursivetwisted squaring construction when not only that the code itself admits a twisted squaring construction,but also its component codes admit a twisted squaring construction,the component codes of the component codes admit a twisted squaring construction,and so forth.Proposition 8:Let C m be the Hermitian code over K=,whereq 2=2l for some even l2q qqqqqq q= q +1v + q u + , = u + (and indeed v q +v =u q +1).Choose a basis f a 1;a 2;111;a l gfor=q=ql2defined by==1i 2i 01+l=2qqqfor some 02with q0+ 0= q +1.Hence,the above choice of a basisfor==2)=2)=2)=2)=2)=2)q .For 1 i l=2,the existence of the automorphisms corresponding to =1, =0,and with i =1and j =0for j =i ,1 j l completes the proof,since,under the above defined coordinate ordering,these auto-morphisms show that all the relevant component codes are symmetric ,and hence admit a twisted squaring construction [2,Theorem3].),”IEEE Trans.Inform.Theory ,vol.34,pp.1345–1348,Sept.1988.[13],“Self-dual Goppa codes,”J.Pure Appl.Math.,vol.55,pp.199–211,1988.[14],Algebraic Function Fields and Codes .Berlin,Germany:Springer-Verlag,1993.[15]A.Vardy,“Trellis structure of codes,”in Handbook of Coding Theory ,V .S.Pless and W.C.Huffman,Eds.Amsterdam,The Netherlands:Elsevier,Dec.1998.[16] A.Vardy and Y .Be’ery,“Maximum-likelihood soft decision decoding of BCH codes,”IEEE rm.Theory ,vol.40,pp.546–554,Mar.1994.[17]V .K.Wei,“Generalized Hamming weights for linear codes,”IEEE rm.Theory ,vol.37,pp.1412–1418,Sept.1991.[18]J.K.Wolf,“Efficient maximum likelihood decoding of linear block codes using a trellis,”IEEE rm.Theory ,vol.IT-24,pp.76–80,Jan.1978.[19]T.Yaghoobian and I.F.Blake,“Hermitian codes as generalized Reed-Solomon codes,”Des.,Codes,Cryptogr.,vol.2,pp.5–17,1992.[20]K.Yang,P.V .Kumar,and H.Stichtenoth,“On the weight hierarchy of geometric Goppa codes,”IEEE rm.Theory ,vol.40,pp.913–920,May 1994.A Class of Linear Codes with Good Parameters fromAlgebraic CurvesChaoping Xing and San LingAbstract—A class of linear codes with good parameters is constructed in this correspondence.It turns out that linear codes of this class are subcodes of the subfield subcodes of Goppa’s geometry codes.In particular,we find 61improvements on Brouwer’s table [1]based on our codes.Index Terms—Algebraic curves,algebraic-geometry codes,subfield sub-codes.I.I NTRODUCTIONAlgebraic-geometry codes constructed by Goppa [2]make use of algebraic curves with many rational points.These codes have excel-lent asymptotic parameters.In particular,the q -ary Gilbert–Varshamov bound was broken by Goppa’s geometric codes for some sufficiently large q [8],[3].However,for small q ,it seems difficult to find many good codes by Goppa’s construction.The reason is that the number of rational points of an algebraic curve over F q is not satisfactory to construct good Goppa’s geometric codes for small q .In order to increase the length of geometric codes,researchers have been looking for possibilities to use points over some extensions of F q to construct good codes [5],[10],[11],[4],[12].In this correspondence,we make use of curvesManuscript received July 23,1999;revised February 14,2000.This work was supported under the NUS Grant R-146-000-018-112.The authors are with the Department of Mathematics,National Univer-sity of Singapore,Singapore 117543(e-mail:xingcp@.sg;matlings@.sg).Communicated by I.F.Blake,Associate Editor for Coding Theory.Publisher Item Identifier S 0018-9448(00)05020-3.0018–9448/00$10.00©2000IEEE。
![[17] A. Vardy, “Trellis structure of codes, ” in Handbook of Coding Theory,](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/0ba90dd6360cba1aa811dad9.webp)
