Checksum Bitwise

What Is a Checksum at the Bit Level?

A checksum is a small, fixed-size value computed from a larger block of data. At the bit level, it is nothing more than running a deterministic bitwise operation — XOR, addition, or parity counting — across every byte or word of the data. The result is a compact fingerprint that changes if any bit in the original data changes. I use checksums constantly: verifying file downloads, checking RAM integrity via ECC, and debugging serial protocol implementations.

Every checksum system follows the same pattern. The sender computes the checksum and appends it to the data. The receiver computes the checksum from the received data and compares it to the appended value. If they match, the data is assumed intact. If they differ, corruption occurred and the receiver can request a retransmission. The fundamental limitation is that no checksum can detect all possible errors — the question is how many it misses.

I wrote a TCP-like checksum routine for a custom network protocol used in an IoT project. The algorithm was straightforward — sum 16-bit words with carry-wrap — but implementing it in C on a microcontroller with limited memory required careful attention to the carry handling.

Parity Bits: The Simplest Checksum

A parity bit is a single-bit checksum. Even parity ensures the total number of 1 bits in the data plus the parity bit is even. Odd parity ensures it is odd. Parity can detect any odd number of bit flips, but it misses even-numbered flips. Despite this limitation, parity is everywhere: in RAM (ECC memory uses multiple parity bits), in serial communication (UART frames have a parity bit), and in RAID arrays (dedicated parity drives).

// Parity calculation in C
uint8_t parity_even(uint8_t byte) {
    // Count bits with a simple loop (or use a lookup table)
    uint8_t count = 0;
    while (byte) {
        count += byte & 1;
        byte >>= 1;
    }
    return (count % 2 == 0) ? 0 : 1;
}
// XOR all bits: parity = (bit0 ^ bit1 ^ ... ^ bit7)
// Compiler: (__builtin_popcount(byte) & 1)

XOR Checksum (LRC — Longitudinal Redundancy Check)

An XOR checksum goes beyond a single parity bit by XORing all bytes in the message together. The result is a single byte (or word) that captures the parity of each bit position across all bytes. XOR checksums detect any odd number of bit flips in any bit position, but they miss cases where an even number of bits flip in the same bit position across different bytes.

XOR checksums are popular in embedded systems and serial protocols because they are trivially cheap to compute. The MODBUS RTU protocol uses an XOR-based checksum for its simpler variants. Many bootloaders use XOR checksums to verify firmware images before flashing.

// XOR checksum implementation
uint8_t xor_checksum(const uint8_t *data, size_t len) {
    uint8_t checksum = 0;
    for (size_t i = 0; i < len; i++) {
        checksum ^= data[i];  // XOR each byte into the accumulator
    }
    return checksum;
}

The IP Header Checksum (One's Complement Sum)

The Internet Protocol (IP) header checksum is a more robust checksum that uses one's complement addition instead of XOR. It is computed by summing all 16-bit words of the IP header, wrapping any carry back around, and then complementing the result. This detects all single-bit errors and most multi-bit errors.

The clever part is verification. The receiver sums all 16-bit words including the checksum field itself. If the header is intact, the result will be 0xFFFF (all bits 1 in one's complement). Any other value indicates corruption. This "inclusive" check simplifies receiver logic — no comparison needed, just check if the result is all ones.

// IP header checksum calculation
uint16_t ip_checksum(const uint16_t *header, size_t word_count) {
    uint32_t sum = 0;
    for (size_t i = 0; i < word_count; i++) {
        sum += header[i];
    }
    // Fold 32-bit sum to 16 bits (one's complement addition)
    while (sum >> 16) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }
    // Return one's complement
    return (uint16_t)~sum;
}
// Verification: if sum of all 16-bit words (including checksum) is 0xFFFF, header is intact

Checksum Weaknesses You Should Know

No checksum is perfect. I once spent an afternoon tracking down a data corruption bug in a serial protocol — the XOR checksum passed every time because two bytes had flipped in a way that cancelled out. Here is what each checksum type misses:

XOR Checksum Blind Spots

If byte 0 has bit 3 flip from 0 to 1 and byte 2 has bit 3 flip from 1 to 0, the XOR checksum stays the same. The flips cancel because 1 XOR 1 = 0 and 0 XOR 0 = 0 at that bit position. This happens whenever an even number of bits flip in the same bit position across different bytes.

Parity Weakness

A two-bit flip in the same byte maintains parity (even stays even, odd stays odd). This is why DDR memory uses ECC with multiple parity bits — SECDED (single error correct, double error detect) requires multiple parity bits per data word.

Complement Sum Weakness

The IP header checksum can miss errors where 16-bit words are swapped in order, since addition is commutative. It also misses cases where zeros are inserted between non-zero words. This is why TCP and UDP use a stronger checksum that includes a pseudo-header.

Summation Checksums in Practice

A simple summation checksum (adding all bytes as 8-bit or 16-bit values) catches more errors than XOR but has a different blind spot: it can miss overflow cancellations. Most practical implementations use a one's complement sum or a Fletcher checksum, which adds both a simple sum and a cumulative sum to improve error detection.

The Fletcher checksum detects all single-bit errors, all two-bit errors, and most burst errors. It is used in UDP-Lite, SCTP, and some file systems. It sits between simple XOR checksums and full CRC in both complexity and error-detection strength.