The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.2k views
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 ____.
asked in Computer Networks by Veteran (59.6k points)
edited by | 2.2k views
+3
@habibkhan , @Arjun
check this
0
see my answer @anirudh

hope it is clear.

3 Answers

+14 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 ].

answered by Veteran (69.3k points)
edited by
0
Can u please explain the reason behind the formulas d+1 and 2*d+1
+3

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

@Hemant Parihar  No there is no such rule

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.

 

+15 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$
answered by Veteran (55.4k points)
edited by
0
It is 3 bit error detection and 1 bit error correction.
0
check answer now..
+6

Hamming Rule , parity bit "p"

d + p + 1 < = 2 ,  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://cs.stackexchange.com/questions/32025/hamming-distance-required-for-error-detection-and-correction http://courses.cs.vt.edu/cs2506/Spring2009/Notes/Lecture7.pdf

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

                               

0
yes..
0
How is detection and correction bits related to data bits Plz explain

Standard formula is 2 power p >=p+m+1
0
for 1 bit error correction  minimum Hamming distance = 2*1+1 =4 ???

how come 2*1 + 1 became 4 here ?
–1
+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
0 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]

answered by Boss (11.2k points)
0
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.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,082 questions
47,676 answers
147,482 comments
62,393 users