PaperlayerView exact revision on arXiv

Source-linked AI summary

Order-Optimal Systematic Permutation Codes for Correcting t Deletions

Bolin Wu, Quan D. Bui, Kai Niu, Van Khu Vu, Shuche Wang

arXiv:2609.37578v1cs.ITmath.IT

TL;DR

The paper asks how to build full-systematic permutation codes that correct fixed-t deletions with O(t) redundancy markers and polynomial-time encoding and decoding. It embeds a deletion-correcting syndrome in marker positions, achieving order-optimal redundancy for both deletion models.

  • Problem

    The paper asks how to build full-systematic permutation codes correcting fixed t deletions with O(t) redundancy markers and polynomial-time encoding and decoding.

    Source: §I · p. 2

  • Method

    An inner deletion-correcting syndrome is encoded in the relative positions of distinct redundancy markers using an algebraic outer code.

    Source: A. The Outer-Code Framework as a… · p. 24

  • Results

    (7t −1) log n + O_t(1) bits for PIDs and 4t log n + O_t(1) bits for SIDs are order-optimal redundancies with uniform polynomial-time encoding and decoding.

    Source: §VII · p. 26

  • Takeaways & Limitations

    Embedding the syndrome in marker positions circumvents the impossibility of appending conventional checksum suffixes to permutations.

    Source: §VII · p. 26

Abstract

from arXiv · show

This paper investigates the construction of full-systematic permutation codes capable of correcting multiple deletions under two complementary models, namely symbol-invariant deletions (SIDs), where surviving symbol values are preserved, and permutation-invariant deletions (PIDs), where the surviving sequence is standardized to a permutation. For any fixed integer $t \ge 1$ and all sufficiently large message lengths $n$, our proposed encoders map any message permutation of length $n$ to a codeword by inserting distinct redundancy symbols while strictly preserving the sequence order of the original message symbols. The proposed constructions correct up to $t$ deletions using $7t-1$ redundancy markers for PIDs and $4t$ redundancy markers for SIDs, achieving redundancies of $(7t-1)\log n + O_t(1)$ bits and $4t\log n + O_t(1)$ bits, respectively. Both code families are uniformly constructible, encodable, and decodable in $n^{O(t)}$ time. The underlying framework stores an inner deletion-correcting syndrome in the relative positions of redundancy markers via an algebraic outer code based on integer moments and residual graph coloring. We further extend this framework to fixed-composition and strictly $\lambda$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $\lambda > t$.

I. INTRODUCTION

Rank modulation represents information through relative order, but deletion errors create a need for systematic permutation codes that preserve each message as an unaltered subsequence. The paper develops constructions for SID and PID channels and extends them to multipermutations.

A. The SID and PID Deletion Models

  • SIDs preserve surviving symbol labels, whereas PIDs standardize the surviving sequence and conceal the original symbol values.For example, deleting 1 from (3, 1, 4, 2) yields (3, 4, 2) under SID and (2, 3, 1) under PID.Source: §I · p. 1

C. Organization of the Paper

  • The paper’s framework addresses the permutation constraint that conventional checksum suffixes cannot simply be appended without altering the permutation structure.The paper is organized into preliminaries, PID and SID constructions, multipermutation extensions, redundancy and complexity trade-offs, and a conclusion.Source: §I · p. 1, C. Organization of the Paper · p. 3

I. INTRODUCTION

  • The paper targets full-systematic codes that preserve every message permutation as an unaltered subsequence while adding distinct redundancy markers.Removing the markers recovers the message, and the goal is correction of fixed t deletions with O(t) markers and polynomial-time algorithms.Source: §I · pp. 1–2

A. Related Work and Problem Formulation

  • Earlier permutation deletion codes were non-systematic, and existing multiple-PID constructions were limited to single deletions or localized bursts.Systematic deletion codes for arbitrary composition profiles were also unaddressed in prior multipermutation work.Source: A. Related Work and Problem Formulation · p. 2

B. Main Contributions

  • The contributions include PID codes with (7t−1) log n + O_t(1) bits and SID codes with 4t log n + O_t(1) bits of redundancy.The paper also extends the framework to fixed-composition and strictly λ-regular multipermutations; for λ > t, PID and SID channels coincide.Source: B. Main Contributions · pp. 2–3

II. NOTATION AND PRELIMINARIES

  • The notation fixes t and uses logarithms to base two, with O_t and Ω_t constants allowed to depend on t but not blocklength.Here n denotes message length and r the number of redundancy symbols.Source: §II · p. 3

B. Permutation Codes and Systematicity

The paper formulates deletion-correcting permutation codes through confusability and systematicity, then develops a polynomial-time inner syndrome for multiple PIDs. Its construction uses graph coloring to compress syndrome classes while retaining their correction property.

C. Bounds and Benchmarks

  • The lower-bound parent counts differ because a SID descendant has O_t(m^t) possible parents, while a PID descendant has O_t(m^2t).PID standardization obscures the absolute values of deleted symbols.Source: C. Bounds and Benchmarks · p. 5

III. SYSTEMATIC CODES FOR PERMUTATION-INVARIANT DELETIONS

  • The PID construction combines an inner syndrome correcting up to t PIDs with an outer code that places it in 7t−1 marker positions.The inner syndrome has O_t(n^(6t−2)) possible values; integer moments narrow outer candidates to a constant-size list before greedy coloring.Source: §III · p. 6

A. A Polynomial-Time Inner PID Syndrome

  • Residual-graph coloring compresses the large Lehmer-rank coloring locally while preserving properness and hence PID correction within each color class.The residual graph has bounded, efficiently enumerable neighborhoods, enabling the algebraic fingerprinting approach.Source: A. A Polynomial-Time Inner PID Syndrome · pp. 6–8
  • Every class of the inner syndrome κ_n,t corrects up to t PIDs, and its syndrome space has size at most C_t n^(6t−2).The map, decoding procedure, and design parameters are computable in n^O(t) time.Source: A. A Polynomial-Time Inner PID Syndrome · p. 8

B. An Algebraic Outer Code for PID

The PID outer code represents marker locations as labeled gaps and maps standardized deletion outputs to a channel over these patterns. This projection removes dependence on surviving message-symbol values, enabling protection of the marker-position syndrome.

B. An Algebraic Outer Code for PID

1) Canonical labeled-gap words:

  • In a labeled-gap word, coordinate z_j gives the number of data placeholders preceding marker j.Markers at each gap are ordered by label, and substituting the message symbols for placeholders produces the full-systematic permutation.Source: 1) Canonical labeled-gap words · p. 8

2) The projected PID outer channel:

  • After up to t PIDs, the projected output depends on the marker-gap vector and deleted data positions, not on surviving data values.The projection captures the channel’s deletion pattern by masking and relabeling surviving markers.Source: 2) The projected PID outer channel · p. 9

3) Moment checks and constant-list reduction:

Integer moment checks reduce the possible marker-gap vectors to a constant-size list within each moment class, and residual graph coloring distinguishes vectors with intersecting projected outputs. The resulting outer partition supports the full-systematic PID construction.

3) Moment checks and constant-list reduction:

  • Within a moment class, an output word is consistent with only a constant number of marker-gap vectors, with the bound independent of n.The moments constrain visible gap coordinates; a nonsingular Vandermonde system uniquely determines the remaining coordinates for each fixed choice.Source: 3) Moment checks and constant-list… · pp. 9–10
  • The outer syndrome combines the moment vector with a greedy coloring of the residual graph, whose edges connect vectors sharing a projected output.Each syndrome class corrects the projected outer channel.Source: 3) Moment checks and constant-list… · p. 10
  • The outer code’s scaling exponent r−t is order-optimal for codes with mutually disjoint projected output sets.A deletion pattern removing the first t markers gives the matching upper-bound argument.Source: 3) Moment checks and constant-list… · p. 11

C. The Full-Systematic Construction

  • A common received PID output implies that the two underlying messages share a PID descendant after at most t deletions.The decoder first identifies the outer vector from the projected word, then uses its index to recover the inner syndrome and select the unique message candidate.Source: C. The Full-Systematic Construction · pp. 11–12
  • The full-systematic construction corrects up to t PIDs using 7t−1 markers and has uniform construction, encoding, and decoding algorithms running in n^O(t) time.The encoder preserves the message permutation as an unaltered subsequence.Source: C. The Full-Systematic Construction · p. 12

IV. SYSTEMATIC CODES FOR SYMBOL-INVARIANT DELETIONS

