Document Zbl 1364.68190

On the snake-in-the-box codes for rank modulation under Kendall’s \(\tau \)-metric. (English) Zbl 1364.68190

Des. Codes Cryptography 83, No. 2, 455-465 (2017).

Summary: For exactly and efficiently representing and storing data in flash memories, the rank modulation scheme has been presented. In this scheme, Gray codes over the permutations are important, which are used to represent information in flash memories. For a Gray code, two consecutive codewords are obtained using one “push-to-the-top” operation. Specially, a snake-in-the-box code under the Kendall’s \(\tau \)-metric is a Gray code, which is capable of detecting one Kendall’s \(\tau \)-error. In this paper, we consider only the Kendall’s \(\tau \)-metric on the permutations. And we answer one open problem proposed by M. Horovitz and T. Etzion [IEEE Trans. Inf. Theory 60, No. 11, 7016–7025 (2014; Zbl 1360.94376)]. That is, we prove that the length of the longest snake in \(S_{2n+2}\) is longer than the length of the longest snake in \(S_{2n+1}\).

Cited in 5 Documents

MSC:

94A14	Modulation and demodulation in information and communication theory
68P30	Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94B25	Combinatorial codes

Keywords:

flash memory; rank modulation; Gray codes; push-to-the-top operations; snake-in-the-box codes

Citations:

Zbl 1360.94376

Cite Review PDF

Full Text: DOI

References:

[1]	Abbott H.L., Katchalski M.: On the snake in the box problem. J. Comb. Theory Ser. B 45, 13-24 (1988). · Zbl 0662.05034
[2]	Barg A., Mazumdar A.: Codes in permutations and error correction for rank modulation. IEEE Trans. Inf. Theory 56, 3158-3165 (2010). · Zbl 1366.94657
[3]	Buzaglo S., Etzion T.: Bounds on the size of permutation codes with the Kendall \[\tau\] τ-metric. IEEE Trans. Inf. Theory 61, 3241-3250 (2015). · Zbl 1359.94784
[4]	Deza M., Huang H.: Metrics on permutations, a survey. J. Comb. Inf. Sys. Sci. 23, 173-185 (1988). · Zbl 1217.05038
[5]	Farnoud F., Skachek V., Milenkovic O.: Error-correction in falsh memories via codes in the Ulam metric. IEEE Trans. Inf. Theory 59, 3003-3020 (2013). · Zbl 1364.94711
[6]	Gad E.E., Langberg M., Schwartz M., Bruck J.: Constant-weight Gray codes for local rank modulation. IEEE Trans. Inf. Theory 57, 7431-7442 (2011). · Zbl 1365.94508
[7]	Gad E.E., Langberg M., Schwartz M., Bruck J.: Generalized gray codes for local rank modulation. IEEE Trans. Inf. Theory 59, 6664-6673 (2013). · Zbl 1364.94195
[8]	Gray F.: Pulse code communication. U.S. Patent 2632058 (1953).
[9]	Horvitz M., Etzion T.: Constructions of snake-in-the-box codes for rank modulation. IEEE Trans. Inf. Theory 60, 7016-7025 (2014). · Zbl 1360.94376
[10]	Jiang A., Mateescu R., Schwartz M., Bruck J.: Rank modulation for flash memories. IEEE Trans. Inf. Theory 55, 2659-2673 (2009). · Zbl 1367.94121
[11]	Jiang A., Schwartz M., Bruck J.: Correcting charge-constrained errors in the rank-modulation scheme. IEEE Trans. Inf. Theory 56, 2112-2120 (2010). · Zbl 1366.94767
[12]	Kløve T., Lin T.T., Tsai S.C., Tzeng W.G.: Permutation arrays under the Chebyshev distance. IEEE Trans. Inf. Theory 56, 2611-2617 (2010). · Zbl 1366.94761
[13]	Savage C.D.: A survey of combinatorial gray codes. SIAM Rev. 39, 605-629 (1997). · Zbl 1049.94513
[14]	Savage C.D., Winkler P.: Monotone gray codes and middle levels problem. J. Comb. Theory Ser. A 70, 230-248 (1995). · Zbl 0827.05039
[15]	Tamo I., Schwartz M.: Correcting limited-magnitude errors in the rank-modulation scheme. IEEE Trans. Inf. Theory 56, 2551-2560 (2010). · Zbl 1366.94672
[16]	Yehezkeally Y., Schwartz M.: Snake-in-the-box codes for rank modulation. IEEE Trans. Inf. Theory 58, 5471-5483 (2012). · Zbl 1364.94648
[17]	Zhang Y.W., Ge G.N.: Snake-in-the-box codes for rank modulation under Kendall’s \[\tau\] τ-metric. IEEE Trans. Inf. Theory 62, 151-158 (2016). · Zbl 1359.94918

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.