For a CRC whose generator polynomial has degree r, which corruption patterns on a frame are guaranteed to be detected?

## The only way corruption hides The transmitted frame is an exact multiple of the generator `G(x)`. What arrives is that codeword plus an **error pattern** `E(x)`, a polynomial with a 1 in every position that flipped and 0 everywhere else. When the receiver divides, the codeword contributes nothing, so: > The corruption goes undetected **if and only if** `G(x)` divides `E(x)`. Everything below is a consequence of that one line. Note what it does *not* depend on: the content of the frame, its length, or how many good frames came before. A CRC's guarantees are properties of error patterns alone. ## Single-bit errors One flipped bit at position `i` gives `E(x) = x^i`. The only divisors of `x^i` are powers of `x`, so as long as the generator has more than one non-zero term — every practical generator has both its top term and a constant term — it cannot divide `x^i`. **Every single-bit error is detected, at any position, for any frame length.** ## Bursts, and what the generator's degree buys A **burst of length L** means the flipped bits are confined to a window of `L` consecutive positions, with the first and last positions inside that window both flipped; the bits in between may flip or not. Such a pattern factors as `E(x) = x^j · B(x)` where `B(x)` has degree `L - 1` and a non-zero constant term. - `G(x)` cannot divide the `x^j` part, because it has a non-zero constant term of its own. - So the generator would have to divide `B(x)` — impossible when `deg B = L - 1 < r`, unless `B` is zero. - Therefore **every burst of length at most `r` is detected**, wherever it starts and however many bits inside the window flipped. That is the headline number: a degree-32 generator catches every burst up to 32 bits long, a degree-16 generator every burst up to 16. It matters because physical corruption on a wire is usually bursty — one disturbance smears across adjacent bit times rather than picking isolated bits at random. Beyond the guaranteed window the picture becomes probabilistic: a burst of exactly `r + 1` bits escapes with probability about `2^-(r-1)`, and longer bursts with probability about `2^-r`. ## Odd weight and the (x + 1) factor The **weight** of an error pattern is how many bits it flips. If `(x + 1)` is a factor of the generator, every odd-weight pattern is detected. The reason is a one-line evaluation: a polynomial with an odd number of terms evaluates to 1 at `x = 1`, while any multiple of `(x + 1)` evaluates to 0 there, so no odd-weight pattern can be a multiple. This effectively folds a parity bit into the generator. It is a deliberate design choice with a cost: reserving the factor constrains what the rest of the polynomial can deliver, so a generator chosen for odd-weight coverage and one chosen for the best two-bit separation at a given frame length are not always the same polynomial. ## Two-bit errors and the frame-length ceiling Two isolated flips give `E(x) = x^i · (x^k + 1)` for some separation `k`. Such a pattern is detected unless the generator divides `x^k + 1`. Well-chosen generators do not divide `x^k + 1` for any `k` below a large bound, so two-bit errors are detected up to a maximum data length — and **above that length the guarantee lapses**. This is why published generators come with a characterised range rather than a single claim: the protection depends on how long the frames are. ## Summary of the guarantees | Error pattern | Guaranteed? | Condition | | --- | --- | --- | | One flipped bit | Yes | Generator has at least two non-zero terms | | Burst of length at most r | Yes | None — position and inner weight irrelevant | | Odd number of flipped bits | Yes | `(x + 1)` divides the generator | | Two isolated flips | Within a stated length | Generator does not divide `x^k + 1` for that separation | | Burst longer than r | No | Escapes with probability about `2^-r` | | Arbitrary heavy corruption | No | Escapes with probability about `2^-r` | ## Reading the guarantees honestly - The guarantees are about *detection only*. The receiver learns that something is wrong, discards the frame and relies on a retransmission; it does not locate or repair the flipped bits. - "Detected" covers only the bits inside the region the check field is defined to cover. Anything outside it is invisible to the check. - A residue of zero on a corrupt frame is possible, just improbable for random noise; the guarantees above say exactly which patterns can never do it.