check this

The Gateway to Computer Science Excellence

+16 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 ____.

0

To calculate the numbers of redundant bits (r) required to correct d data bits, let us find out the relationship between the two. So we have (d+r) as the total number of bits, which are to be transmitted; then r must be able to indicate at least d+r+1 different values. Of these, **one value means no error**, **and** **remaining d+r values indicate error location of error in each of d+r locations**. So, d+r+1 states must be distinguishable by r bits, and r bits can indicates 2 r states. Hence, 2 r must be greater than d+r+1.

$2^{r}$ $\geqslant$ d+r+1

Put d=4 then what is the value of r ?

r=3 in order to satisy the condition.

+23 votes

Best answer

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, $\text{d=data bits , p = parity bits , d=4 bits given}$.

According to $1^{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.$

**Answer for 2 blanks are [ 3,4 ].**

+4

Can someone give any resources to confirm this line? Thank you..!!

each error detection we need 1 parity bit

for 3 bit error detection we need 3 parity bit ...... So, 3 parity bit requires here. answer is 3.

0

@Bikram Sir the "d" bits you used to represent the errors and the "d" used for data bits..they aren't same, right? It might create confusion.

0

can you please check if the minimum hamming distance of two coded words is 4 ,since i can think of a counter example like M1:0000 encoded to E1:0000000 and M2:0010 encoded to E2:0101010(consider left to right message coding) ,here the hamming distance is only 3 which is not sufficient for 3 bit error detection

+1

@Bikram "It can be shown that a single parity check code can detect only odd number of errors in a code word."

https://nptel.ac.in/courses/106105080/pdf/M3L2.pdf Page 7

Doesn't it mean that a single parity bit can be used to detect odd no. of errors and hence 3 bit error?

Which would make your statement "For 3 bit bit error detection we need 3 parity bits" false?

+20 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$

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$

+7

Hamming Rule , parity bit "p"

d + p + 1 < = 2^{p } , Where d is the number of data bits and p is the number of parity bits

hamming minimum distance , if d bit is the detection bit = d + 1 bit ,

...................is correct....???

http://iete-elan.ac.in/SolQP/soln/soln_ac07.pdf http://en.wikipedia.org/wiki/Hamming_code

0

How is detection and correction bits related to data bits Plz explain

Standard formula is 2 power p >=p+m+1

Standard formula is 2 power p >=p+m+1

0

+2

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

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

+1

@Akash No, ans is correct.

and min distance will be 1 bit error correction

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

and min distance will be 1 bit error correction

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

+1 vote

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]**

0 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

52,345 questions

60,470 answers

201,795 comments

95,272 users