A New Lower Bound for Permutation Codes Using Reed–Solomon Codes

Abstract

We present a constructive lower bound for permutation codes under Kendall’s τ-metric that improves upon the classical Gilbert-Varshamov estimate for many parameters. For any length p > 5, we construct codes with minimum Kendall’s τ-distance 6 and size at least p!/p3. This result is achieved by proving that Reed-Solomon codes of length p and dimension p-3 have a minimum Lee distance of 6, and then applying a metric embedding from the Lee metric to the Kendall’s τ-metric. © 2013 IEEE.