ADV TOPICS ALGEBRA
ADV TOPICS ALGEBRA MATH 690A
Popular in Course
Popular in Mathematics (M)
This 55 page Class Notes was uploaded by Ms. Helen Sipes on Sunday September 27, 2015. The Class Notes belongs to MATH 690A at Iowa State University taught by Staff in Fall. Since its upload, it has received 66 views. For similar materials see /class/214498/math-690a-iowa-state-university in Mathematics (M) at Iowa State University.
Reviews for ADV TOPICS ALGEBRA
Report this Material
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: 09/27/15
lkunnnnglt30des James Fiedler FaH2004 1n the late 1940s Richard Hamming recognized that the further evolution of computers required greater reliability in particular the ability to detect and correct errors At the time parity checking was being used to detect errors but was unable to correct any errors He created the Hamming Codes perfect 1error correcting codes and the extended Hamming Codes 1error correcting and 2error detecting codesi Hamming Codes are still widely used in computing 39 39 ot er 39 39 including data compression popular puzzles and turbo codesi De nition A code C is a subset of A for some set or alphabet A1 De nition A code with a eld as alphabet and which is a linear space over the eld is a linear code De nition A word is an element of A711 A codeword is an element of C1 Here the alphabets will be nite elds Linear codes with length n and dimension k will be described as nk codesi Hamming Codes are linear codes and a Hamming Code will be described as a nk q ary Hamming Code where q is the size of the base eld Fqi In other words an nk qary Hamming Code is a linear subspace of the ndimensional vector space over Fqi As an introduction here is a concrete construction of a 74 binary Hamming Codei Begin with 4 ordered bits base eld F2 of information and rename these as 13 I5 15 17 respectively Choose 14 1515I7 6 F2 12 1315I7 6 F2 11 13 15 17 6 F2 Our Hamming codeword is then 11 12 13 I4 15 15 17 So for instance if we started with 1 0 1 0 we would get stepbystep 1112114011 11 12 1 0 0 1 1 11 1 1 0 0 1 1 0 1 1 0 0 1 1 Now for the error correction we do the following Let a I41515I7 b I2Is1517 C I1Is15177 and suppose that one error occurred during transmission of the codeword 11 12 13 I4 15 15 17 Then abc interpreted as a binary number will give the subscript of the bit that is in error For instance suppose we sent 0 1 1 0 0 1 1 and 0 1 1 0 1 1 1 was received In this case we compute a 1 b 0 c 1 and abc101 which is the binary representation of 5 so we know that the 5 bit is wrong If there is no error then abc 000 indicates no error occurred For a more general construction of nk binary codes we need the de nitions of generator and check matricesi De nition A generator matrix G for an nk linear code C over any eld Fq is a kbyn matrix for which the row space is the given code In other words 0 xG x e Ff De nition The dual of a code C is the orthogonal complement Cir De nition A check matrix for an n k linear code is a generator matrix for the dual code If C is an nk linear code the dual to it is an n nk linear code If M is the check matrix for C M is an n 7 k X k matrix the rows of which are orthogonal to C and x l MXT 0 Ci ur general construction of a binary Hamming Code is actually a construc tion of a matrix from which we7ll de ne the Hamming Code as the linear code for which this matrix is the check matrix For a given positive integer r form an r X 2T 7 1 matrix M by making the columns the binary representations of 1111 7 1 not necessary in increasing order though this is often most convenient Now x l MXT 0 is a linear code of dimension 2T 71 7 r which we de ne to be a 2T 71 2T 717 r binary Hamming Coder Call x l MXT 0 a 2T 7 1 2T 7 1 7 r binary Hamming Code The 74 binary Hamming Code r 3 rst introduced has check matrix 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 the code is C0000000100001101001010001111 0011001 0010011 0010110 0110011 E0110111lE01011113E1000011lE10110103 1110000100110011001101111111 The construction also produces for 7 3 the check matrix 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 which gives a different set of Hamming codewords and thus a different 74 binary Hamming Code The word 1 0 0 0 1 1 1 is in this latter code but does not appear in the list for the former De nition The Hamming distance d between any two words of the same length is de ned as the number of coordinates in which they differ Any mention of distance herein refers to Hamming distance Proposition The minimum distance between binary Hamming codewords is 31 Proof Suppose x and y are two codewords from a Hamming Code C with check matrix M1 Then x 7 y E C since C is a linear code If dHX y 1 then Mxy is a column of M1 All columns of M are nonzero but if x y is a Hamming codeword then Mxy 01 Contradiction lf dHX y 2 then Mxy 0 iff there are two columns of M which are linearly dependenti This is not the case hence dHxy 2 3 for all codewords x y Every check matrix for a binary Hamming Code will have three columns that are linearly dependent so in fact some codewords are of distance 31 It is easy to see the Hamming distance is a metric Then any word within distance 1 to a codeword is in fact within distance 1 to a unique codewordi Thus if any Hamming codeword is transmitted and at most 1 error occurs then the original codeword is the unique codeword within distance 1 to the received word Thus it is true that the minimum distance between any two Hamming codewords is 2 3 then it is true that Hamming Codes are 1error correctingi Decoding any received word to this nearest Hamming codeword corrects any single error In the general case error correction is even easier than in the introductory concrete construction Again we are assuming no more than one error during transmission The method is called syndrome decodingi 1n the case of binary Hamming Codes syndrome decoding takes the following formi Both the sender and receiver of a word have agreed on an nk binary Hamming Code with check matrix M1 Upon receiving a word y the receiver will compute MyT which will be a binary rtuple and thus be either the zero rtuple in which case there is no error or be identical to one column of M since M cointains every possible nonzero binaryrtuple as a column say mil This tells the receiver that an error has occurred in the ith coordinate of y Consider the example from the concrete construction above where we sent 0 1 1 0 0 1 1 and 0 1 1 0 1 1 1 was received The syndrome is 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 1 whic matches the 5 column of the check matrix We take this to mean that the 5 bit of the received word is in error Hamming Codes run into problems if more than one error has occurred If in the last example the word 1 1 1 0 1 1 1 is received errors in places 1 and 5 then the syndrome will be 1 1 00011111 1 011001100 10101011 0 1 1 telling us to switch the 4 bit which will give the word 0 1 1 1 1 1 1 Thus more than one error can not be corrected nor even can we know that more than one error has occurred The extended Hamming Codes are slightly more powerful able to detect when 2 errors have occurred as well as able to correct any single errori Returning to the introductory construction of a 74 binary Hamming Code we include a new 77 parity check77 bit 10 with 1011I213I4I5I5I77 so that all eight digits sum to 0 The code now has length 8 and is still a linear code of dimension 4 We call this code an 84 extended binary Hamming Code The construction of an extended binary Hamming Code which corrects one error and detects two follows the same procedure for any length n just add a parity check biti Check matrices can easily be constructed for the extended binary Hamming Codes from the check matrix for a Hamming Code add a zero column on the left then a row of all 17s on the bottomi For example the Hamming Code with check matrix 01111 10011 10101 0 1 0 9 becomes the extended Hammin Code with check matrix Suppose that x and y are binary Hamming codewords of distance 31 Then one of x or y has even parity and the other odd say x has even parity1 If x and y are the extended Hamming codewords obtained from adding a check digit1 Then 10 0 since x has even parity and yo 1 since y has odd parity1 The distance between x and y is one more than the distance between x y so the minimum distance between codewords of an extended Hamming Code is 41 Now any received word with one error is distance 1 from a unique codeword and a received word with 2 errors is not within distance 1 from any codeword1 If a word is within distance 1 to a codeword then we decode the word to that codeword as before If a word is not within distance 1 to any codeword then we recognize that 2 errors have occurred and report that two errors have occurred Decoding with an extended Hamming Code is a little more complicated Let M be a check matrix for an extended Hamming Code let M7 be the regular Hamming Code matrix from which is was derived and let y yo yl 1 1 1 yn be a received word Suppose only one error has occurred and suppose rst that it has occurred in the last n bits1 Computing the rst n rows of the syndrome My is the same as computing the syndrome Myl ynT1 This last syndrome will be nonzero since there is an error in one of these bits1 The last row of the syndrome MyT will be 1 since the parity is off with only one error1 Thus the syndrome matches a column of M1 Suppose now that only the parity bit is in error1 Then Myl 1 11 ynT will be zero so the rst n columns of MyT will be zero but the last column will be 1 since the parity is off again thus MyT will match the rst column of M1 Thus as long as the syndrome matches a column of the check matrix then we can assume 1 error has occurred and switch the bit of the word corresponding to that column Now suppose 2 errors have occurred Wherever they occur the parity of the entire word will be correct thus the syndrome will have a 0 in the last row and will not be a column of the check matrix The syndrome will not be zero either since codewords of the extended Hamming Code are distance at least 4 apart1 Thus a nonzero noncolumn syndrome indicates 2 errors assuming that no more than two errors occurred1 We can generalize our construction of binary Hamming Codes to qary Ham ming Codes where an nk Hamming Code is now a linear space over a eld of order q prime1 For a given r choose a nonzero rtuple of elements of Fq1 Choose another rtuple from El linearly independent from the rst Make this column 2 Continue choosing rtuples such that any two are linearly independent until it is no longer possible to do so Arrange these rtuples as the columns of a matrix Mi There are qT 7 1 possible nonzero rtuples and each choice eliminates its q 1 nonzero multiples from further consideration Thus the number of columns of our matrix is qT 7 1q 7 1 De ne the linear code for which this is a check matrix to be a 41T 71q 71 qT 71q 7 1 7 T qary Hamming Coder Recall that a check matrix is the generator matrix of the dual code which in this case must have dimension r hence the dimension of our Hamming Code must ben739r qT71q717ri A 42 ternary Sary Hamming Code can be given by the check matrix 1120 0111 which has Hamming Code 000001110222 E1012g20211120 2210 1201 2102 i The same Hamming Code is produced with the check matrix 0 1 1 1 1 0 1 2 A different 42 Hamming Code results from the check matrix Hamming Code These q ary codes are again 1error correcting relying on that fact that each codeword is at a distance of at least 3 from any other codeword which in turn relies on the construction of the check matrix Speci cally the fact that no two columns of the check matrix are linearly dependent means that the minimum distance between any two codewords is at least 3 Syndrome decoding of at most one error easily extends to the q ary casei Again we compute the syndrome MyT for check matrix M and received word y If the syndrome is the zero vector then we assume no error If the syndrome is nonzero then it is a multiple of some column If the syndrome is ami for ozqu and mi the ith column of M take this to mean that an error vector was added to the intended codeword during transmission where the error vector is 0 0 a 0 0 with a in the ith spoti Then we recover the intended codeword asy70 0a 0 0 De nition A sphere of radius p centered at x is SAX y 6 Flt1nld1 10 7yS P For any x E F lSOxl 1 that 1 being just xi There are ql ways to change any coordinate of x and get a new word and n possible coordinates to change Hence l51xl l nq 7 1 There are 3 ways to choose two coordinates to change and q 7 12 ways to change the two so l52xl 1 n l q 71 In general mom 7 ltq7 1y From discussion above a code is eerror correcting if 58 x N 58 y 0 whenever x f y Thus if C is an eerror correcting code lCl 58 S qul for any x since the cardinality of the sphere does not depend on the choice of x This inequality is called the spherepacking boundi De nition An eerror correcting code is called a perfect eerror correcting code if 0 WIN g qul or if e n C n 7 1 l l qul A q 1 10 Proposition Hamming Codes are perfect lerror correcting codesi Proof We need to check that M a 71V 7 mm The right hand side of this is q where n qT 7 lq 7 l The left hand side Wlt1nltq71gtgt 7 W 1 ltq71gtgt Wlt1ltqr71gtgt 7 Wm q n Thus Hamming Codes are perfect lerror correcting codes De nition A ecoverz39ng code is a code C C A for Which A USe xl x E C Proposition If C is an ecovering code then lCl 58 2 qulni De nition lf equality holds in the last proposition then C is called a perfect ecoverz39ng coder Of course the perfect eerror correcting codes and the perfect ecovering codes coincidei It is known that Hamming Codes are the only perfect lerror correcting codesi Goppa Codes Key One Chung Goppa Codes Key One Chung December 2004 Department of Mathematics Iowa State University Ames Iowa 500112064 email kochungiastateedu Page 1 Goppa Codes Key One Chung Contents 1 Introduction 11 Linear Codes 12 Bounds on Codes 13 ReedSolomon Codes 2 Goppa Codes 21 Introduction to Goppa Codes 22 Algebraic and Projective Curves 23 Nonsingularity and the Genus 24 Points Functions Divisors on Curves 25 Good Codes from Algebraic geometry 3 McEliece Cryptosystem k Page 2 Goppa Codes Key One Chung 1 Introduction 11 Linear Codes Definition A linear code C n k overa eld F is a vector subspace of F n with dimension k n is called the length of the code C The minimum distance of C is d mindx mix y E C E 7E Where d1c y is the Hamming distance 71 k d is called the parameter of C Ifa basis for C is T1 rk then T1 T2 G Tic Qa generator matrix for C and C uGiu E Page 3 Goppa Codes Key One Chung What is a good code Why are d and k of C important 0 dimension k the larger the better We may think of each codeword as having k information symbols and n k checks 80 large k with respect to 71 makes an efficient code 0 minimum distance d the larger the better We can correct up to errors How good can a code be k Page 4 Goppa Codes Key One Chung 12 Bounds on Codes Theorem Singleton Bound Let Cn k be a linear code of minimum distance d over Fq Then d g n k i 1 Given n both k and d cannot be large Definition Let q be a prime power and let n d be positive integers with d g n Then the quantity Aqn d is de ned as the maximum value of M such that there is a code over Fq of length n With M codewords and minimum distance d Let Vqn r denote the number of elements in the ball of radius r centered at E for any E E F3 Then Vqnr 2270 q 173 Theorem GilbertVarshamov Bound Aqn d 2 qnqu d 1 k Page 5 Goppa Codes Key One Chung Asymptotic Bounds Definition Let C be a code over Fq of length n with qk codewords and minimum distance d The information rate of C is R krn and the relative minimum distance of C is 6 2 d n Note that 0 g R 6 g 1 and C is a good code if both R and 6 are close to 1 Definition Letq be a prime power and 6 E R With 0 g 6 g 1 Then 1 aq6 lim sup 10gq Aqn 6n n gtoo n aq6 is the largest R such that there is a sequence of codes over Fq with relative minimum distance converging to 6 and information rate converging to R k Page 6 Goppa Codes Key One Chung Set6 1 1q We define a function Hqx on 0 g E g 6 by Hm 0if16 0 xlogqq 1 xlogqx 1 xlogq1 x ifO lt x g 6 The function H q is called the Hilbert entropy function Theorem Asymptotic GilbertVarshamov Bound For any6 with 0 g 6 g 6 we have aq6 Z 1 Hq6 The GilbertVarshamov Bound was the best known lower bound on aq6 for a full 30 years following its original discovery in 1952 In 1982 the existence of a sequence of codes having better than The GilbertVarshamov Bound was first proven by Tsfasman Vladut and Zink using Goppa codes k Page 7 Goppa Codes Key One Chung 13 ReedSolomon Codes Definition LT f e Fqixiidegm g r U0 Note that LT is a vector subspace over Fq Definition F2 a1aq1and1 g k 3 q 1 Then the ReedSolomon code RS k3 q is de ned to be RSWQ I f061 7f06q 1if E Liz 1 It is an image of a linear transformation 6 Lk1 gt Fill 1 given by f 17061 7fO q 1 Parameters of RSIltq are n q 1 dim C k and d n k 1 k Page 8 Goppa Codes Key One Chung o By singleton bound given 71 q 1 and dimension k3 RSlt q is the best 0 However it is a very restrictive class of codes because the length is so small with regard to the alphabet size q1q o In practice we want to work with codes which are long with respect to the alphabet size k Page 9 Goppa Codes Key One Chung 2 Goppa Codes 21 Introduction to Goppa Codes 1981 1 Choose a finite field Fq 2 Choose a projective nonsingular plane curve X over Fq 3 Pick 71 distinct Fqrational points 73 P1Pn C XFq on X 4 Choose a divisor D on X such that 73 suppD 0 5 Goppa code CX7737D I fP1 fPnif E LD C F k Page 10 Goppa Codes Key One Chung Note 1 dim C dim LD 2 If f17 fk is a basis for LD over Fq then f1P1 f1Pn is a generator matrix for C fkP1 fkPn 3 It is the first infinite family of codes whose parameters beats the GilbertVarshamov bound k Page 1 1 Goppa Codes Key One Chung 22 Algebraic and Projective Curves E denotes the algebraic closure of the field k3 Definition We de ne the af ne place A2 to be the set k2 Definition If f E Mac then the af nealgebraic curve is de ned to be of 2 P e A2lfP 0 Let X be an algebraic curve over k3 Then X f E kxylfP 0foraP E X is an ideal of Mac The quotient ring I X Mac yIX is called the coordinate ring of X k Page 12 Goppa Codes Key One Chung Example x y y x2 and gxy y C E RJcy In R if C gt 0 then we have two intersections If C 0 then we have a single intersection of multiplicity 2 InC IE 2 If g1c y IE C then we have one intersection However if we regard Cf and Cg intersect once at infinity as well then iC39f H 09 2 k Page 13 Goppa Codes Key One Chung For given x y E Mac we construct the polynomial FX Y Z deXZ YZ e m Y Z where d degf The polynomial F is called the homogenization of f Observation 39 9507390 0ltgtFIE07CUO1 0 o For any 04 E k we have FaX 041 aZ adFXY Z 80 FX0Y0Z0 0 ltgt F04X004Y004Z0 0for all 04 E k gt We identify the solutions X0 Y0 Z0 and aXO 04K aZO 0 Since F is homogeneous F0 0 0 0 gt We ignore the solution 0 0 0 ofF 0 k Page 14 Goppa Codes Key One Chung Definition The projective plane is PW k3000 N where X0Y0 ZO X1 Y1Zl ifand onyifthere is some a e k with X1 aXO Y1 Osz and Z1 aZO We write X0 Y0 Z0 forthe equivalence class of X 0 Y0 Z0 in P2 By multiplying through by a unit we have P2k X02Y01lX0Y0 e kUX01OlX0 e k Um 0 0 Any point of the form X Y 0 is called a point at in nity k Page 15 Goppa Codes Key One Chung Definition Let F be the homogenization of f Then the projective curve of F is 07 XO Y0 20 e P2EiFXOYOZO 0 Example f1c y y x2 g1c y IE C What is 07 CA39g FXY Z 22YZ xZ2 YZ X2 GXYZ X CZ WhenZ1YX2andXCSowehavecc2 1 Whenz0X0X2Sowehave010 Therefore 539 2 Theorem Bezout s Theorem If f g E Mac y are polynomials of degree d and 6 respectively then Cf and Cg intersect in at most d6 points Further Cf and CA39g intersect in exactly d6 points of P2 when points are counted With multiplicity k Page 16 Goppa Codes Key One Chung G3 Nonsingularity and the Genus For coding theory we only want to work with nice curves Since we have already decided to restrict ourselves to plane curves the only other restriction we will need is that our curve will be nonsingular Definition Let fZE y E Mac A singularpoint of Of is a pointp E E X E such that f p fxp fyp 0 The curve Cf is nonsingular if it has no singular points If F is the homogenization of f then P E P2 is a singular point ofa iffP FX P FyP FZP 0 The curve CA39f is nonsingularif it has no singular points Note lntuitively a singular point is a point where the curve does not have a welldefined tangent line or where it intersects itself Definition Pliicker Formula Let fZE y E Mac y be a polynomial of degree d such that Of is nonsingular Then the genus of Of or of Of is de ned to be d 1d 2 Page 17 Goppa Codes Key One Chung 24 Points Functions Divisors on Curves Definition Let C be the projective plane curve de ned by F 0 Where F E kX Y Z is a homogeneous polynomial Let K be an extension eld of k We de ne a Krational point on C to be a point X0 Y0 Z0 E P2 such that F X0 Y0 Z0 0 C K denotes the set of all K rational points on C Definition Let C be a nonsingular projective plane curve A point of degree n on C over Fq is a set P P0 Pn1 ofn distinct points in CFqn such that P7 JENKPO forz39 1 n 1 Where can Fqn gt Fqn is the Frobenius automorphism With aqmm Olq Note Elements of Cki are called points of degree one or simply rational points k Page 18 Goppa Codes Key One Chung Example Let CO be the projective plane curve over F3 corresponding to 119673 92 x3 2x 2 E F3xy Homogenization FXY Z Y2Z X3 2XZ2 2Z3 0 FX 4Z2ZO Fy 2YZO F2 2 Y2 4XZ2Y22XZO gtZYXO 80 CO is nonsingular Also genus g 1 k Page 19 21 2 Goppa Codes Key One Chung Now let s find points of degree 1rational points 00F3 yZ x3 2x 2O If E 0 then y2 2 No such elements in F3 If E 1 then y2 2 No such elements in F3 If E 2 then y2 2 No such elements in F3 80 no rational points of the type X Y 1 WhenZ 0 X3 0 80 X 0 So COF3 P00 2 O 1 k Page 20 Goppa Codes Key One Chung To find the points of degree 2 let s compute COF32 first Note thatt2 l 1 is irreducible over F3 Then F9 F3tt2 l 1 Let 04 E F9 corresponding t Then F9 a l boda b E F3 where a2 12WhenZ1Y2 X3 2X 20 le0Y2 2gtYaor a2a So0a102a 1 E COF9 By doing similar computation COF9 0a102a11a112a1 2 oz 1 2 204 1POO Frobenius map 0372 F9 gt F9 or i gt 043 204 Then 0320 oz 1 0 204 1 So we have one pointQ1 0 oz 1 0 204 1 of degree 2 Similarly Q2 1 oz 1 1 204 Q3 2 oz 1 2 204 So we have three points of degree two on CO Page 21 Goppa Codes Key One Chung Similarly F33 F3tt3 2t 2 and let w E F27 corresponding to t Thenwehave 00F27 w011w01 12w2w212w2w21POO with 28 F27rational points Also we see that 00F27 R1 U URQ UPoo where R1 R9 are the nine points of degree three on CO Forexample R1 0 11 w 0 1 2 1 11 0 k Page 22 Goppa Codes Key One Chung Let C and Cquot be two projective plane curves over Fq defined by polynomials of degree d and 6 respectively Then the set of points overF q where they intersect will cluster into points P1 Pl of varying degrees over Fq where a point is listed more than once if the intersection of the two curves is with multiplicity greater than one Let n denote the degree of the point P7 over Fq Then we have de 71 73 l l rl Inthis case we write C C P1Pz and call C H Cquot the intersection divisor of C and Cquot k Page 23 Goppa Codes Key One Chung Definition 0 Let C be a curve de ned by over Fq A divisorD on C over Fq is an element of the free abelian group on the set of pointsof arbitrary degree on C over Fq Thus every divisor is of the form D Z nQQ Where the nQ are integers and each Q is a point of arbitrary degree on C o If mg 2 0 for all Q we call D effective and write D Z 0 0 We de ne the degree of the divisor D Z nQQ to be deg D Z nQdeg Q o the support ofthe divisorD Z nQQ is supp D QinQ 7E 0 Note C H Cquot is an effective divisor of degree d6 k Page 24 Goppa Codes Key One Chung Definition Let FX Y Z be the polynomial which de nes the nonsingular projective plane curve C over the eld Fq The eld of rational functions on C is FqC igh e FqXY Z hom same deg Um N Wheregh N g h ifand onyifgh g h E C FqXYZ Example FX Y Z 122 X3 2X22 223 e F3X Y Z Then X2Z2 Y2 XZ Z2XZ in F3CO since X2XZ 2202 XZ Z2 2 ZX3 2Y2 XZ2 Z3 6 ltFgt k Page 25 Goppa Codes Key One Chung Definition Let C be a curve de ned over Fq and let f gh E FqC The divisor off is de ned to be divf Z P 2 Q Where Z P is the intersection divisor C H Cg and 2 Q the intersection divisor C H Ch Note that since degC Cg degC Oh we have deg dz3921f 0 Definition Let D be a divisor on the nonsingular projective plane curve C de ned over the eld Fq Then the space of rational functions associated to D is LltDgt f e Fq0idz39vf D 2 0 Um Note LD is a finite dimensional vector space over Fq k Page 26 Goppa Codes Key One Chung Theorem RiemannRoch Theorem Let C be a nonsingular projective plane curve of genus 9 de ned over Fq and let D be a divisor on C Then dim LD 2 deg D 1 g Further ifdeg D gt 29 2 then dim LD degD 1 g Page 27 Goppa Codes Key One Chung 25 Good Codes from Algebraic geometry Theorem Let X be a nonsingular projective plane curve of genus g de ned over Fq Let 73 C X Fq be a set of n distinct Fqrational points on X and let D be a divisor on X satisfying 2g 2 lt deg D lt n Then Goppa code C CX 73 D is linear oflength n dimension k 2 deg D l 1 g and the minimum distance d Where d 2 n deg D Note The information rate R of C is krn deg D l 1 gn and the relative minimum distance 6 of C is dn Z n deg We want R l 6 large We have R6Z de D1 n de D g n 9 i n9 1 l 1n gn So for given genus g it is betterto have large n g lXFql k Page 28 Goppa Codes Key One Chung How many rational points can a curve of genus 9 have Theorem HasseWeil let X be a nonsinguar projective curve of genus 9 over Fq and set N XFq Then W q1i S 29 Theorem Serre In the situation of the above theorem we have iN q1i S 9L2xEJ k Page 29 Goppa Codes Key One Chung 3 McEliece Public Key Cryptosystem 31 Idea Syndrome decoding of linear codes when considered as a decision problem is an NPcomplete problem if the number of errors is not bounded However there are classes of linear codes which have very fast decoding algorithms The basic idea of the McEliece system is to take one of these linear codes and disguise it so that Oscar when trying to decrypt a message is forced to use syndrome decoding while Bob who set up the system can remove the disguise and use the fast decoding algorithm McEliece suggested using Goppa Codes which are linear codes with a fast decoding algorithm in the system but any linear code with a good decoding algorithm can be used k Page 30 Goppa Codes Key One Chung 32 Key Creation 0 The private key consists of the matrices S G P where S is a random invertible k X k matrix P is a random n X n permutation matrix and G is the k X n generator matrix of a Goppa code that corrects up to t errors 0 The public key is the matrix product of the three private matrices so it is a k X 71 matrix G SGP Additionally a number 15 g t has to be advertised which stands for the number of errors that a sender of a message is allowed to add to his message 80 the public key is G t k Page 31 Goppa Codes Key One Chung G3 Encryption encoding 34 Decryption k The plain text is dissected into blocks of size k bits For every block a random error vector of size n that has at most 15 entries is chosen and is added to the Cme The receiver multiplies the cipher text with the inverse of the permutation matrix C CP1 WLGP 1 l eP 1 mSG l P1 Since G is a t error correcting code and eP 1 will contain at most the t g t intentional errors he can quickly Goppa decode into C and already has the result 7713 To get the plain text messages he will then multiply with the inverse of S m mSS1 Page 32 Goppa Codes Key One Chung 65 Security To be able to use a trap door Goppa code to decipher a message the inverse matrices of P and S have to be known If some unauthorized person does not have this information she will face the problem to solve a linear code With an average choice oft Z 50 and n 2 210 this is a very difficult problem 36 Drawbacks o The size of the public key is quite large Using the Goppa code with parameters suggested by McEliece the public key would consist of 219 bits This will certainly cause implementation problems 0 The encrypted message is much longer than the plaintext message This increase of the bandwidth makes the system more prone to transmission errors Page 33 Goppa Codes Key One Chung 37 Discussion m encrypt C encode C public line C l C decode C decrypt m m encrypt C mG l C public line C mG l C l C decrypt m Assume that we have a Goppa code Cn k with the minimum distance d 2t l 1 As we stated ift Z 50 and n 2 210 then McEIiece Cryptosystem is considered to be fairly secure However we need a big key size We know that cellular phone does not require much security Therefore it would be a good problem to find a proper t t and 71 having a little security for cellular phone and not so much big key size In this case we can correct up to t t errors k Page 34 Goppa Codes Key One Chung References 1 JL Walker Codes and Curves American Mathematical Society 2000 1 44 2 JH Silverman The Arithmetic of Elliptic Curves Springer 1986 1 44 3 PJ Morandi Error Correcting Codes and Algebraic Curves Lecture Notes 2001 3 63 httpemmynmsuedu pmorandimath601f01LectureNotespdf 4 B Cherowitzo httpwwwmathcudenveredu wcherowicoursesm5410ctcmcehtm 5 httpentropystop1984comenmceliecehtml k Page 35 BCH Codes Bose Chaudhuri and Hocquenghem Introduction How do we modify a Hamming code to correct two errors In other words how can we increase its minimum distance from 3 to 5 We will either have to lengthen the code words or eliminate some of them from our code Correcting two errors in a long word may not be much better than correcting one error in a short one So we will try to produce a double error correcting subcode of the Hamming code by removing some code words to make a new code BCH codes is a generalization of Hamming codes for multiple error correction Binary BCH codes were first discovered by A Hocquenghem in 1959 an independently by RC Bose and DK RayChaudhuri in 1960 1 BCH Codes as Subcodes of Hamming Codes Recall that an encoder E for a linear binary nmblock code C is a linear map from Bm to B De nition 11 Let C be a linear nmcode with encoder E Let the n X m matrix C be chosen so that GIT for any word I of length m Then G is called a generator matrix of the code C De nition 12 A check matrix for a linear code C over a eld F is a k X n matrix H with the property that for any word 1 in F H UT 0 if and only if v E C The number k is arbitrary here but the smallest possible value for k is n 7 min terms of linear algebra C is the null space of H The most natural way of reducing the set of words of a Hamming code is by introducing further checks ie adding new rows to the Hamming check matrix Hk The additional checks may be a linear combination of the ones that we have In that case the set of code words will not be changed Although the set of code words may be reduced the minimum distance may not be increased Finding additional checks is not easy at all because we have to find a nonlinear extension rows for the check matrix Hk On the other hand if we form the extra rows in an unstructured way it will be difficult to prove that the minimum distance increases So new rows must be de ned in a systematic way Since B 01 has only two elements it is not easy to de ne nonlinear functions for binary vectors For this we follow this trick we gather bits together in groups of k and consider the groups to represent the elements of the eld CFOk For this larger eld there are many nonlinear functions for example 13 Example 13 Consider the columns of the Hamming check matrix H4 as representing the nonzero elements of CF24 Bzz4 13 1 Choosing the columns of H4 in a decreasing powers of the primitive element 2 gives the check matrix H4 in the following form 126313105147151198421 1n binary digits this matrix is 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 Now we add further rows of elements of GF24 to extend the matrix as simple as possible the simplest way of extending the rows is to choose each entry as a function of the original entry at the head of its column ie 2139 1617 M where is some function for i 1 7 Good choice of f1 m fr will enable us to correct an additional error per block Vandermonde Matrices Theorem 14 Let C be a linear code with check matrix H Then C has minimum distance greater than d if and only if no set of d columns of H is linearly independent There are families of matrices for which the condition can be veri ed The simplest of these families is the class of of Vandermonde matrices De nition 15 An n X n Vandermonde matrix V is de ned as follows The rst row of V can be chosen arbitrarily A1 A2 m An then the whole matrix is A1 A2 An A A3 A V V1727 my An Ail A A2 Theorem 16 If A1 A2 n are distinct7 then the columns of V V12 M An are linearly independent over F Extending a Hamming Check Matrix We have the following proposition from linear codes Proposition 17 A code can correct all errors of weight S t if and only if it has minimum distance 2 27H 1 De nition 18 We de ne the double error correcting BCH code BCHk2 to have the check matrix V1672 with columns 3 E98 3333 E Here a is the primitive element of the eld Example 19 V4 has the following form 14 7 15 11 9 8 4 2 12 3 10 14 15 9 5 15 8 1 3 5 15 4 6 5 11 2 3 14 rooohum HHHH Veri cation To verify that the code has minimum distance 5 and thus can correct 2 errors7 we have to prove that no four columns of V4 are linearly dependent Proposition 110 No four columns of V4 are linearly dependent proof Suppose that Vi Vj Vk V are four different columns of V43 They form a Vandermonde matrix Oli Otj 01k Oil 12139 12139 a2k a2 13139 13139 ask as 14139 14139 a4k a4 Moreover7 ai aj 04k and al are distinct and nonzero7 so it follows from the Theorem 2 that the columns Vi Vj Vk V are linearly independent Further Extension De nition 111 The t errorcorrecting BCH code BCHkt over the eld of order 2k based on the primitive element k 7 a has as its check matrix an n X 275 matrix V1167 where n e number the columns Vi of V16 from 0 to n 7 counting from the right Then for i 01 n 7 17 Vi is de ned by the formula The block length of the code is the number of the columns of its check matrix In this case n2k 7 1 For a code to have minimum distance greater than 2t we must have 2t lt n Hence this de nition makes sense for t lt 2k 1 Example 112 The chcek matrix of BCH43 is V V43 The columns are where i 1413 0 and the complete matrix is 12 6 3 13 10 5 14 7 15 11 9 8 4 2 1 6 13 5 7 11 8 2 12 3 10 14 15 9 4 1 3 5 15 8 1 3 5 15 8 1 3 5 15 8 1 13 7 8 12 10 15 4 6 5 11 2 3 14 9 1 10 11 1 10 11 1 10 11 1 10 11 1 10 11 1 5 8 3 15 1 5 8 3 15 1 5 8 3 15 1 This matrix can also be written in binary form as a 24 X 15 matrix7 in which each column consists of the binary repre sentations of the elements of GF24 in the matrix above The Reduced Check Matrix The matrix V16 contains many redundant rows for it to be a practical check 1n elds of characteristic 27 squaring is a linear function and we know that any row of a check matrix that is a linear function of the other rows is redundant So we will introduce a reduced check matrix H16 that contains only the oddnumbered rows of V1 De nition 113 The matrix H16 obtained from V16 by deleting the evennumbered rows is called the reduced check matrix of BCHUsJ The rows of H1 will be numbered with the same indices as in k Example 114 The reduced check matrix of BCH43 is 12 6 3 13 10 5 14 7 15 11 9 8 4 2 1 H43 3 5 15 8 1 3 5 15 8 1 3 5 15 8 1 10 11 1 10 11 1 10 11 1 10 11 1 10 11 1 Proposition 115 For any It and t lt 2116 1 the matrices H16 and V16 are check matrices for the same code BCHUcJ proof Let w14w13w0 be a code word of the code C de ned by H1 then H167th 0 This product can be expressed as the equations 14 Z wiaik 0 2390 which hold for all odd k lt 2t Since wi is either 0 or 1 for all i wi By squaring the previous equation7 we nd that 14 Ewiam 0 i0 for all 16 But this states that 14 th 0 Hence w is a code word of BCHUc7 it Since the rows of H16 are a subset of V1 any code word of BCHkt must be a code word of C Thus two codes are equal Theorem 116 BCHUc7 t has a block length n 2k 7 1 and rank at least n 7 kt Theorem 1171t has minimum distance at least 2t 1 so it can correct all error patterns of weight at most ti proof We apply the criterion of the Vandermonde Theorem to the check matrix V16 We must show that no 2t columns of V16 are linearly independent Choose 2t columns Via Via in Vial and consider the matrix formed by these columns Denoting the power at by ak we have the following matrix 11 a2 a2 2 2 2 a1 a2 12 2t 2t 2t 11 a2 12 This is a Vandermonde matrix and a1a2wagt are distinct and nonzero so the columns are linearly independent Hence it follows from Theorem 1 that BCHk t has a minimum distance greater than 2t The Check Matrix and Error Patterns De nition 118 Given a linear nmcode C and check matrix H the syndrome of a word u of length n is HuTT so syndrome of a word is a row vector Proposition 119 Let u be a code word of BCHk t and let 1 be obtained from u by adding an error pattern 6 of weight at most t ie 1 u e Then 6 is uniquely determined by the syndrome 116th proof Assume that an error pattern f y e of weight at most t produces the same syndrome as 1 then va 7 fT 0 so 1 7 f is a code word But the Hamming distance from u to v 7 f u e 7 f is the weight of e 7 f which is at most 2t contradicting the fact that the minimum distance of the code is greater than 2t 2 BCH Codes as Polynomial Codes Checking a binary word Cl 52 m an is a code word of BCHkt is equivalent to verifying the equations for powers 04k of a primitive element a k 12 12ti So it is natural to identify code words 5 with binary polynomials 01 of degree less than n Hence the equations can be rewritten COtk 0 Convention Let V be a vector space E of binary n tuplesi We write an element u E V as un71un2 in u1u0 and identify it with the polynomial n71 2390 The polynomial corresponding to a word u be will be denoted by The set of all binary polynomials of degree less than n will be denoted by Pni Example 21 The code word 000011101100101 corresponds to the polynomial I10I9I81615121 Proposition 22 De nition of BCHkt Let n 2k 7 1 and let the columns of the check matrix V16 be ordered so that Vim 1117171 If 01 E P then Cz is a code polynomial of BCHkta if and only if Caj 0 for all powers j S 2t of at Proposition 23 Let 91 be the product of all the distinct minimal polynomials of a 12 M 12 over B each polynomial is taken only once even if it occurs as a minimal polynomial several times Then a polynomial 01 of degree less than n 2k 7 l is a code polynomial of BCHk ta if and only if91 divides proof lf 91 divides 01 then 0aj 0 for j 12 M 2t because 9aj 0 Hence by Proposition 22 01 is a code polynomia Conversely if 0aj 0 for j l 2 M 2t the minimal polynomial of aj over B divides 01 for all j 91 is the product of these polynomials and each of them are taken only once Since they are distinct and irreducible they are relatively primer so 91 divides 01 De nition 24 The polynomial 91 is called the generator polynomial of BCHktl Rank and the generator polynomial of BCH codes Corollary 25 a The generator polynomial of BCHk t is the unique nonzero polynomial of lowest degree in BCHk t b The rank of BCHkt is 2k 7 de991 71 Example 26 BCH43 the generator polynomial is m21m31m111 14 13 l14 13 12 1 l12 1 1 110 19 18 16 15 12 1 The corresponding code word is 000011101100101 This is the only nonzero code word that starts With four zerosl proof a The degree of a nonzero multiple b191 of 91 is equal to at least deg91 and the equality holds only if 121 is a constant 1 is the only nonzero constant of B Hence all nonzero code polynomials have degree at least equal to deg91 and the only code polynomial With deg91 is b All code polynomials can be obtained by multiplying 91 With 121 of degree less than m 2k 7 de991 7 1 Moreover multiplying 91 by distinct polynomials 91 and 21 of degree S gives different code polynomials So the number of the code polynomials is 27 and therefore the rank is ml Multiplicative encoding The corollary above gives a simple encoding algorithm for BHCk t The message space consists of Pml Encode 121 6 Pn by multiplying it by Example 27 BCH43 Suppose that we want to encode the message word I l 0 l l l The corresponding polynomial is 121 14 12 1 1 then the corresponding code word 01 is obtained by multiplying 121 With the generator polynomial 91 110 19 18 16 15 12 1 so 01 b191 1l4 11319 16 15131l and the corresponding code word is 110001001101011 A Generator Matrix for BCHkt We Will use the generator polynomial 91 to construct a generator matrix for BCHkt ilel represent polynomial mul tiplication by the generator matrix 91 by a suitable matrix The columns of the generator matrix of a code C are the all code words of C We choose as the columns of the code words corresponding to for i m 7 1721 7 2 M l 0 Example 28 BCH43 A generator matrix C for BCH43 is 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 This matrix is obtained by writing down as successive columns of the coef cients of for i 4372170 where 91 110 19 18 16 15 12 11 Suppose that our message contains a block b 1 0 1 1 1 The corresponding codeword0isGbT1100010011010111 For linear codes7 we have the following proposition Proposition 29 Let C be an mm linear code and let G be an n X n matrixi Then G is a generator matrix for C if and only if it has rank m and its columns are code words Proposition 210 Let 91 be a generator polynomial of BCHk7 t and let G be the n X n matrix constructed by taking as its columns the coef cients of for i m 7 17 m 10 then G is a generator matrix for BCHkt The Check Polynomial Let 9 2k and let n q 7 1i 1 7 1 is the product of distinct minimal polynomials of the nonzero elements of GFqi The generator polynomial 91 of BCHkt is the product of a certain subset of these minimal polynomialsi So we can write 1 71 91h1 for some Consider the code polynomial 01 b191 for some polynomial 121 of degree less than mi If we multiply 01 by h1 we get that CIh1 5I9Ih1 WWI 1 It is easy to recognize multiples of 1 7 1 by lowdegree polynomials and that gives us an easily checkable necessary and suf cient condition for 01 to be a code polynomial De nition 211 The polynomial h1 is called the check polynomial of BCHUc7 t Proposition 212 Let 01 be a polynomial of degree less that n Then 01 is a code polynomial of BCHkt if and only if1 7 1 divides proof We have already seen that if 01 is a code word7 then 01h1 is a multiple of 1 7 1 Example 213 BCH43 The check polynomial of BCH43 is 1514121 Multiplicative Decoding for BCHkt We can use the check polynomial to provide a multiplicative decoder for our code It incorporates a check for the correct ness of the received word7 but it does no error processing It is based on a simple observationi If 121 has degree less than n7 then 121 1 71 b11 7 121 so if we multiply a code polynomial 01 b191 by h17 the rst m coef cients will be the coef cients of Example214lfthecodewordcis110001001101011then cxhr10111000000000010111 so the message word I is 10111 3 BCH Error Correction Determining the error word Assume that we are using a code BCHkt of block length n 2k 7 1 which is designed to correct errors at most ti Suppose that a code word 5 is sent and the word d is received By using the check matrix if V16th a 0 we can say that d is not a code word We have the following proposition for the linear codes Proposition 31 Let C be a linear code with a check matrix Hi Suppose that a code word 5 is transmitted and the word d c e is received then the syndromes of e and d are equal iei HdT He proof HdT HGT HeT HeT Since HGT 0 Let the error word be e d 7 c then we have that VICth ngeT If s S t errors occurred then from Proposition 119 there is exactly one possible error word 6 of weight at most t which satis es V1th VMeT The error word 6 determines a set of columns of V16 whose sum is ngeTi If there is only one error we have a Hamming code and the search is easy since we just check the n columns of V1 to nd which one gives the syndrome Vkthi However if t gt 1 we have to consider lt9 g lt9 If k 8 and t 3 this number is 2763775 so we need to nd an ef cient procedurei Let c 0771111 0100 be the code word that is sent d dn71 M d1 do be the received word 6 enL1 in 6160 be the error where ei 7 di cit De nition 32 If the component 6 of the error word 6 is not 0 i is called error location of di Let M be the set of error locations then M has 8 S t elements and s is the weight of 6 Example 33 Let 5110110010100001 d110000010100001 e000110000000000 then s 2 and the error locations are 10 and 111 The Syndromes of a Received Word Consider the check matrix V1 then the full syndrome of V16 is a word of length 2t with the entries 51 52 m 52 The corresponding polynomials to the words above are 61 11447113 4711147110 17151 d1 11411317151 61 111 110 The rows of V16 are of the form aq 2j M 12 aj 10 where q 2k 1 is the primitive element of GF2k and j 2t M 1 Thus 239 7th entry 539 can be written as n71 S Zdjaij dw 13971 De nition 34 The values Si dai i 12 M 2t are called the syndromes of The word 116th 31 52 M 52 is called the full syndrome or the syndrome vector Proposition 35 a If 61 is a code polynomial d1 is a polynomial of degree at most 2k 7 2 and 61 d1 7 61 then the syndromes 539 of d1 and 61 are identical for i 12 M 2t b The syndrome 321 512 for i 12 t C d1 is a code polynomial of BCHkt if and only if syndromes 51 52 M SQ are all 0 proof I 7171 7171 7171 5 Zdjaw Edga j Z dja j S2 j0 j0 j0 Example 36 Syndromes of 61 114 113 111 110 17 15 1 51 62 0 5393 68 055 611 0 Syndromes of d1 114 113 17 15 1 51 d2 7 SS d8 955 d11 1 Syndromes of 61 111 110 5391 62 7 5393 68 9 S5 611 1 Now we consider the case 8 2 Assume that there are precisely two errors Test whether the syndromes form a column of the check matrix V1 If they do the column gives the error locations Let M ij be the error locations then we have to solve ai aj 5391 12139 a2j 5392 13139 13139 53 Example 37 BCH43 ai aj 7 12139 an 12 13139 13139 9 then I I a217a115 0 a 10 210 a 13 211 so 10 and 11 are the error locations then M 1011 The Syndrome Polynomial De nition 38 The syndrome polynomial of the word d with syndromes 51 521 SQ is the polynomial 2t71 52 51 522 521122 4 Z Silzi i0 The syndrome polynomial of dz E BCH43 is 32 1425 24 623 922 122 7 Since n71 n71 7 V ij 7 V if 517 E 6101 7 E dja j0 j0 32 can be rewritten as 271 271 32 E 521121 E 6111 E 1112Z i0 jeM i0 Let L 112 then the inner sum can be written as 2t71 Zaijzi 71qq2w42H i0 1742 174 Formula Syndrome Polynomial Proposition 39 The syndrome polynomial 32 can be written as v 17 ozj22 Ejaj 32 2 gau 7 16M 12 17aj2 jEM jEM eja2t1j22t 1 7 aj 2 where M is the set of error locationsi Example 310 By using this formula the syndrome polynomial sz of dz is 210 211 27025 27725 7 7 5 4 3 2 3zgtmm m mm 2 62 92 122 Introduction to Fundamental Equation By adding fractions the syndrome polynomial can be expressed as difference 32 7 u222 2 2 It is clear that 2 1 7 112 GM The roots of 2 are the inverses of the powers Ozj j 6 Mi So 2 can used to determine the error locations 2 is called the error locater polynomial of However nding 2 is still a problem since we assumed that the error polynomial 61 is known Example 311 The error locations of dz are 10 and 11 so that the error locator is 12 17 210217 2112 171021132 1522 72 1 Proposition 312 The polynomials and satisfy the following formulas Z Ejaj H 17 aiz jeM ieMi j Z Ejaa ll H l 7 aiz jeM ieMJ 39 proof From the de nition Z Ejaj ejajl2 ejaj HjeM 1 O jz 39 i V wzZiZ Zejaj H 1702 2 jeM 1 7 0 12 jeM 1 7 0 12 jeM 1 7 0 12 jeM ieMij Example 313 With the error locations 10 and 117 222 2101 2112 2111 2102 101 132 131 102 7 222 27 1 132 2771 2102 14 122 Once we know the error locator 2 and hence error locations7 can be used to calculate the error values It is called the error evaluator The polynomial can also be used to determine the error values and it is called the error co evaluator ln practice7 is used The Fundamental Equation The equation 282 uz22 obtained from 2 32 12 12 is called the fundamental equation for BCH codes Example 314 By using the calculated polynomials 2 and we see that the fundamental equation is 232 uz22t 1227 1425 71227 1425 Proposition 315 If 8 errors occurred in the received word dz7 then the degrees of the error locator7 error evaluator7 error co evaluator satisfy degltzlt2gtgt s deguz lt s degltwlt2gtgt lt 3 Moreover 0 1 Now we present an ef cient algorithm invented by Sugiyama in 1975 It is based on the Euclid s algorithm the knowledge of the error locator enables us to calculate is roots and thus to nd the error locations and correct the received word The key to the solution of this problem is the fundamental equation 282 uz22 BCH Algorithm with Example BCH473 The algorithm that we will use is based on the fact that all the polynomials that that we are looking for appear in the table produced when Euclid s algorithm applied to 22 and Step 1 Calculate Sl dai for i 13 M 2t 71 and nd 521 512 for i 12 t Then calculate the syndrome polynomial 2t 32 ESQ121 2391 1f 32 0 then STOP The received word has no errors We found that syndrome polynomial of dz is 32 1425 24 623 922 122 7 Step 2 Apply Euclid s algorithm to a2 22 and 122 Finish at the stage where the reminder Tj has degree less that t We can use the notation Tj w2 u 2 vj l 2 Applying Euclidls algorithm to 22 and 32 1425 24 623 922 122 7 we nd that T22 5 w 2 1122 22 10 u2 1122 1422 52 4 l2 Step 3 1f Tj 0 there are more than t errors so STOP Otherwise put l2 vj This differs from 2 only by a nonzero constant factor nd the roots 6152 Theorem 316 Denote the polynomials calculated by the BCH algorithm by l2 u 2 w 2 and true error locator evaluator polynomials 2 102 1f 3 S t errors occurred then there exists a nonzero constant K such that l2 K 2 w2 K u2 K Since l 2 differs from 2 by a constant factor they have same roots For our example l2 1422 52 4 41522 72 1 w 2 5 4 7 u2 22 10 4122 14 Now consider l 2 1422 52 4 Since 4 92 59 4 0 9 is a root of l2 and since 2 7 9 142 7 6 l 2 the roots of l2 are 9 and 61411 Step 4 1fthe roots of l are 117 then the errors occurred at the place 2k 7pi71 counting from the right starting from 0 9 24 and 11 25 so that the error locations are 164110 and 165110 Termination of the Algorithm Proposition 317 Assume that l lt s S t errors occurred7 then the step 2 of the algorithm Will end With a nonzero Tj such that deg39rj lt t and deg7 j1z 2 ti proof From the fundamental equation 232 uzz2 the greatest common divisor sz22 of 32 and 22 divides so that degsz722 S degwz lt 8 St Also degz2 2t gt t Since the Euclid s algorithm terminates With sz22 2 there exists a j such that deg39rjz lt t and degTj1z 2 ti
Are you sure you want to buy this material for
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'