Also known as: cyclic redundancy check, CRC, FCS, frame check sequence
A cyclic redundancy check (CRC) is an error-detection code that appends a short checksum — the remainder of a polynomial division of the message by a fixed generator polynomial.1 The receiver repeats the division; a non-zero remainder means the frame was corrupted in transit, so it is discarded. A CRC detects errors but, on its own, does not correct them, which distinguishes it from forward error correction.
How it works
CRCs work in the algebra of polynomials over GF(2) — binary coefficients where addition is
XOR and there are no carries. The message bits are treated as the coefficients of a big
polynomial M(x). That polynomial is shifted left by the CRC width (multiplied by xⁿ) and
divided by a fixed generator polynomial G(x) of degree n; the remainder R(x) is the
n-bit CRC that gets appended. Because the transmitted word M(x)·xⁿ + R(x) is now exactly
divisible by G(x), the receiver just divides the whole thing again and checks for a zero
remainder. In hardware or software this “division” is a chain of XORs implemented with a
linear-feedback shift register or a byte-wise
lookup table, so it costs almost nothing.
The strength of a CRC comes from choosing G(x) well. A well-chosen degree-n generator guarantees detection of: all single-bit errors; all odd numbers of bit errors (if G(x) has x+1 as a factor); all burst errors up to n bits long; and any other error pattern except the vanishingly small fraction (about 2⁻ⁿ) that happens to be a multiple of G(x). This is far stronger than a simple sum-based checksum for the same number of bits, which is why CRCs dominate frame validation in communications.
Variants
Standard generators are known by width and polynomial:
- CRC-16-CCITT (
0x1021) — used as the frame check sequence (FCS) in AX.25 packet radio, AIS, and many HDLC-derived links. - CRC-24 — ADS-B / Mode S uses a 24-bit CRC (
0xFFF409) that is also overlaid with the aircraft address, so a valid remainder simultaneously confirms integrity and recovers the ICAO address. - CRC-16 / CRC-9 / CRC-8 — DMR sprinkles several CRC widths across its bursts (a 9-bit CRC on the CSBK/data headers, 5- and 8-bit CRCs elsewhere).
- CRC families in P25 — Project 25 uses a CRC-16 on packet data and header blocks and shorter CRCs on control words.
- DSC — maritime Digital Selective Calling protects its sequences with a parity/error-check scheme in the same spirit.
In practice
A subtlety worth knowing: many real CRCs are not the textbook plain remainder. Protocols add
an initial fill (preloading the register with all-ones so leading zeros are covered), a
final XOR of the output, and bit-reflection of input and/or output bytes. Getting a CRC to
match a live signal often means matching those parameters exactly, not just the polynomial —
CRC-16/CCITT-FALSE vs CRC-16/X25 differ only in init and reflection yet produce entirely
different check values.
Relevance to SDR
CRC validation is the last gate before GopherTrunk trusts a decoded frame: after demodulation, de-interleaving, and any FEC, the CRC says whether the surviving bits are self-consistent. GopherTrunk recomputes the appropriate CRC for each protocol it decodes — CRC-24 on ADS-B squitters, CRC-16 on AIS sentences and AX.25 frames, the DMR and P25 header CRCs — and drops frames that fail, so it reports channel grants, positions, and talkgroups that actually arrived intact rather than noise that happened to pass framing. Some systems combine a CRC with a burst-correcting Fire code or a BCH code so the same polynomial machinery can both correct short bursts and detect what it cannot fix.
Sources
-
Cyclic redundancy check — Wikipedia, for the polynomial-division construction, standard generators, and detection guarantees. ↩