Error Correcting Codes

Even and Odd Parity

If a binary number contains an even number of 1 bits, we say that it has even parity. If the number contains an odd number of 1 bits, it has odd parity.

When data must be transmitted from one device to another, there is always the possibility that an error might occur. Detection of a single incorrect bit in a data word can be detected simply by adding an additional parity bit to the end of the word. If both the sender and receiver agree to use even parity, for example, the sender can set the parity bit to either 1 or zero so as to make the total number of 1 bits in the word an even number:

8-bit data value:   1 0 1 1 0 1 0 1
added parity bit:   1
transmitted data:  1 0 1 1 0 1 0 1 1

Or, if the data value already had an even number of 1 bits, the parity bit would be set to 0:

8-bit data value:   1 0 1 1 0 1 0 0
added parity bit:   0
transmitted data:  1 0 1 1 0 1 0 0 0

The receiver of a transmission also counts the 1 bits in the received value, and if the count is not even, an error condition is signalled and the sender is usually instructed to re-send the data. For small, non-critical data transmissions, this method is a reasonable tradeoff between reliability and efficiency. But it presents problems in cases where highly reliable data must be transmitted.

The primary problem with using a single parity bit is that it cannot detect the presence of more than one transmission error. If two bits are incorrect, the parity can still be even and no error can be detected. In the next section we will look at an encoding method that can both detect multiple errors and can correct single errors.

Hamming Code

In 1950, Richard Hamming developed an innovative way of adding bits to a number in such a way that transmission errors involving no more than a single bit could be detected and corrected.

The number of parity bits depends on the number of data bits:

Data Bits :   4   8   16   32   64   128

Parity Bits:  3   4    5    6    7     8

Codeword :    7  12   21    38  71   136

We can say that for N data bits, (log₂ N)+1 parity bits are required. In other words, for a data of size 2ⁿ bits, n+1 parity bits are embedded to form the codeword. It's interesting to note that doubling the number of data bits results in the addition of only 1 more data bit. Of course, the longer the codeword, the greater the chance that more than error might occur.

Placing the Parity Bits

(From this point onward we will number the bits from left to right, beginning with 1. In other words, bit 1 is the most significant bit.)

The parity bit positions are powers of 2: {1,2,4,8,16,32...}. All remaining positions hold data bits. Here is a table representing a 21-bit code word:

The 16-bit data value 1000111100110101 would be stored as follows:

Calculating Parity

For any data bit located in position N in the code word, the bit is checked by parity bits in positions P₁, P₂, P_{3, ...,} P_k if N is equal to the sum of P₁, P₂, P_{3, ...,} P_k. For example, bit 11 is checked by parity bits 1, 2 and 8 (11 = 1 + 2 + 8). Here is a table covering code words up to 21 bits long:

Turning this data around in a more useful way, the following table shows exactly which data bits are checked by each parity bit in a 21-bit code word:

It is useful to view each row in this table as a bit group. As we will see later, error correcting using the Hamming encoding method is based on the intersections between these groups, or sets, of bits.

* Some of the hints (3rd column) only make sense for larger code words.

Encoding a Data Value

Now it's time to put all of this information together and create a code word. We will use even parity for each bit group, which is an arbitrary decision. We might just as easily have decided to use odd parity. For the first example, let's use the 8-bit data value 1 1 0 0 1 1 1 1, which will produce a 12-bit code word. Let's start by filling in the data bits:

Next, we begin calculating and inserting each of the parity bits.

P1: To calculate the parity bit in position 1, we sum the bits in positions 3, 5, 7, 9, and 11: (1+1+0+1+1 = 4). This sum is even (indicating even parity), so parity bit 1 should be assigned a value of 0. By doing this, we allow the parity to remain even:

P2: To generate the parity bit in position 2, we sum the bits in positions 3, 6, 7, 10, and 11: (1+0+0+1+1 = 3). The sum is odd, so we assign a value of 1 to parity bit 2. This produces even parity for the combined group of bits 2, 3, 6, 7, 10, and 11:

P4: To generate the parity bit in position 4, we sum the bits in positions 5, 6, 7, and 12: (1+0+0+1 = 2). This results in even parity, so we set parity bit 4 to zero, leaving the parity even:

P8: To generate the parity bit in position 8, we sum the bits in positions 9, 10, 11 and 12: (1+1+1+1 = 4). This results in even parity, so we set parity bit 8 to zero, leaving the parity even:

All parity bits have been created, and the resulting code word is: 011010001111.

Detecting a Single Error

When a code word is received, the receiver must verify the correctness of the data. This is accomplished by counting the 1 bits in each bit group (mentioned earlier) and verifying that each has even parity. Recall that we arbitrarily decided to use even parity when creating code words. Here are the bit groups for a 12-bit code value:

If one of these groups produces an odd number of bits, the receiver knows that a transmission error occurred. As long as only a single bit was altered, it can be corrected. The method can be best shown using concrete examples.

Example 1: Suppose that the bit in position 4 was reversed, producing 011110001111. The receiver would detect an odd parity in the bit group associated with parity bit 4. After eliminating all bits from this group that also appear in other groups, the only remaining bit is bit 4. The receiver would toggle this bit, thus correcting the transmission error.

Example 2: Suppose that bit 7 was reversed, producing 011010101111. The bit groups based on parity bits 1, 2, and 4 would have odd parity. The only bit that is shared by all three groups (the intersection of the three sets of bits) is bit 7, so again the error bit is identified:

Example 3: Suppose that bit 6 was reversed, producing 011011001111. The groups based on parity bits 2 and 4 would have odd parity. Notice that two bits are shared by these two groups (their intersection): 6 and 7:

But then, but 7 occurs in group 1, which has even parity. This leaves bit 6 as the only choice as the incorrect bit.

Multiple Errors

If two errors were to occur, we could detect the presence of an error, but it would not be possible to correct the error. Consider, for example, that both bits 5 and 7 were incorrect. The bit groups based on parity bit 2 would have odd parity. Groups 1 and 4, on the other hand, would have even parity because bits 5 and 7 would counteract each other:

This would incorrectly lead us to the conclusion that bit 2 is the culprit, as it is the only bit that does not occur in groups 1 and 4. But toggling bit 2 would not to fix the error--it would simply make it worse.

For an excellent introductory discussion of error-correcting codes, see Tanenbaum, Andrew. Structured Computer Organization, Fourth Edition (1999), pp. 61-64.

If you would like to learn how to construct your own error-correcting codes, here is a good explanation of the mathematics: Laufer, Henry B. Discrete Mathematics and Applied Modern Algebra. Chapter 1: Group Codes. Prindle, Weber & Scmidt, 1984.