Hamming Code
->Hamming code was invented by Richard W Hamming in 1950 for error correction. There are two types of coding in one linear coding and another one is non-linear coding, it belongs to linear coding and feature of linear code is that it has not much complex encoding and decoding system but in non-linear coding system it has very complex structure.
->Hamming codes are useful in single or double bit flipped errors and in that also it can correct only one error and detect another error. For that it use basic parity methods .It include encoding and decoding two main function to secure or correct the data.
1. Linear Hamming Method:
# Basic Notation:
->The hamming code is generally represented as (n,k) code; where n is the number of total bits that include parity and data bits and k is the number of data(information) bits.
->Relation between n and k is :
2^k >= n + k + 1
->By that formula, we can calculate the number of parity bits required for a fixed number of bits. For example,for a (7,4) code we need 3 parity bits and for a (11,7) code we need 4 parity bits. These numbers can be verified by the above formula.
# Encoding of Hamming codes :
-> We can divide this process in to three steps,
Step 1 : Calculation of the number of parity bits.
->In the above formula of n and k we can how many parity bits you have to choose by
r = n-k.
->For example (7,4) there are three parity bits. so if you have 4 bit of information code then you have attach 3 more bit (parity bit) at particular place so it is able to correct error.
Step 2 : Positioning the parity bits.
->In this section we arrange the parity bit at some decided place such that at the time of the decoding process, we do some mathematical operations and find error bits. Hamming did all arrangements and then he concluded by saying that all parity bits will be placed at the power of two, like 1,2,4,8.....and more.
For example:
Positioning of parity bits (7,4)
->Just like shown in image we have to start calculating position of any message from the end. and also parity will always place at position like 1,2,4,8,16.... because of this codes properties.
Step 3 : Calculate the value of each parity bit.
->Now, we decide the value of parity according to parity types. We have two types of parity: 1) Even parity and 2)Odd parity. First, you have to count the number of 1s in the binary code and then you can apply any of the two, odd parity or even parity. In even parity, if the number of 1s is odd, the parity bit is 1, and if the number of 1s if even, the parity bit is 0. The odd parity method works vice-versa. We generally use the even parity method in hamming code.
->Now, to decide which information bit to use for a particular parity bit, we follow a simple rule. Each parity bit covers all bit positions whose binary representation includes a 1 in the i th position except the position of ri.
For example, for a (7,4) code the parity bits are calculated like:
P1=D7⊕ D5⊕ D3
P2 = D7⊕ D6⊕ D3
P4 = D7⊕ D6⊕ D5
Let’s take one example:
->We have message of length seven(7) so now we have (11,7) hamming coding that has information "10011001" .So it also include 4 parity bit that will include in the original data so encoded data’s size will be 11.
To get parity value we have formula of four parity bits :
P1=D3⊕ D5⊕D7⊕D9⊕D11
P2 = D3⊕ D6⊕D10⊕D11⊕D7
P3= D5⊕ D6⊕ D7
P4=D9⊕D10⊕D11
Now we can follow the below steps for encoding.
Encoding Diagram
->The above image explains to you about each and every xor operation that happened for each parity.
->After that we can say that the final encoded message is :
Final Encoded Message
#Decoding of hamming codes:
->In the decoding, you have to do two main steps: first- identify if there is any error or not and second locate the error-bit and correct it. Hamming code can maximum detect a maximum of two errors and correct one error.Thus, with the use of parity, we can find one error. Finding the check bits follows the same mathematical algorithm as finding the parity bits. You can see the check bits for a (7,4) hamming code in the below image:
C1=D7⊕D5⊕D3⊕D1
​
C2=D7⊕D6⊕D3⊕D2
​
C3=D7⊕D6⊕D5⊕D4
​
Formula for decoding
->From the above expressions you can check whether there is any error or not. If there is an error, the check bits give us the index of error and if no error is present the result is 0.
For example :Our encoded code is "1001111" so for this:
"110" = 6th position from back
->Thus, from this we can say that "110" is the place where the error has occurred. Therefore the actual code is "1101111" which was encoded by the machine. That’s how data decoding works and it is very useful for the detection and correction of single-bit error.
2. Hamming code with the help of table(matrix) :
#.One bit error:
->This method is only a 2-D version of linear hamming code. Its basic function is similar to the linear codes. Follow the below pictures carefully and you will understand the process:
Binary: 11110111110
->In this type of code we have to calculate parity first. So, we are arranging the information bits in a 4x4 matrix in such a way that they do not occupy the positions for parity bits
(power of two).
After arranging :
->In this matrix we have two choices for choosing the value of parity. You have to decide whether you want odd parity or even parity. For now, we are working on even parity. In that, we have to count 1 in the block of bits and choose parity accordingly. For example, the number of 1s is odd so parity is 1. Thus p1 became 1.
->In the above image we can see that there is a shaded blue part. Those are parity spots and we have to decide the value for them. So you have to go two columns and two rows at a time for deciding parity. We compute four local parities and one global parity.
Step 1 : second and fourth columns:
->Here, we are selecting parity value 1 as we are following the even parity method.
Step 2 : third and fourth columns:
->Now, the parity value is 0 from the 3 rd and 4 th column, following the even parity method..
Step 3 : second and fourth row:
->Now, the parity value is 0 from the 2 nd and 4 th row.
Step 4 : third and fourth row:
->Now, the parity value is 1 from the 3 rd and 4 th row.
Step 5 : Global parity:
->For finding the global parity, find the parity bit according to all the remaining 15 bits. In this example, we are considering the global parity bit as 1 following the even parity method.
This binary table is encoded successfully and it is transmitted. Now suppose, that there is one error due to noise and cosmic-ray in communication technology as marked red in the figure:
->Hamming codes can also find the error. It follows the below mentioned techniques:
1->Logical-Methods:
->In this method, we go column by column and row by row. So, you check the second and fourth columns. Does it have an odd parity? In our example "NO" then C0=0;
->After that you check the third and fourth columns. Does it have odd parity? In our example "YES". Thus, C1=1.
->Similarly, you check the second and fourth rows. Do they have odd parity? In our example "NO"; so, C2=0.
->Finally, check the third and fourth rows. Does it have odd parity? In our example "YES", thus C3=1.
->Now arrange C0,C1,C2 and C3 as [C3C2C1C0]. In our example, we can say that it is [1010] which means that the 10th box i.e. (3,3) element in the matrix has an error. You can correct the error and get your original message.
2-> Exor method:
->You have to get that one-bit location which has one and after collecting all indexes as shown in the image you will find either zero or any non-zero number, If you get zero, then it means there is no error and if you get any non-zero number then that number shows you the index containing the bit which has an error. So here by example, you get indexes (0000,0001,0011,0101,0110,0111,1000,1011,1100,1101,1110) and exor all of them. You will get (1010) which shows the position of the error.
#.Two-bit error:
->If you have a two-bit error, in that case, you will find that for our example, the total number of 1s remains the same. So you might think there is no error. But in that case, you also have to check for columns by columns and row by row. and you will found that there is no match with even parity of that row or columns, In that case, you can say that it has two-bit error. Let’s take one example in which you have to find the number of errors:
-> In above image you found that total no of 1 is even so you think it has no error, but if you look at second and fourth columns, third and fourth columns ,second and fourth row and third and fourth row, you will find that number of 1 is odd .This is contrary to the fact that there are even numbers of 1s in total. This indicates that there is a Two-bit error.
->Drawback of this theorem is that you can’t find second bit error location you can only find one bit error location.