Snake-in-the-Box Codes for Rank Modulation

DOI10.1109/TIT.2012.2196755MaRDI QIDQ2989856zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yonatan Yehezkeally, Moshe Schwartz

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.3372

Mathematics Subject Classification ID

Modulation and demodulation in information and communication theory (94A14) Combined modulation schemes (including trellis codes) in coding theory (94B12)

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 $au$-metric, which applies to charge-constrained errors, and the $el{l}_{i}nfty$-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.

Recommendations

• Constructions of Snake-in-the-Box Codes for Rank Modulation
• Perfect Snake-in-the-Box Codes for Rank Modulation
• Snake-in-the-Box Codes for Rank Modulation Under Kendall’s $\tau $ -Metric
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• Snake-in-the-Box Codes for Rank Modulation under Kendall’s <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math> </inline-formula>-Metric in <inline-formula> <tex-math notation="LaTeX">$S_{2n+2}$ </tex-ma
• scientific article; zbMATH DE number 2154157
• scientific article; zbMATH DE number 36687
• Constructions of Rank Modulation Codes
• scientific article; zbMATH DE number 1498820

Cited in

(15)

• A new lower bound for snake-in-the-box codes
• Isomorphism of maximum length circuit codes
• Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
• Covering radius of permutation groups with infinity-norm
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Snakes, coils, and single-track circuit codes with spread \(k\)
• Exhaustive search for snake-in-the-box codes
• New formulations and branch-and-cut procedures for the longest induced path problem
• scientific article; zbMATH DE number 2154157 (Why is no real title available?)
• On the maximum length of coil-in-the-box codes in dimension 8
• Space-optimal quasi-Gray codes with logarithmic read complexity
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• New nonexistence results on perfect permutation codes under the Hamming metric
• MIP formulations for induced graph optimization problems: a tutorial
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric

This page was built for publication: Snake-in-the-Box Codes for Rank Modulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989856)