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).
| Data | Count of 1s | Even-parity bit | Sent |
|---|---|---|---|
| 1011001 | 4 | 0 | 10110010 |
| 1110000 | 3 | 1 | 11100001 |
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.
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:
- Splits the data into 16-bit words.
- Adds them using one's complement addition — any carry out of the top bit is added back at the bottom ("wrap around").
- 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):
- Append n zeros to the data.
- 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.
- 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.
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:
| To | You need d of at least |
|---|---|
| detect up to s errors | s + 1 |
| correct up to t errors | 2t + 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?
| Situation | Usual choice | Why |
|---|---|---|
| Wired LAN, fibre | detect (CRC) + resend | errors are rare; resends are cheap |
| Wi-Fi, mobile data | strong correction and detection | errors are common |
| Deep-space links, satellite | heavy forward error correction | a resend would take minutes |
| RAM in servers (ECC memory) | Hamming-style correction | no 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.