Parity and checksums

The formula

Even parity over n bits:

p = b₁ ⊕ b₂ ⊕ ... ⊕ bₙ

Reading: XOR every data bit together; append p so the total count of 1s comes out even. Odd parity is the complement. ASCII K is 1001011 — four 1s, already even — so its even-parity bit is 0.

What one parity bit buys:

detects: every odd number of bit errors
misses:  every even number of bit errors

Reading: flip one bit and the parity check fails. Flip two and it passes clean. There is no partial credit in between.

XOR-style longitudinal redundancy check over a block of bytes:

LRC = B₁ ⊕ B₂ ⊕ ... ⊕ Bₙ

Reading: the same parity idea run lengthwise — bit 0 of the LRC is the parity of every byte's bit 0, and so on up. NMEA GPS sentences use exactly this over the characters between $ and * ^[12].

Additive two's-complement LRC (Modbus ASCII, Intel HEX flavor) ^[3]^[13]:

LRC = (−(B₁ + B₂ + ... + Bₙ)) mod 256

Reading: sum the bytes, throw away carries, negate. The receiver adds everything including the LRC and checks for zero. For the Modbus request bytes 01 03 00 00 00 0A, the sum is 0x0E and the LRC is 0xF2.

The Internet checksum (IP, TCP, UDP) ^[6]^[7]:

checksum = NOT( ones'-complement sum of the 16-bit words )

Reading: add the data as 16-bit words, folding each carry back into the low end, then invert. Two words 0x4500 and 0x0030 sum to 0x4530, giving checksum 0xBACF. The end-around carry makes the result identical on big- and little-endian machines ^[7].

Fletcher's checksum — the position-sensitive fix ^[8]^[9]:

A := (A + Dᵢ) mod 255        B := (B + A) mod 255

Reading: A is a plain running sum; B is a running sum of A, so early bytes are counted more times than late ones. Reorder the data and B changes even though A doesn't.

Where you meet it

The UART settings fight on the bench. 8N1 versus 7E1 versus 8E1 — that middle letter is the parity bit, and a mismatch between your terminal and the device under test produces the classic maddening symptom: some characters arrive fine and others arrive as garbage or framing errors, depending on how many 1s each character happens to carry. The scope's serial decode will show you the ninth bit if you tell it parity is there.
GPS integration. Every NMEA 0183 sentence ends in * plus a two-hex-digit XOR checksum, and the checksum is mandatory ^[12]. $GPGLL,4916.45,N,12311.12,W,225444,A*31 — hand-edit that sentence in a simulator script without recomputing the 31 and your receiver will silently drop it. Half of all "the simulator isn't working" tickets are this.
The test stand PLC and the firmware load. Modbus ASCII frames carry the additive LRC ^[13]; Modbus RTU carries a CRC-16 instead. Every line of an Intel HEX firmware image ends in a two's-complement checksum byte, which is why a flash loader can reject a file that got mangled in an email or a bad FTP transfer before it ever touches the part.
The acceptance data package. "File checksums verified" is a line item in most ATPs and delivery reviews. When the review board asks how you know the as-run procedure PDF on the delivery drive matches the one that was signed, a checksum — usually a much stronger hash by now — is the answer on record.

How it works

Everything in this family is the same move: compress the message down to a few check bits with a function cheap enough to run on every byte, send both, recompute on the far end, compare. The engineering content is entirely in what each function can and cannot see.

Parity sees exactly one thing — whether an odd number of bits flipped ^[1]. That was a good match for early hardware where errors really did arrive one bit at a time. It is a poor match for serial lines, where the common failure is a noise burst that clobbers several adjacent bits; a burst that flips an even number sails through, so parity's catch rate on real burst noise is roughly a coin flip. It also cannot locate the error. Hamming's whole career pivot started from that exact limitation ^[10].

Simple checksums are blind in more interesting ways, and each blindness is worth knowing cold:

Order. XOR and plain addition are commutative, so the LRC of bytes 12 34 56 and 56 34 12 is 0x70 either way. A DMA engine that transposes words, or a protocol bug that swaps fields, is invisible to both — and to the Internet checksum too. Fletcher's second accumulator exists precisely to break this symmetry: the same two byte orders produce Fletcher-16 values 0xF49C and 0x7D9C ^[8].
Compensation. In an additive checksum, a +1 error in one byte and a −1 error in another cancel exactly ^[2]. Two wrongs make a pass.
Zeros. The XOR LRC, the additive LRC, and Fletcher's sums all return zero for all-zero data, so on those checks a dead driver streaming zeros looks like a valid message carrying a valid checksum ^[3]^[8]. The Internet checksum dodges this by design: the final inversion means correct all-zero data ships a checksum of 0xFFFF, so an all-zero packet cannot verify — the appendix to RFC 1071 shows the designers naming "an all-zero message passing to the destination" as exactly the failure to engineer out ^[7]. The zeros trap that does survive in IP-land is different: an IPv4 UDP checksum field of 0x0000 means "no checksum computed," not "checksum is zero" ^[14]. And Fletcher has its own blind spot between all-zero and all-one blocks, since 0x00 and 0xFF are congruent mod 255 ^[8].

The quantitative way to think about it: an n-bit check that behaves well lets a random corruption through with probability about 2⁻ⁿ — 1 in 256 for one byte of LRC, 1 in 65,536 for the Internet checksum. But burst errors and structured hardware faults are not random, which is where CRCs earn their keep: a CRC is parity's grown-up sibling, and it guarantees detection of any burst shorter than the check width instead of hoping. The pecking order for detection strength per bit is roughly parity, additive checksum, Fletcher/Adler, CRC — and cost climbs the same ladder, which is the whole reason all four still exist. (Adler-32 trades Fletcher's modulus for the prime 65,521; measured results show Fletcher-32 detecting slightly better anyway ^[8].)

