Chapter 3. Error Correction

3.1. Close but No Cigar

1. Speedwalking.
2. America OnLine, CompuServe and Prodigy.
3. Veggie burgers.
4. Using a Stairmaster.
5. Winning the Wild Card pennant.
6. Driving 55 mph.
7. Living in suburbia.
8. New Year's Resolutions.
9. Lists as poetry.
10. Lists as a simple way to give structure to humor.
11. Cigarettes.

3.2. Correcting Errors

The theory of computers rests on an immutable foundation: a bit is either on (“1”) or off (“0”). Underneath this foundation, however, is the normal, slightly random, slightly chaotic world in which humans spend their time. Just as the sun is sometimes a bit brighter than usual and sometimes it rains for a week straight, the physics that govern computer hardware are a bit more random. Sometimes the spot on the hard disk responsible for remembering something doesn't behave exactly perfectly. Sometimes an alpha particle from outer space screams through a chip and changes the answer.

Computer designers manage to corral all of this randomness through a mixture of precision and good mathematics. Clean machines eliminate the dirt that screws things up and the math of error-correcting codes is responsible for fixing up the rest of the problems that slip through. This mathematics is really one of the ideas that is most responsible for the digital explosion by making it possible to build a digital circuit with a bit of sloppiness that can never be present in an analog world. Designers know that the sloppiness can be fixed by a bit of clever mathematics.

Error-correcting codes can be used effectively to hide information in a number of important ways. The most obvious is to just introduce small errors into a file in an organized fashion. If someone tries to read the file with ordinary tools, the error correction patches up these changes and no one is the wiser. More sophisticated tools could find these changes by comparing the original file with the cleaned-up version or simply using the error-correcting principles to point the location. The message could be encoded in the position of the errors.

A high number of errors might indicate the existence of a message. Chapter 17 describes how to build statistical models to detect abnormal patterns like a high error rate.

Some music CD manufacturers are taking advantage of the differences between the error-correcting mechanisms in computers and CD players. Strategically placed errors will be corrected by a CD player but labeled as disk failure by the mechanisms in computers.

Page 178 shows how to construct a system using random walks. Ross Anderson, Roger Needham, and Adi Shamir used a similar approach to hide information in their steganographic file system. [ANS98]

Error-correcting codes can also be used to help two people share a channel. Many semi-public data streams make ideal locations to hide information. It might be possible to insert bits in a photograph or a music file that floats around on the Internet by grabbing it and replacing it with a copy that includes your message. This works well until someone else has the same idea. Suddenly one message could overwrite another. An ideal solution is to arrange it so no one took up more than a small fraction of a channel like this one. Then, they would write their information with an error-correcting code. If two messages interacted, they would still only damage a fraction of each other's bits and the error-correcting code would be used to fix it. This is how the codes are used in many radio systems.

Of course, error-correcting codes can also help deal with errors introduced by either attackers, a noisy channel, or a format conversion. Some web sites reduce the size of images or apply subtle color corrections. In some cases, these modifications introduce only a few changes to the file and the error-correcting codes can recover them. This additional strength is hard to measure because there is no easy way to predict the damage waiting for the file.

On occasion, it makes sense to split a message into a number of different parts to be shipped through different channels. Ideally, the message could be reconstructed if a few of the parts have been compromised along the way. The part could either be lost or scrambled by a malicious courier. In either case, error-correcting codes can defend against this problem.

Better secret splitting solutions are found in Chapter 4.

A system of error-correcting codes comes in any number of flavors. Many of the most commonly used codes have the ability to carry k bits in a packet of n bits and find the right answer if no more than m errors have been made. There are many possible codes that come with different values of k, n, and m, but you never get anything for free. If you have 7 bits and you want each block to carry at least 4 bits of information, then one standard code can only correct up to one error per block. If you want to carry 6 bits of information in a 7bit block, then you can't successfully correct errors and you can only detect them half of the time.

