PCPlus 320: Error detection and correction

OK, I admit it. I’ve been in the programming industry for more years that I care to count, and although I’d vaguely considered error detection in the past, it wasn’t until I did some research for this next article that I finally got to have some understanding of it all. And not only error detection but correction too: now that was pure magic. But, as with all these things, once you get the basic idea about how it works, all the magic gets stripped away.

I suppose the first kind of error detection I’d come across was the parity bit, especially with regard to the dodgy RAM and diskettes and trundling hard disks you used to have in the MSDOS days. Here we suppose that the storage medium is subject to some errors (either writing to the storage medium or reading it back again). What happened was that bytes were stored as 9 bits, the required eight bits in the byte and a parity bit. If there were an odd number of 1 bits in the byte, the parity bit would be set to 1 for even parity or 0 for odd parity. When the byte was retrieved the hardware could check that the 9 bits read had an even number of 1 bits or an odd number, depending on the parity scheme in place. It couldn’t do anything about it if it detected an error, of course.

The next example of error detection I came across was a checksum calculation, such as credit card numbers: again, it detects errors but doesn’t help correct them. Mind you, with a credit card number you can just ask the customer for it again; it’s unlikely you’d have such a data storage problem that a credit card number gets corrupted. A more interesting checksum is Cyclic Redundancy Check (CRC), or cryptographic hashes like SHA-1 or MD5. These checksums try and identify cases where the input message is corrupted in a perhaps subtle way.

Then there’s barcodes. Although linear barcodes tend to have error detection though some kind of checksum,  2D barcodes generally have error correction as well since they can store more information per unit area. The familiar QR code uses the Reed-Solomon error correction algorithm. In the article I show how to calculate an earlier error correction algorithm, Hamming codes, and how they can be used to detect and correct errors. The (7,4) Hamming code I show is the best way to detect and correct single bit flips in 4 data bits.

In essence, in any situation where you are trying to transmit data (a message) from point A to point B digitally (scanning barcodes, streaming from a DVD, reading SSD memory chips, etc) where there is a possibility that some physical damage will cause data corruption, there will be some error detection and correction algorithm in the background trying to make sure that we get what we expect. Like many things in the digital realm, it’s just invisibly working for us.

This article first appeared in issue 320, April 2012.

You can read the PDF here.

(I used to write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK, which sadly is no longer published. The column was called Theory Workshop and appeared in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

  Loading links to posts on similar topics...