What is the max size of subset of a Hamming Space with this property

96 Views Asked by At

Keep in mind I know virtually no coding theory, I simply recognized this as an equivalent formulation to another question I was considering.

Let $F(r,n)$ denote the set of all words of length $r$ on $n$ letters. and let $H(f,g)$ be the Hamming distance between $f$ and $g$.

What I wish to know is the following:

For fixed integers $r,n,k$ what is the maximum possible cardinality of $S \subset F(r,n)$ with the property that $ \forall f,g \in S$, $H(f,g) \ge k$.

Any information you can give me about this would be greatly appreciated, thanks!

1

There are 1 best solutions below

2
On

In general your question has no complete answer. Even if you are in the case that $n=q$ is a prime power the answer is very hard in general.

However, when the size of the alphabet is a prime power you could have a look at some bounds on the maximum possible cardinality of $S$ here

Some upper bounds

https://en.wikipedia.org/wiki/Hamming_bound

https://en.wikipedia.org/wiki/Griesmer_bound

https://en.wikipedia.org/wiki/Singleton_bound

https://en.wikipedia.org/wiki/Johnson_bound

A lower bound

https://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound