Hamming Codes in Digital Communication

HAMMING CODES

(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 = 2^q – 1

3) Number of message bits, k = n – q

4) Minimum hamming distance, d_min = 3

5) Since d_min = 3,

The error detection capability is

d_min ≥ 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 P^T is 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 p₁, p_2, and p₃represent 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.