5
$\begingroup$

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 (MRRW) which states that the rate $R(\delta)$ corresponding to a relative 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$ (using simple approximations of entropy), 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$? Or am I wrong in the above conclusion (most sources claim the MRRW bound stated above is the best known bound, but its not clear if that holds for larger q as well). 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$.

  • 0
    Bharat, It is not trivial to see how this compares to Singleton bound, but IIRC it is not weaker. A point is though that for larger $q$ we have longer and longer MDS-codes. And after that we have AG-codes that are asymptotically very good. When $q\ge49$ Tsfasman, Vladuts and Zink proved that we can get codes better than Gilbert-Varshamov bound using algebraic geometry.2018-10-21

0 Answers 0