parallel CRC and ragged words

M

Matt

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

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

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.
Click to expand...

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

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.
Click to expand...
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
 
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))

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
Click to expand...
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
 
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))

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?
Click to expand...


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
 
On Feb 9, 5:05 pm, Allan Herriman <allanherri...@hotmail.com> wrote:
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))

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
Click to expand...
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
 
In article <a9dbb914-48ad-4bcc-b2f2-589ebb28c137@o4g2000pbc.googlegroups.com>,
Matt <maplante80@gmail.com> 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.
Click to expand...
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top