Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > parallel CRC and ragged words

Reply
Thread Tools

parallel CRC and ragged words

 
 
Matt
Guest
Posts: n/a
 
      02-08-2012
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....7b14d0fc43dbc1

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))

If I use some some test code, and the easics crc generator (http://
www.easics.com/webtools/crctool) :

reg [31:0]a = 32'haaaaaaaa;
reg [31:0]b = 32'hbbbbbbbb;

@(posedge clk) crca = nextCRC32_D64({{32{1'b0}},a}, {32{1'b0}});
@(posedge clk) crcab = nextCRC32_D64({a,b}, {32{1'b0}});
@(posedge clk) crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});

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.

Thank you
 
Reply With Quote
 
 
 
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      02-08-2012
In comp.lang.verilog Matt <(E-Mail Removed)> 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....7b14d0fc43dbc1


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.

-- glen
 
Reply With Quote
 
 
 
 
Matt
Guest
Posts: n/a
 
      02-09-2012
Hi Glen,

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 <(E-Mail Removed)> wrote:
> In comp.lang.verilog Matt <(E-Mail Removed)> 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....m/thread/587b1...

>
> 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.
>
> -- glen


 
Reply With Quote
 
Mark Curry
Guest
Posts: n/a
 
      02-09-2012
In article <(E-Mail Removed)>,
Matt <(E-Mail Removed)> 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....7b14d0fc43dbc1
>
>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))
>
>If I use some some test code, and the easics crc generator (http://
>www.easics.com/webtools/crctool) :

<snip>

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.

A great reference for crcs is:
http://www.ross.net/crc/download/crc_v3.txt

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.

Regards,

Mark



 
Reply With Quote
 
Allan Herriman
Guest
Posts: n/a
 
      02-09-2012
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....dl/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))
>
> If I use some some test code, and the easics crc generator (http://
> www.easics.com/webtools/crctool) :
>
> reg [31:0]a = 32'haaaaaaaa;
> reg [31:0]b = 32'hbbbbbbbb;
>
> @(posedge clk) crca = nextCRC32_D64({{32{1'b0}},a}, {32{1'b0}});
> @(posedge clk) crcab = nextCRC32_D64({a,b}, {32{1'b0}}); @

(posedge
> clk) crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});
>
> 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.

Regards,
Allan
 
Reply With Quote
 
Allan Herriman
Guest
Posts: n/a
 
      02-09-2012
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....dl/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))
>>
>> If I use some some test code, and the easics crc generator (http://
>> www.easics.com/webtools/crctool) :
>>
>> reg [31:0]a = 32'haaaaaaaa;
>> reg [31:0]b = 32'hbbbbbbbb;
>>
>> @(posedge clk) crca = nextCRC32_D64({{32{1'b0}},a}, {32{1'b0}});
>> @(posedge clk) crcab = nextCRC32_D64({a,b}, {32{1'b0}}); @

> (posedge
>> clk) crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});
>>
>> 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
 
Reply With Quote
 
Matt
Guest
Posts: n/a
 
      02-09-2012
On Feb 9, 6:34*am, Allan Herriman <(E-Mail Removed)> 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....dl/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))

>
> >> If I use some some test code, and the easics crc generator (http://
> >>www.easics.com/webtools/crctool) :

>
> >> reg [31:0]a = 32'haaaaaaaa;
> >> reg [31:0]b = 32'hbbbbbbbb;

>
> >> * * * *@(posedge clk) *crca = nextCRC32_D64({{32{1'b0}},a}, {32{1'b0}});
> >> * * * *@(posedge clk) *crcab = nextCRC32_D64({a,b}, {32{1'b0}}); @

> > (posedge
> >> * * * *clk) *crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});

>
> >> 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?

Thanks for your help,

-- Matt
 
Reply With Quote
 
Allan Herriman
Guest
Posts: n/a
 
      02-09-2012
On Thu, 09 Feb 2012 09:31:18 -0800, Matt wrote:

> On Feb 9, 6:34*am, Allan Herriman <(E-Mail Removed)> 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....dl/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))

>>
>> >> If I use some some test code, and the easics crc generator (http://
>> >>www.easics.com/webtools/crctool) :

>>
>> >> reg [31:0]a = 32'haaaaaaaa;
>> >> reg [31:0]b = 32'hbbbbbbbb;

>>
>> >> * * * *@(posedge clk) *crca = nextCRC32_D64({{32{1'b0}},a},
>> >> * * * *{32{1'b0}});
>> >> * * * *@(posedge clk) *crcab = nextCRC32_D64({a,b}, {32{1'b0}});
>> >> * * * *@
>> > (posedge
>> >> * * * *clk) *crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});

>>
>> >> 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
 
Reply With Quote
 
Matt
Guest
Posts: n/a
 
      02-10-2012
On Feb 9, 5:05*pm, Allan Herriman <(E-Mail Removed)> wrote:
> On Thu, 09 Feb 2012 09:31:18 -0800, Matt wrote:
> > On Feb 9, 6:34*am, Allan Herriman <(E-Mail Removed)> 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....dl/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))

>
> >> >> If I use some some test code, and the easics crc generator (http://
> >> >>www.easics.com/webtools/crctool) :

>
> >> >> reg [31:0]a = 32'haaaaaaaa;
> >> >> reg [31:0]b = 32'hbbbbbbbb;

>
> >> >> * * * *@(posedge clk) *crca = nextCRC32_D64({{32{1'b0}},a},
> >> >> * * * *{32{1'b0}});
> >> >> * * * *@(posedge clk) *crcab = nextCRC32_D64({a,b}, {32{1'b0}});
> >> >> * * * *@
> >> > (posedge
> >> >> * * * *clk) *crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});

>
> >> >> 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.

Cheers,

-- Matt

-- Matt
 
Reply With Quote
 
Mark Curry
Guest
Posts: n/a
 
      02-10-2012
In article <(E-Mail Removed)>,
Matt <(E-Mail Removed)> wrote:
>
>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.

--Mark

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
CCITT CRC X1021 parallel calc Niv VHDL 7 05-22-2009 12:02 AM
String::CRC crc function returns incorrect result, why? `Zidane Tribal Perl 1 07-28-2007 08:01 PM
String::CRC crc function returns incorrect result, why? `Zidane Tribal Perl Misc 3 07-27-2007 11:41 AM
crc-8 and crc-16 code... Mamut C++ 5 02-22-2007 02:22 PM
parallel CRC equation generator Shukla, Sunil Kumar VHDL 2 05-31-2005 01:57 AM



Advertisments