1
$\begingroup$

Theorem 7.3 on page 67 in these lecture notes states the following.

For every even power of a prime $q$, and every parameter $\delta < 1 - 1/(\sqrt{q} - 1)$, there exists an infinite family of $q$-ary linear codes of relative distane $\delta$ and rate $R \geq 1- \delta - 1/(\sqrt{q} - 1)$. Further a generator matrix for such a code can be construted in $\tilde{\mathcal{O}}(n^3)$ time, where $n$ is the length of the code.

While this is really nice in asymptotic contexts, I wonder how flexible one can choose the concrete parameters of these algebraic geometric codes. For example: Could one choose $q = 64, \delta = 0.19$ and $k = 2$ to have an $[3, 2, 1]_64$ code? Or phrased more generally: Which constraints are there on the choice of these parameters?

I tried reading the paper the theorem above is based on, but I am to unacquainted to algebraic geometry to answer the question myself.

$\endgroup$
2
  • 1
    $\begingroup$ Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,\delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise. $\endgroup$ Dec 30 '18 at 20:03
  • $\begingroup$ @JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $\tilde{\mathcal{O}}(n^3)$. $\endgroup$
    – Dave
    Dec 30 '18 at 21:42
1
$\begingroup$

There is no single theorem that says what parameters are possible.

If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.

In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.

$\endgroup$
2
  • $\begingroup$ Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist. $\endgroup$
    – Dave
    Dec 28 '18 at 20:07
  • $\begingroup$ @Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible. $\endgroup$
    – rschwieb
    Dec 28 '18 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.