[ Pobierz całość w formacie PDF ]
.26.Let H be an m × n matrix over Z2, where the ith column is the number iwritten in binary with m bits.The null space of such a matrix is called aHamming code.(a) Show that the matrix111 H =111111136CHAPTER 7ALGEBRAIC CODING THEORYgenerates a Hamming code.What are the error-correcting propertiesof a Hamming code?(b) The column corresponding to the syndrome also marks the bit thatwas in error; that is, the ith column of the matrix is i written as abinary number, and the syndrome immediately tells us which bit is inerror.If the received word is (101011), compute the syndrome.In whichbit did the error occur in this case, and what codeword was originallytransmitted?(c) Give a binary matrix H for the Hamming code with six informationpositions and four check positions.What are the check positions andwhat are the information positions? Encode the messages (101101) and(001001).Decode the received words (0010000101) and (0000101100).What are the possible syndromes for this code?(d) What is the number of check bits and the number of information bitsin an (m, n)-block Hamming code? Give both an upper and a lowerbound on the number of information bits in terms of the number ofcheck bits.Hamming codes having the maximum possible number ofinformation bits with k check bits are called perfect.Every possiblesyndrome except 0 occurs as a column.If the number of informationbits is less than the maximum, then the code is called shortened.Inthis case, give an example showing that some syndromes can representmultiple errors.Programming ExercisesWrite a program to implement a (16, 12)-linear code.Your program should beable to encode and decode messages using coset decoding.Once your program iswritten, write a program to simulate a binary symmetric channel with transmissionnoise.Compare the results of your simulation with the theoretically predicted errorprobability.References and Suggested Readings[1] Blake, I.F.“Codes and Designs,” Mathematics Magazine 52 (1979), 81–95.[2] Hill, R.A First Course in Coding Theory.Oxford University Press, Oxford,1986.[3] Levinson, N.“Coding Theory: A Counterexample to G.H.Hardy’s Concep-tion of Applied Mathematics,” American Mathematical Monthly 77 (1970),249–58.[4] Lidl, R.and Pilz, G.Applied Abstract Algebra.Springer-Verlag, New York,1984.EXERCISES137[5] MacWilliams, F.J.and Sloane, N.J.A.The Theory of Error-CorrectingCodes.North Holland, Amsterdam, 1977.[6] Roman, S.Coding and Information Theory.Springer-Verlag, New York,1992.[7] Shannon, C.E.“A Mathematical Theory of Communication,” Bell SystemTechnical Journal 27 (1948), 379–423, 623–56.[8] Thompson, T.M.From Error-Correcting Codes through Sphere Packing toSimple Groups.Carus Monograph Series, No.21.Mathematical Associationof America, Washington, DC, 1983.[9] van Lint, J.H.Introduction to Coding Theory.Springer-Verlag, New York,1982.8IsomorphismsMany groups may appear to be different at first glance, but can be shownto be the same by a simple renaming of the group elements.For example,Z4 and the subgroup of the circle group T generated by i can be shownto be the same by demonstrating a one-to-one correspondence between theelements of the two groups and between the group operations.In such acase we say that the groups are isomorphic.8.1Definition and ExamplesTwo groups (G, ·) and (H, ◦) are isomorphic if there exists a one-to-oneand onto map φ : G → H such that the group operation is preserved; that is,φ(a · b) = φ(a) ◦ φ(b)for all a and b in G.If G is isomorphic to H, we write G ∼= H.The map φis called an isomorphism.Example 1.To show that∼Z4 = hii, define a map φ : Z4 → hii by φ(n) = in.We must show that φ is bijective and preserves the group operation.Themap φ is one-to-one and onto becauseφ(0)=1φ(1)=iφ(2)=−1φ(3)=−i.Sinceφ(m + n) = im+n = imin = φ(m)φ(n),1388.1DEFINITION AND EXAMPLES139the group operation is preserved.Example 2.We can define an isomorphism φ from the additive group ofreal numbers (R, +) to the multiplicative group of positive real numbers( +R , ·) with the exponential map; that is,φ(x + y) = ex+y = exey = φ(x)φ(y).Of course, we must still show that φ is one-to-one and onto, but this can bedetermined using calculus.Example 3.The integers are isomorphic to the subgroup of∗Q consistingof elements of the form 2n.Define a map φ :∗Z → Q by φ(n) = 2n.Thenφ(m + n) = 2m+n = 2m2n = φ(m)φ(n).By definition the map φ is onto the subset {2n : n ∈∗Z} of Q.To show thatthe map is injective, assume that m 6= n.If we can show that φ(m) 6= φ(n),then we are done.Suppose that m > n and assume that φ(m) = φ(n).Then2m = 2n or 2m−n = 1, which is impossible since m − n > 0.Example 4.The groups Z8 and Z12 cannot be isomorphic since they havedifferent orders; however, it is true that U (8) ∼= U (12).We know thatU (8)={1, 3, 5, 7}U (12)={1, 5, 7, 11}.An isomorphism φ : U (8) → U (12) is then given by17→ 137→ 557→ 777→ 11.The map φ is not the only possible isomorphism between these two groups.We could define another isomorphism ψ by ψ(1) = 1, ψ(3) = 11, ψ(5) = 5,ψ(7) = 7.In fact, both of these groups are isomorphic to Z2 × Z2 (seeExample 14 in Chapter 2).Example 5.Even though S3 and Z6 possess the same number of elements,we would suspect that they are not isomorphic, because Z6 is abelian andS3 is nonabelian.To demonstrate that this is indeed the case, suppose thatφ : Z6 → S3 is an isomorphism.Let a, b ∈ S3 be two elements such that140CHAPTER 8ISOMORPHISMSab 6= ba [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl centka.pev.pl
.26.Let H be an m × n matrix over Z2, where the ith column is the number iwritten in binary with m bits.The null space of such a matrix is called aHamming code.(a) Show that the matrix111 H =111111136CHAPTER 7ALGEBRAIC CODING THEORYgenerates a Hamming code.What are the error-correcting propertiesof a Hamming code?(b) The column corresponding to the syndrome also marks the bit thatwas in error; that is, the ith column of the matrix is i written as abinary number, and the syndrome immediately tells us which bit is inerror.If the received word is (101011), compute the syndrome.In whichbit did the error occur in this case, and what codeword was originallytransmitted?(c) Give a binary matrix H for the Hamming code with six informationpositions and four check positions.What are the check positions andwhat are the information positions? Encode the messages (101101) and(001001).Decode the received words (0010000101) and (0000101100).What are the possible syndromes for this code?(d) What is the number of check bits and the number of information bitsin an (m, n)-block Hamming code? Give both an upper and a lowerbound on the number of information bits in terms of the number ofcheck bits.Hamming codes having the maximum possible number ofinformation bits with k check bits are called perfect.Every possiblesyndrome except 0 occurs as a column.If the number of informationbits is less than the maximum, then the code is called shortened.Inthis case, give an example showing that some syndromes can representmultiple errors.Programming ExercisesWrite a program to implement a (16, 12)-linear code.Your program should beable to encode and decode messages using coset decoding.Once your program iswritten, write a program to simulate a binary symmetric channel with transmissionnoise.Compare the results of your simulation with the theoretically predicted errorprobability.References and Suggested Readings[1] Blake, I.F.“Codes and Designs,” Mathematics Magazine 52 (1979), 81–95.[2] Hill, R.A First Course in Coding Theory.Oxford University Press, Oxford,1986.[3] Levinson, N.“Coding Theory: A Counterexample to G.H.Hardy’s Concep-tion of Applied Mathematics,” American Mathematical Monthly 77 (1970),249–58.[4] Lidl, R.and Pilz, G.Applied Abstract Algebra.Springer-Verlag, New York,1984.EXERCISES137[5] MacWilliams, F.J.and Sloane, N.J.A.The Theory of Error-CorrectingCodes.North Holland, Amsterdam, 1977.[6] Roman, S.Coding and Information Theory.Springer-Verlag, New York,1992.[7] Shannon, C.E.“A Mathematical Theory of Communication,” Bell SystemTechnical Journal 27 (1948), 379–423, 623–56.[8] Thompson, T.M.From Error-Correcting Codes through Sphere Packing toSimple Groups.Carus Monograph Series, No.21.Mathematical Associationof America, Washington, DC, 1983.[9] van Lint, J.H.Introduction to Coding Theory.Springer-Verlag, New York,1982.8IsomorphismsMany groups may appear to be different at first glance, but can be shownto be the same by a simple renaming of the group elements.For example,Z4 and the subgroup of the circle group T generated by i can be shownto be the same by demonstrating a one-to-one correspondence between theelements of the two groups and between the group operations.In such acase we say that the groups are isomorphic.8.1Definition and ExamplesTwo groups (G, ·) and (H, ◦) are isomorphic if there exists a one-to-oneand onto map φ : G → H such that the group operation is preserved; that is,φ(a · b) = φ(a) ◦ φ(b)for all a and b in G.If G is isomorphic to H, we write G ∼= H.The map φis called an isomorphism.Example 1.To show that∼Z4 = hii, define a map φ : Z4 → hii by φ(n) = in.We must show that φ is bijective and preserves the group operation.Themap φ is one-to-one and onto becauseφ(0)=1φ(1)=iφ(2)=−1φ(3)=−i.Sinceφ(m + n) = im+n = imin = φ(m)φ(n),1388.1DEFINITION AND EXAMPLES139the group operation is preserved.Example 2.We can define an isomorphism φ from the additive group ofreal numbers (R, +) to the multiplicative group of positive real numbers( +R , ·) with the exponential map; that is,φ(x + y) = ex+y = exey = φ(x)φ(y).Of course, we must still show that φ is one-to-one and onto, but this can bedetermined using calculus.Example 3.The integers are isomorphic to the subgroup of∗Q consistingof elements of the form 2n.Define a map φ :∗Z → Q by φ(n) = 2n.Thenφ(m + n) = 2m+n = 2m2n = φ(m)φ(n).By definition the map φ is onto the subset {2n : n ∈∗Z} of Q.To show thatthe map is injective, assume that m 6= n.If we can show that φ(m) 6= φ(n),then we are done.Suppose that m > n and assume that φ(m) = φ(n).Then2m = 2n or 2m−n = 1, which is impossible since m − n > 0.Example 4.The groups Z8 and Z12 cannot be isomorphic since they havedifferent orders; however, it is true that U (8) ∼= U (12).We know thatU (8)={1, 3, 5, 7}U (12)={1, 5, 7, 11}.An isomorphism φ : U (8) → U (12) is then given by17→ 137→ 557→ 777→ 11.The map φ is not the only possible isomorphism between these two groups.We could define another isomorphism ψ by ψ(1) = 1, ψ(3) = 11, ψ(5) = 5,ψ(7) = 7.In fact, both of these groups are isomorphic to Z2 × Z2 (seeExample 14 in Chapter 2).Example 5.Even though S3 and Z6 possess the same number of elements,we would suspect that they are not isomorphic, because Z6 is abelian andS3 is nonabelian.To demonstrate that this is indeed the case, suppose thatφ : Z6 → S3 is an isomorphism.Let a, b ∈ S3 be two elements such that140CHAPTER 8ISOMORPHISMSab 6= ba [ Pobierz całość w formacie PDF ]