Solution Manual- Coding Theory by Hoffman et al.

A basis for C is g(x) = 1 + x3 + x6 xg(x) = x + x4 + x7 x2g(x) = x2 + x5 + x8 1 0 0 1 0 0 1 0 0 and a generator matrix for C is G = 0 1 0 0 1 0 0 1 0 001001001 (c)n = 15, g(x) = 1 + x + x4 A basis for C is {g(x), xg(x), x2g(x), . . . , x10g(x)} and hence the generator matrix can be found as in previous question. (d)n = 15, g(x) = 1 + x4 + x6 + x7 + x8 A basis for C is {g(x), xg(x), x2g(x), . . . , x6g(x)} and a generator matrix can be found similarly. (e)n = 15, g(x) = 1+x+x2+x4+x5+x8+x10 A basis for C is {g(x), xg(x), x2g(x), x3g(x), x4g(x)} and a generator matrix can be found similarly. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 4.3.6 Show that the linear code with given generator matrix is cyclic and find the generator poly- nomial. 1 1 0 1 1 0 (a)G = 0 0 1 0 0 1 1 0 1 1 0 1 101101 (b)G = 0 1 0 1 0 1 1 1 1 1 1 1 (b)The linear code is C = {000000, 010101, 111111, 101010} and B = {010101, 111111} is a basis for C. Since π(010101) = 101010 and π(111111) = 111111 are in C, it is a cyclic code. Now generating polynomial is g(x) = 1 + x2 + x4 ↔ 101010. 4.3.11 Find a parity check matrix for the linear cyclic code of length 7 with generator g(x) = 1 + x + x2 + x4. 1 0 0 0 0 1 0 0 0 0 1 0 Following the procedure in Example 4.3.7, a parity check matrix H for C is H = 0 0 0 1 1 1 1 0 0 1 1 1 1101 4.3.12 Find a parity check matrix for a cyclic code of length n and with generator g(x): (a)n = 6, g(x) = 1 + x2 1 0 0 1 H = 1 0 0 1 1 0 01 100

(b)n = 6, g(x) = 1 + x3 1 0 0 0 1 0 H = 0 0 1 1 0 0 0 1 0 001 (c)n = 8, g(x) = 1 + x2 1 0 0 1 1 0 HGovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur=01 1 0 0 1 1 0 01 (d)n = 9, g(x) = 1 + x3 + x6 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 H = 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 001001 (e)n = 15, g(x) = 1 + x + x4 (this generates a Hamming code) 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 H = 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1010 (f )n = 23, g(x) = 1 + x + x5 + x7 + x9 + x11 (this generates a Golay code) Can be found in a similar way as in the previous question. (g)n = 15, g(x) = 1 + x4 + x6 + x7 + x8 (this generates a 2-error correcting BCH code, constructed in Chapter 5). Can be found in a similar way as in the previous question. 4.3.13 g(x) = 1 + x4 + x6 + x7 + x8 generates a 2-error correcting linear cyclic code of length 15. Use Algorithm 4.3.8 to decode the following received words that were encoded using C. (a) 001000001110110 101

