Solution Manual- Coding Theory by Hoffman et al.

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Coding Theory Solution manual as per the University of Calicut Syllabus from 2020 onwards Prasanth G.Narasimha-Shenoi, Sneha Balakrishanan, Sreelakshmi Kuttikod Department of Mathematics Government College Chittur, Palakkad, Kerala, India - 678104

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Acknowledgement This solution manual will not be complete without the help of Sneha B and Sreelakshmi K my Post Graduate Students, who agreed to typeset the entire problems in LATEX . I express my sincere thanks to them for helping to complete the solutions. This is only a begining, I hope my next students will help to complete the “gaps” in this solution manual as well as rectifying the errors (if any). Prasanth G. Narasimha-Shenoi 1

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturChapter 1 Introduction to Coding Theory 1.1 Introduction 1.2 Basic Assumptions 1.2.1 List all words of length 3; of length 4; of length 5. When n = 3: 000,001,010,011, 100,101,110,111. When n = 4: 0000,0001,0010,0100,1000,1001,1010,1100,1101,1110,1111,0101, 0110, 0011,1011,0111. When n = 5: 00000,10000,01000,00100,00010,00001,11000,10100,10010,10001,01100, 01010, 00110, 00101, 00011, 11100, 11010, 11001, 01110, 00101, 00011, 11100, 11010, 11001, 01110, 01101, 10110, 10101, 10011, 01011, 00111, 11110, 11101, 11011, 10111, 01111,11111 1.2.2 Find a formula for the total number of words of length n. In a word of length n, each entry can take values 0 or 1. Therefore, there are 2n words of length n. 1.2.3 Let C be the code consisting of all words of length 6 having an even number of ones. List the codewords in C. 000000, 110000, 101000, 100100, 100010, 100001, 011000, 010100, 010010, 010001, 001100, 001010, 001001, 000110, 000101, 000011, 001111, 010111, 011011, 011101, 011110, 100111, 101011, 101101, 101110, 110011, 110101, 110110, 111001, 111010, 111100, 111111. 1.2.4 Explain why a channel with p = 0 is uninteresting? If a channel has p = 0, then every digit will be altered while transmission. So 0 changes to 1 and 1 changes to 0. Thus to find the message sent, we need only to change the 0s to 1s and 1s to 0s in the received word. 1.2.5 Explain how to convert a channel with 0 ≤ p ≤ 1/2 into a channel with 1/2 ≤ p ≤ 1? Let 0 ≤ p ≤ 1/2. Then 1 − p is such that 1/2 ≤ 1 − p ≤ 1. Let B1 be the channel with p such that 0 ≤ p ≤ 1/2. Then in B1 the probability that the digit sent is the digit received is p and 2

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturthe probability that the digit sent is not the digit received is 1 − p. In a channel with reliability 1 − p, the probability that the digit sent is the digit received is 1 − p and the probability that the digit sent is not the digit received is p. Thus the channel B2 with reliability 1 − p is the required channel. 1.2.6 What can be said about a channel with p = 1/2? In a channel with p = 1/2, the probability that the digit sent is the digit received and the digit sent is not the digit received is the same value, p = 1/2. So nothing can be concluded. 1.3 Correcting and Detecting Error Patterns 1.3.4 Let C be the code of all words of length 3. Determine which codeword was most likely sent if 001 is received? C Consists of all words of length 3. In particular 001 ∈ C. Therefore, the most likely word sent was 001. 1.3.5 Add a parity check digit to the codewords in the code in Exercise 1.3.4, and use the resulting code C to answer the following questions. The new code is C1 = {0000, 1001, 0101, 0011, 1100, 0110, 1010, 1111}. (a) If 1101 is received can we detect an error? Since 1101 ∈/ C1, the error can be detected. (b) If 1101 is received what code words were most likely to have been transmitted? 0101, 1001, 1111, 1100 are the codewords in C1 that differ from 1101 in exactly one posi- tion. Thus the most likely codewords to have been transmitted are 0101, 1001, 1111 and 1100. (c) Is any word of length 4 that is not in the code, closest to a unique codeword? In C1 there are all codewords with length 4 and even number of ones. Any word w ∈/ C1 will have an odd number of ones. Thus there are 4 codewords in C1 that differ exactly in one position with the word w. So there is no word of length 4 that is not in C1 and closest to a unique word in C1. 1.3.6 Repeat each codeword in the code C defined in Exercise 1.3.4 three times to form a repetiion code of length 9. Find the closest codewords to the following received words: The codeword is C1 = {000000000, 100100100, 010010010, 001001001, 110110110, 101101101, 011011011, 111111111}. (a) w = 001000001. For each v ∈ C1, we find the number of position v and w differ. Then the closest codeword is the v ∈ C1 which differ from w in least number of positions. 3

Codeword Number of positions v differ from w = 001000001 000000000 2 100100100 5 010010010 5 001001001 1 ← least number 110110110 8 101101101 4 011011011 4 111111111 7 The closest codeword is 001001001. (b) w = 011001001 Codeword Number of positions v differ from w = 001000001 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 000000000 5 100100100 7 010010010 4 001001001 2 110110110 7 101101101 5 011011011 1 ← least number 111111111 4 The closest codeword is 011011011 (c) w = 101000101 Codeword Number of positions v differ from w = 001000001 000000000 4 100100100 3 010010010 7 001001001 3 110110110 6 101101101 2 ← least number 011011011 6 111111111 5 The closest codeword is 101101101. (d) w = 101000101 Codeword Number of positions v differ from w = 001000001 000000000 2 ← least number 100100100 3 010010010 3 001001001 5 110110110 4 101101101 6 011011011 6 111111111 7 The closest codeword is 000000000. 4

1.4 Information Rate 1.4.1 Find the information rate for each of the codes in Exercises 1.3.4,1.3.5, and 1.3.6 The information rate of a code C of length n is defined to be 1 log2 |C|. n 1.3.4 C0 = {000, 100, 010, 001, 110, 011, 101, 111}. |C0| = 8 = 23 and n = 3. Information rate = 1 log2 23 = 1. 3 1.3.5 C1 = {0000, 1001, 0101, 0011, 1100, 0110, 1010, 1111}. |C0| = 8 = 23 and n = 4. Information rate = 1 log2 23 = 3 . 4 4 1.3.6 C2 = {000000000, 100100100, 010010010, 001001001, 110110110, 011011011, 101101101, 111111111}. |C0| = 8 = 23 and n = 4. Information rate = 1 log2 23 = 1 . GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 9 3 1.5 The Effects of Error Correction and Detection 1.6 Find the Most Likely Codeword Transmitted 1.6.2 Calculate φ.97(v, w) for each of the following pairs of v and w. It is known that φp(v, w) = pn−d(1 − p)d, where n is the length of v and w and d is the number of positions v and w differ. (a) v = 01101101, w = 10001110 φ.97(01101101, 10001110) = (0.97)3(0.03)5 = 2.2178 × 10−8 (b) v = 1110101, w = 1110101 Here d = 0 and n = 7 φ.97(v, w) = (0.97)7(0.03)0 = 0.8079 (c) v = 00101, w = 11010 d = 5, n = 5 φ.97(v, w) = (0.97)0(0.03)5 = 2.43 × 10−8 (d) v = 00000 = w d = 0, n = 5 φ.97(v, w) = (0.97)5(0.03)0 = 2.43 × 0.8587 5

(e) v = 1011010, w = 0000010 d = 3, n = 7 φ.97(v, w) = (0.97)4(0.03)3 = 2.3903 × 10−5 (f ) v = 10110, w = 01001 d = 5, n = 5 φ.97(v, w) = (0.97)0(0.03)5 = 2.43 × 10−8 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (g) v = 111101, w = 000010 d = 6, n = 6 φ.97(v, w) = (0.97)0(0.03)6 = 7.29 × 10−10 1.6.5 Suppose that w = 0010110 is received over a BSC with reliability p = 0.90. Which of the following code words is mostlikely to have been sent? Given 1/2 < p = 0.90 < 1. Therefore the codeword with smallest d, where d is the number of disagreements of v with w is the most likely codeword sent. v d (Number of disagreements with w) 1001011 5 1111100 4 0001110 2 ← smallest d 0011001 4 1101001 7 Therefore most likely codeword sent is 0001110. 1.6.6 Which of the 8 codewords in the code of Exercise 1.3.6 is most likely to have been sent if w = 101000101 is received? v d (Number of disagreements with w) 000000000 4 100100100 3 010010010 7 ← largest d 001001001 3 110110110 6 101101101 2 ← smallest d 011011011 6 111111111 5 If the reliability of the channel p is such that 0 < p < 1/2 Then most likely codeword is the one which has least d value. Thus the codeword is 101101101. If the reliability of the channel p is such that 1/2 < p < 1 Then most likely codeword is the one which has largest d value. Thus the codeword is 010010010. Since we usually choose p between 1/2 and 1, the answer is 101101101. 6

1.6.7 If C = {01000, 01001, 00011, 11001} and a word w = 10110 is received, which codeword is most likely to have been sent? v d (Number of disagreements with w) 01000 4 01001 5 ← largest d 00011 3 ← smallest d 11001 4 If p is between 0 and 1/2 most likely codeword is 01001 and if p is between 1/2 and 1, most likely codeword is 00011. 1.6.8 Repeat Exercise 1.6.7 after replacing C with {010101, 110110, 101101, 100110, 011001} and w with 101010. v d (Number of disagreements with w) GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 010101 5 110110 3 101101 3 ← smallest d 100110 2 011001 4 The most likely codeword sent is 100110. 1.6.9 Which of the codewords 110110, 110101, 000111, 100111, 101000 is most likely have sent if w = 011001 is received? v d (Number of disagreements with w) 110110 5 110101 3 ← smallest d 000111 4 100111 5 101000 3 ← smallest d 110101, 101000 are the most likely words sent. 1.6.10 In Theorem 1.6.3, we assume that 1/2 < p < 1. What would change in the statement of the Theorem 1.6.3, if we replace this assumption with the following. Theorem 1 (1.6.3). Suppose we have a BSC with 1/2 < p < 1. Let v1 and v2 be codewords and w a word,each of length n. Suppose that v1 and w disagree in d1 positions and v2 and w disagree in d2 positions. Then φp(v1, w) ≤ φp(v2, w) if and only if d1 ≥ d2. (a) Suppose 0 < p < 1/2: φp(v1, w) ≤ φp(v2, w) ⇐⇒ pn−d1 (1 − p)d1 ≤ pn−d2 (1 − p)d2 ⇐⇒ ⇐⇒ p d2−d1 ≤1 1−p d2 ≥ d1 Since 1 p p < 1 − (b) Suppose p = 1/2 1 n−d1 1 d1 1n φp(v1, w) = 2 =. 22 7

