Search

Abstract: The celebrated Feng–Rao bound estimates the minimum distance of codes defined by means of their parity check matrices. From the Feng–Rao bound it is clear how to improve a large family of codes by leaving out certain rows in their parity check matrices. In this paper we derive a simple lower bound on the minimum distance of codes defined by means of their generator matrices. From our bound it is clear how to improve a large family of codes by adding certain rows to their generator matrices. The new bound is very much related to the Feng–Rao bound as well as to Shibuya and Sakaniwa''s bound in [T. Shibuya, K. Sakaniwa, A dual of well-behaving type designed minimum distance, IEICE Trans. Fund. E84-A (2001) 647–652]. Our bound is easily extended to deal with any generalized Hamming weights. We interpret our methods into the setting of order domain theory. In this way we fill in an obvious gap in the theory of order domains. [Copyright &y& Elsevier]

The main results of this paper are derived by using only simple Gro¨bner basis techniques. We present a new construction of evaluation codes from Miura–Kamiya curves Cab. We estimate the minimum distance of the codes and estimate the minimum distance of a class of related one-point geometric Goppa codes. With respect to these estimates the new codes perform at least as well as the related geometric Goppa codes. In particular we consider codes from norm–trace curves. We show that our estimates give actually the true minimum distance of these codes. The new codes from norm–trace curves perform rather well. In many cases much better than the corresponding geometric Goppa codes. It turns out that an alternative description of the new codes from norm–trace curves can be made by using Høholdt et al.'s in: V.S. Pless, W.C. Huffman (Eds.), Handbook of Coding Theory, Vol. 1, Elsevier, Amsterdam, 1998, pp. 871–961 (Chapter 10) construction of improved dual codes. [Copyright &y& Elsevier]

We generalize the unique decoding algorithm for one-point AG codes over the Miura–Kamiya C a b curves proposed by Lee et al. (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng–Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010) . It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals ( Beelen and Brander, 2010; Guruswami and Sudan, 1999 ) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs. [ABSTRACT FROM AUTHOR]

We generalize the list decoding algorithm for Hermitian codes proposed by Lee and OʼSullivan (2009) based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander (2010). Our generalization enables us to apply the fast algorithm to compute a Gröbner basis of a module proposed by Lee and OʼSullivan (2009), which was not possible in another generalization by Lax (2012). [ABSTRACT FROM AUTHOR]