Hamming codes - Free MCQ Practice Test with solutions, GATE ECE Engineering

Convolution codes

• Convolution codes are generally error-detecting codes 
• They are comprised of parity bits with the message bits
• In convolution coding, k number of message bits are encoded continuously with m number of parity bits to have an overall sequence of n bits
• Linear matrix is not used to represent convolution code

The convolution code is generally represented by

• State diagram
• Logic tables
• Tree diagram
• Trellis diagram
• Generator polynomial 
• Generator matrix

Hence the correct option is 4

To represent the 4-bit code 1101 into a 7-bit, even parity Hamming code, we first need to add 3 parity bits to the 4 data bits. The parity bits are chosen so that the total number of 1's in each group of bits (including the parity bit) is even.
Hamming Code:

Given data 1101
i.e. d1 = 1, d2 = 1, d3 = 0, d4 = 1
We can write:
P1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1
P2 = d1 ⊕ d4 ⊕ d3 = 1 ⊕ 1 ⊕ 0 = 0
P3 = d2 ⊕ d4 ⊕ d3 = 1 ⊕ 1 ⊕ 0 = 0
Then transmitted final code is P1 P2 d1 P4 d2 d3 d4 which is 1010101

Given code words are: 11001011 and 10000111
Hamming distance can also be calculated by taking XOR of two code words.

The number of 1’s in XOR result is 3
∴ Minimum Hamming distance is 3 only 

Hamming code:
Hamming codes are linear block codes. The family of (n, k) hamming codes for q ≥ 3 is defined by the following expressions:

1. Number of Block diagrams (n) = 2q – 1
2. Number of message bits (k) = 2q – q – 1
3. Number of Parity bits (q) = (n – k)
Hamming code is a set of error-correction codes that can be used to detect and correct '1' bit errors that can occur when the bitstream is sent through the channel. It can be employed in both burst and signal error correction. 

The minimum bits change between any valid Hamming codes is 3.
Analysis:
The change of bits between the given code: 0001011 and option C code: 0011010 is two bits change only.
So 0011010 can’t be a valid Hamming code of the same group.

Given:
Error detected = 2 = s
Error corrected = 1 = t
From(1),
d_min ≥ 3
From(2),
d_min ≥ 3
We need to find for both correction and detection and hence, 
Using formula (3)
d_min ≥ t + s + 1
d_min ≥ 2 + 1 + 1
d_min = 4

Hamming (7, 4) code: It is a linear error-correcting code that encodes four bits of data into seven bits, by adding three parity bits.
Example: It is used in the Bell-Telephone laboratory, error-prone punch caret reader to detect the error and correct them.
Hamming code:

P₁ = d₁ ⊕ d₂ ⊕ d₄
P₂ = d₁ ⊕ d₄ ⊕ d₃
P₃ = d₂ ⊕ d₄ ⊕ d₃

Given data 1101 i.e.
d₁ = 1, d₂ = 1, d₃ = 0, d₄ = 1
We can write:
P₁ = d₁ ⊕ d₂ ⊕ d₄ = 1 ⊕ 1 ⊕ 1 = 1
P₂ = d₁ ⊕ d₄ ⊕ d₃ = 1 ⊕ 1 ⊕ 0 = 0
P₃ = d₂ ⊕ d₄ ⊕ d₃ = 1 ⊕ 1 ⊕ 0 = 0
Then transmitted final code is

i.e. 1010101
Option 3 correct.

• A linear code is an error correcting code.
• Any linear combination of codewords is also a code word.
• A Hamming code (7, 4) = (n, k) can correct any single bit error. 4-bit data is encoded with 7-bit code-word
• Hamming distance is the distance between the code-words. 
• The minimum distance tells us how many errors can be corrected. 

0010 = (0001) ⊕ → EXOR (0011)
To get the code word, Exor the two code words.
(0000111) ⊕ (1100110)
= 1100001

Let d = (d₁, d₂ …. d_k)
Codeword C can be written as:

C_d = d₁
C₂ = d₂
C₃ = d₃
⋮
C_k = d_k

Note: The parity bits are generated by a linear combination of message bits.
Application:
Given (7, 4) linear Hamming code.
(m_i, c_i) given are:
(1100 ; 0101100)
(1110 ; 0011110)
(0110 ; 1000110)
Clearly, we can observe that the first 3 bits are parity bits and the last 4 bits are message bits.

Observe when P₀, P_1, and P₂ are one, and write their combination, i.e.
P₀ = d₀ ⊕ d₁ ⊕ d₃
P₁ = d₁ ⊕ d₂ ⊕ d₃
P₂ = d₀ ⊕ d₁ ⊕ d₂
Now checking each of the options:
Option (1): 1011010
Message bits are:

P₀ = d₀ ⊕ d₁ ⊕ d₃ = 1
P₁ = d₁ ⊕ d₂ ⊕ d₃ = 1
P­₂ = d₀ ⊕ d₁ ⊕ d₂ = 0
So, the codeword is 1101010.
Hence option (1) is invalid codeword.
Option (2): 0110100
Message bits are:

P₀ = d₀ ⊕ d₁ ⊕ d₃ = 1
P₁ = d₁ ⊕ d₂ ⊕ d₃ = 1
P­₂ = d₀ ⊕ d₁ ⊕ d₂ = 1
So, the valid codeword is 1110100
Hence option (2) is an invalid codeword.
Option (3): 0001011
Message bits are:

P₀ = d₀ ⊕ d₁ ⊕ d₃ = 0
P₁ = d₁ ⊕ d₂ ⊕ d₃ = 0
P₂ = d₀ ⊕ d₁ ⊕ d₂ = 0
So the valid codeword is 0001011
Hence option (3) is a valid codeword.

Concept: Hamming distance gives minimum positions at which the corresponding symbols are different.
Calculation: Fixed length code n = 5
Minimum harming distance d min = 2
Hamming distance gives minimum positions at which the corresponding symbols are different.
The table shows all possible codewords having a minimum hamming distance of 2.

Hence there are 16 such codes where minimum Hamming distance 2 is possible.