Snake-in-the-Box Codes for Rank Modulation Under Kendall’s $\tau $ -Metric
Yiwei Zhang, Gennian Ge · IEEE Transactions on Information Theory · 2015
For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations, and two consecutive codewords are obtained using a push-to-the-top operation. We consider the snake-in-the-box code under Kendall’s$\tau $-metric, which is a Gray code capable of detecting one Kendall’s$\tau $-error. We answer two open problems posed by Horovitz and Etzion. First, we prove the validity of a construction given by them, resulting in a snake of size$M_{2n+1}=({(2n+1)!}/{2})-2n+1$. Second, we come up with a different construction aiming at a larger snake of size$M_{2n+1}=({(2n+1)!}/{2})-2n+3$. The construction is applied successfully to$S_{7}$.