In a CRC (Cyclic Redundancy Check), the sender and receiver agree on a divisor $g$. The sender then appends bits to the message such that the message becomes divisible by $g$. The receiver checks for divisibility by $g$ to detect errors. CRCs can be extended to allow for error correction as well but here, we only consider error detection. In contrast to the previous algorithms, CRC can guarantee detection of more than two bit flips, regardless of their position in the message. In the following, we first discuss the algorithm in general without detailing the method for division. Afterwards, we explain the polynomial division algorithm.

Untitled

Polynomial Long Division example