φp(v2, w) = 1 n−d2 1 d2 1n That is, φp(v1, w) = φp(v2, w). 2 = . 2 2 1.7 Some Basic Algebra 1.7.1 Show that if v is a word in Kn then v + v = 0. Let v = v1v2 · · · vn. v + v = v1v2 · · · vn + v1v2 · · · vn = (v1 + v1)(v2 + v2) · · · (vn + vn) = 00 · · · 0 = 0. 1.7.2 Show that if v and w are words in Kn and v + w = 0 then v = w. Suppose v, w are words in K with v + w = 0. Then (v + w) + w = 0 + w =⇒ v + (w + w) = w =⇒ v + 0 = w =⇒ v = w 1.7.3 Show that if u, v and w are words in Kn and u + v = w then u + w = v. Let u, v and w are words in K and u + v = w. Then (u + v) + v = w + v =⇒ u + (v + v) = w + v =⇒ u + 0 = w + v =⇒ u = w + v =⇒ w + u = w + (w + v) =⇒ u + w = (w + w) + v =⇒ u + w = 0 + v =⇒ u + w = v. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1.8 Weight and Distance 1.8.1 Compute the weight of each of the following words, and the distance between them. v1 = 1001010, v2 = 0110101, v3 = 0011110, and v4 = v2 + v3. wt(v1) = 3, wt(v2) = 4, wt(v3) = 4 and wt(v4) = wt(0101011) = 4. Now d(v1, v2) = 7, d(v1, v3) = 3, d(v1, v4) = 3, d(v2, v3) = 4, d(v2, v4) = 4 and d(v3, v3) = 4 and d(vi, vi) = 0 for i = 1, 2, 3, 4. 1.8.2 Let u = 01011, v = 11010, w = 01100. Compare the following: 8

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(a) wt(v + w) = wt(10110) = 3, wt(v) = 3 and wt(w) = 2. That is wt(v) + wt(w) = 5. Thus wt(v + w ≤ wt(v) + wt(w). (b) d(v, w) = 3, d(v, u) = 2 and d(u, w) = 3d(v, u) + d(u, w) = 5. Therefore d(v, w) ≤ d(v, u) + d(u, w) 1.8.3 Construct an example in K5 of each of the eleven rules defined in this section: 1. 0 ≤ wt(v) ≤ n. Let v = 10010. Then wt(v) = 2 and 0 ≤ 2 ≤ 5 is true. 2. wt(0) = 0. wt(00000) = 0 is true since 00000 has no 1’s. 3. If wt(v) = 0 then v = 0. For any word in v ∈ K5, if wt(v) = 0, then by definition there are no 1’s in v. That is all digits of v are 0. Thus v = 00000. So v = 0. 4. 0 ≤ d(v, w) ≤ n. Let v = 10010 and w = 01111. Then d(v, w) = 4 and it follows that 0 ≤ 4 = d(v, w) ≤ 5. 5. d(v, v) = 0. Let v = 10010. Then d(10010, 10010) = 0 since v and v cannot differ in any position. 6. If d(v, w) = 0, then v = w. For v, w ∈ Kn suppose d(v, w) = 0. This means that v and w cannot differ in any position. Thus v = w. 7. d(v, w) = d(w, v). d(v, w) is the number of positions in which v and w disagree. This is same as the number positions in which w and v disagree. Hence d(v, w) = d(w, v). 8. wt(v + w) ≤ wt(v) + wt(w). Let v = 10010 and w = 10000. Then wt(v + w) = wt(00010) = 1 and wt(v) + wt(w) = 2 + 1 = 3. Then wt(v + w) ≤ wt(v) + wt(w). 9. d(v, w) ≤ d(v, u) + d(u, w). Let v = 10010 and w = 10000 and u = 10101. Then d(v, w) = 1, d(v, u) = 3, d(u, w) = 2 and d(v, u) + d(u, w) = 5. So d(v, w) ≤ d(v, u) + d(u, w). 10. wt(av) = a · wt(v). Case 1: a = 0. Let v = 10010. Then wt(av) = wt(00000) = 0 and a.wt(v) = 0 · 2 = 0. In this case wt(av) = a · wt(v). Case 2: a = 1. wt(av) = wt(10010) = 2. and a.wt(v) = 1.wt(10010) = 2. That is wt(av) = a · wt(v). 11. d(av, aw) = a · d(v, w). Case 1: a = 0. Then d(av, aw) = d(00000, 00000) = 0, and a.d(v, w) = 0.d(v, w) = 0. Case 2: a = 1. Let v = 10010, w = 10001. Now d(av, aw) = d(10010, 10001) = 2 and a.d(v, w) = 1.d(10010, 10001) = 2. Thus d(av, aw) = a · d(v, w). 1.8.4 Prove each of the eleven rules defined in this section: 9

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur1. 0 ≤ wt(v) ≤ n for v ∈ Kn. Let v ∈ Kn. Then v is a word of length n. So v can have a minimum of zero 1s and a maximum of all 1’s. That is 0 ≤ wt(v) ≤ n. 2. wt(0) = 0. Zero word in Kn is a word of length n with all digits 0. That is 0 has no 1’s in it. Thus wt(0) = 0. 3. If wt(v) = 0 then v = 0. Let v be a word in Kn with wt(v) = 0, which means there are no 1’s in the word v. Thus all digits of v are 0’s. Hence v = 0. 4. 0 ≤ d(v, w) ≤ n. Let v, w ∈ Kn. Then v, w can differ at a minimum of zero positions and at a maximum of n positions(all positions). Thus 0 ≤ d(v, w) ≤ n. 5. d(v, v) = 0. Since v differ from v in no positions, we have d(v, v) = 0. 6. If d(v, w) = 0, then v = w. Let v ∈ Kn and let it be such that d(v, w) = 0. So v and w does not differ in any positions. So v = w. 7. d(v, w) = d(w, v). Let v, w be elements in Kn. Then d(v, w) is the number of positions in which v and w disagree, which is same as the number of positions in which w and v disagree. Thus d(v, w) = d(w, v). 8. wt(v + w) ≤ wt(v) + wt(w). Let v, w be elements in Kn. Suppose there are k ones in v and m ones in w. While adding v and w, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0, 1 + 1 = 0 are the possibilities. That is when there is a 1 in the ith position of v and w, it will contribute 1 to wt(v) and wt(w), bu 0 to wt(v + w). Hence wt(v + w) ≤ wt(v) + wt(w). 9. d(v, w) ≤ d(v, u) + d(u, w). Let u, v, w ∈ Kn.Then d(v, w) = wt(v + w) = wt(v + u + u + w)( Since u + u = 0) ≤ wt(v + u) + wt(w + u)( Rule 8) = d(v + u) + d(u, w) 10. wt(av) = a · wt(v). Let v ∈ Kn. Case 1: a = 0. Then wt(av) = wt(0 · v) = wt(0) = 0 and a · wt(v) = 0 · wt(v) = 0 So wt(av) = a · wt(v). Case 2: a = 1. Then wt(av) = wt(1 · v) = wt(v) = 1.wt(v) = a.wt(v). 11. d(av, aw) = a · d(v, w). Let a ∈ K and v, w be in Kn. Then using the rule 10, d(av, aw) = wt(av + aw) = wt(a(v + w)) = awt(v + w) = ad(v, w) 10

1.9 Maximum Likelihood Decoding 1.9.5 |M | = 2, n = 3 and C = {001, 101} is sent, when will IMLD conclude this correctly, and when will IMLD incorrectly conclude that 101 was sent? We construct the IMLD Table as follows: Received Error Pattern Decode w v 001 + w 101 + w 000 001 001 001∗ 101 001 010 001 011 000* 100 001 100 101 101 011* 111 101 110GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur101 111 010* 110 101 101 001* 100 000* 111 011* 110 010* So IMLD will conclude correctly that 001 was sent if 000, 001, 010, or 011 is received, and IMLD will conclude incorrectly that 101 was sent if 100, 101, 110 or 111 was received. 1.9.6 Let |M | = 3 and n = 3. For each word w ∈ K3 that would be received, find the word v in the code C = {000, 001, 110} which IMLD will conclude was sent. We construct the IMLD Table as follows: Received Error Pattern Decode w 000 + w 001 + w 110 + w v 000 000 001 001∗ 101 001 001 010 001 000∗ 111 —– 011 001 100 010 011 110 —– 101 011 010∗ 101 001 110 110 111 100 101 010 110 101 100∗ 011 110 111 000∗ 111 110 001∗ For 000 ∈ K3, IMLD will conclude 000 ∈ C was sent. For 001, 011, 101 ∈ K3, IMLD will conclude 001 in C was sent. For 110 and 111 in K3, IMLD will conclude 110 in C was sent. For 010 and 100 in K3, IMLD cannot conclude which message was sent. 1.9.7 Construct IMLD table for each of the following codes: (a) C = {101, 111, 011}: 11

Received Error Pattern Decode w 101 + w 111 + w 011 + w v 000 —– 001 101 111 011 —– 010 011 100 110 010 011 100 111 101 001∗ 011 101 110 100 000∗ 101 110 001∗ 011 111 101 111 000∗ 010 110 011 001∗ 101 111 010 000∗ 100 111 (b) C = {000, 001, 010, 011} GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturReceived000 + wError Pattern011 + wDecode w 000∗ v 001 + w 010 + w 011 000 001 000 010 001 010 010 001 001 011 000∗ 011 001 010 010 100∗ 011 000∗ 000∗ 011 011 101 010 001 111 000 100 110 101 110 110 001 101 111 100∗ 111 101 010 110 111 100∗ 100∗ 011 111 110 101 (c) C = {0000, 0001, 1110}. Received Error Pattern Decode w v 0000 + w 0001 + w 1110 + w 0000 0000 0001 0000∗ 0001 1110 0001 0010 0000 0011 0001 0000∗ 1111 0001 0100 0000 0101 0010∗ 0011 1100 0001 0110 1110 0111 0011 0010∗ 1101 —– 1000 0000 1001 0100∗ 0101 1010 0001 1010 1110 1011 0101 0100∗ 1011 —– 1100 1110 1101 0110 0111 1000∗ —– 1110 1110 1111 0111 0110 1001 1110 1000∗ 1001 0110 1001 1000∗ 0111 1010 1011 0100∗ 1011 1010 0101 1100 1101 0010∗ 1101 1100 0011 1110 1101 0000∗ 1111 1110 0001∗ (d) C = {0000, 1001, 0110, 1111}: 12

Received Error Pattern Decode w v 0000 + w 1001 + w 0110 + w 1111 + w 0000 0000∗ 0000 0001 1001 0110 0111 —– 0010 0001 1110 —– 0011 0010 1000 0111 1101 —– 0100 0011 1100 —– 0101 0100 1011 0100 1011 —- 0110 0101 1010 0110 0111 0110 1010 0101 1001 —– 1000 0111 1000 —– 1001 1000 1101 0010 0111 1001 1010 1001 0110 —– 1011 1010 1100 0011 0101 —– 1101 1011 0100 —– 1110 1101 1111 0000∗ 0010 —– 1100 1110 0001 —– 1111 1100 1110 0001 0011 1111 1111 0000∗ 0001 1110 0000∗ 1111 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 0011 1100 0010 1101 0100 1011 0111 1000 0101 1010 0110 1001 (e) C = {00000, 11111}: Received Error Pattern Decode w v 00000 + w 11111 + w 00000 00000 00001 00000∗ 11111 00000 00010 00000 00011 00001∗ 11110 00000 00100 00000 00101 00001∗ 11101 00000 00110 00000 00111 00011∗ 11100 11111 01000 00000 01001 00100∗ 11011 00000 01010 00000 01011 00101∗ 11010 11111 01100 00000 01101 00110∗ 11001 11111 01110 11111 01111 00111 11000∗ 11111 10000 00000 10001 01000∗ 10111 00000 10010 00000 10011 01001∗ 10110 11111 10100 00000 10101 01010∗ 10101 11111 01011 10100∗ 01100∗ 10011 01101 10010∗ 01110 10001∗ 01111 10000∗ 10000∗ 01111 10001∗ 01110 10010∗ 00101 10011 01100∗ 10100∗ 01011 10101 01010∗ 13

10110 10110 01001∗ 11111 10111 10111 01000∗ 11111 11000 11000∗ 00000 11001 00111 11111 11010 11001 00110∗ 11111 11011 11010 00101∗ 11111 11100 11011 00100∗ 11111 11101 11100 00011∗ 11111 11110 11101 00010∗ 11111 11111 11110 00001∗ 11111 11111 00000∗ GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(f ) C = {00000, 11100, 00111, 11011} Received Error Pattern Decode w v 00000 + w 11100 + w 00111 + w 11011 + w 00000 00000 00001 00000* 11100 00111 11011 00000 00010 00001* 11010 00000 00011 00010* 11101 00110 11001 00111 00100 00011 11000 00000 00101 00100* 11110 00101 11111 00111 00110 00101 11110 00111 00111 00110 11111 00100* 11101 00111 01000 00111 11100 00000 01001 01000* 11000 00011 10011 01010 01001 10010 —– 01011 01010 11001 00010* 10001 —– 01100 01011 10000* 11011 01101 01100 11010 00001* 10111 11100 01110 01101 10110 —– 01111 01110 11011 00000* 10101 —– 10000 01111 10100 00111 10001 10000* 10100 01111 01010 00000 10010 10001 01010 —– 10011 10010 10101 01110 01001 —– 10100 10011 01000* 11011 10101 10100 10110 01101 01111 11100 10110 10101 01110 —– 10111 10110 10101 01100 01101 —– 11000 10111 01100 00111 11001 11000 10000* 01011 00011 11100 11010 11001 00010* 11011 11011 11010 10001 01010 00001* 11011 11011 00000* 11011 10010 01001 10011 01000* 01100 10111 01101 10110 01110 10101 01111 10100 01000* 10011 01001 10010 01010 10001 01011 10000* 00100* 11111 00101 11110 00110 11101 00111 11100 14

11100 11100 00000* 11011 00111 11100 11101 11101 00001* 11010 00110 11100 11110 11110 00010* 11001 00101 11100 11111 11111 00011 11000 00100* 11011 (g) C = {00000, 11110, 01111, 10001}: Received Error Pattern Decode w v 00000 + w 11110 + w 01111 + w 10001 + w 00000 00000 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 00001 00000* 11110 01111 10001 —– 00010 00001 10000 00011 00010* 11111 01110 10011 00000 00100 00011 10010 —– 00101 00100* 11100 01101 10101 00110 00101 10100 00000 00111 00110 11101 01100 101111 —– 01000 00111 10110 —– 01001 01000* 11010 01011 11001 01010 01001 11000 01111 01011 01010 11011 01010 11011 00000 01100 01011 11010 01101 01100 11000 01001 11101 —– 01110 01101 11100 —– 01111 01110 11001 01000* 11111 01111 10000 01111 11110 —– 10001 10000 10110 00111 00001 01111 10010 10001 00000* —– 10011 10010 10111 00110 00011 01111 10100 10011 10001 —– 10101 10100 10100 00101 00101 10001 10110 10101 00100* —– 10111 10110 10101 00100* 00111 10001 11000 10111 00110 —– 11001 11000 10010 00011 01001 10001 11010 11001 01000* 11110 11011 11010 10011 00010* 01011 —– 11100 11011 01010 —– 11101 11100 10000 00001 01101 10001 11110 11101 01100 11110 11111 11110 10001 00000* 01111 —– 11111 01110 11110 01110 11111 —– 11110 01111 11110 —– 01100 11101 11100 00010* 01010 11011 01011 11010 01000* 11001 01001 11000 00110 10111 00111 10110 00100* 10101 00101 10100 00010* 10011 00011 10010 00000* 10001 00001 10000 15

(h) C = {000000, 101010, 010101, 111111} Received Error Pattern Decode w v 000000 + w 101010 + w 010101 + w 111111 + w 000000 000000∗ 000000 000001 101010 010101 111111 000000 000010 000001* 111110 000000 000011 000010* 101011 010100 111101 000000 000100 000011* 111100 000000 000101 000100* 101000 010111 111011 010101 001110 000101 111010 101010 001111 001110 101001 010110 110001 111111 010000 001111 110000∗ 000000 010001 010000∗ 101110 010001 010101 010010 101111 000000 010011 010001 101111 010000* 1001110 010101 010100 010010∗ 101101 010101 010101 100100∗ 011011 101100 010101 010110 010011 101011 010101 010111 010100 100101 011010 101010 010101 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur011000010101 101001 000000 011001 010110 111010 000101 101000 010101 011010 010111 100111 101010 011011 011000∗ 111011 000100∗ 100110 111111 011100 100101 010101 011101 011001 111000 000111 100100∗ 010101 011110 011010 111111 011111 011011 111001 000110∗ 100011 111111 100000 011100 100010 000000 100001 011101 111110 000001∗ 100001∗ 000000 100010 011110 100000∗ 101010 100011 011111 111111 000000∗ 101010 100100 100000∗ 011111 000000 100101 100001∗ 111100 000011∗ 011110 010101 100111 011101 111111 101000 100010 111101 000010∗ 011100 101010 101001 100011 011011 101010 101010 100100* 110010 001101 011010 101010 101011 100101 011000* 101010 101100 100111 110011 001100∗ 010111 101010 101101 101000 010110 111111 101110 101001 110000∗ 001111 010101 101010 101111 101010 010100 111111 110000 101011 110001 001110 010011 000000 110001 101100 010010* 010101 101101 110110 001001∗ 010001 101110 010000* 101111 110111 001000∗ 001111 110000* 001110 110001 110100 001011 110101 001010 001010 110101 001011 110100 001000* 110111 001001* 110110 001110 110001 001111 110000* 001101 110010 000010* 111101 000011* 111100 000000* 111111 000001* 111110 000110* 111001 000111 111000 000100* 111011 000101 111010 011010 100101 011011 100100* 16

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur110010110010011000*100111001101101010 110011 110011 011001 100110 001100* 111111 110100 110100 01110 100001* 001011 010101 110101 110101 011111 100000* 001010 010101 110110 110110 011100 100011 001001* 111111 110111 110111 011101 100010 001000* 111111 111000 111000 010010* 101101 000111 101010 111001 111001 010011 101100 000110* 111111 111010 111010 010000* 101111 000101 101010 111011 11011 010001 101110 000100* 111111 111100 111100 010110 101001 000011* 111111 111101 111101 010111 101000 000010* 111111 111110 111110 010100 101011 000001* 111111 111111 111111 010101 101010 000000* 111111 1.10 Reliability of MLD 1.10.2 Suppose p = .90, |M | = 2, n = 3, and C = {001, 101}. (a) If v = 001 is sent, ind the probability that IMLD will correctly conclude this after one transmission. (b) Repeat part (a) for v = 101. Received Error pattern Decode w 001+w 101+w v 000 001* 101 001 000* 100 001 010 011* 111 001 011 010* 110 001 100 001 101 101 001* 101 110 100 000* 101 111 111 011* 101 110 010* 101 Table 1.5: The IMLD Table (a) From the IMLD table 1.5, we see that v = 001 is decoded in the first four rows, so L(001) = {000, 001, 010, 011}. 17

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturThus, θp(C, 001) = φp(000, 001) + φp(001, 001) + φp(010, 001) + φp(011, 001) = p2(1 − p) + p3 + p(1 − p)2 + p2(1 − p) = p3 + p(1 − p)2 + 2p2(1 − p) = .90 (b) From the IMLD table 1.5, we see that v = 101 is decoded in the last four rows, so L(101) = {100, 101, 110, 111}. Thus, θp(C, 101) = φp(101, 100) + φp(101, 101) + φp(101, 110) + φp(101, 111) = p2(1 − p) + p3 + p(1 − p)2 + p2(1 − p) = p3 + p(1 − p)2 + 2p2(1 − p) = .90 1.10.4 Suppose p = .90 and C = {000, 001, 110} as in Exercise 1.9.6. If v = 110 is sent, find the probability that IMLD will correctly conclude this, and the probability that IMLD will incorrectly conclude that 000 was sent: Suppose v = 110 was sent. v = 110 is decoded in the last two rows. Then L(110) = {110, 111}. Thus θp(C, 110) = φp(110, 110) + φp(110, 111) = p3(1 − p)0 + p2(1 − p) = p2 Since p = .90, θ(C, 110) = 0.92 = 0.81. Thus the probablility that IMLD will correctlycon- clude 110 was sent is 0.81. Now if 000 is received from IMLD table, it can be inferred that IMLD decode it as 000. Since no other word in K3, IMLD will conclude 000 was sent. Thus l(000) = {000}. Thus θp(C, 000) = φp(000, 000) = p3(1 − p)0 = p3 Now p = .90. So θp(C, 000) = 0.729. That is the probability that IMLD will incorrectly conclude 000 was sent is 0.729. 1.10.5 For each of the following codes C calculate θP (C, v for each v in C using p = .90. The IMLD tables for these codes were constructed in Exercise 1.9.7 18

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(a) C = {101, 111, 011}. i. Let v = 101, then L(v) = {100, 101}. θp(C, v) = φp(100, 101) + φp(101, 101) = p2(1 − p) + p3(1 − p)0 = p2 − p3 + p3 = p2 That is θ0.90(C, 101) = 0.81. ii. Let v = 111, then L(v) = {110, 111}. θp(C, v) = φp(110, 111) + φp(111, 111) = p2(1 − p) + p3 = p2 − p3 + p3 = p2 That is θ0.90(C, 111) = 0.81. iii. Let v = 011, then L(v) = {010, 011}. θp(C, v) = φp(010, 011) + φp(011, 011) = p2(1 − p) + p3 = p2 − p3 + p3 = p2 That is θ0.90(C, 011) = 0.81. (b) C = {000, 001, 010, 011} i. Let v = 000, then L(v) = {000, 100}. θp(C, v) = φp(000, 000) + φp(000, 100) = p3 + p2(1 − p) = p2 − p3 + p3 = p2 That is θ0.90(C, 000) = 0.81. ii. Let v = 001, then L(v) = {001, 101}. θp(C, v) = φp(001, 001) + φp(001, 101) = p3 + p2(1 − p) = p2 − p3 + p3 = p2 19

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturThat is θ0.90(C, 001) = 0.81. iii. Let v = 010, then L(v) = {010, 110}. θp(C, v) = φp(010, 010) + φp(010, 110) = p3 + p2(1 − p) = p2 That is θ0.90(C, 010) = 0.81. iv. Let v = 011, then L(v) = {011, 111}. θp(C, v) = φp(011, 011) + φp(011, 111) = p3 + p2(1 − p) = p2 That is θ0.90(C, 011) = 0.81. (c) C = {0000, 0001, 1110} i. Let v = 0000, then L(v) = {0000, 0010, 0100, 1000}. θp(C, v) = φp(0000, 0000) + φp(0010, 0000) + φp(0100, 0000) + φp(1000, 0000) = p4 + p3(1 − p) + p3(1 − p) + p3(1 − p) = p4 + 3p3(1 − p) That is θ0.90(C, 0000) = 0.8748. ii. Let v = 0001, then L(v) = {0001, 0011, 0101, 1001}. θp(C, v) = φp(0001, 0001) + φp(0001, 0011) + φp(0001, 0101) + φp(0001, 1001) = p4 + p3(1 − p) + p3(1 − p) + p3(1 − p) = p4 + 3p3(1 − p) That is θ0.90(C, 0001) = 0.8748. iii. Let v = 1110, then L(v) = {0110, 1010, 1100, 1110, 1111}. θp(C, v) = φp(0110, 1110) + φp(1010, 1110) + φp(1100, 1110) + φp(1110, 1110) +φp(1110, 1111) = p3(1 − p) + p3(1 − p) + p3(1 − p) + p4 + p3(1 − p) = p4 + 4p3(1 − p) That is θ0.90(C, 1110) = 0.9477. 20

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(d) C = {0000, 1001, 0110, 1111} i. Let v = 0000, then L(v) = {0000}. θp(C, v) = φp(0000, 0000) = p4 That is θ0.90(C, 0000) = 0.6561. ii. Let v = 1001, then L(v) = {1001}. θp(C, v) = φp(1001, 1001) = p4 That is θ0.90(C, 1001) = 0.6561. iii. Let v = 0110, then L(v) = {0110}. θp(C, v) = φp(0110, 0110) = p4 That is θ0.90(C, 0110) = 0.6561. iv. Let v = 1111, then L(v) = {1111}. θp(C, v) = φp(1111, 1111) = p4 That is θ0.90(C, 1111) = 0.6561. (e) C = {00000, 11111} i. Let v = 00000. Then L(v) = {00000, 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001, 01010, 01100, 10000, 10001, 10010, 10100, 11000}. θp(C, 00000) = φp(00000, v) + φp(00001, v) + φp(00010, v) + φp(00011, v) + φp(00100, v) +φp(00101, v) + φp(00110, v) + φp(01000, v) + φp(01001, v) + φp(01010, v) +φp(01100, v) + φp(10000, v) + φp(10001, v) + φp(10010, v) + φp(10100, v) +φp(11000, v) = p5 + p4(1 − p) + p4(1 − p) + p3(1 − p)2 + p4(1 − p) + p3(1 − p)2 +p3(1 − p)2 + p4(1 − p) + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 +p4(1 − p) + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 = p5 + 5p4(1 − p) + 10p3(1 − p)2 That is θ0.90(C, 00000) = 0.99144. 21

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturii. Let v = 11111. Then L(v) = {00111, 01011, 01101, 01110, 10011, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101, 11110, 11111}. θp(C, 11111) = φp(00111, v) + φp(01011, v) + φp(01101, v) + φp(01110, v) + φp(01111, v) +φp(10011, v) + φp(10101, v) + φp(10110, v) + φp(10111, v) + φp(11001, v) +φp(11010, v) + φp(11011, v) + φp(11100, v) + φp(11101, v) + φp(11110, v) +φp(11111, v) = p5 + p4(1 − p) + p4(1 − p) + p3(1 − p)2 + p4(1 − p) + p3(1 − p)2 +p3(1 − p)2 + p4(1 − p) + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 +p4(1 − p) + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 + p3(1 − p)2 = p5 + 5p4(1 − p) + 10p3(1 − p)2 That is θ0.90(C, 11111) = 0.99144. (f ) C = {00000, 11100, 00111, 11011} i. Let v = 00000. Then L(v) = {00000, 00001, 00010, 00100, 01000, 10000} θp(C, v) = φp(00000, v) + φp(00001, v) + φp(00010, v) + φp(00100, v) + φp(01000, v) +φp(10000, v) = p5 + p4(1 − p) + p4(1 − p) + p4(1 − p) + p4(1 − p) + p4(1 − p) = p5 + 5p4(1 − p) That is θ0.90(C, 00000) = 0.91854. ii. Let v = 11100. Then L(v) = {01100, 10100, 11000, 11100, 11101, 11110} θp(C, v) = φp(01100, v) + φp(10100, v) + φp(11000, v) + φp(11100, v) + φp(11101, v) +φp(11110, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 + p4(1 − p) + p4(1 − p) = p5 + 5p4(1 − p) That is θ0.90(C, v) = 0.91854. iii. Let v = 00111. Then L(v) = {00011, 00101, 00110, 00111, 01111, 10111}. θp(C, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 + p4(1 − p) + p4(1 − p) = p5 + 5p4(1 − p) That is θ0.90(C, v) = 0.91854. iv. Let v = 11011. Then L(v) = {01011, 10011, 11001, 11010, 11011, 11111} θp(C, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 + p4(1 − p) + p4(1 − p) = p5 + 5p4(1 − p) That is θ0.90(C, v) = 0.91854. (g) C = {00000, 11110, 01111, 10001} 22

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturi. Let v = 00000, then L(v) = {00000, 00010, 00100, 01000} θp(C, v) = p5 + p4(1 − p) + p4(1 − p) + p4(1 − p) = p5 + 3p4(1 − p) That is θ0.90(C, v) = 0.78732. ii. Let v = 11110, then L(v) = {10110, 11010, 11100, 11110} θp(C, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 = p5 + 3p4(1 − p) That is θ0.90(C, v) = 0.78732. iii. Let v = 01111, then L(v) = {00111, 01011, 01101, 01111} θp(C, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 = p5 + 3p4(1 − p) That is θ0.90(C, v) = 0.78732. iv. Let v = 10001, then L(v) = {10001, 10011, 10101, 11001} θp(C, v) = p4(1 − p) + p4(1 − p) + p4(1 − p) + p5 = p5 + 3p4(1 − p) That is θ0.90(C, v) = 0.78732. (h) C = {000000, 101010, 010101, 111111} i. Let v = 000000, then L(v) = {000000, 000001, 000010, 000011, 000100, 000110, 001000, 001001, 001100, 010000, 010010 011000, 100000, 100001, 100100, 110000} θp(C, v) = φp(000000, v) + φp(000001, v) + φp(000010, v) + φp(000011, v) + φp(000100, v) +φp(000110, v) + φp(001000, v) + φp(001001, v) + φp(001100, v) + φp(010000, v) +φp(010010, v) + φp(011000, v) + φp(100000, v) + φp(100001, v) + φp(100100, v) +φp(110000, v) = p6 + p5(1 − p) + p5(1 − p) + p5(1 − p) + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p4(1 − p)2 = p6 + 5p5(1 − p) + 9p4(1 − p)2 That is θ0.90(C, v) = 1.476225. ii. Let v = 101010, then L(v) = {001010, 001011, 001110, 011010, 100010, 100011, 100110, 101000, 101001, 101010, 101011, 101100, 101110, 110010, 111000, 111010} θp(C, v) = p6 + p5(1 − p) + p5(1 − p) + p5(1 − p) + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p4(1 − p)2 = p6 + 5p5(1 − p) + 9p4(1 − p)2 That is θ0.90(C, v) = 1.476225. 23

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturiii. Let v = 010101, then L(v) = {000101, 000111, 001101, 010001, 010011, 010100, 010101, 010110, 010111, 011001, 011100, 011101, 10010, 110001, 110100, 110101} θp(C, v) = p6 + p5(1 − p) + p5(1 − p) + p5(1 − p) + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p4(1 − p)2 = p6 + 5p5(1 − p) + 9p4(1 − p)2 That is θ0.90(C, v) = 1.476225. iv. Let v = 111111, then L(v) = {001111, 011011, 011110, 011111, 100111, 101101, 101111, 110011, 110110, 110111, 111001, 111011, 111100, 111101, 111110, 111111} θp(C, v) = p6 + p5(1 − p) + p5(1 − p) + p5(1 − p) + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 + p4(1 − p)2 + p5(1 − p) + p4(1 − p)2 +p4(1 − p)2 + p4(1 − p)2 = p6 + 5p5(1 − p) + 9p4(1 − p)2 That is θ0.90(C, v) = 1.476225. 1.11 Error-Detecting Codes 1.11.2 Let C = {001, 101, 110}. Determine whether C will detect the error patterns (a) 011. Calculate v + 011 for v ∈ C. 001 + 011 = 010 101 + 011 = 110 belongs to C 110 + 011 = 101 Thus C will not detect the error pattern 011. (b) 001. 001 + 001 = 000 101 + 001 = 100 110 + 001 = 111 Since 000, 100, 111 ∈/ C, it follows that C detect the error pattern 001. (c) 000. Since 001 + 000 = 001 ∈ C, it follows that C will not detect the error pattern 000. 1.11.3 For each of the following codes C determine whether or not C detects u: 24

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(a) C = {00000, 10101, 00111, 11100} i. u = 10101. Since 10101 + 00000 = 10101 ∈ C, it follows that C wil not detect 10101. ii. u = 01010. 00000 + 01010 = 01010 10101 + 01010 = 11111 00111 + 01010 = 01101 11100 + 01010 = 10110 Since v + w ∈/ C, ∀w ∈ C, follows that C will detect 01010. iii. u = 11011. Since 11011 + 00111 = 11100 and 11100 ∈ C, it follows that C will not detect 11011. (b) C = {1101, 0110, 1100} i. u = 0010 1101 + 0010 = 1111 0110 + 0010 = 0100 1100 + 0010 = 1110 Since 1111, 0100, 1110 ∈/ C, implies that C will detect 0010. ii. u = 0011. 1101 + 0011 = 1110 0110 + 0011 = 0101 1100 + 0011 = 1111 Since 1110, 0101, 1111 ∈/ C, implies that C will detect 0010. iii. u = 1010. Since 0110 + 1010 = 1100 ∈ C, follows that C will not detect 1010. (c) C = {1000, 0100, 0010, 0001} i. u = 1001. Since 1000 + 1001 ∈ C, follows that C will not detect 1001. ii. u = 1110. 1000 + 1110 = 0110 0100 + 1110 = 1010 0010 + 1110 = 1100 0001 + 1110 = 1111 Since 0110, 1010, 1100, 1111 ∈/ C, it follows that C will detect 1110. 25

iii. u = 0110. Since 0100 + 0110 = 0010 ∈/ C, implies that C will not detect 0110. 1.11.4 Which error patterns will the code C = Kn detect? C = Kn will not detect any error pattern. Since if u is an error pattern u + u = 0 ∈ Kn. 1.11.5 (a) Let C be a code which contains a the zero word as a codeword. Prove that if the error pattern u is a codeword, then C will not detect u. Let 0 ∈ C and u ∈ C be an error pattern. Then since u + u = 0 ∈ C, it can be seen that C will not detect u. (b) Prove that no code will detect the zero error pattern u = 0. Let C be any code and w ∈ C. Since 0 + w = w ∈ C, follows that C will not detect u = 0. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 1.11.7 Determine the error patterns detected by each code in Exercise 1.9.7 by using the IMLD tables constructed there. Consider the IMLD table in Exercise 1.9.7. (a) C = {101, 111, 011}. Received words are the error patterns. If these error patterns when added with elements in C (that is the middle columns of IMLD) results in any word in C, corresponding error pattern will not be detected by C. Otherwise, C will detect the corresponding error patterns. C cannot detect 000 because the first row contains elements in C. The second row consists of 100, 110, 010. None of them are in C. Thus C will detect the corresponding error pattern 001. In the third row 111 is there and 111 ∈ C. So C will not detect the error pattern 010. 110, 100, 000 ∈/ C. Thus C will detect the error pattern 011. Continuing like this it can be shown that the error patterns detected by C are 101, 111 different from error patterns discusses in this problem. So the error patterns detected by C are 001, 011, 101, 111. (b) C = {000, 001, 010, 011} will detect 100, 101, 110, 111. (c) C = {0000, 0001, 1110} will detect the following error patterns: 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101. (d) C = {0000, 1001, 0110, 1111}, will detect the following error patterns: 0001, 0010, 0011, 0100, 0101, 0111, 1000, 1010, 1011, 1101, 1110, 1100 (e) C = {00000, 11111} will detect all error patterns in K5 \\ C. (f ) C = {00000, 11100, 00111, 11011}, will detect the following error patterns: 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11101, 11110, 11111. (g) C = {00000, 11110, 01111, 10001}, will detect the following error patterns: 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 10000, 10010, 10011, 10100, 10101, 10110, 10111, 11100, 11001, 11010, 11011, 11100, 11101, 11111. (h) C = {000000, 101010, 010101, 111111}, will detect the following patterns. 000001, 000010, 000011, 000100, 000101, 000110, 000111, 001000, 001001, 001010, 26

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur001011, 001100, 001101, 001110, 001111, 010000, 010001, 010010, 010011, 010100, 010110, 010111, 011000, 011001, 011010, 011010, 011011, 011100, 011101, 011110, 011111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101011, 101100, 101101, 101110, 101111, 110000, 110001, 110010, 110011, 110100, 110101, 110110, 110111, 111000, 111001, 111010, 111011, 111100, 111101, 111110. 1.11.10 Find the error patterns detected by each of the following codes and compare your an- swers with those Exercises 1.11.7. (a) C = {101, 111, 011}: C will detect all error patterns in K3 \\ {000, 010, 110, 100}. In Exercise 1.11.7, we saw that C will detect the error patterns 001, 011, 101, 111. Hence they both are the same. Similarly we can prove the rest. (b) C = {000, 001, 010, 011} (c) C = {0000, 0001, 1110} (d) C = {0000, 1001, 0110, 1111} (e) C = {00000, 11111} (f ) C = {00000, 11100, 00111, 11011} (g) C = {00000, 11110, 01111, 10001} (h) C = {000000, 101010, 010101, 111111} 1.11.12 Find the distance of each of the following codes. Distance C = min{d(v, w) : v, w ∈ C, v = w}. (a) C = {101, 111, 011}: distance of C = 1. (b) C = {000, 001, 010, 011}: distance of C = 1. (c) C = {0000, 0001, 1110}: distance of C = 1. (d) C = {0000, 1001, 0110, 1111}: distance of C = 2. (e) C = {00000, 11111}: distance of C = 5. (f ) C = {00000, 11100, 00111, 11011}: distance of C = 3. (g) C = {00000, 11110, 01111, 10001}: distance of C = 2. (h) C = {000000, 101010, 010101, 111111}: distance of C = 3. 1.11.13 Find the distance of the code formed by adding a parity check digit to Kn. Let C denote the code obtained from Kn by adding a parity check digit to Kn. Let v, w be code words in C with v = w. Then wt(v) and wt(w) are even. Let wt(v) = 2r and wt(w) = 2s. Suppose there are m number of 1’s common to v and w. Then wt(v + w) = wt(v) + wt(w) − 2m = 2r + 2s − 2m = 2(r + s − m) That is d(v, w) = wt(v + w) = 2(r + s − m), an even number. 11000 . . . 0 and 00000 . . . 0 are in C. Thus d(000 . . . 0, 11000 . . . 0) = 2. That is d(v, w) is even for v, w ∈ C with v = w and we got v = 0 and w = 11000 . . . 0 ∈ C with d(v, w) = 2. Hence the distance of C is 2. 27

1.11.17 The code C = {0000, 1010, 0111} has distance d = 2. Using Exercise 1.11.5, show that the error pattern 1010 is not detected. Show that this is the only error pattern of weight 2 that C does not detect. Find all error patterns that C detects. C will detect all error patterns in Kn\\{0000, 1010, 0111, 1101}. That is C will detect 1100, 1001, 0110, 0101, 0 all error patterns of weight 2 other than 1010. 1.11.18 Find all error patterns which the code C3 of Example 1.3.3 will detect. Note that C3 is a single error-detecting code. Thus C3 will detect all words in K3 \\ {011, 101, 110}. Note that C3 will detect all words of weight. Thu C3 will detect all signle error-detecting code. 1.11.19 For each code C in Exercise 1.11.12 find the error patterns which Theorem 1.11.14 gu- ranties C will detect. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur (a) d = 1. Thus by the theorem which says that a code with distance d will atleast detect all non-zero- error patterns of weight less than or equal to d − 1, none of the codeword is gurantied to be detected. (b) d = 1. Thus none. (c) d = 1. Thus none. (d) d = 2. Thus C will detect 1000, 0100, 0010 and 0001 (e) d = 5. Thus C will detect all error patterns of weight 1, 2, 3 or 4. (f ) d = 3. Thus C will detect all error patterns of weight 1 or 2. (g) d = 2. Thus, C will detect 10000, 01000, 00100, 00010 and 00001. (h) d = 3. Thus C will detect all error patterns of weight 1 or 2. 1.11.20 Let C be the code consisting of all words of length 4 which have even weight. Find the error patterns C detects. 1.12 Error-Correcting Codes 1.12.5 Let C = {001, 101, 110}. Does C correct the error pattern u = 100? What about u = 000? We construct only the three rows of the IMLD table where 100 appears. We find the received words from v + 100 for v ∈ C. Received Error Pattern Decode w v 101 001 + w 101 + w 110 + w 001 010 100 000* 011 000* 100 111 011 111 100* u = 100 does not receive asterisk in every column. Thus C does not correct 100. Now for u = 000 received words that will correspond to 000 as one of its error pattern are 001, 101, 110. The IMLD is: 28

Received Error Pattern Decode w v 001 001 + w 101 + w 110 + w 101 011 110 000* 100 111 101 110 100 000* 011 111 011 000* 000 receives an asterisk in every column. Thus C corrects u = 000. 1.12.6 Prove that the same error pattern cannot occur more than once in a given row of an IMLD table. Suppose that the error pattern u occur more than once in a given row in an IMLD table. Then u = v1 + w and u = v2 + w for some received word w and for some v1, v2 ∈ C with v1 = v2. Then u = v1 + w = v2 + w implies v1 = v2, a contradiction to the assumption of v1 and v2. Thus our assumption is wrong and hence the same error pattern cannot occur more than once in a give row of an IMLD table. 1.12.7 Prove that the zero error pattern is always corrected. If we consider the IMLD table where 000 . . . 0, the zero error pattern occur, then zero error pattern being the lest weight among any other word will receive an asterisk and hence C will correct zero error pattern. 1.12.8 Which error patterns will the code C = Kn correct? C will correct only the zero error pattern because, corresponding to each received word w in kn, w is in C and the error pattern w + w = 0 will always appear in each row exactly once and always get an asterisk. So no other error pattern in Kn can receive an asterisk and hence C will only correct the zero error pattern. 1.12.12 For each of the following codes C (a) determine the error patterns that C will correct (the IMLD tables for these codes were constructed in Exercise 1.9.7, and (b) find the error patterns that Theorem 1.12.9 guaranties that C corrects. a. C = {101, 111, 011} GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur i. From the IMLD table in Exercise 1.9.7, we conclude that C corrects an error pattern u if u receives an asterisk in all columns. Thus C will correct 000 and 001. ii. Theorem 1.12.9 states that a code C corrects all error pattern with weight less than or equal to (d−1) where d is the distance of the ode C. Here d = 1 so 000 2 will be corrected by C. b. C = {000, 001, 010, 011} i. C will correct 000 and 100. ii. Here d = 1 so 000 will be corrected by C. c. C = {0000, 0001, 1110} i. C will correct 0000, 0010, 0100 and 1000 ii. Here d = 1 so 000 will be corrected by C. d. C = {0000, 1001, 0110, 1111} 29

i. C will correct 0000 ii. Here d = 2 so (d−1) = 0 so 000 will be corrected by C. 2 e. C = {00000, 11111} i. C will correct 00000, 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001, 01010, 01100, 10000, 10001, 10010, 10100, 11000. ii. Here d = 5 so (d−1) = 2 so C will correct all error patterns of weight 0, 1 or 2. 2 f. C = {00000, 11100, 00111, 11011} i. C will correct 00000, 10000, 01000, 00100, 00010, 00001. ii. Here d = 3 so (d−1) = 1 so C will correct all error patterns of weight 0 or 1. 2 g. C = {00000, 11110, 01111, 10001} i. C will correct 00000, 00010, 00100 and 01000 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur ii. Here d = 2 so (d−1) = 0 so C will correct 00000. 2 h. C = {000000, 101010, 01010, 111111} i. C will correct 000000, 000001, 000010, 000011, 000100, 000110, 001000, 001001, 001100, 01000 100000, 100001, 100100, 110000. ii. Here d = 3 so (d−1) = 1 so C will correct all error patterns of weight 0 or 1. 2 1.12.13 Use the technique described in Example 1.12.11 to decide whether or not the following error patterns are corrected by the accompanying code. (a) C = {000000, 100101, 010110, 001111, 110011, 101010, 011001, 111100} i. u = 001000. Construct IMLD table where u = 001000 appear. u + v where v ∈ C will give us all received words where u occur as an error pattern. All columns with 001000 has asterisk on u = 001000. Thus IMLD will correct the error pattern u. ii. u = 000010 iii. u = 100100 (b) C = {1001011, 0110101, 1110010, 1111111} i. u = 0100000 ii. u = 0101000 iii. u = 1100000 1.12.14 For each code in Exercise 1.12.12, find an error pattern of weight (d − 1)/2 + 1 that C does not correct. a) d = 1 and (d − 1)/2 + 1 = 1. From IMLD table in Exercise 1.9.7, we find a word of weight 1 that C will not correct. 100 does not receive an asterisk. Hence C will not correct 100. b) d = 1 and (d − 1)/2 + 1 = 1. From IMLD C will not correct 001. c) d = 1 and (d − 1)/2 + 1 = 1. From IMLD C will not correct 0001. d) d = 1 and (d − 1)/2 + 1 = 1. From IMLD C will not correct 0001. 30

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itture) d = 5 and (d − 1)/2 + 1 = 3. From IMLD C will not correct 00111. f ) d = 3 and (d − 1)/2 + 1 = 2. From IMLD C will not correct 00011. g) d = 2 and (d − 1)/2 + 1 = 1. From IMLD C will not correct 00001. h) d = 3 and (d − 1)/2 + 1 = 2. From IMLD C will not correct 000101. 1.12.15 Let C be the code consisting of all words of length 4 having even weight. Determine the error patterns that C will correct. From the first three rows of IMLD itself we can conclude C will only correct 0000. 1.12.16 Let u1 and u2 be error patterns of length n, and assume that u1 and u2 agree at least in the positions where a 1 occurs in u1. Prove that if a code C will correct u2, then C will also correct u1. 31

Chapter 2 Linear Codes GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.1 Linear Codes 2.1.1 Determine which of the following codes are linear. (a) C = {101, 111, 011}. Since 000 ∈/ C, its not a linear code. (b) C = {000, 010, 001, 011}. A linear code. (c) C = {0000, 0001, 1110}. Since 0001 + 1110 = 1111 ∈/ C, its not a linear code. (d) C = {0000, 1001, 0110, 1111}. A linear code. (e) C = {00000, 11111}. A linear code (f ) C = {00000, 11100, 00111, 11011}. A linear code (g) C = {00000, 11110, 01111, 10001}. A linear code. (h) C = {000000, 101010, 010101, 111111}. A linear code 2.1.2 Show that C = {0000, 1100, 0011, 1111} is a linear code and that its distance is d = 2. We can easily show that C is linear. Each word in C will contain either no 1’s or an even number of ones and 1100 is in C. Hence d = 2. 2.1.3 Prove the distance of each linear code in Exercise 2.1.1. Check the answers with exer- cise 1.11.12. (a) C = {101, 111, 011} d = 1. (b) C = {000, 010, 001, 011} d = 2. 32

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(c) C = {0000, 0001, 1110} d = 1. (d) C = {0000, 1001, 0110, 1111} d = 2. (e) C = {00000, 11111} d = 5. (f ) C = {00000, 11100, 00111, 11011} d = 3. (g) C = {00000, 11110, 01111, 10001} d = 2. (h) C = {000000, 101010, 010101, 111111} d = 6. 2.1.4 Prove that the distance of a linear code is the weight of the nonzero codeword of least weight. Let C by any linear code and 0 = v ∈ C. Choose v such that wt(v) ≤ wt(w), ∀w ∈ C. Now the distance of a code C is given by d = min{d(u, w) : u, w ∈ C}. That is d = min{wt(u + w) : u, w ∈ C}. Since C is a linear code, for any u and w in C, u + w ∈ C. Therefore d = min{wt(w) : w ∈ C} = wt(v), where v a nonzero codeword of least weight. Thus the distance of a linear code is the weight of the nonzero codeword of least weight. 2.2 Two Important Subspaces 2.2.3 For each of the following sets S, list the elements of the linear code < S >: (a) S = {010, 011, 111} C =< S >= {000, 010, 011, 111, 001, 101, 100, 110} = K3 (b) S = {1010, 0101, 1111} C =< S >= {0000, 1010, 0101, 1111}. (c) S = {0101, 1010, 1100} C =< S >= {0000, 0101, 1010, 1100, 1111, 1001, 0110, 0011}. (d) S = {1000, 0100, 0010, 0001} C =< S >= K4. (e) S = {11000, 01111, 11110, 01010} C =< S >= {00000, 11000, 01111, 11110, 01010, 10111, 00110, 10010, 10001, 00101, 10100, 01001, 11101, 11011, 01100, 00011}. (f ) S = {10101, 01010, 11111, 00011, 10110} C =< S >= {00000, 10101, 01010, 11111, 00011, 10110, 01001, 11100}. 2.2.4 Construct examples in K5 of each of the following rules (a) u · (v + w) = u · v + u · w. Choose u = 10000, v = 11000, w = 00111 and choose a = 0, 1 33

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(b) a(v · w) = (av) · w = v · (aw) Choose u = 10000, v = 11000, w = 00111 and choose a = 0, 1 2.2.5 Prove that the two rules in Exercise 2.2.4 hold in Kn (a) u · (v + w) = u · v + u · w. Let u = u1u2 · · · un, v = v1v2 · · · vn, w = w1w2 · · · wn ∈ Kn. u · (v + w) = u1u2 · · · un(v1v2 · · · vn + w1w2 · · · wn) = u1u2 · · · un(v1 + w1, v2 + w2, · · · , vn + wn) = u1(v1 + w1) + u2(v2 + w2) + · · · + un(vn + wn) = (u1v1 + u2v2 + · · · + unvn) + (u1w1 + u2w2 + · · · + unwn) = u·v+u·w (b) a(v · w) = (av) · w = v · (aw) a(v · w) = a(v1w1 + v2w2 + · · · + vnwn) = av1w1 + av2w2 + · · · + avnwn = (av) · w = v · (aw) 2.2.7 Find the dual code C⊥ for each of the codes C =< S > in the Exercise 2.2.3. Choose an arbitrary code v = v1v2 · vn ∈ Kn and find the dot product with each elements in C or S. Solve vj, will give us an answer. (a) S = {010, 011, 111}: C⊥ = {000}. (b) S = {1010, 0101, 1111}: C⊥ = {0000, 0101, 1010, 1111}. (c) S = {0101, 1010, 1100} C⊥ = {0000, 1111}. (d) S = {1000, 0100, 0010, 0001}. C⊥ = {0000}. (e) S = {11000, 01111, 11110, 01010}. C⊥ = {00000, 11111}. (f ) S = {10101, 01010, 11111, 00011, 10110}. C⊥ = {00000, 01111}. 2.2.8 Find an example of a nonzero word v such that v · v = 0. What can you say about the weight of such a word? Any nonzero word v such that v · v = 0 must have an even weight. 2.2.9 For any subset S of a vector space V , (S⊥)⊥ = S. Use the example above to construct an example of this fact in K4. We leave it as an exercise. 34

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur2.2.10 Prove that < S >⊆ (S⊥)⊥. In fact (S⊥)⊥ =< S >; for a linear code C, this means (C⊥)⊥ = C. Let S = {v1, v2, . . . , vn}. Let v ∈< S >. Therefore v = a1v1 + a2v2 + · · · + anvn Now for any w ∈ S⊥,we have w · vi = 0 for i = 1, 2, . . . , n. w · v = w · (a1v1 + a2v2 + · · · + anvn) = w · (a1v1) + w · (a2v2) + · · · + w · (anvn) = a1(w · v1) + a2(w · v2) + · · · + an(w · vn) = a1 · 0 + a2 · 0 + · · · + an · 0 =0 Hence v ∈ (S⊥)⊥. So < S >⊆ (S⊥)⊥. 2.3 Independence, Basis and Dimension 2.3.4 Test each of the following sets for linear independence. If the set is linearly dependent, extract from S a largest linearly independent subset. (a) S = {1101, 1110, 1011} Let a,b,c,d be scalars such that a(1101) + b(1110) + c(1011) = 0000 Equating components on both sides yields the equations a + b + c = 0, a + b = 0, b + c = 0, a + c = 0 These equations give a=b=c=0. Therefore S is a linearly independent set. (b) S = {101, 011, 110, 010} Let a,b,c,d be scalars such that a(101) + b(011) + c(110) + (010) = 000 Equating the components yields the equations a+c=0, b+c+d=0, a+b=0 This gives a=b=c and d=0. Thus we an choose a=b=c=1. Therefore S is linearly dependent. Here 101 + 011 = 110. Hence 110 is discarded from S and the set S = {101, 011, 010} is formed. Now S must be checked for linear independence. Let a,b,c be scalars such that a(101) + b(011) + c(010) = 000 This gives a=0, b+c=0, a+b=0. Therefore a=b=c=0 Thus S is linearly independent and it is a largest linearly independent subset of S. (c) S = {1101, 0111, 1100, 0011} Let a, b, c, d be scalars such that 35

a(1101) + b(0111) + c(1100) + (0011) = 0000 This gives us that a+c = 0 a+b+c = 0 b+d = 0 a+b+d = 0 a+c=0 =⇒ a = c =⇒ b = 0 and d = 0 =⇒ a = 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Therefore a = b = c = d = 0. Thus S is a linearly independent set. (d) S = {1000, 0100, 0010, 0001} Let a, b, c, d be scalars such that a(1000) + b(0100) + c(0010) + d(0001) = 0000. This gives a = b = c = d = 0. Therefore S is a linearly independent set. (e) S = {1000, 1100, 1110, 1111} Let a, b, c, d be scalars such that a(1000) + b(1100) + (1110) = d(1111) = 0000 This gives a+b+c+d = 0 b+c+d = 0 c+d = 0 d=0 Therefore a = b = c = d = 0. Thus S is a linearly independent set. (f ) S = {1100, 1010, 1001, 0101} Let a, b, c, d be scalars such that a(1100) = b(1010) = c(1001) = d(0101) = 0000 This gives a+b+c = 0 a+d = 0 b=0 c+d = 0 and therefore we can choose a = c = d = 1. Thus S is linearly dependent. 36

Here 1(1100) + 0(1010) + 1(1001) = 0101 So consider S = {1100, 1010, 1001}. Let a, b, c be scalars such that a(1100) + b(1010) + c(1001) = 0000 This gives a+b+c = 0 a=0 b=0 c=0 Therefore S is linearly independent. Thus S is a largest linearly independent subset of S. (g) S = {0110, 1010, 1100, 0011, 1111} Let a, b, c, d, e be scalars such that a(0110) + b(1010) + c(1100) + d(0011) + e(1111) = 0000 This gives b+c+e = 0 a+c+e = 0 a+b+d+e = 0 d+e = 0 =⇒ d = e a=b GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Choose a = b = d = e = 1 and c = 0. Then S is linearly dependent. (2.1) Now form S = {0110, 1010, 1100, 0011}. (2.2) Let a, b, c, d be scalars such that (2.3) a(0110) + b(1010) + c(1100) + d(0011) = 0000. (2.4) This gives b+c = 0 a+c = 0 a+b+d = 0 d=0 and this implies a = b = c and d = 0. Choose a = b = c = 1. Then S is linearly dependent. Also 1(0110) + 1(1010) + 1(1100) + 0(0011) = 0000. Now form S = {0110, 1010, 0011}. Let a(0110) + b(1010) + c(0011) = 0000. This implies a = b = c = 0. Thus S is a largest linearly independent subset of S. 37

(h) S = {111000, 000111, 101010, 010101} Let a, b, c, d be scalars such that a(111000)+b(000111)+ c(101010) + d(010101) = 000000. =⇒ a+c = 0 (2.5) a+d = 0 (2.6) b+d = 0 (2.7) b+c = 0 (2.8) =⇒ a = b = c = d. Therefore choosing a = b = c = d = 1 makes the set S linearly dependent. Now 1(111000) + 1(000111) + 1(101010) = 010101. Form S = {111000, 000111, 101010}. Let a, b, c be scalars such that a(111000) + b(000111) + c(101010) = 000000. This implies GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur a+c = 0 b+c = 0 a=0 b=0 =⇒ a = b = c = 0. Therefore S is linearly independent. Hence S = {111000, 000111, 101010} is a largest linearly independent subset of S. (i) S = {00000000, 10101010, 01010101, 11111111} Since the word 00000000 belongs to S, the set is linearly dependent. Also 1(10101010) + 1(01010101) + 1(11111111) = 00000000. Therefore the set S is linearly dependent. So form S = {10101010, 01010101}. Let a, b be scalars such that a(10101010) = b(01010101) = 00000000. This implies a = b = 0. Therefore S = {10101010, 01010101} is a largest linearly independent subset of S. 2.3.7 For each set in Exercise 2.2.3 find a basis B for the code C =< S > and a basis B⊥ for the dual code C⊥. (a) S = {010, 011, 111} C =< S >= K3 and C⊥ = {000}. K3 has dimension 3. Since S has three elements and S is linearly independent, S itself forms a basis for C = K3. Since C⊥ contains only the zero word B⊥ = φ. (b) S = {1010, 0101, 1111} C =< S >= {0000, 1010, 0101, 1111} and C⊥ = C. Therefore B = B⊥. Since 1(1010) + 1(0101) = 1111 S is linearly dependent. But a(1010) + b(0101) = 0000 for some scalars a and b implies a = b = 0. Therefore B = {1010, 0101} = B⊥. (c) S = {0101, 1010, 1100} C =< S >= {0000, 1010, 0101, 1100, 1111, 1001, 0110, 0011} and C⊥ = {0000, 1111}. Here |C| = 23 and therefore dimC = 3. Therefore we check whether S is linearly independent or not. 38

