hamming code explained , what is HAMMING CODES , formula , pdf calculator , in c , c++ , java

what is HAMMING CODES , formula , pdf calculator , in c , c++ , java hamming code explained :-
HAMMING CODES
Hamming codes are linear block codes. The family of (n, k) Hamming codes for m > 23 is defined by the following expressions:

1. Block diagram : n = 2^m – 1
2. Number of message bits : k = 2^m – m – 1         …(10.13)
3. Number of parity bits : (n – k) = m.

where m ≥ 3. i.e., minimum number of parity bits is 3.

4. The minimum distance d_min = 3.
5. The code rate or code efficiency=  …(10.14)

If m >> 1, then code rate r  1.
The general structure of Hamming code word is shown in figure 10.19.
diagram
FIGURE 10.19 Code word structure of Hamming code.
10.12.1. Error Detection and Correction Capabilities of Hamming Code
(U.P. Tech. Sem. Exam. 2005-06) (10 marks)
Considering table 10.3 for the minimum distance, we have, d_min, = 3,

1. The number of errors that can be detected per word = 2.

since d_min, ≥ (s + 1)   ⸫ 3 ≥ s + 1    ⸫ s ≥ 2.

2. The number of errors that can be corrected per word = 1

since d_min ≥ (2t + 1)  ⸫ 3 ≥ (2t + 1)   ⸫ t ≤ 1
Thus, with d_min= 3, it is possible to detect upto 2 errors and it is                                           possible to correct upto only 1 error.
There is another way of expressing the relationship between the message bits and the parity check bits, of a linear block code. Let H denote an (n – k) x n matrix defined as under :
H = [P^T | I_n-k]                                       …(10.15)
where P^T = An (n – k) x k matrix representing the transpose of the coefficient matrix P and I_n-k is an (n – k) x (n – k) identify matrix.
The transpose of the coefficient matrix can be obtained by interchanging the rows and columns of the coefficient matrix P given by equation (10.9), i.e.,
P^T =                      …(10.16)
Therefore, the matrix H is given by,
equation
The matrix H is called as the parity check matrix. If generator matrix G has been given then we can obtain the parity check matrix and vice-versa.
EXAMPLE 10.5. The generator matrix for a (6, 3) block code is given below. Find all the code vectors of this code.
G =
Solution : The general pattern of the block codes is (n, h), hence, in this case, n = 6 and k= 3. This means that the message block size k is 3 and the length of code vector i.e. n is 6. For obtaining the code vectors, we shall follow the steps given below :
(i)         First, we separate out the identity matrix I and coefficient matrix
We know that the generator matrix is give by :
G = [I_k | P]
Comparing this with the given generator matrix, we obtain
I_k = I_{3 x 3} =
and                              P = P_3×3 =
As the size of message block is k = 3, there are eight possible message blocks : (0, 0, 0) (0, 0, 1), (0, 1, 0), (0, 1,1) (1, 0, 0), (1, 0, 1), (1,,1, 0), (1, 1, 1).
Now, let us obtain the relation between parity vectors B, message vectors M and the coefficient matrix P as under:
[c₀, c₁, c₂] = [m₀, m₁, m₂]                           …(i)
Now, let us obtain parity words for all the message words.
The solution of equation (i) is given by,
c₀ = (m₀ x 0) Å (m₁ x 1) Å (m₂ x 1) = m₁ Å m₂                       …(ii)
c₁ = (m₀ x 1) Å (m₁ x 0) Å (m₂ x 1) = m₀ Å m₂                       …(iii)
c₂ = (m₀ x 0) Å (m₁ x 1) Å (m₂ x 1) = m₀ Å m₁                       …(iv)
By substituting the values of m₀, m₁ and m₂ into these equations, it is possible for us to obtain the parity bits c₀, c₁ and c₂.

1. For the message word (m₀, m₁, m₂) = 0 0 0, we have

c₀ =0 Å 0 = 0
c₁ =0 Å 0 = 0
c₂ =0 Å 0 = 0
⸫                                                  c₀ c₁ c₂ = (0, 0, 0)
The complete code word for this message word is given by,
diagram

2. For the second message vector, i.e., (m₀, m₁, m₂) = 0 0 1, we have

c₀ = 0 Å 1 = 1
c₁ = 0 Å 1 = 1
c₂ = 0 Å 1 = 1

⸫         (c₀, c₁, c₂,) = (1, 1, 0)
The complete code word for this message word is given by,
m₀ m₁ m₂ c₀ c₁ c₂
diagram

