Error Detection and Correction#

Concept#

Improve the reliability of a memory unit.

Error Detection#

• A parity bit.
• A single bit error can be detected, but cannot be corrected.

Error Correction code#

• Generates multiple parity check bits.
• The check bits generate a unique pattern, called a syndrome.
• The specific bit in error can be identified.

Hamming Code#

Construction#

$k$ parity bits are added to an $n$-bit data word with properties :

• $2^k-1\ge n+k$.
• The bit positions are numbered in sequence from $1$ to $n+k$.
• Those positions numbered as a power of $2$ are reserved for the parity bits.
• The remaining bits are the data bits.
• Each parity bit should be determine by :

$$P_i = \bigoplus\limits_{t\space \in \space S_i}D_t$$

where $P_i$ is the $i$-th parity bit and $D_t$ is the $t$-th data bit, and the set $S_i = \{\enspace x\enspace|\enspace x\in[1, n+k],\enspace x \enspace \& \enspace2^i = 1, \enspace x \neq2^i , \enspace x \in \mathbb{Z} \enspace\}$.

Here is an example :

Example (Construction)#

Success:

Consider a $8$-bit data word $11000100$, find out its hamming code.

Since we have the equation $2^k-1\ge 8+k$, so the minimum $k$ should be $4$. That means we will have four parity bits $\{P_1, P_2, P_3, P_4\}$. So the total bit number should be $n+k = 8+4 = 12$ bits.

At first, the total hamming code should look like this:

Now, we need to calculate those parity bits using the rule above, so lets first look at the table of the binary representation of each non $2^i$ number :

Thus, we can get :

$$\begin{cases} P_1 &= \bigoplus \{D_3, D_5, D_7, D_9, D_{11}\} &= \space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 \space&=0 \\ P_2 &= \bigoplus \{D_3, D_6, D_7, D_{10}, D_{11}\}&=\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space1 \space\oplus\space0 \space&=0 \\ P_4 &= \bigoplus \{D_5, D_6, D_7, D_{12}\} &=\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 &=1\\ P_8 &= \bigoplus \{D_9, D_{10}, D_{11}, D_{12}\} &=\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0&=1\\ \end{cases}$$

Finally, we can get the hamming code :

Error Detection#

When we want to check the hamming code, we will evaluate like this :

$$C_i =P_i\oplus P'_i = P_i\oplus (\bigoplus\limits_{t\space \in \space S_i}D_t)$$

Notice that the data $D_i$ now might be wrong, so the value of $P_i'$ might be different from $P_i$.

Hence, if there is no error, $\bigwedge\limits_{i=1}^k C_i = 0$. Otherwise, there might be errors, we need to correct it.

Example (Error Detection)#

Success:

Following by the above example :

Checking is there any error in the data.

So by the definition of $C_i$, we can have :

$$\begin{cases} C_1 &= \bigoplus \{P_1, D_3, D_5, D_7, D_9, D_{11}\} &= \space0 \space\oplus\space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 \space&=0 \\ C_2 &= \bigoplus \{P_2, D_3, D_6, D_7, D_{10}, D_{11}\}&=\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space1 \space\oplus\space0 \space&=0 \\ C_4 &= \bigoplus \{P_4, D_5, D_6, D_7, D_{12}\} &=\space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 &=0\\ C_8 &= \bigoplus \{P_8, D_9, D_{10}, D_{11}, D_{12}\} &=\space1 \space\oplus\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0&=0\\ \end{cases}$$

Then we can have :

$$C = C_8C_4C_2C_1 = 0000 = 0$$

Thus the hamming code is correct! No error in this data.

Error Correction#

Danger:

$! Important !$ $Hamming code can only correct one error.$

So lets simply assme that there is only one error in the code.

Now, we need to specify the error position.

By the error detection above, we have a lots of $C_i$ indicating the checking out come, we want to use this data to find what data is wrong (Causing $C_i$ to be $1$), here are two cases :

• Case 1 : Only one checking bit is 1. This may be caused by error in the specific parity bit.
• Case 2 : Multiple checking bits are 1. Then turn the sequence $C$ into decimal then we can get the wrong data bit.

Look at the following example :

Example_01 (Error Correction)#

Success:

Following by the above example :

Checking is there any error in the data, if so, fix the wrong data.

First, lets calculate the checking bits :

$$\begin{cases} C_1 &= \bigoplus \{P_1, D_3, D_5, D_7, D_9, D_{11}\} &= \space0 \space\oplus\space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space \color{red}{1} \space&=\color{red}{1} \\ C_2 &= \bigoplus \{P_2, D_3, D_6, D_7, D_{10}, D_{11}\}&=\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space1 \space\oplus\space\color{red}{1} \space&=\color{red}{1} \\ C_4 &= \bigoplus \{P_4, D_5, D_6, D_7, D_{12}\} &=\space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 &=0\\ C_8 &= \bigoplus \{P_8, D_9, D_{10}, D_{11}, D_{12}\} &=\space1 \space\oplus\space0 \space\oplus\space1 \space\oplus\space\color{red}{1} \space\oplus\space0&=\color{red}{1}\\ \end{cases}$$

Then we can have :

$$C = C_8C_4C_2C_1 = 1101 = 11_{10}$$

So not only we can know C is not zero (so there is an error), and we can also know that the error is not in the parity bit (multiple 1s), then we can correct the wrong bit in $D_{11}$ and get :

Lets look at another example :

Example_02 (Error Correction)#

Success:

Following by the above example :

Checking is there any error in the data, if so, fix the wrong data.

First, lets calculate the checking bits :

$$\begin{cases} C_1 &= \bigoplus \{P_1, D_3, D_5, D_7, D_9, D_{11}\} &= \space0 \space\oplus\space1 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space 0 \space&=0 \\ C_2 &= \bigoplus \{P_2, D_3, D_6, D_7, D_{10}, D_{11}\}&=\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space1 \space\oplus\space0 \space&=0 \\ C_4 &= \bigoplus \{P_4, D_5, D_6, D_7, D_{12}\} &=\space\color{red}{0} \space\oplus\space1 \space\oplus\space0 \space\oplus\space0 \space\oplus\space0 &=\color{red}{1}\\ C_8 &= \bigoplus \{P_8, D_9, D_{10}, D_{11}, D_{12}\} &=\space1 \space\oplus\space0 \space\oplus\space1 \space\oplus\space0 \space\oplus\space0&=0\\ \end{cases}$$

Then we can have :

$$C = C_8C_4C_2C_1 = 0100 = 4_{10}$$

So not only we can know C is not zero (so there is an error), and we can also know that the error is in the parity bit (only one 1), then we can correct the wrong bit in $P_{4}$ and get :

tags: Logic Design EECS1010#