Back to Search
Start Over
Constructions of Snake-in-the-Box Codes for Rank Modulation.
- Source :
- IEEE Transactions on Information Theory; Nov2014, Vol. 60 Issue 11, p7016-7025, 10p
- Publication Year :
- 2014
-
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 using the push-to-the-top operation, and distance measure is defined on permutations. In this paper, the Kendall’s \(\tau \) -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 \(M_{2n+1}=((2n+1)(2n)-1)M_{2n-1}\) for permutations of \(S_{2n+1}\) , from a snake of length \(M_{2n-1}\) for permutations of \(S_{2n-1}\) . Thus, we have \(\lim \limits _{n\to \infty }{M_{2n+1}}/{S_{2n+1}}\approx 0.4338\) , improving on the previous known ratio of \(\lim \limits _{n\to \infty }{1}/\sqrt {{({\pi n})}}\) . 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 \(S_{2n+1}\) . The direct construction was applied successfully for \(S_{7}\) and \(S_{9}\) , and hence \(\lim \limits _{n\to \infty } {M_{2n+1}}/{S_{2n+1}}\approx 0.4743\) . [ABSTRACT FROM PUBLISHER]
- Subjects :
- GRAY codes
MODULATION coding
PERMUTATIONS
FLASH memory
HYPERGRAPHS
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 60
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 99041698
- Full Text :
- https://doi.org/10.1109/TIT.2014.2359193