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/