Two mistakes worth naming. First: a passing checksum is evidence, not proof. It bounds the probability of undetected corruption; it does not certify the data, and it says nothing at all about whether the data was right before the checksum was computed over it. Garbage in, checksummed garbage out. Second: none of this is security. Any of these checks can be recomputed by whoever altered the data, in microseconds. Integrity against accident is a checksum problem; integrity against intent is a cryptographic-hash problem, and confusing the two is how "verified" firmware gets a rootkit.

One bench trick that looks like a bug until you know it: RS-485 multidrop firmware sometimes runs "mark" or "space" parity — a ninth bit forced to 1 or 0 — not as a check at all, but as an address flag telling every drop on the bus whether the byte is an address or payload. UART vendors document the trick outright: since UARTs move 8-bit data, the parity bit stands in as the ninth bit — the master forces it to 1 for an address byte and 0 for data, and non-addressed slaves ignore everything until the next address byte ^[15]. If a device's parity setting reads as permanently wrong, check whether it's actually nine-bit addressing.

History

Parity checking is as old as commercial computing — by the time anyone thought to name it, it was already wired in. The UNISERVO tape drive that shipped with UNIVAC I in 1951, the first tape drive on any commercially sold computer, wrote eight tracks: six for data, one for timing, and one parity track for error checking ^[4]^[5]. Detection without correction had a known cost: at Bell Labs in the late 1940s, Richard Hamming's weekend jobs on relay computers died unattended whenever a check tripped, and his irritation at machines that could detect an error but not fix it produced the error-correcting codes he published in 1950 ^[10]^[11]. Parity was the floor those codes were built on.

The checksum branch grew up with networking. The ARPANET-era designers of IP and TCP standardized the 16-bit ones' complement sum in 1981 ^[6], chosen less for detection strength than for properties an implementer loves — byte-order independence and cheap incremental update when a router touches one header field; by 1988, Braden, Borman, and Partridge devoted RFC 1071 to computing it fast, because the checksum loop had become a limiting factor on TCP throughput ^[7]. Meanwhile John G. Fletcher at Lawrence Livermore had worked out, in the late 1970s, how to buy position sensitivity for two adds per byte; his paper ran in the January 1982 IEEE Transactions on Communications ^[8], and the algorithm was later offered as a TCP alternate checksum outright ^[9]. The family's newest members are the fuzzy and cryptographic hashes — different animals, same job description: a small number that vouches for a big one.

Related tools

/tools/adc-resolution — the bits and word sizes these checks ride shotgun on
/tools/snr-enob — the analog noise budget that decides how often a parity error actually fires
/tools/link-budget — bit error rate at the demodulator sets the workload for every check downstream
/tools/loop-4-20ma — the process-instrumentation world where Modbus and its LRC live

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →