Checksum

Checksum: Simple Yet Effective Error Detection

A checksum is one of the simplest and most widely-used error detection techniques in digital communication. Every time you download a file, send an email, or browse a website, checksums are silently working behind the scenes to verify data integrity. The concept is elegantly simple: add up all the data values, transmit the sum alongside the data, and let the receiver verify that the sum still matches.

The Basic Concept

Think of it this way: imagine you are a cashier counting money. You have a stack of bills, and someone tells you the total should be $847. You count the bills yourself — if you also get $847, the stack is probably correct. If you get a different number, someone has swapped a bill or one is missing. This is exactly how a checksum works with data.

In its simplest form:

1. Sender: Add up all data units (bytes, words, etc.) to get a sum
2. Sender: Transmit the data followed by the checksum (sum or its complement)
3. Receiver: Add up all received data units and compare with the received checksum
4. Result: Match → data probably correct; Mismatch → error detected

Types of Checksums

Simple Sum Checksum: Add all data bytes together, keep only the lower bits (modular arithmetic):

• Data: [0x25, 0x62, 0x3F, 0x52]
• Sum: 0x25 + 0x62 + 0x3F + 0x52 = 0x118
• Checksum (8-bit): 0x18 (lower byte only)

One's Complement Checksum: Add all data words using one's complement arithmetic (carry is added back):

• Used in TCP, UDP, and IP headers
• Sum all 16-bit words with end-around carry
• Take one's complement (flip all bits) as checksum

Two's Complement Checksum: Similar to one's complement but uses two's complement arithmetic. Less common in networking.

Fletcher's Checksum: Maintains two running sums — the data sum and the sum of partial sums:

• Checksum1 = (Checksum1 + data_byte) mod 255
• Checksum2 = (Checksum2 + Checksum1) mod 255
• Catches byte reordering that simple sums miss

The Internet Checksum (RFC 1071)

The Internet Checksum used in TCP/IP is perhaps the most important checksum in computing:

Algorithm:

1. Divide data into 16-bit words
2. Add all words using one's complement addition (if final sum exceeds 16 bits, wrap carry around)
3. Take one's complement of the result (invert all bits)
4. This is the checksum value

Verification:

1. Add all 16-bit words including the checksum
2. If no errors: result = 0xFFFF (all ones)
3. If result ≠ 0xFFFF: error detected

Example calculation: Data words: 0x4500, 0x0073, 0x0000, 0x4000, 0x4011

Step 1: 0x4500 + 0x0073 = 0x4573 Step 2: 0x4573 + 0x0000 = 0x4573 Step 3: 0x4573 + 0x4000 = 0x8573 Step 4: 0x8573 + 0x4011 = 0xC584

One's complement: ~0xC584 = 0x3A7B ← This is the checksum

Why one's complement?

• Byte-order independent (same result on big-endian and little-endian machines)
• Easy to update incrementally (if one field changes, adjust checksum without recomputing everything)
• Zero checksum indicates no errors (all-ones in one's complement = valid "zero")

Error Detection Capability

The checksum detects:

• All single-bit errors — Any single flipped bit changes the sum
• Most multi-bit errors — Multiple errors usually change the sum
• All errors in odd number of bits (for one's complement checksum)

The checksum FAILS to detect:

• Reordered data words — Moving words around may keep the same sum
• Compensating errors — +1 in one word and -1 in another cancel out
• All-zeros inserted or removed — Adding zero words does not change the sum

Detection probability: For random errors, an n-bit checksum fails to detect errors with probability approximately 2⁻ⁿ. A 16-bit checksum misses about 1 in 65,536 random error patterns.

Checksum vs. CRC vs. Hash

Implementation Efficiency

The Internet checksum was designed for efficient software implementation on 1970s hardware:

Modern processors compute this in a tight loop with minimal instructions. Some network interface cards compute TCP/UDP checksums in hardware for zero CPU overhead.

Where Checksums Are Used

1. IPv4 Header — 16-bit checksum protects the IP header (not payload)
2. TCP Segment — 16-bit checksum covers header + data + pseudo-header
3. UDP Datagram — 16-bit checksum (optional in IPv4, mandatory in IPv6)
4. ICMP — 16-bit checksum over entire message
5. File transfers — MD5/SHA checksums verify downloaded file integrity
6. Memory systems — ECC memory uses checksums for error detection/correction
7. Serial protocols — UART, SPI, I2C often use simple 8-bit checksums

Incremental Checksum Update

A powerful feature of one's complement checksums: when a single field changes, the checksum can be updated without recomputing over the entire data:

New checksum = Old checksum - Old field value + New field value (in one's complement)

This is essential for routers that must modify the TTL field in every IP packet — recomputing the full checksum for every packet would waste valuable processing time.

Limitations and When to Use Something Better

Checksums are appropriate when:

• Speed is critical and some undetected errors are acceptable
• The error model is random single-bit errors
• Hardware simplicity is important

Use CRC instead when:

• Burst errors are common (serial links, storage media)
• Higher detection reliability is needed
• You cannot tolerate undetected reordering

Use cryptographic hashes when:

• Intentional tampering must be detected
• File integrity verification over untrusted channels
• Digital signatures are required

Key Takeaways

1. A checksum detects errors by computing a sum of data values and comparing at the receiver — conceptually the simplest error detection method.
2. The Internet Checksum (one's complement sum) protects TCP, UDP, and IP headers with minimal computational overhead.
3. Checksums reliably detect single-bit errors but can miss compensating errors and data reordering.
4. For a 16-bit checksum, approximately 1 in 65,536 random error patterns goes undetected.
5. Incremental update capability makes one's complement checksums ideal for router processing.
6. Checksums trade detection strength for speed — use CRC for burst errors or cryptographic hashes for security.