The best metaphor for understanding error-correcting codes is to think about spheres. Imagine that each letter in a message is represented as the center of a sphere. There are 26 spheres for each letter and none of them overlap. You send a message by sending the coordinates to this point at the center. Occasionally a transmission glitch might nudge the coordinates a bit. When the recipient decodes the message, he or she can still get the correct text if the nudges are small enough so the points remain inside the sphere. The search for the best error-correcting codes involves finding the best way to pack the spheres so that you can fit the most spheres in a space and transmit the most characters.

Although mathematicians talk about sphere packing on an abstract level, it is not immediately obvious how this applies to the digital world where everything is made up of binary numbers that are on or off. How do you nudge a zero a little bit? If you nudge it enough, when does it becomes a one? How do you nudge a number like 252, which is 11111100 in binary? Obviously a small nudge could convert this into 111111101, which is 253. But what if the error came along when the first bit was going through the channel? If the first bit was changed the the number would become 011111100. That is 114, a change of 128, which certainly doesn't seem small. That would imply that the spheres really couldn't be packed too closely together.

The solution is to think about the bits independently and to measure the distance between two numbers as the number of different bits. So 11111100 and 11111101 are one unit apart because they differ in only one bit. So are 11111100 and 01111100. But 01111100 and 11111101 are two units apart. This distance is often called the Hamming distance.

This measure has the same feel as finding the distance between two corners in a city that is laid out on a Manhattan-like grid. The distance between the corner at 10th Avenue and 86th Street and the corner at 9th Avenue and 83rd Street is four blocks, although in Manhattan they are blocks of different lengths. You just sum up the differences along each of the different dimensions. In the street example, there are two dimensions that are the avenues that run north and south or the streets that run east and west. In the numerical example, each bit position is a different dimension and the 8-bit examples above have eight dimensions.

Error-correcting codes spread the information out over a number of bits in the same fashion as the spread-spectrum algorithms in Chapter 14.

The simplest example of an error-correcting code uses 3 bits to encode each bit of data. The code can correct one error in a bit but not two. There are eight possible combinations of three bits: 000, 001, 010, 011, 100, 101, 110, and 111. You can think of these as the eight corners of a cube as shown in Figure 3.1. A message 0 can be encoded as “000,” and a 1 can be encoded as “111”. Imagine there is an error and the “000” was converted into a “001”. The closest possible choice, “000”, is easy to identify.

Figure 3.1. The eight corners of the cube. The two corners, 000 and 111, are used to send the message of either 0 or 1. If there is an error in one bit, then it can be recovered by finding the closest corner.

The sphere of “000” includes all points that are at most one Hamming unit away: 001, 010, and 100. Two errors, however, nudge a point into the adjacent sphere.

Obviously, the technique can be extended into higher-dimensional spaces. The trick is to find an optimal number of points that can be packed into a space. Imagine, for instance, a five-dimensional space made up of the points 00000, 00001, 00010,…,11111. Every point has an opposite point that is five units away from it. 00000 is five steps away from 11111 and 10111 is five units away from 01000. It is easy to construct a sphere with a radius of two units around each point. That means 0 can be encoded as 00000 and 1 can be encoded as 11111. Up to two errors could occur and the correct answer would be found. 10110 is two units away from 11111, so it would fall in its sphere of influence and be decoded as a 1.

Generally, odd-dimensional spaces are much better than even-dimensional spaces for this basic scheme. Imagine the six-dimensional space created from the points 000000, 000001, 000010,…,111111. Both 000000 and 111111 are six units apart. But if you draw a sphere of radius 3 around each point, then the spheres overlap. The point 010101, for instance, is both three units away from 000000 and three units away from 111111. It's in both spheres. If you were to try and construct an error-correcting code using this arrangement, then you would only be able to fit two spheres of radius 2 in the space and the code would only be able to resist up to two errors per block. Obviously the 5-bit code in the five-dimensional space is just as error-resistant while being more efficient.

Figure 3.2. The Hamming distance shows that the corner “011” is three steps or units away from “100”. That's the longest distance in this cube.

Figure 3.3. A poor way to pack circles. If the system error can't shift the signal more than the radius of the sphere, then the space between the circles is wasted. Figure 3.4 shows a better approach.

