Feng-Rao decoding of primary codes

摘要

We show that the Feng-Rao bound for dual codes and a similar bound by Andersen and Geil (2008) [lj for primary codes are consequences of each other. This implies that the Feng-Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique applies to any linear code for which information on well-behaving pairs is available. Consequently we are able to decode efficiently a large class of codes for which no non-trivial decoding algorithm was previously known. Among those are important families of multivariate polynomial codes. Matsumoto and Miura (2000) [30] (see also Beelen and Haholdt, 2008 [3]) derived from the Feng-Rao bound a bound for primary one-point algebraic geometric codes and showed how to decode up to what is guaranteed by their bound. The exposition in Matsumoto and Miura (2000) [30] requires the use of differentials which was not needed in Andersen and Geil (2008) [1]. Nevertheless we demonstrate a very strong connection between Matsumoto and Miura's bound and Andersen and Ceil's bound when applied to primary one-point algebraic geometric codes.