check this

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+12 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 ____

$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 ____

+12 votes

Best answer

The Hamming distance between two bit strings is the number of bits that would have

to flip to make the strings identical.

To **detect d errors** requires 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 bit $\ldots\ldots$ So, $3$ parity bit

requires here. answer is $3$.

Also we can calculate this way, formula is $d+p+1 <= 2^p$

where $\text{d=data bits , p = parity bits , d=4 bit given}$.

according to $1^{st}$ question, d$=4$ so $4+p+1<= 2^p$

$p+5 <= 2^p$ now if p$=2$ it becomes 7 <= 4 , Not satisfy . p$=3$

it becomes $8<= 8,$ satisfy.

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 $d+1.$

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

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

+6

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

–1

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 408
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,780 questions

41,758 answers

118,934 comments

41,400 users