A Cyclic Redundancy Check (CRC) is an error-detecting code computed by treating a data block as a polynomial over GF(2) — the binary field where all arithmetic is modulo 2 (XOR) — and dividing it by a fixed generator polynomial. The remainder of this division is appended to the data; the receiver recomputes the division and flags any mismatch as a transmission error. CRC-32, defined by the generator polynomial 0x04C11DB7, is used in Ethernet frames, ZIP archives, PNG images, and the TCP/IP suite, offering guaranteed detection of all single-bit errors, all double-bit errors, all odd numbers of bit errors, and all burst errors shorter than 32 bits.
The simulator visualises the XOR long-division step by step, showing each intermediate remainder and the shift register circuit that performs the same computation in hardware. You can switch between CRC-8, CRC-16, and CRC-32 presets, edit the input message, and inject single or multi-bit errors to verify detection.
Why is arithmetic over GF(2) (XOR) used for CRC?
GF(2) arithmetic has no carries, making CRC computation extremely efficient in hardware and software: addition becomes XOR, multiplication becomes AND, and polynomial division can be implemented as a linear feedback shift register (LFSR) clocked once per bit. The algebraic structure of GF(2) polynomials also makes formal error-detection proofs tractable using coding theory.
What types of errors does CRC-32 guarantee to detect?
CRC-32 detects: all single-bit errors; all double-bit errors (for messages shorter than 2³² − 1 bits); all odd numbers of bit errors (because 0x04C11DB7 is divisible by (x+1)); all burst errors of length ≤ 32 bits; and a large fraction (1 − 2⁻³²) of longer burst errors. It does NOT guarantee detection of all multi-bit random errors — for that, stronger codes such as Reed-Solomon are used.
How does a linear feedback shift register (LFSR) compute CRC in hardware?
An LFSR is a chain of flip-flops whose feedback taps correspond to the 1-bits of the generator polynomial. Each clock cycle shifts one bit of input in and XORs it with feedback from the taps. After all data bits have been clocked through, the register contents are the CRC remainder. This processes one bit per cycle at full wire speed — billions of bits per second in modern Ethernet ASICs.
There are several CRC-32 variants: the Ethernet/ZIP/PNG variant (polynomial 0x04C11DB7, initial value 0xFFFFFFFF, reflected input/output, final XOR 0xFFFFFFFF) and the Castagnoli variant CRC-32C (polynomial 0x1EDC6F41) used in iSCSI, SCTP, and ext4. Mixing variants causes checksum mismatches. The Rocksoft model defines 7 parameters that fully specify a CRC algorithm.
No. CRC is a simple error-detecting code, not a cryptographic hash. An adversary who can modify a message can trivially recompute the CRC and forge a valid checksum. For tamper detection in security contexts, use a message authentication code (MAC) such as HMAC-SHA256 or a cryptographic hash like SHA-3. CRC is appropriate only for accidental corruption detection in trusted channels.
Processing one bit at a time is slow in software. Instead, a 256-entry lookup table is precomputed: table[b] = CRC of a single byte b followed by zero-padding. Processing each byte of input then requires only one table lookup, one XOR, and one shift — making table-driven CRC-32 compute at several GB/s on modern CPUs. x86 processors with the SSE4.2 instruction set have a dedicated CRC32 instruction for CRC-32C.
The number indicates the degree of the generator polynomial and the width of the checksum in bits. CRC-8 (8-bit remainder) is used in embedded protocols like SMBus and 1-Wire where code size is at a premium. CRC-16 (16-bit) is common in serial protocols (MODBUS, USB data packets) and detects all burst errors up to 16 bits. CRC-32 (32-bit) gives 1-in-4-billion false-negative probability and is the standard for file systems and network packets.
Yes — collisions exist because CRC maps arbitrarily long messages to a fixed-length checksum (e.g., 32 bits). Given a valid message+CRC pair, you can always construct another message with the same CRC by appending carefully chosen bits. The probability that a random corruption produces the same CRC-32 is 2⁻³² ≈ 2.3×10⁻¹⁰, which is negligible for communication but not for adversarial scenarios.
The generator polynomial g(x) determines the error-detection properties of the CRC. A good generator must be primitive (to detect all odd-bit errors) or at least include (x+1) as a factor. The CRC-32 polynomial 0x04C11DB7 was designed to maximise burst-error detection for Ethernet frame lengths. Selecting optimal polynomials for specific code lengths and error models is an active area of coding theory research.