The syndrome polynomial is s(x) = w(x)modg(x) = x + x2 + x3 and t = 2. Now s1(x) = xs(x)modg(x) = x2 + x3 + x4 s2(x) = x2s(x)modg(x) = x3 + x4 + x5 s3(x) = x3s(x)modg(x) = x4 + x5 + x6 s4(x) = x3s(x)modg(x) = x5 + x6 + x7 s5(x) = x5s(x)modg(x) = 1 + x4 Now wt(s5) = 2 ≤ t. So j = 5 and hence the error polynomial is e(x) = xn−jsj(x)modg(x) = x10(1 + x4)modg(x) = x + x2 + x3. Thus c(x) = e(x) + w(x) = x + x3 + x8 + x9 + x10 + x12 + x13 ↔ 010100001110110 (b) 110001101000101 c(x) = e(x) + w(x) = 1 + x + x2 + x6 ↔ 111000100000000. (c) 001111101001001 Similarly as in the above questions. (d) 001000000110000 Similarly as in the above questions. (e) 110010000111010. Similarly as in the above questions. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 4.4 Finding Cyclic Codes 4.4.6 Find the number of proper linear cyclic codes of length n, where (a) n = 4 Here 4 = 22.1 and z = 1. Therefore the number of proper linear cyclic codes of length 4 are 22 + 11 − 2 = 3 (b)n = 5 Here 5 = 20.5 and z = 2. Therefore the number of proper linear cyclic codes of length 5 are 20 + 12 − 2 = 2 (c)n = 7 The number of proper linear cyclic codes are 6. (d)n = 14 The number of proper linear cyclic codes are 25. (e)n = 56 The number of proper linear cyclic codes are 727. (f )n = 15 The number of proper linear cyclic codes are 30. (g)n = 120 The number of proper linear cyclic codes are 59047. (h)n = 1024 The number of proper linear cyclic codes are 1023. 102

4.4.7 Find the generator polynomial for all proper linear cyclic codes of length n, where (a)n = 4 There are 3 proper linear cyclic codes of length 4 and their generators are the proper factors of 1 + x4. We have 1 + x4 = 1 + x4. Therefore the three generator polynomials are 1 + x, 1 + x2, 1 + x + x2 + x3. (b)n = 5 The generator polynomials for the proper linear cyclic codes of length 5 are 1 + x and 1 + x + x2 + x3 + x4. 4.4.8 Find two generators of degree 4 for a linear cyclic code of length 7. Any generator of a linear cyclic code of length 7 must be a factor of 1 + x7. The two factors of 1 + x7 of degree 4 are 1 + x + x2 + x4 and 1 + x2 + x3 + x4. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 4.4.9 Find a generator and a generating matrix for a linear code of length n and dimension k where (a)n = 12, k = 5 Since the code has dimension 5, the generator polynomial has degree 7. So a factor of 1 + x12 that has degree 7 is required. One such factor is g(x) = 1 + x + x6 + x7 and hence a generating 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 matrix for the code is G =  0 0 1 1 0 0 0 0 1 1 0 0     0 0 0 1 1 0 0 0 0 1 1 0    000011000011 (b)n = 12, k = 7 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0  0 0 1 0 1 1 0 1 0 0 0 0    g(x) = 1 + x2 + x3 + x5 and G =  0 0 0 1 0 1 1 0 1 0 0 0     0 0 0 0 1 0 1 1 0 1 0 0     0 0 0 0 0 1 0 1 1 0 1 0    000000101101 (c)n = 14, k = 5 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 g(x) = 1 + x3 + x4 + x8 + x9 and G =  0 0 1 0 0 1 1 0 0 0 1 1 0 0     0 0 0 1 0 0 1 1 0 0 0 1 1 0    00001001100011 (d)n = 14, k = 6 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 g(x) = 1 + x4 + x6 + x8 and G =  0 0 1 0 0 0 1 0 1 0 1 0 0 0   0 0 0 1 0 0 0 1 0 1 0 1 0    0    0 0 0 0 1 0 0 0 1 0 1 0 1 0    00000100010101 (e)n = 14, k = 8 103

