allanh@netcom.UUCP (Allan N. Hessenflow) (03/07/90)
I've been using a crc routine from a document by Stephen Satchell which is supposed to be the same one used in xmodem. I seem to remember reading about the properties of this crc a long time ago that it would catch all single bit errors and all double bit errors for messages < n bytes long, where n is significantly larger than 6. However, I've recently discovered that this is not the case. Specifically, $41 76 03 01 00 09 has a crc of 37fb, while $41 76 03 01 00 08 has a crc of 37fa. Is this normal for the CCITT CRC, or is the function I'm using faulty? I'm fairly certain it's not a coding/translation error, as I've tried two different functions from the same document with the same results. -- apple!netcom!allanh allanh@netcom.uucp
kaufman@Neon.Stanford.EDU (Marc T. Kaufman) (03/07/90)
In article <8548@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes:
-I've been using a crc routine from a document by Stephen Satchell which
-is supposed to be the same one used in xmodem. I seem to remember reading
-about the properties of this crc a long time ago that it would catch all
-single bit errors and all double bit errors for messages < n bytes long,
-where n is significantly larger than 6. However, I've recently discovered
-that this is not the case. Specifically,
-$41 76 03 01 00 09 has a crc of 37fb, while
-$41 76 03 01 00 08 has a crc of 37fa.
-Is this normal for the CCITT CRC, or is the function I'm using faulty? I'm
-fairly certain it's not a coding/translation error, as I've tried two
-different functions from the same document with the same results.
The last time I looked, 37fb and 37fa were different numbers, so the CRCs of
the two input strings were, in fact, different. What's the problem?
The way CRCs are meant to be used is: Initialize the CRC to all 1's, then
compute the CRC of the message. Send the message with the CRC appended to it.
On the receiving side, initialize the CRC to all 0's. Compute the CRC of the
entire message PLUS the message CRC. The result should be 0. If not, you
have an error. The CRC alone is not strong enough to enable you to correct
the error.
Marc Kaufman (kaufman@Neon.stanford.edu)cpcahil@virtech.uucp (Conor P. Cahill) (03/07/90)
In article <8548@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes: > >$41 76 03 01 00 09 has a crc of 37fb, while >$41 76 03 01 00 08 has a crc of 37fa. >Is this normal for the CCITT CRC, or is the function I'm using faulty? I'm >fairly certain it's not a coding/translation error, as I've tried two >different functions from the same document with the same results. Maybe I am being real thick this morning, but why do you expect the CRCs to be the same? I would hope that the CRCs are different when the data is different. -- Conor P. Cahill (703)430-9247 Virtual Technologies, Inc., uunet!virtech!cpcahil 46030 Manekin Plaza, Suite 160 Sterling, VA 22170
allanh@netcom.UUCP (Allan N. Hessenflow) (03/08/90)
In article <1990Mar7.065639.11927@Neon.Stanford.EDU>, kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: > In article <8548@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes: > > -$41 76 03 01 00 09 has a crc of 37fb, while > -$41 76 03 01 00 08 has a crc of 37fa. > > The last time I looked, 37fb and 37fa were different numbers, so the CRCs of > the two input strings were, in fact, different. What's the problem? > > > Marc Kaufman (kaufman@Neon.stanford.edu) the problem is that there are only two bits different between the two messages, including the crc. -- apple!netcom!allanh allanh@netcom.uucp
kaufman@Neon.Stanford.EDU (Marc T. Kaufman) (03/08/90)
In article <8603@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes: >In article <1990Mar7.065639.11927@Neon.Stanford.EDU>, kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: -> In article <8548@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes: -> -> -$41 76 03 01 00 09 has a crc of 37fb, while -> -$41 76 03 01 00 08 has a crc of 37fa. -> The last time I looked, 37fb and 37fa were different numbers, so the CRCs of -> the two input strings were, in fact, different. What's the problem? >the problem is that there are only two bits different between the two >messages, including the crc. I understand your concern. However, I must unfortunately report that the CRC is a checksum of the Message, only. Not the Message+CRC. If you need to be able to discover 2-bit errors in the message+CRC, you will need to compute a CRC on the original Message+CRC (or use a longer CRC, say 32 bit). It is also the case that the few bits very near the end of the message have less effect on the resultant CRC than earlier bits do. Maybe just padding the message with some '1' bits will work, though I haven't tried it. By the way: It is certainly true that some 4-bit errors will leave the CRC unchanged -- and the length of the bit substring in error can be as short as 17 bits for a 16 bit CRC. Marc Kaufman (kaufman@Neon.stanford.edu)
allanh@netcom.UUCP (Allan N. Hessenflow) (03/09/90)
In article <1990Mar8.051028.20207@Neon.Stanford.EDU>, kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: > In article <8603@netcom.UUCP> allanh@netcom.UUCP (Allan N. Hessenflow) writes: > > > > -$41 76 03 01 00 09 has a crc of 37fb, while > > -$41 76 03 01 00 08 has a crc of 37fa. > > >the problem is that there are only two bits different between the two > >messages, including the crc. > > I understand your concern. However, I must unfortunately report that > the CRC is a checksum of the Message, only. Not the Message+CRC. If you > need to be able to discover 2-bit errors in the message+CRC, you will need > to compute a CRC on the original Message+CRC (or use a longer CRC, say 32 bit). > > Marc Kaufman (kaufman@Neon.stanford.edu) Since my original posting, I've found another source for the CCITT CRC which isn't equivalent to the one I had been using from Stephen Satchell. The original document I had been working from contained five different routines, three of which worked according to Mr. Satchell. Those three are indeed equivalent to each other, but aren't equivalent to the CCITT CRC they claim to be (at least they aren't equivalent to the one published in the 'C Programmer's Guide to Serial Communication'). I've replaced my original routine with one from that book, and so far it appears to be less sensitive to two bit errors (although it's too early to be certain). I was rather hoping to hear that no two message+crc blocks will differ by only two bits. I don't understand why anyone would want to know how may bits in the message can be incorrect and still be caught if errors in the CRC itself aren't included. Surely in most applications the CRC is sent over the same noisy channel as the message. -- apple!netcom!allanh allanh@netcom.uucp
rob@cs.mu.oz.au (Robert Wallen) (03/10/90)
In article <1990Mar7.065639.11927@Neon.Stanford.EDU> kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: > >The way CRCs are meant to be used is: Initialize the CRC to all 1's, then >compute the CRC of the message. Send the message with the CRC appended to it. >On the receiving side, initialize the CRC to all 0's. Compute the CRC of the >entire message PLUS the message CRC. The result should be 0. If not, you Can someone confirm this? Or preferably deny it? I have never used a seed value of all 1's (except one weirdo case where it wasnt CCITT CRC's being used anyway) From my (limited) understanding of the underlying mathematics (polynomial division), it doesnt make a lot of sense to start with different values at the sender and the receiver ... Ohh, did anybody think to crosspost this to comp.os.minix? It would be interesting to see what ast@whereever.he.is had to say; as I recall, 'Computer Networks' was the first book that ever really explained these things good enough for me to just accept that 'yeh, they work'
jimo@phred.UUCP (Jim Osborn) (03/13/90)
rob@murtoa.UUCP (Robert Wallen) writes: -kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: --The way CRCs are meant to be used is: Initialize the CRC to all 1's, then --compute the CRC of the message. Send the message with the CRC appended to it. --On the receiving side, initialize the CRC to all 0's. Compute the CRC of the --entire message PLUS the message CRC. The result should be 0. If not, you - -Can someone confirm this? Or preferably deny it? I have never used a seed -value of all 1's (except one weirdo case where it wasnt CCITT CRC's being -used anyway) You must use the same initial value on both ends. Some people seem to like zero, but that leaves you vulnerable to computing a good CRC on an all-zero message. All-ones is a better choice, though I suppose you could use any non-zero value, as long as both ends agree to it. jimo -- pilchuck!jimo@phred Jim Osborn, Physio Control Corp 11811 Willows Rd, Redmond, WA, 98073 206-867-4704 direct to my desk