There is no reason why you need to pack only two spheres into each space. You might want to fit in many smaller spheres. In seven-dimensional space, you can fit in two spheres of radius 3 centered around any two points that are seven units apart. But you can also fit in a large number of spheres that have a radius of only 1. For instance, you can place spheres with a single unit radius around 0000000, 0000111, 1110000, 0011001, 1001100, 1010001, and 1000101. None of these spheres overlap and the space is not full. You could also add a sphere centered around 1111110. There are eight code words here, so eight different messages or 3 bits of information could be stored in each 7-bit code word. Up to one bit error could be found and resolved.

In general, packing these higher-dimensional spaces is quite difficult to do optimally. It should be clear that there are many other points that are not in any of eight different spheres. This reflects a gross inefficiency.

“Constructing Error-Correcting Codes” on page 46 describes how to build general Hamming codes. It is possible to use the algorithm given there to construct an error-correcting code that packs 4 bits of information, or 16 different messages, into one 7-bit code word. That's one extra bit of data. The code can also resist up to 1 bit of error. The 16 centers generated by this method are:

Figure 3.4. A better approach to packing the circles from Figure 3.3. This is about 86.6% of the original height. It is wider by one half of the radius of a circle.

0000000	0001111	0010011	0011100
0100101	0101010	0110110	0111001
1000110	1001001	1010101	1011010
1100011	1101100	1110000	1111111

There are many other types of error-correcting codes. The metaphor of sphere packing is a good way to understand the basic idea, but it offers little guidance on how it can be done effectively. It is easy to imagine stacking pool balls in a rack, but it is impossible to visualize how to do this in multiple dimensions—especially if the Hamming distance is used.

In practice, error-correcting codes rest on algorithms that take the data and add extra parity bits that can be used to recover the data. The parity bits “puff up” the data into more dimensions and move the points away from each other. For instance, in four dimensions the points 1110 and 1111 are right next to each other. But if three parity bits are added to the end of each one, the results, 1110000 and 1111111, are four units apart.

If you look carefully at the table on page 43, the first four bits represent all of the possible points in a four-dimensional space. The last three bits are parity bits that were added to puff it out into seven dimensions.

The location of the parity bits varies significantly between different codes. Some codes can correct a certain number of errors that occur anywhere in a block of data. Others can correct errors that happen in bursts. They might be able to correct only one burst of errors, but that burst can contain anywhere between one flipped bit and an upper limit of k. If the errors don't occur next to each other, however, then the code can't fix the error. Each of these codes places the parity bits in different arrangements to grab different types of errors.

The rest of this book will rely on error-correcting codes to add robustness to protocols, perhaps add randomness, and provide another way to split information into a number of different parts. Using error-correcting codes is essential if information might bump into other information in the channels.

3.2.1. Error Correction and White Noise

Error-correcting codes may be intended to correct errors, but they can also be used to make a bit stream conform to some pattern. Once a collection of bits is encoded in an error-correcting code then changes can be introduced without destroying the underlying information. These changes might add randomness or, with some difficulty, make the data conform to a pattern.

In practice, the best choice for this approach is error-correcting codes that can sustain a high number of errors. A good first choice might be the 3-bit error-correcting code that conveys one bit. You write 000, 001, 010, or 100 for the 0 bit and 111, 110, 101, or 011 for the 1 bit. Any of the three are acceptable choices. This will triple the size of the file, but it will allow plenty of flexibility in rearranging the structure of the data.

Adding randomness is easy, but there are limitations to making the data fit some other pattern. Obviously the underlying data must come close enough to the pattern so that errors can be introduced successfully. In an abstract sense, the pattern must fall into the spheres. The bigger the spheres, the more patterns that can work successfully. For instance, you could easily use the 3-bit code described above to produce a bit stream that never had more than three ones or three zeros occur in a row. Each bit could be encoded with a pattern that started with a 1 or a 0. On the other hand, you could not produce a pattern that always requires that there were five ones or zeros in a row.

This technique can be taken one step further that takes it outside of the realm of error-correcting codes entirely. If you're planning to use the error-correcting codes to give you enough room to add some randomness to the data, then you're going to lose many of the error-correcting properties. For instance, one flipped bit can convert 110, a value representing 1, into 010, a value representing 0. In essence, you might want to forget about the error-correcting ability altogether and just construct a list of codes that represent each bit. 1 might be encoded as 001, 100, 011, and 111, while 0 may be encoded as 110, 101, 010, and 000. The main advantage of this approach is that the distribution of zeros and ones can be even more balanced. In the 3-bit code used as an example in this section, there are an average of 2.25 bits used to encode a 1 and .75 used to encode a 0. This means a file with a high percentage of ones, for instance, will still have a high percentage after the encoding. Using random codes assigned to each bit can remove this bias.

3.2.2. Error Correction and Secret Sharing

Error-correcting codes have a functional cousin known as secret sharing — that is, a class of algorithms that allow a file be split into m parts so that only m − k parts are necessary to reconstruct it. Obviously, an error-correcting code that could handle up to k errors in m bits would works similarly. Simply encode the file using this method and then break up the m bits into m different files.

Secret sharing is described in detail in Chapter 4.

There is one problem with this approach. Some bits are more privileged than others in some error-correcting schemes. For instance, the next section on Hamming codes describes a code that takes 11 bits and adds 4 parity bits that will correct any single error. Ideally, a file encoded with this code could be broken into 15 parts and any 14 parts would suffice to recover the data. But, there are only 11 bits of data in every block of 15 bits. The other 4 parity bits are used just to correct the errors. If the i^th bit of each block always goes in the i^th part, then the right 11 parts would suffice. The key is to distribute the bits so this never happens. Here are the steps:

1. Choose an error-correcting code that offers the right recovery properties. It is easy to find Hamming codes that recover single errors.
2. Encode the file using this technique.
3. If there are n bits in each block and n files, then place one bit from each block in each file. That is, place bit i in file i + j mod n. The choice of j should vary with each block. It can either increase sequentially or be chosen by a random number generator. If a random number generator is used, it should be a pseudo-random number generator that can be reseeded to recover the information later.

For most practical purposes, error-correcting codes are not ideal ways to share secrets. While it is easy to construct a Hamming code that can sustain one error, it is pretty inefficient to generate an error-correcting code that contains n bits per block and still survive, say, n − 2 errors. The theory is not optimized around this solution and, in fact, the approach presented in this chapter can't detect more than

errors.

A better secret-sharing technique emerges directly from geometry. Imagine that you encode a message as a point in a plane. One solution is to draw three lines through the point and distribute the lines to different people. Two lines are enough to reconstruct the point. The process can be turned into an error-correcting code just by choosing the one point that represents the largest intersection of lines. If you want to encode larger amounts of data, you can use higher-dimensional spaces and use planes or higher dimensions. This is close to what the Hamming codes are doing, but it is difficult to think in these terms when only bits are being used.

3.3. Constructing Error-Correcting Codes

[Ara88] and [LJ83] were the source for this material.

Hamming codes are easy and elegant error-correcting codes. Constructing them and using them is relatively easy. The problem can be thought of as taking your incoming message bits and then adding parity bits that will allow you to correct the errors. The net effect is to create an overdetermined collection of linear equations that can be solved in only one way.

Section 4.2 shows how to use error-correcting codes as a way to share responsibility or split a secret into multiple parts. Better algorithms follow.

The easiest way to introduce the algorithm is by constructing an example code that takes 11 bits and adds 4 new parity bits to the mix so that an error of at most one bit can be corrected if it occurs. The input bits will be a¹,…,a¹¹. The output bits are b¹,…,b¹⁵. For the purpose of illustrating the algorithm, it is easier to use binary subscripts: b⁰⁰⁰¹ through b¹¹¹¹.

The best way to illustrate the process is with a table of the output bits. The input bits are merely copied over into an output slot with a different number. This is easy to do in hardware if you happened to be implementing such an algorithm in silicon. The extra parity bits are computed by adding up different sets of the input bits modulo 2. They are found in output bits b⁰⁰⁰¹, b⁰⁰¹⁰, b⁰¹⁰⁰, and b¹⁰⁰⁰.

Table 3.1. Output Bit: Where It Comes From

b0001	a1 + a2 + a4 + a5 + a7 + a9 + a11 mod 2
b0010	a1 + a3 + a4 + a6 + a7 + a10 + a11 mod 2
b0011	a1
b0100	a2 + a3 + a4 + a8 + a9 + a10 + a11 mod 2
b0101	a2
b0110	a3
b0111	a4
b1000	a5 + a6 + a7 + a8 + a9 + a10 + a11 mod 2
b1001	a5
b1010	a6
b1011	a7
b1100	a8
b1101	a9
b1110	a10
b1111	a11

Errors are detected by calculating four formulas that will give the location of the error:

c0	= b0001 + b0011 + b0101 + b0111 + b1001 + b1011 + b1101 + b1111 mod 2
c1	= b0010 + b0011 + b0110 + b0111 + b1010 + b1011 + b1110 + b1111 mod 2
c2	= b0100 + b0101 + b0110 + b0111 + b1100 + b1101 + b1110 + b1111 mod 2
c3	= b1000 + b1001 + b1010 + b1011 + b1100 + b1101 + b1110 + b1111 mod 2

These four equations yield 4 bits. If they're combined into a single number, then they'll reveal the location of an error. For instance, imagine that bit b¹⁰¹¹ was flipped by an error. This is the incoming bit a⁷ and this bit is part of the equation that produces parity bits b¹⁰⁰⁰, b⁰⁰¹⁰, and b⁰⁰⁰¹. The pattern should be obvious. The parity bits are stuck at slots that have only a single 1 in the binary value of their subscript. A normal bit is added into the equation by examining the binary value of its subscript. If there is a 1 at position i, then it is added into the parity bit that has a 1 at position i. b¹⁰¹¹ has three 1's, so it ends up in four equations.

The effect of an error in b¹⁰¹¹ is easy to follow. b⁰⁰⁰¹ will not match the sum b⁰⁰¹¹ + b⁰¹⁰¹ + b⁰¹¹¹ + b¹⁰⁰¹ + b¹⁰¹¹ + b¹¹⁰¹. This will mean that c⁰ will evaluate to 1. The same effect will set c¹ = 1 and c³ = 1. c² will stay zero. If these are combined in the proper order, 1011, then they point directly at bit b¹⁰¹¹.

These equations also correct errors that occur in the parity bits. If one of these is flipped, only one of the equations will produces a 1. The rest yield zeros because the parity bits are not part of their equations.

The general steps for constructing such an error-correcting code for n bits can be summarized:

1. Find the smallest k such that 2^k − k − 1 ≤ n. This set of equations will encode 2^k − k − 1 bits and produce 2^k − 1 bits.
2. Enumerate the output bits with binary subscripts: b⁰⁰…⁰¹…b¹¹…¹¹.
3. The parity bits will be the output bits with a single 1 in their subscript.
4. Assign the input bits to the nonparity output bits. Any order will suffice, but there is no reason not to be neat and do it in order.
5. Compute the parity bit with a 1 at position i by adding up all of the output bits with a 1 at the same position, i, except the parity bit itself. Do the addition modulo 2.
6. To decode, compute cⁱ which is the sum of all output bits that have a 1 in position i, including the parity bit. This will yield a 0 if the parity bit matches and a 1 if it doesn't. Aggregating the cⁱ values will reveal the position of the error. This code will only detect one error.

What is the most efficient choice of k for this algorithm? Given that the number of parity bits is proportional to the log of the number of input bits, it is tempting to lump the entire file into one big block and use only a small number of parity bits. This requires a large number of additions. There are about

additions in a block of n bits. Large blocks require fewer parity bits but need more computation. They also correct only one error in the entire block and this substantially limits their usefulness. The best trade off must be based on the noisiness of the channel carrying the information.

Implementations of Hamming codes like this one are often fastest when they are done a word at a time. Most CPUs have instructions that will do a bitwise XOR of an instruction word, which is usually either 32 or 64 bits long. XOR is addition modulo 2. These fast XORs provide a good way of computing up to 32 or 64 encodings in parallel. This is done by using all of the above equations, but doing the calculations with words instead of bits and XOR instead of basic arithmetic.