The SID construction stores an inner deletion-correcting syndrome in the relative positions of redundancy markers. Its inner syndrome uses cyclic successors and algebraic power-sum partitions to support efficient correction of up to t SIDs.

IV. SYSTEMATIC CODES FOR SYMBOL-INVARIANT DELETIONS

  • 4t redundancy markers yield a full-systematic code correcting up to t SIDs with 4t log n + O_t(1) bits of redundancy and n^O(t)-time construction, encoding, and decoding.The inner syndrome is stored in an outer code class; deleting the markers recovers the original message order.Source: §IV · p. 12

A. A Polynomial-Time Inner SID Syndrome

  • The inner SID syndrome is built from cyclic successors, and each syndrome class corrects up to t SIDs with syndrome evaluation and decoding in n^O(t) time.For n ≥ 3t, the construction uses the cyclic-successor mapping; its syndrome space has at most O_t(n^(3t−1)) values.Source: §IV · p. 12, A. A Polynomial-Time Inner SID Syndrome · pp. 13–14
  • Power-sum syndromes partition permutations into classes with minimum Hamming distance at least d, using at most p^(d−2) values and O(Nd) field operations.The distance follows from a nonsingular Vandermonde matrix over F_p; the construction uses an injective map into that field.Source: A. A Polynomial-Time Inner SID Syndrome · p. 13

B. Algebraic Outer Partition

The outer partition makes marker sequences correct up to t SIDs, while the full-systematic construction encodes the inner SID syndrome in marker positions. Together they provide efficient SID-correcting permutation codes.

C. The Full-Systematic SID Construction

B. Algebraic Outer Partition

  • Within an outer syndrome class, distinct vectors cannot share an SID descendant after at most t deletions.The SID output can be transformed into a projected outer-channel output, whose sets are disjoint within each syndrome class.Source: B. Algebraic Outer Partition · p. 14

C. The Full-Systematic SID Construction

  • 4t markers give a full-systematic code correcting up to t SIDs with 4t log n + O_t(1) bits of redundancy and n^O(t)-time construction, encoding, and decoding.The encoder selects an outer vector from the inner syndrome's rank and interleaves its markers with the message permutation.Source: C. The Full-Systematic SID Construction · p. 15

V. EXTENSION TO MULTIPERMUTATIONS

The paper extends systematic deletion-correcting codes to fixed-composition multipermutations, where repeated symbols require tie-preserving standardization and a stable lift. For strictly λ-regular profiles with λ > t, PID and SID channels coincide.

V. EXTENSION TO MULTIPERMUTATIONS

  • For strictly λ-regular profiles with λ > t, no symbol class can be fully deleted within t deletions, so PID and SID channels coincide.The extension addresses fixed-composition and strictly regular multipermutations.Source: §V · p. 16

A. Deletion Models in Multipermutation and the Stable Lift

  • PID standardization can conceal which symbol classes disappeared, so the construction uses profile-dependent ambiguity to handle the resulting uncertainty.A PID descendant has at most B_s(m) s! parents, while an SID descendant has at most s!; parents can be enumerated in n^O(s) time.Source: §V · p. 16, A. Deletion Models in Multipermutation… · p. 17
  • For either deletion model, sharing a descendant after at most t deletions is equivalent to sharing one after exactly t deletions when n > t.For PIDs, the reduction deletes the same additional positions from both sequences and uses tie-preserving standardization.Source: A. Deletion Models in Multipermutation… · p. 16
  • A canonical stable lift connects multipermutation PIDs to the permutation PID framework by labeling repeated-symbol occurrences in order.The lift is a bijection onto a subspace of permutations and commutes with tie-preserving standardization of surviving positions.Source: A. Deletion Models in Multipermutation… · pp. 16–17

B. From a Single-Deletion Code to a t-Deletion Syndrome

The method amplifies a single-deletion-correcting syndrome into one that corrects t deletions. It combines residual graph coloring with local algebraic fingerprints and enumerates candidate parents for decoding.

