Error Detection: Parity, Checksum & CRC

By the end of this lesson you will be able to add a parity bit, calculate an Internet checksum, do CRC division by hand and check it with Python, and explain why each method catches some errors and misses others.

Signals get damaged. A microwave oven near a Wi-Fi router, a loose connector or electrical noise near a lift motor can flip a 0 into a 1. The receiver cannot avoid errors, but it can detect them and throw the bad frame away. The trick is to send a few extra bits computed from the data. The receiver computes them again and compares.

The basic idea: redundancy

Every method on this page works the same way:

1. The sender calculates a small check value from the data.
2. It sends the data plus the check value.
3. The receiver recalculates the check value from the data it received.
4. If the two values differ, the data was damaged.

Think of a bank cashier counting a bundle of notes and writing the total on the band. At the next branch, the cashier counts again. If the totals differ, something went wrong on the way. The extra bits are called redundancy, because they carry no new information.

Parity bits

The simplest check is one parity bit.

• Even parity: the parity bit is chosen so that the total number of 1s, including the parity bit, is even.
• Odd parity: the total number of 1s is made odd.

def even_parity(bits):
    return "1" if bits.count("1") % 2 else "0"

data = "1011001"
sent = data + even_parity(data)
print("Sent:", sent)

received = "10110010"          # nothing changed
print("OK" if received.count("1") % 2 == 0 else "ERROR", received)

received = "10100010"          # one bit flipped
print("OK" if received.count("1") % 2 == 0 else "ERROR", received)

received = "10000010"          # two bits flipped
print("OK" if received.count("1") % 2 == 0 else "ERROR", received)

Sent: 10110010
OK 10110010
ERROR 10100010
OK 10000010

Look at the last line. Two flipped bits cancel out, and parity says "OK". A single parity bit catches every odd number of flipped bits and misses every even number.

Two-dimensional parity arranges the data in a grid and adds a parity bit to every row and every column. It catches all 1-, 2- and 3-bit errors, and can even correct a single-bit error, because the bad row and the bad column cross at the broken bit.

The Internet checksum

IPv4, TCP and UDP headers carry a 16-bit checksum, described in RFC 1071. Here is how it works:

1. Split the data into 16-bit words.
2. Add them all up using one's complement addition: if the sum overflows past 16 bits, the carry is added back into the low bits ("wrap around").
3. Flip every bit of the result. That is the checksum.

The receiver adds all the words including the checksum. If nothing changed, the result is 0xFFFF, which flips to 0.

def internet_checksum(data: bytes) -> int:
    if len(data) % 2:
        data += b"\x00"                      # pad to a whole number of words
    total = 0
    for i in range(0, len(data), 2):
        total += (data[i] << 8) | data[i + 1]
        total = (total & 0xFFFF) + (total >> 16)   # wrap the carry around
    return ~total & 0xFFFF

msg = b"Pune"
c = internet_checksum(msg)
print(f"Checksum of {msg}: 0x{c:04x}")
print("Receiver check:", internet_checksum(msg + c.to_bytes(2, "big")))
print("Damaged check: ", internet_checksum(b"Puna" + c.to_bytes(2, "big")))

Checksum of b'Pune': 0x4125
Receiver check: 0
Damaged check:  4

A result of 0 means "no error found". The damaged message gives a non-zero result. The checksum is quick to compute in software, which is why it is used in IP, TCP and UDP. But it is weak: if two words are swapped, the sum is the same, so the error is missed.

CRC: cyclic redundancy check

Ethernet and Wi-Fi use a much stronger check, the CRC. It treats the bits as a polynomial and divides by an agreed generator polynomial. Do not worry about the word polynomial: in practice it is long division where subtraction is replaced by XOR.

Here are the rules for a generator of r + 1 bits:

1. Append r zeros to the data.
2. Divide by the generator using XOR, never borrowing or carrying.
3. The r-bit remainder is the CRC. Send the data followed by the CRC.
4. The receiver divides what it received by the same generator. A remainder of all zeros means no error was detected.

