Modular curves and codes with a polynomial construction. (English) Zbl 0544.94016
Let \(F_ q\) be a field of q elements. Then a q-ary block code of length n is an arbitrary subset \(C\subseteq F^ n_ q\). Hamming distance between a and b, \(a\in F^ n_ q\), \(b\in F^{n}_{q}\) is the number of unequal components in a and b. The rate and the relative distance of the code are \(R(C)=\log_ q| C| /n\); \(\delta(C)=d(C)/n\), where d(C) is the minimal Hamming distance between two unequal vectors in C. Let \(I=\{1,...,| C| \}\). A bijective map \(\phi:I\to C\) is referred to as coding. The code C has a polynomial complexity of construction iff we can construct \(\phi\) with polynomial complexity in n and \(\phi\) (i) itself also has polynomial complexity in n. The problem is to find such codes having maximal possible rate (\(\delta\) (C) being fixed). In this paper we prove a new lower bound for the rate of binary codes with polynomial complexity of construction, which is better than the best known bound [see Eh. L. Blokh and V. V. Zyablov, Linear concatenated codes (Russian) (1982)]. We use the construction of concatenated codes with the fixed binary codes as the inner codes and codes arising from the classical modular curves through the Goppa construction as outer codes.