On the Labeling Problem of Permutation Group Codes under the Infinity Metric

Details On the Labeling Problem of Permutation Group Codes under the Infinity Metric On the Labeling Problem of Permutation Group Codes under the Infinity Metric

2011-02-14

arxiv.org/abs/1102.2702v2

Computer Science

Information Theory

Scientific paper

Codes over permutations under the infinity norm have been recently suggested as a coding scheme for correcting limited-magnitude errors in the rank modulation scheme. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding/decoding procedures, and then optimize the code's minimal distance via relabeling. We formally define the relabeling problem, and show that all codes may be relabeled to get a minimal distance at most 2. The decision problem of whether a code may be relabeled to distance 1 is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved hard to approximate. Finally, we consider general bounds on the relabeling problem. We specifically show the optimal relabeling distance of cyclic groups. A specific case of a general probabilistic argument is used to show $\agl(p)$ may be relabeled to a minimal distance of $p-O(\sqrt{p\ln p})$.

Affiliated with

Also associated with

No associations

Rating

On the Labeling Problem of Permutation Group Codes under the Infinity Metric does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Labeling Problem of Permutation Group Codes under the Infinity Metric, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Labeling Problem of Permutation Group Codes under the Infinity Metric will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215264