1
$\begingroup$

Let $W(r,n)$ be the set of all words of length $r$ on $n$ letters.

For two words $a,b \in W(r,n)$ define the Hamming distance $d(a,b)$ as the number of places that they have different letters.

Let $M(r,n,k)$ be the maximum $|S|$ such that $S \subseteq W(r,n)$ and $\forall a,b \in S$ $d(a,b) \ge k$ (I believe this is usually denoted $A_n(r,k)$ in coding theory)

Most of the results I have seen about this value have been in the case $n=2$ since most applications of this idea are in binary codes. I am not particularly interested in $n=2$ and am wondering if any general bounds are known (lower or upper) or even a list of known exact values for small numbers would be nice. I do know that the Singelton bound says $M(r,n,k) \le n^{r-k+1}$. Any other information you could give me would be greatly appreciated. General bounds or exact values are good, or even if $M(r,n,k)$ has a "name" attached to it?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ There are many upper bounds that work in the generality you are asking, in addition to the Singleton bound. E.g. the Plotkin and Hamming bounds. For a lower bound, there is the Gilbert-Varshamov bound. Tightening these bounds is of course a well known old wide open problem, so if you want something more specific, you need to narrow your question a bit. $\endgroup$ – Felipe Voloch Mar 6 '17 at 20:27
  • $\begingroup$ Thank you I will read up on those. Are you aware of anything about exact values? $\endgroup$ – Elliot Mar 6 '17 at 20:52
  • $\begingroup$ often Delsarte (linear programming) is quite good. You can look up upper/lower bounds for small tuples of parameters in codetables.de, and compute them with Sagemath or Magma. $\endgroup$ – Dima Pasechnik Mar 6 '17 at 21:42
  • 1
    $\begingroup$ If $n$, the size of the alphabet, is a prime power (in particular prime) and sufficiently large (bigger than the length $r$ is enough), then the Singleton bound is attained by the Reed-Solomon codes. This has been known since the 1960s. $\endgroup$ – Felipe Voloch Mar 7 '17 at 14:47
  • 1
    $\begingroup$ @Felipe Voloch: linear programming bounds hold for nonlinear codes just as well, and Sagemath can compute these for you. Regarding tables of nonlinear codes and bounds, one can check the page win.tue.nl/~aeb of Andries Brouwer for links. $\endgroup$ – Dima Pasechnik Mar 7 '17 at 19:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.