- 2070 Asar · 2+4 marks
Minimum Hamming distance; find k and n
Short answer
Minimum Hamming distance d_min is the smallest distance between any two codewords, enabling detection of d_min−1 and correction of ⌊(d_min−1)/2⌋ errors. A dataword is the k-bit message; a codeword is the n-bit encoded block with redundancy. For Hamming code with d_min=3 and k≥11: use r=4 parity bits, n=2^r−1=15, k=n−r=11, giving C(15,11).
What is the minimum Hamming distance? Differentiate between dataword and codeword. We need a dataword of at least 11 bits. Find the values of (k) and (n) in the Hamming code C(n,k) with dmin = 3.
Minimum Hamming distance
The minimum Hamming distance d_min of a code is the smallest Hamming distance between any two distinct codewords. It decides the capability: a code detects up to d_min − 1 errors and corrects up to ⌊(d_min − 1)/2⌋ errors.
Dataword vs codeword
| Point | Dataword | Codeword |
|---|---|---|
| Meaning | Original message block | Encoded block sent on channel |
| Length | k bits | n bits (n > k) |
| Content | Information only | Information + redundant bits |
| Number | 2ᵏ possible | 2ᵏ valid out of 2ⁿ |
Finding k and n
For a Hamming code with d_min = 3: n = 2ʳ − 1, k = n − r, where r is the number of parity bits. We need k ≥ 11.
- r = 3: n = 7, k = 4 (too small)
- r = 4: n = 15, k = 11 (k ≥ 11 satisfied)
Check: 2ʳ ≥ k + r + 1 → 16 ≥ 11 + 4 + 1 = 16 ✓.
Answer: n = 15, k = 11, i.e. the Hamming code C(15, 11) with 4 parity bits.
✓ Answer checked by Claude Sonnet 5.5
Related questions
- Dataword vs codeword; error coding techniques · Data Communication, chapter 8
- Capability of a code with dmin = 4 · Data Communication, chapter 8
- Hamming distance and minimum distance · Data Communication, chapter 8 · asked 2×
- (6,3) block code words, weights, dmin · Data Communication, chapter 8
- Redundancy, Hamming distance, linear vs cyclic · Data Communication, chapter 8
- Construct a (7,4) Hamming code · Data Communication, chapter 8
- Significance of dmin; (7,4) cyclic code for 1101 with g(x) = 1 + x + x² · Communication Systems, chapter 8
- Hamming weight and distance; (7,4) cyclic code for 1011 · Communication Systems, chapter 8 · asked 2×
- Hamming distance and weight; (6,3) code check for 100101 · Communication Systems, chapter 8
- Hamming weight and distance; validate code 100011 · Communication Systems, chapter 8