clearing up CRC

Clearing up the CRC business PhL 7.3.13 Part I : Correcting wrong statement about error detection of CRC. 1 Part II : Correcting confusing comments about n,k and cyclicness. 6 Part I : Correcting wrong statement about error detection of CRC. Before I do this, I have to get straight these three words period of some h(x) min poly in Galois theory where smallest n such that (xn-1)/h(x) is even order of an element α of GF(q) exponent of GF(q) as I used it in Galois (order of largest cyclic subgroup of GF(q) - 0. exponent as used in the CRC original paper below. ( where it means period! ) Here was my erroneous CRC statement _______________________________________ So imagine a packet of 100,000 bytes followed by 16 parity check bytes all stored on some medium. In theory, the code distance could be d = 17 in this example, according to (7.34), so in the long data packet (code word) there would have to be a 17-symbol (17-byte) error in order that the code word be interpreted as some other valid code word. Since symbol errors are presumably rare, perhaps on the order of 10-6, an error of 16 or less bad symbols would be reliably detected by this CRC scheme. _______________________________________ July 3, 2013. I am preparing to fix my CRC problem. I have started reading (proofing) at Section 7 (f) which is the first discussion of distance. I am making tiny edits along the way, cosmetic really. (f) is excellent (g) is excellent (h) just fine (i) also just fine, mention of turbo codes, and here Chapter 7 ends. There is really not much about "distance" other than definition and a few facts. If you know the H matrix, then you might know the distance! The CRC packet has k = 1000 data symbols and perhaps n-k = 16 parity check bits. I will continue reading into Chapter 8. opening -- good example, fine (a) OK, but reader still has no idea what the cyclic systematic basis is. That comes next (b) I claim that for the cyclic systematic basis, you can find a matrix G that does the same thing in a regular block code, but I never pursue this idea. This section is OK (c) encoders and decoders and syndrome in the systematic basis. Maybe I should have called this thing S(x), since it is no doubt different from the s mentioned in the previous block code chapter. But that was a vector, and now we have s(x), I think it is OK to stay with s(x). (d) is the CRC section! ________________________________________________________________________- OK, I am now ready to start working on the problem. I have put in red my wrong statements. We know that d ≤ n-k+1 so d ≤ 17 for the CRC situation. But no one says this is a maximal length code, so no one can say that d = 17 for example. So do I know anything about d in this situation? d = smallest distance between any pair of code words d = min weight of all the code words = the min number of non-zero symbols in a code word! Suppose the entire data packet was zero. Then the parity check bits would be 0 I am pretty sure from (8.8) and then result is an all zero code word and d = 0 ! But we could rule out such a data packet. Suppose that for an ensemble of k = 1000 long data packets, each packet has at most 50 zeros. Then the parity checks won't all be zeros, but suppose they were. Then all n packets have ≤ 66 zeros, so they all have weight > 1016-66 = 1000 - 50 = 950 so d = 950! If we scramble the data stream, then the probability of having a lot of zero bytes can be statistically computed and is small. So this is some kind of statistical problem. _____________________________________________________________________________ So now I will go to the web and see what I can find. I found the original CRC paper! The CRC was invented by W. Wesley Peterson in 1961. Wow, this is the author of the book, I never knew this connection to CRC. The first edition was 1961. I wonder what he called CRC at that time, and maybe that is where it is located in the book! Proceedings of the IRE  (Volume:49 ,  Issue: 1 ) "Cyclic Codes for Error Detection" I have the paper now as a PDF from somewhere. Let's lock onto his conventions before trying to decode the theorems claimed. n, k same as me m-tuple ordered with first symbol the lowest power of X highest order sent first same as me, but his argument seems wrong so I ignore it P(x) generator degree n-k same as my g(x) generator degree n-k m = degree code polynomials divisible by P(x) check G(x) = message poly = my d(x) data poly H(x) = received message F(x) = code poly, has degree < n he says (does not use "code word") E(x) = difference H(x)-F(x) t = number of errors detectable m = maximum possible value of exponent e = my q-1 = pm-1 = 2m - 1 for him ( page 1961 left) n = length of code words = same as mine = q-1 for a Galois Induced Code. e = exponent to which any P(x) belongs means smallest e such (xe-1)/P(x) has no remainder. So his exponent = my period!! For sure, here it is stated: Theorem 1: If g(x) has more than one term, all single errors will be detected. Also, all odd numbers of errors. I think this is the same as parity. Example: If g(x) is a prim poly for GF(216) which has q = 216 = 65,536, it has degree n-k = 16 and period = exponent = q-1 = 65535. Code words have n = q-1 = 216-1 = 65535 symbols. So this is indeed a pretty long packet and we get single and double detection! My comment: Such a P(X) cannot be a primitive polynomial since 1 is one of the roots. Here is the most impressive claim, since it makes no requirement of the length of the code. I think this is the benefit you get over parity. Notice the definition of burst as just the range between first and last error. This is a theorem I could quote, and I should add this paper as a reference. OK, I think I have extracted everything useful from this original paper, it took a while, so I now want to look at a more modern source. ____________________________________________________________________________ I have found another good reference but don't have it yet. Numerical recipes third edition. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. But first lets look at another source crc.pdf which I have: The first items reassert single and double symbol errors detected (but called bits not symbols). The third item excludes G from being a prim poly, but gets all odd bit errors detected. So nothing really new here compared to the original paper. Realization: Assume GF(pm) is used, and in these cases GF(2m). The period max is q-1 = 2m - 1 and this is the size of the code packet protected by the checksum. Larger m means longer protected packet! ________________________________________________________________________ My CRC paper quotes some standards and says the first three polys have (x-1) as a factor, which to me means they are not primitive. They do this to be able to detect all odd-bit errors. Perhaps the last one is primitive. Let's see if it is in the P&W list. First, here is their limited data on m = 32, where recall that EFGH are primitive. Fact: The Hex notation for the CRC=32 case does not include the leading power! Horrors. here is why So it takes me a lot of work to fix this up and then compare it to the P&W table. But I see what I wanted to know, it is irreducible but not primitive! OK, I have run out of steam on the above path. But I think I know enough now about the error detection ability of a CRC scheme and I can alter Galois accordingly. Part II : Correcting confusing comments about n,k and cyclicness. This is a separate topic, also confusing. My "scream out" comment is (8.29), very hard to find. But hold n that for moment and go back to MY definition of a cyclic code. I say to start by picking an integer n and then "find" some g(x) that divides into xn - 1. Stop right there, I have lots of questions already. ______________________________________________________________________ Question 1. Can you find such a g(x) of any degree you want that is less than n ? The answer is no. Even for GF(2) the answer is no, but in general there are many degrees of g(x) that do work. See counter examples below etc etc. I interpret this question to say " The polynomial xn-1 lies in my polynomial space R with coeffs in GF(p). Can you find a g(x) for any degree you want where g(x) lies in R and g(x) divides xn - 1 ? " In general I don't know how to answer that question. But if it happens that n = q-1 = pm - 1 for prime p and positive integer m, then I know one possible answer: any g(x) which is a minimum polynomial of GF(q) works. This is because such a g(x) contains a subset of the factors of xn- 1 and is in R. In this specialized case, I don't think g(x) exists for any degree < n. For example, for GF(25) all min polys have degree 5. So if you choose n = 25-1 = 31, then the only possible g(x) have degree 5 ! In the case GF(24) I tried all possible g(x) and classified each of them A,B,C,D,E. I found 4 min polys. Three had degree 4 and one had degree 3. Here n = 24-1 = 15. So for x15- 1 I think the only g(x) in R that divide evenly are these min polys. But that is wrong as next paragraph shows! I guess I could just try all possible polys and see if this is true. I don't really have a proof. I just did this for GF(2) case that n = 24 - 1 = 15. I divide (x15-1) by all possible polys in R of degree 15 and less, and I do in fact find a g(x) that divides evenly for every single degree ≤15. I am surprised. All the successful g(x) have a "+1" which I guess makes sense since x does not divide x15-1 . Some degrees have several candidate g(x). I tried the same program for x14-1 and get the same kind of result. BUT, it does not work in the general case. Here is a counterexample: You see that degree = 2 and 3 are missing, there is no g(x) that works for these degrees of g(x). I first made sure that the code really does sequence through all possibly polys in ever increasing degrees. This example shows that (x5-1) cannot be divided by any g(x) of degree 2 or 3 ! I did this by hand and confirmed the result. I tried to find (x2+bx+1)(x3+βx2+δx+1) = (x5-1) You get a set of equations in variables b,β,δ which cannot be solved. You get b + b + 1 = 0 which has no solution for b, for example. So I am sure this is a true fact. There are lots of counterexamples: Not all are prime, not all are even. n = 5 no degree 2 or 3 n = 7 no degree 2 or 5 n = 9 no degree 4 or 5 n = 10 no degree 3 or 7 n = 14 OK, all degrees present n = 15 OK, all degrees present So it just happened that the first two cases I tried worked. ______________________________________________________________________ Idea: Suppose we want g(x) to divide xn-1. Suppose g(x) factors into g1g2 because it is reducible. Then we want (g1g2) to divide xn-1. That requires that each of g1 and g2 divide xn- 1 !!! (xn-1)/(g1g1) = h => (xn-1)/g1 = g2h so g1 must divide xn-1. Example: If g = xg2, then x must divide xn-1, but it clearly does not, so this form can never work, and that is why there is always a "+1" in the above. _______________________________________________________________________ Conclusion: I think that for any n, you can find one or more g(x) in R for each degree ≤n that divide xn-1 [wrong!] . If you restrict to the case that n = 2m- 1, some of these g(x) will be min polys of GF(2m). The above example had m = 4 since I picked n = 15. Here are the min polys for GF(24): p1(x) = (x - α)(x - α2)(x - α4) (x - α8) = x4 + x + 1 10011 p7(x) = (x - α7)(x - α14)(x - α13)(x - α11) = x4 + x3 + 1 11001 m3(x) = (x - α3)(x - α6)(x - α12)(x - α9) = x4 + x3 + x2 + x + 1 11111 m5(x) = (x - α5)(x - α10) = x2 + x + 1 111 (6.21) and yes, they all appear on the above list. Resume now: So I first pick an integer n as in (8.2). I now know I can next pick some k < n, any value I want. There will be some g(x) of degree n-k that divides xn - 1. [ This is true, but only after I did a lot of work elsewhere!! ] So I can make a cyclic code for any (n,k) pair that I want! I am still working inside GF(2) of course, that is my R world [ true for GF(p)]. So starting off in Chapter 8, I really have no Galois connection at all except GF(2) is a GF. I can talk about irreducible with respect to GF(2), that is true. But there is no min poly connection, nothing like that. This is the context of things when I have my little CRC subsection. So given this context, I can probably pick any values of n and k and m = n-k that I want. If I pick n-k = 16, then I can pick any k that I want, and have n = k+16. So my comment seems way off base. For any n I can even find a g(x) of any degree m ≤n which divides xn- 1, so my CRC g(x) can always then be cyclic. _______________________________________________________________________ More questions: Question 2: Do the theorems of the CRC Peterson paper require that code by cyclic? I suspect yes. Let's see how he defines his stuff. On his page 228,229 nothing about xn-1. Key point: if the received codeword cannot be divided by g(x) due to error, then neither can the error codeword. So if you have a 1 bit error, the error codeword is just xi and certainly you cannot divide this by any g(x)! That is why it detects single bit errors! Good. OK, I understand better the opening discussion: Now he continues If you pick an arbitrary P(x) = g(x), must it have an exponent e ? He is quiet on this. His double correction comment also seems good. OK, now he is more explicit concerning exponent e. We are no longer talking about a general e, we are talking about e having the form e = q-1 = 2m -1 and we are dealing now with GF(2m). For such a value of e, I know that I can find a prim poly g(x) and its period will be q-1 so that will be the lowest e. So for code words not too long, you get double-bit error detection. He really is setting n = 2m - 1 = e, so this is the same as my n in my cyclic code definition Conclusion: You must have some exponent for your generator, or Theorem 3 does not fly. Question 3: Is it possible that some given g(x) won't divide xe-1 no matter how large e is allowed to be? I don't know. But if it is possible, then we might say e = ∞. In this case, look at the Theorem 3. The proof is still flawless and it seems we can have n then be any size we want (code word length). Pete is interested in those prim polys because we get at least some value for e. I suspect there is always some finite e for the GF(2) case. Idea: Suppose we start with some n for our xn - 1 and we define everything over GF(p). We can then start running through all the extension fields GF(pm) for m = 1,2,3....∞. For each m, we have q-1 = pm-1 being the largest possible value for which a min poly divides xe - 1, that is to say, q-1 is the largest possible value of order = period of a min poly. So here is a question: Question: For GF(pm), is there at least one element of each order from the set divisors(q-1) ? [ yes! ] Suppose this were true. Then we systematically try m = 1,2,3... and for each m, we list off the divisors of q-1 and then we know that for each such divisor we have an α of that order and thus a min poly of that period = order. We do this until we eventually hit the value n that we started with. 1. For GF(23) I find { α, α2, α4 }, { α3, α6, α5 }, {1} (5.23) prim prim In this example, q = 23 = 8 and so q-1 = 7. Both polys are order 7, there are no divisors, boring. 2. For GF(24) α15 = 1 and we get q-1 = 15 and { α, α2, α4, α8 }, { α3, α6, α12, α9 }, { α5, α10 }, { α7, α14, α13, α11 }, {1} (5.26) prim prim order = 15 order = 5 order = 3 order = 15 All these min polys divide x15- 1. Do I know the order of each conjugate set's elements? The size of the sets are associated with the degree of the min poly, not the order. For each set, I have to do this test: test first element: is (α3)5 = 1? Yes, so 5 is a candidate order of α3 is (α3)3 = 1? No, since α9 ≠ 1 so 3 not a candidate Therefore order α3 = 5. You have to try out each divisor d of q-1 and test to see if (αb)d = 1, and pick the smallest d. The statement (αb)d = 1 means bd = multiple of 15. In the above example we DO have min pols of order 3, 5 and 15. Well consider We can never hit an even integer since q = 2p = even and q-1 = odd. So for example, we are never going to find a min poly that divides x4 - 1. So n = 4 has no g(x). But for other values of p, this conclusion does not follow. I might comment on this somewhere. Are all odd values hit? I think eventually they will be, but how would you prove that? I wrote a little test program for p = 2 and seems true. In general I think pm- 1 can never be a multiple of p. Yes, this is special case of my lemma Lemma: Show that GCD( pi, (pm-1)/K) = 1 for i = 0,1....m (note that m ≥ i ) . (5.35a) GCD( p, (pm-1)) = 1 This says that (pm-1) is not a multiple of p. That means that (pm-1) cannot have p in its set of divisors. That means that no multiple of p is in the set of divisors. Ie, if A/p ≠ int, then A/np ≠ = (1/n)A/p ≠ int. This is born out for p = 3 by my same code. Fact: When you select your value of n, n cannot be a multiple of p. The reason is that any multiple of p is never in the set divisors(pm-1) for any m, so you can never have an α which has an order which is a multiple of p, and thus you can never have period p for a min poly. I should get this stated correctly and then add it somewhere. Probably every other value of n is OK. Conclusion: If we pick any n not a multiple of p, then our plan of scanning all the GF(pm) for m = 1,2,... will eventually produce a min poly which divides xn-1. We will eventually find among the divisors of pm-1 then umber n and for the winning m, that means that n is a possible value for the order of an element of that GF. If we knew that a GF has at least one element of each possible order, then we have it. But I have not shown that part yet. Idea on showing that in any GF(q) there is an element whose order is each divisor of q-1 Form the set of divisors(q-1). We know order(αk) = (q-1)/gcd(k,q-1). For each divisor element d, try to find a k that satisfies this equation. I think I can make this fly. d = (q-1)/I = (q-1)/ gcd(k,q-1) => I = gcd(k,q-1) So for a given q-1, and a given divisor I, is there always a value of k in the set 1..q-2 so I = gcd(k,q-1) ? Could write that as I = gcd(k,dI). I think this needs a Maple run before I do more. Maple suggests that k = I is always a solution. So is this true I = gcd(I, q-1) where I is a divisor of q-1 ? We know that I divides q-1 and I divides I, and no greater integer could divide I do no greater integer could divide both, so I is in fact the gcd, simple! Claim: For any divisor I in the set divisors(q-1) there exists an element of GF(q) whose order is I. Proof: We know from (4.21) that [order(αk)] = (q-1)/gcd(k,q-1). Suppose I is a divisor of q-1. Then we can write IM= q-1 where M is the other factor. M then also divides q-1. We know that [order(αM)] = (q-1)/gcd(M,q-1) But we claim that gcd(M,q-1) = M. The reason is that M is a candidate GCD since it divides M and q-1, and no larger integer can divide M, so M is it. Thus we have shown that [order(αM)] = (q-1)/M = I. Thus we have found an element of GF(q), namely αM , which has order I, for any I in divisors(q-1). Therefore, the conjugate set of αM has order I and corresponds to a min poly of order I which has period I! Conclusion: For every integer I in divisors(q-1), there exists at least one min poly with period I. I think I have a solid proof of this claim. The subgroup is what has order n, and this has to divide q-1. But who says we have a subgroup for each candidate order? So I come back to the other claim: // stop ________________________________________________________________________________ Question 4: Using my definition, what bad thing perhaps happen if n is not the period of g(x)? Do you still get a cyclic code? We could compare n1and n2 . [ this is now well answered ] Question 5: Pete talks about code words of length n ≤ e, whereas I seem to assign n to be e. For the prim poly situation, we do know that e = q-1. Otherwise we are not really sure how low e might be. [ this is now explained in the CRC section and yes, n < e is needed for double-bit errors. ] I think question 4 is the only one I need to look at. I think it causes code words to have repeated sections or something like that, which is probably OK. I could add a comment that if n is the period, then we get exhaustion. But does that proof work without regard to Galois theory?