The Taub Faculty of Computer Science Events and Talks

Snake-in-the-box code is a Gray code which is capable to detect a single error. Gray codes are important in the context of 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 talk the Kendall's $\tau$-metric is used. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length $((2n+1)2n-1) M$ for permutations of $S_{2n+1}$ from a snake of length $M$ for permutations of $S_{2n-1}$. We present a direct construction based on necklaces which might yield snakes of length $\frac{(2n+1)!}{2}-2n+1$ for permutations of $S_{2n+1}$. The construction is applied successfully for $S_7$ and $S_9$.