×

Polynomial-time construction of codes. I: Linear codes with almost equal weights. (English) Zbl 0757.94014

Summary: We prove that there are infinite families \((C_ i)_{i\geq 0}\) of codes over \({\mathbf F}_ q\) with polynomial complexity of construction whose relative weights are as close to \((q-1)/q\) as we want and are such that \(\lim_{i\to\infty}\dim C_ i/\text{length }C_ i>0\). The disparity of these families, which is the limit of the ratio of the maximum weight to the minimum one, is also close to one. The method used is the concatenation process. We give the asymptotic expansion of the behaviour of our families as the relative distance approaches \((q-1)/q\).

MSC:

94B05 Linear codes (general theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goppa, V. D.: Algebraico-geometric codes. Izv. Akad. Nauk S.S.S.R.46 (1982). Math. U.S.S.R. Izvestiya,21, 75-91(1983) · Zbl 0522.94013
[2] Goppa, V. D.: Geometry and codes. Dordrecht: Kluwer Academic, 1988 · Zbl 1097.14502
[3] Katsman, G. L., Tsfasman, M. A., Vladut, S. G.: Modular curves and codes with polynomial complexity of construction. Problemy Peredachi Informatsii20, 47-55 (1984);=Problems of Information Transmission20, 35-42 (1984) · Zbl 0555.94008
[4] Katsman, G. L., Tsfasman, M. A., Vladut, S. G.: Modular curves and codes with a polynomial construction. IEEE Trans. Inf. Theory30, 353-355 (1984);=Problems of Information Transmission20, 35-42 (1984) · Zbl 0544.94016 · doi:10.1109/TIT.1984.1056879
[5] Lachaud, G.: Les codes géométriques de Goppa. Séminaire Bourbaki 1984/1985, exp. N{\(\deg\)} 641, Astérisque133-134, 189-207 (1986)
[6] Lachaud, G.: Projective Reed-Müller Codes. Coding theory and applications, Proc. 2nd Int. Colloq., Paris/Fr. 1986. Lect. Notes Comput. Sci. vol.311, pp. 125-129. Berlin Heidelberg New York: Springer 1988
[7] Lachaud, G.: The parameters of projective Reed-Müller Codes, Discrete Math.81, 1-5 (1990) · Zbl 0696.94015 · doi:10.1016/0012-365X(90)90155-B
[8] McWilliams, F. J., Sloane, N. J. A.: The theory of error-correcting codes. Amsterdam: North-Holland, 1977 · Zbl 0369.94008
[9] Manin, Yu. I., Vladut, S. G.: Codes linéaires et courbes modulaires. Itogi Nauki i Tekhniki25, 209-257 (1984); trad, angl., J. Soviet Math.30, 2611-2643 (1985); trad. franç., Pub. Math. Univ. Pierre et Marie Curie, n{\(\deg\)} 72, 91p
[10] Tsfasman, M. A., Vladut, S. G., Zink, Th.: Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Math. Nach.109, 21-28 (1982) · Zbl 0574.94013 · doi:10.1002/mana.19821090103
[11] Tsfasman, M. A., Vladut, S. G.: Algebraico-geometric codes. Dordrecht: Kluwer Academic 1991
[12] Lachaud, G., Stern, J.: Polynomial-time construction of linear codes with almost equal weights, to appear in Proc. of the ?Sequences? Conference, Positano, Lecture Notes in Comp. Sci. Berlin, Heidelberg, New York: Springer (to appear) · Zbl 0836.94023
[13] Lachaud, G., Stern, J., Polynomial-time construction of spherical codes and the kissing number of spheres, Proc. of the 9th Int. Symp. ?Applied Algebra, Algebraic Algorithms and Error-Correcting Codes? (AAECC-9), New Orleans, Lecture Notes in Comp. Sci. Vol. 539, pp. 218-223. Berlin, Heidelberg, New York: Springer 1991 · Zbl 0767.94015
[14] Lachaud, G., Stern, J., Polynomial-time construction of codes II: spherical codes and the kissing number of spheres (to appear) · Zbl 0813.94024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.