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) [1] 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 Høholdt, 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 Geilʼs bound when applied to primary one-point algebraic geometric codes.