Hamming codes are the most efficient single-bit-error correcting codes. For a Ha

Question

Hamming codes are the most efficient single-bit-error correcting codes. For a Hamming code with c check bits, bits in the code word are numbered from 1 to 2^c - 1 and the check bits occupy the power of 2 positions, i.e. positions 1, 2. 4, 8, ... The remaining positions are filled by the data bits. The ith check bit is a parity over all bits where the bit position in binary has a '1' in the ith bit. So, the first check bit is a parity over positions 1, 3, 5, 7, ..., the second check bit is a parity over positions 2, 3, 6, 7, ..., etc. For c = 3, a Hamming code word has the form c1 c2 d1 c3 d2 d3 d4(with bit numbering from left to right). For example, the Hamming code word for data 0110 is 1100110 (using even parity). a) Compute the 4-bit data words corresponding to the following 7-bit words, which could be valid Hamming code words or could have single-bit errors inserted. Even parity is used in all cases. Show your work. b) Derive a big ''O'' expression for the number of parity bits in a Hamming code in terms of n, where n is the number of data bits. Try to make this the tightest big ''O'' bound you can. c) Compare the efficiency of Hamming codes and two-dimensional parity codes by comparing your answers to 1b) and 2b).

Explanation / Answer

a)

7 bit word = 0011101

First, we need to check whether it is a valid hamming code or has an error.

Since even parity is used, the number of 1-bit must add up to an even number.

In the above example, bits at position 1, 2, and 4 are parity bits

Therefore 4 bit data word is

1's are in position 3, 4, 5, and 7

Position 3=21+20

4=22

5=22+20

7=22+21+20

Removing the check bit positions 1,2,4

word=1101

2) 1101000

Removing the check bit positions 1,2,4

word=0000

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.