@comment{ generated by }
@Unpublished{ALGO-STUDENT-2007-006,
abstract = {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.},
affiliation = {EPFL},
author = {Maatouk, Ghid},
details = {http://infoscience.epfl.ch/record/101083},
documenturl = {https://infoscience.epfl.ch/record/101083/files/maatouk_report.pdf},
oai-id = {oai:infoscience.epfl.ch:101083},
oai-set = {driver},
status = {PUBLISHED},
title = {Good {E}nsembles of {G}oppa {C}odes},
unit = {ALGO},
year = 2007
}