The maximal number of codewords in a code of length n with minimum distance at least d.

1.1k Views Asked by At

A code $C$ of length $n$ is a subset of the set of all binary words of length $n$. A codeword is an element in C. The minimum distance of a code is the minimum Hamming distance over all pairs of distinct codewords. Let $A(n,d)$ be the maximal number of codewords in a code of length $n$ such that the minimum distance of the code is at least $d$.

Here are some facts about $A(n,d)$ that I understand. If $d>n, A(n,d) = 1.$ If $d = n$ then $A(n,d) = 2$ because we can choose a word and its complement to be in the code. If $d = 1 $ then $A(n,d) = 2^n$ because every word could be in the code. If $d = 2 $ then $A(n,d) = 2^{n-1}$ because we can choose the words with the same parity to be in the code.

The known values for $A(n,4)$ are given in Sloane's OEIS A005864. There is a link to a table of $A(n,d)$. In the link it is stated that: If $3*d/2 > n$ then $A(n,d) = 2$. Is there an easy explanation for this?

Also the link states: $A(n-1,2e-1) = A(n,2e)$. I am trying to figure out why this is true as well.

I do not have any background in coding theory. I know some basic combinatorical enumeration techniques that might apply to counting binary words. I would like to see a gentle derivation of the above two statements.