Boost logo

Boost :

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/ 

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk