1
$\begingroup$

I came across following in Huffman coding:

Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the original codeword is still closer than any other codeword.

Then I came across following:

Consider dataword length of $m$ bits, codeword length of $n$ bits. So redundant check bits will be $n-m = r$. Each of the $2^m$ legal messages has $n$ illegal codewords at a distance of $1$ from it. These are formed by systematically inverting each of the $n$ bits in the $n$-bit codeword formed from it. Thus, each of the $2^m$ legal messages requires $n+1$ bit patterns dedicated to it. Since the total number of bit patterns is $2^n$, we must have $(n+1) 2^m ≤ 2^n$.

Using this information, I took $m=4$ and found that to meet above equation, $n \ge 7$. So with $n = 7$, I prepared Huffman code for $m = 4$ as shown in the image ($d$ are data bits, $c$ are check bits):

enter image description here

The code has hamming distance of 3 which confirms with $2(1)+1 = 3$ as required to correct 1 bit errors.

Q1. But then, how satisfying $(n+1) 2^m ≤ 2^n$ also ensures hamming distance is 3?

Q2. Also what will be equation if I want to correct $k$ bit errors? Will it be $(\binom{n}{k}+1)2^m\leq 2^n$?

$\endgroup$
2
$\begingroup$

The answer to both questions is the sphere-packing bound.

Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of radius $d$, consisting of all points at distance at most $d$ from the point. These balls must be disjoint: if the balls corresponding to $x,y$ contain some point $z$ in common (note that $z$ need not be in the code), then $d(x,y) \leq d(x,z) + d(y,z) \leq 2d$, contradicting the stated minimum distance. Each ball contains $\binom{n}{\leq d} := \sum_{r=0}^{d} \binom{n}{r}$ points, and so $$ M \times \binom{n}{\leq d} \leq 2^n. $$ This is because there are $M$ disjoint balls, each containing $\binom{n}{\leq d}$ points, while in total there are $2^n$ binary strings of length $n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "Surrounding each point of the code with a ball of radius $d$, consisting of all points at distance at most $d$ from the point". Doesnt that mean each ball contains $\binom{n}{\leq d}$ points (given a codeword corrsponding to the center of the ball, we choose any $r (\leq d)$ bit positions out of $n$ to get illegal codewords at distance at most $d$ from the center)? What I am missing? $\endgroup$ – anir Mar 10 at 19:49
  • $\begingroup$ Right, thanks for the correction. $\endgroup$ – Yuval Filmus Mar 10 at 19:51
  • $\begingroup$ Bit confused. Does above answer resolve my Q2? Does it mean, to correct $k$ errors, we need $d=2k+1$ & then follow $M\times \binom{n}{\leq d}\leq 2^n$? For correcting $k$ bit errors, we have $d=2k+1$ & need $M\times \binom{n}{\leq(2k+1)}\leq 2^n$. Q3. Is it so? Q4. Also are two inequalities comparable: $(n+1)2^m≤2^n$ and $M×\binom{n}{≤d}≤2^n$. That is, should $\binom{n}{≤d}==n+1$>? **Q5.** I [read](en.wikipedia.org/wiki/Hamming_code) that $d=3$ for Hamming code & can correct only 1 bit errors. Cant we design Hamming code with $d>3$ to correct more than 1 bit errors? $\endgroup$ – anir Mar 11 at 19:42
  • $\begingroup$ Sorry for a lot questions (and also for that ill formatter comment. Dont know why it does not render links and bold face correctly. I copy pasted same markdown in new question box and it was correctly rendering.) $\endgroup$ – anir Mar 11 at 19:49
  • $\begingroup$ Your $k$ and my $d$ are the same. Sorry for the confusion. $\endgroup$ – Yuval Filmus Mar 11 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.