Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Error detection and correction: parity, checksum and CRC

Notes on parity, checksums (1's-complement) and CRC: definitions, how they work, exact polynomial division method for CRC, formulas, worked examples, common mistakes and exam pointers.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Error detection and correction are used whenever digital data is sent or stored and must be trusted — for example in Ethernet frames, IP/UDP/TCP packets, disk storage, and wireless links. Simple methods (parity), medium-strength (checksums) and very strong, hardware-friendly methods (CRC) are applied depending on cost, latency and the expected error patterns.

Key ideas

  • Parity bit (single-bit parity): append one extra bit so that the total number of 1 bits in the block is either even (even parity) or odd (odd parity). This is the simplest error-detecting method. It guarantees detection of any odd number of bit flips in the block, but cannot detect an even number of flips (e.g., two flipped bits may cancel).

    • Draw for exam: a horizontal rectangle labelled DATA bits b_{n-1} ... b_1 b_0, a small box to the right labelled PARITY. Above the parity box write either EVEN or ODD. Below the rectangle draw an arrow to RECEIVER showing parity check: compute parity and compare.
  • Two-dimensional (matrix) parity: place data in a matrix, compute parity for each row and for each column, and send these parity bits. This can detect and locate (and correct) any single-bit error (by intersecting the row and column with parity mismatch) and detect many multiple-bit errors but not all.

  • Checksum (additive): split data into fixed-size words (commonly 16-bit for IP/TCP/UDP), compute the arithmetic sum using either ordinary modular arithmetic or 1's-complement arithmetic, and send the complement (so that receiver's sum including checksum gives a fixed pattern, e.g., all 1s). The Internet checksum (IP, UDP, TCP) uses 1's-complement 16-bit addition with end-around carry and then the 1's complement of the sum as the checksum. It detects many errors but not all: it is weak against certain re-orderings and multiple compensating errors.

    • Define 1's-complement addition: add words; if an overflow (carry out of MSB) occurs, add that carry back into the LSB (end-around carry); final checksum = complement (bitwise NOT) of that sum.
  • Cyclic Redundancy Check (CRC): treat the bit sequence as coefficients of a polynomial D(x) over GF(2). Choose a generator polynomial G(x) of degree r. To form the transmitted codeword, multiply D(x) by x^r (append r zeros), divide x^r·D(x) by G(x) in modulo-2 (binary XOR) polynomial division, take the remainder R(x) (degree < r) and transmit T(x) = x^r·D(x) + R(x). Receiver divides received polynomial by G(x); if remainder ≠ 0, an error is detected.

    • Draw for exam: show polynomial long division in binary: top line dividend x^r·D(x), divisor G(x); show remainder R(x) of degree < r appended to original data bits.

    • Exact statements (standard properties, assumptions: arithmetic over GF(2)):

      • If G(x) has at least two nonzero terms (i.e., not equal to x^m), the CRC detects any single-bit error (error polynomial E(x)=x^k) because G(x) cannot divide x^k.
      • It detects all double-bit errors if G(x) does not divide x^k + 1 for any k in 1 ≤ k ≤ n−1, where n is the frame length; in practice, generators with at least three nonzero terms are chosen to satisfy this for useful n.
      • If G(x) has factor (x + 1), the CRC detects any error pattern with an odd number of bit flips (because polynomials with odd Hamming weight evaluate to 1 at x = 1 and so are not divisible by x + 1).
      • A CRC with generator of degree r detects all burst errors of length ≤ r (a burst error is an error polynomial whose first and last coefficients are 1). Proof: any such burst is a polynomial of degree ≤ r and nonzero, so cannot give remainder zero when divided by degree-r generator unless the burst polynomial is a multiple of G(x), but degree less than r prevents that.
      • For burst errors longer than r, the CRC will fail to detect some bursts; for random independent errors, the probability that a random error polynomial is divisible by a given degree-r generator is 2^{-r} (so chance of detection ≈ 1 - 2^{-r}).
    • Show polynomial method step-by-step in answer: (1) choose G(x); (2) append r zeros; (3) perform modulo-2 long division (XOR instead of subtraction); (4) remainder R(x) appended to data.

Formulas

r = degree(G) — r is the number of CRC bits; unit: bits; applies to CRC with generator G(x).

