Peterson CRC theorems

This is the Title PhL 3.26.05 This stuff is fully handled in Appendix F, just archiving older notes here. It is the CRC detection theorems. Not sure what this was for. Little Lemma: Rem(c/ab) = 0 Rem(c/a) = 0 and Rem(c/b) = 0 Proof: [Rem(c/ab)] = 0 => c/ab = N => c/a = bN = N1 => Rem(c/a) = 0 => c/b = aN = N2 => Rem(c/b) = 0 Corollary: Rem(c/a) ≠ 0 Rem(c/ab) ≠ 0 Fact: If g(x) divides xn -1 then g(x) cannot be written g(x) = xif(x) for any i > 1 Proof: First a little obvious Lemma Lemma: Rem(c/ab) = 0 Rem(c/a) = 0 and Rem(c/b) = 0 or ab divides c a divides c and b divides c or ab | c a | c and b | c Proof: [Rem(c/ab)] = 0 => c/ab = N => c/a = bN = N1 => Rem(c/a) = 0 => c/b = aN = N2 => Rem(c/b) = 0 Thus, if g(x) divides xn- 1 then both xi and g1(x) must divide xn- 1. But xi is not a factor of xn- 1, QED. Fact: If g(x) divides xn -1 then g(x) cannot be written g(x) = (xi+xj)f(x) for any i ≥ j > 0. Proof: As above, this requires that xn-1 be divisible by (xi+xj) = xj(xi-j+1), and that in turn requires that xn- 1 be divisible by xj but we showed above that is impossible. ______________ Maybe this stuff is Appendix Material. Which one should come first Appendix E on Existence of g(x) of any order theorem. I would refer to this right where cyclic codes are defined. Appendix F on Cyclic Code Error Detection. I would refer to this from my little CRC section _________________________________________________________________ Fact 1: If g(0) ≠ 0, a cyclic code generated by g(x) over GF(p) detects all single-symbol errors. Proof. Suppose C'(x) and C(x) differ in one symbol position. Then E(x) ≡ C'(x)-C(x) = αxi where i = 0,1..n-1 and α is some non-zero element of GF(p). We need to show that in this case the syndrome will be non-zero so the error will then be detected. But : s(x) = Rem[C'(x)/g(x)] = Rem[{C(x) + E(x)}/g(x)] = Rem[E(x)/g(x)] = Rem[α xi/g(x) ] where we used Rem[C(x)/g(x)] =0. Now: For i = 0, Rem[αxi/g(x) ] = Rem[α/g(x) ] = α ≠ 0. Note that g(0) ≠ 0 rules out g(x) = constant ≠ 0. For i > 1, Rem[αxi/g(x) ] ≠ 0 unless g(x) = αxn for n ≤ i, but g(0) ≠ 0 rules out such a g(x). QED. Notice that it was not required that g(x) divide evenly into xn - 1. Fact 2: If g(x) = (x-1)f(x),a cyclic code generated by g(x) over GF(2) detects all odd-num-of-bit errors. Proof: In this case, E(x) = C'(x) - C(x) is a polynomial with an odd number of terms. We must show that in this case the syndrome does not vanish so the error will be detected. But: s(x) = Rem[E(x)/g(x)] = Rem[(poly with odd of terms) /g(x) ] Assume that this remainder is 0. Then we would have poly with odd of terms (x) = g(x) s(x) = (x-1)f(x) s(x) Evaluate at x = 1 to get odd sum of 1's = 1 = (1-1)f(1)s(1) = 0 Since 1 ≠ 0 we have a contradiction, so it must be that s(x) ≠ 0 and the error is detected. Notice that it was not required that g(x) divide evenly into xn - 1. Fact 3: If g(0) ≠ 0 and the period of g(x) = n, a cyclic code generated by g(x) over GF(2) detects all double-bit errors and all single-bit errors. Proof: We already know from Fact 1 that single-bit errors are detected. For double bit errors we have E(x) = xi + xj for some 0 ≤ i ≤ j ≤ n-1 We need to show that the syndrome does not vanish in this case. s(x) = Rem[E(x)/g(x)] = Rem[(xi+xj)/g(x)] = Rem[xi(xj-i+1)/g(x)] . Since g(0) ≠ 0, we know that g(x) has no factors of x so the xi cancels nothing in g(x), so the only way for s(x) to be 0 is if Rem[(xj-i+1)/g(x)] = 0 which we rewrite in GF(2) as Rem[(xj-i - 1)/g(x)] = 0 (*) The maximum value of j-i is (n-1)-(0) = n-1. If the period of g(x) is n, then (*) cannot be true, since the period s of g(x) is the smallest s such that (xs-1) is divisible by g(x). Then we get s(x) ≠ 0 and the double-bit error will be detected. This proof requires that g(x) divide evenly into xn - 1 and that n be the period of g(x). Fact 4: If g(0) ≠ 0 and g(x) = (x-1)f(x) and the period of g(x) = n, a cyclic code generated by g(x) over GF(2) detects all single-bit, double-bit, triple-bit and other odd_number_of_bit errors. Proof: Such a g(x) meets the criteria for Facts 1,2 and 3 so we can take the union of the detections of each. Definition: A burst error of length (extent) r means any number of symbol errors occurring within a sequential set of powers xs to xs+r-1. For example, if a,b,c,d are non-zero elements of GF(p), the error pattern E(x) = ax3 + bx5 + cx9 would be the error pattern for a burst error of length r = 7. Other E(x) of length 7: ax4 + bx10, ax2 + bx4 + cx6 + dx8. For GF(2) all coefficients are of course 1. Fact 5: If g(0) ≠ 0, a cyclic code generated by g(x) over GF(p) detects all burst errors of length n-k or smaller. Proof: The error pattern can be written E(x) = xs f(x) where f(x) has degree r-1 = n-k-1. The syndrome is s(x) = Rem[E(x)/g(x)] = Rem[xs f(x)/g(x)] . As before, xs cancels nothing in g(x) if g(0)≠ 0, so the only way to get s(x) = 0 is if Rem[f(x)/g(x)] = 0 . But since g(x) has degree n-k and f(x) has degree n-k-1, this remainder is just f(x) ≠ 0. QED. Notice that it was not required that g(x) divide evenly into xn - 1. Fact 6: The cyclic code of Fact 5 detects all burst errors of length r ≤ n-k. It does not detect all burst errors for r > n-k, but statistically it can detect a lot of them. For GF(2), here are the conclusions: fraction of burst errors NOT detected for r = (n-k) + 1: 1/2(n-k-1) fraction of burst errors NOT detected for r > (n-k) + 1: 1/2(n-k) For example, if n-k = 32 as in CRC-32, then 1/2(n-k-1) = 1/231 ~ 10-9. For such a code, only one burst error out of a billion goes undetected even if the burst extent is the entire packet! And all bursts of extent 32 or less are detected. Proof: See Theorem 6 of the original Peterson and Brown CRC paper appearing in the References.