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

hope it is clear.

3 Answers

+17 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 (68.1k points)
edited by
Can u please explain the reason behind the formulas d+1 and 2*d+1

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.


@Hemant Parihar  No there is no such rule


@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.


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

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 , correct....??? 


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

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

how come 2*1 + 1 became 4 here ?
@Akash No, ans is correct.

and min distance will be 1 bit error correction
Shouldn't it be,  p+d+1<= 2^p
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

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 (12.2k points)
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.

Related questions

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
49,540 questions
54,100 answers
71,007 users