1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0  0 0 1 0 1 0 0 0 1 0 0 0 0 0    g(x) = 1 + x2 + x6 and G =  0 0 0 1 0 1 0 0 0 1 0 0 0 0   0 0 0 0 1 0 1 0 0 0 1 0 0    0    0 0 0 0 0 1 0 1 0 0 0 1 0 0     0 0 0 0 0 0 1 0 1 0 0 0 1 0    00000001010001 4.4.10 Show that the Golay Code C23 is equivalent to a linear cyclic code. 4.4.15 Find all idempotent polynomials mod 1 + xn and the corresponding generator polynomials for, GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(a)n = 5 First find Ci. C0 = {0}, C1 = {1, 2, 4, 3} = C2 = C3 = C4. So for n = 5 we have C0 = {0} and C1 = {1, 2, 3, 4}. Therefore I(x) = a0c0(x) + a1c1(x) = a0 + a1(x + x2 + x3 + x4) Idempotent polynomial the generator polynomial I(x) g(x) = g.c.d(I(x), 1 + x5) 11 x + x2 + x3 + x4 1+x 1 + x + x2 + x3 + x4 1 + x + x2 + x3 + x4 (b)n = 7 the generator polynomial Idempotent polynomial g(x) = g.c.d(I(x), 1 + x5) I (x) 1 1 + x + x3 1 x + x2 + x4 x x3 + x5 + x6 1 + x + x2 + x4 1 + x + x2 + x4 1 + x2 + x3 + x4 1 + x3 + x5 + x6 x + x2 + x3 + x4 + x5 + x6 1+x 1 + x + x2 + x3 + x4 + x5 + x6 1 + x + x2 + x3 + x4 + x5 + x6 (c)n = 11 Similarly as in the above questions. (d)n = 15 Similarly as in the above questions. (e)n = 31 Similarly as in the above questions. 4.5 Dual Cyclic Codes 4.5.5 Find the generator polynomial for the dual code of the cyclic code of length n having generator polynomial g(x) where: (a)n = 6, g(x) = 1 + x2 If g(x) is the generator polynomial for a cyclic code C of dimension k and 1 + xn = g(x)h(x), 104

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturthen the generator polynomial g⊥(x) for C⊥ is xkh(x−1). Given g(x) = 1 + x2. So k = 4 and h(x) = 1 + x2 + x4. Therefore g⊥(x) = 1 + x2 + x4. (b)n = 6, g(x) = 1 + x3 g⊥(x) = 1 + x3. (c)n = 8, g(x) = 1 + x2 g⊥(x) = 1 + x2 + x4 + x6. (d)n = 9, g(x) = 1 + x3 + x6 g⊥(x) = 1 + x3 (e)n = 15, g(x) = 1 + x + x4 g⊥(x) = 1 + x3 + x4 + x6 + x8 + x9 + x10 + x11. (f )n = 15, g(x) = 1 + x4 + x6 + x7 + x8 g⊥(x) = 1 + x + x3 + x7 (g)n = 23, g(x) = 1 + x + x5 + x6 + x7 + x9 + x11 g⊥(x) = 1 + x2 + x5 + x8 + x9 + x10 + x11 + x12. (h)n = 7, g(x) = 1 + x + x2 + x4 g⊥(x) = 1 + x2 + x3. 105

GovDeerpnt.moefntMaCtolhleegmeatiCcsh,itturChapter 5 BCH Codes 5.1 Finite Fields 5.1.10 Define multiplication in K4 modulo h(x) = 1 + x + x4. Calculate the following products. (a) (0011)(1011) (b) (1110)(1001) (c) (1010)(0110) (d) (0100)(0010) (e) (1100)(0111) (f ) (1111)(0001) (a) (0011)(1011) ↔ (x2+x3)(1+x2+x3). But (x2+x3)(1+x2+x3) = 1+x mod (1+x+x4). Thus, (0011)(1011) ↔ 1100. 5.1.11 Find all products of elements in K2 using 1+x+x2 to define multiplication (that is make a multiplication table). (00)(00) ↔ (0)(0). But (0)(0) = 0 mod (1 + x + x2). Thus, (00)(00) ↔ 00. (01)(01) ↔ (x)(x). But (x)(x) = 1 + x mod (1 + x + x2). Thus, (01)(01) ↔ 11. (01)(10) ↔ (x)(1). But (x)(1) = x mod (1 + x + x2). Thus, (01)(10) ↔ 01. (01)(11) ↔ (x)(1 + x). But (x)(1 + x) = 1 mod (1 + x + x2). Thus, (01)(11) ↔ 10. (10)(10) ↔ (1)(1). But (1)(1) = 1 mod (1 + x + x2). Thus, (10)(10) ↔ 10. (10)(11) ↔ (1)(1 + x). But (1)(1 + x) = 1 + x mod (1 + x + x2). Thus, (10)(11) ↔ 11. (11)(11) ↔ (1 + x)(1 + x). But (1 + x)(1 + x) = x mod (1 + x + x2). Thus, (11)(11) ↔ 01. 106

