Every Ethernet frame, ZIP file, and PNG carries a CRC: a few check bits computed by treating the data as one enormous binary number and taking its remainder after dividing by a fixed polynomial. Flip any bit in transit and the remainder changes, so the error is caught. It is polynomial division over GF(2) — pure bitwise — so it runs in real I-13. And it is kin to the corpus’s own self-checking seal.
THE TECHNIQUE remainder mod a generator polynomial
Read the message bits as the coefficients of a polynomial over GF(2) (arithmetic where 1+1=0, i.e. XOR). Divide by a fixed generator polynomial and keep the remainder — that is the CRC, appended to the message. The receiver re-divides the whole thing; a clean message leaves remainder zero, a corrupted one does not. Type a message, then flip a bit. live demo
HISTORY & CREDIT a framework, then a committee’s polynomial
“Peterson invented CRC-32” — he gave the polynomial theory; the actual polynomial everyone runs was chosen by a committee 14 years later. cited
1961 · W. Wesley Peterson & D. T. Brown publish the general theory of cyclic codes for error detection and the shift-register hardware — the framework. ~1975 · the ubiquitous CRC-32 generator (0x04C11DB7) comes from AUTODIN-II work, and is cemented by Ethernet / IEEE 802.3. Crediting it to Peterson conflates framework with a later choice. the strength · a good degree-n polynomial catches all burst errors shorter than n bits, all single- and double-bit errors, and all odd numbers of bit flips — exactly the failures a wire produces. the limit · a CRC is a linear function — an adversary can edit the message and fix the CRC to match. It guards against noise, not malice; it is not a hash.
The corpus’s own seal echoes this: a palindrome that reads the same backward is its own check — rev-e — where a CRC bolts an external remainder on. noise, not malice
RECOMMEND FOR I-13 XOR and shift, exactly what landed
A bitwise CRC is a loop of shift, test the top bit, conditional XOR with the polynomial — the integrated bitwise operators (darts 001/029), and it runs bit-exact on the compiler:
$ i13 run crc.i13 # CRC-8 (poly 0x07) of the byte 0x42
out = 201 # 0xC9, bit-exact vs the reference; append it and re-check -> 0
Recommend:nothing new — a strict no-wall: the whole computation is & << ^ over integers that stay within f64’s exact range (a byte-at-a-time CRC keeps values under 232). The 256-entry table variant is a bounded array; the bit-at-a-time variant is pure bitwise. A clean fit. Note: conceptually the CRC is the external checksum the corpus mostly avoids — rev-e’s point is that a palindrome needs none; the CRC is the honest counter-example, the check you bolt on when the data is not self-mirroring.