This approach is a very fast way to encode the error-correcting bits and it is a quick way to detect errors, but correcting the error can be slow. Testing for errors can be done just by seeing if all of the cⁱ values are zero. If one of the cⁱ is not zero, then the code must step through each of the bits individually and compute the location of the errors. This is much slower, but not any slower than computing the code in a bitwise fashion.

The Hamming codes described in this section are particularly elegant, in my opinion, because of the way that the results of the cⁱ are aggregated to find the location of the error. This is just a result of the arrangements of the parity bits. The same basic algorithm could be used no matter what order the bits were found. Any permutation of the bits b⁰⁰⁰¹ through b¹¹¹¹ would work. The recovery process wouldn't be as elegant.

This elegant arrangement is not necessary for hardware-based implementations because the correction of the error does not need to be done by converting the cⁱ values into an index that points to the error. It is quite possible to create a set of AND gates for each bit that looks for a perfect match. This means the parity bits could be placed at the beginning or the end of each block. This might simplify stripping them out.

3.3.1. Periodic Codes

The codes described in the previous section correct only one bit error per block. This may suffice, but it can be pretty inefficient if the block sizes are small. The Hamming codes need three parity bits to correct one error in four bits. That's almost a 50% loss just to correct one bit out of four.

The Hamming codes are also less than optimal because of the nature of the noise that can corrupt digital data. The errors may not be randomly distributed. They are often grouped in one big burst that might occur after an electrical jolt or some other physical event disrupts the stream. A scratch on a CD-ROM may blur several bits that are right next to each other. These errors would destroy any Hamming solution that is limited to correcting one bit in each block.

Periodic codes are a better solution for occasions that demand detecting and recovering errors that occur in bursts. In this case, the parity bits will be distributed at regular intervals throughout the stream of bits. For instance, every fourth bit in a stream might be a parity bit that is computed from some of the previous bits. As before, the location of the parity bits can be varied if the number of parity bits per set of bits is kept constant, but it is often cleaner to arrange for them to occur periodically.

The Hamming codes are designed to work with predefined blocks of bits. The convolutional codes described here will work with rolling blocks of bits that overlap. The same convolutional technique will also work with fixed blocks, but it is left out here for simplicity. To avoid confusion, this section will use the word subblock to refer to the smaller sets of bits that are used to create the rolling block.

The periodic code will consist of a subblock of bits followed by a set of parity bits that are computed from the bits that are present in any number of the preceding subblocks. The parity might also depend on some of the bits in the following subblocks, but this configuration is left out in the interest of simplicity.

A set of bits from a convolutional code might look like this:

Here, b^(i,1) stands for the first data bit in subblock i. p^(i,1) is the first parity bit. There are five data bits and one parity bit in this example.

The parity bit could be any function of the bits in the previous subblocks. For simplicity, let

That is, each parity bit is affected by one of the bits in the previous five subblocks.

These parity bits can detect one burst of up to five bits that occurs in each rolling set of five subblocks. That means that the error will be detected if every two error bursts have at least five subblocks between them. The error, once detected, can be fixed by asking for a retransmission of the data.

The error can be detected by watching the trail it leaves in the parity bits that follow it. A burst of errors in this case might affect any of the five parity bits that come after it. When the parity bits don't match, the previous set of five subblocks can be retransmitted to fix the problem. It should be easy to see how spreading out the parity bits makes it possible for the code system to detect bursts of errors. None of the equations used to calculate the parity bits depends on neighboring bits. In this example, there are at least five bits in the bit stream between each of the bits used to calculate each parity bit. In the Hamming example, each of the parity equations depended on some adjacent bits. If both of those bits were flipped because of a burst of error noise, then the errors would cancel out and the error would be recoverable.

Section 14.4.2 describes a coding scheme that can produce the right parity values when only some of the bits can be changed, a solution that's useful when you only want to tweak the least damageable parts of an image.