× 00 01 10 11 00 00 00 00 00 01 00 11 01 10 10 00 01 10 11 11 00 10 11 01 5.1.14 Use GF (24) constructed in Table 5.1 to compute the products in K4 in Exercise 5.1.10. [(a)](0011)(1011) ↔ β6β13 = β4 ↔ 1100 5.1.15 Construct the following fields as in Example 5.1.13 (b) Construct GF (23) using h(x) = 1 + x2 + x3 Write every vector as a power of β ↔ x mod h(x) . We have β7 = 1. Table is : GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur word polynomial in x ( mod h(x)) power of β 000 0 ––– 100 β0 = 1 010 1 001 β 101 x β2 111 x2 β3 110 1 + x2 β4 011 1 + x + x2 β5 β6 1+x x + x2 5.1.16 Show that if h(x) ∈ K[x] is an irreducible polynomial of degree n, then h(x) divides 1 + xn for some m ≤ 2n − 1. 5.1.17 Find all primitive elements in GF (24). An element α ∈ GF (2r) is primitive if αm = 1 for 1 ≤ m < 2r − 1. From table we see that β, β2, β4, β8, β11, β13, β14 are primitive element. But β3, β5, β6, β9, β10, β12 are not primitive elements. 5.1.18 Show that βi ∈ GF (2r) is primitive if and only if gcd(i, 2n − 1) = 1. We have β2n−1 = 1. An element α ∈ GF (2r) is primitive if αm = 1 for 1 ≤ m < 2r − 1. Let α = βi Then by definition, βi ∈ GF (2r) is primitive if and only if (βi)m = 1 for 1 ≤ m < 2r −1 if and only if gcd(i, 2n − 1) = 1. 5.2 Minimal polynomials 5.2.6 Verify the entries in Table 5.2, for GF (24). Clearly x and 1 + x are the minimal polynomials of 0 and 1 respectively. Let m1(x) = a0 + a1x + a2x2 + a3x3 + a4x4 m1(β) = 0 =⇒ a01 + a1β + a2β2 + a3β3 + a4β4 = 0 =⇒ a0(1000) + a1(0100) + a2(0010) + a3(0001) + a4(1100) = 0000 =⇒ a0 + a4 = 0, a1 + a4 = 0, a2 = 0, a3 = 0 =⇒ a0 = a1 = a4 = 1, a2 = a3 = 0 107

