1
$\begingroup$

It is well known that linear block codes can achieve capacity and hence study of good codes can be limited to study of linear block codes. It is also well known that BCH codes are asymptotically bad and cannot achieve capacity. What are the corresponding results for cyclic codes that fall between these two classes of codes? Can they achieve capacity? Can they achieve the cutoff rate? Is their error exponent different from linear block codes?

$\endgroup$
  • 1
    $\begingroup$ A random code of rate $R$ (for which the average error probability, averaged over all possible random codes, is small) has the property that each of the $q^n$ vectors has equal probability of belonging to the code. The ensemble of all linear codes of rate $R$ codes do not satisfy this requirement since all linear codes have $\mathbf 0$ as a codeword. So, there are additional tricks that need to be used to make your statement be true. $\endgroup$ – Dilip Sarwate Apr 7 '13 at 14:41
  • $\begingroup$ I am referring to the early work of Elias and more recent results by Montanari and Barg and Forney. $\endgroup$ – Palo Apr 7 '13 at 23:58
1
$\begingroup$

There are subtle distinctions between what makes a code "good". One classical notion is that a sequence $\mathcal{C}_m$ of length-$N_m$ binary codes is "good" if their minimum distances $d_m$ satisfy $d_m / N_m > \delta$ for all $m$. In this sense, sequences of BCH codes are "bad" because $d_m \sim N_m / log N_m$.

This is different than achieving capacity. In fact, it was really shown that sequences of BCH codes do achieve capacity on the binary erasure channel (https://arxiv.org/abs/1601.04689).

The question of whether there exists a "good" sequence binary cyclic codes (i.e., satisfying $d_m / N_m > \delta$ for all $m$) is a well-known problem in coding theory. As far as I know, it remains open.

However, there are good sequences of quasi-cyclic codes, as noted in:

T. Kasami, A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2. IEEE Trans. Information Theory IT-20 (1974)

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