Snake-in-the-Box Codes for Rank Modulation

Abstract

Motivated by the rank-modulation scheme with applications to flash memory, we consider Gray codes capable of detecting a single error, also known as snake-in-the-box codes. We study two error metrics: Kendall's $\tau$-metric, which applies to charge-constrained errors, and the ${\ell }_{\infty }$-metric, which is useful in the case of limited magnitude errors. In both cases we construct snake-in-the-box codes with rate asymptotically tending to 1. We also provide efficient successor-calculation functions, as well as ranking and unranking functions. Finally, we also study bounds on the parameters of such codes.

References in corpus (3)

• Codes in Permutations and Error Correction for Rank Modulation
• Constructions of Rank Modulation Codes
• Compressed Encoding for Rank Modulation

Cited by in corpus (11)

• Secure Index Coding: Existence and Construction
• Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation
• New formulations and branch-and-cut procedures for the longest induced path problem
• Constructions of Snake-in-the-Box Codes under ${\ell }_{\infty }$-metric for Rank Modulation
• Snake-in-the-Box Codes for Rank Modulation under Kendall's $\tau$-Metric
• The Maximum Length and Isomorphism of Circuit Codes with Long Bit Runs
• LP-decodable multipermutation codes
• Master's thesis: Permutations With Restricted Movement
• Infinity-Norm Permutation Covering Codes from Cyclic Groups
• Constructions of Snake-in-the-Box Codes for Rank Modulation
• Nonexistence of perfect permutation codes under the Kendall τ-metric