App B

This is the Title PhL 3.26.05 This has been installed. Appendix B: A Proof of Fact 4 (2.3.8) Here is what we want to prove: Fact 4: If c is any code word of the cyclic code generated by g(x), then the infinite sequence {oi} = {c,c,c,c ...} is a solution of the difference equation (2.3.2), which equation says = 0 m = 0,1,2.... . (2.3.2) The g(x) here is what one gets doing the division g(x) = (xn-1)/h(x), and we assume that such an n exists such that such an even division exists (this assumption is discussed below). Our proof is broken down into six short parts (1) through (6). (1) GA Chapter 7 discusses the notion of a linear block code associated with a matrix G. One applies the non-square matrix G to a data vector d having k components and obtains thereby a code vector c having n components with n > k. If the vectors are row vectors, one writes c = dG. Associated with matrix G is another matrix H called the parity check matrix for code G and one finds that, for any code word c, cHT = 0. One can use matrix H then to "check" to see whether c really is a code word of code G by seeing if cHT = 0 or not. One can show that the matrices G and H satisfy GHT = 0 and HGT = 0 (B.1) where each 0 is an all-zeros matrix of an appropriate size. It turns out that the matrix H can itself be used to define another linear block code which is known as the dual code to code G. One applies the matrix H to a data vector d' having n-k components and obtains thereby a code vector c' having n components. If the vectors are row vectors, one writes c' = d'H. It then turns out that the c' c = 0 for any code word c of code G and any code word c' of code H. The proof is simple: c' c = c'cT = (d'H)(dG)T = (d'H)GTdT = d'(HGT)dT = d'(0)dT = 0 (B.2) (2) GA Chapter 8 then discusses cyclic codes which have a close relationship to the block codes. The k components of the data vector d are now the coefficients of a polynomial d(x). The code words are generated now as the coefficients of polynomial c(x) which is obtained from polynomial multiplication, c(x) = d(x) g(x). (B.3) Here g(x) is a polynomial of degree n-k which is called the generator of the cyclic code. Associated with this cyclic code is a dual cyclic code where we have c'(x) = d'(x) h(x) (B.4) where the n-k components of the data polynomial d'(x) are the components of the data vector d' mentioned above. Polynomial h(x) is the generator of the dual code and has degree k. The relationship between g(x) and h(x) is this g(x)h(x) = (xn - 1) . (B.5) Now the coefficients of c(x) which we call ci are not necessarily the same as the ci in part (1) above, but they are nonetheless the coefficients of some code word in the space of code words. The same comment applies to c'(x) and the c'i. (3) In (2.3.6) we assumed that there existed an integer n such that g(x)h(x) = (xn - 1) where h(x) was the polynomial used to construct the polynomial representation GF(q=pk) = R / ( h(x) ) in (2.2.6). If h(x) is monic and irreducible with respect to GF(p) (sometimes we say "under GF(p)" ), we know from (2.2.10) that h(x) is a minimum polynomial for some element α of GF(q). From the explanation given in the Proof of (2.2.33), we know that such an h(x) divides evenly into (xq-1- 1). We noted that there might be some n smaller than q-1 for which h(x) divides evenly into (xn-1). Whatever the smallest n is, we just call it n. It might be q-1 if nothing smaller works. So, given our irreducible monic h(x) of Chapter 2, we know for sure that there exists a g(x) such that g(x)h(x) = (xn - 1). So we use that exact g(x) to define the cyclic code described in part 2 above, and then h(x) is our h(x) of interest in Chapter 2, it is not just some h(x) pulled out of a hat. (4) Certainly d'(x) = 1 is a legal data word for the cyclic dual code and if we use it in (B.4) we obtain the legal dual code word c'(x) = h(x) . We can then write this equation c'(x) = h(x) as c'0 + c'1x + c'2x2 + ... c'kxk + ... + c'n-1xn-1 = h0 + h1x + h2x2 + ... hkxk + 0 + ... + 0xn-1 We then write a vector equality for the coefficients, c' = h where h = (h0,h1,......hk,0,0...0) (B.6) where we fill out the end of vector h with a set of n-k-1 zeros so it then has n components to match c'. We then apply (B.2) to conclude that, for any code word c of the cyclic code generated by g(x), h c = 0 . (B.7) If we write this out as a summation, we get = 0 (B.8) where the numbers {c0, c1, c2, ...ck} are the first k+1 coefficients of c. We have just proved in (B.8) this fact: Fact : The dot product of the coefficients of h(x) with the first k+1 coefficients of any code word is 0. (5) What happens if we dot h with any k+1 consecutive coefficients of a code word c? We know that there is some other code word C for which these k+1 consecutive coefficients are the first k+1 coefficients. We know this because we know that all cyclic permutations (rotations) of code words are also code words. Thus we have proved that : Fact: The dot product of the coefficients of h(x) with any consecutive k+1 coefficients of any code word gives 0. For example if k = 3 we might have this situation where (B.8) includes the products shown here as pairs of numbers one above the other : c0 c1 c2 c3 c4 c5 ..... cn-1 h0 h1 h2 h3 But (B.8) will also be true for any alignment which wraps the last coefficient like this one. c0 c1 c2 c3 c4 c5 ..... cn-1 h1 h2 h3 h0 Thus, when we say "consecutive coefficients" we would include a sequence like this .... cn-2 cn-1 c0 c1 c2..... (6) Now consider the difference equation (2.3.2), = 0 m = 0,1,2.... (2.3.2) (B.9) Picture the sequence {oi} as an infinite row of numbers. Picture the sequence {hj} as a finite row of numbers. Place the row {hj} anywhere under the infinite row {oi}, then take the sum of the product of the abutting numbers as done above. This is then the left side of (B.9), and the result is supposed to be zero. Varying m means varying the position of the row {hj}. Here is a picture drawn for k=3 and m=5: o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 ... h0 h1 h2 h3 Now consider our candidate solution of the difference equation: {oi} = {c, c, c, c ...} (B.10) Consider the above process. No matter where we position {hj}, we will be dotting h with a "consecutive" set of k+1 coefficients of the code word c. Suppose k = 3 and n = 5 (the size of the code words). The for (B.9) with m = 4 we would have c0 c1 c2 c3 c4 c0 c1 c2 c3 c4 c0 c1 ... h0 h1 h2 h3 No matter where we put our hi row (that is, for any m > 0), equation (B.9) is satisfied. Therefore, the sequence of (B.10) is a solution of the difference equation (B.9) and that is what we set out to prove.