2
$\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$
1

1 Answer 1

3
$\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$.

$\endgroup$
7
  • $\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$
    – RajS
    Mar 10, 2020 at 19:49
  • $\begingroup$ Right, thanks for the correction. $\endgroup$ Mar 10, 2020 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$
    – RajS
    Mar 11, 2020 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$
    – RajS
    Mar 11, 2020 at 19:49
  • $\begingroup$ Your $k$ and my $d$ are the same. Sorry for the confusion. $\endgroup$ Mar 11, 2020 at 19:53

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .