Sphere packing inequality for error-correcting codes

Question

i am wondering if the following inequality is correct:

if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^k_{i=1}\binom{m+r}{i}+1≤2^r$$

holds true?

please if you can explain so i can understand how you choose answer you give.

the only inequality i find in books that look similar is about "perfect code" with the inequality given is: $2^n = 2^k\sum_{i=0}^k\binom n i$. but i not see how this code is relevant. i try to do research in other books or internet and no answer sadly. please help me understand if given inequality is true or not based on information given.

thank you much.

Answer 1

For a codeword $x$, let $B_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that $$|B_k(x)| = \sum_{i=0}^k \binom{m+r}{i}. $$ If the code supports correcting up to $k$ errors, then the sets $\{ B_k(x) : x \in C \}$ must be disjoint. The code contains $2^m$ many different codewords, hence we get $$ 2^m \sum_{i=0}^k \binom{m+r}{i} \leq 2^{m+r}, $$ which is the same as your inequality. Here $m+r$ is the length of each codeword, and $2^{m+r}$ is the number of possible vectors.

If your code is $q$-ary rather than binary, then the same calculation shows that $$ \sum_{i=0}^k (q-1)^i \binom{m+r}{i} \leq q^r. $$