applets.

Error Fixer

← All apps

About Error Fixer

Computers keep everything as bits, 0s and 1s, and bits get flipped: by electrical noise on a line, a scratch on a disc, a cosmic ray hitting a memory chip. This bench shows the tricks that catch the flips, and the cleverer ones that put them right. Each bit is drawn as a ring of a core memory, the way computers stored bits from the 1950s to the 1970s: a lit ring is a 1, a dark one a 0, and a red outline marks a bit the noise flipped (you can see that; the receiver can't).

PARITY: type a short message; each letter becomes a byte of 8 bits (accented letters take two or more), plus one parity bit that makes the number of 1s even. Click any ring to flip it. One flip in a byte makes its count odd and the lamp goes red; two flips in the same byte cancel out and slip through. Tick 2-D grid for a row of parity bits along the bottom too: one flip then lights one row and one column, which cross at the bad bit, and FIX IT flips it back.

HAMMING: four data bits become seven. Each of the three circles must hold an even number of 1s. Flip a bit and the circles that turn odd point at it: the bit inside exactly those circles. Two flips fool it into "mending" a third bit; tick (8,4) for one more bit, the parity of the whole word, and two flips are spotted instead of being made worse.

NOISY LINE: send a message down a line that flips each bit with the chance you set. RUN sends it four ways at once, each with its own noise: plain, every bit said three times (the receiver takes the majority), Hamming (7,4) and Hamming (8,4). Wrong letters are red; yellow letters are ones the (8,4) code knows are damaged but can't mend (it would ask for them again). The table shows the cost in bits and the share of letters that arrive wrong, with the Expected share worked out exactly. Changing a setting fades the old result until you RUN again. The noise number makes a run repeatable.

CHECK DIGITS: the last digit of an ISBN, a barcode or a bank card number is worked out from the others, so most typing slips give a number that doesn't add up. Type a number (or one digit short, and the page gives the missing check digit), or press CHANGE A DIGIT or SWAP NEIGHBOURS to make a slip. The report tries every possible single slip of your number. Card numbers here are made-up test numbers only: never type a real card number into any page that doesn't need it. Nothing you type here is sent or kept.

QR: a message as the codewords of the smallest QR code (26 bytes), the data followed by Reed–Solomon check codewords. Click a codeword to damage it: a SCRATCH changes it without the reader knowing where; a BLOT is damage the reader can see, so it knows where the gaps are. The reader can mend e scratches and b blots as long as 2e + b is no more than the number of check codewords.

THE STORY

Parity bits are old: punched paper tape and magnetic tape carried a parity track, and early computer memories kept a parity bit for each word, so a flipped bit stopped the machine instead of quietly giving a wrong answer.

Richard Hamming worked at Bell Telephone Laboratories, where in 1947 he ran his programs on a relay computer at weekends. When it found an error it gave up on the job and moved on to the next, and on Monday he found his work thrown away. His complaint, as he told it: if the machine can find an error, why can't it work out where it is and correct it? His answer was published in 1950 as "Error Detecting and Error Correcting Codes" (Claude Shannon had already used the (7,4) code as an example in his 1948 paper, crediting Hamming). The extended (8,4) form, which corrects one error and detects two, is the idea behind the error-correcting memory in servers today, which stores 8 check bits with every 64 data bits.

Hans Peter Luhn, a researcher at IBM, filed a patent in 1954 for a hand-held device to check numbers (granted in 1960); his rule now checks bank card numbers and phone handset serial numbers. The 10-digit ISBN became an international standard in 1970, growing out of the 9-digit book numbers British publishers began in the late 1960s; since 2007 books carry a 13-digit ISBN, which is a barcode number starting 978 or 979. The 13-digit barcode number dates from the late 1970s, a European form of the American 12-digit supermarket barcode of 1973.

Irving Reed and Gustave Solomon published their codes in 1960. They now guard CDs, DVDs, data from deep-space probes, hard drives and QR codes, which were invented in Japan in 1994 to track car parts.

HOW IT WORKS

Parity only counts: any odd number of flips in a byte shows, any even number hides. The 2-D grid adds a count for every column, so one flip shows in exactly one row and one column. Two flips are always seen but can't be placed; four flips on the corners of a rectangle hide completely.

Hamming's code numbers the seven bits 1 to 7 and puts parity bits at 1, 2 and 4. The parity bit at 1 checks every position whose binary number ends in 1 (1, 3, 5, 7), the one at 2 those with a 2 in them (2, 3, 6, 7), the one at 4 those with a 4 (4, 5, 6, 7): these are the three circles. When one bit flips, the failing checks, read as a binary number (4s, 2s, 1s), are its position. Any two codewords differ in at least 3 places, so one flip leaves a word nearer to the original than to any other. The (8,4) code's extra bit makes that 4 places: one flip changes the whole-word parity and two don't, which is how it tells them apart.

Check digits: ISBN-10 multiplies the digits by 10, 9, … 1 and the total must divide by 11 (the check digit can need to be 10, written X). Because 11 is prime, every single wrong digit and every swap of two digits is caught. The barcode number weights the digits 1, 3, 1, 3, … and the total must divide by 10: every single slip is caught, but swapping two neighbours that differ by 5 (such as 0 and 5) is not. Luhn doubles every second digit from the right, taking 9 off anything over 9; it catches every single slip and every neighbour swap except 09 ↔ 90.

Reed–Solomon treats each byte as a number in a field of 256 elements (GF(28), where adding is exclusive-or and multiplying is done with powers of a generator) and the message as the coefficients of a polynomial. The check codewords make the whole block a multiple of a known polynomial with roots 1, α, α2, … Damage leaves a remainder at those roots (the syndromes); the Berlekamp–Massey method finds a polynomial whose roots mark the damaged places, and Forney's formula gives how much each one is out. The page does all of this for real: the mended message is whatever the sums give, so too much damage is refused, or (rarely) mended into the wrong message. The smallest QR code holds 26 codewords: at levels L, M, Q and H, 7, 10, 13 and 17 of them are check codewords, and the standard promises to mend 2, 4, 6 and 8 wrong ones, roughly the 7%, 15%, 25% and 30% usually quoted. Mathematically the L and M levels could mend one more; the spare check codewords guard against a wrong mend. A real QR code also starts the data with a few bits saying what kind of data follows and how long it is, and spreads the codewords over the square; here the codewords are just the bytes of your message, then filler bytes 236 and 17 as QR codes use.

The noisy line uses a seeded random number generator, so the same noise number gives the same flips. The Expected shares come from going through every possible pattern of flips in a block (all 128 or 256 of them) and adding up the chances.

FURTHER WATCHING AND READING

up to 10 bytes
Try