Help with 32 bit CRC (maths ahead...)
Alex McDonald
I've been in discussion about a modified form of a standard 32 bit CRC. The
technique commonly used (as in Ethernet) is:
CRC32( MESSAGE | 0 | CRC32( MESSAGE ) ) = CRC32( MESSAGE )
that is, the CRC of the message augmented by 32 bits of zero and the 32 bit
CRC itself is equal to the original CRC of the message.
My correspondent has suggested that
CRC32( MESSAGE | XCRC32( MESSAGE ) ) = 0
that is, the CRC of the message, augmented with some "inverse" CRC that
results in a CRC of zero, is as strong as the traditional method. I disagree
on two counts;
first, I can't see how to calculate (as opposed to search for) XCRC32(
MESSAGE ) to get a CRC of 0;
second, if I could calculate it, it just looks like 32 bit modulo to me.
This site helped me understand the normal method
http://www.piclist.com/techref/method/math/crcguide.html. But my maths isn't
good enough for the posed method; would anyone care to comment?
--
Regards
Alex McDonald
Petrus Prawirodidjojo
----- Original Message -----
From: "Alex McDonald" <alex...@btopenworld.com>
Newsgroups: comp.lang.forth
To: <comp.la...@ada-france.org>
Sent: Wednesday, November 12, 2003 05:33
Subject: Help with 32 bit CRC (maths ahead...)
> Too hard for me; any mathematicians here?
>
> I've been in discussion about a modified form of a standard 32 bit CRC.
The
> technique commonly used (as in Ethernet) is:
>
> CRC32( MESSAGE | 0 | CRC32( MESSAGE ) ) = CRC32( MESSAGE )
Assume the message is "An Arbitrary String"
CRC32(MESSAGE): 6FBEAAE7
CRC32(MESSAGE | 0 | CRC32(MESSAGE)): 4824B315
> that is, the CRC of the message augmented by 32 bits of zero and the 32
bit
> CRC itself is equal to the original CRC of the message.
>
> My correspondent has suggested that
>
> CRC32( MESSAGE | XCRC32( MESSAGE ) ) = 0
CRC32(MESSAGE | XCRC32(MESSAGE)): 2144DF1C
> that is, the CRC of the message, augmented with some "inverse" CRC that
> results in a CRC of zero, is as strong as the traditional method. I
disagree
> on two counts;
And
CRC32(MESSAGE | CRC32(MESSAGE)): FFFFFFFF
XCRC32(MESSAGE | CRC32(MESSAGE)): 00000000
Regards,
Petrus-Pet4th.
Alex McDonald
> ----- Original Message -----
> From: "Alex McDonald" <alex...@btopenworld.com>
> Newsgroups: comp.lang.forth
> To: <comp.la...@ada-france.org>
> Sent: Wednesday, November 12, 2003 05:33
> Subject: Help with 32 bit CRC (maths ahead...)
>
>
> > Too hard for me; any mathematicians here?
> >
> > I've been in discussion about a modified form of a standard 32 bit CRC.
> The
> > technique commonly used (as in Ethernet) is:
> >
> > CRC32( MESSAGE | 0 | CRC32( MESSAGE ) ) = CRC32( MESSAGE )
>
> Assume the message is "An Arbitrary String"
> CRC32(MESSAGE): 6FBEAAE7
> CRC32(MESSAGE | 0 | CRC32(MESSAGE)): 4824B315
Sorry, I may have mislead both you and me here. The previous should
read;
CRC32( MESSAGE | 0 | CRC32( MESSAGE ) ) = 0
that is, checksum the entire thing and the result should be zero. I
don't understand your result CRC32(MESSAGE | 0 | CRC32(MESSAGE)):
4824B315 based on this. Your string is 19 bytes; has the CRC been done
over 20? (5 32bit words).
Apologies for the confusion.
--
Regards
Alex McDonald
Petrus Prawirodidjojo
----- Original Message -----
From: "Alex McDonald" <alex...@btopenworld.com>
Newsgroups: comp.lang.forth
To: <comp.la...@ada-france.org>
Sent: Thursday, November 13, 2003 01:43
Subject: Re: Help with 32 bit CRC (maths ahead...)
> CRC32( MESSAGE | 0 | CRC32( MESSAGE ) ) = 0
>
> that is, checksum the entire thing and the result should be zero. I
> don't understand your result CRC32(MESSAGE | 0 | CRC32(MESSAGE)):
> 4824B315 based on this. Your string is 19 bytes; has the CRC been done
> over 20? (5 32bit words).
I use "commonly used" CRC-32 with polynomial: 1-04C1-1DB7 with proper shift
direction and initial value FFFFFFFF, and based on CRC32(MESSAGE |
CRC32(MESSAGE)): FFFFFFFF
CRC-32 is fed with initial 32 bit value but the smallest unit of message
should be 1 bit, not 32 bits. But for our purpose usually the smallest unit
is 1 byte (we are using standard computers, not some communication devices).
CRC has nothing to do with message length, any message length will do.
If you are talking about standard CRC-32 (commonly used CRC-32), you may
find Forth program on Will Baden (Neil Bawd) web site. You may also find
assembly language source for at least Win32Forth on my web site. If you are
talking about special CRC-32, then I have no idea at all.
Regards,
Petrus-Pet4th.
Ed
"Alex McDonald" <alex...@btopenworld.com> wrote in message
news:boro4h$1uv$1...@titan.btinternet.com...
Are you referring to the technique used in the Xmodem
receiving protocol?
In Xmodem-CRC, the initial crc is set to zero. The transmit
end calculates the CRC while sending the block of data.
After all the data is sent, a zero is then pushed through the
CRC routine and the resulting CRC transmitted. At the
receiving end, the crc is init to zero and the transmitted
data and CRC is then received. The result should be a
CRC value of zero.
Note that the TX and RX ends use the same CRC algorithm.
I imagine the CRC32 variant would do something similar.
Probably, the initial CRC values would be different.
(Normally, CCITT-CRC32 starts with an initial CRC
value of -1 (all bits set) and inverts the result.)
If you need the math for the basic CRC routines, you
may want to have a look at:
ftp://ftp.taygeta.com/pub/Forth/Applications/ANS/crc16b.zip
Ed