32 bit or 64 bit words are common, but for illustration purposes, we will use our 7 bit word from the example above, without the parity bit. We need to calculate the extra parity bits to write into memory along with the data bits, at the appropriate bit positions.

101 1010 becomes

1-0-1 C4-1-0-1 C3-0-c2-c1

The new check bits are used to generate parity for their appropriate bits. C1 checks each alternate bit, C2 checks each alternate 2 bits, C3 checks each alternate 4 bits, C4 checks each alternate 8 bits.

101 C101 C0CC
1=1 =1=1 =0=C - C1 is a 1 to make odd parity
10= =10= =0C= - C2 is a 1 to make odd parity
=== =101 C=== - C3 is a 1 to make odd parity
101 C=== ==== - C4 is a 1 to make odd parity

Thus the ECC (Error Correction Code) is 1111, and the word becomes

101 1101 1011

Just for security we can add a parity bit for this new word (can't be too careful!)

1101 1101 1011 The overall parity bit is not considered in the coding.

This word, which has grown from 7 bits to 12 bits can now be written to memory. When we need to read the data from memory we can check the bit pattern to see if we have a problem. For example suppose bit 7 in our word has dropped, and is now 0. Once again we generate the ECC to compare with the one we stored. The word we read out is now

1101 0001 0011 - the parity bit is incorrect, showing even parity. The ECC we read out is 1111 (same as we wrote). Generate the new ECC.

101 C001 C0CC
1=1 =0=1 =0=C - C1 is 0 to make odd parity
10= =00= =0C= - C2 is 0 to make odd parity
=== =001 C=== - C3 is 0 to make odd parity
101 C=== ==== - C4 is 1 to make odd parity

Our new ECC is 1000, while the one we read out was 1111. We now perform an XOR (eXclusive OR) of these two ECCs. This means, where we have a 1 bit in one bit position, but not both, the result is a 1.

1111 - read out
1000 - generated
---- - XOR
0111 - result - C4=0, C1-3=1

The result is called the Error Syndrome, and is used to correct the failing bit. In this case we have bits C1, C2, and C3 = 1. This gives us decimal 1+2+4=7. The seventh bit is flipped from 0 to 1, restoring the original data. The ECC bits are stripped off and the data bits passed on.

Like all error detection systems, the more logic you add, the more potential there is for something to go wrong! Sometimes the problems are in the error detection logic, and not the data. This system detects errors in the check bits, as well as the data bits! It will correct a single bit error, and detect but not correct multiple errors.

Tony is an experienced computer engineer. He is currently webmaster and contributor to http://www.what-why-wisdom.com A set of diagrams accompanying these articles may be seen at http://www.what-why-wisdom.com/history-of-the-computer-0.html RSS feed also available - use http://www.what-why-wisdom.com/Educational.xml