Let us use data 110101 and generator 1011 (that is x³ + x + 1, so r = 3).

def xor_divide(bits, gen, show=False):
    bits = list(bits)
    for i in range(len(bits) - len(gen) + 1):
        if bits[i] == "1":
            for j in range(len(gen)):
                bits[i + j] = "0" if bits[i + j] == gen[j] else "1"
            if show:
                print("  step:", "".join(bits))
    return "".join(bits[-(len(gen) - 1):])

data, gen = "110101", "1011"
print("Dividing", data + "000")
crc = xor_divide(data + "000", gen, show=True)
print("CRC:", crc)
print("Send:", data + crc)
print("Receiver remainder:", xor_divide(data + crc, gen))

Dividing 110101000
  step: 011001000
  step: 001111000
  step: 000100000
  step: 000001100
  step: 000000111
CRC: 111
Send: 110101111
Receiver remainder: 000

Each "step" line is one XOR of the generator under a leading 1. Compare this with your hand working line by line. In GATE, they usually give the data and the generator and ask for the transmitted bits: here, 110101111.

Real CRC-32

Ethernet uses a 32-bit CRC called CRC-32. Python's zlib.crc32 uses the same generator polynomial, so you can see how even a tiny change gives a completely different value.

import zlib

for text in [b"Pay Rs 500 to Meera", b"Pay Rs 900 to Meera", b"Pay Rs 500 to Meena"]:
    print(f"{zlib.crc32(text):08x}  {text.decode()}")

4418ad9c  Pay Rs 500 to Meera
4112e01d  Pay Rs 900 to Meera
a26ff0c1  Pay Rs 500 to Meena

A good CRC catches all single-bit errors, all burst errors (a run of damaged bits) shorter than the CRC length, and the vast majority of other damage. That strength, plus fast hardware support, is why every Ethernet and Wi-Fi frame carries one.

Detection, correction and Hamming distance

The Hamming distance between two code words is the number of bit positions where they differ. For a code whose valid words are at least distance d apart:

• it can detect up to d - 1 bit errors;
• it can correct up to (d - 1) // 2 bit errors.

Networks usually detect errors and resend the data (TCP does the resending). Correction codes, called forward error correction, are used where resending is too slow or impossible, such as Wi-Fi, mobile links and satellite links.

Common mistakes

• Thinking parity catches two flipped bits. It catches only an odd number of flips.
• Using normal subtraction in CRC. CRC division uses XOR: 1 XOR 1 = 0, with no borrowing.
• Appending the wrong number of zeros. Append generator length minus one.
• Thinking error detection fixes errors. Detection only finds them. A higher layer must resend.

Key points

• Error detection adds redundant bits that the receiver recalculates and compares.
• One parity bit catches any odd number of bit errors; two-dimensional parity can fix one-bit errors.
• The Internet checksum is a one's complement sum of 16-bit words, used by IPv4, TCP and UDP.
• CRC divides by a generator using XOR; the remainder is sent, and the receiver expects a zero remainder.
• Ethernet and Wi-Fi use CRC-32 in the FCS field.
• A code with minimum Hamming distance d detects d - 1 errors and corrects (d - 1) // 2.

def xor_divide(bits, gen):
    bits = list(bits)
    for i in range(len(bits) - len(gen) + 1):
        if bits[i] == "1":
            for j in range(len(gen)):
                bits[i + j] = "0" if bits[i + j] == gen[j] else "1"
    return "".join(bits[-(len(gen) - 1):])

data, gen = "1001101", "1101"
crc = xor_divide(data + "000", gen)
sent = data + crc
print("CRC:", crc, "Sent:", sent)

damaged = sent[:2] + ("1" if sent[2] == "0" else "0") + sent[3:]
print("Damaged:", damaged, "remainder:", xor_divide(damaged, gen))

CRC: 100 Sent: 1001101100
Damaged: 1011101100 remainder: 001