6
$\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 (derived through a linear programming relaxation approach) 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$, 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 that the MRRW bound is worse than even the Singleton bound for larger $q$? Also, could someone direct me to references for comparisons of different upper bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.

$\endgroup$
3
$\begingroup$

This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see the paper "On the optimum of Delsarte's linear program" by Samorodnitsky (1998).

Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$. Even for $q=2$, this is a complicated analysis, so I don't know whether anybody has performed it for larger $q$.

$\endgroup$

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.