Thus, m1(x) = 1 + x + x4. Now if β is a root of m1(x), so is β2, β4, β8, · · · . Hence, third row verified. Fourth row is done in the Example [5.2.3]. Next, Let m5(x) = a0 + a1x + a2x2 + a3x3 + a4x4 m5(β5) = 0 =⇒ a01 + a1β5 + a2β10 + a31 + a4β5 = 0 =⇒ a0(1000) + a1(0110) + a2(1110) + a3(1000) + a4(0110) = 0000 =⇒ a0 + a2 + a3 = 0, a1 + a2 + a4 = 0 Choose a0 = a1 = a2 = 1, a3 = a4 = 0 to get an irreducible polynomial. Then, m5(x) = 1+x+x4. Now other roots of m5(x) is β10. Now, consider m7(x) = a0+a1x+a2x2+a3x3+a4x4 m7(β7) = 0 =⇒ a01 + a1β7 + a2β14 + a3β6 + a4β13 = 0 =⇒ a0(1000) + a1(1101) + a2(1001) + a3(0011) + a4(1011) = 0000 =⇒ a0 + a1 + a2 + a4 = 0, a1 = 0, a3 + a4 = 0, a1 + a2 + a3 + a4 = 0 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur Choose a0 = a3 = a4 = 1, a1 = a2 = 0 to get an irreducible polynomial. Then, m7(x) = 1 + x3 + x4. Now other roots of m7(x) are β11, β13, β14. 5.2.7 Find the minimal polynomial of each element of GF (23) constructed using p(x) = 1 + x + x3 Same procedure as that of Exercise 5.2.6 5.2.8 Find the minimal polynomial of each element of GF (24) constructed using p(x) = 1 + x3 + x4 Same procedure as that of Exercise 5.2.6 5.2.9 Find the minimal polynomial of each element of GF (25) constructed using p(x) = 1 + x2 + x5 Same procedure as that of Exercise 5.2.6 5.2.10 Show that 1 + x + x2 = (β5 + x)(β10 + x). (Use Table 5.1). (β5 + x)(β10 + x) ↔ (x2)(1 + x2) = 1 + x + x2 5.2.11 Show that mα(x) is a primitive polynomial if and only if α is a primitive element. 5.3 Cyclic Hamming Codes 5.3.5 Find a parity check matrix for a cyclic Hamming code of length 7 using GF (23) con- structed with 1 + x + x3, where the generator polynomial is m3(x). If w(x) = x + x2 + x4 is received find the most likely codeword c(x).  1   100   β3   110   β6   101      Here, the primitive element is β3 ↔ 110. Note that β7 = 1. Thus,  β2  ↔  010  = H.      β5   111       β   010      β4 011 108

Now, w(x) = x + x2 + x4 was received. Then, w(β3) = β3 + β6 + β5 = 110 + 101 + 111 = 100 = β0 =1 Thus e(x) = 1, and c(x) = w(x) + 1 = 1 + x + x2 + x4. 5.3.6 Repeat Exercise 5.3.5 using GF (23) constructed with p(x) = 1 + x2 + x3 and generator polynomial m1(x). Similar to that of Exercise [5.3.5] 5.3.7 Repeat Exercise 5.3.5 using GF (23) constructed with p(x) = 1 + x2 + x3 and generator polynomial m3(x). Similar to that of Exercise [5.3.5] 5.3.8 Construct a parity check matrix for a cyclic Hamming code of length 15. Consider h(x) = 1 + x + x4. From Theorem 5.3.2, and Table 5.2, 1 + x3 + x4 generates a cyclic Hamming code of length 15 Now do Exercise [5.3.5] using p(x) = 1 + x + x4 and generator polynomial m7(x). 5.3.9 Find the generator polynomial for a cyclic code of length 15 having roots 1, β7, β5 ∈ GF (24) (constructed using 1 + x + x4). Construct a parity check matrix for this code. Show that c(x) ∈ C if and only if wt(c) is even. From Theorem 5.3.3, and Table 5.2, we get g(x) = (1 + x)(1 + x3 + x4)(1 + x + x2) = 1 + x2 5.3.10 Show that every codeword of a cyclic code has even weight if and only if 1+x is a factor of the generator polynomial. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 5.4 BCH Codes 5.4.2 2 error-correcting BCH codes are defined for r ≥ 4. What code does g(x) = m1(x)m3(x) generate when r = 3. 5.4.3 β is a primitive element of GF (24) constructed using the irreducible polynomial p(x) = 1 + x3 + x4. Find the generator polynomial g(x) of the 2-error-correcting BCH code of length 15 using this representation of GF (24); that is, find g(x) = m1(x)m3(x). In GF (24) if α is a root of a polynomial f (x), then so is α2. So m1(x) has β, β2, β4, β8 as roots and hence m1(x) has degree 4. Let m1(x) = a0 + a1x + a2x2 + a3x3 + a4x4. Now m1(β) = 0 =⇒ a0β0 + a1β + a2β2 + a3β3 + a4β4 = 0. = 0000 =⇒ a0(1000) + a1(0100) + a2(0010) + a3(0001) + a4(1001) =⇒ a1 = a2 = 0, a0 = a3 = a4 = 1 109

