1Constructions of Snake-in-the-Box Codes for Rank Modulation

Abstract—Snake-in-the-box code is a Gray code which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme which was suggested recently for representing information in flash memories. For a Gray code in this scheme the codewords are permutations, two consecutive codewords are obtained by using the ”push-to-the-top ” operation, and the distance measure is defined on permutations. In this paper the Kendall’s τ-metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length M2n+1 = ((2n+1)(2n)−1)M2n−1 for permutations of S2n+1, from a snake of length M2n−1 for permutations of S2n−1. Thus, we have lim n→∞ M2n+1 S2n+1 ≈ 0.4338, improving on the previous known ratio of lim n→∞ 1√ pin. By using the general method we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length (2n+1)! 2 − 2n + 1 for permutations of S2n+1. The direct construction was applied successfully for S7 and S9, and hence lim n→