1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you for help and more for explanation. help to understand $\endgroup$ – hpr16 Mar 26 at 10:29

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.