Intro to Computer Systems

Chapter 5: Memory & Hamming/SECDED Codes

Coding Schemes

Hamming Codes

In the general case, the way we add those bits is up the scheme used. The most popular one is the Hamming code. In the Hamming code the number of Parity/Check bits p must be:

2p ≥ m + p + 1

where m = number of data bits and p = number of check bits.

An example:

Find the number of check bits required to detect and correct a single bit error in the BCD code for 910 = 10012

As a guess we can try p = 2 then 2p = 22 = 4, but since 4 + 2 + 1 = 7 and 4 is not ≥ 7, p = 2 is not enough.

However, if we now try p = 3 then 2p = 23 = 8 and m + p + 1 = 4 + 3 + 1 = 8. Therefore p = 3 is sufficient.

A Hamming code includes several parity bits, to be able to detect and correct 1-bit errors. In principle the parity bits may go in many different places, but the most common use is interspersed with the data bits, because:

To get the position of the check bits we count the bits from right to left (i.e. LSB to MSB) starting from 1, and the check bits are at positions 1, 2, 4, 8, 16, 32, etc, all powers of 2. All the other bits are data bits, part of the message.

Bit Position
10
9
8
7
6
5
4
3
2
1
Data/Parity
D6
D5
P4
D4
D3
D2
P3
D1
P2
P1

The table above is an example of Hamming code for 6 data bits (P = parity bit, D = data bit).

The scheme works by using each check bit as a parity bit for a specific group of bits, as follows:

We can think about it in a different way:

An example: determine the single bit error-correcting Hamming code for the data 10112. Use EVEN parity. From the formula we can see that p = 3 is sufficient, so we can write:

7
6
5
4
3
2
1
1
0
1
1

Therefore the final code is 1 0 1 0 1 0 1.

The idea is that the parity bits cover each bit (data and parity) with a unique pattern, that is each bit (including the parity bits) is covered by a unique combination of parity bits. For example, bit 5 is covered by bits P1 and P3 only and exclusively, and bit 4 is covered by P3 exclusively.

Then, if we check and find a parity error on bits P1 and P3, but no other parity errors, we know that the problem is with bit 5. So, if bit 5 is a 1, we change it to 0, and if it is a 0 we change to 1 to correct the symbol.

Why Only One-Bit Errors?

It may be surprising that we are only interested in 1-bit errors, but in computer operation 2-bit errors are very, very unlikely. If the probability of a 1-bit error is of the order of 10-9, that is 1/1,000,000,000, this is really small, but if a computer makes 10,000,000 moves a second, on average you get an error every 100 seconds = less than
2 minutes.

However, since these communications are most likely parallel, 2-bit errors occur when there is one error on two lines at the same time. That is, the probability is the product of the two probabilities 10-18. With the same computer you get a 2-bit error once every 1011 seconds = once every 3,171 years.

There may be other considerations, specifically to do with data communications. It is quite common to establish communications over noisy lines, for example, and then the probability of errors increase dramatically. It often happens that there is a short period when may be multiple-bit errors, and it would be impracticable to use a Hamming code in this situation. Other schemes more appropriate to this problem are used instead.

SECDED Coding

The ability of a Hamming code to correct an error is based on the assumption that only one bit has changed. Changes of two or more bits either are not going to be detected, or will give a false indication of which bits are in error. A common scheme to improve on the situation is called SECDED Coding (single-error correct, double-error detect), which makes possible the correction of single-bit errors and the detection, but not correction, of double-bit errors.

The original Hamming code is extended by using the unused P0 bit as a parity (odd or even) bit for all the bits in the transmitted symbol. In this way, if one bit is in error, the Hamming checks will fail for a particular set of bits, and also the overall parity will be wrong.

We may then assume that there has been a 1-bit error and the Hamming code can correct it. If 2 bits are in error, some Hamming checks will fail but the overall parity will be right, indicating that more that 1 bit was in error but this time we are not able to correct it.

Summarising, using SECDED coding:

Of course, is there have actually been more than 2 errors, the SECDED scheme will give a wrong result. As we have discussed, this is very unlikely.