Good Ensembles of Goppa Codes

It is well-known that random error-correcting codes achieve the Gilbert-Varshamov bound with high probability. In [2], the authors describe a construction which can be used to yield a polynomially large family of codes of which a large fraction achieve the Gilbert-Varshamov bound. In this project, we investigate ways to obtain codes known to achieve this bound, given such a family of codes. Since computing the minimum distance of a code is NP-hard, we work with a class of Goppa codes described in [1] whose minimum distance is known. We know that there exist Goppa codes which achieve the Gilbert-Varshamov bound, but we do not know if there are codes in this class which achieve it. We investigate various approaches to determining the rate of a code and try to apply them to this class of codes in order to determine if they achieve the Gilbert-Varshamov bound. These approaches include investigating upper bounds on the covering radius of a code and refining an existing lower bound on the code dimension. We also implemented the described class of Goppa codes using the PARI/GP computer algebra system [5], in order to obtain numerical values which would allow us to detect patterns and formulate conjectures regarding those codes