Re: summary

[Luben Tuikov <luben@splentec.com>]

Vince,

Part 1
======

D = Divide only simple circuit.
SMD = Simultaneous Multiply and Divide.

Now, in SMD we never talk about prepending the message.
In SMD we only talk about what we do to the first 32 MSb
of the message and that is only because we know how
the circuit works.

We talk about prepending (prefixing) only for D.

Now follow carefully and check the following,
some of it is really trivial and some is very
tricky to _see_ and understand.

Let k = the message bits,
    n = deg G(x), also = to # of bits in CRC

In D:
-----
(0)  M'(x) = x^n M(x) + x^n x^k D(x)
           = x^n ( M(x) + x^k D(x) )

where D(x) is some initial constant poly. The above means
that we are prepending the message with D(x) and we are
allocating 32 0's at the end.

Now since we are going to divide by G(x) anyway,
lets see the equivalence:

(1)  M'(x) =  x^n M(x) + x^k E(x)  (mod G(x))

deg E(x) = n-1,  so deg(x^kE(x)) = k+n-1,
and deg(x^nM(x)) = k+n-1

so here is where we see that prepending the message with
D(x) is equivalent to XORing the 32 MSb of the
message with E(x).

In (1) we can factor out x^n,
resulting in a similar conclusion:
                             k-1 
(2)  M'(x) = x^n ( M(x) +    SUM e_i x^{k-n+i} )
                           i=max(0, n-k)

When k >> n, i.e. message bits are a lot more than the
width of the CRC (32 bits), which is 99.99% of the time,
then the above expression just XORs the bits of E(x)
to the 32 MSb of the message and THEN the message is
multiplied by x^n.

When k < n, i.e. the message has less than the bits of
the CRC width then we also XOR, but only the bits which
make sense.

Part 2
======

Now imagine a ``serial'', or long division simple
circuit:
Now from (2), we can derive SMD, by noting that
multiplication by x^n allocates n 0's at the end of M(x).
The reason for this is that the computation will be
carried out for n more clicks, i.e. until the
REAL data is out the left, and the CRC is full of
those n 0s (32 0s).

Also imagine the message as a long string of bits
and the CRC below it, bit by bit shifting to the
right (started from the far left, exactly as in
long division). At any moment of the computation
the contents if the CRC is a function of the
initial constant and the number of ``clicks''
and the current window of bits we are under
of the message. (at the very beginning that state
was the constant XOR 32 MSb of the message)

But,
(3) A xor (B xor C xor D xor .... xor X)
         = (A xor B xor ... xor Y) xor X

and also note that the decision is made ONLY when
a bit pops out the left of the CRC register.

IF 1 poped out we put the next mesage bit at the right
and then we xor with the poly,
ELSE we just put the next message bit at the right
(this is equivalent to long division and I'm sure
are know it very well)

So instead of the message bits travelling through
the register each time going another XOR with some
value which is equal to some funcion of the number
of clicks and initial const, (CRC(0 state) = const XOR 32 MSb
of message) (0 state is initial state)

  I can keep the message bits separate and
xor only when I need to.

So at 0 state: CRC = const XOR 32 MSb of message.
at 1 state CRC = CRC shifted left, next message
bit appended and xored with the Poly given
a what popped out, etc.

Upon close inspection I see that

(4)
               | CRC(i-1) << 1 XOR poly(32 LSb)
CRC(i state) = {
               | CRC(i-1) << 1

Plus the message bits being XORed at each click,
which I've isolated now. I.e. a window of n message
bits being XOR-ed at each click.

The first condition above if the
message bit XOR the bit poping out is 1,
and the second if 0.

All this is by (3).

Now at the very last state of the CRC I'd
have a window of 0, being XORed with
the CRC and THAT WILL BE MY final CRC value,
All the other bits of the message went through
the CRC register to change my XOR-ing pattern
as seen above (4).

But a xor 0 = a, so here is SMD:
======================
0. The CRC register contains the CRC
---atomic----
1. Take the next bit B.
2. Shift left the CRC register, bit A popped out.
3. If A xor B is 1 (one) then 
     CRC = CRC XOR last 32 bits of poly
     (since G(x) is 33 bits)
   else
     NOTHING (CRC was already shifted left in 2.)
---atomic----
4. The CRC register contains the CRC.
=======================

Initial constraint: CRC should be initialized to
0xFFFFFFFF.

Part 3
======

Now, we ask: what is this 0xFFFFFFFF 
equivalent to in D?

Well, going back to our definitions:
0xFFFFFFFF is E(x).

Looking at  (1) and (0) we see that
we are seeking D(x) where:

  x^nD(x) = K(x)G(x) + E(x)  (mod G(x))

where deg x^nD(x) = 2n-1  <- that is important!
so the LHS has to have deg = 2n-1
but  deg E(x) = n-1,
thus deg K(x)G(x) = 2n-1,
but  deg G(x) = n
thus deg K(x) = n-1  <- that is important!

Note that all n-1 lower degree terms of x^nD(x) are 0,
and that E(x) is all 1's. This implies that
the n-1 lower degree terms of K(x) are 1s.

Now, 
            n-1
 K(x)G(x) = SUM k_i x^i G(x)
            i=0

But we are interested only in the n-1 lower terms.
So let
        n-1          n-1-i
 R(x) = SUM k_i x^i ( SUM g_j x^j )
        i=0           j=0

Now this gives a linear system G*K = R,
where G is (n)x(n), K is (n)x(1) and
R is (n)x(1).

We need to solve for R = [n 1's] = [32 1's].

Then K = inverse(G)*R.

Finding K is trivial. Finding K(x)G(x) is also
trivial.
Then 
  x^n D(x) = K(x)G(x) + E(x)
           = 0x2a26f82600000000 + 0xFFFFFFFF
           = 0x2a26f826FFFFFFFF

so D(x) = 0x2a26f826.

Thus in simple division-prepending-postfixing
algorithm, prepending the message by D(x)
(equivalently init the CRC by D(x)) and postfixing
the message by 32 0's and then computing the CRC

is EQUIVALENT to simultaneous multiply and divide,
WITHOUT the message being prefixed or postfixed
(it doesn't make sense). ONLY the CRC has to be
init to 0xFFFFFFFF.

Part 4 (please implement and verify!!!!)
======

Lets test and verify the examples as given
in the iSCSI draft: 28 zeros, 28 ones,
28 incs (0..27), and 28 decs (27..0).

Those are bytes AND are BIG endian on bytes
BIG endian on bits in memory, e.g.
natural (black board) order of bytes and bits.

A. mirror the bytes all 28 of them.
B. initialize CRC to 0xFFFFFFFF.
---atomic---
1. Take the next bit B.
2. Shift left the CRC register, bit A popped out.
3. If A xor B is 1 (one) then 
      CRC = CRC XOR last 32 bits of poly
      (since G(x) is 33 bits)
   else
      NOTHING (CRC was already shifted left in 2.)
---atomic----
C. The CRC register contains the CRC.

Please note that this algorithm means that we do
not need any information on what the PREVIOUS
bit(s) is(are) or what the NEXT bit(s) is(are).

Implement this -- simulation, circuit, program,
whatever and then let me know what you get.

-- 
Luben Tuikov, Senior Software Engineer, Splentec Ltd.
Bus: +1-905-707-1954x112, 9-5 EST. Fax: +1-905-707-1974.