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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.