T(x) = x^r · D(x) + R(x) — T(x): transmitted polynomial, D(x): data polynomial, R(x): remainder polynomial (degree < r); unit: none (polynomials over GF(2)).

Received is accepted iff (Received polynomial) mod G(x) = 0 — condition test at receiver; arithmetic over GF(2).

Checksum = NOT( Sum_{i} word_i (1's-complement addition) ) — word_i are fixed-size words (e.g., 16-bit); result is the checksum word; unit: bits.

P_detect(burst ≤ r) = 1 — CRC with degree r detects all burst errors of length ≤ r.

P_undetected(random error) = 2^{-r} — for random error polynomials equally likely, probability a random polynomial is divisible by a degree-r generator is 2^{-r} (approximate model).

Worked examples

Example 1 — Single parity (even parity) Data: 7 bits 1011001. Compute parity bit (even parity). Step 1: count 1s in data: 1+0+1+1+0+0+1 = 4 (even). Step 2: For even parity parity bit = 0 (because data already has even number of 1s). Transmitted bits = 1011001 0. If a single bit flips anywhere, receiver recomputes parity and finds odd count → detects error. If two bits flip, parity may remain even and error is undetected. Final answer: 10110010.

Example 2 — Internet-style 1's-complement checksum (8-bit words example for exam clarity) Words (8-bit): W1 = 11011010 (218), W2 = 01100101 (101). Step 1: Add: 218 + 101 = 319 decimal = binary 1 00111111 (9-bit: carry 1 + 8-bit payload). Since we use 8-bit words, do end-around carry: low 8 bits = 319 - 256 = 63; add the carry 1 -> 64. Step 2: Sum (after end-around carry) = 01000000 (64). Step 3: Checksum = bitwise NOT of sum = 10111111 (191). Transmitted: W1, W2, CHECKSUM = 11011010 01100101 10111111. Receiver sums W1+W2+CHECKSUM with end-around carry; final result should be all ones (11111111). If not, error. (Reviewer: verify arithmetic and example word sizes if your exam uses 16-bit words — replace 8-bit with 16-bit and same algorithm.)

Example 3 — CRC (polynomial method) — small illustrative trace Choose data D = 1101 (bits), generator G = 1011 (which corresponds to polynomial x^3 + x + 1); so r = 3. Step 1: append r zeros: 1101 000. Step 2: divide 1101000 by 1011 using modulo-2 long division (use XOR when subtracting). Show the division steps in long-division form on the paper: write 1011 as divisor and 1101000 as dividend, perform XOR where the current leftmost bit is 1, bring down bits until the dividend is finished. The remainder is R = 001 (3 bits), which is appended to D for transmission. Step 3: Transmit T = 1101 001. Step 4: Receiver divides received bits by 1011; if remainder ≠ 0 then error.

Checked: for this example the remainder is R = 001.

Common mistakes

  • For CRC: forgetting that arithmetic is over GF(2) (subtraction = XOR), or appending the remainder incorrectly (sometimes students append the one's complement of remainder — this is wrong unless specified by a protocol).
  • Misstating the CRC properties: claiming CRC detects all errors — must state the precise limits (all single-bit errors, all bursts ≤ r, odd-number errors only when G(x) divisible by x+1).
  • In long division, dropping leading zeros incorrectly; require consistent procedure: at each step, align the divisor under the dividend's current MSB that is 1 (leftmost 1) and XOR, then bring the next bit down.

For your exam

Question types you will see: short definitions (parity, checksum, CRC), short notes (advantages/disadvantages), derivations (show why CRC detects bursts ≤ r), numerical problems (compute parity, compute 1's-complement checksum for given words), and algorithm traces (show modulo-2 division for CRC on small data). A full-marks answer for CRC division includes: stating generator polynomial degree r, showing x^r·D(x) (i.e., show appended zeros), performing each XOR step in long-division until remainder of degree < r, writing remainder bits and final transmitted codeword, and stating the receiver check.

Quick check

  1. What error patterns does a single parity bit always detect?
  2. In the Internet checksum, how is an overflow carry handled when adding words?
  3. A CRC generator of degree r always detects all burst errors of what maximum length?
    Answers: 1) Any odd number of bit flips. 2) End-around carry: add the carry back into the least significant bit position (1's-complement addition). 3) All burst errors of length ≤ r.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?