3. Similarly, we can obtain the code words for the remaining message words. All these code words have been given in Table 10.4.

 
Table 10.4 Code vectors for (6, 3) block code

 
Now let us obtain the code words for a (7, 4) Hamming code.
EXAMPLE 10.6. The parity check matrix of a particular (7, 4) lienar block code is given by,
[H] =
            (i)         Find the generator matrix (G).
            (ii)        List all the code vectors
            (iii)       What is the minimum distance between the code vectors ?
            (iv)       How many errors can be detected? How many errors can be corrected?
Solution : First, let us obtain the P^T matrix.
P^T is the transpose of the coefficient matrix P. The given parity check matrix H is (n – k) x n matrix.
It is given that the code is (7, 4) Hamming code. Therefore, we have
n = 7 and k = 4
Hence, the parity check matrix [H] will be 3 x 7 matrix i.e.,
[H] = [P^T | I_n-k]
where P^T is (n – k) by h matrix and I_n-k is (n – k) x (n – k) matrix.
equation
The transpose matrix P^T is given by,
PT =
Let us obtain the coefficient matrix P from P^T.
The P matrix can be obtained by interchanging the rows and columns of the transposed matrix P^T.
We have                                  P =
Let us add the identity matrix to P matrix to get generator matrix
The generator matrix G is a k x n matrix. So, here, it will be a 4 x 7 matrix.
Thus, we have                                     G = [I_k | P]
where I_k is a k x k i.e. 4 x 4 matrix.
Substituting the 4 x 4 identity matrix and the coefficient matrix, we obtain,
equation
This is the required generator matrix
Now, let us obtain the parity bits for each message vector.
The parity bits can be obtained by using the following expression :
C = MP
Therefore, [c₀, c₁, c₂]_{1 x 3} = [m₀ m₁, m₂ m₃]_1×4 [P]_4×3
Therefore, [c₀, c₁, c₂]_{1 x 3} = [m₀ m₁, m₂ m₃]
Solving, we obtain
c₀ = (m₀ x 1) Å (m₁ x 1) Å (m₂ x 1) Å (m₃ x 0)
c₁ = (m₀ x 1) Å (m₁ x 1) Å (m₂ x 0) Å (m₃ x 1)
c₂ = (m₀ x 1) Å (m₁ x 0) Å (m₂ x 1) Å (m₃ x 1)
Simplifying the equations, we obtain
c₀ = m₀ Å m₁ Å m₂
c₁ = m₀ Å m₁ Å m₃                                                …(10.18)
c₂ = m₀ Å m₂ Å m₃
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be,
m₀ m₁ m₂ m₃ = 0 1 0 1
Then, we have                         c₀ = 0 Å 1 Å 0 = 1
c₁ = 0 Å 1 Å 1 = 0
c₂ = 0 Å 0 Å 1 = 1
Hence, the parity bits are b₀ b₁ b₂ = 1 0 1
Therefore, the complete code word for the message word 0 1 0 1 is
diagram
Similarly, we can obtain the code words for the other message vectors. All these message vectors and the corresponding parity bits and code words are given in table 10.5. The weight of the code word is also given.
Table 10.5. Code words for the (7, 4) Hamming code

 
We know that the minimum distance d_min is equal to the minimum weight of any non-zero code vector. Looking at table 10.5, we obtain
d_min = 2 Ans.
Number of errors that can be detected is given by
d_min ≥ s + 1
3 ≥ s +1
or                                                         s ≤ 2
Hence, at the most two errors can be detected.
Number of errors that can be corrected is given by
d_min ≥ 2t + 1
or                                                         3 ≥ 2t + 1
or                                                         t ≤ 1
This means that at the most one error can be corrected.
Thus, for the (7, 4) linear block code, at the most two errors can be detected and at the most only one error can be corrected.
10.12.2. Encoder of (7, 4) Hamming Code
            The encoder for (7, 4) Hamming code is shown in figure 10.20. This encoder produces all the code words corresponding to various message words listed in table 10.4.
The parity or check bits (c₂, c_l, c₀) are being generated for each message word (m₃, m₂, m₁, m₀) with the help of equation 10.18. The parity bits are obtained from the message bits by means of modulo-2 adders*. The output switch S is first connected to the message register to transmit all the message bits in a code word. Then it is connected to the parity hit register to transmit the corresponding parity bits. Thus, we get a 7 bit code word at the output of the switch.
diagram
FIGURE 10.20 Encoder for (7, 4) Hamming code