How to find the maximal minimal distance between m points in a k-dimension Hamming space? Assume we have m points in a k-dimension Hamming space. I wish all points are spread as far as they can in the space. So I wish to optimize the max-minimal distance between any pairs. Is there any algorithm that can solve this problem? I guess this problem might have a connection with Error Correction Code, but I am not familiar with it. Is someone could give me some idea? Thanks!
If we can find a theory or algorithm to find generated solution is best. But in most cases, the dimension $k=2^n$, for example: $k=16, 32, 64, 128$. $m=10, 20, 100, 1000$. $M < 2^k$. Currenty, I wish to solve $m=10$ with $k=16, 32, 64$. And then to see if can solve $m=20, 100$ with same $k$ value.
 A: I will give some pointers for binary codes using standard notation so you can refer to other sources as well. This is a vast topic and you will need to do some research yourself online.
In coding theory usually the length of the codeword is denoted by $n$ the size of the code by $M$ (=number of codewords) and the dimension of a linear code by $k$ (Here $M=2^k$ where necessarily $k\leq n$ and the code is just a subspace of the vector space of length $n$ binary vectors). The minimum distance $d$ is the quantity you are trying to maximize, it is the minimum pairwise hamming distance between codewords.
In general, we define $A(n,d)$ to be the largest size of a code with length $n$ and distance $d:$
There are tables, and upper and lower bounds for this, in terms of what we know. The exact value in general is not known, as I mentioned. Here is one such site:
http://www.eng.tau.ac.il/~litsyn/tableand/
But usually the tables are focused on small $n,d$. In this table, look at for example the entry for $d=3$, and $n=33,$ it says that $$A(n,d)\geq N\times 2^k=85\times 2^{23}.$$
In terms of bounds, there is the Hamming bound and Plotkin bounds, which upper bound code size and the Gilbert Varshamov bound which lower bounds code size.
In terms of explicit code family constructions (not necessarily optimal)  the Reed-Muller codes are simple to understand, see their wikipedia entry as well.
Reed-Muller Code of Order $r$:
Length $n=2^m$
Dimension $k=1+\binom{m}{1}+\cdots+\binom{m}{r}$ so $M=2^k.$
Minimum Distance: $d=2^{m-r}.$
Example:
You ask for $n=16=2^4,$ if you take $r=1$ you get a first order Reed-Muller code with $k=1+4=5$ so $M=2^5=32$ codewords with distance $d=2^{4-1}=8.$ Or you could have $r=2$ which gives $k=1+4+6=11$ thus $M=2^11=2048$ with $d=2^2=4.$ Note that this space has $2^{16}=65536$ possible binary words.
Note:
Other codes to look for, for your other parameters, might be BCH codes, where the dimension vs minimum distance tradeoff is a bit more flexible.
Happy hunting!
It's easier to consider linear codes for implementation, their sizes won't be a power of 10 but a power of 2 but you can just remove some codewords to get a smaller code.
