Calculating Checksum: Frame Length vs Generator Polynomial

[prashantgolu]

To compute the checksum for some frame with m bits, corresponding to the polynomial M(x), the frame must be longer than the generator polynomial.
Why...?

 

[rcgldr]

The encoded frame will be longer. If G(x) is a r+1 bit polynomial, then a polynomial modulo G(x) produces an r bit remainder. An encoded frame will consist of d + r bits, where d is the number of data bits to be encoded. The encode process appends r zeroes to the data to create a polynomial, then divides this poynomial by G(x) to produce a r bit remainder. The encoded frame then consists of d bits of data followed by the r bit remainder. Note that the number of data bits, d, can be just 1 bit.

 

[prashantgolu]

I get it...but it says that M(x) should be longer than G(x)
i.e without encoding the data bits should be more than the generator polynomial...
(i think they are talking about the initial data bits and not after adding the check bits which it will obviously be longer than the generator polynomial as we are adding r bits to it in any case)

 

[rcgldr]

I updated my previous post to use your terminology with G(x).

I get it...but it says that M(x) should be longer than G(x)

There's no rule that the number of data bits needs to be greater than the number of redundancy bits. You might want to check and make sure that M(x) doesn't mean an encoded message as opposed to the data portion of an encoded message.

It might waste space or bandwidth, but in some cases, such as communications from distant sattelites, where the time it takes for the message to travel between the Earth and the satellite makes it impractical to use a scheme that relies on status responses and re-transmission of data, there are more reduncancy bits than data bits for each message, perhaps 2 or 3 times as many reduncancy bits than data bits (a corrective code is used instead of crc).

For magnetic media, if the goal is to maximize effective user data density, there is a trade off between increasing bit density and increasing the redundancy required to support the increased bit density while maintaining some unrecoverable read error rate (usually 1 in 10¹⁴ for most computer peripherals). Usually some form of Reed-Solomon ecc code is used versus crc.

 

[prashantgolu]

thanks a lot...it makes sense to have it that way :)