Bounding A ( n , d ) = <mo movablelimits="true" form="prefix">max <mo fence="fals

Question

Bounding

A (n, d) = max {M |

exists a code with parameters n,M,d}
I would like to prove that this lower bound of

A (n, d) = max {M |

exists a code with parameters n,M,d} (where n is the length of the block code, M the number of words of the code, and d, the minimal distance of the code), holds:

\frac{2^{n}}{\sum_{i = 0}^{d - 1} (\binom{n}{i})} \leq A (n, d)

For trying to see this, I have tried to connect this inequality with the cardinal of the ball of radius

d - 1

, that is

\sum_{i = 0}^{d - 1} (\binom{n}{i}) 2^{i}

, so for sure, that quantity is less than

2^{n} \sum_{i = 0}^{d - 1} (\binom{n}{i})

. But I don't see if this is or not helping me at all... I would appreciate some guidance, help, hint,... Thanks!

Answer 1

Step 1
You are nearly there! Note that the sphere of Hamming radius t has

\sum_{i = 0}^{d - 1} (\binom{n}{i})

vectors in it, not

\sum_{i = 0}^{d - 1} (\binom{n}{i}) 2^{i}

vectors as you state.
Suppose that there are spheres of Hamming radius

d - 1

centered at the M codewords in a (n, M, d) code. Some of these spheres might be overlapping (i.e., not disjoint) but never mind that. The total volume occupied by these M spheres (ignoring the overlap) is

M \sum_{i = 0}^{d - 1} (\binom{n}{i})

. Now, if it so happens

\begin{matrix} (1) & M \sum_{i = 0}^{d - 1} (\binom{n}{i}) < 2^{n}, \end{matrix}

then there is at least one vector in the binary n-space that is, by construction, at distance d or more from all the M codewords that we started with. So, we can include this vector in our code to create a

(n, M + 1, d)

code. Lather, rinse, and repeat. We now have a

(n, M + 1, d)

code for which we can test whether

\begin{matrix} (2) & (M + 1) \sum_{i = 0}^{d - 1} (\binom{n}{i}) < 2^{n} \end{matrix}

holds or not. If (2) holds, we can add another codeword to construct a

(n, M + 2, d)

code, and repeat the whole process again.
Step 2
We stop when we reach a point where we have a (n, M′, d) code for which the inequality reverses:

M^{'} \sum_{i = 0}^{d - 1} (\binom{n}{i}) \geq 2^{n}

and we can no longer apply the above argument. We could try to see if more sophisticated thinking and reasoning about the overlap between spheres that we totally ignored might improve the result, but we won't: many people have already tried without much success. But, we have shown that there exists a (n, M′, d) code such that

M^{'} \sum_{i = 0}^{d - 1} (\binom{n}{i}) \geq 2^{n} ⟹ M^{'} \geq \frac{2^{n}}{\sum_{i = 0}^{d - 1} (\binom{n}{i})} .

It follows that

A (n, d) \geq \frac{2^{n}}{\sum_{i = 0}^{d - 1} (\binom{n}{i})}

which is the result you are trying to prove.

Bounding A ( n , d ) = <mo movablelimits="true" form="prefix">max <mo fence="fals

Want to know more about Discrete math?

Answers (1)

Not exactly what you’re looking for?

Relevant Questions