DocumentCode :
1757719
Title :
Constructions of Snake-in-the-Box Codes for Rank Modulation
Author :
Horovitz, Michal ; Etzion, Tuvi
Author_Institution :
Dept. of Comput. Sci., Technion - Israel Inst. of Technol., Haifa, Israel
Volume :
60
Issue :
11
fYear :
2014
fDate :
Nov. 2014
Firstpage :
7016
Lastpage :
7025
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 T-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/√(π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 S2n+1. The direct construction was applied successfully for S7 and S9, and hence lim;n→∞ M2n+1/S2n+1 ≈0.4743.
Keywords :
Gray codes; error detection codes; modulation coding; Gray code; Kendall´s T-metric; codeword; distance measurement; flash memory; rank modulation scheme; recursive method; single error detection; snake-in-the-box code construction; Ash; Context; Indexes; Measurement; Modulation; Reflective binary codes; Tin; 3-uniform hypergraph; Flash memory; Gray code; necklaces; push-to-the-top; pushto- the-top; rank modulation scheme; snake-in-the-box code; spanning tree;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2014.2359193
Filename :
6914565
Link To Document :
بازگشت