Linear Codes - Michigan State University

1 Chapter 3 Linear CodesIn order to define Codes that we can encode and decode efficiently, we add morestructure to the codespace. We shall be mainly interested in Linear Codes . Alinear codeof lengthnover the fieldFis a subspace ofFn. Thus the words oflinear codethe codespaceFnare vectors, and we often refer to codewords the first section we develop the basics of Linear Codes , in particular weintroduce the crucial concept of the dual of a code . The second and third sectionsthen discuss the general principles behind encoding and decoding Linear encounter the important concept of a BasicsIfCis a Linear code that, as a vector space over the fieldF, has dimensionk,then we say thatCis an [n,k] Linear codeoverF, or an [n,k] code , for short.[n, k] Linear codeThere is no conflict with our definition of the dimension ofCas a code , since|C|=|F|k. (Indeed the choice of general terminology was motivated by thespecial case of Linear Codes .) In particular the rate of an [n,k] Linear code isk/n.

2 IfChas minimum distanced, thenCis an [n,k,d] Linear code numbern kis again begin to useF2in preference to{0,1}to denote our binary alphabet,since we wish to emphasize that the alphabet carries with it an arithmeticstructure. Similar remarks apply to ternary (i) The repetition code of lengthnoverFis an [n,1, n] Linear code .(ii) The binary parity check code of lengthnis an [n, n 1,2] linearcode.(iii) The [7,4], [8,4], and [4,2] Hamming Codes of the introductionwere all defined by parity considerations or similar equations. We shallsee below that this forces them to be Linear .(iv) The real Reed-Solomon code of our example is a [27,7,21] linearcode over the real 3. Linear Codes ( )Theorem. (Shannon s theorem for Linear Codes .)LetFbe afield withmelements, and consider amSC(p)withp <1/m. SetL ={ Linear Codes overFwith rate at least }.ThenL is a Shannon family provided < Cm(p).2 Forney (1966) proved a strong version of this theorem which says that we needonly consider those Linear Codes of lengthnwith encoder/decoder complexityon the order ofn4(but at the expense of using very long Codes ).

3 Thus thereare Shannon families whose members have rate approaching capacity and are,in a theoretical sense, weight(for short,weight) of a vectorvis the number of itsHamming weightnonzero entries and is denoted wH(v). We have wH(x) = dH(x,0). Themini-mum weightof the codeCis the minimum nonzero weight among all codewordsminimum weightofC,wmin(C) = min06=x C(wH(x)).( ) a field, Hamming distance is translation invariant. Inparticular, for Linear Codes , the minimum weight equals the minimum dH(x,y) = dH(x z,y z) for allz. In particulardH(x,y) = dH(x y,y y) = dH(x y,0).2A consequence of the lemma is that minimum distance for Linear Codes ismuch easier to calculate than for arbitrary Codes . One need only survey|C|codewords for weight rather than roughly|C|2pairs for course the minimum weight of the lengthnrepetitioncode isn. Also the minimum weight of the parity check code is clearly minimum weight of the length 27 real Reed-Solomon code is equal toits minimum distance which we found to be 21.

4 We listed the codewordsof the [4,2] ternary Hamming code , and so it visibly has minimum that the minimum weight of the [7,4] Hamming code is 3 iseasy to do directly by hand, but we will give a conceptual way of doingthis calculation below. The extended [8,4] Hamming code adds an overallparity check bit to the [7,4] code , so its minimum weight is following elementary property of binary weights can be very instance, it proves directly that the parity check code is Linear .( ) that, for binary vectorsxandyof the same length, wehavewH(x+y) = wH(x) + wH(y) 2wH(x y)wherex yis defined to have a1only in those positions where bothxandyhave BASICS33 The matrixGis aspanning matrixfor the Linear codeCprovidedC=spanning matrixRS(G), the row space ofG. Agenerator matrixof the [n,k] Linear codeCovergenerator matrixFis ak nmatrixGwithC= RS(G). Thus a generator matrix is a spanningmatrix whose rows are linearly independent. We may easily construct manycodes using generator matrices.

5 Of course it is not clear from the matrix howgood the code will (i) The repetition code has generator matrixG=h1,1, .. ,1i.(ii) A particularly nice generator matrix for the parity check code is2666666641 0 0 0 0 10 1 0 0 0 10 0 1 0 0 0 0 1 0 10 0 0 0 1 1377777775,composed of all weight 2 codewords with a one in the last column. Thiscode will have many other generator matrices as well. Here are two forthe [7,6] parity check code :266666641 1 0 0 0 0 01 0 1 0 0 0 01 0 0 1 0 0 01 0 0 0 1 0 01 0 0 0 0 1 01 0 0 0 0 0 137777775,266666641 1 1 1 1 1 01 0 1 0 0 0 01 1 0 1 0 1 11 1 1 0 1 0 00 0 0 0 0 1 11 1 1 1 0 0 037777775.(iii) Consider the [7,4] Hamming code of Example In turn weset the four message symbols (X3, X5, X6, X7) to (1,0,0,0), (0,1,0,0),(0,0,1,0), and (0,0,0,1).