Therefore m1(x) = 1 + x3 + x4. β3, β6, β9, β12 are the roots of m3(x). Let m3(x) = b0 + b1x + b2x2 + b3x3 + b4x4. Now m3(β3) = 0 =⇒ b0(β0) + b1(β3) + b2(β6) + b3(β9) + b4(β12) = 0 =⇒ b0(1000) + b1(0001) + b2(1111) + b3(1010) + b4(1100) = 0000 =⇒ b0 = b1 = b2 = b3 = b4 = 1 Therefore m3(x) = 1 + x + x2 = x3 + x4. Thus g(x) = (1 + x3 + x4)(1 + x + x2 + x3 + x4) = 1 + x + x2 + x4 + x8. 5.4.4 Find a generator polynomial for a 2 error-correcting BCH code of length 31 constructing GF (25) with the irreducible polynomial 1 + x2 + x5. GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 5.4.7 Show that the columns of the parity check matrix of C15 in Table 5.4 are linearly independent and hence that C15 has dimension k = 7. Let a, b, c, d, e, f, g, h be scalars such that a(100010011010111) + b(010011010111100) + c(001001101011110) + d(000100110101111) + e(100011000110001) + f (000110001100011) + g(001010010100101) + h(011110111101111) = 000000000000000 a + e = 0, b + h = 0, c + g + h = 0, d + f + h = 0 a + b + e + f + g + h = 0, b + c + e = 0, c + d + h = 0 a + b + d + g + h = 0, a + c + f + h = 0, b + d + e + f + g + h = 0 a + b + c + e = 0, b + c + d + h = 0, a + b + c + d + g + h = 0 a + c + d + f + h = 0, a + d + e + f + g + h = 0 =⇒ a = b = c = d = e = f = g = h = 0. Thus the columns of the parity check matrix of C15 are linearly independent. Therefore dim(C⊥) = 8 and hence dim(C) = 7. 5.4.8 Show that d = 5 for C15 by using the parity check matrix. 5.4.9 Show that if β is a primitive element of GF (2r), r > 2 then | {β2i|0 ≤ i ≤ r − 1} |= r and | {(β3)2i|0 ≤ i ≤ r − 1} |= r. Therefore m1(x) and m3(x) both have degree r. If β is a primitive element, then βm = 1 for all 0 ≤ m < 2r − 1. Now β2i = β2j for 0 ≤ j < i ≤ r − 1 =⇒ β2i−j = 1 which is not possible since 2i−j < 2r − 1. Therefore β2i = β2j for distinct i and j between 0 and 2r − 1. Thus | {β2i|0 ≤ i ≤ r − 1} |= r. Since (β3)2i = (β2i)3 we get | {(β3)2i|0 ≤ i ≤ r − 1} |= r. 5.4.10 Determine whether each of the following words of length 15 is a codeword in C15, where g(x) = 1 + x4 + x6 + x7 + x8. (a)011001011000010 011001011000010 ↔ x + x2 + x5 + x7 + x8 + x13 = f (x). Now f (x) = g(x)(1 + x2 + x4 + x5) + (1 + x). Therefore g(x) does not divide f (x) and hence f (x) ↔ 011001011000010 ∈/ C. 110

