# Intro to Computer Systems

## 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 be able to put them at the beginning or the end we have to know in advance the number of data bits, and that it not always possible;
• giving them fixed positions means that we know exactly where the extra bits are.

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 Data/Parity 10 9 8 7 6 5 4 3 2 1 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:

• P1 covers bits 1, 3, 5, 7, 9, 11, 13, 15, etc.
P1 covers positions where there is a 1 in the first binary bit of the position number binary expression (highlighted in boldface): 0001, 0011, 0101, ...
• P2 covers bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, etc.
P2 covers positions where there is 1 in the second binary bit of the position number binary expression: 0010, 0011, 0110, 0011, ...
• P3 covers bits 4, 5, 6, 7, 12, 13, 14, 15, etc.
P3 covers positions where there is a 1 in the third binary bit of the position number binary expression: 0100, 0101, 0110, 0111, ...
• P4 covers bits 8, 9, 10, 11, 12, 13, 14, 15, etc.
P4 covers positions where there is a 1 in the fourth binary bit of the position number expression: 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

We can think about it in a different way:

• P1 covers bits 1, 3, 5, 7, 9, 11, 13, 15, etc.
P1 covers one bit, skips one bit
• P2 covers bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, etc.
P2 covers two bits, skips two bits
• P3 covers bits 4, 5, 6, 7, 12, 13, 14, 15, etc.
P3 covers four bits, skips four bits
• P4 covers bits 8, 9, 10, 11, 12, 13, 14, 15, etc.
P4 covers eight bits, skips eight bits

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
• P1 checks bits 1, 3, 5, 7 = ? 1 1 1, P1=1
• P2 checks bits 2, 3, 6, 7 = ? 1 0 1, P2=0
• P3 checks bits 4, 5, 6, 7 = ? 1 0 1, P3=0

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:

• If some Hamming checks fail, and there is also an overall parity error, we assume that there was a 1-bit error and we correct it as before.
• If some Hamming checks fail but there is no overall parity error, we assume that there have been 2 or more errors, and we don't correct them.

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.