Let a,b,c,d be scalars such that a(0101) = b(1010) + c(1100) = 0000. This gives b + c = 0, a + c = 0, a = 0, b = 0 i.e; a = b = c = 0 Therefore S is linearly independent. Thus B = S = {0101, 1010, 1100}. Since |C⊥| = 2, B⊥ = {1111}. (d) S = {1000, 0100, 0010, 0001} C =< S >= K4 and C⊥ = {0000}. Therefore dimC = 4 and dimC⊥ = 0. (e) S = {11000, 01111, 11110, 01010} C =< S >= {00000, 11000, 01111, 11110, 01010, 10111, 00110, 10010, 10001, 00101, 10100, 01001, 111 Therefore |C| = 24 and |S| = 4. Since C has dimension 4 we check if S is linearly inde- pendent or not. Let a, b, c, d be scalars such that a(11000) + b(01111) + c(11110) + d(01010) = 00000. This implies GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur a+c =0 a+b+c+d =0 =0 b+c =0 b+c+d =0 =⇒ c = 0 b =⇒ a = 0 =⇒ d = 0 =⇒ a = b = c = d = 0. Therefore S is linearly independent set. Thus B = S = {11000, 11110, 01111, 01010}. Now C⊥ = {00000, 11111} and hence B⊥ = {11111}. (f ) S = {10101, 01010, 11111, 00011, 10110}. C =< S >= {00000, 10101, 01010, 11111, 00011, 10110, 01 Since |C| = 23, dimension of C is 3 and therefore S contains a basis for C. 1(10101) + 1(01010) + 1(11111) = 00000. So 11111 is eliminated from S. But then 1(10101) + 1(00011) + 1(10110) = 00000. So 10110 is also eliminated from S. Now the set S has three elements and it spans C. Thus B = {10101, 01010, 00011}. Now C⊥ = {00000, 01111, 11011, 10100}. Since |C⊥| = 22 and 1(01111) + 1(11011) = 10100, B⊥ = {01111, 11011} is a basis for C⊥. 2.3.8 Find the dimensions of each code C =< S > and its dual C⊥ in Exercise 2.2.3 (see also Exercise 2.2.7). (a) S = {010, 011, 111}: C =< S >= {000, 010, 011, 111, 001, 101, 100, 110} = K3. Therefore dim C = 3 and dim C⊥ = 0. (b) S = {1010, 0101, 1111}: C =< S > and C⊥ = C. Therefore dim C = 2 = dim C⊥, since |C| = 22. 39

(c) S = {0101, 1010, 1100}: C = {0000, 0101, 1010, 1100, 1111, 1001, 0110, 0011}, and C⊥ = {0000, 1111}. So |C| = 8 = 23 and |C⊥| = 2. Therefore dim C = 3, dim C⊥ = 1. (d) S = {1000, 0100, 0010, 0001}: C = K4 and C⊥ = {0000}. Therefore dim C = 4 and dim C⊥ = 0. (e) S = {11000, 01111, 11110, 01010}: C = {00000, 11000, 01111, 11110, 01010, 10111, 00110, 10010, 10001, 00101, 10100, 01001, 11101, 1101 and C⊥ = {00000, 11111}.Since |C| = 16 = 24, dim C = 4 and |C⊥| = 2, implies dim C⊥ = 1. (f ) S = {10101, 01010, 11111, 00011, 10110}: C = {00000, 10101, 01010, 11111, 00011, 10110, 01001, 11100} and C ⊥= {00000, 01111, 11011, 10100 Since |C| = 8 = 23 and |C⊥| = 4 = 22, dim C = 3, dim c⊥ = 2 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.3.10 Write each of the following words in K4 as a unique linear combination of the words in the basis{1000, 1100, 1110, 1111}: (a) 0011: Let a, b, c, d be scalars such that a(1000) + b(1100) + c(1110) + d(1111) = 0011. Solving for a, b, c, d we give a = 0, b = 1, c = 0, d = 1. (b) 1010: 1010 = 1.(1000) + 1.(1100) + 1.(1110) + 0.(1111). (c) 0111: 0111 = 1.(1000) + 0.(1100) + 0.(1110) + 1.(1111) (d) 0001: 0001 = 0.(1000) + 0.(1100) + 1.(1110) + 1.(1111). (e) 0000: Here a = b = c = d = 0. 2.3.12 (a) Find a basis for K4 which contains {1001, 1111}. Now < S >= {1001, 1111, 0000, 0110} = K4. Now 1000 ∈/< S > Let new S = {1001, 1111, 1000} and < S >= {1001, 0000, 1111, 1000, 0001, 0111, 1110, 0110} = K4. Now 0100 ∈/ S. So the new set is S = {1001, 1111, 1000, 0100} is a basis for K4. (b) Extend {101010, 010101} to a basis for K6: Let S = {100000, 010000, 001000, 000100, 000010, 000001, 101010, 010101}. We can see that 1(101010) + 1(100000) + 1(001000) = 000010 Eliminating 000010 from S . and since 1(010101) + 1(010000) + 1(000100) = 000001, eliminate 000001 from S . Claim: B = {101010, 010101, 100000, 010000, 001000, 000100} is a basis for K6. Its enough if we show that B is linearly independent. Let a, b, c, d, e, f be scalars such that a(101010) + b(010101) + c(100000) + d(010000) + e(001000) + f (000100) = 000000. 40

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturThis implies a+c = 0 b+d = 0 a+e = 0 b+f = 0 a=b= 0 =⇒ c = 0 d=0 e=f = 0 Therefore B is linearly independent and since |B| = 6, B forms a basis for K6. 2.3.15 Check your answers in Exercise 2.3.8 with the equation in Theorem 2.3.14.: Theorem 1 (2.3.14). If C is a linear code generated by a subset S of Kn, them dim C + dim C⊥ = n. a) C = K3, C⊥ = {000}. dim C + dim C⊥ = 3 = n. In a similar manner we can do the rest. 2.3.16 Let S be a subset of K7, let C =< S > and assume C⊥ has dimension 3: a) Find the dimension of C =< S >. By theorem 1 dim C + dim C⊥ = n. Since dim C⊥ = 3 and n = 7, dim C = 7 − 3 = 4. b) Find the number of words in C. The number of words in C is 2dim C = 24 = 16. 2.3.17 Let S be a subset of K8 and assume that {11110000, 00001111, 10000001} is a basis for C⊥. Find the number of words in C =< S >: Since {11110000, 00001111, 10000001} is a basis for C⊥, dim C⊥ = 3 and so dim C = 8 − 3 = 5. Therefore the number of words in C =< S > is 25 = 32. 2.3.18 Theorem 1 also holds in Rn. In Rn every vector can be written uniquely as the sum of a vector in < S > and a vector in S⊥, and the zero vector is the only vector < S > and S have in common. (For example, in R3, take < S > to be xy-plane and S⊥ the z-axis). Use S = {000, 101} in K3 to show that this is not the case in general Kn.: Given S = {000, 101}. Then < S >= {000, 101}. Let V = (x, y, z) ∈ S⊥. Then v · 101 = 000 =⇒ x + z = 0. So x = z. Therefore S⊥ = {000, 101, 010, 111}. Consider 100 ∈ K3. Since S ⊆ S⊥ and S⊥ is linear, 100 cannot be written as a sum of two vectors one from < S > and the other from S⊥. 2.3.21 Let bn be the number of different bases for Kn. Verify the entries in the following table: 41

n 12 3 4 5 6 bn 1 3 28 840 83,328 27,998,208 A linear code of dimension k has precisely 1 k−1 k! (2k − 2i) different bases. Since Kn has dimen- i=0 sion n, the number of different bases for Kn is as follows: n = 1 =⇒ b1 = 1 n=2 =⇒ b2 = 1 (22 − 20)(22 − 21) = 3 2! =⇒ 1 (23 − 20)(23 − 21)(23 − 22) n=3 b3 = 3! = 28 In a similar manner, b4 = 840, b5 = 83328, b6 = 27998208 2.3.22 List all the bases for K2 and for K3: The number of different bases of K2 is 3 and each has 2 elements since dim K2 is 2. These bases are {10, 01}, {10, 11} and {01, 11}. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 2.3.23 Find the number of different bases for each code C =< S > (a) S = {010, 011, 111}: C =< S >= {000, 010, 011, 111, 001, 101, 100, 110} = K3. Therefore C has 28 different bases. (b) S = {1010, 0101, 1111}: Since |C| = 4 = 22, dim C = 2. Therefore C has 3 different bases. (c) S = {0101, 1010, 1100}: Since |C| = 8 = 23, dim C = 3. Therefore C has 28 different bases. (d) S = {1000, 0100, 0010, 0001}: Since |C| = 16 = 24, dim C = 4. Therefore C has 840 different bases. (e) S = {11000, 01111, 11110, 01010}: Since |C| = 16 = 24, dim C = 4. Therefore C has 840 different bases. (f ) S = {10101, 01010, 11111, 00011, 10110}: Since |C| = 8 = 23, dim C = 3. Therefore C has 28 different bases. 2.4 Matrices 2.4.1 Find the product of each pair of following matrices whenever the product is defined. 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 A = 0 0 1 0 1 , B = 1 0 0 1 , C 1 1 0 1 1 0 10. 1 0 1 11 1 0 0 = 0 0 1 1 0 1 , D = 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 11 • Since A has order 3 × 5 and no other matrix has 5 rows, and 3 columns, A cannot be pre multiplied or post multiplied with any other matrix. 1 1 0 0 0 0 1 0 0 0 DC = 1 0 1 0 1 1 • BC = 0 1 1 1 0 1, BD = 0 0 1 0, 1 0 0 0 0 1 1 0 11 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 42

2.4.2 Find 2 × 2 matrices A and B over K such that AB = BA Let A = 1 1 ,B = 1 0 , then AB = 0 0 and BA = 1 1 . So AB = BA. 0 0 1 0 0 0 1 1 2.4.3 Find 2 × 2 matrices A and B over K, both different from the zero matrix 0, such that AB = 0. 1 1 1 0 0 0 0 0 1 0 0 0 Let A = ,B = , then AB = , So AB = 0. 2.4.4 Find 2 × 2 matrices A, B and C over K, such that AB = AC but B = C. Let A = 1 1 ,B= 1 0 ,C = 0 1 , then AB = 0 0 = BC, but B = C. 0 0 1 0 0 1 0 0 2.4.6 Find RREF for each of the matrices in Exercise 2.4.1.GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur A) 1 1 0 1 1 −−−−−−−−−−−→ 1 1 0 1 1 A = 0 0 1 0 1 R1 −→ R3 + R1 0 0 1 0 1 11011 00000 1 0 0 1 B) 0 1 0 1 0000 1 0 1 0 1 1 C) 0 1 1 0 1 1 0 0 0 1 1 0 000000 1 0 0 0 D) 0 1 0 1 0 0 1 0 0000 2.5 Bases for C =< S > and C⊥ 2.5.3 Use Algorithm 2.5.1 to find a basis for C =< S > for each of the following sets S. (a) S = {010, 011, 111}: 0 1 0 −−−−−−−−−−−→ 1 1 1 A = 0 1 1 using REF steps 0 1 0 111 001 So the basis B for < C > is B = {111, 010, 001}. 43

