PaperlayerView exact revision on arXiv

Source-linked AI summary

Codes in Permutations and Error Correction for Rank Modulation

Alexander Barg, Arya Mazumdar

arXiv:0908.4094v3cs.IT

TL;DR

Rank modulation needs error-correcting codes for flash-memory data represented by permutations under Kendall tau distance. This paper derives bounds and constructions that establish optimal-code scaling and codes within a constant factor of the sphere-packing bound for any fixed number of errors.

  • Problem

    Rank modulation uses relative cell charges in flash memories, but coding bounds and code families for correcting Kendall errors remain limited.

  • Method

    The paper studies rank permutation codes as subsets of permutations equipped with Kendall tau distance, using inversion vectors and bounds on code size and sphere volumes.

  • Results

    For distance d ∼ n^(1+ε), 0 < ε < 1, optimal code size scales as exp((1 − ε)n ln n), and fixed-error codes can be within a constant factor of the sphere-packing bound.

  • Takeaways & Limitations

    The results establish exact large-n scaling across intermediate distance regimes and construct t-error-correcting codes of order O(n!/n^t).

Abstract

from arXiv · show

Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of $n$ elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of $n$. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.

I. INTRODUCTION

The paper studies rank permutation codes in the Kendall tau metric as error protection for rank modulation, including flash-memory storage. It derives bounds and constructions that characterize optimal-code scaling and approach sphere-packing performance for fixed error counts.

  • I. INTRODUCTION: Codes in permutations are classical, but this work focuses on the Kendall tau metric rather than the more commonly studied Hamming distance.The Kendall tau distance counts adjacent transpositions needed to transform one permutation into another.
  • I. INTRODUCTION: Rank modulation stores information in the relative ranks of cell charges, making Kendall distance relevant to drift and rewriting constraints in flash memory.Different charge-drift speeds motivate tracking relative values of adjacent cells.
  • I. INTRODUCTION: Earlier sphere analyses did not yield nontrivial code rates, while prior constructions covered only single-error-correcting codes of size at least (1/2)(n−1)!.The paper addresses both the bounds problem and the limited range of prior code constructions.
  • I. INTRODUCTION: The paper derives Singleton-type and sphere-packing bounds for rank permutation codes and analyzes their asymptotic behavior.These bounds are used to study how optimal code size scales with n.
  • I. INTRODUCTION: For d ∼ n^(1+ε), 0 < ε < 1, optimal code size scales as exp((1−ε)n ln n), covering the intermediate regime between d = O(n) and d = Θ(n^2).The two endpoint regimes correspond to close-to-one and vanishing proportions of the permutation space, respectively.
  • I. INTRODUCTION: A family correcting a constant number of errors has size within a constant factor of the sphere-packing bound, using the Bose-Chowla theorem.The construction is presented as a rank permutation code family.

II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL

The Kendall space is analyzed through permutation weights, inversions, and embeddings into related metric spaces. These representations transfer code constructions and distance information while exposing where exact distance preservation does and does not hold.

  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: Kendall tau distance is right-invariant, so permutation weight can be defined as distance from the identity.Right multiplication preserves pairwise Kendall distances.
  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: The Kendall graph is regular of degree n−1 but not distance-regular, limiting the direct use of algebraic-combinatorics machinery.Its diameter is N and is attained by opposite permutations.
  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: The inversion count equals the Kendall distance from a permutation to the identity and provides the main tool for studying the metric.For two permutations, their distance is expressed through the inversion count of a relative permutation.
  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: The inversion-vector mapping is one-to-one and weight-preserving, allowing permutations to be reconstructed from vectors in G_n.The associated coordinates record inversion counts at successive positions.
  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: An ℓ1-distance construction on inversion vectors yields Kendall-distance codes of at least the same size and distance.The transfer follows from the weaker distance relation, although the mapping is not fully distance-preserving.
  • II. WEIGHT-PRESERVING EMBEDDINGS OF THE KENDALL: A second mapping records every pairwise inversion in a binary vector, giving an isometry from X_n to a subset of Hamming space of dimension N.The binary Hamming weight equals the permutation's inversion count.

III. BOUNDS ON THE SIZE OF RANK PERMUTATION CODES

The paper defines code size and rate in the Kendall space and establishes the asymptotic capacity across distance-growth regimes. The resulting rate transitions from one to zero as required distance grows from linear to quadratic scale.

  • III. BOUNDS ON THE SIZE OF RANK PERMUTATION CODES: An (n, M, d) code contains M permutations whose pairwise Kendall distances are at least d, and A(n, d) denotes the maximum possible M.The rate is normalized by ln n! for asymptotic analysis.
  • III. BOUNDS ON THE SIZE OF RANK PERMUTATION CODES: The asymptotic rate is 1 when d = O(n), 1−ε when d = Θ(n^(1+ε)) for 0 < ε < 1, and 0 when d = Θ(n^2).These regimes give the exact scaling of optimal rank permutation code size.
  • III. BOUNDS ON THE SIZE OF RANK PERMUTATION CODES: The intermediate rate 1−ε remains valid under the weaker condition d = n^(1+ε)α(n), where α(n) grows slower than every positive power of n.The condition broadens the stated Θ(n^(1+ε)) regime.

A. A Singleton bound

