All of the identities Allan calls out make perfect sense, except when
I try
#5.) If the CRC register is initialised to zero,
CRC(A & B) = CRC(CRC(A) & B))
I haven't thought about the wide parallel CRC for a while, but...
> All of the identities Allan calls out make perfect sense, > except when I try
> #5.) If the CRC register is initialised to zero,
> CRC(A & B) = CRC(CRC(A) & B))
My guess is that this is the case for the beginning of the
calculation, where some bytes are zeroed out.
With most CRC functions, CRC(0)==0, which my guess is what
he is using. Note the condition that it be initialized to zero.
That only matters at the beginning.
But for just this reason, most CRC's do not initialize to zero,
as it will give the same result for missing X'00' bytes
at the beginning.
As far as doing it for odd byte combinations, my first thought
is to compute it through the end, and then undo the last bytes.
The operation has an inverse, so you can cancel out the bytes at
the end that you don't want. You might be able to do that at
the beginning, too. Keep the complicated logic outside the
critical path.
Yes, the idea is to rotate the unwanted bits following the frame (set
to zero) to the front of the word. The CRC initialized with 0 won't
change as a result. If I understand Allen correctly, he then goes on
to state that you shift in the previous word's CRC (thinking serially,
even though it's a parallel operation), followed by the last few data
bytes of the frame. This is where I'm having the problem. I assume
the intent is to load the lfsr with the old crc data, and then shift
in the remaining data bytes, but it doesn't appear to work the way I'm
attempting to do it.
What's the inverse operation you mentioned?
Thanks,
-- Matt
On Feb 8, 5:24 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> I haven't thought about the wide parallel CRC for a while, but...
> > All of the identities Allan calls out make perfect sense,
> > except when I try
> > #5.) If the CRC register is initialised to zero,
> > CRC(A & B) = CRC(CRC(A) & B))
> My guess is that this is the case for the beginning of the
> calculation, where some bytes are zeroed out.
> With most CRC functions, CRC(0)==0, which my guess is what
> he is using. Note the condition that it be initialized to zero.
> That only matters at the beginning.
> But for just this reason, most CRC's do not initialize to zero,
> as it will give the same result for missing X'00' bytes
> at the beginning.
> As far as doing it for odd byte combinations, my first thought
> is to compute it through the end, and then undo the last bytes.
> The operation has an inverse, so you can cancel out the bytes at
> the end that you don't want. You might be able to do that at
> the beginning, too. Keep the complicated logic outside the
> critical path.
>All of the identities Allan calls out make perfect sense, except when
>I try
>#5.) If the CRC register is initialised to zero,
>CRC(A & B) = CRC(CRC(A) & B))
While not directly answering your question, I'll add my 2 cents.
I commented on this before, but I do it again - I really don't like tools such as
those on easics web site. CRCs in verilog or VHDL are dead-nuts simple. Using
those tools leads to more confusion and obtuse code than not.
For HW guys - don't read past chapter 8. After chapter 8, the doc is all about
optimizing the calcs in SW. For HW, it's really simple - just code up the algorithm shown in chapter 8, and put a for loop in it for the number of bits
you need. Done.
Now you know that basics, there's two references that can help for the
special cases you've got:
J. Satran, D. Sheinwald, and I. Shimony, "Out of Order Incremental CRC Computation" IEEE Transactions on Computers, Vol. 54, No. 9, September 2005.
and
M. Walma, "Pipelined Cycle Redundancy Check (CRC) Calculation". Intel Corporation
(My paper is lacking a clear reference, but it looks to be from some
IEEE doc published in 2007)
Both these papers have some great ideas to do creative things with CRCs, including
similar to what you're trying to do.
On Wed, 08 Feb 2012 14:09:40 -0800, Matt wrote:
> I've been looking over the following post concerning parallel crc
> computation and how to handle a multi-byte parallel bus where the data
> can end in any 8b position:
> http://groups.google.com/group/comp.lang.vhdl/browse_frm/
> All of the identities Allan calls out make perfect sense, except when I
> try #5.) If the CRC register is initialised to zero,
> CRC(A & B) = CRC(CRC(A) & B))
> where nextCRC32_D64 is the easics CRC function, arguments are (data,
> lfsr state)
> I do not get CRC({A, B}) = CRC({CRC(A) , B}))
> I'm replacing the &'s with {}'s, since this originally came from a vhdl
> group, and I'm assuming he's referring to the vhdl concat operator.
> What I actually get is CRC(A) = 85f89652 CRC({a,b}) = 8a0c00ba
> CRC({CRC(A),b} = cae34aea
> I'm sure I must have missed something along the way, but I don't know
> what it is.
> Any help or direction you could provide would be greatly appreciated.
The answer to your question is that the statement #5 I made isn't actually correct (which is another way of saying that it is wrong).
It's *almost* right, but there's something wrong in the detail. I didn't discover this until a co-worker tried to implement a wide CRC following those guidelines and came unstuck, just as you did.
In hand-waving terms, statement #5 says that you can break up the calculation into two parts, which really helps at the end of a packet.
I'll look up some actual code (that works) to see if I can find the error.
On Thu, 09 Feb 2012 10:30:19 +0000, Allan Herriman wrote:
> On Wed, 08 Feb 2012 14:09:40 -0800, Matt wrote:
>> I've been looking over the following post concerning parallel crc
>> computation and how to handle a multi-byte parallel bus where the data
>> can end in any 8b position:
>> http://groups.google.com/group/comp.lang.vhdl/browse_frm/ > thread/587b14d0fc43dbc1
>> All of the identities Allan calls out make perfect sense, except when I
>> try #5.) If the CRC register is initialised to zero,
>> CRC(A & B) = CRC(CRC(A) & B))
>> where nextCRC32_D64 is the easics CRC function, arguments are (data,
>> lfsr state)
>> I do not get CRC({A, B}) = CRC({CRC(A) , B}))
>> I'm replacing the &'s with {}'s, since this originally came from a vhdl
>> group, and I'm assuming he's referring to the vhdl concat operator.
>> What I actually get is CRC(A) = 85f89652 CRC({a,b}) = 8a0c00ba
>> CRC({CRC(A),b} = cae34aea
>> I'm sure I must have missed something along the way, but I don't know
>> what it is.
>> Any help or direction you could provide would be greatly appreciated.
> The answer to your question is that the statement #5 I made isn't
> actually correct (which is another way of saying that it is wrong).
> It's *almost* right, but there's something wrong in the detail. I
> didn't discover this until a co-worker tried to implement a wide CRC
> following those guidelines and came unstuck, just as you did.
> In hand-waving terms, statement #5 says that you can break up the
> calculation into two parts, which really helps at the end of a packet.
> I'll look up some actual code (that works) to see if I can find the
> error.
Got it.
Here's what I originally posted:
#5.) If the CRC register is initialised to zero,
CRC(A & B) = CRC(CRC(A) & B))
I'm inserting CRC(A) 32 bits too soon. Gah!
Instead of "CRC(A) & B" it really should say that the CRC(A) gets xored with the first 32 bits of B, then we take the CRC of that result.
I think B might need to be at least 32 bits long, i.e. it will be the last two words of the packet.
(Apologies to the c.l.verilog readers: ampersand (&) is the VHDL concatenation operator.)
> On Thu, 09 Feb 2012 10:30:19 +0000, Allan Herriman wrote:
> > On Wed, 08 Feb 2012 14:09:40 -0800, Matt wrote:
> >> I've been looking over the following post concerning parallel crc
> >> computation and how to handle a multi-byte parallel bus where the data
> >> can end in any 8b position:
> >>http://groups.google.com/group/comp.lang.vhdl/browse_frm/ > > thread/587b14d0fc43dbc1
> >> All of the identities Allan calls out make perfect sense, except when I
> >> try #5.) If the CRC register is initialised to zero,
> >> CRC(A & B) = CRC(CRC(A) & B))
> >> where nextCRC32_D64 is the easics CRC function, arguments are (data,
> >> lfsr state)
> >> I do not get CRC({A, B}) = CRC({CRC(A) , B}))
> >> I'm replacing the &'s with {}'s, since this originally came from a vhdl
> >> group, and I'm assuming he's referring to the vhdl concat operator.
> >> What I actually get is CRC(A) = 85f89652 CRC({a,b}) = 8a0c00ba
> >> CRC({CRC(A),b} = cae34aea
> >> I'm sure I must have missed something along the way, but I don't know
> >> what it is.
> >> Any help or direction you could provide would be greatly appreciated.
> > The answer to your question is that the statement #5 I made isn't
> > actually correct (which is another way of saying that it is wrong).
> > It's *almost* right, but there's something wrong in the detail. I
> > didn't discover this until a co-worker tried to implement a wide CRC
> > following those guidelines and came unstuck, just as you did.
> > In hand-waving terms, statement #5 says that you can break up the
> > calculation into two parts, which really helps at the end of a packet.
> > I'll look up some actual code (that works) to see if I can find the
> > error.
> Got it.
> Here's what I originally posted:
> #5.) If the CRC register is initialised to zero,
> CRC(A & B) = CRC(CRC(A) & B))
> I'm inserting CRC(A) 32 bits too soon. Gah!
> Instead of "CRC(A) & B" it really should say that the CRC(A) gets xored
> with the first 32 bits of B, then we take the CRC of that result.
> I think B might need to be at least 32 bits long, i.e. it will be the
> last two words of the packet.
> (Apologies to the c.l.verilog readers: ampersand (&) is the VHDL
> concatenation operator.)
> Regards,
> Allan
Hi Allan,
Thanks for the correction! I tried your update, and was able to
generate a correct CRC on a 64b bus for a packet that ended on a 32b
boundary
i.e.
...
64'h2223242526272829;
64'h2a2b2c2d00000000; // last 32b invalid data
However I've been unable to get a correct crc for a packet ending in
any arbitrary position, like:
...
64'h2a2b2c2d2e2f3031;
64'h3200000000000000; // last 56b invalid data
xor'ing the previous crc with the last32b (if you pull from the
previous word, so 32'h2f303132) doesn't work; nor does it work if you
try to xor an 8b chunk of the previous crc with the remaining valid 8b
of data (if proceeded by 0's and the last crc is initialized to 0's).
On Thu, 09 Feb 2012 09:31:18 -0800, Matt wrote:
> On Feb 9, 6:34 am, Allan Herriman <allanherri...@hotmail.com> wrote:
>> On Thu, 09 Feb 2012 10:30:19 +0000, Allan Herriman wrote:
>> > On Wed, 08 Feb 2012 14:09:40 -0800, Matt wrote:
>> >> I've been looking over the following post concerning parallel crc
>> >> computation and how to handle a multi-byte parallel bus where the
>> >> data can end in any 8b position:
>> >>http://groups.google.com/group/comp.lang.vhdl/browse_frm/ >> > thread/587b14d0fc43dbc1
>> >> All of the identities Allan calls out make perfect sense, except
>> >> when I try #5.) If the CRC register is initialised to zero,
>> >> CRC(A & B) = CRC(CRC(A) & B))
>> >> where nextCRC32_D64 is the easics CRC function, arguments are (data,
>> >> lfsr state)
>> >> I do not get CRC({A, B}) = CRC({CRC(A) , B}))
>> >> I'm replacing the &'s with {}'s, since this originally came from a
>> >> vhdl group, and I'm assuming he's referring to the vhdl concat
>> >> operator.
>> >> What I actually get is CRC(A) = 85f89652 CRC({a,b}) = 8a0c00ba
>> >> CRC({CRC(A),b} = cae34aea
>> >> I'm sure I must have missed something along the way, but I don't
>> >> know what it is.
>> >> Any help or direction you could provide would be greatly
>> >> appreciated.
>> > The answer to your question is that the statement #5 I made isn't
>> > actually correct (which is another way of saying that it is wrong).
>> > It's *almost* right, but there's something wrong in the detail. I
>> > didn't discover this until a co-worker tried to implement a wide CRC
>> > following those guidelines and came unstuck, just as you did.
>> > In hand-waving terms, statement #5 says that you can break up the
>> > calculation into two parts, which really helps at the end of a
>> > packet.
>> > I'll look up some actual code (that works) to see if I can find the
>> > error.
>> Got it.
>> Here's what I originally posted:
>> #5.) If the CRC register is initialised to zero,
>> CRC(A & B) = CRC(CRC(A) & B))
>> I'm inserting CRC(A) 32 bits too soon. Gah!
>> Instead of "CRC(A) & B" it really should say that the CRC(A) gets xored
>> with the first 32 bits of B, then we take the CRC of that result.
>> I think B might need to be at least 32 bits long, i.e. it will be the
>> last two words of the packet.
>> (Apologies to the c.l.verilog readers: ampersand (&) is the VHDL
>> concatenation operator.)
>> Regards,
>> Allan
> Hi Allan,
> Thanks for the correction! I tried your update, and was able to
> generate a correct CRC on a 64b bus for a packet that ended on a 32b
> boundary
> i.e.
> ...
> 64'h2223242526272829;
> 64'h2a2b2c2d00000000; // last 32b invalid data
> However I've been unable to get a correct crc for a packet ending in any
> arbitrary position, like:
> ...
> 64'h2a2b2c2d2e2f3031;
> 64'h3200000000000000; // last 56b invalid data
> xor'ing the previous crc with the last32b (if you pull from the previous
> word, so 32'h2f303132) doesn't work; nor does it work if you try to xor
> an 8b chunk of the previous crc with the remaining valid 8b of data (if
> proceeded by 0's and the last crc is initialized to 0's).
> Is there something else I should be doing?
I think it's meant to work like this:
64'h1a1b1c1d1e1f2021;
64'h2223242526272829; // end of 'A'
---------------------
64'h2a2b2c2d2e2f3031; // start of 'B'
64'h3200000000000000; // last 56b invalid data
Lets assume that the CRC register was FFFF after the 'A' calculation.
Take that value, xor it into the start of the 'B' contents
(i.e. the 2a2b2c2d part).
This gives the following:
64'h d5d4d3d22e2f3031; // start of 'B'
64'h 32xxxxxxxxxxxxxx; // last 56b invalid data
Then rotate it so that the end is aligned:
64'hxxxxxxxxxxxxxxd5;
64'hd4d3d22e2f303132;
and zero out the unwanted leading octets:
64'h00000000000000d5;
64'hd4d3d22e2f303132;
Then take the CRC.
Sorry if I'm a bit rusty; I haven't done one of these at this level for about a decade.
> On Thu, 09 Feb 2012 09:31:18 -0800, Matt wrote:
> > On Feb 9, 6:34 am, Allan Herriman <allanherri...@hotmail.com> wrote:
> >> On Thu, 09 Feb 2012 10:30:19 +0000, Allan Herriman wrote:
> >> > On Wed, 08 Feb 2012 14:09:40 -0800, Matt wrote:
> >> >> I've been looking over the following post concerning parallel crc
> >> >> computation and how to handle a multi-byte parallel bus where the
> >> >> data can end in any 8b position:
> >> >>http://groups.google.com/group/comp.lang.vhdl/browse_frm/ > >> > thread/587b14d0fc43dbc1
> >> >> All of the identities Allan calls out make perfect sense, except
> >> >> when I try #5.) If the CRC register is initialised to zero,
> >> >> CRC(A & B) = CRC(CRC(A) & B))
> >> >> where nextCRC32_D64 is the easics CRC function, arguments are (data,
> >> >> lfsr state)
> >> >> I do not get CRC({A, B}) = CRC({CRC(A) , B}))
> >> >> I'm replacing the &'s with {}'s, since this originally came from a
> >> >> vhdl group, and I'm assuming he's referring to the vhdl concat
> >> >> operator.
> >> >> What I actually get is CRC(A) = 85f89652 CRC({a,b}) = 8a0c00ba
> >> >> CRC({CRC(A),b} = cae34aea
> >> >> I'm sure I must have missed something along the way, but I don't
> >> >> know what it is.
> >> >> Any help or direction you could provide would be greatly
> >> >> appreciated.
> >> > The answer to your question is that the statement #5 I made isn't
> >> > actually correct (which is another way of saying that it is wrong).
> >> > It's *almost* right, but there's something wrong in the detail. I
> >> > didn't discover this until a co-worker tried to implement a wide CRC
> >> > following those guidelines and came unstuck, just as you did.
> >> > In hand-waving terms, statement #5 says that you can break up the
> >> > calculation into two parts, which really helps at the end of a
> >> > packet.
> >> > I'll look up some actual code (that works) to see if I can find the
> >> > error.
> >> Got it.
> >> Here's what I originally posted:
> >> #5.) If the CRC register is initialised to zero,
> >> CRC(A & B) = CRC(CRC(A) & B))
> >> I'm inserting CRC(A) 32 bits too soon. Gah!
> >> Instead of "CRC(A) & B" it really should say that the CRC(A) gets xored
> >> with the first 32 bits of B, then we take the CRC of that result.
> >> I think B might need to be at least 32 bits long, i.e. it will be the
> >> last two words of the packet.
> >> (Apologies to the c.l.verilog readers: ampersand (&) is the VHDL
> >> concatenation operator.)
> >> Regards,
> >> Allan
> > Hi Allan,
> > Thanks for the correction! I tried your update, and was able to
> > generate a correct CRC on a 64b bus for a packet that ended on a 32b
> > boundary
> > i.e.
> > ...
> > 64'h2223242526272829;
> > 64'h2a2b2c2d00000000; // last 32b invalid data
> > However I've been unable to get a correct crc for a packet ending in any
> > arbitrary position, like:
> > ...
> > 64'h2a2b2c2d2e2f3031;
> > 64'h3200000000000000; // last 56b invalid data
> > xor'ing the previous crc with the last32b (if you pull from the previous
> > word, so 32'h2f303132) doesn't work; nor does it work if you try to xor
> > an 8b chunk of the previous crc with the remaining valid 8b of data (if
> > proceeded by 0's and the last crc is initialized to 0's).
> > Is there something else I should be doing?
> I think it's meant to work like this:
> 64'h1a1b1c1d1e1f2021;
> 64'h2223242526272829; // end of 'A'
> ---------------------
> 64'h2a2b2c2d2e2f3031; // start of 'B'
> 64'h3200000000000000; // last 56b invalid data
> Lets assume that the CRC register was FFFF after the 'A' calculation.
> Take that value, xor it into the start of the 'B' contents
> (i.e. the 2a2b2c2d part).
> This gives the following:
> 64'h d5d4d3d22e2f3031; // start of 'B'
> 64'h 32xxxxxxxxxxxxxx; // last 56b invalid data
> Then rotate it so that the end is aligned:
> 64'hxxxxxxxxxxxxxxd5;
> 64'hd4d3d22e2f303132;
> and zero out the unwanted leading octets:
> 64'h00000000000000d5;
> 64'hd4d3d22e2f303132;
> Then take the CRC.
> Sorry if I'm a bit rusty; I haven't done one of these at this level for
> about a decade.
> Regards,
> Allan
Allan,
I looks like that may have worked. Thanks for all of your help!
BTW, Mark, I did grab a copy of that "Pipelined Cycle Redundancy Check
(CRC) Calculation" paper you mentioned. Very interesting. I'm a
little confused about where the G matrix comes from and how to
generate subsequent G^P's. I've generated their H up to 16384 and
matched that matrix.
>BTW, Mark, I did grab a copy of that "Pipelined Cycle Redundancy Check
>(CRC) Calculation" paper you mentioned. Very interesting. I'm a
>little confused about where the G matrix comes from and how to
>generate subsequent G^P's. I've generated their H up to 16384 and
>matched that matrix.
My goals in using the paper were a little different - I didn't need
the G matrix, but looks to me it's just the inverse operation of H.
H allows you to "shift N zeros" onto the previous CRC state.
G allows you to unshift N zeros back off. In your case, you'd use
it like - always assume you're shifting through for the full 32 bits.
But, in the case of only 1 byte of the last 4 was valid, you need
to reverse the final shift by three bytes. The G matrix allows
that.
I imagine you calculate it like H - calculate the matrix for one
bit unshift, then raise the matrix to the power of n for the other bits.