B. From a Single-Deletion Code to a t-Deletion Syndrome

  • Residual graph coloring amplifies a syndrome whose classes correct one deletion into a syndrome whose classes correct up to t deletions.The construction colors residual graphs formed within each original syndrome class, with adjacency defined by sharing an exact-t descendant.Source: B. From a Single-Deletion Code to a… · p. 18
  • Local algebraic fingerprints produce a proper coloring using fewer than 64K^2 colors, and computing both fingerprints requires enumerating radius-two residual neighborhoods.Within each original syndrome class, equality under the second coloring excludes graph adjacency.Source: B. From a Single-Deletion Code to a… · p. 18
  • The decoder enumerates all parents of the received word and retains the unique candidate matching the syndrome; the resulting decoder runs in n^O(t) time.Residual graph neighborhoods and parent lists are enumerable in n^O(t) time.Source: B. From a Single-Deletion Code to a… · p. 18

C. Inner Syndromes for Multipermutation SIDs

The section constructs inner syndromes for multipermutation SID and PID correction. For PIDs, it gives a profile-sensitive construction and a lifted alternative, with the final construction choosing between them by required redundancy markers.

C. Inner Syndromes for Multipermutation SIDs

  • Within a fixed composition profile, each Varshamov–Tenengolts syndrome class corrects one SID, and the syndrome takes at most n values.Source: C. Inner Syndromes for… · p. 19
  • For every composition profile and n>t, an inner syndrome map has classes correcting up to t SIDs.The syndrome evaluation and decoder run in n^O(t) time.Source: C. Inner Syndromes for… · p. 19

D. Profile-Sensitive Inner Syndromes for Multipermutation PIDs

E. General Fixed-Composition Full-Systematic Construction

The fixed-composition construction encodes inner deletion-correcting syndromes through marker positions and uses disjoint outer-code output sets to recover the syndrome. The regular-profile extension preserves strict multiplicity and makes the PID and SID models coincide when λ > t.

E. General Fixed-Composition Full-Systematic Construction

  • The outer code's projected output sets are disjoint, allowing the decoder to identify the outer vector uniquely under either deletion model.For fixed-composition messages, a common PID output also induces a common message descendant after at most the same number of deletions.Source: E. General Fixed-Composition… · pp. 20–21
  • The encoder indexes an outer-code vector by the inner syndrome, then interleaves its marker pattern with the message so deleting markers recovers the message.For each channel, the outer class is chosen large enough to index the inner syndrome space for sufficiently large n.Source: E. General Fixed-Composition… · pp. 20–21
  • For every composition profile, the construction gives full-systematic codes correcting up to t SIDs and PIDs, with uniform construction, encoding, and decoding in n^O(t) time.The SID encoder maps M(m) to M(m+5t); the PID encoder's destination and redundancy expression are incomplete in the supplied passage.Source: E. General Fixed-Composition… · pp. 21–22

F. Regular Profiles and the PID-to-SID Transition

  • The regular-profile construction groups formal markers into λ-sized blocks and uses non-decreasing block vectors to retain strict λ-regularity.The restricted outer class has size Ω_R,t,λ(n^R−t) and disjoint projected output sets.Source: F. Regular Profiles and the PID-to-SID… · p. 22
  • For fixed t and λ, the strictly regular encoders are full-systematic, correct up to t deletions, and uniformly constructible, encodable, and decodable in n^O_t,λ(1) time.The supplied theorem passage says their redundancies satisfy a bound but does not include its expression.Source: F. Regular Profiles and the PID-to-SID… · p. 23
  • When λ > t, PID and SID models coincide on every codeword, and the encoders can be chosen identically.At most t deletions cannot remove an entire symbol class, so tie-preserving standardization is the identity on surviving sequences.Source: F. Regular Profiles and the PID-to-SID… · p. 23

VI. GENERALITY OF THE OUTER FRAMEWORK AND REDUNDANCY COMPARISONS

The section presents the labeled-marker outer framework as a systematic compiler: it encodes an inner deletion-correcting syndrome in marker positions while preserving the message permutation. It also gives single-deletion constructions with explicit marker counts and redundancies.

VI. GENERALITY OF THE OUTER FRAMEWORK AND REDUNDANCY COMPARISONS

  • The framework is presented as a universal systematic compiler that can turn any inner syndrome partition correcting the prescribed deletions into a full-systematic code.The outer code must accommodate the inner syndrome cardinality.Source: §VI · p. 24, A. The Outer-Code Framework as a… · p. 24