Recovering a parity error is normally not possible with a simple code like this example. If one of the parity bits doesn't agree in this example, then the error could have been introduced by an error in six different bits. Finding which one is impossible. To some extent, a larger burst of errors will make the job easier. For instance, if three bits in a row are flipped, then three consecutive parity bits will also be flipped. If the parity bits are examined individually, then each one could have been caused by up to six different errors. But periodic codes like this are designed to handle bursts of errors. So it is acceptable to assume that the three errors would be adjacent to each other. This limits the location to two different spots.

For instance, here is a data stream with correct parity bits:

If the first three bits are flipped, then the first three parity bits are also flipped:

Each individual error could have occurred in any of the previous five blocks, but the overlapping nature of the code limits the error to the first block shown here or either of the two blocks that preceded it. If five bits were flipped in a row, then the exact location would be known and it would be possible to correct the errors. This pushes the code to an extreme and it would be better not to hope for bursts to come at the extreme limit of the ability of the codes to detect the errors.

Both [LJ83] and [Ara88] are good sources.

The periodic code described in this section is a good way to detect bursts of errors, but it cannot help correct them unless the burst is at the extreme. There is some information available, but it is clearly not enough to recover the data.

3.4. Summary

Error-correcting codes are one of the most important tools for building digital systems. They allow electronic designers to correct the random errors that emerge from nature and provide the user with some digital precision. If the electronics were required to offer perfect accuracy, then they would be prohibitively expensive.

These codes are useful for correcting problems that emerge from the transmission systems. It might be desirable, for instance, for several people to use the same channel. If they use a small part of the channel chosen at random, then the codes will correct any occasional collisions.

The field is also blessed with a deep body of literature exploring many different variations that lie outside of the scope of this introduction. Unfortunately this book does not have the space to consider them all nor outline the different ways that they can be more or less useful for steganography.

Chapter 14 describes spread-spectrum-like applications for hiding information. These techniques also rely on distributing the message over a relatively large number of elements in the file. If several of the elements are disturbed or mangled, these spread-spectrum solutions can still recover the message.

• The Disguise If you want to use these codes to hide information, the best solution is to tweak a small subset of bits. If each block has 8 bits, for instance, the you can send 3 bits per block. If you want to send 000, then flip bit 0. If you want to send 011, then flip bit 3, and so on. When the bits are finally read at the other end, the error-correcting codes will remove the errors and the casual reader won't even know they were there. You can use the error-correcting codes to recover them. Of course, this solution trades accuracy for steganography. Accidental or intentional errors will destroy the message. The error-correcting powers of the equation will be spent on carrying the information. Another simple solution is to encode your message by making a few small changes in a signal that is already protected by some error correction. Your message might be hide three bits (0 ≤ i < 8) by creating a fake error in bit i. This can be repeated for every error-corrected byte, a pretty good packing ratio. When someone receives the file, the regular error correction code will fix the problem effectively hiding your changes. You can strip the secret bits out by using the error-correcting algorithm to detect the changes.
• How Secure Is It? Error-correcting codes are not at all secure against people who want to read them. The patterns between the bits are easy to detect. They are quite resistant, however, against errors.
• How To Use Them? Error-correcting codes are rarely sold to consumers directly, although consumers use them all the time. Many electronic devices, however, like CD players and cell phones, rely on them. Programmers who need to use error-correcting codes should search out complete books on the topic, which is large and engaging.

Further Reading

• Shu Lin and Daniel J. Costello's book, Error Control Coding, is one of the classic treatments in the area. [LC04]
• Jessica J. Fridrich, Miroslav Goljan, Petr Lisonek and David Soukal discuss the use of Michael Luby's LT Codes as a foundation for building better versions of perturbed quantization discussed in Section 14.4.2. They are like error-correcting codes that are computed when some of the bits can't be changed. These graph-based codes can be faster to compute than matrix-based solutions.[Lub02, FGLS05]
• Wojciech Mazurczyk and Krzyszt of Szczypiorski found that Voice Over IP calls could hide information because the algorithms work around missing packets— or packets replaced with hidden messages.[MS08]