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:
- Block diagram : n = 2m – 1
- Number of message bits : k = 2m – m – 1 …(10.13)
- Number of parity bits : (n – k) = m.
where m ≥ 3. i.e., minimum number of parity bits is 3.
- The minimum distance dmin = 3.
- 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, dmin, = 3,
- The number of errors that can be detected per word = 2.
since dmin, ≥ (s + 1) ⸫ 3 ≥ s + 1 ⸫ s ≥ 2.
- The number of errors that can be corrected per word = 1
since dmin ≥ (2t + 1) ⸫ 3 ≥ (2t + 1) ⸫ t ≤ 1
Thus, with dmin= 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 = [PT | In-k] …(10.15)
where PT = An (n – k) x k matrix representing the transpose of the coefficient matrix P and In-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.,
PT = …(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 = [Ik | P]
Comparing this with the given generator matrix, we obtain
Ik = I3 x 3 =
and P = P3×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:
[c0, c1, c2] = [m0, m1, m2] …(i)
Now, let us obtain parity words for all the message words.
The solution of equation (i) is given by,
c0 = (m0 x 0) Å (m1 x 1) Å (m2 x 1) = m1 Å m2 …(ii)
c1 = (m0 x 1) Å (m1 x 0) Å (m2 x 1) = m0 Å m2 …(iii)
c2 = (m0 x 0) Å (m1 x 1) Å (m2 x 1) = m0 Å m1 …(iv)
By substituting the values of m0, m1 and m2 into these equations, it is possible for us to obtain the parity bits c0, c1 and c2.
- For the message word (m0, m1, m2) = 0 0 0, we have
c0 =0 Å 0 = 0
c1 =0 Å 0 = 0
c2 =0 Å 0 = 0
⸫ c0 c1 c2 = (0, 0, 0)
The complete code word for this message word is given by,
diagram
- For the second message vector, i.e., (m0, m1, m2) = 0 0 1, we have
c0 = 0 Å 1 = 1
c1 = 0 Å 1 = 1
c2 = 0 Å 1 = 1
| DO YOU KNOW? |
| The two key system parameters available to the designer are transmitted signal power and channel bandwidth. These two parameters, together with the power spectral density of receiver noise, determine the signal energy per bit-to-noise power spectral density ratio Eb/N0. |
⸫ (c0, c1, c2,) = (1, 1, 0)
The complete code word for this message word is given by,
m0 m1 m2 c0 c1 c2
diagram
- 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
| S.No. | Message Vectors | Parity bits | Complete code vector |
| m0 m1 m2 | c0 c1 c2 | m0 m1 m2 c0 c1 c2 | |
| 1 | 0 0 0 | 0 0 0 | 0 0 0 0 0 0 |
| 2 | 0 0 1 | 1 1 0 | 0 0 1 1 1 0 |
| 3 | 0 1 0 | 1 0 1 | 0 1 0 1 0 1 |
| 4 | 0 1 1 | 0 1 1 | 0 1 1 0 1 1 |
| 5 | 1 0 0 | 0 1 1 | 1 0 0 0 1 1 |
| 6 | 1 0 1 | 1 0 1 | 1 0 1 1 0 1 |
| 7 | 1 1 0 | 1 1 0 | 1 1 0 1 1 0 |
| 8 | 1 1 1 | 0 0 0 | 1 1 1 0 0 0 |
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 PT matrix.
PT 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] = [PT | In-k]
where PT is (n – k) by h matrix and In-k is (n – k) x (n – k) matrix.
equation
The transpose matrix PT is given by,
PT =
Let us obtain the coefficient matrix P from PT.
The P matrix can be obtained by interchanging the rows and columns of the transposed matrix PT.
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 = [Ik | P]
where Ik 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, [c0, c1, c2]1 x 3 = [m0 m1, m2 m3]1×4 [P]4×3
Therefore, [c0, c1, c2]1 x 3 = [m0 m1, m2 m3]
Solving, we obtain
c0 = (m0 x 1) Å (m1 x 1) Å (m2 x 1) Å (m3 x 0)
c1 = (m0 x 1) Å (m1 x 1) Å (m2 x 0) Å (m3 x 1)
c2 = (m0 x 1) Å (m1 x 0) Å (m2 x 1) Å (m3 x 1)
Simplifying the equations, we obtain
c0 = m0 Å m1 Å m2
c1 = m0 Å m1 Å m3 …(10.18)
c2 = m0 Å m2 Å m3
Using these equations, we can obtain the parity bits for each message vector. For example, let the message word be,
m0 m1 m2 m3 = 0 1 0 1
Then, we have c0 = 0 Å 1 Å 0 = 1
c1 = 0 Å 1 Å 1 = 0
c2 = 0 Å 0 Å 1 = 1
Hence, the parity bits are b0 b1 b2 = 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
| Sr. No. | Message Vector M m0 m1 m2 m3 |
Parity bits B c0 c1 c2 |
Code Words X x0 x1 x2 x3 x4 x5 x6 |
Weight of the code vector |
| 1 | 0 0 0 0 | 0 0 0 | 0 0 0 0 0 0 0 | 0 |
| 2 | 0 0 0 1 | 0 1 1 | 0 0 0 1 0 1 1 | 3 |
| 3 | 0 0 1 0 | 1 0 1 | 0 0 1 0 1 0 1 | 3 |
| 4 | 0 0 1 1 | 1 1 0 | 0 0 1 1 1 1 0 | 4 |
| 5 | 0 1 0 0 | 1 1 0 | 0 1 0 0 1 1 0 | 3 |
| 6 | 0 1 0 1 | 1 0 1 | 0 1 1 0 0 1 1 | 4 |
| 7 | 0 1 1 0 | 0 1 1 | 0 1 1 0 0 1 1 | 4 |
| 8 | 0 1 1 1 | 0 0 0 | 0 1 1 1 0 0 0 | 3 |
| 9 | 1 0 0 0 | 1 1 1 | 1 0 0 0 1 1 1 | 4 |
| 10 | 1 0 0 1 | 1 0 0 | 1 0 0 1 1 0 0 | 3 |
| 11 | 1 0 1 0 | 0 1 0 | 1 0 1 0 0 1 0 | 3 |
| 12 | 1 0 1 1 | 0 0 1 | 1 0 1 1 0 0 1 | 4 |
| 13 | 1 1 0 0 | 0 0 1 | 1 1 0 0 0 0 1 | 3 |
| 14 | 1 1 0 0 | 0 1 0 | 1 1 0 1 0 1 0 | 4 |
| 15 | 1 1 1 0 | 1 0 0 | 1 1 1 0 1 0 0 | 4 |
| 16 | 1 1 1 1 | 1 1 1 | 1 1 1 1 1 1 1 | 7 |
We know that the minimum distance dmin is equal to the minimum weight of any non-zero code vector. Looking at table 10.5, we obtain
dmin = 2 Ans.
Number of errors that can be detected is given by
dmin ≥ 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
dmin ≥ 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 (c2, cl, c0) are being generated for each message word (m3, m2, m1, m0) 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