Re: [boost] Re: CRC Computation Problem (was: Re: Review Request: CRC)

From: Joel Young (jdy_at_[hidden])
Date: 2001-02-27 12:16:04

Thanks,

If you look at most standard CRC polynomials you will notice that
$x+1$ is a factor.  $x+1$ gives sensitivity to odd-count bit errors so
it is almost invariably a factor in real CRCs.

So I guess there are two ways of applying CRCs.  One is to compute a
checksum which is transmitted with the data.  Upon receipt a new
checksum is computed based on the data and then compared to the
checksum.  The second way (which I am more comfortable with) is to place
the "checksum" as the last bytes.  Then:

1.  Set the checksum to zero (all bits zero)

2.  Compute the CRC remainder for the entire block

3.  Set the checksum to this value.

Transmit then:

1.  Compute the CRC remainder for the entire block

2.  If it is non-zero you know there was a transmission error.

Leon-Garcia, Widjaja: Communication Networks has an approachable
discussion.

Joel
--------
From: Daryle Walker <darylew_at_[hidden]>
Date: Tue, 27 Feb 2001 11:57:10 -0500
  To: <boost_at_[hidden]>
Subj: [boost] Re: CRC Computation Problem (was: Re: Review Request: CRC)

on 2/23/01 5:29 PM, Joel Young at jdy_at_[hidden] wrote:

> x^6+x^5+x^3+x^2 / x+1   should give a remainder of zero unless I screwed
> up.
> 
> So the codeword for transmission to get zero remainder should then be
> the original message.

You did get a zero remainder.  Ignore my earlier claim that it wasn't the
lowest bit; your initial understanding was right.  The problem was I screwed
up making my masking constant.  I didn't catch it before because I always
used a bit size divisible by the number of bits per byte (8).  The new
version (3) of the CRC classes fixes this.

Is your given divisor (x + 1) something you made up, or is it part of an
official CRC?  Maybe I should use it as a test case, but we would have to
confirm what the its CRC-value for "123456789" (my baseline data) is.

(To be more specific about my masking error: I initially created it by right
shifting the all-ones bit pattern.  I thought that the compiler would make
the new bits [in the highest] positions zero for unsigned types.  But it
kept the new bits high, just like for signed types.  So I ended up with an
unchanged mask.  This let the 1 you saw in the 16-place leak through.  I
fixed the problem by left shifting an all-ones bit pattern, getting zeros in
the new [lowest position] bits, then complementing that result.)

> From: Daryle Walker <darylew_at_[hidden]>
> Date: Fri, 23 Feb 2001 15:09:12 -0500
> To: <boost_at_[hidden]>
> Subj: [boost] CRC Computation Problem (was: Re: Review Request: CRC)
> 
>> on 2/22/01 11:20 AM, Joel Young at jdy_at_[hidden] wrote:
>> 
>>> Question on the usage of the crc:
>>> 
>>> I run the following code:
>>> 
>>> {
>>>     boost::crc_slow<1> crc_1(1,0,0,false,false);
>>> 
>>>     std::bitset<7> t = 108; //("1101100");
>>>     std::cerr << t << std::endl;
>>>     for (int i=t.size()-1; i>=0; --i)
>>>         crc_1( t.test(i) );
>>>     std::bitset<7> s = *crc_1; //("1101100");
>>>     t |= *crc_1;
>>>     std::cerr << t << std::endl;
>>>     std::cerr << s << std::endl;
>>> }
>>> 
>>> And get this result:
>>> 
>>> 1101100
>>> 1111100
>>> 0010000
>>> 
>>> Indicating that the remainder returned by crc_1 is way to big.
>>> 
>>> Shouldn't the remainder be only one bit?  Or am I misunderstanding the
>>> process?
>> 
>> It is one bit, but it's not the lowest bit.  Since you specified only an
>> one-bit CRC, the answer should be one or zero.  I'll take a look.  By the
>> way, what is the CRC supposed to be?

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/