HAMMING CODES IN DIGITAL COMMUNICATION
(n, k) linear block codes are Hamming codes. They can be produced in a systematic or non-systematic manner.
A systematic form of Hamming codes
The following conditions apply to Hamming codes in their systematic form.
1) Number of check bits, q ≥ 3
2) Codeword length, n = 2q – 1
3) Number of message bits, k = n – q
4) Minimum hamming distance, dmin = 3
5) Since dmin= 3,
The error detection capability is
dmin≥ s + 1 => 3 ≥ s + 1 => s ≤ 3 – 1 => s ≤ 2
The error correction capability is
dmin ≥ 2t + 1 => 3 ≥ 2t + 1 => 2t ≤ 2 => t ≤ 1
As a result, we can correct single-bit errors and detect two-bit errors using Hamming code.
Parity check matrix (H)
Hamming codes employ a parity check matrix (H) for encoding and decoding. A q x n parity check matrix exists for each block code (H). It's defined as
[𝐻]𝑞 x 𝑛 = [𝑃𝑇⋮𝐼]𝑞 x 𝑛 -------------------- (1)
Where PTis the Transpose of the submatrix
'I' is the Identity matrix
We have the submatrix as
By changing rows to columns, we can get the transpose of the submatrix.
[P𝑘 x 𝑞]𝑇 = [𝑃𝑇] x 𝑘
On substituting in equation (1), the parity check matrix (H) is
Non-Systematic form of Hamming Code:
It is impossible to distinguish between messages and check bits in a non-systematic block coding. They're jumbled together in the block. An example may be used to demonstrate the error detection and correction capacity of non-systematic hamming code.
Example 1
Consider the following data (message) block: 1 1 0 1. The hamming code adds three parity bits to the message bits, resulting in a mixture of the message and check bits. The positions of the check bits are listed below.
• Here p1, p2, and p3represent the parity check bits to be added. D represents the data (message) bits. Then we have
• From a check of bit positions 3, 5, and 7, the first parity bit, p1, yields even parity. They are 1, 1, and 1 respectively. As a result, p1 will be 1 to attain equal parity.
• The second parity bit, p2, examines places 3, 6, and 7. They are 1, 0, and 1 respectively. As a result, p2 will be 0 to attain equal parity.
• Locations 5, 6, and 7 are checked by the third parity bit, p3. They are 1, 0, and 1 in this case. As a result, p3 will be 0 to attain equal parity.
• The resulting 7-bit codeword generated is as below.
• Assume the code word is changed during transmission. Assume that location 5 is now 0 instead of 1. As a result, the code word received with an error is listed below.
• We must analyze the parity bits at the decoder to discover where the error arises. This is done by assigning a 1 to any parity bit that is wrong, and a 0 to the right parity bit.
• For positions 3, 5, and 7, we check p1. They are 1, 0, and 1 in this order. P1 should be 0 for even parity, however, we got p1 as 1, which is erroneous. We give p1 a score of one.
• For positions 3, 6, and 7, we check p2. They are 1, 0, and 1 in this case. P2 should be 0 for even parity, and we have also got p2 as 0, which is accurate. We give p2 a 0 value.
• We look for places 5, 6, and 7 on p3. They are 0 in this case, 0 in this case, and 1 in this case. P3 should be 1 for even parity, but we received p3 as 0, which is wrong. We give p3 a score of one.
• The binary form of the three allocated numbers is 1 0 1, which has a decimal value of 5. This indicates that the error is located at bit location 5. The 5th location bit is subsequently changed from 0 to 1 by the decoder.
• As a result, the hamming code is capable of detecting a single error. However, if multiple errors occur in a single data block, it fails.