### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Coding Theory and Practice in Communication ECE 7670

Utah State University

GPA 3.77

### View Full Document

## 8

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 48 page Class Notes was uploaded by Nelle Braun DDS on Wednesday October 28, 2015. The Class Notes belongs to ECE 7670 at Utah State University taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/230402/ece-7670-utah-state-university in ELECTRICAL AND COMPUTER ENGINEERING at Utah State University.

## Reviews for Coding Theory and Practice in Communication

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/28/15

ECE 7670 Lecture g nt Introduction to multipleerror correcting codes Objective To demonstrate important concepts that lead to more general families of codes to introduce the idea behind Galois elds We have seen how the Hamming code can be used to correct single errors and met syndrome decoding and standard arraysl We have also seen that the storage andor decoding complexity could be very high What is needed to deal with this complexity is some sort of structure While linear algebra provides some structure more algebraic structure is needed The material in these lecture notes is drawn from Elwyn Berlkamp Algebraic Coding Theory McGrawHill 1968 The book is de nitely a classic in coding and should be explored by all who are truly interested in this materiall Of this material Berlekamp writes The student is urged to study the next section with care In my opinion it is the most important section of the book77 irst a reminder For a Hamming code we can look at the syndrome and determine from the column corresponding what the error location is For example if we write Hh1 h2 hn the syndrome rHT hi where 239 indicates the location of the error assuming of course that there is only one i Let us take the case of a 3126 Hamming code and write the parity check matrix as a H HOOOO OHOOO HHOOO 1 1 1 1 1 OHHHH That is for this example we order the columns in binary numerical order We will consider each column as a 5tuple and also write this as Hl71 72 73 730 731 where the ith column of H has the binary representation of i in the symbol 71x Now let us move beyond Hamming codes and attempt to formulate a double error correcting code We will do this in this example by starting with the same parity check matrix but not adding 5 more rowsl We will denote this as HHHH 1 1 1 1 1 0 1 0 1 f11 132 f13 39 f130 f131 f23 quot39 f230 f231 f31 1H2 f33 quot39 f330 f331 f43 quot39 f430 f431 f51 f52 f43 quot39 f530 f531 EOE 7670 Lecture g nt 7 Introduction to multipleerror correcting codes 2 The argument tells which column we are dealing with and the subscript tells which bit Another way to think about this that is notationally important is to have a function which maps binary 5tuples to binary 5tuplesi In the shorthand notation we could write H 71 72 73 quot39 730 731 le f72 st quot39 730 169731 We might have for example 7 or l l l l l7i To do much more than this simple stuff however we need some way of dealing with these 5tuples as objects in their own right We need to develop and appropriate arithmetic add subract multiply divider Adding is easy iwe simply go component by componenti But how do we multiply The key here is to think of each 5tuple as corresponding to a polynomial of degree S 4 For example 00000 H 0 00001 H1 00010 H z 00100 H z 10101 H z4z21 Note that each coefficient of the polynomials is binary we assume that addition is modulo 2 ie over GF2i Clearly addition of polynomials accomplishes exactly the same thing as addition of the vectors They are isomorphic How can we multiply We want our polynomials representing the 5tuples to have degree S 4 and yet when we multiply the degree may exceed that For example 13zlz4zgzlz7zs153142131221lz715z5z412li To reduce the degree we choose some polynomial of degree 5 and reduce the product modulo That is we divide by and take the remainder Analogous to multiplication modulo and integer Let us take I5 12 1 Performing the division we get a quotient of 12 z l and remainder of 13 12 1 Then we can write 13zlz4zgzlz715z5z4z2l 1312z mod1512li In general we write 141 E az mod iff there is a polynomial 41 such that 141 4IMI a Now before we proceed some facts about modulo operations these go way back to Gauss EOE 7670 Lecture g nt 7 Introduction to multipleerror correcting codes 3 o If a1 E 141 mod and 21 E B1 mod Then a1 i 121 E 141 i B1 mod a1b1 E 141B mod Our modulo operations allows us now to add subtract and multiply these 5 tuples considered as polynomials modulo some Can we divide More fun damentally given a polynomial a1 is there some other polynomial 141 7 we may consider it a multiplicative inverse or a reciprocal 7 such that a1141 E 1 mod The answer lies in the oldest algorithm in the world More details later For polynomials a1 and 121 there exist polynomials 141 and B1 such that aIAI 9031 ar7br where a1 is the standard notation for the greatest common divisor of a1 and Does this provide the answer Well suppose that a1b1 1 then we have a1141 b1B 1 We can then say that a1141 E 1 mod 121 So if we put in the role of 121 we have the answer In order to have this work for any a1 we need to ensure that a1M1 l for any a11 This means that we need to have no factors 7 it is irreduciblei This is quite analogous to being a prime number Show that 15 12 l is irreducible Observe that when we have a1141 E 1 mod M1 we can say that division by a1 is equivalent to multiplication by 141 when operations are done modulo Now let us suppose that there are two errors occuring at positions ii and i2 Since the code is linear we can suppose that we can write r00111 1 1 0m0 i1 i2 We nd rHT5132 with m m S1 EOE 7670 Lecture g nt 7 Introduction to multipleerror correcting codes 4 flt7i1 f7i2 82 We will write this as 717281 le 1672 82 If we set our function up correctly we will have two equations in two unknowns which we could solve for 7 which in turn will determine 239 since 7 is in this case simply the binary representation of Let us consider some possible simple functionsi One might be a simple mul tiplication az7z mod But this would lead to a dependent equation 32 asl the new parity check equations would tell us nothing newi We could try 7 a This would not help since we would always have 32 31 Let us try some powersi Say 72 We would then obtain 717281 Vi722 82 This looks like independent equations but we have to remember that we are dealing with operations modulo 2 Notice that 8 71 722 7 722 27172 7 75 82 We have only the redundant s 82 the second equation is the square of the rst and conveys no new information Try 73 Now the decoder equations are 717281 These are independent Now let s see what we can do to solve this We can do more or less conventional algebraic manipulation keeping in the back of our mind how we do multiplication and division i We can write 82 7 73 71 727 7 7172 75 817 7172 75 S17172 7 3 Hence we have the two equations 717281 2 52 7172 31 81 if 31 f 0 Note that the rst deals with sums of values and the second with products We can combine these into a quadratic 7817s 3 amp EOE 7670 Lecture g nt 7 Introduction to multipleerror correcting codes 5 S 723173i8 20 1 W 1 sw l a 32 0 1 For reasons hopefully to made clear later it is more useful to deal with the recip rocals of the roots The polynomial 41 is said to be an error locator polynomial The roots of the quadratic 41 can be reciprocated to nd 71 and 72 How to nd the roots If there is only one error then 71 31 and 7 82 and we end up with the equation 1 317 1 0 And if there are no errors then 31 32 0 Let us summarize the steps we have taken First we have devised a way of operating on 5tuples as single algebraic objects de ning addition subtraction multiplication and division This required nding some irreducible polynomial which works behind the scenes Once we have got this the steps are as follows 1 We compute the syndrome rHTi 2 From the syndrome we set up the error locator polynomiali If we let 5127i81 5227i382 we can write 2 SS 2 421 512 51 5 1 We note that there must be some relationship between the sums of the powers of roots and the coef cients 3 We then nd the roots of the polynomial which determine the error locationsi For binary codes knowing where the error is is suf cient to knowing now to correct it For nonbinary codes which are very commonly used there is another step knowing the error location we must also determine the error value This involves setting up another polynomial the error evaluation polynomial whose roots determine the error values The above steps establish the outline for the next several weeks Not only will we develop more fully the arithmetic but we will be able to generalize to whole families of codes capable of correcting many errors However the concepts are all quite similar to those demonstrated here It is historically interesting that it took roughly ten years of research to bridge the gap between Hamming and the code presented above Once this was accom plished other generalizations followed quicklyi ECE 7670 Lecture 8 7 Other cyclic codes Objective To examine some other common families of cyclic codes Reading 0 Chapter 6 In this chapter we will introduce some other cyclic codes which are of both historical and practical signi cance To get started we will need some more matrix and number theory background 1 Hadamard matrices Consider the following 1 l l H 7 H2 H2 7 l 7 l 4 H2 7H2 1 1 These are examples of Hadamard matrices which have the property that they are i1 matrices such that HnHE n1 Hadamard matrices exist of orders 12 4 or a multiple of 4 Hadamard matrices are of interest because we can de ne codes based on the rows of the Hadamard matrix There are two known ways of making Hadamard matrices One way is as follows H H H n n This is the Sylvester construction The second construction the Paley construc tion is somewhat more subtle We begin with a discussion of quadratic residues Suppose we wanted for some strange reason to know for which values of z the following quadratic equation has a solution y2 E 1 mod p where p is prime For example let p 5 Then we have 1221 2224 3224 4221 In this example only I l and z 4 have a solution to the quadratic equation Those values mod p that are perfect squares are called the quadratic residues modulo 11 Example 1 When p 7 we have 12 equivl 22 equiv4 32 equiv 42 equiv 52 equiv4 62 equivl EOE 7670 Lecture 8 7 Other cyclic codes 2 So the quadratic residues perfect squares mod 7 are 12 41 D We observe 11 We only need to check the rst half since 17 7 z2 E 12 mod p 21 There are p 7 12 quadratic residues mod p 31 RRRandRNNi De nition 1 We de ne the Legendre symbol xz in the context of a given prime p to 0 if z is a multiple of p xz 1 if z is a quadratic residue ofp 71 if z is not a quadratic residue of p Now de ne a p X p matrix Q with elements indexed starting from zero of an XJ39 7 i For example let p 51 Then the quadratic residues are 1 4 so we would have Q of the form 01771 10177 Q71017 77171 10010 Such a matrix is called a Jacobsthal matrixi Now we form without proof the matrix 1 1 Hn 1 1T Qn71 In71 For certain orders n this is a Hadamard matrix A Hadamard matrix is normalized if the left column is all equal to one 11 Codes over Hadamard matrices Take a Hadamard matrix H and convert 1 A 0 and 71 A 11 Call the resulting matrix Ani We can make codes three different ways 11 The rows of Hn are orthogonal so that the rows of An differ in n2 placesi These give us n code words of length n We may delete the left column without affecting the distance to obtain a length n 7 1 code with minimum distance nZi This code is known as the An code it is also called a simplex coder E0 Take An and complement each word The resulting code is called 3 and has 2n codewords of length n 7 1 and minimum distance n2 7 11 If n is not a power of two then the code is nonlinear our rst example this quarter Every code resulting from a Paleyconstructed matrix of order n gt 8 gives rise to a nonlinear code If we take a nonlinear code and adjoin all linear combinations of codewords we obtain a linear code This is the quadratic residue code we will talk about lateri Overhead EOE 7670 Lecture 8 7 Other cyclic codes 3 2 Quadratic residue codes We begin with a review Recall that cyclotomic cosets modulo n represent the exponents of conjugate elements in a eld such as WWW where B is some element in CFq with order n Also recall that the set of roots of a polynomial with coef cients in CFq must consist of the union of one or more sets of conjugacy classes with respect to GFqi ow let us consider the quadratic residues of p in light of conjugacy classes Let Q be the set of quadratic residues and let N be the set of quadratic nonresidues mod p The set of integers modulo p forms the eld GFp so this division into N and Q divides CFp into two sets CFp has a generator 7 so that successive powers of 7 generates the p 7 1 distinct elements of GFp 77727 H7 Yp711 o The generator 7 must lie in Ni Otherwise there is some element 6 E P such that 62 7 so that we could have 6 62 763 64 72 i H 6217724521772 1 which would have 2p 7 1 distinct elements in it which cannot happen 0 Observe that We 6 Q for an even number 6 and 70 E N for and odd number or 0 We can write the elements of Q as the rst 17 7 l2 consecutive powers of 72 Q is generated by 72 and hence forms a cyclic group under multiplication mo pi Let plsm7li Then GFsm has a primitive pth root of unity Let us add another restriction s is a quadratic residue mod p Now among the powers of 5 66263 75quot 17 are the exponents 12 l H p Of these integers some are in Q and some are in Ni But by are restriction s E Now consider the conjugates of B with respect to s GF 2 5755755 7m Since 8 E Q and Q forms a group we must also have SQEQ SSEQiHi Hence the exponents of B that form its conjugates are all in We conclude that Q is the union of one or more cyclotomic cosets modulo p with respect to GFs The bottom line is that a polynomial 41 H I 7 a1 ieQ must have its coef cients in GFsi Similarly we must have H z 7 ai iEN EOE 7670 Lecture 8 7 Other cyclic codes 4 is in GF3I and we can also write 117 71z 7 The quadratic residue codes Q N and W are generated by respectively 41 1 14I7n171 0711 QR codes have pretty good rates and pretty good distance properties d2 2 p 3 Golay codes Let us take p 23 and form the QR code The binary Golay 923 is the 23123 code thus formed Properties 1 Every codeword with even weight has weight divisible by 4 2 The rnin distance is 7 tripleerror correcting Wlt23gtlt2fgtlt23gtlt23gt21 It is said that this code was found by playing around with Pascalls triangle 3 Perfect code We can add an overall parity check bit to obtain the 24127 8 code Good decoding algorithms exist for the binary Golay codes we will not go into them ECE 7670 Lecture 4 Polynomials over Galois elds Objective To become acquainted with some basic algebraic concepts of polyno mials 1 The Euclidean algorithm The Euclidean algorithm is perhaps the oldest algorithm in the world being at tributed to Euclid and appearing in his Elements It applies on any Euclidean domain De nition 1 A Euclidean domain is a set D with operations and satisfying 1 D forms an additive commutative ring with identity 2 Multiplicative cancelation if ab be and I f 0 then a c 3 Every a E D has a metric 9a such that a 9a S gab for b E D I f 0 b For all a b E D with 9a gt 91 there is a q quotient and T remainder such that a 412 T with gT lt 91 or T 0 This is for integers the division algorithm D lntegers and polynomials form a Euclidean domain where the metric for integers is simply the absolute value and for polynomials it is the degree of the polynomial Before we get to Euclid7s algorithm we need one more fact about GCDs For any integer 1 ab b a a 7b ab ax Euclid7s algorithm nds the greatest common divisor of a pair elements in a Euclidean domain The Euclidean algorithm works by repeated division Example 1 Let a 168 and b 166 and nd 168166 We have 168 11662 Divide again 166 2 83 0 Take the last nonzero remainder 168166 2 D Example 2 Find 33654 Divide 336 54 6 12 54 12 4 6 12 6 2 0 Take the last nonzero remainder 33654 6 D This can be coded in nothing at all in MATLAB Algorithm 1 GCD program 1 EOE 7670 Lecture 4 7 Polynomials over Galois elds 2 function g gcdint1bc quot0 function g gcdint1bc quot0 Compute only the GCD ab using the Euclidean algorithm whi1ec g c c rembc b g end We can do more however It is a fact of number theory that a7 5 ax by for some integers z and y We can use the Euclidean algorithm to determine 1 and y In many of our applications these will be the numbers that we need Another useful fact if there is an I and y such that or by 1 then ab 11 Example 3 Determine 8519661 By the division algorithm we can write 966 1 8511151 By the property stated above we have 966851 851966 71851 8511151 Thus the GCD problem has been reduced Applying the division algorithm again we can write 851 711546 hence 851115 115 851 7 7 115 11546 Proceeding by application of the division algorithm and the property we obtain successively 115 2 46 23 11546 4623 46 23 46 23 231 Chaining together the equalities we obtain 966851 231 We can find the z and y in the representation 966 851 9661 851y by working the equations backwards 231157246 11572851771157285115115 72851159667185115966717851 soz15andy7171 More formally the algorithm may be stated in the following theorem which also fixes some useful notationi EOE 7670 Lecture 4 7 Polynomials over Galois elds 3 Theorem 1 The Euclidean algorithm Let b and c be integers gt 0 Then by repeated application of the division algorithm write beqlr1 0ltr1lte c rlqgr2 0ltr2ltr1 T1 T243T3 0ltT3ltT2 7772 rjilqj rj 0 lt rj lt rjil T171 WIHI 0 Then lye rj the last nonzero remainder of the division process That the theorem stops after a nite number of steps follows since every remainder must be less than the preceding remainderi If the GCD g and the coef cients 1 and y are desired such that bi Cy 97 a little more work is required Observe that the recursion in the Euclidean algorithm may be expressed as 4139 lTi3972Ti3971l Ti T122 Tiilqi 1 for i 1727 H until termination with ril b and r0 cl The values for z and y may be obtained by nding intermediate integers 11 and yi satisfying 111139 0 M In conjunction with 1 we obtain Ii Ii72 7 qixiil 2 9i 7 M72 Qini39il for i 127 l i i until termination with 11 1 IO 0 971 0 yo 1 This algorithm applies as well to polynomials over a eld as to integers The following implementation is for polynomials Algorithm 2 GCD program 2 7 polynominals function gst gcdpolybcthresh quot0 function gst gcdpolybc quot0 Compute the GCD g bc using the Euclidean algorithm quot0 and return st such that bsct g where b and c are polynomials quot0 with real coefficients quot0 thresh optional threhold argument used to truncate small remainders rm2 b rm1 c sm2 1 sm1 tm2 O tm1 1 whileanyrm1 EOE 7670 Lecture 4 7 Polynomials over Galois elds qtr polydivrm2rm1 ifnargi 3 trfindabstr lt thresh 0 end quot0 truncate small ts polysubsm2polymu1tqsm1 tt polysubtm2polymu1tqtm1 rm2 rml sm2 sml tm2 tml rml tr sml ts tml tt end 1c rm21 quot0 make monic g rm21c s sm21c t tm21c As an example7 we can try gtgt gxy gcdpoly4 10 8 28 14 7 1 10000 15000 05000 03333 01667 2 Minimal polynomials and conjugate elements We begin with a reminder from polynomials over real Suppose we are given a number 11 23ji Over the extension eld C there is a polynomial 1724r3j which has 11 as a root But suppose we are asked to nd the polynomial of smallest degree with real coef cients that has 11 as a root We are well acquainted with the fact that the roots of real polynomials come in complex conjugate pairs7 so we conclude immediately that there a real polynomial with root 11 must also have a root 12 2 7 Sji We say that 12 is a conjugate root to 11 A polynomial of smallest degree having these roots is z 7 2 3jr 7 2 7 3m 7 12 7 41 13 We will apply the ideas of conjugate roots and polynomials having speci ed roots with coef cients in a given eld now to nite elds De nition 2 Let a E GFqmi The minimal polynomial of a with respect to GFq is the smallestdegree nonzero polynomial 101 6 GFqz such that pa 0 D ln our previous example7 the polynomial we found would be a minimal polyno mial for 2 Sji Some properties for minimal polynomials Theorem 2 For each a E GFqm there exists a unique monic polynomial 101 of minimal degree in GFqz such that 1 pa 0 2 The degree of 101 S m 5 fa 0 means that 4 101 is irreducible in GFq EOE 7670 Lecture 4 7 Polynomials over Galois elds 5 Proof Write down the m 1 elements laa2iu am which are elements of GFqmi Since GFqm is a vector space of dimension m over GFq these m 1 elements must be linearly dependenti Hence there exist coef cients such that aoa1aamam 0 these are the coef cients of the polynomial 101 which has a as the root To show uniqueness suppose there are two minimal monic polynomials of a call them and These must both have the same degree Then there must be a polynomial Tz such that 1 91 N1 where deg39rz lt degfzi Since a is a root we get 0 fa 9a T01 so that Ta 0 which contradicts the minimality de nition If there is an siti fa 0 we write using the division algorithm 1 PI4T N1 where deg39r lt degpi But then Ma 0 again a contradiction of the minimalityi lf 101 factors so p fg then either fa 0 or 9a 0 again a contradiction to the minimalityi D We observe that primitive polynomials are the minimal polynomials for primitive elements in a GE De nition 3 Let B E GFqmr The conjugates of B with respect to a sub eld GFltqgt are WWW H i a The conjugates of B with respect to GFq form a set called the conjugacy class of wort GF qr Theorem 3 The conjugacy class Ufa E GFqm wmt GFq contains d elements w ere Proof The elements aaqaq2 l H has only a nite number of elements in it The rst number to repeat must be at Otherwise there is a number s such that aqd 1 15 for some 8 lt d This means that aqd qs ll But by a previous result we must have 0rdalqd 7 45 454 1 5 71 Recall that ordalqm 7 ll Since L15 is a power of prime no factors in common with 4 14 7 l we must have ordalqd 5 7 l c175 so that aq at D Example 4 EOE 7670 Lecture 4 7 Polynomials over Galois elds 6 1 ln GFQS the conjugacy classes of a are m2 of a4 a a B as7 a32 as7 as Q12 15 Note that each conjugacy class has the same number of elements in it and that the number of elements divides m E0 Let a E GF16 be an element such that orda 3 Check for consistency since 3 15 there are 2 elements of order 3 in GF16 The conjugacy class of a is So there are 2 elements in this conjugacy class Theorem 4 Let a E GFqm and let 101 be the minimal polynomial of a The roots of 101 are exactly the conjugates ofa wmt GFq In other words the minimal polynomial does just what we want it to and the conjugates of a can be interpreted as we expect Before proving this we make the following observation a102quot39atpT01T02Tquot390 T for 7 123 In other words we don7t need to worry about the cross terms Prove using two terms recall that pl Also use a 6 ltlta Wquot av 617 at 5172 Proof If pa 0 then using the observation just made 0 Maw 10aq so 1 1 is a root of Similarly 0 PWWT May The remaining step is to show that the polynomial with the conjugates of a as its roots has its coef cients in CF01 Let be this polynomial 16041 I 7 az 7 01 I 7 aqdil Id 14017110171 A11 140 Then Maw W Agilzqw ll AM Aquot 1314 Start in product form rearrange using uniqueness We therefore get A A for i 01 d 7 1 Since every coef cient satisfies this every coef cient is in GFq see thm 216 B EOE 7670 Lecture 4 7 Polynomials over Galois elds 7 Lemma 5 All the roots of an irreducible polynomial have the same order Proof Let 101 6 GFqzi By a previous result the orders of the roots divide gm 7 ll Since the coef cients of 101 are in GFq the roots must be conjugates and are of the form 6545 12 i i i We must have 4 p for some ui Thus 4 and its powers are relatively prime to gm 7 l and all divisors of gm 7 ll We note that k ord ord 1 ord i 8 l 412 crew 8 Since this is true for any 16 root has the same order D Example 5 Using the conjugacy classes we found before in GF8 we can write down the minimal polynomials 0 I 1 1 aa2a4 17az7a2z7a4 zgzl a3a5a5 zgz2li 3 Factoring x 1 Recall that every element 6 E GFqm has an order that divides gm 7 1 thus every element is a root of zqm l 7 ll Put another way the elements of GFqm are the gm 7 lst roots of unity and these are all the nonzero elements of the eld Given a eld we divide it into conjugacy classes taking the minimal polynomial from each Then based on our observation we must have zqm l as a product of the minimal polynomials of the nonzero elements Example 6 I771zlzszlzsz2li D We can now pursue a more general problem roots of I 7 l for other values of in These n roots of unity must exist in some eld We nd the eld then nd the minimal polynomials of the conjugacy classes in the eld Suppose we have an element 6 of order n in some eld GFpmi Then 6 is a root of I 7 l in that eld and so are the elements 5253 i H n li We can nd such a B if we form the eld correctlyi Before doing so it is interesting to pause a moment and suggest an application of this Consider the DFT N71 V Xk Z unja mN n0 Note that the number e jQWN is an Nth root of unity We can de ne a Fourier transform in a nite eld GFpm of length N provided that we can nd a eld in which Nth roots of unity existi Recall that if nlpm 7 1 then there are elements of order n in CFpmi De nition 4 The smallest positive integer m such that nlqm 7 l is called the order of q modulo n D EOE 7670 Lecture 4 7 Polynomials over Galois elds 8 If m is the order of q modulo 717 then GFqm is the smallest extension eld of CFq in which nth roots of unity existi Example 7 We are looking for an extension of CFO in which 5th roots of unity exist 5m 71 5m 71 5mg 71 5124 71 15 So in GF16 there are primitive fth roots of unity 1n GF167 let a be primitive it has order 151 Then 6 a3 has order 57 as needed The conjugacy class for B is We want 13th roots of unity in an extension of GF31 Note that 13133 7 1 so they live in GF331 D Example 8 We want to nd a eld GFQM which has 25th roots of unity We nee 25127 7 1 For m 20 this works Now let us divide the roots of 225 71 into conjugacy classes Let B be a primitive 25th root of unity 1 2481671436122423211791811221913 575 75 75 75 75 75 75 75 5 75 75 75 75 75 75 75 75 75 751 5 10 20 15 5 75 75 75 So 125 i 1 10114 11020 where the subscript represents the degree D Example 9 Let us nd a eld GF7m in which 115 7 1 has roots We need to nd m such that 1517 71 m 4 works Let 7 be a primitive 15th root of unity in GF741 The conjugacy classes with respect to CF4 of the roots of unity are 1 Thus 115 7 1 factors into six irreducible polynomials in GF71 If we list the exponents of the primitive roots of unity7 we get what are called the cylotomz39c cosetsi For example7 for the last example we have the following Conjugacy class Cyclotomic cosets lt 0 771 7 13 lt7 17774713 rmwgwu lt7 27148711 737157712719 lt7 37671279 75 lt 5 710 lt 10 EOE 7670 Lecture 4 7 Polynomials over Galois elds 9 The cyclotomic cosets modulo n with respect to GFq contain the exponents of the n distinct powers of a primitive nth root of unity with respect to GFq each coset corresponding to a conjugacy class These cosets provide a shorthand representation for the conjugacy class 4 Ideals in GFq 1 Review we have seen that we can de ne a ring by operations on integers modulo an integer eigi ltZ5 If the modulo number m is prime we get a eld We can also do operations on polynomials modulo another polynomial For example the ring of polynomials GFqz can be reduced modulo another polynomial Notationally we write lf is irreducible then GFq is a eld these are the Galois elds we have already seen When is reducible then is a ring A particular ring that will be of some importance to us is the ring GFlt4gtlIlIn 1 Example 10 Consider CF2zI3 l The original ring contains all polynomials with coef cients in CFO When reduced modulo 13 1 they divide into equivalence classes 0zs lz4zz5 1215 lHi lzgz4zl15zx lzf ui 1zgz114z5zxz15lzui 12zsz2lz4z2zz51512li I 1 171 1 z 1 1 17m 2 1 3 2 4 x 1 5 1 5 2 12z1312zlz412z5115z2zui 12zlzg12zz412lz5zl1512zui There are thus 8 equivalence classes which we can label by the smallestdegree element of each class eg the rst element listed above D We will denote Rn GF2zzn 1 We now introduce a new algebraic concepti De nition 5 Let R be a ring A nonempty subset l C R is an ideal if it satis es the following ll 1 forms a group under addition 2 For any a E l and any 7 E R or E It In other words elements outside the ideal fall back into the ideal under the multiplicative operationi D Example 11 For any ring R there are at least the two trivial ideals 0 and Rt The set I 0 I4 13 12 z 1 forms an ideal in R5i For example take the element 14 z l E R5i Then 14zlz4zg12zl 18z715z4l EO modz4zs12zl El D EOE 7670 Lecture 4 7 Polynomials over Galois elds 10 De nition 6 An ideal I in a ring R is said to be principal if there is a 9 E I such that every element 5 E I can be expressed as the product m9 for some in 6 Bi The element 9 is said to be the generator element for the principle ideal and the ideal generated by 9 is denoted D Here s the lowdown for the rest of the course the codes we will be studying are ideals in a ring Since ideals will be so important to us let us examine some properties of idealsi Theorem 6 Let I be an ideal in GFq 7 1 Then 1 There is a unique monic polynomial 91 6 I of minimal degree 2 I is principal with generator 91 3 yltzgtlltzn 71gt in 0mm The latter fact accounts for our interest earlier in factors of1 7 1 Proof The ideal is not empty since the entire ring is an ideal and there is a lower bound on the degrees of polynomials Hence there must be at least one polynomial in the ring of minimal degree which may be normalized to be monici Now to show uniqueness let 91 and be monic polynomials in I of minimal degree with f f 9 Then h1 91 7 must be in I since I forms a group under addition and h1 must be of lower degree contradicting the minimality of the degree of 9 and i To show that I is principal we assume to the contrary that there is an E I that is not a multiple of Then by the division algorithm 1 mryr rr with degr lt deg9i But E I de nition of a ideal and r f 77219 E I de nition of ideal contradicting the minimality of the degree of 9 unless r 0 To show that 7 1 we assume to the contrary that 91 7 1 By the division algorithm as 71 7 hltzgtgltzgt was with 0 S degr lt deg9i But h191 E I and r1 1 7 l 7 h191 is the additive inverse of r1 E I and so is in I contradicting the minimality of the degree of 9 B When we deal with codes we will pick a code length n then nd a generator 9 dividing 1 1 which will be our generator polynomiali All of our codewords will be multiples of91i ECE 7670 Lecture 1 7 Introduction Objective To introduce fundamental concepts in digital communications and motivate the need for error correction Also to introduce a simple error correction co e Introduction Digital communication is becoming increasingly important in the new communica tions infrastructures that are being developed It is interesting to note some of the advantages that digital offers over conventional analog communications 1 Channel coding theorem reliability 2 Flexibility encryption interleaving etc 3 Compression 4 Spectral shaping 5 Performance assessment There is substantially more to digital communication than simply connecting two digital chips togetherl Bits are an abstract concept and bits must be represented by voltages Every signal must ultimately be a continuoustime waveform and we want to design our system so that the waveform ts well with the channel A l t 4 digit 39 39 ramework is as follows 44 o The source is the source of digital data 0 The source encoder serves the purpose of removing as much redundancy as possible from the data This is the data compression portion 0 The channel coder puts a modest amount of redundancy back in order to do error detection or correction o The channel is what the data passes through possibly becoming corrupted along the way There are a variety of channels of interest including 7 The magnetic recording channel 7 The telephone channel 7 Other bandlimited channels 7 The multiuser channel 7 Deepspace channels 7 Fading and or jamming and or interference channels 7 The genetic representation channel 7 Any place where there is the possibility of corruption in the data 0 The channel decoder performs error correction or detection EOE 7670 Lecture 1 7 Introduction 2 o The source decoder undoes what is necessary to get the data back There are also other possible blocks that could be inserted into this model 0 There is always the need to perform some kind of synchronization on carrier on symbols on frames etc o A block to enforce channelconstraints Some channels eg the magnetic recording channel have constraints on how long a run of zeros or ones can be The constraints are enforced in what is often known as a line coder 0 A block to perform encryptiondecryption o A block to perform lossy compression In this class we focus on the channel encoder and the channel decoder The goal is to obtain coders which are effective correct lots of errors with a reasonable complexity The motivation for this area of study comes from Shannon7s channel coding theorem which states roughly every channel has a capacity C bitssec such that whenever the transmission rate R is less than C the probability of error can be made arbitrarily small However the proof does not explain how to construct the codes For transmission over a channel with bandwidth W with Gaussian noise at a SNR of EsNo the capacity is Es C Wlogg l 7 b1tssecond No Shannon7s theorem was a major step forward Prior to Shannon it was believed that either in nite power or in nitesimal rate would be required for arbitrarily reliable performance Example 1 An example of code performance BPSK Pb Q 2EbNo lmprovement repetition code or increase EbNo D Shannon7s theorem sparked a great deal of research into nding codes 1 1950 Hamming codes singleerror correcting 2 195971960 BCH and ReedSolomon codes 3 Late 507s convolutional codes It took 10 years to bridge the gap This is nontrivial stuff Some motivation Why is coding used It can provide the difference between an operating communi cations system and a disfunctional systeml Every modern digital communications link including magnetic storage cellular phones the internet employs some kind of error control Networks usually do not have forward error correction In some instances the gains are signi cant DSN When viewed from a purely economic standpoint the impact can be impressive It was estimated in the late 19607s that each dB of coding gain was worth 1000000 in development and launch costs The current value for the Deep Space network is 80000000 per dB of gain In the Galileo mission coding may have made the difference between success and failure in a billion dollar effort77 Heegard and Wicker p 5 ECE 7670 Lecture 1 7 Introduction 3 A little bit of digital communications For most of the semester we will assume binary digital communications using BPSKi This is modeled from a bit point of view using the BSCi From a sig nal point of view we send a normalized signal with either an amplitude m or 7E where E5 is the energybit in Joulesbit The performance of BPSK is determined by Pb 0 Q 2EbNo Show slider Let us suppose that we are sending Rs bitssecondi Then the power en ergytime is equal to P RsEb Wattsi Now what if we increase the rate of transmission send more bits per second while retaining the same transmission power Suppose that we have a quantity R the code rate such that R lt 1 If we need to send RsR bits second a higher rate Then xing the power will require a new energy level E2 satisfying P RsRE2 RSEI so that E2 REbi That is we have less energy per bit because the bits are coming fasteri ow what does this have to do with error correction Suppose that we have a desired bit throughput rate of Rs bitssecond and a xed level of power P Error correction introduces redundancy We might get for example 15 bits of coded information for every 11 bits inputi We say this is a rate 15 code To keep the original date throughput the same we must send the coded bits at a rate 1511 faster This means that the energybit that can be expended on the coded information is 1115 of the energybit that can be expended on the uncoded information we are losing ground Suppose we have a system where EbNO 10 dB For BPSK this corresponds to a BER of 3 9 X 104quot When a 1511 code is used the SNR is 865 dB a drop of 1010g101115 7134 dB But the 1511 is able to correct a single error in every blocki It can be shown that the output of the decoder has a BER of 5 6 X 10 3 better than it was before it was coded To achieve this BER without coding the transmitter would have had to produce an EbNo of 115 dB The difference between this value and the value actually sent is the coding gaini Show slider Distance between codewords Error correction is obtained by adding redundant symbols to a codeword If we send k symbols into the coder we get n out The rate of a code is R kni It is always the case for error correction that R lt 1 Example 2 Binary repetition code We can represent codewords as points in some geometrical space The distance measure that we use is the Hamming distance If x an y are codewords then the Hamming distance is dxy number of places that x and y differ EOE 7670 Lecture 1 7 Introduction 4 We also de ne the weight of a vector x as the number of elements of x which are nonzeror That is wx dx 0 De nition 1 Let Ccii0lxrMil be a code The minimum distance of the code is the Hamming distance between pairs of codewords of smallest distance d min dccvr a c cg 39 17 J D For a code with k input symbols and n output symbols and minimum distance d we may write that this is a n kd co er Think of each codeword as being a point in n dimensional spacer Draw picture Suppose that Co is sent and r is received and that dc0 r ll If the distance to all other codewords is larger than 1 we may guess that Co is the transmitted code The design goal for error correction coding essentially is how to choose 2k points out of a space of 2 points n gt k to maximize the distance between all pairs of codewords Suppose that t errors occur between transmission and reception lf d22t1 then the closest codeword is correct Thus we can correct up to t errors We can also check if an error has occurred We have both correction capability and detection capability The coding design problem in a nutshell is to place points in an n dimensional space to maximize the distance Example 3 Parity check codes 00 H000 01 A 011 10 A 101 11 A 110 What is dquot How many errors can we correct How many errors can we detect D Classes of codes Picture We will focus throughout the semester on linear codes We will rst work through a code known as the Hamming code to introduce some of the ideas The intent here is to introduce the concepts we will return to these ideas later to clarify some of the details Linear codes begin with a generator matrix Gr Let m be an input vector of k symbols Then the codeword is computed by c mGr For example 1 0 0 0 l 0 l G 7 0 l 0 0 l l l 0 0 l 0 l l 0 0 0 0 l 0 l l EOE 7670 Lecture 1 7 Introduction 5 If m m07m17m27m3 170070 then c1000 1000101 HOOD 0 1 1 1 HOHH 1 1 1 0 OHOO 0 1 0 0 OOOH Note that in this case the input word appears explicitly in the output coder Such a code is called a systematic code The other bits are called parity bits The use of matrices to describe these codes motivates a close examination of linear algebra or each linear code there is also a parity Check matrix H with the following property An ntuple C is a codeword if and only if it is orthogonal to every row vector 0 CHT 0 42gt C is a codeword Explain orthogonal to every row vector Now we observe that the rows of G are possible codewordsi why Then we have GHT 0 Let us use this property about the parity check matrix Suppose we send C7 and an error occurs rce mG e At the receiver7 we do not know e If we multiply r by HT we obtain the syndrome s rHT mGeHT mGHTJreHT eHTr Thus the syndrome does not depend upon the transmitted codewordl Now7 given the syndrome we want to determine our best guess of the error e Let us look at the syndrome for the code above We have 1 1 1 0 1 0 0 H 0 1 1 1 0 1 0 1 1 0 1 0 0 1 The syndrome is given by 1 0 1 1 1 1 1 1 0 SI HTT17T27T3PHT7 0 1 1 1 0 0 0 1 0 0 0 1 7 11017 21117 31107 7001 The syndrome is the sum of the columns of H sidewaysi Now suppose m 170070 Then c 1000101 Suppose that r 171707071707 1l EOE 7670 Lecture 1 7 Introduction 6 Note the error The syndrome is s rHT 111 This is the second column of H1 Hence7 since the syndrome is not zero7 we conclude that an error occurred in the second position of r Note that this code cannot correct more than one error if there were two errors7 say at 7 2 and T4 then the syndrome is the sum of the syndromes7 which gives us just another column of H1 Extension of this idea to be able to correct more than one error leads us to a careful examination of the way we do arithmetici We will take the mathematical properties we are familiar with and use them to create other structures that have suf cient power to do what we nee 1 ECE 7670 Lecture 2 4 Linear block codes Objective To deepen understanding of the concepts of linear block codes previ ously introduced 1 Introduction to linear block codes Recall the example from the last time of a code we had some generator matrix some parity check matrix and a means of doing some decoding We will generalize these ideas A block code is a code in which Is bits or more generally symbols are input and n bits or more generally symbols are output We designate the code as an n h code We will start with bits elements from the eld CFO later we will consider elements from a eld GFq after we know what this means If we input h bits then there are 2k distinct messages or more generally qk Each message of n symbols associated with a with each input block is called a codeword We could in general simply have a lookup table with h inputs and n outputs However as h gets large this quickly becomes infeasible Try h 255 for example We therefore restrict our attention to linear codes De nition 1 A block code C of length n with 2k codewords is called a linear n h code if and only if its 2k code words form a hdimensional subspace of the vector space of all ntuples over the eld CFO More generally with a bigger eld a block code C of length n with qk is called a linear n h code if and only if its qk code words form a hdimensional subspace of the vector space of all ntuples over the eld CF01 D We remind ourselves of what a vector space is we have an addition de ned that is commutative and closed we have scalar multiplication that is closed distributive and associative We will formalize these properties a little further but this suf ces for the present purposes We will see later that we have a group structure on the addition operation So what does this mean for codewords the sum of any two codewords is a codeword Being a linear vector space there is some basis and all codewords can be obtained as linear combinations of the basis We can designate g0 g1 gk71 as the basis vectors In a nutshell it means that we can represent the coding operation as matrix multiplication as we have already seen We can formulate a generator matrix as g0 g1 G gkil G is a k X n matrix If m m0m1 mk1 is an input sequence then the output is the codeword mG mogo mlgl 39 39 mkilgkir We observe that the allzero sequence must be a codeword Therefore the minimum distance of the code C is the codeword of smallest weight Comment on circuits to implement encoding EOE 7670 Lecture 2 7 Linear block codes 2 We have a vector space of dimension k embedded in a vector space of dimension n the set of all ntuplesi Associated with every linear block code generator G is a matrix H called the parity check matrix whose rows span the nullspace of G1 Then if C is a codeword then CH T 0 That is a codeword is orthogonal to each row of Hi From this we observe that GHT 0 There is also associated with each code a dual code that has H as its generator matrix The dual code is denoted as Cir If G is the generator for an n 16 code then H is the generator for an n n 7 16 code Example 1 A 7 4 Hamming code can be generated by G HOHH 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 The 16 codewords are 0000000 0001111 0010110 0011001 0100101 0101010 0110011 0111100 1000011 1001100 1010101 1011010 1100110 1101001 1110000 1111111 The parity check matrix is H 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 When regarded as a generator of an 73 code the codewords of this code the dual code has the codewords 0000000 1101001 1011010 0110011 0111100 1010101 1100110 0001111 EOE 7670 Lecture 2 7 Linear block codes 3 It may be veri ed that every codeword in C is orthogonal to every codeword in L When we want to do the encoding it is often convenient to have the original data explicitly evident in the codeword Coding of this sort is called systematic encodingi For the codes that we are to talk about it will always be possible to determine a generator matrix in such a way the encoding is systematic simply perform row reductions and column reordering on C until an identity matrix is revealed We can thus write G as G PlIkl where 1k is the k X k identity matrix and P is k X n 7 hi t Then C mG mPlIk c0 c1 enk1lm0 m1 i H mk When G is systematic it is easy to determine the parity check matrix Hi It is simply H 144 7 y Note in CF2 binary operations the negative of a number is simply the number We could write for binary codes H 146 PT The parity check matrix whether systematic or not can be used to get some useful information about the coder Theorem 1 Let a linear block code C have a parity check matrix H The minimum distance of C is equal to the smallest positive number of columns of H which are linearly dependent This concept should be distinguished from that of rank which is the largest number of columns of H which are linearly independent Proof Let the columns of H be designated as d0 11 i i i dn71i Then since CHT 0 for any codeword C we have 0 Code Cidi 39 39 39 Ga71dn71 Let C be the codeword of smallest weight w wC dmini Then the columns of H corresponding to the elements of C are linearly dependenti D Based on this we can determine a bound on the distance of a code dmin S n 7 h 1 The Singleton bound This follows since H has n 7 k linearly independent rows The row rank the column rank So any combination of n 7 k 1 columns of H must be linearly dependenti For a received vector r the syndrome is s rHTi Obviously for a codeword the syndrome is equal to zero We can determine if a received vector is a codeword Furthermore the syndrome is independent of the transmitted codewordi If r C e s ceHT eHTi EOE 7670 Lecture 2 7 Linear block codes 4 Furthermore if two error vectors e and e have the same syndrome then the error vectors must differ by a nonzero codewordi That is if eHT e HT then eie HT 0 which means they must be a codeword 2 Maximum likelihood detection Before talking about decoding we should introduce a probabilistic criterion for decoding and show that it is equivalent to nding the closest codewordi Given a received vector r the decision rule that minimizes the probability of error is to nd that codeword C which maximizes PC Ci r This is called the maximum a posteriori decision rule Proof that this minimizes probability of error is shown in the communications class We note by Bayes rule that P C P r C PM ltgt my PM where for example Pr is the probability of observing the vector ri Now since Pr is independent of C maximizing PC I is equivalent to maximizing PCP1 Ci If we now assume that each codeword is chosen with equal probability then maxi mizing PCPI C is equivalent to maximizing P rlCi A codeword which is selected on the basis of maximizing PI C is said to be selected according to the maximum likelihood criterioni We shall assume throughout the text a maximum likelihood criterioni Let us see what this means for us Pltrwcgt H We Assuming a BSC channel with crossover probability p we have 17 p ifci Ti PltTil6i p ifc 7quot Then Pltrwcgt H Pole lt1 7 pgtz01gtpltmegt i1 dcr 1 pnpz01ppz01 17pn lt15 Then if we want to maximize PI C we should choose that C which is Closest to r since 0 S pl 7 17 S ll Thus under our assumptions the ML criterion is the minimum distance criterioni In every case we should choose the error vector of lowest weighti EOE 7670 Lecture 2 7 Linear block codes 5 3 The standard array and syndrome table decod ing Suppose we send C and we receive r C e Assuming that error sequences with lower weight are more probable than error sequences with higher weight the maximum likelihood criterion7 we want to de termine our decoded word C such that the error sequence 3 satisfying r C e has minimum weight One way to do this is to create a standard army We form it the following way 1 Write down a list of all possible codewords in a row7 with the allzero codeword rsti E0 From the remaining n tuples which have not already been used in the standard array7 select one of smallest weighti Write this down as the coset leader under the allzero codewordi On this row7 add the coset leader to each codeword at the top of the column 3 Repeat step 2 until all the n tuples have been listed An example standard array for a 77 3 code is shown here7 where 1000111 G0101011 0011101 We make the following observations EOE 7670 Lecture 2 7 Linear block codes 6 H i There are 2k codewords columns and 2 possible vectors so there are 2n k rows in the standard array E0 The sum of any two vectors in the same row of the standard array is a code vector 3 No two vectors in the same row of a standard array are identical Because otherwise we have eici eicj withiy j which means Ci Cj which is impossible 4 Every vector appears exactly once in the standard array We know every vector must appear at least once by the construction If a vector appears in both the lth row and the mth row we must have ez Ci emCj for some i and j Let us take 1 lt mi We have em el l ci Cj el l ck for some kl This means that em is on the lth row of the array which is a contradiction Each row of the standard array is called a coset we will encounter the term coset in a more formal setting soon To decode with the standard array we locate the received vector r in the stan dard array Then the error sequence is the coset leader the best guess of the transmitted word is the codeword at the top of the column For example if r 0011011 then C 00111011 Since we designed the standard array with the smallest error patterns as coset leaders this is the ML decision As 0 served before there are 2n k coset leadersi These are called the correctable error patterns Fact an n 16 code is capable of correcting 2n k error patterns The standard array can be used to decode linear codes but suffers from a major problem the memory requirements quickly become excessive We want to look for easier approaches A rst step which doesn7t go far enough is to use the syndrome in the decoding Based on the properties of the syndrome above all elements in a row of the standard array have the same syndrome We therefore only need to store syndromes and their associated error patterns For the code whose standard array was given before we have 0 1 1 0 1 1 1 1 OOOH OOHO OHOO HOOD 1 1 0 1 EOE 7670 Lecture 2 7 Linear block codes 7 Steps to decoding 1 Compute the syndrome s rHTi 2 Look up the error pattern e using s1 3 Thenc rei Example 2 We provide another example of the standard array because it raises some interesting issues For the 5 2 code With the standard array is i This code is capable of correcting all errors of one bit In addition there are two other errors of two bits that can be corrected Note that the minimum distance of this code is 3 The parity check matrix is 111 H100 110 OHO HOD EOE 7670 Lecture 2 7 Linear block codes 8 The standard array using syndromes is 4 Hamming codes Hamming codes are the earliest and simples example of linear block codes The parameters are as follows for m 2 2 code length n 2m 7 1 Number of information symbols k 2m 7 m 7 1 Number of parity symbols n 7 k m Error correcting capability 1 Examples are 3 l 74 1511 and 3126 codes The parity check matrix of a Hamming code consists of all nonzero binary m tuples The columns may be ordered to correspond to a systematic code Syndrome decoding of Hamming codes using the standard array is straightforward the syn drome indicates which column of H corresponds to the error position 5 Weight distributions and performance of linear codes We pause in our development of decoding algorithms to address the question of how well linear codes can perform We recall that we can correct up to t errors if d 2t 1 We can also detect up to d 7 1 errors It may be possible to detect some errors up to d but it cannot detect all of them because there is at least one codeword with weight d We say that the random error detecting capability of a code is dquot However it may be possible to detect a large number of error patterns with weight 2 dquot Consider the following there are 2 possible vectors of which 2k are codewords There are thus 2 72k error patterns which are distinct from codewords It is possible that an error sequence is exactly equal to a codeword in which case the error is undetectable There are 2 7 l undetectable error patterns the all zero error does not matter The 2 7 2k patterns which are detectable are called detectable error patterns In many codes 2k 7 l is much smaller than 2 so that only a small fraction of the error patterns are undetectab e In carefully characterizing the performance of codes the weight distribution of the code is important Consider the codewords of a linear n 16 code C One of the codewords has weight 0 There may be codewords with weight 1 weight 2 and so forth Let Ai be the number of code vectors of weight i The numbers 0 A1 An are called the weight distribution of C Example 3 For the 74 Hamming code presented above 1401 1410 1420 1437 1447 1471 EOE 7670 Lecture 2 7 Linear block codes 9 If we want to use a code for error detection we can determine the probability of an undetected error using the weight distribution The probability of an undetected error is the probability that an error pattern is equal to a nonzero code vector n RAE 271139le 7 FY i1 where p is the crossover probabilityl For the Hamming example RAE 7 710317 M 710417 m3 p77 lfp 01 then PuE m 7 X lO F l e saw in example 2 that it may be possible to correct more than the minimum number of errors in some cases The number i W 712l is called the Tandomerror correctz39ng capability of the coder Based upon this number the probability of erroneous decoding is upper bounded by n n P z 7 net E s I lt1 p zt1 Example 4 For the 74 Hamming code PE S 211020 7 M5 351030 7 m4 351040 7 m3 211050 7 P2 710517 0 107 When p 001 we get PE S 00020 D In most cases we can correct many error patterns of more than t errorsl There are a total of 2n k correctable error patterns the number of rows in the standard arrayl When we know the weight distribution we can get a more precise statement of the probability of error We make a decoding error if and only if the error pattern is not a coset leaderl Let Ozi be the number of coset leaders of weight ii The numbers a0a1 l H an are called the weight distribution of the coset leadersl Using these numbers PltEgt 17 Zaipi 7 W72 i0 Example 5 For the 73 code presented above Then PE 717 17 10V 7 71017 m5 7 710217 m5 7 10317 p lfp 001 then PE 1 4 X 10 D There is an interesting relationship between the weight distribution of a code and a dual coder Let A0 A1 7 l 7 An be the weight distribution of a code C and let B0 B1 H Bn be the weight distribution of the dual code Oil Also let 142 A0 A12 Anznl EOE 7670 Lecture 2 7 Linear block codes 10 This polynomial is called the weight enumerate for C Think of the Z transform of a nite seriesi Let Bz B0B12 anni The following identity is known as the Mac Williams identity Ac 27ltHgt1 2m it The MacWilliams identity can be used to compute the probability of an undetected error from a linear code from the weight distribution of its dual It can be shown that RAE 27ltHgtBlt17 2pgt7lt17 p 6 Modi cations to linear codes We introduce some minor modi cations to linear codesi De nition 2 A code is punctured by deleting one of its parity symbolsi An n 16 code becomes an n 7 l k co e D De nition 3 A code is shortened by deleting a message symboli An n 16 code becomes an n k 71 code D De nition 4 A code is expurgated by deleting some of its codewords while still maintaining the linear code propertiesi D De nition 5 A code is extended by adding an additional redundant coordinate producing an n l 16 code D 7 Bounds on linear block codes Thinking geometrically around each code point is a cloud of points corresponding to noncodewordsi These form a sphere around each of the code vectors The Hamming sphere is the sphere of radius t that contains vectors a distance S t from a codeword The number of vectors in the Hamming sphere is denoted Vqn t where q 2 for binary codesi We can see that Van lt47 1 From a decoding point of view if a received vector r falls inside the Hamming sphere of a codeword then that codeword is selecte i The redundancy of a code is essentially the number of parity symbols in a codeword More precisely we have Tn7long where M is the number of codewordsi For the codewords we have seen to this point 7 n 7 kl EOE 7670 Lecture 2 7 Linear block codes 11 Theorem 2 The Hamming Bound A terror correcting qary code must have redundancy r satisfying r 2 logq Vqnt Proof Each of M spheres in C has radius t The spheres do not overlap The total number of points enclosed by the spheres must be S q We must have MVqnt S q tinM 2 WWW from which the result follows E A code that satis es the Hamming bound with equality is said to be a perfect code In terms of the standard array it means that the random error correcting capability is the best it gets there are no leftover codewords Hamming codes are perfect codes Actually being perfect codes does not mean the codes are the best possible codes The set of perfect codes is actually quite limited since it can be shown that the number of codewords of a qary code must be M qk Possible perfect codes H The set of all ntuples with minimum distance 1 and t 0 to Oddlength binary repetition codes CA3 Hamming codes linear or other nonlinear codes with equivalent parameters he The Golay G23 code 01 The G11 and G23 codes related to quadratic residue codes An upper bound on the redundancy is the Gilbert bound Theorem 3 There exists a terror correcting qary code of length n and redundancy r that satis es r S logq Vqn 2t The proof is interesting because it demonstrates a power technique in coding the random code It also points out that the code need not be linear Proof There are q ntuples possible Begin by selecting one of these at random then delete from further consideration all vectors that are at Hamming distance less than or equal to 2t from the selected codeword Repeat selecting another codeword at random from those still available The selection of each code word results in the deletion of at most Vqn2t vectors from the set of 4 possible Continuing at least M code vectors may be selected where M lqnqu t 2 EOE 7670 Lecture 2 7 Linear block codes 12 Of considerable theoretical interest is how families of codes perform as their block length becomes longi Consider the ratio 5 dminn We would hope that as n gets longer dmin might grow correspondinglyi ln exploring this behavior let Aqndmin be the maximum possible number of codewords for a qary code of length n and minimum distance dmini Then the number of codewords is logq Aqndmin and the rate is logq Aq n dmin n We say that the asymptotic rate of the code is the limiting value of this 1 A d W5 11m sup W n7gtoo n We will now examine a bound on a6i De nition 6 Let the qary entropy function be de ned as Hqz zlogqq 7 l 7 zlong 7 17 I logql 7 z for0ltzltq7lqi D This function has the following property which we will not prove here see the boo Lemma 4 ForO g 6 S L17 14 logq V1101 l5nl hm n7gtoo n qu We now employ this in a bound EOE 7670 Lecture 2 7 Linear block codes 13 Theorem 5 Gilbert Varsharmov bound f0 S 6 S q 7 lq then a6 2 17 H1105 Proof The error correction capability is t W 12l7 so that Vqnv 2t S VA Will Then logq Aq n7 n a6 lim sup n7gtoo n 1 q gt hm lo Gilber bound gq Van MD hm 1 7 Iogq van l nl n7gtoo n 1 7 Hg 6 previous lemma We also can state a lower bound Theorem 6 McElz39ece RodemiChRumsey Welsh bound am 3 HA 7 W17 6 Plots of these bounds for binary codes are shown ECE 7670 Lecture 9 ReedMuller codes Objective To examine basic attributes of ReedMuller codes Reading 0 Chapter 7 This chapter gets us closest to the concepts of digital design for these digital codes that we will get We will be looking at functions of Boolean variables As we know we can represent these using truth tables We will m represent the number of inputs We will list the input variables with Um being the most signi cant bit Example 1 14 0000000011111111 13 0000111100001111 12 0011001100110011 11 0101010101010101 f1 H 0110100101101001 f2 lOlOlOlllOlOOlOO Without ambiguity we can represent the functions simply using the bit strings as f1 0110100101101001 f2 1010101110100100 D The set of Boolean functions of which there are 22m forms a vector space ng over CF We will interchange a functional and vector notation Here are some examples of important functions 1H 1 1111111111111111 v1 H v1 0101010101010101 v2 H v2 0011001100110011 v3 H vs 0000111100001111 v4 H v4 0000000011111111 mg H vva 0001000100010001 74712713714 H v1v2v3v4 0000000000000001 In the RM codes we will be interested in monomial Boolean functions of the sort in functional notation vlvgvg or 112114 or 01020304 We will let M denote the set of all monomial functions M lv1v2 vm 111112 H Um1vmv1v2vg H vlvg mm These functions are linearly independent as are their vector representations De nition 1 The binary ReedMuller code RT m of order 7 and length 7 consists of all linear combinations of vectors f associated with Boolean functions f that are monomials of degree S 7 in m variab es Example 2 The Rl3 code length 23 8 The monomials are 1111 v2 113 with associated vectors EOE 7670 Lecture 9 7 Reed Muller codes 2 1 11111111 v3 00001111 1 00110011 v1 01010101 These vectors can be considered as taken as the rows of a generator matrix1 This is an 844 code it is singleerror correcting and doubleerror detecting1 This is also the extended Hamming code obtained by adding an extra parity bit to the 74 Hamming code1 D Example 3 The R2 4 code The monomials up to degree 2 are 17 1117 U27 Us 1147 U102 U103 U104 1121137 1121147 113114 Corresponding are the following binary vectors 1 This is a 1611 code with min1 distance 41 D In general for an RT m code we have m m m k 1 1 lt1gtlt2gt 0 We can recursively construct an RT lm 1 code 7 twice the length 7 from an RT m and RT lm code1 Theorem 1 RT 1771 l fgf0r all f E RT lm andg E RTm1 Proof The codewords of RT lm l are associated with Boolean functions in ml variables of degree S Tl1 lfcv1 1 1 1 vm1 is such a function we can write Cv1111vm1fv1111vmv7mlgv1111vm1 Then f is a Boolean function in m variables of degree S Tl and g has degree S 7 so the corresponding vectors f and g are in RT lm and RT m respectively B Theorem 2 The minimum distance of RT m is 2quot Proof By induction When m l the R0l code is the length2 repetition code in this case dmin 21 The Rl 1 code has four codewords of length 2 hence dmin 1 As an inductive hypothesis assume that up to m and for 0 S 7 lt m the minimum distance is 2quot We will show that dmin for RTm l is 2m r11 EOE 7670 Lecture 9 7 Reed Muller codes 3 Let ff E RTm and let gg E RT 7 1721 By the previous theorem the vectors C1 ff g and C2 f f g must be in RTm 1 If g g then dcl02 2dff 2 22m If g y g then dC17 C2 6 7 f wg 7 g f 7 f Claim wx y 2 wx 7 Proof Let wry be the number of places in which the nonzero digits ofx and y overlap Then wxy wx7w yw y7w y But since 2wy 2 210 the result follows By this result d017c2 2 wf 7 f Mr 7 g 7 wf 7 f 7 wg 7 I But g 7 g E RltT 71721 so that wg 7 g 2 27 1 0 1 2quot 1 D 1 The Reed decoding algorithm The most interesting codes are those for which effective decoding algorithms exist The decoding algorithms for RM coding rely upon an interesting and powerful idea in coding the majority vote more technically known as majority logic decoding We will demonstrate this rst for a R24 code Let us write the generator for this code as follows We will write the 11 input bits partitioned to correspond to the rows of this matrix as m m07m47m37m27m17m347m247 M 777112 11107111171112 Thus the bits in me are associated with the zeroth order term the m1 bits are associated with the rst order terms and the secondorder terms are associated with mg The encoding operation is Go C 7 607617627 H 7615 7 m9 7 m07m17m2l Cl 2 The general operation of the algorithm is as follows given a received vector r estimates are rst obtained for the highestorder block of message bits m2 Then mgGg is subtracted off from r leaving only lowerorder code words Then the message bits for m1 are obtained which are subtracted and so forth The key to nding the message bits comes from writing multiple equations for the same quantity and taking a majority vote Observe the following COm0 Cim0m1 C2m0m2 Csm0m1m2m12 EOE 7670 Lecture 9 7 Reed Muller codes 4 Adding these code bits together we obtain CoCiC2Cs m12 We can also add together the next four code bits C4C556C7m12 and C8 Cg 010 611 mm and 012 013 014 C15 mlgi Now what we actually have to deal with is the received sequence r To T17 7 T15 We use this in conjunction with the equations above to obtain four estimates of mm 112 T0T1T2T3 112 T4T5T5T7 112 T8 T9 T10 T11 m12T12T13T14T15 Expressions such as this in which the check sums all yield the same value are said to be orthogonal on the message bit mm which is a different usage from the vectorspace sensei From these four estimates we determine the value of mm by majority vote if only one is incorrect we get it right if two are incorrect we can at least detect that an error has occurred It is similarly possible to set up multiple equations for the other secondorder bits m13m14 i H m34i Based upon these equations which I will not write here we determine an estimate of the entire secondorder b oc 7amp2 W134m24ym1477h2377 1377h12 We then peel off77 this layer to get r r 7 m2 Ggi Now we repeat for the rstorder bitsi We have eight orthogonal check sums on each of the rstorder message bitsi For example m1004r01 m10309 m1 C2Cs m1 010611 m1 C465 m1 012613 m1 65C7 m1 014615 From eight estimates obtained from the received codeword we estimate ml by voting Having obtained all the bits in m1 we remove it r r 7 mlGl and look for moi But r m01e so the parity sums in this case are just the bits 7 0 through T15i EOE 7670 Lecture 9 7 Reed Muller codes 5 Up to this point we have dealt with the special case of the R24 code and we could look at the exhaustive list of generator vectors and at least justify that the parity sums work But we need to work out a general way to proceed to other codes This will lead us into some interesting geometric questions First for the codeword C c0c1 i H cn1 we associate ci with the m tuple P that is the complement of the binary equivalent of ii For example the following applies to R24i 239 binary P 0 0000 1111 1 0001 1110 2 0010 1101 These m tuples P can be regarded as points in an m dimensional geometry known as the Euclidean geometry EGm 2 In this geometry we can represent cubes77 by connecting the points Pl those points that differ in exactly one coordinatei In our example every vertex has four immediate neighborsi Each codeword from RT m is an incidence vector that de nes a subspace in RT m in which the nonzero coordinates of the codeword to points lying in the subspace For example the codeword 0110011001100110 E R2 4 is an incidence vector for the subspace containing the points P1 P2 P5 P5 P9 P10 P13 P14 Based upon this geometry we can nd equations for orthogonal checksums as follows To nd a set of orthogonal checksums that provide an estimate for the kth order message bit milky ik corresponding to the basis vectors Vilvi2 Vik39 1 Let S be the subspace of points associated with the incidence vectors Vi Vi2 Niki 2 Form the set difference77 j17j27m 439ch 1727M 7m i17i2ym 72k Let T be the subspace of point associated with the incidence vector le ij ijiki The space T is said to be the complementary subspace to 5 quot CAD i The rst checksum consists of the sum of the codeword coordinates speci ed b T F The rest of the codewords are obtained by translating T with respect to the nonzero elements 0 i Whewl Is that cryptic or what EOE 7670 Lecture 9 7 Reed Muller codes 6 Example 4 Checksums for R27 4 Let us nd checksums for V2V4 00000000000011111 The subspace for Which V3V4 is an incidence vector contains t e S P12P13P14P15 0011001000010000 Dotted line The difference set is 139171392 1727374 374 172 Then we use V1V2 00010001000100011 This corresponds to the set of points T Pg7 P77 Pu7 P15 1100101101000000 The darker region1 From this we obtain one checksum 77134 Cs C7 011 615 The translations of T by the nonzero elements of S are by P12 0011 A 1111101101110011 130134 13331312 by P13 0010 A 1110101001010010 131135 13131313 by PM 0001 A 1101100101010001 132135 13101314 These correspond to the checksums m34000408012 m34010509013 77134 C2Cs610614 Other checksums are obtained similarlyi D 2 Algorithms for rstorder RM codes Some ef cient algorithms have been developed for rstorder R1m codesi Con sider the R13 code generated by 1 C 507517111707 mG m07m37m27m1 V V1 1 1 1 1 1 1 1 1 7 0 0 0 0 1 1 1 1 mo mg m ml 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 EOE 7670 Lecture 9 7 Reed Muller codes 7 The columns of G are simply the 4tuples 1000 increasing to 1111 in binary counting order We can generate these using a simple counter circuiti Decoding We can translate the binary received signal r to a i1 sequence by the mapping Hr F 71T071 m71m711 De ne the correlation between two of the sequences as n71 corFG 7 001F0F1m Fn1G0Glm GH 7 Zia0 i0 Finding the the codeword C that minimizes the distance dr C is equivalent to nding the codeword that maximizes the correlation corfr fc1 The operation of computing the correlation can be performed ef ciently by means of the Hadamard transformi Let F FHQm denote the Hadamard transform of F where Hgm is the T X T Hadamard matrix For decoding the R1 3 code we would use the Hadamard matrix 11111111 17171717 11771177 17711771 H811117777 17177171 11777711 1717117 Observe that the rst second and fourth columns starting counting from the zeroth column are 7V17V2 and 7V3 respectively The ith column of H3 where i igigil in binary is the vector HCD 7i1V1 i2V2 13 For example the fth column 5 101 consists of the vector f1v1 0 V2 1v3 7 f10101010 7 11110000 7 f01011010 7 1717 7171 The Hadamard transform of F fr thus computes the correlation of fr with the mappings of all the codewordsi We simply nd the coordinate in the transform with the largest value and determine the codeword from it There is one last trick The R1m code has 2m1 codewords in it and we only get 7 values out of the Hadamard transform just described However we note that if we complement each bit by f1c f1c1v1 chQ cmvm then the correlation is the negative of fc1 Thus we can look at the sign and on that basis get the other half of the codewordsi H Given r compute F fr1 Compute the Hadade transform F FHgm E0 Determine the coordinate a ami 1 1 agal where F has the greatest magni tude starting count from zero Let Fa denote the correlation value at that coordinate 9 EOE 7670 Lecture 9 7 Reed Muller codes 8 41 If Fa is negative then C 1 alvl amvmr if Fa is positive then C alvl amvmr Example 5 We receive r 10000011 11 F 71111117 7 21 F FHg 2 4172172704 3 Fa 76 starting count from zero and a 6 110 41 The codeword is c 1 1v3 1v2 0v1 11000011 D Fast algorithms exist for the Hadamard transform making the decoding operation fairly ef cient ECE 7670 Lecture 10 i A short look at cryptography As may be appreciated there are several useful connections between cryptog raphy and error control codingi Some of the algebraic techniques used in error correction codes end up getting employed in cryptogaphic techniques Other meth ods are entirely new but share an analytical kinshipi In any event it is arguable that cryptography is a very important facet in the technological future providing the difference between useful network commerce and dismal failure We will focus on publickey algorithms These have a public key part and a private key part Describe mailing a signed letter for example Public key algorithms rely on the fact that some problems may be extremely dif cult to solve unless a key number is known If this number is known then it is straightforward The easy approach when the key is known is known as a trapdoor and such problems with known trapdoors are called trapdoor functions 1 RSA Named after its inventors Ron Rivest Adi Shamir and Leonard Adleman this method gets its security from the dif culty of factoring large numbers Choose two random prime numbers p and q of roughly equal length for best security and compute n 174 Then randomly choose an encryption key 6 such that 67 10 1q 711 they are relatively primei By the extended Euclidean algorithm there are numbers d and f such that def01471 1 ed E 1 mod p14 That is d 6 1 mod p 1 7 The numbers 6 and n are the public key d is the private key The factors p and 4 should be discarded and never revealedi Encryption break the message into blocks of length less than the length of n For each block mi compute the encryption by Ci mod To decrypt we compute mi 0 mod n cf c p71q711 mimMP lxq l mod n for some integer kl Now we need a result from number theory Recall the function the number of integers less than or equal to m that are relatively prime to mi Eulerls theorem awm E mod m if am ll EOE 7670 Lecture 10 7 A short look at cryptography 2 Assuming that l we therefore get in our decodig c mi as desired To crack this a person knowing n and 6 would have to factor n to nd d At least this is what is believed is necessary Example 1 Let p 47 and q 71 n 3337 p 71e 71 3220 The encryption key must be relatively prime to 3220 take 6 79 Then we nd by the Euclidean algorithm that d 1019 To encode m1 688 we compute cl 6887g mod 3337 1570 If we exponentiate 1570101g mod 3337 688 2 On the availability of primes The following observations have been made by Schneier There are approximately 10151 primes 512 bits in length or less With approx imately 1077 atoms in the universe and if every atom in the universe needed a billion new primes every microsecond from the beginning of time until now you would need only 10109 primes So the odds of two people picking the same prime at random is for all practical purposes zero The odds of that happening are signi cantly less than the odds of your computer spontaneously combusting at the exact moment you win the lottery77 Nor can all the primes of interest be prestored If you could store one gigabyte of data per gram the list of the 512bit primes would weigh so much that it would exceed the Chandrasar sic limit and collapse into a black hole77 Of course the problem is nding long primes This is done not by factoring but by testing pick a number and determine if it is prime by a primality test 3 McEliece Who is a CaltechJPL came up with a method based on a family of error correcting codes known as Goppa codes that can correct t errors The private key an X n generator G for the code a permutation matrix P and a nonsingular matrix S The public key The k X n matrix C SG P Encryption c mG z where 2 is a random sequence of weight S t Decryption 1 Compute c cP l 2 Decode to nd the nearest sequence m 3 Compute m M S l This has not been subjected to successful attack However the key information is large For example a key might have n 1024 k 524 and t 50

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.