Skills101

AdvancedComputer Networks · Lesson 15 of 15 · Updated ·

Error Detection and Correction — Parity, Checksum, CRC and Hamming Code with Solved Examples

Electrical noise, a weak Wi-Fi signal or a scratched cable can flip a 0 into a 1. If nobody notices, a bank transfer of ₹500 could become ₹900. Every layer of the network therefore adds a few redundant bits — extra bits computed from the data — so the receiver can check whether what arrived is what was sent.

Two different goals:

  • Error detection — notice that something is wrong (then ask for a resend or drop the data).
  • Error correction — work out which bits are wrong and fix them, without a resend.

1. Single parity bit

Add one bit so that the total number of 1s is even (even parity) or odd (odd parity).

DataCount of 1sEven-parity bitSent
10110014010110010
11100003111100001

The receiver counts the 1s again. If one bit flipped, the count becomes odd — error detected.

The weakness: if two bits flip, the count is even again and the error is missed. Single parity detects every odd number of bit errors and no even number of them.

2. Two-dimensional parity

Arrange the data in a grid and add a parity bit for every row and every column.

Two 4 by 5 grids of bits with even parity on each row and column; in the received grid one bit has flipped, and the failing row 2 and failing column 3 cross exactly at the wrong bit, so it can be corrected

If one bit flips, exactly one row check and one column check fail. They cross at the bad bit — so the receiver can correct it by flipping it back. 2-D parity detects all 1-, 2- and 3-bit errors, but some 4-bit patterns (the corners of a rectangle) slip through.

3. The Internet checksum

IP, TCP and UDP headers carry a 16-bit checksum. The sender:

  1. Splits the data into 16-bit words.
  2. Adds them using one's complement addition — any carry out of the top bit is added back at the bottom ("wrap around").
  3. Inverts all bits of the sum. That is the checksum.

The receiver adds all the words including the checksum and inverts the result. If nothing changed, it gets 0.

def internet_checksum(words):
    total = 0
    for w in words:
        total += w
        total = (total & 0xFFFF) + (total >> 16)   # wrap the carry around
    return ~total & 0xFFFF                           # one's complement

header = [0x4500, 0x0073, 0x0000, 0x4000, 0x4011,
          0x0000, 0xC0A8, 0x0001, 0xC0A8, 0x00C7]   # checksum field set to 0
c = internet_checksum(header)
print(f"checksum = {c:04X}")

header[5] = c                                        # put it in the header
print(f"receiver's result = {internet_checksum(header):04X}")
checksum = B861
receiver's result = 0000

The checksum is quick to compute in software, which is why IP and TCP use it. But it is weak: for example, swapping two 16-bit words gives the same sum, so that error is not detected. The link layer therefore adds a much stronger check — CRC.

4. Cyclic Redundancy Check (CRC)

CRC treats the bits as a polynomial and divides by an agreed generator polynomial, using XOR instead of subtraction (modulo-2 arithmetic: no carries, no borrows).

Sender's steps (generator with n + 1 bits):

  1. Append n zeros to the data.
  2. Divide by the generator using XOR. At each step, if the leading bit is 1, XOR with the generator; if it is 0, just move on.
  3. The last n bits left are the remainder — the CRC. Replace the appended zeros with it and send.

Receiver: divide the whole received frame by the same generator. Remainder all zeros = accept; anything else = error.

Worked example. Data = 100100, generator = 1101 (x³ + x² + 1). The generator has 4 bits, so append 3 zeros: 100100000.

CRC long division of 100100000 by 1101 shown row by row: five XOR steps, each applied where the leading bit is 1, leave the remainder 001, so the frame sent is 100100001

Remainder = 001, so the sender transmits 100100001. The same division in Python, plus a check with one damaged bit:

def crc_remainder(bits, gen):
    n = len(gen) - 1
    work = list(bits + "0" * n)              # append n zeros
    for i in range(len(bits)):
        if work[i] == "1":                   # XOR only when the leading bit is 1
            for j in range(len(gen)):
                work[i + j] = "0" if work[i + j] == gen[j] else "1"
    return "".join(work[-n:])

def check(frame, gen):
    n = len(gen) - 1
    return crc_remainder(frame[:-n], gen) == frame[-n:]

data, gen = "100100", "1101"
rem = crc_remainder(data, gen)
frame = data + rem
print("remainder:", rem)
print("sent frame:", frame)
print("received OK?", check(frame, gen))
damaged = frame[:2] + ("1" if frame[2] == "0" else "0") + frame[3:]
print("one bit flipped:", damaged, "OK?", check(damaged, gen))
remainder: 001
sent frame: 100100001
received OK? True
one bit flipped: 101100001 OK? False

Writing the generator as a polynomial. Each bit is a coefficient, highest power first: 1101 = 1·x³ + 1·x² + 0·x + 1 = x³ + x² + 1. Exam questions often give the polynomial; convert it back to bits before dividing. A degree-n generator gives an n-bit CRC.

What CRC catches. With a well-chosen generator, a CRC with n check bits detects all single-bit errors, all odd numbers of errors (when x + 1 is a factor of the generator), and all burst errors of length n or less. Ethernet uses a 32-bit CRC called the FCS (frame check sequence) at the end of every frame.

5. Hamming distance

The Hamming distance between two codewords is the number of bit positions in which they differ. 10110 and 11100 differ in positions 2 and 4, so the distance is 2.

The minimum distance d of a code (the smallest distance between any two valid codewords) tells you its power:

ToYou need d of at least
detect up to s errorss + 1
correct up to t errors2t + 1

Single parity has d = 2: it detects 1 error and corrects none. To correct 1 error you need d = 3.

6. Hamming code: correcting a single bit

Hamming codes place parity bits at positions that are powers of 2 (1, 2, 4, 8…). Each parity bit checks the positions whose binary number contains that power. With r parity bits and m data bits, the parity bits must be able to name every position plus "no error":

2ʳ ≥ m + r + 1

def parity_bits_needed(m):
    r = 0
    while 2 ** r < m + r + 1:
        r += 1
    return r

for m in (4, 7, 8, 16, 32):
    r = parity_bits_needed(m)
    print(f"{m:2} data bits -> {r} parity bits, codeword {m + r}")
 4 data bits -> 3 parity bits, codeword 7
 7 data bits -> 4 parity bits, codeword 11
 8 data bits -> 4 parity bits, codeword 12
16 data bits -> 5 parity bits, codeword 21
32 data bits -> 6 parity bits, codeword 38

So 4 data bits need 3 parity bits — the famous Hamming(7, 4) code. When a single bit flips, the failing parity checks, read as a binary number, give the position of the bad bit. For example, if checks 1 and 4 fail and check 2 passes, the bad bit is at position 1 + 4 = 5.

7. Detect and resend, or correct?

SituationUsual choiceWhy
Wired LAN, fibredetect (CRC) + resenderrors are rare; resends are cheap
Wi-Fi, mobile datastrong correction and detectionerrors are common
Deep-space links, satelliteheavy forward error correctiona resend would take minutes
RAM in servers (ECC memory)Hamming-style correctionno one to "resend" a memory read

Correction that happens at the receiver without any resend is called forward error correction (FEC).

Common mistakes

  • Using normal subtraction with borrows in CRC — it is XOR only.
  • Appending as many zeros as the generator has bits — append one fewer (the degree).
  • Saying a parity bit detects any error — it misses every even number of flipped bits.
  • Mixing up the rules: detect s errors needs d ≥ s + 1; correct t errors needs d ≥ 2t + 1.
  • Thinking the TCP checksum makes CRC unnecessary — the link layer's CRC is much stronger.

Quick recap

  • Parity: detects odd numbers of bit errors; 2-D parity can also correct one bit.
  • Internet checksum: one's complement sum of 16-bit words, inverted; the receiver gets 0 if fine.
  • CRC: append n zeros, XOR-divide by the (n + 1)-bit generator, send the n-bit remainder; receiver expects remainder 0. Catches all bursts up to n bits.
  • Hamming distance d: detect d − 1 errors, correct (d − 1) / 2 errors (rounded down).
  • Hamming code: parity bits at powers of 2; 2ʳ ≥ m + r + 1.

Practice what you learned

📝 Quiz: Error Detection and Correction5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →