edited by
11,725 views
28 votes
28 votes
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 _______.
edited by

4 Answers

Best answer
40 votes
40 votes

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 ].$

edited by
25 votes
25 votes
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$
edited by
2 votes
2 votes

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]

1 votes
1 votes

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

Answer:

Related questions

11 votes
11 votes
1 answer
1
Kathleen asked Sep 12, 2014
3,108 views
A simple and reliable data transfer can be accomplished by using the 'handshake protocol'. It accomplishes reliable data transfer because for every data item sent by the ...
16 votes
16 votes
4 answers
2
Kathleen asked Sep 12, 2014
3,481 views
The purpose of instruction location counter in an assembler is _______
19 votes
19 votes
2 answers
3
Kathleen asked Sep 12, 2014
2,286 views
Many microprocessors have a specified lower limit on clock frequency (apart from the maximum clock frequency limit) because _____
22 votes
22 votes
4 answers
4
Kathleen asked Sep 12, 2014
5,143 views
The Boolean function in sum of products form where K-map is given below (figure) is _______