Snake-in-the-Box Codes for Rank Modulation under Kendall’s $\tau $ -Metric in $S_{2n+2}$
Yiwei Zhang, Gennian Ge · IEEE Transactions on Information Theory · 2016
Snake-in-the-box codes under Kendall’s$\tau $-metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in$S_{n}$with minimal Kendall’s$\tau $-distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in$S_{2n+1}$. As for$S_{2n+2}$, this framework keeps the last element fixed, and thus, a snake in$S_{2n+2}$is equivalent to a snake in$S_{2n+1}$, which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s$\tau $-distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in$S_{2n+2}$is not larger than the size of the largest snake in$S_{2n+1}$. A first step toward this problem is a negative answer by Wang and Fu, who construct a snake in$S_{2n+2}$with exactly one more permutation than an optimal snake in$S_{2n+1}$. In this paper, we give an explicit construction of a snake in$S_{2n+2}$with size asymptotically approaching$({1}/{4})|S_{2n+2}|$.