1

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.

Cosmo
  • 13
  • This is an open problem for general $k$ and $m$. There are literally hundreds of papers in coding theory considering different versions of this problem. And this is a duplicate of https://math.stackexchange.com/questions/996933/highest-pairwise-hamming-distance-between-k-bitvectors-of-length-n?rq=1 – kodlu Mar 30 '22 at 13:51
  • Does this answer your question? Highest pairwise Hamming distance between k bitvectors of length n – kodlu Mar 30 '22 at 13:51
  • Thank you kodlu! The answer of https://math.stackexchange.com/questions/996933/highest-pairwise-hamming-distance-between-k-bitvectors-of-length-n seems did not solve my question. It said there is no easy way for general k and m. In your view, is there any coding theory provides some algorithm solutions? Thank you so much! – Cosmo Mar 31 '22 at 06:09
  • 1
    Please provide details, such as what value of $m$ and $k$ you are looking at. This can be specific values, or say $m=k$ or $m=k^2$ or $m=2^k,$ etc. Then I can answer with suggestions. Actually, incorporate those values into your question so it is easier to read all in one spot. – kodlu Mar 31 '22 at 15:12
  • Thank you for your suggestions! In my field, the dimension $k=2^n$ normally, for example: $k=16, 32, 64, 128$. $m$ do not have a specific value, but there are some often used values such as $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 it possible to solve $m=20, 100$ with same $k=16, 32, 64$. – Cosmo Mar 31 '22 at 23:53

1 Answers1

0

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.

kodlu
  • 9,338
  • Thank you kodlu! You are so kind and I did not expect such a detailed answer! I will do some research, such as linear code, and Reed-Muller code and learn some knowledge of information theory.

    Yesterday, my supervisor told me that he thought my question should be a well-studied problem and should have a well-known algorithm to solve it. But from your answer, it seems not that easy.

    Well, I am going to learn. Thank you again.

     – Cosmo Apr 02 '22 at 04:42
  • glad it was helpful, if you are happy with the answer you can accept it. – kodlu Apr 02 '22 at 04:44
  • Hi kodlu, may I ask a relevant question? Are there any solution for: how many Hamming balls with radio=r be put in a Hamming space with dimension=k? This is a very similar question to my previous one, but we know radio(distance) instead of the number of centers(codewords). Thank you! – Cosmo Apr 07 '22 at 05:46