EMZETT.
Login

Emzett Wiki

Checksums, parity and CRC: Detecting errors in data

Properties1
tagsglossar, grundlagen, daten

2 min read

Checksums, parity and CRC: Detecting errors in data

In short: Check values such as parity bit, checksum and CRC are stored or sent with the data; if they do not match at the receiver, something went wrong in transmission or storage.

In more detail: When radioing, cabling, storing and copying, individual bits can flip (noise, defects, radiation). To notice this, redundant information is appended to the data. These methods detect (and some correct) random errors but do not protect against manipulation: for that you need cryptographic hashes and signatures.

In Depth

Parity bit

An additional bit makes the number of ones even (even parity) or odd:

Data 1011001  → number of ones 4 → parity bit 0 → 10110010
Data 1011011  → number of ones 5 → parity bit 1 → 10110111

Detects every single-bit error but not errors in an even number of bits and locates nothing. Used in simple serial links and memories. Two-dimensional parity (rows and columns) can locate a single error.

Checksum

The data words are added (often modulo 2^n) and the result sent along. Examples: internet checksum in IP/TCP/UDP headers (16-bit one’s-complement sum), ISBN and IBAN check digits (modulo 11/97 detect typing errors), Luhn algorithm for credit card numbers. Simple and fast but weaker (swaps are not always noticed).

CRC (cyclic redundancy check)

The data is regarded as a large polynomial over GF(2) and divided by a generator polynomial; the remainder is the CRC value (for example CRC-32).

import zlib
print(hex(zlib.crc32(b"Hello world")))

CRC detects single-bit, double-bit and all burst errors up to the length of the value with high certainty, is easy to implement in hardware and therefore standard in Ethernet, Wi-Fi, USB, SATA, ZIP, PNG, Bluetooth. It is no protection against attacks (easy to forge).

Assessment and practice

  • Hashes (SHA-256) as download check values: also protect against deliberate changes (if the source of the hash is trustworthy).
  • Error correction (ECC RAM, Hamming code, Reed-Solomon in CDs/QR codes, RAID parity) additionally repairs errors.
  • Layer model: physical → data link (Ethernet CRC) → transport (TCP checksum) → application (hash); each layer checks for itself.
  • When copying large data sha256sum/rsync --checksum helps against silent errors (bit rot).

See also: Hashing, SHA-256

Backlinks