The Singleton-bound analysis reduces a code in S_n to smaller permutation spaces through deletion maps. Right invariance and asymptotic estimates then produce a nontrivial bound in the relevant distance range.

  • A. A Singleton bound: Right invariance permits assuming that any (n, M, d) code contains the identity permutation.This normalization simplifies the subsequent projection argument.
  • A. A Singleton bound: For k ≤ n, the map φ_k deletes elements k+1 through n while preserving the relative order of the first k elements.The image is a code C_k in S_k derived from the original code.
  • A. A Singleton bound: Choosing the greatest k for which φ_k is non-injective makes φ_(k+1) injective and yields M ≤ (k+1)!.The injectivity transition is the combinatorial core of the Singleton-style argument.
  • A. A Singleton bound: The resulting estimate is nontrivial when d > n−1.This is the stated condition under which the bound improves over a trivial estimate.
  • A. A Singleton bound: For d = δN, the asymptotic bound contains a factor that can be improved from 1−δ to a quantity decaying as (ln n)^−1.The improvement is established in the following section.

B. Sphere packing bounds

Sphere-packing analysis relates Kendall-space code bounds to inversion counts in permutations. Explicit and asymptotic inversion-count results determine the capacity scaling at small and large distances.

  • Inversion counts determine sphere volumes and connect sphere-packing bounds in Kendall space to code-size estimates.The section studies how the number of permutations with a given inversion count controls asymptotic behavior of C(d).
  • The inversion count of a random permutation is asymptotically Gaussian, suggesting that codes with distance greater than the central inversion level cannot have large size.The section states that this implication is established in Sect. III-D.
  • For 1 ≤ k ≤ n, the number of permutations with k inversions is given explicitly through the coefficients of the generating function.The expression uses binomial coefficients and generalized pentagonal-number indices u_j.
  • |B1| = n, and A(n, 3) ≤ (n − 1)! follows from the inversion-count expression.
  • For k = O(n), K_n(k) ≤ exp(c1n), while for k = Θ(n^2), K_n(k) = n! / exp(c2n).The constants c1 and c2 exist, and their implicit values are available in the cited references.
  • These asymptotic inversion-count bounds yield the two boundary cases of the expression for C(d).

C. Bounds from embedding in the ℓ1 space

The paper bounds Kendall-space code sizes by embedding permutations into an ℓ1 space and comparing metric-ball volumes. This approach supplies explicit bounds and establishes the middle asymptotic capacity regime.

  • Embedding X_n into H_n with the ℓ1 metric provides both lower and upper code-size bounds through ℓ1-ball volumes.The upper bound uses the Hamming bound, while the lower bound uses a Gilbert construction.
  • A Kendall-distance-d code induces an ℓ1-distance-d code after inversion, while an ℓ1-distance-d code induces Kendall distance at least d/2.
  • Proposition 3.4 bounds A(n, d) using metric balls in H_n, with t = floor((d − 1)/2).The upper bound follows from the Hamming bound and the lower bound from a Gilbert procedure in the permutation space.
  • The ball-mapping lemma gives an injection from a ball centered at 1 into a ball centered at any y, while at most 2n points share an image in the reverse comparison.
  • For r < n^2 / ln n, Lemma 3.7 supplies inequalities used to estimate the asymptotic behavior of the embedding-based bound.
  • When d = Θ(n^(1+ε)) for 0 ≤ ε < 1, the resulting lower bound is C(d) ≥ 1 − ε.

D. Bounds from embedding in Hamming space

Embedding the Kendall space into a Hamming space transfers known coding bounds and constructions, but the resulting existence bounds do not close the gap to sphere-packing upper bounds.

  • Embedding and transferred bounds: Codes in Xn with distance greater than the average satisfy |C| = O(N).This follows from applying the Plotkin bound after embedding into HN.
  • Existence from binary codes: A binary linear [N, k, d] code yields a rank permutation code of size at least n!/2^(N−k) with distance d.At least one coset contains enough vectors that map back to valid permutations.
  • Existence from binary codes: A t-error-correcting BCH code gives a rank permutation code of size n! with dimension at least N − t log2(N + 1).The construction uses a BCH code of length N, adding zeros if necessary.
  • Gap to sphere packing: The sphere-packing bound gives M ≤ O(n!/n^t), leaving a gap that the Hamming embedding cannot close.A different construction is introduced to achieve the sphere-packing order within a constant factor.

IV. TOWARDS OPTIMAL t-ERROR-CORRECTING CODES

The paper constructs t-error-correcting rank permutation codes through additive-error codes on inversion vectors, using Bose–Chowla-based syndromes. The resulting codes have size within a constant factor of the sphere-packing order for fixed t.

  • Construction framework: The construction represents permutations by inversion vectors and seeks codes correcting additive errors in ℓ1 distance.An inequality between code distances transfers additive-error correction from inversion vectors to rank permutation codes.
  • Construction framework: A code corrects t additive errors exactly when all syndromes of error vectors with ℓ1 weight at most t are distinct and nonzero modulo m.This criterion is the operational basis for constructing the integer codes.
  • Bose–Chowla construction: The Bose–Chowla theorem supplies integers whose bounded multisums are distinct modulo m, yielding asymmetric t-additive-error correction.The theorem’s distinct-sum property is then extended to the symmetric-error construction.
  • Bose–Chowla construction: Choosing q + 1 = n − 1 and using the resulting group code, a coset contains at least M ≥ n!/m_t valid inversion vectors.The coset partition argument supplies a large subset of valid permutations.
  • Main construction result: For n − 2 a prime power, a t-error-correcting rank permutation code has size at least n!/[t(t + 1)m] for odd t and n!/[t(t + 2)m] for even t.Here m = ((n − 2)^(t + 1) − 1)/(n − 3).
  • Main construction result: The construction achieves size O(n!/n^t), matching the sphere-packing order up to a constant factor.The constant-factor loss is attributed to using an integer alphabet rather than the more restricted product alphabet.
  • Main construction result: The construction is explicit except for selecting a large-size code in one coset during the final step.The existence claim for that coset is not accompanied by an explicit selection procedure.
Loading 0908.4094v3…