We study the list-decoding problem of alternant codes (which includes obviously that of classical Goppa codes). The major consideration here is to take into account the (small) size of the alphabet. This amounts to comparing the generic Johnson bound to the q-ary Johnson bound. The most favourable case is q = 2, for which the decoding radius is greatly improved. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, we acknowledge that it can be made up from separate previous sources, which may be a little bit unknown, and where the binary Goppa codes has apparently not been thought at. Only D. J. Bernstein has treated the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous and simplified treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength n, when decoding e-away of the relative maximum decoding radius.
展开▼
机译：我们研究了交替码的列表解码问题（显然包括经典的Goppa码）。这里主要考虑的是要考虑字母的（小）大小。这相当于将通用Johnson绑定与qary Johnson绑定进行比较。最有利的情况是q = 2，其解码半径大大提高。尽管已公布的结果（二进制Goppa码的列表解码半径）是新的，但我们承认它可以由单独的先前来源组成，这可能有点未知，而且二进制Goppa码显然在哪里没想到。只有D. J. Bernstein在预印本中处理过二进制Goppa码的情况。引言中给出了参考。我们提出了一种自主和简化的处理方法，并且还对所研究算法进行了复杂性分析，当解码相对最大解码半径的e-away时，其块长为n二次方。
展开▼
