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.

2 [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. 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 .

3 (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 ).

4 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).

5 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. 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.

6 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).

7 Thus a generator matrix is a spanningmatrix whose rows are linearly independent. We may easily construct manycodes using generator matrices. 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.

8 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).

9 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.

10 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. (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.)