A. The Outer-Code Framework as a Systematic Compiler

  • The outer framework converts an indexed inner syndrome into redundancy-marker positions, producing a full-systematic codeword while leaving the message permutation intact.The encoder requires enough outer-code vectors to index the inner syndrome classes.Source: A. The Outer-Code Framework as a… · p. 24
  • For single deletions, 4 markers suffice for PIDs and 3 for SIDs, with redundancies of 4 log n + O(1) and 3 log n + O(1) bits, respectively.These constructions apply for all sufficiently large n.Source: A. The Outer-Code Framework as a… · p. 24

B. Baseline Constructions via Direct Confusability Graph Coloring

The section compares direct local fingerprinting on full confusability graphs with algebraically structured inner syndromes, then reports redundancy and complexity trade-offs. The structured constructions reduce marker requirements, while all four code families retain polynomial-time encoding and decoding for fixed t.

B. Baseline Constructions via Direct Confusability Graph Coloring

  • At a_in = 4t, the direct approach requires 5t + 1 markers and systematic redundancy (5t + 1) log n + O_t(1); at a_in = 6t, the outer compiler requires 7t + 1 markers and redundancy (7t + 1) log n + O_t(1).Source: B. Baseline Constructions via Direct… · p. 25

C. Impact of Inner Structural Constraints

  • The cyclic-successor mapping reduces the SID syndrome exponent from 4t to 3t − 1, lowering the marker requirement from 5t + 1 to 4t and saving (t + 1) log n bits.It embeds the Ulam metric into Hamming distance and permits use of a canonical power-sum Hamming syndrome.Source: C. Impact of Inner Structural… · p. 25
  • For PIDs, single-PID syndrome preprocessing reduces the residual graph degree exponent from 3t to 3t − 2 and lowers redundancy from (7t + 1) log n to (7t − 1) log n.The inner syndrome exponent drops from 6t to 6t − 2, saving two markers.Source: C. Impact of Inner Structural… · p. 25

D. Asymptotic Redundancy and Complexity Trade-Offs

VII. CONCLUSION

  • The framework extends to fixed-composition multipermutations and strictly λ-regular profiles, with PID and SID models coinciding when λ > t.The conclusion also identifies closing the gap between existential redundancy bounds and constructive marker counts as future work.Source: §VII · p. 26

APPENDIX A PROOF OF THEOREM 1

The appendix relates PID distance to one-point replacements and bounds replacement sequences whose endpoints remain within t deletions of a fixed permutation. This counting argument supplies the sequence bound used in the triangle-count analysis.

A. Maximum degree and Two-order replacements

  • The sequence-count bound is the additional ingredient used to obtain an upper bound on the triangle count.The text identifies this triangle bound as the ingredient needed for the logarithmic improvement.Source: A. Maximum degree and Two-order… · pp. 27–28
  • A replacement deletes a point and inserts another at specified position and value ranks, yielding a new permutation.The deleted point is identified by its position rank; the inserted point is specified by its position and value ranks.Source: A. Maximum degree and Two-order… · p. 27
  • The minimum number of one-point replacements transforming one permutation into another equals their PID distance.The proof uses the largest order-isomorphic common subsequence as the preserved core.Source: A. Maximum degree and Two-order… · p. 27
  • For fixed t and replacement-sequence lengths h ≤ 2t, the appendix bounds the number of sequences whose endpoint is at PID distance at most t from the start.The count separates cases by the number of distinct original points deleted and uses a canonical pair of isomorphic cores when that number exceeds t.Source: A. Maximum degree and Two-order… · pp. 28–29

B. Triangle count

The triangle-count argument encodes pairs of adjacent PID edges as replacement sequences from a fixed root. It then applies a few-triangles independence bound to derive the stated lower-bound proof for PID codes.

B. Triangle count

  • Concatenating shortest replacement paths from π to σ and σ to τ gives a sequence of length at most 2t when π, σ, and τ form a PID triangle.The third edge ensures the endpoint τ is within PID distance t of π.Source: B. Triangle count · p. 29
  • For fixed sequence length, the concatenated sequence identifies σ and τ, and the split point has at most 2t + 1 possibilities.The sequence-count result is used to bound ordered triangles rooted at π.Source: B. Triangle count · p. 29
  • The proof applies a few-triangles independence bound using the maximum-degree and triangle-count estimates to establish the claimed PID-code lower bound.The cited argument also considers the triangle-free case separately.Source: B. Triangle count · p. 29
Loading 2609.37578v1…