Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

CRC sumcheck

  1. Sep 10, 2011 #1
    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...?
     
  2. jcsd
  3. Sep 10, 2011 #2

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Sep 10, 2011
  4. Sep 10, 2011 #3
    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)
     
  5. Sep 10, 2011 #4

    rcgldr

    User Avatar
    Homework Helper

    I updated my previous post to use your terminology with 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 1014 for most computer peripherals). Usually some form of Reed-Solomon ecc code is used versus crc.
     
    Last edited: Sep 10, 2011
  6. Sep 11, 2011 #5
    thanks a lot...it makes sense to have it that way :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook