Constructions of Snake-in-the-Box Codes for Rank Modulation

DOI10.1109/TIT.2014.2359193MaRDI QIDQ2983344zbMATH OpenFDO

Authors Michal Horovitz, Tuvi Etzion

Publication date 16 May 2017

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

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Other types of codes (94B60) Modulation and demodulation in information and communication theory (94A14)

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 by using the "push-to-the-top" operation, and the distance measure is defined on permutations. In this paper the Kendall's $au$-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 $limlimit{s}_{noinfty}frac{M}_{2n+1}{S}_{2n+1}approx0.4338$, improving on the previous known ratio of $limlimit{s}_{noinfty}frac1sqrtpin$. By using the general method we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length $frac(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 $limlimit{s}_{noinfty}frac{M}_{2n+1}{S}_{2n+1}approx0.4743$.

Cited in

(8)

• scientific article; zbMATH DE number 2154157 (Why is no real title available?)
• Snake-in-the-Box Codes for Rank Modulation
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• A new non-asymptotic upper bound for snake-in-the-box codes
• A new lower bound for snake-in-the-box codes
• Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
• scientific article; zbMATH DE number 2154135 (Why is no real title available?)
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric

This page was built for publication: Constructions of 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 Q2983344)