PaperlayerView exact revision on arXiv

Source-linked AI summary

Function-Correcting Lee-distance Codes for Symbol-Pair Read Channels

Hareesh K., B. Sundar Rajan

arXiv:2610.09491v1cs.ITmath.IT

TL;DR

Recovering only a function value can require less redundancy than recovering an entire message, and symbol-pair reads with q-ary PSK motivate a Lee-metric treatment. The paper generalizes symbol-pair Lee-distance to Zq, develops FCSPLCs and bounds, and presents constructions for several function classes.

  • Problem

    FCCs for symbol-pair read channels had been studied under Hamming distance, while the Lee-metric symbol-pair framework was limited to Z4 and had not been developed for FCCs.

    Source: §I · p. 1, A. Motivation · p. 2

  • Method

    The paper generalizes symbol-pair Lee-distance to Zq, introduces FCSPLCs for q = 2^m, and relates their redundancy to shortest irregular-pair Lee-distance codes.

    Source: C. Contributions · p. 3

  • Results

    The paper derives Plotkin-type and Gilbert–Varshamov-type redundancy bounds, including corresponding bounds for classical Lee metric codes on symbol-pair channels for bijective functions.

    Source: C. Contributions · p. 3, §VII · p. 25

  • Takeaways & Limitations

    The framework includes explicit FCSPLC constructions and upper bounds for pair-locally bounded functions, the pair-Lee weight, and its distribution function.

    Source: C. Contributions · p. 3

Abstract

from arXiv · show

Function-correcting codes (FCCs) protect specified function evaluations of messages against errors while reducing the redundancy required for reliable communication. We study FCCs for symbol-pair read channels, motivated by high-density storage systems that read overlapping symbol pairs. Phase-shift keying (PSK) modulation is well-suited to such systems due to its bandwidth efficiency and noise robustness. While FCCs for symbol-pair read channels have been studied under the Hamming metric, the Lee metric is a more appropriate error model for $q$-ary PSK and, hence for $q$-ary symbol-pair read channels. We generalize the symbol-pair Lee distance, previously defined only over $\mathbb{Z}_4$, to $\mathbb{Z}_q$, $q\ge2$, and introduce function-correcting symbol-pair Lee-distance codes (FCSPLCs) over $\mathbb{Z}_q$, specializing to $q=2^m$, $m\ge1$, for $2^m$-ary PSK constellations. We investigate their redundancy requirements by introducing irregular-pair Lee-distance codes and relating the optimal redundancy of FCSPLCs to the shortest length of such codes. We derive Plotkin-type and Gilbert--Varshamov-type bounds on the optimal redundancy through lower and upper bounds on the shortest length of irregular-pair Lee-distance codes. For bijective functions, we obtain corresponding Plotkin-type and Gilbert--Varshamov-type bounds for classical Lee metric codes for symbol-pair read channels over $\mathbb{Z}_q$, which, to the best of our knowledge, are the first such bounds for the Lee metric symbol-pair setting. We then specialize the FCSPLC framework to pair-locally bounded functions, the Pair-Lee weight function, and the Pair-Lee weight distribution function, giving explicit constructions and corresponding bounds on the optimal redundancy. Finally, for linear functions, we derive a Plotkin-type lower bound on the optimal redundancy.

I. INTRODUCTION

The paper addresses the lack of a Lee-metric framework for function-correcting codes on symbol-pair read channels, motivated by q-ary PSK and overlapping-pair reads. It generalizes the distance to Zq and develops FCSPLCs, bounds, and constructions.

I. INTRODUCTION

  • FCCs target reliable recovery of specified function values, potentially with less redundancy than recovering entire messages when the output space is small.Optimal redundancy is the minimum redundancy required for reliable recovery of the desired function value.Source: §I · p. 1

A. Motivation

  • Overlapping-pair reads arise in high-density storage, and the Lee metric models cyclic q-ary symbol deviations more closely than Hamming distance for q-ary PSK.The paper identifies the Lee-metric framework for general Zq symbol-pair channels as unexplored, beyond prior work over Z4.Source: A. Motivation · p. 2, B. Related Works · p. 3

C. Contributions

  • The paper generalizes symbol-pair Lee-distance from Z4 to Zq, q ≥ 2, and proves that the resulting distance is a metric.It also derives a relationship between symbol-pair Lee-distance and classical Lee-distance.Source: C. Contributions · p. 3
  • For q = 2^m, the paper introduces FCSPLCs and connects their optimal redundancy to the shortest length of irregular-pair Lee-distance codes.This framework supports bounds on FCSPLC redundancy.Source: C. Contributions · p. 3
  • Plotkin-type and Gilbert–Varshamov-type bounds for FCSPLCs yield corresponding bounds for classical Lee metric codes on symbol-pair channels when the function is bijective.The authors identify these as the first such bounds in the Lee-metric symbol-pair setting, to their knowledge.Source: C. Contributions · p. 3
  • The framework gives explicit constructions and upper bounds for pair-locally bounded functions, the pair-Lee weight, and its distribution function.For the pair-Lee weight distribution function, vectors with the same pair-Lee weight receive the same parity vector, while different weights receive different parity vectors.Source: C. Contributions · p. 3
  • For linear functions, the paper derives a Plotkin-type lower bound on optimal redundancy.Source: C. Contributions · p. 3

III. SYMBOL-PAIR LEE-DISTANCE CODES OVER Zq

The paper extends symbol-pair Lee-distance from Z4 to Zq and establishes that the generalized distance is a metric. It also relates it to classical Lee-distance and gives the minimum-distance condition for correcting pair errors.

III. SYMBOL-PAIR LEE-DISTANCE CODES OVER Zq

  • The generalized symbol-pair Lee-distance over Zq is a metric for q ≥ 2.The paper defines the distance by summing, over adjacent cyclic symbol pairs, the larger of the two component Lee-distances.Source: §III · pp. 5–6
  • The relationship between classical Lee-distance and symbol-pair Lee-distance extends to Zq with a proof independent of alphabet size.Source: §III · p. 6
  • A code with minimum symbol-pair Lee-distance dp corrects up to t pair errors if and only if dp ≥ 2t + 1.Source: §III · p. 7

IV. GENERAL REDUNDANCY BOUNDS FOR FCSPLCS

The section develops function-correcting symbol-pair Lee-distance codes over q-ary alphabets and relates their redundancy to irregular-pair Lee-distance codes. This connection supports general redundancy bounds and, for bijective functions, corresponding bounds for classical Lee-distance codes on symbol-pair read channels.

IV. GENERAL REDUNDANCY BOUNDS FOR FCSPLCS

  • For q = 2^m, FCSPLCs have lower and upper optimal-redundancy bounds derived from bounds on the shortest lengths of irregular-pair Lee-distance codes.The framework generalizes symbol-pair Lee-distance from Z4 to Zq, q ≥ 2.Source: §IV · p. 7
  • For bijective functions, the results yield corresponding Plotkin-type and Gilbert–Varshamov-type bounds for classical Lee-distance codes on symbol-pair read channels.Source: §IV · p. 7

A. FCSPLCs and Irregular-Pair Lee-distance Codes

  • When function values differ, a pair Lee-distance of at least 2t + 1 lets minimum-distance decoding recover the correct function value despite up to t pair errors.The guarantee concerns recovering the function value, not necessarily the entire message.Source: A. FCSPLCs and Irregular-Pair… · p. 8
  • The connection between FCSPLCs and irregular-pair Lee-distance codes is the foundation for deriving bounds on optimal redundancy.Source: A. FCSPLCs and Irregular-Pair… · p. 8

B. Simplified Redundancy Bounds

This subsection simplifies the redundancy bounds by working with function values or selected input subsets. The resulting minimum-length quantities are generally easier to evaluate, though finding them exactly is generally difficult.

B. Simplified Redundancy Bounds

  • The simplified bounds can be sub-optimal because they use subsets of the full input space, and determining the relevant minimum lengths exactly is generally difficult.Source: B. Simplified Redundancy Bounds · p. 11
  • A simplified lower bound on optimal redundancy is available from an arbitrary subset of information vectors.Source: B. Simplified Redundancy Bounds · p. 11
  • The simplified upper-bound construction assigns the same redundancy vector to every input with the same function value.It uses a code indexed by the distinct values in Im(f).Source: B. Simplified Redundancy Bounds · p. 12
  • The function-value pair Lee-distance matrices are typically much smaller than the corresponding input-vector matrices, making their minimum-length quantities generally easier to evaluate.Source: B. Simplified Redundancy Bounds · p. 12

C. Bounds on the Shortest Length of Irregular-Pair Lee-distance Codes

The section bounds the shortest length of irregular-pair Lee-distance codes by optimizing distance sums over coordinate columns. It derives Plotkin-type lower bounds and Gilbert–Varshamov-type upper bounds, with corresponding bounds for bijective functions.

C. Bounds on the Shortest Length of Irregular-Pair Lee-distance Codes

  • The Plotkin-type lower bound follows by maximizing each coordinate-column distance sum over equidistant subsets and as-even-as-possible symbol-pair counts.The resulting bound applies to the shortest length of irregular-pair Lee-distance codes.Source: C. Bounds on the Shortest Length of… · pp. 12, 14, 15
  • For even q, the largest subset of Zq × Zq with distinct elements at pair-Lee distance q/2 has four elements.The optimization also favors distributing the coordinate counts over this subset as uniformly as possible.Source: C. Bounds on the Shortest Length of… · pp. 13–14
  • For bijective functions, the derived results specialize to Plotkin-type and Gilbert–Varshamov-type bounds for classical Lee-distance codes on symbol-pair channels over Zq.The paper presents these as variants for minimum pair-distance d.Source: C. Bounds on the Shortest Length of… · p. 16
  • A greedy iterative construction gives a Gilbert–Varshamov-type upper bound when q^r exceeds the summed volumes of the distance balls imposed by the pairwise constraints.The construction selects codewords one at a time while meeting each prescribed distance requirement.Source: C. Bounds on the Shortest Length of… · p. 16
  • A classical Lee-distance code of length NL(M, d) also supplies a symbol-pair Lee-distance code, so Np(M, d) ≤ NL(M, d).This relation lets known classical Lee-metric upper bounds yield symbol-pair upper bounds.Source: C. Bounds on the Shortest Length of… · pp. 16–17

V. CONSTRUCTION OF FCSPLCS FOR PAIR-LOCALLY BOUNDED, PAIR-LEE WEIGHT, AND PAIR-LEE WEIGHT DISTRIBUTION FUNCTIONS

This section presents explicit FCSPLC constructions for pair-locally bounded functions, the Pair-Lee weight function, and the Pair-Lee weight distribution function; each construction gives an upper bound on optimal redundancy.

V. CONSTRUCTION OF FCSPLCS FOR PAIR-LOCALLY BOUNDED, PAIR-LEE WEIGHT, AND PAIR-LEE WEIGHT DISTRIBUTION FUNCTIONS

  • The section constructs FCSPLCs for pair-locally bounded functions and establishes an upper bound on their optimal redundancy.These constructions are part of the section's broader treatment of three function classes.Source: §V · p. 17
  • The section also presents an explicit FCSPLC construction for the Pair-Lee weight function.The stated construction yields an upper bound on optimal redundancy.Source: §V · p. 17
  • An explicit FCSPLC construction is likewise given for the Pair-Lee weight distribution function, with an upper bound on optimal redundancy.Source: §V · p. 17

A. Pair-Locally Bounded Functions

Pair-locally bounded functions extend local boundedness to symbol-pair read channels. Under a contiguous block condition, a coloring-based construction appends repeated parity symbols to separate function values and correct symbol-pair errors.

A. Pair-Locally Bounded Functions

  • Pair-locally bounded functions extend locally bounded functions to symbol-pair read channels, where the number of distinct function values within a pair-Lee neighborhood is limited.The paper studies the resulting function class for FCSPLCs.Source: A. Pair-Locally Bounded Functions · p. 17
  • For a pair-locally (2t, λ)-bounded function satisfying the contiguous block condition, Construction 1 assigns a color and appends r repetitions of its parity symbol.The stated construction assumes λ ≤ q/2.Source: A. Pair-Locally Bounded Functions · pp. 17–18
  • The appended parity block adds at least its own pair-Lee distance to the original input distance.This distance inequality underlies the construction's separation guarantee.Source: A. Pair-Locally Bounded Functions · p. 18
  • When distinct function values occur within pair distance 2t, their assigned parity symbols provide enough added distance for the encoding to reach at least 2t+1.Inputs already at distance at least 2t+1 retain that separation under the construction.Source: A. Pair-Locally Bounded Functions · p. 18
  • Pair-locally binary functions with ρ = 2t are a special case of the bounded-function construction.The two color classes receive parity symbols 0 and q/2, respectively.Source: A. Pair-Locally Bounded Functions · p. 19

2. Consequently,

The pair-locally binary specialization assigns two parity symbols to the two color classes. The construction gives an optimal-redundancy upper bound, and an example illustrates the distance guarantee for q=8 and t=1.

2. Consequently,

  • Construction 1 yields an upper bound on optimal redundancy for pair-locally binary functions.Source: §2 · p. 19
  • For q=8, t=1, and λ=4, the example guarantees encoded pair distance at least 3 for every distinct input pair considered.The example uses parity symbols 0, 2, 4, and 6 for the four color classes.Source: §2 · p. 19

B. Pair-Lee Weight Function

The pair-Lee weight function supports an explicit FCSPLC construction by assigning parity vectors according to pair-Lee weight. The construction connects redundancy to symbol-pair Lee-distance codes and gives explicit upper bounds for q=4.

B. Pair-Lee Weight Function

  • Pair-Lee distance is at least the absolute difference between the vectors’ pair-Lee weights, providing the separation property used by the construction.This follows from the triangle inequality and wp(u) = dp(u, 0).Source: B. Pair-Lee Weight Function · p. 19
  • The construction appends a parity vector indexed by pair-Lee weight, selected from a symbol-pair Lee-distance code with 2t+1 codewords.The resulting encoding is defined as Enc(u) = (u, p_{wp(u)+1}).Source: B. Pair-Lee Weight Function · pp. 19–20
  • When information vectors have distinct pair-Lee weights, the proposed encoding gives distance at least 2t+1 and therefore defines an FCSPLC.The construction’s redundancy upper bound is expressed using the shortest length of a symbol-pair Lee-distance code with 2t+1 codewords.Source: B. Pair-Lee Weight Function · p. 20
  • For q=4, the construction gives redundancy upper bounds 2, 3, and 5 for t=1, t=2, and t=3, respectively.The t=3 bound is stated for k≥2.Source: B. Pair-Lee Weight Function · p. 20

C. Pair-Lee Weight Distribution Function

The pair-Lee weight distribution function is a step threshold function, and Construction 3 assigns parity vectors according to its input’s pair-Lee weight. The construction yields an upper bound of t+1 on optimal redundancy.

C. Pair-Lee Weight Distribution Function

VI. A PLOTKIN-TYPE BOUND ON THE OPTIMAL REDUNDANCY OF FCSPLCS FOR LINEAR FUNCTIONS

For linear functions, the section derives a Plotkin-type lower bound on the optimal redundancy of FCSPLCs. The result is stated for full-rank linear maps with l≤k.

VI. A Plotkin-Type Bound on the Optimal Redundancy of FCSPLCs for Linear Functions

  • The result considers linear maps with l≤k whose matrix F has full rank l over Z_q.The section identifies linear functions as an important class in the study of FCCs under the Lee metric.Source: §VI · p. 23
  • The section derives a Plotkin-type lower bound on the optimal redundancy of FCSPLCs for linear functions.Linear functions are represented as f(u)=Fu, with the kernel and pair-Lee weights of its vectors used in the bound’s development.Source: §VI · p. 23
  • For q=2, the proposed bound reduces to the Plotkin-type bound for function-correcting symbol-pair codes established in.Source: §VI · p. 25

VII. CONCLUSION

The paper establishes a Lee-metric framework for q-ary symbol-pair read channels and develops redundancy bounds and constructions for FCSPLCs. It also identifies tighter bounds and broader optimal constructions as future research directions.

VII. Conclusion

  • The paper generalizes symbol-pair Lee distance from Z4 to Zq for q≥2 and introduces FCSPLCs, specializing to q=2^m.It relates optimal redundancy to the shortest length of irregular-pair Lee-distance codes and derives Plotkin-type and Gilbert–Varshamov-type bounds.Source: §VII · p. 25
  • For bijective functions, the work obtains the first Plotkin-type and Gilbert–Varshamov-type bounds for classical Lee metric symbol-pair codes over Zq.Source: §VII · p. 25
  • The framework yields explicit FCSPLC constructions and redundancy upper bounds for pair-locally bounded functions and the two pair-Lee weight functions.Source: §VII · p. 25
  • For linear functions, the paper derives a Plotkin-type lower bound on optimal redundancy.Source: §VII · p. 25
  • Future work includes tighter optimal-redundancy bounds and optimal constructions for broader function classes.Source: §VII · p. 25

APPENDIX

The appendix gives a proposition on the total symbol-pair Lee weight over Z_q^k and develops its proof through adjacent-coordinate weights and Lee-weight counts.

APPENDIX

  • Proposition 1 concerns the sum of symbol-pair Lee weights over all vectors in Z_q^k for q = 2m, m ≥1.Source: APPENDIX · p. 25
  • The proof expresses a vector’s symbol-pair Lee weight using the maximum Lee weight of adjacent coordinates.Source: APPENDIX · p. 25
  • For even q = 2l, Lee weights 0 through l have multiplicity 1 at the endpoints and 2 for intermediate weights.Source: APPENDIX · p. 26
  • The number A_t of symbols with Lee weight at most t is 2t + 1 for t < l and 2l for t = l.Source: APPENDIX · p. 26
Loading 2610.09491v1…