Best upper bound on rate for q-ary codes

Question

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to arelative distance of $\delta$ is such that: \begin{equation*}R(\delta) \leq H_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation*} where H is the binary entropy function. (A slight improvement of the above exists in the binary case, but within the same framework) In the case of q-ary codes, i.e. codes over $\mathbb F _q ^n$, the above bound is generalized to: \begin{equation*}R(\delta) \leq H_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation*} My question is as follows: For larger alphabet size q, the above bound seems to weaken significantly. In fact, observing the growth of the above bound as $q \rightarrow \infty$, we see that: \begin{equation*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}}) \end{equation*} Thus, it seems to get worse than even the Singleton bound $R(\delta) \leq 1-\delta$.

So which is the best bound for large alphabet size $q$? Also, could someone direct me to references for comparisons of different bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.

Answer 1

So, the supposedly the sharpest one among all known bounds is somehow poorer than the bound you learn in Coding Theory 101 if the alphabet size $q$ approaches infinity. I think the reason you find it funny lies in what you mean by "large $q$."

You can think this way: If the parameter $q$ is large compared to the code length $n$, the Singleton bound is an extremely sharp, invincible upper bound. In fact, it's best possible in the sense that there are infinitely many nontrivial codes attaining it. I think that's why you got caught in a seemingly contradicting situation where the "best upper bound (MRRW)" fails to beat the "poor and elementary bound (Singleton)."

Here's a bit more formal explanation. The upper bounds on the information rate $R$ you're considering are asymptotic ones described by the Hilbert entropy function

$$H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x)$$

and the relative distance $\delta = \frac{d}{n}$, where $d$ is the minimum distance of a code. Bounds of this kind try to understand the behavior of the information rate when the code length $n$ tends to infinity for a fixed $\delta$.

More precisely, by writing the largest possible number of codewords for a $q$-ary code of length $n$ and relative distance $\delta$ as $A_q(n,\delta n)$, we would like to know the exact value of

$$R_q(\delta) = \lim_{n\rightarrow \infty}\sup n^{-1}\log_qA_q(n,\delta n).$$

The MRRW bound you mentioned is a pretty good upper bound on $R_q(\delta)$ obtained through linear programing. Of course, the plain, simple Singleton bound can also be viewed as an asymptotic upper bound if you simply rewrite it with $\delta$, i.e., you have $R \leq 1-\delta$.

Now, what you did to the MRRW bound seem to be simply applying

$$\lim_{q\rightarrow \infty}H_q(\delta) = \delta$$

to see what it's like when "$q$ is large." The problem is that, in order to get a meaningful upper bound better than the Singleton bound, you should consider exactly what you mean by "large $q$."

As you probably already know, there are codes that meet the Singleton bound. Indeed, it's the definition of maximum separable distance (MDS) codes. The famous Reed-Solomon codes are the canonical examples of this type of code, which are conjectured to have the "largest" $n$ relative to $q$ among all possible (linear) MDS codes. More generally, algebraic geometry codes can attain

$$R \geq 1 - \delta - \frac{1}{\sqrt{q}-1}$$

when prime power $q$ is a square. Hence, if your $q$ is in the range where MDS codes may exist, no general upper bound on $R$ can beat the Singleton bound unless it's a very contrived one. If $q$ is small enough compared to $n$ such that unbelievably strong codes like algebraic codes can be realized, you don't expect any other bound can beat it.

So, if you would like a stronger asymptotic upper bound than the Singleton bound, you have to at least rule out the existence of MDS codes by making $q$ grow slow enough. Here's one theorem I know that can be used for this purpose:

If there exists a $q$-ary MDS code of length $n$ and minimum distance $d$, then $q \geq n-d+2.$

(For the proof, see L. M. G. M. Tolhuizen, On maximum distance separable codes over alphabets of arbitrary size, Proc. IEEE Int. Symp. Inf. Theory (1994) 431.)

So, by fixing the relative distance $\delta$, the inequality can be rewritten as $q \geq n(1-\delta)+2$. By this necessary condition for the existence of an MDS code, if you only allow $q$ to be always smaller than the right-hand side when driving $n$ to infinity, your favorite general upper bound may have a chance to beat the Singleton bound.

MDS codes and other very powerful error-correcting codes are extremely important and have various interesting connections to other fields both inside and outside of mathematics. So if you ask a real coding theorist, I think they know the best theorem you can exploit to rule out the existence of MDS codes and also the best methods to get sharp upper bounds on $R$ for $q$ of your favorite size and growth rate.