(b) S = {1010, 0101, 1111} Here 1 0 1 0 u−−si−n−g−−R−E−F−s−t−e→ps 1 0 1 0 A = 0 1 0 1 0 1 0 1 1111 0000 Therefore B = {1010, 0101}. (c) S = {0101, 1010, 1100} 0 1 0 1 u−−si−n−g−−R−E−F−s−t−e→ps 1 0 1 0 A = 1 0 1 0 0 1 0 1 1100 0011 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Therefore the basis B = {1010, 0101, 0011}. (d) S = {1000, 0100, 0010, 0001} Here the basis is B = {1000, 0100, 0010, 0001}, as the matrix A is in REF form. (e) S = {11000, 01111, 11110, 01010}. 1 1 0 0 0 1 1 0 0 0 A = 0 1 1 1 1 −−−−−−−−−−−→ 0 1 0 1 0 1 1 1 1 0 using REF steps 0 0 1 0 1 01010 00011 Therefore B = {11000, 01010, 00101, 00011}. (f ) S = {10101, 01010, 11111, 00011, 10110}. 1 1 0 0 0 1 1 0 0 0 A = 0 1 1 1 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 01010 00011 Therefore B = {11000, 01010, 00101, 00011}. (g) S = {0110, 1010, 1100, 0011, 1111} 0 1 1 0 1 0 1 0 1 0 1 0 −−−−−−−−−−−→ 0 1 1 0 A = 1 1 0 0 using REF steps 0 0 1 1 0 0 1 1 0 0 0 0 1111 0000 Therefore B = {1010, 0110, 0011}. (h) S = {111000, 000111, 101010, 010101} 1 1 1 0 0 0 1 0 1 0 1 0 A = 0 0 0 1 1 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1 1 010101 000000 Therefore B = {101010, 010101, 000111}. 44