6 The four resulting codewords form the rows ofa generator matrix . We find26641 1100 0 01 0011 0 00 1010 1 01 1010 0 13775(iv) A generator matrix for the [8,4] extended Hamming code of Ex-ample results from adding a column at the front to that for the [7,4] code , each new entry checking parity of that row in the matrix . We have26641 1 1 1 0 0 0 01 1 0 0 1 1 0 01 0 1 0 1 0 1 00 1 1 0 1 0 0 137751 Oxymoron!34 CHAPTER 3. Linear Codes (v) For a generator matrix of the [4,2] ternary Hamming code of Ex-ample , we may set (a, b) equal to (1,0) and (0,1) in turn to get thematrix 1 0 1 20 1 1 1 ,although any pair of codewords would do as rows provided one is not amultiple of the other. For instance 0 1 1 11 1 2 0 is also a generator matrix .( ) that, in a Linear code over the fieldFq, either all of thecodewords begin with0or exactly1/qof the codewords begin with0.

7 (You might wantfirst to consider the binary case.)( ) an[n, k, d] Linear code over the fieldFq.(a)Prove that the sum of all the weights of all the codewords ofCis at mostn(q 1)qk 1. (Hint:Use the previous problem.)(b)Prove that the minimum distancedofCis at mostn(q 1)qk 1qk 1. (Hint:Theminimum weight is less than or equal to the average nonzero weight.)(c)Prove the Plotkin bound for Linear Codes withd/n >(q 1)/q:|C| dd q 1qn.( ) the Plotkin bound for a generalm-ary codeCof lengthnand minimum distancedwithd/n >(m 1)/m:|C| dd m 1mn.(Hint:Find an upper bound on the average nonzero distance between codewords bycomparing all distinct pairs of codewords and examining each coordinate position inturn.)LetCbe any code (not necessarily Linear ) inFn, forFa field. ThedualcodeofC, denotedC , is the codedual codeC ={x Fn|x c= 0,for allc C},wherex cis the usual dot product. The dual ofCis Linear even ifCis not.(This is often a good way of proving that a given code is Linear .)

8 We can inturn examine the dual of the dual and discover easily that (C ) =C itself a Linear code , then in factC =C. For instance, the dual ofthe binary repetition code of lengthnis the parity check code of lengthn; andthe dual of the parity check code of lengthnis the repetition code of see thatC =Cfor linearC, we use another description ofC . LetGbe a generator matrix forC. Thenxis inC if and only ifGx>=0. BASICS35the vectors ofC are precisely the transposes of the vectors of the null spaceNS(G). Therefore by Theorem the dimension ofCplus the dimension ofC equals the lengthn, that is,C has dimensionn k. Calculating dimensionstwice, we learn thatC has dimensionk. As this space containsCand hasthe same dimension asC, it is equal toC. In summary:( ) an[n,k] Linear code overF, then its dualC is an[n,n k] Linear code overFandC = Linear codeCisself-orthogonalifC Cand isself-dualifC = , for instance, a binary repetition code of even length is self-orthogonal, as isthe [7,3] binary dual Hamming code .

9 Since the dimension of a code plus that ofits dual add up to the length, a self-dual code must be a [2k,k] Linear code , forsomek. The [8,4] extended Hamming code is self-dual, as can be easily checkedusing the generator matrix given above. The ternary [4,2] Hamming code isalso self-dual, as is easily generator matrixHfor the dual codeC of the linearCis sometimescalled acheck matrixforC. In general it is not difficult to calculate a checkcheck matrixmatrix for a code , given a generator matrixG. Indeed if we pass to a generatorinRREF, then it is easy to find a basis for the null space and so forC byfollowing the remarks of Section of the appendix. In particular, if thegenerator matrixG(or itsRREF) has the special form[Ik k|Ak n k]then one check matrix isH=[ A>n k k|In k n k].( ) a binary code of length16written as4 4squarematrices. The codeEis composed of every4 4binary matrixMsuch that:(i)every row ofMcontains an even number of1 s; and(ii) eitherevery column ofMcontains an even number of1 sorevery column ofMcontains an odd number of1 s.

10 (a)Prove thatEis a Linear code .(b)What is the dimension ofE?(c)What is the minimum distance ofE?(d)If the matrix26641 0 0 00 1 0 00 0 0 00 0 0 03775is received, give all possible decodings subject toMDD. That is, find all code matricesinEthat are at minimum distance from this 3. Linear Codes ( ) a binary code of length21whose words are written asarrays in the following gem shape:x1x2x3x4x5x6x7x8x9x10x11x12x13x14x 15x16x17x18x19x20x21 The codeEis composed of every binary arrayMof this shape and such that:(i)every row ofMcontains an even number of1 s; and(ii)every column ofMcontains an even number of1 s.(a)Prove thatEis a Linear code .(b)What is the dimension ofE?(c)What is the minimum distance ofE?(d)If the array0 1 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0is received, give all possible decodings subject toMDD. That is, find all codewords inEthat are closest to this array.(e)If the array1 0 11 1 1 1 10 1 1 1 01 1 1 1 11 0 1is received, give all possible decodings subject toMDD.