Solution Manual- Coding Theory by Hoffman et al.

1 0 0 0 1 1 0 Therefore G = 0 1 0 0 0 1 1 and hence B = {1000110, 0100011, 0010111, 0001101}. 0 0 1 0 1 1 1 0001101 1 1 0  1 1 0 0 1 1  Now X = 0 1 1 and hence H = 1 1 1 0  1 1 1 1 0 11 0. 101 0 1 0   00 1 Thus B⊥ = {1011100, 1110010, 0111001}. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (c) S = {1111000, 0111100, 0011110, 0001111, 1000111, 1100011, 1110001} 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 −−−−−−−−−−−−→ 0 0 1 0 0 0 1 A = 0 0 0 1 1 1 1 using RREF steps 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1110001 0000000 . 1 0 0 0 0 0 1 0 1 0 0 0 0 1 Therefore G = 0 0 1 0 0 0 1 and hence B = {1000001, 0100001, 0010001, 0001001, 0000101, 000 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0000011 Now X = 1 and hence H = 1 1 1 1 1 1 1. 1 1 1 1 1 Thus B⊥ = {1111111}. (d) S = {101101110, 011011101, 110110010, 011011110, 111111101}. 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 −−−−−−−−−−−−−→ 0 1 0 0 1 0 0 0 0 A = 1 1 0 1 1 0 0 1 0 using RREF steps 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 111111101 000000000 50

1 0 0 1 0 0 0 0 0 Therefore G = 0 1 0 0 1 0 0 0 0 and hence B = {100100000, 010010000, 001001101, 0000000 0 0 1 0 0 1 1 0 1 000000011 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 Now X = 0 0 1 1 0 and hence H = 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0. Thus B⊥ = {100100000, 010010000, 001001 0 0 0 1 0 0 1 0 0 0 0 0 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 00001 2.6 Generating Matrices and Encoding 2.6.4 Determine whether each of the following is a generator matrix for some linear code. A = 0 1 0 0 1 1 1 0 1 and B = 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 A matrix is a generator matrix for some linear code if and only if the rows of the matrix are linearly independent. Now 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 A = 1 0 0 1 0 1 1 0 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 101101101 000001011 Therefore the rows of A are linearly independent and hence A is a generator matrix for some linear code. Now 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 1 0 0 1 0 1 1 0 0 B = 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1010001110 0000000000 The rows of B are not linearly independent and hence B is not a generator matrix of any linear code. 2.6.5 Find a generator matrix in RREF for each of the following codes. 51

(a) C = {000, 001, 010, 011} 0 0 0 0 1 0 A = 0 0 1 −−−−−−−−−−−−→ 0 0 1 0 1 0 using RREF steps 0 0 0 011 000 . 0 1 0 0 0 1 Therefore G = is a generator matrix for C. (b) C = {0000, 1001, 0110, 1111} GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur0 0 0 0 1 0 0 1 A = 1 0 0 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 1 1 0 0 1 1 0 0 0 0 0 1111 0000 Therefore G = 1 0 0 1 is a generator matrix for C. 0 1 1 0 (c) C = {00000, 11111} A= 0 0 0 0 0 −−−−−−−−−−−→ 1 1 1 1 1 1 1 1 1 1 using REF steps 0 0 0 0 0 Therefore G = 1 1 1 1 1 is a generator matrix for C. (d) C = {00000, 11100, 00111, 11011}. 0 0 0 0 0 1 1 1 0 0 A = 1 1 1 0 0 u−−si−n−g−−R−E−F−s−t−e→ps 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 11011 00000 Therefore G = 1 1 1 0 0 is a generator matrix for C. 0 0 1 1 1 (e) C = {00000, 11110, 01111, 10001}. 0 0 0 0 0 1 1 1 1 0 A = 1 1 1 1 0 −u−si−n−g−−R−E−F−s−t−e→ps 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 11011 00000 Therefore G = 1 1 1 1 0 is a generator matrix for C. 0 1 1 1 1 52

(f ) C = {000000, 101010, 010101, 111111} 0 0 0 0 0 0 1 0 1 0 1 0 A = 1 0 1 0 1 0 −−−−−−−−−−−→ 0 1 0 1 0 1 0 1 0 1 0 1 using REF steps 0 0 0 0 0 0 111111 000000 Therefore G = 1 0 1 0 1 0 is a generator matrix for C. 0 1 0 1 0 1 2.6.6 Find a generator matrix for each of the following codes. Give the dimension of the code. (a) C = {000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000}. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 A = 0 1 1 1 1 0 −u−si−n−g−−R−E−F−s−t−e→ps 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 111000 000000 . 1 0 1 1 0 1 Therefore G = 0 1 0 1 0 1 and dimenstion is 3. 001011 (b) C = {00000000, 01101111, 11011000, 11111101, 10010010, 00100101, 01001010, 10110111} 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 A = 1 1 1 1 1 1 0 1 −u−si−n−g−−R−E−F−s−t−e→ps 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 10110111 00000000 . 1 0 0 1 0 0 1 0 Therefore the generator matrix is G = 0 1 1 0 1 1 1 1 and dimenstion is e 3. 00100101 (c) C = {0000000000, 1111100000, 0000011111, 1111111111}. 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 A = 1 1 1 1 1 0 0 0 0 0 u−−si−n−g−−R−E−F−s−t−e→ps 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1111111111 0000000000 53

Therefore the generator matrix is G = 1 1 1 1 1 0 0 0 0 0 and dimenstion is 2. 0 0 0 0 0 1 1 1 1 1 2.6.7 Find a generator matrix for the linear code generated by each of the following sets. Give the parameters (n, k, d) for each code. (a) S = {11111111, 11110000, 11001100, 10101010}. 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 A = 1 1 1 1 0 0 0 0 −−−−−−−−−−−−→ 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 using RREF steps 0 0 1 1 0 0 1 1 10101010 00001111 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1 0 0 1 0 1 1 0 Therefore G = 0 1 0 1 0 1 0 1 is a generator matrix for C =< S >. 0 0 1 1 0 0 1 1 00001111 Hence (n, k, d) = (8, 4, 4). (b) S = {11111100, 11110011, 11001111, 00111111} 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 A = 1 1 1 1 0 0 1 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 00111111 00000011 1 1 0 0 1 1 1 1 Therefore G = 0 0 1 1 1 1 0 0 is a generator matrix for C =< S >. 0 0 0 0 1 1 1 1 00000011 Hence (n, k, d) = (8, 4, 2). 2.6.10 For each of the following generating matrices, encode the given messages. 1 0 0 1 1 (a) G = 0 1 0 1 0. 00101 (i)u = 100 v = uG = 10011. (ii)u = 010 v = uG = 01010. (iii)u = 111 v = uG = 11100. 1 0 0 0 1 1 1 (b)G = 0 1 0 0 1 0 1 0010011 54

(i)u = 000 v = uG = 0000000. (ii)u = 100 v = uG = 1000111. (iii)u = 111 v = uG = 1110001. 1 1 0 1 0 0 1 (c)G = 0 0 1 0 1 1 01. 0 1 0 1 0 1 1111111 (i)u = 1000 v = uG = 1101001. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (ii)u = 1010 v = uG = 1000011. (iii)u = 0011 v = uG = 1010101. (iv)u = 1011 v = uG = 0111100. 2.6.11 Assign messages to the words in K3 as follows: 000 100 010 001 110 101 011 111 . A B E H M R T W Using the generator matrix in Example2.6.9, encode the message BE THERE(Ignore the space). 1 0 1 1 0 The generator matrix in Example 2.6.9 is G = 0 1 0 1 1. 00101 Now each letter is encoded as follows: T A B E H M R 01110 W 00000 10110 01011 00101 11101 10011 11000 . Therefore the message BE THERE is encoded as 10110010110111000101010111001101011. 1 0 0 0 1 1 1 2.6.12 Let C be the code with generator matrix G = 0 1 0 0 1 1 01. 0 0 1 0 1 0 0001011 Assign messages to the words in K4 as follows: 0000 1000 0100 0010 0001 1100 1010 1001 ABCDE F GH 0110 0101 0011 1110 1101 1011 0111 1111 I J K LMN O P (a) Encode the message HELP. EH L P 0001011 1001100 1110100 1111111 and hence the message HELP is encoded as 1001100000101111101001111111. 55

(b) Transmit the message HELP assuming that during transmission the first word receives an error in the first position, the second word receives no errors, the third an error in the seventh position, and the fourth an error in the fifth and sixth positions. The message is transmitted as 0001100000101111101011111001. (c) Encode the message CALL HOME BAMA (Ignore the spaces.). AB C EH LMO 0000000 1000111 0100110 0001001 1001100 1110100 1101010 0111000 and hence CALL HOME BAMA is encoded as 010011000000001110100111010010011000111000110101000010011000111 000000011010100000000. 2.6.13 Find the number of messages which can be sent, and the information rate r,for each of the linear codes in Exercises 2.6.6 and 2.6.7. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (a) C = {000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000}. | C |= 8, r = dimC = 1 . n 2 (b) C = {00000000, 01101111, 11011000, 11111101, 10010010, 00100101, 01001010, 10110111} | C |= 8, r = 3 . 8 (c) C = {0000000000, 1111100000, 0000011111, 1111111111}. | C |= 4, r = 1 . 5 (d) C =< S >, S = {11111111, 11110000, 11001100, 10101010}. | C |= 16, r = 1 . 2 (e) C =< S >, S = {11111100, 11110011, 11001111, 00111111} | C |= 16, r = 1 . 2 (f ) C =< S >, S = {100100100, 010010010, 001001001, 111111111} | C |= 8, r = 1 . 3 (g)C =< S >, S = {10101, 01010, 11111, 00011, 10110} | C |= 8, r = 3 . 5 (h)C =< S >, S = {1010, 0101, 1111} | C |= 4, r = 1 . 2 (i)C =< S >, S = {101101, 011010, 110111, 000111, 110000} | C |= 8, r = 1 . 2 (j)C =< S >, S = {1001011, 0101010, 1001100, 0011001, 0000111} | C |= 16, r = 4 . 7 2.7 Parity-Check Matrices 2.7.4 Find a parity check matrix for each of the following codes. (a) C = {000, 001, 010, 011} If a generator matrix G has the form G = [I, X], then a parity check matrix is H = X . I 56

Now 0 0 0 0 1 0 A = 0 0 1 −−−−−−−−−−−−→ 0 0 1 0 1 0 using RREF steps 0 0 0 011 000 . 1 and hence H = 0. Therefore G = 0 1 0 0 0 1 0 (b) C = {0000, 1001, 0110, 1111} 0 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur G= 1 0 0 1 and hence H = 1 00. 0 1 1 0 1 01 (c) C = {00000, 11111} 1 1 1 1 1 0 0 0 G = 1 1 1 1 1 and hence H = 0 1 0 0. 0 0 1 0 0001 (d) C = {00000, 11100, 00111, 110011} 1 1 1 G= 1 1 0 1 1 1 0 0 0 0 1 1 1 1 and hence H = 0 1 1. 0 0 001 (e) C = {00000, 11110, 01111, 10001} 0 0 1 G= 1 0 0 0 1 1 1 1 0 1 1 1 1 0 and hence H = 1 1 0. 0 0 001 (f ) C = {000000, 101010, 010101, 111111} 1 0 1 0 0 1 0 1 G= 1 0 1 0 1 0 and hence H = 1 0 0 00. 0 1 0 1 0 1 0 1 0 0 0 1 0 0001 2.7.5 Find a parity check matrix for each of the following codes (the generating matrices were con- structed in exercises 2.6.6 and 2.6.7). (a) C = {000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000}. 57

1 1 1 1 0 0 1 1 1 and hence H = 1 0 1 G = 0 1 0 1 0 1 0 1 01. 0 1 0 1 1 1 0 0 0 0 1 001 (b)C = {00000000, 01101111, 11011000, 11111101, 10010010, 00100101, 01001010, 10110111} 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 G = 0 1 1 0 1 1 1 1 1 0 0 0 00. 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturandhenceH= 0 0 0 1 0 0000 (c) C = {0000000000, 1111100000, 0000011111, 1111111111}. 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 G= 1 1 1 1 1 0 0 0 0 0 and hence H = 0 0 0 1 0 0 0 10. 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 00000001 (d) C =< S >, S = {11111111, 11110000, 11001100, 10101010}. 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 G = 0 1 0 1 0 1 0 1 and hence H = 1 0 0 01. 0 0 1 1 0 0 1 1 0 1 1 00001111 0 1 0 0 0 0 1 0 0001 (e) C =< S >, S = {11111100, 11110011, 11001111, 00111111} 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 G = 0 0 1 1 1 1 0 0 and hence H = 0 1 0 00. 0 0 0 0 1 1 1 1 0 0 1 00000011 0 0 1 0 0 0 0 1 0001 58

(f ) C =< S >, S = {100100100, 010010010, 001001001, 111111111}. 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 G = 0 1 0 0 1 0 0 1 0 and hence H = 0 1 0 0 0 0 001001001 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 000001 (g) C =< S >, S = {10101, 01010, 11111, 00011, 10110}. 1 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1 0 1 0 1 0 1 G = 0 1 0 1 0 and hence H = 1 0. 00011 0 1 01 (h) C =< S >, S = {1010, 0101, 1111}. 1 0 G= 1 0 1 0 and hence H = 0 01. 0 1 0 1 1 01 (i) C =< S >, S = {101101, 011010, 110111, 000111, 110000}. 1 1 0 1 0 1 0 1 0 and hence H = 1 1 0 G = 0 1 1 0 1 0 1 0 10. 0 0 1 1 1 0 1 0 0 0 1 001 (j) C =< S >, S = {1001011, 0101010, 1001100, 0011001, 0000111}. 1 0 0 1 0 1 1 G = 0 1 0 1 0 1 01. 0 0 1 1 0 0 0000111 2.7.9 In each part, a parity check matrix for a linear code C is given. Find (i) a generator matrix for C⊥; (ii) a generator matrix for C. 1 0 0 1 0 0 (a)H = 0 1 0 0 0 1 0 1 0 001 1 1 0 0 0 0 Given HC = H. Then GC⊥ = HCT . Therefore GC⊥ = 0 0 1 0 1 0. 000101 59

Also H = X implies GC = [I, X]. I 1 0 0 1 0 0 Therefore G = 0 1 0 0 1 0. 001001 0 1 1 0 (b) H = 0 1 1 0 01 GC⊥ = 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 and GC = 0 1 0 1 0. 0 1 0 1 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1 1 1 1 1 0 1 0 1 (c) H = 0 1 1 1 0 0 0 1 0 001 1 1 1 0 1 0 0 and GC = 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 10. GC⊥ = 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 2.7.10 List all the words in the dual code C⊥ for the code C = {00000, 11111}. Then find generating and parity check matrices for C. C⊥ = {v ∈ K5|v.11111 = 00000}. If v = abcde, then v.11111 = 00000 implies a + b + c + d + e = 0. Therefore C⊥ consists of all words in K5 of even weight. Hence C⊥ = {00000, 11000, 10100, 10010, 10001, 01001, 00101, 00011, 01100, 00110, 01010, 11110, 11101, 11011, 10111, 01111}. 1 1 1 1 1 0 0 0 Now GC⊥ = HCT . Since GC = 1 1 1 1 1 , HC = 0 1 0 0. 0 0 1 0 0001 1 1 0 0 0 0 0 1 0 Therefore GC⊥ = 1 0 0 1 0 and hence HC⊥ = 0 1 0 0 0 0 0. 1 1 1 1 2.7.11 For each code described below, find the dimension of C, the dimension of C⊥, the size of the generating and parity check matrices for C and C⊥, the number of words in C and in C⊥, and the information rates r of C and C⊥. 60

(a) C has length n = 2t − 1 and dimension t. dim(C) = t, dim(C⊥) = n − t = 2t − 1 − t, size of GC = t × (2t − 1), size of HC = (2t − 1) × (2t − 1 − t), size of GC⊥ = (2t − 1 − t) × (2t − 1), size of HC⊥ = (2t − 1) × t, 22t−1−t, .2t−1−t |C | = 2t, |C⊥| = RC = 2t t , RC ⊥ = 2t−1 −1 (b) C has length n = 23 and dimension 11. dim(C) = 11, dim(C⊥) = 12, size of GC = 11 × 23, size of HC = 23 × 12, size of GC⊥ = 12 × 23, size of HC⊥ = 23 × 11, |C | = 211 = 2048, |C⊥| = 212 = 4096, RC = 11 , RC ⊥ = 12 . 23 23 (c) C has length n = 15 and dimension 7. dim(C) = 7, dim(C⊥) = 8, GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur size of GC = 7 × 15, size of HC = 15 × 8, size of GC⊥ = 8 × 15, size of HC⊥ = 15 × 7, |C | = 27 = 128, |C⊥| = 28 = 256, RC = 7 , RC ⊥ = 8 . 15 15 2.8 Equivalent codes 2.8.4 Let G be the generator matrix in Example 2.8.3. Encode each of the following messages u, and observe that the first 4 digits in the resulting codeword form the message u. 1 0 0 0 1 0 1 G = 0 1 0 0 1 0 00. 0 0 1 0 1 1 0001011 (a) u = 1111 uG = 1111100 (b) u = 1011 uG = 1011000 (c) u = 0000 uG = 0000000 2.8.5 Explain a method for recovering u from uG if G is not in standard form. 1 1 0 0 1 0 1 0 1 1 0 1 0 1 2.8.6 If a linear code C has generator matrix G = 1 0 1 1 0 1 1, recover u from v = uG = 1 1 0 0 1 1 0 0110000 0000101. 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 1 1 0 0 0 0 G = 1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0110000 0000011 61

. Now let u = abcde. Then uG = 0000101 implies 1 0 1 0 0 0 0 0 1 1 0 0 0 0 a b c d e 0 0 0 1 0 0 0 = 0000101 0 0 0 0 1 0 1 0000011 =⇒ a = b = 0 a+b=0 c=0 d=1 e=0 =⇒ u = 00010 2.8.10 Find a systematic code C equivalent to the given code C. Check that C and C have same length, dimension and distance. (a) C = {00000, 10110, 10101, 00011}. First find the generator matrix of C in RREF form. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0 0 0 0 0 1 0 1 0 1 A = 1 0 1 1 0 u−−si−n−g−R−−R−E−F−s−t−e→ps 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 00011 00000 . 1 0 1 0 1 0 0 0 1 1 Therefore G = . Let 1 0 0 1 1 0 1 0 0 1 G= = [I2, X] . Therefore C = span{10011, 01001} = {00000, 10011, 01001, 11010}. Now length of C= length of C =5. since G and G have sizes 2 × 5, dimC = dimC = 2. Now distance of C= 2 distance of C . (b)C = {00000, 11100, 00111, 11011}. 0 0 0 0 0 1 1 0 1 1 A = 1 1 1 0 0 −−−−−−−−−−−−→ 0 0 1 1 1 0 0 1 1 1 using RREF steps 0 0 0 0 0 11011 00000 62

. 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 Therefore G = and hence G = . Thus C = span{10111, 01011} = {00000, 10111, 01011, 11100}. Now length of C=length of C =5. dimC = dimC = 2 and distance of C= 3 distance of C . 2.8.11 Find a generator matrix G in standard form for a code equivalent to the code with given gen- erator matrix G. If C is any block code of length n, then a block code C formed by rearranging every word in C by choosing a particular permutation of the n digits is said to be equivalent to C. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur1 0 1 0 1 0 (a)10 1 1 0 0 0 1 0 1 0 0 101011 Find RREF of G and obtain a matrix in standard form from it by rearranging the columns. Then the corresponding codes are equivalent. 1 0 1 0 1 0 1 0 1 0 1 0 G = 0 1 1 0 0 0 −−−−−−−−−−−−→ 0 1 1 0 0 0 1 1 0 1 0 0 using RREF steps 0 0 0 1 1 0 101011 000001 . 1 0 0 0 1 1 Then G = 0 1 0 0 1 0 is in standard form and also C and C are equivalent. 0 0 1 0 0 1 000100 1 1 1 0 0 0 0 0 0 (b) G = 0 0 0 1 1 1 0 0 0 000111111 1 1 1 0 0 0 0 0 0 −−−−−−−−−−−−→ 1 1 1 0 0 0 0 0 0 G = 0 0 0 1 1 1 0 0 0 using RREF steps 0 0 0 1 1 1 0 0 0 000111111 000000111 . 1 0 0 1 1 0 0 0 0 Then G = 0 1 0 0 0 1 1 0 0 is in standard form and also C and C are equivalent. 001000011 2.8.12 Find a generator matrix G in standard form for a code C equivalent to a code C with a given parity check matrix H. 1 1 0 1 0 0 (a)H = 0 1 1 0 1 0 001 63

Given H, G = 1 1 0 1 0 . Then G = 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 (b)H = 1 1 0 1 0 1 0 0 1 011 1 1 1 0 0 1 0 1 0 0 0 1 1 1 G = 1 0 1 1 0 0 0 and hence G = 0 1 0 0 1 1 10. 1 0 0 0 1 1 0 0 0 1 0 1 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0010011 0001011 2.8.13 Prove that equivalent linear codes always have the same length, dimension, and distance. If C and C are equivalent codes, then one is obtained from the other by just a permutation of the digits in each codeword. Therefore their lengths remain the same. Since the corresponding generator matrices are also obtained from one another by permuting the corresponding columns, the dimension is also the same. Also permutation of digits doesn’t alter the weight of the codewords and hence C and C have the same weight. 2.8.14 Determine whether each of the following pairs of matrices G1 and G2 generate equivalent codes. 1 1 0 0 1 0 0 1 (a) G1 = 0 1 1 0 , G2 = 0 1 0 1. 0011 0011 G1 and G2 generate equivalent codes if their corresponding RREFs can be obtained from one another by permutation of the columns. 1 1 0 0 −−−−−−−−−−−−→ 1 0 0 1 G1 = 0 1 1 0 using RREF steps 0 1 0 1 0011 0011 G2 is in RREF and the RREF of G1 is G2. Therefore the corresponding codes are equal and hence equivalent. 1 1 0 0 0 0 1 1 1 1 1 1 (b) G1 = 0 0 1 1 0 0 , G2 = 0 1 1 0 1 1 000011 001001 1 1 1 1 1 1 −−−−−−−−−−−−→ 1 0 0 1 0 0 G2 = 0 1 1 0 1 1 using RREF steps 0 1 0 0 1 0 001001 001001 and G1 is in RREF. Now interchanging columns of G2 will give G1. Therefore the corre- sponding codes are equivalent. 64

1 0 0 0 1 1 1 1 0 1 1 0 0 0 (c) G1 = 0 1 0 0 1 1 0 , G2 = 0 1 0 1 1 0 00. 0 0 1 0 1 0 1 0 0 1 0 1 1 0001011 0001011 1 0 1 1 0 0 0 1 0 0 0 1 0 1 G2 = 0 1 0 1 1 0 0 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0001011 0001011 and G1 is in RREF. Neither G1 nor G2 can be obtained from the other by interchanging columns. Therefore the corresponding codes are not equivalent. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.9 Distance of a linear code 2.9.3 Find the code C in the Example 2.9.2. Compute the weight of each codeword and verify that C has distance 3. 1 1 0 0 1 1 1 0 1 1 0 . 0 0 1 0 1 1 Given H = 1 1 0. Then G = 0 0 001 Therefore C = {00000, 10110, 01011, 11101}. Now wt(00000) = 0 wt(10110) = 3 wt(01011) = 3 wt(11101) = 4 =⇒ distance of C = min{wt(v)|0 = v ∈ C} = min{3, 4} = 3. 2.9.4 Find the distance of linear code C with each of the given parity check matrices. Use Theorem 2.9.1 and then check your answer by finding wt(v) for each v in C. Remark 1. If H is a parity check matrix for C, then d is the distance of C if and only if any set of d − 1 rows of H are linearly independent and atleast one set of d rows are linearly dependent. 0 1 1 1 1 1 1 0 (a)H = 1 0 0 0 0 1 0 0 0 0 1 0 0001 We have 1110 + 1000 + 0100 + 0010 = 0000. 65

=⇒ {1110, 1000, 0100, 0010} is linearly dependent. Now any three rows of the matrix H are linearly independent. Hence d = 4. Since G = 1 0 0 1 1 1 ,C = {000000, 100111, 011110, 111001} and therefore distance 0 1 1 1 1 0 of the code is d = minimum of the weights of the nonzero words in C = 4 1 1 1 0 1 1 0 1 1 0 1 1 (b)H = 0 1 1 1 1 0 0 0 0 1 0 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0 0 1 0 0001 1110+1000+0100+0010 = 0000 implies the set {1110, 1000, 0100, 0010} is linearly dependent. Now any three rows of H are linearly independent and hence d = 4. 1 0 0 0 1 1 1 0 Now G = 0 1 0 0 1 1 0 1 and hence 0 0 1 0 1 0 1 1 00010111 C = {00000000, 10001110, 01001101, 00101011, 00010111, 00010111, 11000011, 10100101, 10011001, 01100110, 01011010, 00111100, 11101000, 11010100, 10110010}. Therefore d = 4. 1 1 0 1 1 0 1 1 1 1 1 0 (c)H = 1 0 0 0 0 1 0 0 0 0 1 0 0001 1101+1000+0100+0001 = 0000 implies the set {1101, 1000, 0100, 0001} is linearly dependent. Now any three rows of H are linearly independent and hence d = 4. 1 0 0 1 1 0 1 Now G = 0 1 0 1 0 1 1 and hence 0011110 C = {0000000, 1001101, 0101011, 0011110, 1100110, 0110101, 1010011, 1111000}. Therefore d = 4. 2.9.5 Find by Theorem2.9.1, the distance of the linear code with the given generator matrix. 1 1 1 0 0 0 0 0 0 (a) G = 0 0 0 1 1 1 0 0 0 111111111 1 1 1 0 0 0 0 0 0 RREF of G is 0 0 0 1 1 1 0 0 0. 000000111 66

1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 Therefore H = 0 0 1 0 0 0. 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 000001 Now 110000 + 100000 + 010000 = 000000 implies the set {110000, 100000, 010000} is linearly dependent. Also any two rows of H are linearly independent and hence d = 3. 1 0 0 0 1 1 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (b) G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0001011 1 1 1 1 1 0 1 0 1 Given G, we get H = 0 1 1. 1 0 0 0 1 0 001 Now 110 + 100 + 010 = 000 implies set {110, 100, 010} is linearly dependent. Also any two rows of H are linearly independent and hence d = 3. 2.10 Cosets 2.10.2 List the rest of the cosets of C = {000, 111}. Notice that there are eight possibilities for the cosets of C, one for each word in K3, but only four of these cosets are distinct. In Example 2.10.1, two cosets of C are given as C = {000, 111} and C + 101 = {101, 010}. The remaining cosets are C + 110 = {110, 001} and C + 100 = {100, 011}. 2.10.6 List the cosets of each of the following linear codes. (a) C = {0000, 1001, 0101, 1100} The cosets are C, C + 1000, C + 0010, C + 1010. (b) C = {0000, 1010, 1101, 0111} The cosets are C, C + 1000, C + 0100, C + 0001. (c) C = {00000, 10100, 01011, 11111} The cosets are C, C + 10000, C + 01000, C + 00010, C + 00001, C + 11000, C + 00110, C + 10001. (d) C = {0000} The cosets are C, C + 1000, C + 0100, C + 0010, C + 0001, C + 1100, C + 0110, C + 0011, C + 1010, C + 0101, C + 1001, C + 1110, C + 1101, C + 1011, C + 0111, C + 1111. 67

2.10.7 List the cosets of each of the linear codes having the given generator matrix. 1 1 1 0 0 0 (a)G = 0 0 1 1 1 0. 100011 C = {000000, 111000, 001110, 100011, 110110, 011011, 101101, 010101}. Therefore the cosets are C, C + 100000, C + 010000, C + 001000, C + 000100, C + 000010, C + 000001, C + 100100. (b) G = 1 0 1 0 1 0 . 0 1 0 1 0 1 C = {000000, 101010, 010101, 111111}. Therefore the cosets are C, C + 100000, C + 010000, C + 001000, C + 000100, C + 000010, C + 000001, C + 110000, C + 011000, C + 001100, C + 000110, C + 000011, GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturC + 100100, C + 100001, C + 001001, C + 010010. 1 0 0 0 1 1 1 (c) G = 0 1 0 0 1 1 01. 0 0 1 0 1 0 0001011 C = {0000000, 1000111, 0100110, 0010101, 0001011, 1100001, 1010010, 1001100, 0110011, 0101101, 0011110, 1110100, 0111000, 1011001, 1101011, 1111111}. Therefore the cosets are C, C + 1000000, C + 0100000, C + 0010000, C + 0001000, C + 0000100, C + 0000010, C + 0000001. 1 0 0 0 1 (d) G = 0 1 0 0 11. 0 0 1 0 00011 C = {00000, 10001, 01001, 00101, 00011, 11000, 10100, 10010, 01100, 01010, 00110, 11101, 01111, 11011, 10111, 11110}. Therefore the cosets are C, C + 10000. 1 0 0 0 (e) G = 0 1 0 0 0 0 1 0 0001 C = K4 and hence there is only one coset, C. (f ) G = 1 1 1 1 . C = {0000, 1111}. Therefore the cosets are C, C + 1000, C + 0100, C + 0010, C + 0001, C + 1100, C + 0110, C + 1010. 2.10.8 List the cosets of the code having the given parity check matrix. 1 0 (a) H = 1 10. 1 01 G= 1 0 1 0 . Therefore the cosets are C = {0000, 1010, 0111, 1101}, C + 1000, C + 0 1 1 1 0100, C + 0001. 68

1 1 1 1 1 0 1 0 1 (b)H = 0 1 1. 1 0 0 0 1 0 001 Refer Exercise 2.10.7(c). 1 0 0 0 1 0 (c)H = 0 1 10. 0 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0 0 1 001 1 0 0 1 0 0 G = 0 0 1 0 1 0 and therefore 000011 C = {000000, 011000, 000101, 000011, 011101, 011011, 000110, 011110}. Hence the cosets are C, C + 100000, C + 010000, C + 000100, C + 110000, C + 100100, C + 001001, C + 101010. 2.10.9 Prove Theorem 2.10.3. [(1)] Since u ∈ C + v, u = w + v for some w ∈ C. If u1 ∈ C + u, then u1 = u2 + u = u2 + (w + v) = (u2 + w) + v and hence u1 ∈ C + v. Now if v1 ∈ C + v, then v1 = v2 + v = v2 + (w + u) = (v2 + w) + u and hence v1 ∈ C + u. Thus C + u = C + v. [(2)] Since C is a linear code the zero word 0 belongs to C. Therefore u = 0 + u ∈ C + u. [(3)] If u + v is in C, then u + v = w for some w ∈ C and hence u = w + v. So u ∈ C + v. Therefore by (1), u and v are in the same cosets. [(4)] If u + v is not in C, then u is not in C + v. But u ∈ C + u and v ∈ C + v. Therefore u and v are in different cosets. [(5)] Let u, v ∈ Kn. Then either u + v ∈ C or u + v ∈/ C. If u + v ∈ C, then C + u = C + v. Otherwise u + v ∈/ C implies C + u = C + v. [(6)] For each w ∈ C, w + u ∈ C + u and for each v ∈ C + u, v = w + u for exactly one w ∈ C. So there is a one-one correspondence between C and C + u. Therefore | C + u |=| C |. [(7)] By (5), Kn = can be written as the disjoint union of cosets of C. Therefore the number of distinct cosets are |Kn| = 2n = 2n−k . Since | C |= 2k, by (6), each coset contains |C | 2k exactly 2k words. [(8)] Since the zero word 0 ∈ C, C + 0 = C is a coset. 69

2.11 MLD for Linear Codes 2.11.2 Let C be the code of Example 2.10.5. Use the procedure for CMLD just outlined to decode each of the following received words. The cosets of C in Example 2.10.5 are C, C + 100000, C + 010000, C + 001000, C + 000100, C + 000010, C + 000001, C + 000101. (a) 000011 000011 ∈ C + 010000. Then 000011 is decoded as 000011 + 010000 = 010011. (b) 001001. 001001 ∈ C + 100000. Then 001001 is decoded as 001001 + 100000 = 101001. (c)001101 001101 ∈ C + 000010. Then 001101 is decoded as 001101 + 000010 = 001111. (d)010110 010110 ∈ C + 000101. Then 010110 is decoded as 010110 + 000101 = 010011. (e)110101 110101 ∈ C. Then 110101 is decoded as 110101 itself. (f )001010 001010 ∈ C + 000101. Then 001010 is decoded as 001010 + 000101 = 001111. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.11.8 Construct an SDA assuming IMLD for each of the codes in Exercise 2.10.6. (a)C = {0000, 1001, 0101, 1100} 0 1 Error pattern Syndrome uH 10. Therefore the SDA is 0000 00 H = 0 1 ∗ 01 1 0010 10 ∗ 11 0 (b)C = {0000, 1010, 1101, 0111}. 1 0 Error pattern Syndrome uH 01. Therefore the SDA is 0000 00 H = 1 1 ∗ 10 1 0100 11 0001 01 0 (c)C = {00000, 10100, 01011, 11111}. Error pattern Syndrome uH 00000 000 1 0 0 ∗ 100 0 1 1 01000 011 00010 010 H = 1 0 0. Therefore the SDA is 00001 001 0 1 0 001 ∗ 111 ∗ 110 ∗ 101 2.11.9 Construct an SDA assuming IMLD for each of the codes in Exercise 2.10.7 70

1 1 1 0 0 0 (a)G = 0 0 1 1 1 0 100011 Error pattern Syndrome uH 0 1 1 000000 000 100000 011 1 0 1 010000 101 001000 110 H = 1 1 00. Therefore the SDA is 000100 100 1 0 000010 010 000001 001 0 1 0 001 ∗ 111 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (b)G = 1 0 1 0 1 0 0 1 0 1 0 1 Error pattern Syndrome uH 000000 0000 100000 1010 010000 0101 001000 1000 1 0 1 0 000100 0100 000010 0100 0 1 0 1 000001 0001 110000 1111 H = 1 0 0 00. Therefore the SDA is 011000 1101 0 1 0 001100 1100 000110 0110 0 0 1 0 0001 000011 0011 100100 1110 100001 1011 001001 1001 010010 0111 1 0 0 0 1 1 1 (c)G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0001011 Error pattern Syndrome uH 1 1 1 0000000 000 1 1 0 1000000 100 0100000 110 1 0 1 0010000 101 H = 0 1 1. Therefore the SDA is 0001000 011 0000100 100 1 0 0 0 1 0 001 0000010 010 0000001 001 71

1 0 0 0 1 (d)G = 0 1 0 0 1 0 0 1 0 1 00011 1 1 Error pattern Syndrome uH H = 1. Therefore the SDA is 00000 0 1 ∗ 1 1 1 0 0 0 (e)G = 0 1 0 0 0 0 1 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0001 Since G generates K4, H = φ. (f )G = 1 1 1 1 Error pattern Syndrome uH 0000 000 1 1 1 1000 111 0100 100 H = 1 0 00. Therefore the SDA is 0010 010 0 1 0001 001 011 001 ∗ ∗ 110 ∗ 101 2.11.10 Construct an SDA assuming IMLD for each of the codes in Exercise 2.10.8. 1 0 (a) H = 1 1 1 0 01 Error pattern Syndrome uH 0000 00 ∗ 10 0100 11 0001 01 1 1 1 1 1 0 1 0 1 (b)H = 0 1 1 1 0 0 0 1 0 001 72

Error pattern Syndrome uH 0000000 000 1000000 111 0100000 110 0010000 101 0001000 011 0000100 100 0000010 010 0000001 001 1 0 0 0 1 0 (c)HGovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur=010 0 0 1 0 0 1 001 Similarly as in the above questions. 2.11.11 Prove Theorem 2.11.4. 1. Assume that w is a codeword in C. Since the columns of H form a basis for C⊥, wH = 0. Now wH = 0 implies that w is orthogonal to every word in C⊥. Then w ∈ (C⊥)⊥. But (C⊥)⊥ = C and hence w ∈ C. 2. If wH = uH, then (w + u)H = 0 and therefore by 1. w + u ∈ C and hence w and u lie in the same coset of C. If w and u lie in the same coset of C, then the corresponding coset leaders are same and hence the syndromes wH and uH are equal. 3. When uH is found, only the rows of H at positions where u has a 1 are added and hence uH is the sum of the rows of H that correspond to the positions in which errors occurred in the transmission. 2.11.14 Continuing the last example with w = 110000 received. Decode assuming that u” = 110000 had been chosen as the coset leader for the last coset. Assuming u” = 110000 as the chosen coset leader w = 110000 is decoded as w + u” = 000000. 2.11.15 Refer to Example 2.11.13 with w = 110111 received. Check that in fact v = 110101 is the closest codeword in C to w. d(000000, 110111) = 5 d(100110, 110111) = 2 d(010011, 110111) = 2 d(001111, 110111) = 3 d(110101, 110111) = 1 d(101001, 110111) = 4 d(011100, 110111) = 4 d(111010, 110111) = 3 Distance between 111010 and 110111 is the least and hence v = 110101 is the closest codeword in C to w = 110111. 2.11.16 Again refer to Example 2.11.13 with w = 110000 received. Find all the codewords in C closest to w. wH = 101 and there are three possible coset leaders for this syndrome. They are 000101, 001010, 110000. Therefore the closest codewords are 110000+000101 = 110101, 110000+001010 = 111010, 110000+ 110000 = 000000. 73

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur2.11.17 Repeat the decoding in Exercise 2.11.2 using the SDA in Example 2.11.7. (a)000011 wH = 011 and the coset leader is 010000. Therefore 000011 is decoded as 000011 + 010000 = 010011. (b)001001 wH = 110 and the coset leader is 100000. Therefore 001001 is decoded as 001001 + 100000 = 101001. (c) 001101 wH = 010 and the coset leader is 000010. Therefore 001101 is decoded as 001101 + 000010 = 001111. (d)010110 wH = 101 and a coset leader is 000101. Therefore 010110 is decoded as 010110 + 000101 = 010011. (e)110101 wH = 000 and the coset leader is 000000. Therefore 110101 is decoded as 110101 itself. (f )001010 wH = 101 and a coset leader is 000101. Therefore 001010 is decoded as 001010 + 000101 = 001111. 2.11.18 For the code in Example 2.11.13 above, decode the following received words w. (a) 011101 wH = 001 and the coset leader is 000001. Therefore w is decoded as 011101+000001 = 011100. (b)110101 wH = 000 and the coset leader is 000000. Therefore w is decoded as w itself. (c)111111 wH = 111 and the coset leader is 001000. Therefore w is decoded as 111111+001000 = 110111. (d) 000000 wH = 000 and the coset leader is 000000. Therefore w is decoded as w itself. 2.11.19 For each of the following codes, use the SDA to decode the given received words.(The SDA’s for these codes were constructed in Exercises 2.11.8 and 2.11.9.) (a) C = {0000, 1001, 0101, 1100} (i)w = 1110 wH = 10 and the coset leader is 0010. Therefore the word w is decoded as 1110 + 0010 = 1100. (ii)w = 1001 wH = 00 and the coset leader is 0000. Therefore the word w is decoded as w itself. (iii)w = 0101 wH = 00 and the coset leader is 0000. Therefore the word w is decoded as w itself. (b)C = {00000, 10100, 01011, 11111} (i) w = 10101 wH = 001 and the coset leader is 00001. Therefore the word w is decoded as 10101 + 00001 = 10100. 74

(ii)w = 01110 wH = 101 and a coset leader is 10001. Therefore the word w is decoded as 01110 + 10001 = 11111. (iii)w = 10001 wH = 101 and a coset leader is 10001. Therefore the word w is decoded as 10001 + 10001 = 00000. (c) C =< 111000, 001110, 100011 > (i)w = 101010 wH = 111 and a coset leader is 100100. Therefore the word w is decoded as 101010 + 100100 = 001110. (ii)w = 011110 wH = 101 and the coset leader is 010000. Therefore the word w is decoded as 011110 + 010000 = 001110. (iii)w = 011001 wH = 010 and the coset leader is 000010. Therefore the word w is decoded as 011001 + 000010 = 011011. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.11.20 Let C be the code with the parity check matrix 0 1 1 1 0 1 H = 1 1 0 1 0 0 0 1 0 001 (Refer 2.9.11(a)). Decode (a)110100 wH = 010 and the coset leader is 000010. Therefore 110100 is decoded as 110100 + 000010 = 110110. (b)111111 wH = 111 and a coset leader is 100100. Therefore 111111 is decoded as 111111 + 100100 = 011011. (c)101010 wH = 111 and a coset leader is 100100. Therefore 101010 is decoded as 101010 + 100100 = 001110. (d)000110 wH = 110 and the coset leader is 001000. Therefore 000110 is decoded as 000110 + 001000 = 001110. 2.11.21 Let C be the code of length 7 which has as a parity-check matrix the 7 × 3 matrix H whose rows are all nonzero words of length 3. (a) Construct an SDA for C. 75

1 1 1 1 1 0 1 0 1 Given H = 0 1 1. Referring to Exercise 2.10.7(c), the SDA is as follows: 1 0 0 0 1 0 001 Errorpattern SyndromeuH 0000000 000 1000000 111 0100000 110 0010000 101 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0001000 011 0000100 100 0000010 010 0000001 001 (b) Decode 1010101. If w = 1010101, then wH = 111. Therefore the coset leader is 1000000 and hence w is decoded as 1010101 + 1000000 = 0010101. 2.12 Reliability of IMLD for linear codes 2.12.2 Calculate θp(C) for each of the codes in Exercises 2.10.6, 2.10.7, 2.10.8. θp(C) = u∈L(0) pn−wt(u)(1 − p)wt(u). (a) C = {0000, 1001, 0101, 1100} Using IMLD there is one coset leader of weight 0 and one coset leader of weight 1. Therefore θp(C) = p4 + p3(1 − p). (b)C = {0000, 1010, 1101, 0111} Using IMLD there is one coset leader of weight 0 and two coset leaders of weight 2. Thus θp(C) = p4 + 2p3(1 − p). (c)C = {00000, 10100, 01011, 11111} Using IMLD there is one coset leader of weight 0 and three coset leaders of weight 1. Thus θp(C) = p5 + 3p4(1 − p). (d)C = {0000} Using IMLD there is one coset leader of weight 0, four coset leaders of weight 1, six coset leaders of weight 2, four coset leaders of weight 3 and one coset leader of weight 4. Thus θp(C) = p4 + 4p3(1 − p)6p2(1 − p)2 + 4p(1 − p)3 + (1 − p)4. 1 1 1 0 0 0 (e) G = 0 0 1 1 1 0 100011 Using IMLD there is one coset leader of weight 0 and six coset leaders of weight 1. Thus θp(C) = p6 + 6p5(1 − p). (f )G = 1 0 1 0 1 0 0 1 0 1 0 1 76

Using IMLD there is one coset leader of weight 0, six coset leaders of weight 1 and nine coset leaders of weight 2. Thus θp(C) = p6 + 6p5(1 − p) + 9p4(1 − p)2. 1 0 0 0 1 1  (g)G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0001011 Using IMLD there is one coset leader of weight 0 and seven coset leaders of weight 1. Thus θp(C) = p7 + 7p6(1 − p). 1 0 0 0 1 (h)G = 0 1 0 0 1 0 0 1 0 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 00011 Using IMLD there is one coset leader of weight 0. Thus θp(C) = p5. 1 0 0 0 (i)G = 0 1 0 0 0 0 1 0 0001 There is only one coset and hence only one coset leader which is of weight 0. Thus θp(C) = p4. (j)G = 1 1 1 1 Using IMLD there is one coset leader of weight 0 and four coset leaders of weight 1. Thus θp(C) = p4 + 4p3(1 − p). 1 0 (k)H = 1 1 1 0 01 Using IMLD there is one coset leader of weight 0 and two coset leaders of weight 1. Thus θp(C) = p4 + 2p3(1 − p). 1 1 1 1 1 0 1 0 1 (l)H = 0 1 1 1 0 0 0 1 0 001 Using IMLD there is one coset leader of weight 0 and seven coset leaders of weight 1. Thus θp(C) = p7 + 7p6(1 − p). 1 0 0 0 1 0 (m)H = 0 1 0 0 0 1 0 0 1 001 77

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturUsing IMLD there is one coset leader of weight 0 and one coset leader of weight 1. Thus θp(C) = p6 + p5(1 − p) 78

Chapter 3 Perfect and Related Codes GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 3.1 Some bounds for codes 3.1.2 Illustrate Theorem 3.1.1 for v = 10110 and t = 3 by listing all words in K5 of distance at most 3 from v, and then check that Theorem 3.1.1 does give the correct number of such words. The words of distance ≤ 3 form v = 10110 are 10110, 00110, 11110, 10010, 10100, 10111, 01110, 00010, 00100, 00111, 11010, 11100, 11111, 10000, 10011, 10101, 10001, 11101, 11011, 11000, 00101, 00011, 00000, 01111, 01100, 01010. There are 26 words. Now, from theorem, 5555 + + + = 1 + 5 + 10 + 10 = 26 0123 3.1.5 Find an upper bound for the size or dimension of a linear code with the given values of n and d. (a) n = 8, d = 3 (b) n = 7, d = 3 (c) n = 10, d = 5 (d) n = 15, d = 3 (e) n = 15, d = 5 (f ) n = 23, d = 7. 2n |C | ≤ , where t is such that d = 2t + 1 or d = 2t + 2 (n0)+(n1)+...+(nt ) (a) t = 1. Thus, |C| ≤ 28 ≈ 28.4444. Since, size of C is always some 2k, we get, (08)+(81) |C| ≤ 24 = 16. (b) t = 1. Thus, |C | ≤ 27 = 16. (07)+(71) (c) t = 2. Thus, |C | ≤ 210 ≈ 18.2857. Since, size of C is always some 2k, we get, (100)+(110)+(120) |C| ≤ 24 = 16. (d) t = 1. Thus, |C | ≤ 215 = 2048. (105)+(115) 79

(e) t = 2. Thus, |C | ≤ 215 ≈ 270.8099. Since, size of C is always some 2k, we (105)+(115)+(125) get, |C| ≤ 28 = 256. (f ) t = 3. Thus, |C | ≤ 223 = 4096. (203)+(213)+(223)+(233) 3.1.6 Verify the Hamming bound for the linear code C with the given generator matrix. 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 (a) G =  0 0 0 0 0 1 1 1 1 1 0 0 0 0 0  000001111111111 1 0 0 1 1 1 (b) G =  0 1 0 1 0 1  001011 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1 0 0 0 1 1 1 (c) G =  0 1 0 0 1 1 0  0 0 1 0 1 0  1   0001011 (b) k = 3 and the parity check matrix is 1 1 1 1 0 1 H =  0 1 1  By trial and error method we see that any two rows of H are linearly  1 0 0       0 1 0    001 independent and rows 2, 4, 6 are linearly dependent. So, d = 3. Hence, t = 1 26 = 64 and 7 (60)+(61) |C| = 23 = 8. Hence verified. 3.1.10 Columns 2,3 and 5 of the generator matrix G below are linearly dependent. Find a codeword which has zeros in positions 2, 3 and 5 1 1 0 0 1 G = 0 1 1 1 0 Let x00y0 be the required codeword in C. We find x and y with the 00101 help of the given generator matrix. Suppose a(11001) + b(01110) + c(00101) = x00y0. Then, we have a = x, a + b = 0, b + c = 0, b = y and a + c = 0 Choose a = b = c = 1. Then, 10010 is the required codeword. 3.1.11 Show that if a k × n generator matrix has k linearly dependent columns then there is a nonzero codeword with zeros in those k positions. 3.1.18 For each part of Exercise 3.1.5, let k = 2d and decide, if possible, whether or not a linear code with the given parameters exists. Find a lower and upper bound for the maximum number of codewords such a code can have, assuming that k is unrestricted. (a) n = 8, d = 3 80

(b) n = 7, d = 3 (c) n = 10, d = 5 (d) n = 15, d = 3 (e) n = 15, d = 5 (f ) n = 23, d = 7. (a) Given k = 2d = 6. To determine if such a code exists, we use the Gilbert-Varshamov bound: 7 + 7 = 8 and 2n−k = 22 = 4. Since 4 < 8, we cannot decide. 0 1 To find a lower bound for the most number of codewords such a code C could have, we use 27 Corollary 3.1.14. |C | ≥ = 16 (70)+(71) GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur To find an upper bound, we use Hamming bound:|C | ≤ 28 = 28.44. Thus, |C | ≤ 16. (80)+(18) (b) Given k = 2d = 6. To determine if such a code exists, we use the Gilbert-Varshamov bound: 6 + 6 = 7 and 2n−k = 21 = 2. Since 2 < 7, we cannot decide. 0 1 To find a lower bound for the most number of codewords such a code C could have, we use 26 Corollary 3.1.14. |C | ≥ = 8 (06)+(16) To find an upper bound, we use Hamming bound:|C | ≤ 27 = 16. Thus, |C | ≤ 16. (70)+(71) (f ) Given k = 2d = 14. To determine if such a code exists, we use the Gilbert-Varshamov bound: 22 + 22 + 22 + 22 + 22 + 22 = 35443 and 2n−k = 29 = 512. Since 512 < 35443, 0 1 2 3 4 5 we cannot decide. To find a lower bound for the most number of codewords such a code C could have, we use 222 Corollary 3.1.14. |C | ≥ = 118.3394 (202)+(212)+(222)+(232)+(242)+(252) Thus, |C | ≥ 128. To find an upper bound, we use Hamming bound: |C | ≤ 223 = (203)+(213)+(223)+(233) 4675.9242. Thus, |C| ≤ 4096. 3.1.19 Find a lower and upper bound for the maximum number of codewords in a linear code of length n and distance d where (a) n = 15, d = 5 (b) n = 15, d = 3 (c) n = 11, d = 3 (d) n = 12, d = 3 (e) n = 12, d = 4 (f ) n = 12, d = 5. (a) To find a lower bound for the most number of codewords such a code C could have, we 214 use Corollary 3.1.14. |C | ≥ = 34.8595. Thus, |C | ≥ 64. To find an upper (104)+(114)+(124)+(134) bound, we use Hamming bound: |C | ≤ 215 = 270.8099. Thus, |C | ≤ 256. All others (105)+(115)+(125) are similar and just a matter of substitution. 81

3.1.20 Is it possible to have a linear code with parameters (8, 3, 5)? Here, n = 8, k = 3 and d = 5. To determine if such a code exists, we use the Gilbert-Varshamov bound: 7 + 7 + 7 + 7 = 64 and 2n−k = 25 = 32. Since 32 < 64, we cannot decide. 0 1 2 3 3.1.21 3.1.22 3.2 Perfect Codes 3.2.5 Show that for n = 2r − 1, n H+encn1 e, =22r0−r .1 For any n, =1 + GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturn+n 0 + 2r −1 = 1 + 2r − 1 = 2r. 0 1 1 n. 3.2.6 Can there exist perfect codes for these values of n and d. (a)n = 15, d = 3. 215 Here, t = 1. Thus, |C | = (105)+(115) = 211. Thus, there may exist a linear perfect code with n = 15, d = 3. (b) n = 31, d = 3. 231 Here, t = 1. Thus, |C | = (301)+(311) = 226. Thus, there may exist a linear perfect code with n = 31, d = 3. (c) n = 15, d = 5. 215 Thus, |C| = = 270.8099. Thus, there cannot exist a linear perfect code with (105)+(115)+(125) n = 15, d = 5. 3.3 Hamming Codes 3.3.3 Find a generator matrix in standard form for a Hamming code of length 15, then en- code the message 11111100000. Given n = 15. So, r = 4. One possible parity check matrix is 1 1 1 1 1 1 0 1  1 0 1 1     0 1 1 1     1 0 0 1     0 1 0 1     0 0 1 1    H =  1 1 1 0     1 1 0 0     1 0 1 0     0 1 1 0     1 0 0 0     0 1 0 0     0 0 1 0    0001 82

It is of the form X . Thus, its generator matrix will be I X . That is I 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1  0 0 1 0 0 0 0 0 0 0 0 1 0 1 1     0 0 0 1 0 0 0 0 0 0 0 0 1 1 1     0 0 0 0 1 0 0 0 0 0 0 1 0 0 1    G =  0 0 0 0 0 1 0 0 0 0 0 0 1 0 1     0 0 0 0 0 0 1 0 0 0 0 0 0 1 1     0 0 0 0 0 0 0 1 0 0 0 1 1 1 0     0 0 0 0 0 0 0 0 1 0 0 1 1 0 0    turGovDeerpnt.moefntMaCtohlleemgaeticCsh,it-  0 0 0 0 0 0 0 0 0 1 0 1 0 1 0    000000000010110 To encode the message u = 11111100000: we compute uG = 1111110010. 3.3.4 Construct an SDA for a Hamming code of length 7, and use it to decode the following words: (a) 1101011 (b) 1111111 (c) 0011010 (d) 0101011 (e) 0100011 (f ) 0001011 An SDA for a Hamming code is coset leader syndrome 000· · · 0 00· · · 0 I2r −1 H Here, n = 7. So, r = 3. Hence, its SDA is: coset leader syndrome 0000000 000 1000000 111 0100000 110 0010000 101 0001000 011 0000100 100 0000010 010 0000001 001 (a) w = 1101011 The syndrome is wH = 001, which is the last row of H. So the corre- sponding coset leader is u = 0000001. Hence we decode w as w + u = 1101010. (b) w = 1111111 The syndrome is wH = 000, which is the first row and second column of SDA. So the corresponding coset leader is u = 0000000. Hence we decode w as w + u = 1111111. 83

3.3.5 Construct an SDA for a Hamming code of length 15, and use it to decode the following words: (a) 01010 01010 01000 Here, n = 15. So, r = 4. Hence, its SDA is: GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturcoset leadersyndrome 000000000000000 0000 100000000000000 1110 010000000000000 1100 001000000000000 1010 000100000000000 0110 000010000000000 1000 000001000000000 0100 000000100000000 0010 000000010000000 0001 000000001000000 1111 000000000100000 1101 000000000010000 1011 000000000001000 0111 000000000000100 1001 000000000000010 0101 000000000000001 0011 (a) w = 01010 01010 01000 The syndrome is wH = 0000. So the corresponding coset leader is u = 000000000000000. Hence we decode w as w + u = 01010 01010 01000. 3.3.6 Show that each of the following is a parity check matrix for a Hamming code of length 7, and that the codes are both equivalent to the one in Example 3.3.1.  001   100   010   110   011   111      H =  100  H =  011       101   101       110   010      111 001 By the method of RREF , we see that H and H are equivalent. 3.3.8 Prove that the Hamming codes of a given length are equivalent. For a given length n = 2r − 1, we form its parity check matrix as the rows with all non zero words of length r. And any two matrices formed in this way are equivalent, and so is the Hamming codes. 3.3.9 Is the following matrix the transpose of a parity check matrix for a Hamming code of length 15? 84

 10001 10111 01000  10001 HT =  11100 00101 11110   01011 01011  11101   10001 00111 So,  1101   0110   0100     0010     1011     1100    GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur  0001    H =  1010     1001     1111     0110     1110     0111     0101    0011 the word 0110 appeared twice in the matrix H. So, the given matrix is not transpose of a parity check matrix. 3.3.10 Show that the Hamming code of length 2r − 1 for r = 2 is a trivial code. Its parity check matrix will be:  11  H =  10  01 Its generator matrix is G = 111 . And, the code is not trivial. 3.3.11 Use the Hamming code of length 7 in Example 3.3.1 and the message assignment in Exercise 2.6.11. Decode the following message received: 1010111, 0110111, 1000010, 0010101, 1001011, 0010000, 111 The assignment is 000 100 010 001 110 101 011 111 A B E H M R T W and the SDA is coset leader syndrome 0000000 000 1000000 111 0100000 110 0010000 101 0001000 011 0000100 100 0000010 010 0000001 001 85

1010111H = 101, 0110111H = 100, 1000010H = 101, 0010101H = 000, 1001011H = 111, 0010000H = 101, 1111100H = 011. So the coset leaders are 0010000, 0000100, 0010000, 0000000, 1000000, and we decode it as 1000111, 0110011, 1010010, 0010101, 0001011, 0000000, 1110100 3.4 Extended Codes 3.4.3 Find generating and parity check matrices for an extended Hamming code of length 8 If G and H are the generator and parity check matrices for a code C respectively, then, the gen- erator and parity check matrices for its extended code C∗ is G∗ = Gb and H∗ = Hj 01 where b is a column such that each row of G∗ has even weight and j is a column of all ones. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 111   100   1000111  101  0100100  011   0010101  100   0001011   010     Here, H =   and G =        001  1111   1001   1011   10001110    Hence, Here, H∗ =  0111  and G∗ =  01001000   1001   00101011         0101  00010111    0011    0001 3.4.4 Construct an SDA for an extended Hamming code of length 8, and use it to decode the following words: (a) 10101010 (b) 11010110 (c) 11111111 SDA is syndrome coset leader 0000 00000000 1111 10000000 1101 01000000 1011 00100000 0111 00010000 1001 00001000 0101 00000100 0011 00000010 0001 00000001 86

w = 10101010. The syndrome is wH = 1010. So the corresponding coset leader is u = 000000000000000. Hence we decode w as w + u = 01010 01010 01000. 3.4.5 Show that an extended Hamming code of length 8 is a self-dual code, i.e.,C = C⊥ 3.4.6 Find a formula for the distance d∗ of the extended code C∗ in terms of the distance of the original code C. If distance d of C is even, then distance of C∗ is d. If not, it is d + 1. 3.4.7 Let C be a Hamming code of length 15. Find the number of error patterns that Theorem 1.11.14 guarantees the extended code C∗ will detect, and the number of error patterns Theorem 1.12.9 guarantees C∗ will correct. How many error patterns does C∗ correct?  1111  GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur  1101   1011     0111     1001     0101     0011    The parity check matrix is H =  1110     1100     1010     0110     1000     0100     0010    0001 Here, d = 2. So, the number of error patterns that Theorem 1.11.14 guarantees the extended code C∗ will detect is 15 and the number of error patterns Theorem 1.12.9 guarantees C∗ will correct is 1, the zero word alone. 3.5 The Extended Golay Code 3.5.1 Show that the word of all ones is in C24  100000000000110111000101   010000000000101110001011   001000000000011100010111     000100000000111000101101     000010000000110001011011    We have G =  000001000000100010110111   000000100000000101101111       000000010000001011011101     000000001000010110111001     000000000100101101110001     000000000010011011100011    000000000001111111111110 87

Add all the rows. Then we get the word of all ones is in C24 3.5.2 Prove fact (4) about C24. From the fact (3), we have H = I is another parity check matrix for C24. Consider B G1 = B I . G1H = B I I = B + B = 0. So, G1 is also a generator matrix for C24. B 3.5.2 Prove fact (5) about C24. turGovDeerpnt.moefntMaCtohlleemgaeticCsh,it- Any two distinct rows of G are also orthogonal. Since every row of G has even weight, every row is orthogonal to itself. Thus, C2⊥4 = C24. 3.5.4 Use Theorem 2.9.1 to verify that C24 has distance 8.  110111000101   101110001011   011100010111     111000101101     110001011011     100010110111     000101101111     001011011101     010110111001     101101110001     011011100011    H =  111111111110   100000000000       010000000000     001000000000     000100000000     000010000000     000001000000     000000100000     000000010000     000000001000     000000000100     000000000010    000000000001 Hence, we see any 7 rows of H is linearly independent. So, d = 8 by Theorem 2.9.1. 3.6 Decoding the Extended Golay Code 3.6.5 The code is C24. Decode, if possible, each of the following received words w. 88

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(a) 111 000 000 000, 011 011 011 011 (b) 111 111 000 000, 100 011 100 111 (c) 111 111 000 000, 101 011 100 111 (d) 111 111 000 000, 111 000 111 000 (e) 111 000 000 000, 110 111 001 101 (f ) 110 111 001 101, 111 000 000 000 (g) 000 111 000 111, 101 000 101 101 (h) 110 000 000 000, 101 100 100 000 (i) 110 001 011 101, 111 000 000 000 (d) Let w = 111 111 000 000, 111 000 111 000. The syndrome is s = wH = 111 111 000 000 + 111 101 010 010 = 000010010010. wt(s) = 3. Hence, u = s, 0 = 000010010010000000000000 and conclude that v = w + u = 111101010010111000111000 was the codeword sent. Use Algorithm 3.6.1 to do rest of the sub-questions. 3.6.6 Find the most likely error pattern for any word with the given syndromes. (a) s1 = 010010000000, s2 = 011111010000 (a) s1 = 010010100101, s2 = 001000110000 (a) s1 = 111111000101, s2 = 111100010111 (a) s1 = 111111111011, s2 = 010010001110 (a) s1 = 001101110110, s2 = 111110101101 (a) s1 = 010111111001, s2 = 100010111111 3.6.7 Show that if s or sB has weight 4, then IMLD requires that the word be retransmitted. 3.7 The Golay Code 3.7.3 Decode each of the following received words that were encoded using C23. (a) 101011100000, 10101011011 (b) 101010000001, 11011100010 (c) 100101011000, 11100010000 (d) 011001001001, 01101101111 (a) Since w = 101011100000, 10101011011, wt(w) = 12, which is even. So form w1. Decode w1 using Algorithm 3.6.1 to decode w1 as done in Exercise 3.6.5 to obtain c. Now remove the last digit from c. 89

3.7.4 Prove that C23 has distance d = 7. Since distance of C24 is 8, and last digit of codes in B were 1 and by the construction of Bˆ, distance of C23 equals distance of C24 − 1 = 8 − 1 = 7. 3.7.5 Find the reliability of C23 transmitted over a BSC of probability p. 3.7.6 Determine whether C23 or C24 has the greater reliability. 3.7.7 Use the fact that every word of weight 4 is distance 3 from exactly one codeword to count the number of codewords of weight 7 in the Golay Code. 3.7.8 Use Exercise 3.7.7 to show that C24 contains precisely 759 codewords of weight 8 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 3.7.9 Use Exercise 3.5.1 and 3.7.8 to verify the following weight distribution table for C24: weight 0 4 8 12 16 20 24 number of words 1 0 759 2576 759 0 1 3.7.10 Let w be a received word that was encoded using C23. Append a digit i to w to form a word wi of odd weight. Show that wi is within distance 3 of a codeword in C24. 3.8 Reed-Muller Codes 3.8.5 Find the generator matrix G(2, 3). We have for 0 < r < m, G(r, m) = G(r, m − 1) G(r, m − 1) . From Example 3.8.4, 0 G(r − 1, m − 1)  1111 1111   1111   0101 0101  0101  0011   11 11   0011 0011   0001   01     00 G(2, 2) = and G(1, 2) = 01 . Hence, G(2, 3) =  0001 0001 .  11  0000 1111     0000 0101    0000 0011 3.8.6 Find the generator matrix G(r, 4), for the codes RM (r, 4) for r = 0, 1, 2.  11111111 11111111  G(1, 3) G(1, 3)  01010101 01010101  0 G(0, 3) G(0, 4) = 1111 , G(1, 4) = =  00110011 00110011 , G(2, 4) =   00001111 00001111    00000000 11111111 90

 11111111 11111111   01010101 01010101   00110011 00110011     00010001 00010001    G(2, 3) G(2, 3)  00001111 00001111  0 G(1, 3)   =  00000101 00000101 ,   00000011 00000011     00000000 11111111     00000000 01010101     00000000 00110011    00000000 00001111 3.8.10 Let G(1, 3) be the generator for the RM (1, 3) code, decode the following received words a. 0101 1110 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur b. 0110 0111 c. 0001 0100 d. 1100 1110 3.8.11 Let G(1, 4) be the generator for the RM (1, 4) code, decode the following received words a. 1011 0110 0110 1001 b. 1111 0000 0101 1111 91

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturChapter 4 Cyclic Linear Codes 4.1 Polynomials and words 4.1.2 Find the sum and the product of each of the following pairs of polynomials over K: (a)f (x) = x5 + x6 + x7, h(x) = 1 + x2 + x3 + x4; f (x) + h(x) = 1 + x2 + x3 + x4 + x5 + x6 + x7 and f (x)h(x) = x5 + x6 + x9 + x11. (b)f (x) = 1 + x2 + x3 + x8 + x13, h(x) = 1 + x3 + x9; f (x)+h(x) = x2 +x8 +x9 +x13 and f (x)h(x) = 1+x2 +x5 +x6 +x8 +x9 +x12 +x13 +x17 +x22. (c)f (x) = 1 + x, h(x) = 1 + x + x2 + x3 + x4. f (x) + h(x) = x2 + x3 + x4 and f (x)h(x) = 1 + x5. 4.1.3 Let f (x) = 1 + x. Find: (a)(f (x))2 (1 + x)(1 + x) = 1 + x2. (b)(f (x))3 (1 + x)3 = 1 + x + x2 + x3. (c)(f (x))4 (1 + x)4 = 1 + x4. 4.1.4 Repeat Exercise 4.1.3 for f (x) = 1 + x + x2. (f (x))2 = 1 + x2 + x4 (f (x))3 = 1 + x + x3 + x5 + x6 (f (x))4 = 1 + x4 + x8 4.1.5 List all polynomials over K of degree n, for n = 0, n = 2, n = 3 and n = 4. Polynomial of degree 0: 1 Polynomials of degree 2: x2, 1 + x2, x + x2, 1 + x + x2. Polynomials of degree 3: x3, 1+x3, x+x3, x2+x3, 1+x+x3, 1+x2+x3, x+x2+x3, 1+x+x2+x3. Polynomials of degree 4: x4, 1 + x4, x + x4, x2 + x4, x3 + x4, 1 + x + x4, 1 + x2 + x4, 1 + x3 + x4, x + x2 + x4, x + x3 + x4, x2 + x3 + x4, 1 + x + x2 + x4, 1 + x + x3 + x4, 1 + x2 + x3 + x4, x + x2 + x3 + x4, 1 + x + x2 + x3 + x4. 92

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur4.1.6 Find the number of polynomials over K of degree atmost 10. The number of polynomials over K of degree atmost 10 is 211 = 2048. 4.1.7 As you may have noticed in Exercises 4.1.3(a) and 4.1.4(a), for any polynomials f (x) and g(x) in K[x], (f (x) + g(x))2 = (f (x))2 + (g(x))2 since xk + xk = 0. Is there also a special rule in K[x] for (a)(f (x) + g(x))4. Yes. (f (x) + g(x))4 = (f (x))4 + (g(x))4 (b)(f (x) + g(x))3. (c)(f (x) + g(x))n, for any positive integer, n? If n = 2k, k ∈ N, then (f (x) + g(x))2k = (f (x))2k + (g(x))2k. 4.1.10 Find the quotient and remainder when h(x) is divided into f (x) for each of the pairs of poly- nomials over K in Exercise 4.1.2. (a)f (x) = x5 + x6 + x7, h(x) = 1 + x2 + x3 + x4 q(x) = x3, r(x) = x3. (b)f (x) = 1 + x2 + x3 + x8 + x13, h(x) = 1 + x3 + x9; q(x) = x4, r(x) = 1 + x2 + x3 + x4 + x7 + x8. (c)f (x) = 1 + x, h(x) = 1 + x + x2 + x3 + x4. q(x) = 0, r(x) = h(x). 4.1.11 Find the quotient and remainder in each part when h(x) is divided into f (x). (a)f (x) = x2 + x3 + x4 + x8, h(x) = 1 + x5. q(x) = x3, r(x) = x2 + x4. (b)f (x) = 1 + x10, h(x) = 1 + x5. q(x) = 1 + x5, r(x) = 0. (c)f (x) = 1 + x7, h(x) = 1 + x + x3. q(x) = 1 + x + x2 + x4, r(x) = 0. (d)f (x) = 1 + x15, h(x) = 1 + x4 + x6 + x7 + x8. q(x) = 1 + x4 + x6 + x7, r(x) = 0. 4.1.13 Represent each codeword C in the following codes with polynomials. (a)C = {000, 001, 010, 011} codeword polynomial c c(x) 000 0 001 x2 010 x 011 x + x2 93

(b)C = {000, 001, 010, 011} Same as in (a). (c)C = {0000, 0001, 1110} codeword polynomial c c(x) 0000 0 0001 x3 1110 1 + x + x2 (d)C = {0000, 1001, 0110, 1111} codeword polynomial c c(x) GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0000 0 1001 1 + x3 0110 x + x2 1111 1 + x + x2 + x3 (e)C = {00000, 11111} codeword polynomial c c(x) 00000 0 11111 1 + x + x2 + x3 + x4 (f )C = {00000, 11100, 00111, 11011}. codeword polynomial c c(x) 00000 0 11100 1 + x + x2 00111 x2 + x3 + x4 11011 1 + x + x3 + x4 4.1.14 Write out the Hamming code of length 7 generated by the matrix G and then represent this code by polynomials. 1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0001011 C = {0000000, 1000111, 0100110, 0010101, 0001011, 1100001, 1010010, 1001100, 0110011, 0101101, 0011110, 1110100, 0111000, 1011001, 1101011, 1111111} 94

codeword polynomial c c(x) 0000000 1000111 0 0100110 1 + x4 + x5 + x6 0010101 0001011 x + x4 + x5 1100001 x2 + x4 + x6 1010010 x3 + x5 + x6 1001100 1 + x + x6 0110011 1 + x2 + x5 0101101 1 + x3 + x4 0011110 x + x2 + x5 + x6 1110100 x + x3 + x4 + x6 0111000 x2 + x3 + x4 + x5 1011001 1 + x + x2 + x4 1101011 x + x2 + x3 1111111 1 + x2 + x3 + x6 1 + x + x3 + x5 + x6 1 + x + x2 + x3 + x4 + x5 + x6 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 4.1.19 Let h(x) = 1 + x3 + x5. Compute f (x)modh(x) and its corresponding word: (a)f (x) = 1 + x + x6 1 + x4 (b)f (x) = x + x4 + x7 + x8 1 + x2 (c)f (x) = 1 + x10 x + x4 4.1.20 Let f (x) = 1 + x7. Compute f (x)modh(x) and p(x)modh(x), and decide whether f (x) ≡ p(x)modh(x): (a)f (x) = 1 + x3 + x8, p(x) = x + x3 + x7 f (x)modh(x) = 1 + x + x3 and p(x)modh(x) = 1 + x + x3. Therefore f (x) ≡ p(x)modh(x). (b)f (x) = x + x5 + x9, p(x) = x + x5 + x6 + x13 f (x)modh(x) = x + x2 + x5 and p(x)modh(x) = x + x5. Therefore f (x) ≡ p(x)modh(x). (c)f (x) = 1 + x, h(x) = x + x7 f (x)modh(x) = 1 + x and p(x)modh(x) = 1 + x. Therefore f (x) ≡ p(x)modh(x). 4.1.21 Let h(x) = 1 + x7 compute (f (x) + g(x))modh(x) and f (x)g(x)modh(x), where (a)f (x) = 1 + x6 + x8, g(x) = 1 + x (f (x) + g(x))modh(x) = x6 and f (x)g(x)modh(x) = x2 + x6. (b)f (x) = 1 + x5 + x9, g(x) = x + x2 + x7 (f (x) + g(x))modh(x) = x5 + x + 1 and f (x)g(x)modh(x) = x6 + x5 + x4 + x3 + x2 + x. 95

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(c)f (x) = 1 + x4 + x5, g(x) = 1 + x + x2 (f (x) + g(x))modh(x) = x + x2 + x4 + x5 and f (x)g(x)modh(x) = x4 + x2 + x. 4.1.22 Prove that if f (x) ≡ g(x)(modh(x)), then f (x)p(x) ≡ g(x)p(x)(modh(x)). If f (x) ≡ g(x)(modh(x)), then f (x) = q1(x)h(x) + r(x) g(x) = q2(x)h(x) + r(x) Let p(x) = q(x)h(x) + r (x). Then f (x)p(x) ≡ r(x)r (x)modh(x) g(x)p(x) ≡ r(x)r (x)modh(x) Thus f (x)p(x) ≡ g(x)p(x)modh(x). 4.2 Introduction to Cyclic Codes 4.2.7 Find a basis for the smallest linear cyclic code of length n containing v: (a)v = 1101000, n = 7 The smallest linear cyclic code of length n containing v is < S > where S = {v, π(v), . . . πn−1(v)}. Here S = {1101000, 0110100, 0011010, 0001101, 1000110, 0100011, 1010001} and therefore C =< S >. If S is linearly independent then S itself is a basis. Now 0110100 + 0011010 + 0001101 + 0100011 = 0000000. Therefore S is linearly dependent. But 0011010+0001101+1000110+1010001 = 0000000. Therefore the set S1 = {1101000, 0011010, 0001101, 100 is linearly dependent. Let S2 = {1101000, 0001101, 1000110, 0100011, 1010001}. Then 1101000+0001101+1000110+ 0100011 = 0000000. Therefore S2 is linearly dependent. Let S3 = {0001101, 1000110, 0100011, 1010001}. Let a, b, c, d be scalars such that a(0001101) + b(1000110) + c(0100011) + d(1010001) = 0000000 =⇒ b + d = 0, c = 0, d = 0, a = 0 =⇒ b = 0 Therefore S3 is linearly independent and hence forms a basis for C. (b) v = 010101, n = 6 S = {010101, 101010} and thus C =< S >= {000000, 010101, 101010, 111111} with S itself as a basis. (c) v = 11011000, n = 8 S = {11011000, 01101100, 00110110, 00011011, 10001101, 11000110, 01100011, 10110001}. By the procedure in (a), a basis can be found. 96

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur4.2.8 Find all words v of length n such that π(v) = v. Let v = (v0v1 . . . vn−2vn−1). Then π(v) = (vn−1v0v1 . . . vn−2). Therefore π(v) = v =⇒ v0 = v1 = . . . = vn−2 = vn−1. Thus the only words in Kn such that π(v) = v are 00 . . . 0 and 11 . . . 1. 4.2.9 Find all words v of length 6 such that (a)π2(v) = v If v = (v0v1v2v3v4v5), then π2(v) = v implies v0 = v2 = v4 and v1 = v3 = v5. Therefore such words in K6 are 000000, 111111, 101010, 010101. (b) π3(v) = v. The words are 000000, 111111, 100100, 010010, 001001, 110110, 101101, 011011. 4.2.20 For each of the words below, find the generator polynomial for the smallest linear cyclic code containing that word. (a)010101 C = {000000, 010101, 101010, 111111}. g(x) = 1 + x2 + x4 ↔ 101010 is the generator poly- nomial. (b)010010 C = {000000, 010010, 001001, 100100, 011011, 101101, 110110, 111111}. g(x) = 1 + x3 ↔ 100100. (c)01100110 g(x) = 1 + x + x64 + x5 ↔ 11001100. (d)0101100 g(x) = 1 + x2 + x3 ↔ 1011000. (e)001000101110000 g(x) = 1 + x4 + x6 + x7 + x8↔ 100010111000000. (f )000010010000000 g(x) = 1 + x3 ↔ 100100000000000 (g)010111010000000 g(x) = 1 + x2 + x3 + x4 + x6 ↔ 101110100000000. 4.2.21 Find the generator polynomial of the smallest linear cyclic code containing each of the follow- ing words. (a)101010 Similar as in 4.2.20(a). (b)1100 g(x) = 1 + x ↔ 1100. (c)10001000 g(x) = 1 + x3 ↔ 10001000 (d)011011 g(x) = 1 + x + x3 + x4 ↔ 110110 (e)10101 g(x) = 1 + x + x3 ↔ 11010. 97

(f )111111 g(x) = 1 + x + x2 + x3 + x4 + x5 ↔ 111111. 4.2.22 For each of the codes C =< S > with S defined below, find the generator polynomial g(x) and then represent each word in the code as a multiple of g(x). (a)S = {010, 011, 111} C = {000, 010, 011, 111, 001, 101, 100, 110}. Now g(x) = 1 and word polynomial f(x) factorisation of f(x) 000 0 0(1) 010 x x(1) 011 x + x2 (x + x2)1 111 1 + x + x2 (1 + x + x2)1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 001 x2 x2(1) 101 1 + x2 (1 + x2)1 100 1 1.1 110 1 + x (1 + x)1 (b)S = {1010, 0101, 1111} g(x) = 1 + x2. word polynomial f(x) factorisation of f(x) 0000 0 0(1 + x2) 1010 1 + x2 1(1 + x2) 0101 x + x3 x(1 + x2) 1111 1 + x + x2 + x3 (1 + x)(1 + x2) (c)S = {0101, 1010, 1100} g(x) = 1 + x word polynomial f(x) factorisation of f(x) 0000 0 0(1 + x) 0101 x + x3 (x + x2)(1 + x) 1010 1 + x2 (1 + x)(1 + x) 1111 1 + x + x2 + x3 (1 + x2)(1 + x) 1100 1+x (1 + x)(1 + x) 1001 1 + x3 (1 + x + x2)(1 + x) 0110 x + x2 x(1 + x) 0011 x2 + x3 x2(1 + x) (d)S = {1000, 0100, 0010, 0001 g(x) = 1. Since < S >= K4 all polynomials f (x) of degree atmost 3 are in the code and f (x) = f (x)g(x). (e)S = {11000, 01111, 11110, 01010} g(x) = 1 + x. 98

word polynomial f(x) factorisation of f(x) 00000 11000 0 0(1 + x) 01111 11110 1+x 1(1 + x) 01010 x + x2 + x3 + x4 (x + x3)(1 + x) 10111 1 + x + x2 + x3 (1 + x2)(1 + x) 00110 (x + x2)(1 + x) 10001 x + x3 (1 + x + x3)(1 + x) 1 + x2 + x3 + x4 x2(1 + x) x2 + x3 (1 + x + x2 + x3)(1 + x) 1 + x4 4.3 Polynomial Encoding and Decoding GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 4.3.4 Let g(x) = 1 + x2 + x3 be the generator polynomial of a linear cyclic code of length 7. (a) Encode the following message polynomials: 1 + x3, x, x + x2 + x3. If a(x) is a message polynomial, then it is encoded as c(x) = a(x)g(x). a(x) c(x) c 1 + x3 1 + x2 + x5 + x6 1010011 x x + x3 + x4 0101100 x + x2 + x3 x + x2 + x6 0110001 (b)Find the message polynomial corresponding to the codeword c(x) : x2 + x4 + x5, 1 + x + x2 + x4, x2 + x3 + x4 + x6. If c(x) is given, then a(x) = c(x) . g(x) c(x) a(x) a x2 + x4 + x5 x2 0010000 1 + x + x2 + x4 1 + x 1100000 x2 + x3 + x4 + x6 x2 + x3 0011000 4.3.5 Find a basis and a generating matrix for the linear cyclic code of length n with generator polynomial g(x). (a)n = 7, g(x) = 1 + x2 + x3 C has dimension k = n − deg(g(x)) = 4. Therefore a basis for C is, g(x) = 1 + x2 + x3 = x + x3 + x4 xg(x) = x2 + x4 + x5 x2g(x) = x3 + x5 + x6 x3g(x) 1 0 1 1 0 0 0 and a generating matrix for C is G = 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0001011 (b)n = 9, g(x) = 1 + x3 + x6 99