(i) S = {00000000, 10101010, 01010101, 11111111} 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 A = 1 0 1 0 1 0 1 0 −u−si−n−g−−R−E−F−s−t−e→ps 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 11111111 00000000 Therefore B = {10101010, 01010101}. 2.5.6 Use Algorithm 2.5.4 to find a basis for C =< S > for each of the following sets S. (a) S = {010, 011, 111} GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur0 0 1 −−−−−−−−−−−→ 1 1 1 A = 1 1 1 using REF steps 0 1 1 011 001 All the three columns are leading columns and hence B = {010, 011, 111}. (b) S = {1010, 0101, 1111} 1 0 1 1 0 1 A = 0 1 1 −−−−−−−−−−−→ 0 1 1 1 0 1 using REF steps 0 0 0 011 000 Therefore B = {1010, 0101}. (c) S = {0101, 1010, 1100} 0 1 1 1 0 0 A = 1 0 1 −−−−−−−−−−−→ 0 1 0 0 1 0 using REF steps 0 0 1 100 000 Therefore B = {0101, 1010, 1100}. (d) S = {1000, 0100, 0010, 0001} 1 0 0 0 A = 0 1 0 0 0 0 1 0 0001 The matrix A is itself in REF and hence B = {1000, 0100, 0010, 0001}. (e) S = {11000, 01111, 11110, 01010} 1 0 1 0 1 0 0 0 1 1 1 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 1 0 0 A = 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0100 0000 Therefore B = {11000, 01111, 11110, 01010}. 45

(f ) S = {10101, 01010, 11111, 00011, 10110} 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 −u−si−n−g−−R−E−F−s−t−e→ps 0 1 1 0 0 A = 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 10110 00000 Therefore B = {10101, 01010, 00011}. (g) S = {0110, 1010, 1100, 0011, 1111} 0 1 1 0 1 1 0 1 0 1 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur A = 1 0 1 0 1 −u−si−n−g−−R−E−F−s−t−e→ps 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 00011 00000 Therefore B = {0110, 1010, 0011}. (h) S = {111000, 000111, 101010, 010101} 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 A = 1 0 1 0 −u−si−n−g−−R−E−F−s−t−e→ps 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0101 0000 Therefore B = {111000, 000111, 101010}. (i) S = {00000000, 10101010, 01010101, 11111111} 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 A = 0 0 1 1 u−−si−n−g−−R−E−F−s−t−e→ps 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0011 0000 Therefore B = {10101010, 01010101}. 2.5.10 Use algorithm 2.5.7 to find a basis for C⊥ for each of the codes C =< S > where (a) S = {010, 011, 111} 0 1 0 −−−−−−−−−−−−→ 1 0 0 A = 0 1 1 using RREF steps 0 1 0 111 001 46

Now form the matrix G consisting of all the nonzero rows of the RREF. 1 0 0 G = 0 1 0. Now form X from G by deleting the leading columns of G. Here all the 001 columns of G are leading columns. Therefore X = G. In this case the basis for C⊥ is φ. (b) S = {1010, 0101, 1111} 1 0 1 0 u−−si−n−g−R−−R−E−F−s−t−e→ps 1 0 1 0 A = 0 1 0 1 0 1 0 1 1111 0000 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturTherefore G =1010and X =10. 0 1 0 1 0 1 1 0 Thus H = 0 1 1 0 01 Hence the basis for C⊥ is B⊥ = {1010, 0101}. (c) S = {0101, 1010, 1100} 0 1 0 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 1 0 0 1 A = 1 0 1 0 0 1 0 1 1100 0011 1 The leading columns are 1, 2, 3. Therefore X = 1. 1 1 Thus H = 1 and hence B⊥ = {1111}. 1 1 1 0 0 0 (d) S = {1000, 0100, 0010, 0001} A = 0 1 0 0 0 0 1 0 0001 Here A is in RREF and so X = G = A. Therefore B⊥ = φ. (e) S = {11000, 01111, 11110, 01010} 1 1 0 0 0 1 0 0 0 1 A = 0 1 1 1 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 01010 00011 47

The leading columns of G are 1, 2, 3, 4 and therefore X = 1 Thus H = 1 11. 1 1 1 and 1 1 hence B⊥ = {11111}. (f ) S = {10101, 01010, 11111, 00011, 10110} 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 −−−−−−−−−−−−→ 0 1 0 1 0 A = 1 1 1 1 1 using RREF steps 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur10110 00000 1 1 1 1 0 1 0. Therefore X = 0 1 and H = 1 1 0 1 0 1 0 Thus B⊥ = {10100, 11011}. (g) S = {0110, 1010, 1100, 0011, 1111} 0 1 1 0 1 0 0 1 1 0 1 0 −−−−−−−−−−−−→ 0 1 0 1 A = 1 1 0 0 using RREF steps 0 0 1 1 0 0 1 1 0 0 0 0 1111 0000 Therefore X = 1 and so H = 1 1 11. 1 1 Thus B⊥ = {1111}. (h) S = {111000, 000111, 101010, 010101} 1 1 1 0 0 0 1 0 1 0 1 0 A = 0 0 0 1 1 1 −u−si−n−g−R−−R−E−F−s−t−e→ps 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 010101 000000 1 1 0 The leading columns are 1, 2, 4 and so X = 0 1 0. 011 1 1 0 0 1 0 Hence H = 1 0 0 and thus B⊥ = {101000, 110110, 000101}. 0 1 1 0 1 0 001 48

(i) S = {00000000, 10101010, 01010101, 11111111} 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 A = 1 0 1 0 1 0 1 0 −−−−−−−−−−−→ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 using REF steps 0 0 0 0 0 0 0 0 11111111 00000000 The leading columns are 1, 2 and so X = 1 0 1 0 1 0 1 0 . 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 HenceGovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturH=010000andthus B⊥ = {10100000, 01010000, 10001000, 01000100, 10000010 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 000001 2.5.11 With the notation of Algorithm 2.5.7, explain why it is expected that GH = 0. Since H is a parity check matrix for the code C, H is a generator matrix for C⊥. Also G is a generator matrix for C. Therefore GH = 0. 2.5.12 For each of the following sets S, use algorithm 2.5.7 to produce a basis B for the code C =< S > and a basis B⊥ for the dual code C⊥. (a)S = {000000, 111000, 000111, 111111} 0 0 0 0 0 0 1 1 1 0 0 0 A = 1 1 1 0 0 0 u−−si−n−g−R−−R−E−F−s−t−e→ps 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 111111 000000 Therefore G = 1 1 1 0 0 0 and hence B = {111000, 000111}. 0 0 0 1 1 1 1 1 0 0 1 0 0 0 Now X = 1 1 0 0 . Hence H = 0 1 0 0 and thus B⊥ = {110000, 101000, 000110, 000101}. 0 0 1 1 0 0 1 1 0 0 1 0 0001 (b) S = {1101000, 0110100, 0011010, 0001101, 1000110, 0100011, 1010001} 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 −u−s−in−g−−R−R−E−F−−st−e→ps 0 0 1 0 1 1 1 A = 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1010001 0000000 49