(b)000111010000110 000111010000110 ↔ x3 + x4 + x5 + x7 + x12 + x13 = f (x). Now f (x) = g(x)(x + x2 + x3 + x5) + (x + x2 + x4 + x5 + x6 + x7). Therefore 000111010000110 ∈/ C. (c)011100000010001 011100000010001 ↔ f (x) and f (x) = g(x)(x+x2+x3+x5+x6). Therefore 011100000010001 ∈ C. (d)111111111111111 111111111111111 ↔ f (x) and f (x) = g(x)(1+x+x2 +x3 +x6). Therefore 111111111111111 ∈ C. 5.5 Decoding 2 Error-Correcting BCH Code GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur 5.5.2 Verify by substitution that β4 and β13 are indeed solutions of the quadratic equation x2 +β11x+ β2 = 0. Also check that the sum of the 4th and 13th rows of H in Table 5.4 is [s1, s3]. Substituting β4 in the equation gives β8 + 1 + β2 ↔ 1010 + 1000 + 0010 = 0000 ↔ 0. Now for x = β13, β11 + β9 + β2 ↔ 0111 + 0101 + 0010 ↔ 0. Therefore β4 and β13 are indeed solutions of the quadratic equation x2 + β11x + β2 = 0. 5.5.3 Find the roots in GF (24) of the following polynomials, if possible(use Table 5.1). (a)x2 + β4x + β13 The sum of the roots must be β4 and their product must be β13. Now (1 + x2) + (x + x2) = 1 + x ↔ β4. Therefore the roots are β5 = 0110 and β8 = 1010. (b)x2 + β7x + β2 Similarly as in (a). (c)x2 + β2x + β5 β9 and β11 are the roots. (d)x2 + β6 β3 ↔= 0001 is the double root. (e)x2 + β2x β2 ↔= 0010 is the double root. (f )x2 + x + β8 The roots are β11 ↔ 0111 and β12 ↔ 1111. 5.5.9 Messages are encoded using C15. Determine if possible the locations of the errors if w is received and the syndrome wH is given in each part. (a) 0100 0101 (e) 0000 0100 (b) 1110 1000 (f ) 1010 0100 (c) 1100 1101 (g) 0011 1101 (d) 0100 0000 (h) 0000 0000 Apply Algorithm 5.5.4. (a) Given [s1, s3]=[0100, 0101]=[β, β9]. s1 = 0 and s3 = 0. Also s13 = β3 = β9 = s3. s3 Therefore form the quadratic equation x2 + s1x + s1 + s21 = 0. =⇒ x2 + βx + β10 = 0. Now the roots of the equation are β12 and β13. Since the roots are distinct the errors are occurred most likely at the positions 12 and 13. 111

(b) Given [s1, s3]=[1110, 1000]=[β10, β0]. Since s31 = β30 = β0 = s3, a single error has occurred at position 10. (e) Given [s1, s3]=[0000, 0100]=[0, β]. Since s1 = 0 and s3 = 0 ask for a retransmission. Similarly the rest can be solved. 5.5.10 The code is C15. Decode, if possible, each of the following received words w. (a) 11000 00000 00000 (h) 10101 00101 10001 (b) 00001 00001 00001 (i) 01000 01000 00000 (c) 01000 10101 00000 (j) 01010 10010 11000 (d) 11001 11001 11000 (k) 11011 10111 01100 (e) 11001 11001 00000 (l) 10111 00000 01000 (f ) 11100 00000 00001 (m) 11100 10110 00000 GovDeerpnt.moefntMaCtolhleegmeatiCcsh,ittur(g) 10111 00000 00000(n) 00011 10100 00110 Apply Algorithm 5.5.4. (a) Given w = 110000000000000, the syndrome is wH = 11001001 = [1100, 1001] = [s1, s3]. Now β5 and β 10 are the distinct roots of the equation x2 + s1x + s3 + s21 = 0. s1 Therefore the errors are in the 5th and the 10th position and hence the codeword is v = 110010000100000. (b) Given w = 000010000100001, the syndrome is wH = 00001111 = [s1, s3]. Since s1 = 0 and s3 = 0 a retransmission is requested. (c) Given w = 010001010100000, the syndrome is wH = 10100101 = [1010, 0101] = [s1, s3]. Now s13 = (β8)3 = β24 = β9 = s3. Therefore a single error is most likely to have occurred in the 8th position. Hence the codeword is v = 010001000100000. The remaining can be solved in a similar way. 112