Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
A cyclic redundancy check appends the remainder of binary polynomial division to a message so that the codeword is divisible by the generator polynomial.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
Bit strings and polynomial coefficients over GF(2); r is the generator degree and number of check bits
| Symbol | Meaning | Unit |
|---|---|---|
| Message polynomial over GF(2) | bit polynomial | |
| Generator polynomial of degree r with constant term 1 | bit polynomial | |
| Generator degree and number of appended check bits | bit count | |
| Remainder of xʳM(x) divided by G(x) | bit polynomial | |
| Transmitted codeword | bit string |
R(x)=(x^rM(x))\bmod G(x),\quad C(x)=x^rM(x)+R(x)The teaching definition works over GF(2): addition and subtraction are XOR, with no carries. For message polynomial M and degree-r generator G, divide xʳM by G and append remainder R. Then C=xʳM+R is divisible by G because GF(2) addition cancels the remainder. This is the basic idea, not a complete CRC profile: implementations also specify polynomial notation, initial value, reflection, bit/byte order and final XOR. Detection depends on the generator and error pattern; CRC is not cryptographic integrity protection.
The teaching definition works over GF(2): addition and subtraction are XOR, with no carries. For message polynomial M and degree-r generator G, divide xʳM by G and append remainder R. Then C=xʳM+R is divisible by G because GF(2) addition cancels the remainder. This is the basic idea, not a complete CRC profile: implementations also specify polynomial notation, initial value, reflection, bit/byte order and final XOR. Detection depends on the generator and error pattern; CRC is not cryptographic integrity protection.
A cyclic redundancy check appends the remainder of binary polynomial division to a message so that the codeword is divisible by the generator polynomial.
Codeword condition
Addition and subtraction in GF(2) both use XOR; there are no carries.
Use the example for CRC checksum as a polynomial remainder over GF(2) to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
A cyclic redundancy check appends the remainder of binary polynomial division to a message so that the codeword is divisible by the generator polynomial.
The relation applies only under its stated assumptions.
For M=1101 and G=1011 (degree 3), find the remainder and codeword using the basic CRC rule over GF(2).
Append three zero bits: 1101000.
XOR polynomial division by 1011 gives remainder 001.
The codeword is 1101001; dividing it by 1011 gives remainder 000.
This is a teaching example, not a complete standard profile.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: The teaching definition works over GF(2): addition and subtraction are XOR, with no carries. For message polynomial M and degree-r generator G, divide xʳM by G and append remainder R..
Formula cluster
A cyclic redundancy check appends the remainder of binary polynomial division to a message so that the codeword is divisible by the generator polynomial.
Teaching calculation: M=11012 and G=10112=x3+x+1, so r=3. Dividing 1101000 by 1011 gives remainder 001. The codeword is 1101001. Check: XOR polynomial division of 1101001 by 1011 has remainder 000. These values illustrate the basic operation and do not identify a standardized CRC format.
Understand error detection in transmitted or stored bit strings and identify parameters of a concrete CRC profile.
Here is how to work through a typical CRC checksum as a polynomial remainder over GF(2) (CRC = Rest der Polynomdivision über GF(2)) task step by step:
Task
Use the example for CRC checksum as a polynomial remainder over GF(2) to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
A cyclic redundancy check appends the remainder of binary polynomial division to a message so that the codeword is divisible by the generator polynomial.
The relation applies only under its stated assumptions.
Task
For M=1101 and G=1011 (degree 3), find the remainder and codeword using the basic CRC rule over GF(2).
Solution path
Append three zero bits: 1101000.
XOR polynomial division by 1011 gives remainder 001.
The codeword is 1101001; dividing it by 1011 gives remainder 000.
This is a teaching example, not a complete standard profile.
A CRC polynomial has coefficients in GF(2), only 0 and 1. Addition and subtraction are identical: 0⊕0=0, 1⊕0=1 and 1⊕1=0. Long polynomial division therefore uses XOR steps, without carries or ordinary integer arithmetic. The bit string encodes coefficients in descending power order. The hand calculation explains the GF(2) idea, not every parameter of an interoperable CRC standard. A concrete profile must specify its generator polynomial, initial value, reflection, bit order and final XOR. CRC detects certain transmission errors but provides no cryptographic authentication.
The generator G has degree r, so the remainder has at most r bits. First multiply the message by xʳ, represented by appending r zero bits. Division then determines check bits that make the codeword remainder zero. The remainder replaces those zeros; it is not appended after an already completed remainder field. The hand calculation explains the GF(2) idea, not every parameter of an interoperable CRC standard. A concrete profile must specify its generator polynomial, initial value, reflection, bit order and final XOR. CRC detects certain transmission errors but provides no cryptographic authentication.
With M=1101 and degree-three G=1011, first form 1101000. Polynomial division repeatedly removes the leading term by XORing a shifted 1011; the remainder is 001. The appended codeword is 1101001. Dividing it by 1011 gives remainder 000. This is a teaching convention and should not be mistaken for a complete CRC-32 profile. The hand calculation explains the GF(2) idea, not every parameter of an interoperable CRC standard. A concrete profile must specify its generator polynomial, initial value, reflection, bit order and final XOR. CRC detects certain transmission errors but provides no cryptographic authentication.
The generator polynomial determines which error patterns are guaranteed to be detected and the checksum’s properties. Two implementations can use the same width but different polynomials and produce incompatible results. Initialization, reflection and final XOR also change the output value. Communication requires both ends to use the same named profile and bit order. The hand calculation explains the GF(2) idea, not every parameter of an interoperable CRC standard. A concrete profile must specify its generator polynomial, initial value, reflection, bit order and final XOR. CRC detects certain transmission errors but provides no cryptographic authentication.
No. CRC is designed to detect accidental transmission or storage errors. An actor who can modify a message can generally calculate a matching remainder and replace the checksum. Authenticity and protection against deliberate tampering require cryptographic mechanisms such as a message authentication code or digital signature. A CRC check cannot replace security validation. The hand calculation explains the GF(2) idea, not every parameter of an interoperable CRC standard. A concrete profile must specify its generator polynomial, initial value, reflection, bit order and final XOR. CRC detects certain transmission errors but provides no cryptographic authentication.
Quanta exam set
Curated exam set for "CRC checksum as a polynomial remainder over GF(2)":
Question (front)
Which formula describes CRC checksum as a polynomial remainder over GF(2)?
Answer in your set
Question (front)
How do you rearrange CRC checksum as a polynomial remainder over GF(2) for Codeword condition?
Answer in your set
Question (front)
Which common mistake happens with CRC checksum as a polynomial remainder over GF(2)?
Answer in your set
+ 8 more cards: units, variables, derivation, example, exam task
The formula set contains 11 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for CRC = Rest der Polynomdivision über GF(2): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential