CRC (cyclic redundancy check) Understanding an Optimization

Question

Over the past few days I've been trying to understand how CRC works. I am stuck on a particular optimization that is recommended for its implementation.

What I understand:

*CRC is polynomial division where bits represent powers of x. I can do a division (using regular polynomial division or using bits) and correctly get the CRC.

*A shift register is used to hold the remainder. It is n bits (for a polynomial of degree n) because each subtraction affects at most n bits. Once the entire message is fed through the register, it contains the division remainder.

Where I'm stuck:

On this page: http://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks the Implementation section has some pseudocode. I'm fine with the first pseudocode and with its two problems (though the first is easily solved). I cannot understand the second, and how associativity/commutativity of xor helps. By hand, I see that the second pseudocode works, but why?

Other sources: A few other articles give this same optimization (feeding the bits in at the left of the register rather than the right). In particular, this article: http://www.ross.net/crc/download/crc_v3.txt in section 10 does it (text-search the word mangled). Except that this does it with tables, and I'm not ready for tables yet! It does say that the final n iterations serve only to get the tail of the message to the left of the register, and I understand that, but again I can't understand the optimization here.

Edit: I found another reference (page 8): http://www.hackersdelight.org/crc.pdf but this one still doesn't help. It says that pre-multiplying is the same as post-multiplying, but I don't see how this is true given that this changes the bits that are in the register when 1 bits are found at the left of the register (to trigger a subtraction).

Thanks. I appreciate your help with my curiosity here!

Dan

Answer 1

In the first pseudo-code, the remainder is initialized with leading portion of the input bit string. Then during iterations, in each step the remainder is up-shifted, and the now-vacant bottom bit is filled with the next bit from the input bit string. To complete the operation, the input bit string needs to be appended with zero. These zeros will effectively flush out data through the remainder during computation.

In the second pseudo-code, the remainder starts clear (full of zeros). During iterations, the next bit from the input bit string is placed directly at the top position in the remainder. Therefore no initialization and no flushing are necessary to complete the computation. In addition, test of the top bit and up-shifting of the remainder operations are re-ordered.

You can convert the first pseudo-code algorithm to the second pseudo-code algorithm in few transformation steps as follows.

Starting with pseudo-code of the basic algorithm (code fragment 1):

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := polynomialForm(bitString[1..n])   // First n bits of the message
    for i from 1 to len {
        remainderPolynomial  := remainderPolynomial * x + bitString[i+n] * x0   // Define bitString[k]=0 for k>len
        if coefficient of xn of remainderPolynomial = 1 {
            remainderPolynomial  := remainderPolynomial xor generatorPolynomial
        }
    }
    return remainderPolynomial
}

First transformation is to swap the order of updating the remainder polynomial and testing the top bit i.e. we can test the second-top bit (before up-shifting), then in the if branch update the remainder before xor-ing with the generator polynomial, and add else branch that also updates the remainder (in case the top bit is zero). Further, note that update of the remainder is essentially up-shifting it and then setting the empty bottom bit to the next bit from the input bit string. So the + operation is basically doing 0 + ? and this is equivalent to 0 xor ?. By applying these principles we now get the following equivalent pseudocode:

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := polynomialForm(bitString[1..n])   // First n bits of the message
    for i from 1 to len {
        if coefficient of xn-1 of remainderPolynomial = 1 {
            remainderPolynomial  := (remainderPolynomial * x xor bitString[i+n] * x0) xor generatorPolynomial
        } else {
            remainderPolynomial  := remainderPolynomial * x xor bitString[i+n] * x0
        }
    }
    return remainderPolynomial
}

Now, notice that in the loop we take bitString[i+n] and put it at x0 position. The bit then gets shifted up during subsequent computation. We can conceptually change bitString[i+n] * x0 to bitString[i] * xn. And if we take it out of the if/else branches and do it before up-shifting the remainder (... * x), we get ... xor bitString[i] * xn-1. And because we are now placing bits from the input bit string at the top of the remainder, we simply clear the remainder at the beginning and do not need to append zeros to flush out the data through the remainder register. Voila, we now have pseudo-code of the modified algorithm (code fragment 2):

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := 0
    for i from 1 to len {
        remainderPolynomial  := remainderPolynomial xor (bitstring[i] * xn-1)
        if (coefficient of xn-1 of remainderPolynomial) = 1 {
            remainderPolynomial  := (remainderPolynomial * x) xor generatorPolynomial
        } else {
            remainderPolynomial  := remainderPolynomial * x
        }
    }
    return remainderPolynomial
}