GATE CSE 1992 | Question: 01,ii

Question

Consider a $3$-bit error detection and $1$-bit error correction hamming code for $4$-bit data. The extra parity bits required would be _____ and the $3$-bit error detection is possible because the code has a minimum distance of _______.

Comments

suryakumarus The extra parity bits required would be _____ 
“Extra” means how many parity bits must be added to the 4-bit data.
For 4-bit data, the Hamming code itself requires 3 parity bits.
The question is not saying extra beyond Hamming.

---

@Ꭾʀιɴᴄᴇ the standard hamming code have only min. hamming distance of 3 only, then how can we detect 3 bit error.

pease read my answer ,I have also given resourse to refer(wiki). 

if question is intent to ask the total number of parity bit then answer would be [4,4].but from my understanding it is asking the extra parity bit in addition to the  already 3 bits parity bit in the standard hamming code

I think the question is clearly targeting the extended hamming code ,as I mentioned in answer

---

To correct a single bit error , min no of parity bits required are given by the formula 2^r >= m+r+1 (Here r is the number of parity bits and m is the number of data bits) . The formula is based on the fact that for r parity bits there are 2^r combinations (0 or 1 for each position) and the single bit error can occur anywhere in the codeword (m+r) or may not occur at all (m+r+1) . So for each combination of parity bits the error occurs at a particular position . So 2^r >= m+r+1

so 2^r >= 4+r+1

2^r >= 5+r ==> From here we get that r should be 3 (8 >= 8)

so extra parity bits should be 3.

To detect a 3 bit error minimum hamming distance should be 3+1=4

So the answer is (3,4)

Answer 1

The Hamming distance between two-bit strings is the number of bits that would have to be flipped to make the strings identical.

To detect $d$ errors we require a minimum Hamming distance of $d + 1$.

Correcting $d$ bit flips requires a minimum Hamming distance of $2\times d + 1,$ where $d$ is number of bit in errors.

 For the first blank, each error detection we need $1$ parity bit

For $3$ bit error detection we need $3$ parity bits. So, $3$ parity bits requires here. 

Also, we can calculate this way, formula is $d+p+1 \leq 2^p$ where, $d=$ data bits , $p =$ parity bits , $d=4$ bits given.

According to $1^{\text{st}}$ question, $d=4$  so $4+p+1\leq 2^p$ 

$p+5 \leq 2^p$  now if  p$=2$ it becomes $7 \leq 4,$ Not possible.

If $p=3$ it becomes $8\leq 8,$ which is possible.

So, $p$ must be $3.$[ Minimum value of $p$ is $3$ ]

The second blank the $3$-bit error detection is possible because the code has a minimum distance of $\underline{\qquad}$answer is $3+1=4,$ where d$=3.$ Formula used is $d+1.$

The answer for $2$ blanks is $[ 3,4 ].$

Comments

For 3 bit error detection hamming distance should be 4 but if we use parity bit 3 then hamming distance is 3 not 4

---

@harshpeswani45 bro , number of parity bits and minimum hamming distance are two different things . 

---

i dont think you require 3 parity bits for 3 bit error detection. Even with a single parity bit u can detect a 3 bit error. 

In this case 3 parity bits are required because you are correcting a 1 bit error along with detection of a 3 bit error. And the minimum no. of parity bits required to correct a single bit error can be given by 2^r >= m+r+1 (which you have mentioned as the other way to solve this part of the  question)

 

Answer 2

let minimum Hamming distance is $t.$
so with this hamming distance $t-1\ bit$ error detection as well as $\dfrac{ (t-1)}{2}$
bit error correction is possible..

for $3\ bit$ error detection minimum Hamming distance $=3+1=4$
for $1\ bit$ error correction  minimum Hamming distance $=2\times1+1= 3$
no. of parity bits $=p$
$p + t + 1 <= 2^p$
$p + 4 +1 <= 2^p$
$p=3$

Comments

https://en.wikipedia.org/wiki/Hamming_code#.5B7.2C4.5D_Hamming_code_with_an_additional_parity_bit

https://en.wikipedia.org/wiki/Hamming%287,4%29#Multiple_bit_errors

Your answer of 3 is incorrect as hamming (7,4) code has distance 3. So Max 2 bit erros can be detected !

https://en.wikipedia.org/wiki/Hamming_code

---

@Akash No, ans is correct.

and min distance will be 1 bit error correction

http://courses.cs.vt.edu/cs2506/Spring2009/Notes/Lecture7.pdf

---

Shouldn't it be,  p+d+1<= 2^p

Answer 3

Now, (binary) Hamming Codes are usually depicted using the following notation: (n,k,d). Here, n is the number of bits in the code-word, k is the number of information/data bits, and d is again the Minimum Hamming Distance. The Hamming Bound for this code is a mathematical relation between n,k and d. The code can exist if and only is the Hamming Bound is satisfied.

Refer --> 

Harsh Aurora's answer on https://www.quora.com/How-many-check-bits-are-required-for-16-bit-data-word-to-detect-2-bit-errors-and-single-bit-error-correction-using-hamming-code

Now n = ? , k = 4, d = 3+1 (because this much minimum distance is required for 1 bit correction and 3 bit error detection)

so putting all values in the formula you will get 

$2^{n-k} \geqslant \binom{n}{0} + \binom{n}{1}$

n = 7. so extra parity bits are n-k = 3.

So final answer is [3,4]

Comments

I think there is misinterpretation here.The code requires to satisfy both those properties.3 parity bits won't suffice for this(if only ensures 1 bit correction).You could easily create a counter-case.I think 5 parity bits are enough.Will post the formal proof soon.

---

I think this formula is right as it considers minimum hamming distance also.

Answer 4

I think the question is wrong because Hamming codes cannot detect arbitrary 3-bit errors.

Intuition : Suppose that we flip the first three bits (first two bits are redundancy bits and the third bit is a message bit), then the error will go undetected in any version of the Hamming code.

Further explanation : Suppose that we are using Hamming code (7, 4) and the codeword is [1R, 2R, 3M, 4R, 5M, 6M, 7M]. Flipping 1R, 2R and 3M will never be detected. This is true for any arbitrary Hamming code as the first message bit affects only the first two redundancy bits. So maximum distance of any Hamming code can be 2. (Note that maximum distance of any two Hamming codewords can be greater than 2. But distance of a code is defined as the minimum distance of any two valid codewords in it.)

Reference : https://en.wikipedia.org/wiki/Hamming(7,4)

... Hamming codes cannot detect or recover from an arbitrary three-bit error

Comments

There is a  slight error in your answer. The hamming distance of any hamming code is max 3. It can be less for a code with less than 4 data bits. In your own example, you showed that flipping the first 3 bits of any hamming code yields a valid codeword. Hence dmin = 3 is possible and it is the max dmin.

---

And to make your point more clear Hamming Codes only correct and detect only 1 bit chage.

Answer 5

Q.Consider a 3-bit error detection and 1-bit error correction hamming code for 4-bit data. The extra parity bits required would be _____ and the 3-bit error detection is possible because the code has a minimum distance of _______.
ans.after reading this question it fills hard,

tip 1)focus on what question is asking (1)min dist , 2)extra parity bits(with min hamming dist for correction of 1 bit only))

that it you have got the answer now
1)min dist=t+1.     (t is number of bits that can be detected)

min dist=3+1=4

2)extra parity bits in hamming code

so use formula 2^r >= m+r+1 
2^r >= 4+r+1 

2^r >= 5+r

r=3

ans.3,4 

Answer 6

May be this question is referring to SECDED (extended hamming Code).

In the question it is asked to mention the extra parity bit required so it will 1  (3 +1)

and a minimum hamming distance of 4

ANSWER [ 1, 4] 

 

additional screen shot from:wiki