A Construction of Permutation Codes From Rational Function Fields and Improvement to the Gilbert-Varshamov Bound

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert-Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert-Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number n of a symbol length, this class of permutation codes improves the Gilbert-Varshamov bound by a factor n asymptotically for a minimum distance d with d = O(root n). Furthermore, for a constant minimum distance d, we improve the Gilbert-Varshamov bound by a factor n as well as the recent one given by Gao et al. by a factor n/log n asymptotically for all sufficiently large n.