Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
Also asked at math.stackexchange.com/questions/224933/… and at cstheory.stackexchange.com/questions/14121/… Personally I quite like the question, so I will not vote to close it here just over this, but still wanted to give the links for everybodies benefit. –  quid Oct 30 '12 at 10:21
1  
A superficial remark: "best bound" is a bit of an oversimplifiying notion, e.g., also for q=2 the bound you give is not "good" for very small delta; for example, the relatively simple to prove Hamming bound is better there. But then it seems suffieciently clear what you are looking for. –  quid Oct 30 '12 at 10:28
    
@quid: Sorry, I asked the same questions there too. For a while, Overflow was disabled for maintenance and wasn't accepting new questions, hence I tried other available forums too. If thats wrong on my part, I apologize for it. –  Brazen Oct 30 '12 at 11:31
    
It is true that even in the binary case, the above bound is weaker than the Hamming bound for small $\delta$, but that can be rectified through the second MRRW bound whose existence I hinted at without going into details. You may be right that my question is less specific and more exploratory. I was initially surprised that the MRRW bound deteriorates so much for large q that it gets worse than the Singleton bound, and mainly wanted some affirmation of this. I'd be grateful if someone could direct me to useful references on comparisons of different bounds for large $q$. –  Brazen Oct 30 '12 at 11:33

1 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.

share|improve this answer
    
That's nice; I was always looking forward to an answer to this question. –  quid May 12 '13 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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