PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Protection in Function-Correcting Symbol-Pair Codes: Redundancy Bounds and Protection Profiles

Anamika Singh, Abhay Kumar Singh

arXiv:2609.10989v1cs.ITmath.IT

TL;DR

Function correction can leave the message itself unprotected, even though some applications need both the function value and the data recovered. This paper develops function-correcting codes with data protection for the symbol-pair metric, deriving redundancy results and graph-based protection criteria. It shows that sufficiently large pair separation can make data protection cost no additional redundancy.

  • Problem

    Function correction alone can leave messages sharing a function value too close to protect the underlying data, while symbol-pair channels require a distance measure sensitive to adjacent-symbol errors.

    Source: §I · p. 3

  • Method

    The paper combines data-protection and function-protection distance requirements in the symbol-pair metric, then develops redundancy matrices, constructions, and graph invariants.

    Source: §I · pp. 3–4, §VIII · p. 39

  • Results

    When the pair-separation constant is sufficiently large, data protection requires no additional redundancy, and graph invariants characterize strict protection parameters realizable by a linear code.

    Source: §VIII · p. 39

  • Takeaways & Limitations

    For a given linear code, the graph invariants trace the trade-off between function-protection strength and the number of protected function values.

    Source: §VIII · p. 39

Abstract

from arXiv · show

In several storage systems, including DNA storage and flash memory, errors affect neighbouring symbols jointly, and the Hamming metric does not adequately capture such error patterns. The symbol-pair read channel, introduced by Cassuto and Blaum~\cite{cassuto2011codes}, addresses this by reading consecutive pairs of symbols rather than individual symbols. Motivated by this, we introduce function-correcting symbol-pair codes with data protection (FCSPC-DP), which guarantee reliable recovery of a desired function of the message while simultaneously protecting the message itself against symbol-pair errors. We derive bounds on the optimal redundancy of such codes and establish a relationship with joint-pair distance matrices. We also give explicit constructions of FCSPC-DP for locally pair-bounded functions and symbol-pair weight functions. We introduce the pair-separation constant of a function, the minimum symbol-pair distance between messages sharing a function value, and show that when it is sufficiently large, data protection requires no additional redundancy: the optimal redundancy coincides with that of the corresponding code without data protection. Considering the symbol-pair analogue of the $\alpha$-distance graph, we introduce two code invariants, the generation profile and the disconnection threshold, and use them to characterise a code's protection properties. Relating the two metrics through these invariants yields upper and lower bounds on the symbol-pair threshold in terms of its Hamming counterpart, both of which are attained. We further extend the classical Plotkin and sphere-packing bounds to this setting.

I. INTRODUCTION

Function-correcting codes can reduce redundancy when only a function value must be recovered, but they do not necessarily protect the message itself. This paper combines function correction with the adjacency-sensitive symbol-pair metric to study codes that protect both.

A. Contribution

  • FCSPC-DP codes require simultaneous minimum symbol-pair distances for the data and for messages with distinct function values.The function receives stronger protection in the strict case of interest.Source: §I · p. 3
  • The symbol-pair setting changes distance bookkeeping because systematic encoding blocks share a junction, producing a one-unit loss in each direction that can be avoided under a structural condition.Both extremes of the loss are attained.Source: §I · p. 3
  • The framework links the Hamming and symbol-pair metrics: Hamming-metric codes induce symbol-pair codes with stronger protection, while symbol-pair codes yield Hamming-metric codes with roughly half the protection..Source: A. Contribution · p. 4
  • The two-step construction adapts to symbol-pair distances and yields redundancy bounds with coded pair-requirement matrices.The matrices account for separation supplied by codewords rather than messages.Source: A. Contribution · p. 4
  • When a function’s pair-separation constant is sufficiently large, data protection requires no additional redundancy.The optimal redundancy then equals that of the corresponding code without data protection.Source: A. Contribution · p. 4
  • The symbol-pair α-distance graph yields generation-profile and disconnection-threshold invariants that characterize strict protection parameters realizable by a linear code.These parameters trace the trade-off between function-protection strength and the number of protected function values.Source: A. Contribution · p. 4, §I · p. 4
  • Explicit constructions are given for functions whose values vary little over small message-space neighbourhoods, with the symbol-pair weight function treated separately..Source: A. Contribution · p. 4
  • The classical Plotkin and sphere-packing bounds are extended to the function-correcting symbol-pair setting.The Plotkin-type bound depends on the function only through its level-set sizes.Source: A. Contribution · p. 4

C. Function-Correcting Codes

This section reviews function-correcting-code and Cayley-graph preliminaries, defines data protection for symbol-pair codes, and relates protection thresholds and function-correcting symbol-pair codes with data protection to Hamming-metric constructions. It also gives a worked example of a redundancy bound and introduces joint pair-distance matrices.

C. Function-Correcting Codes

D. Cayley Graphs

  • A Cayley graph is disconnected when its connection set does not generate the group, with components equal to cosets of the generated subgroup.Source: D. Cayley Graphs · p. 8

III. FUNCTION-CORRECTING SYMBOL-PAIR CODES WITH DATA PROTECTION(FCSPC-DP)

  • Minimum symbol-pair distance governs data protection, while the minimum distance across codewords with different function values governs function recovery.A distance threshold d protects against floor((d − 1)/2) symbol-pair errors at the corresponding data or function level.Source: §III · pp. 9–10
  • The section extends the Hamming-to-symbol-pair distance relationship to function minimum pair-distance, bridging Hamming-metric FCCs and their symbol-pair counterparts.Source: §III · p. 10
  • For the binary OR function, two encodings with redundancy 2 correct the same function-level errors, but only one also corrects a symbol-pair error in the data.The other encoding corrects no data-level symbol-pair errors.Source: §III · p. 11, Table I · p. 12
  • When df < n, an (f : dd, df) Hamming FCC yields an (f : dd + 1, df + 1) symbol-pair code with the same redundancy; conversely, pair thresholds imply Hamming thresholds (ceil(dd/2), ceil(df/2)).Source: §III · pp. 12–13
  • Pair-metric data and cross-function distance requirements transfer to Hamming distances of at least ceil(dd/2) and ceil(df/2), respectively.Thus an (f : dd, df)p-FCSPC-DP is also an (f : ceil(dd/2), ceil(df/2))H-FCC-DP.Source: §III · p. 13
  • Translating an optimal pair-metric FCSPC into a Hamming FCC-DP preserves redundancy, yielding a lower bound from the minimum Hamming redundancy for those distance requirements.The comparison uses the Hamming redundancy H(k, ceil(dd/2), ceil(df/2)).Source: §III · p. 13
  • For the least-frequent-coordinate function on F3^2, the cited example uses dd = 3 and df = 5 and reports optimal Hamming redundancy 6.The function assigns its output to the position of the least frequent symbol.Source: §III · pp. 13–14
  • The example gives an upper bound of 6 on symbol-pair optimal redundancy for dd = 4 and df = 6, with code distances 4 and 7.The example code meets both distance requirements, with pair data distance 4 and cross-function pair distance 7 > 6.Source: §III · p. 14
  • Joint pair-distance matrices are defined for M vectors as M × M symbol-pair distance matrices, with entries reflecting pair distances within a function class.For distinct vectors with the same function value, the provided entry expression is [dd + 1 − dp(xi, xj)]+.Source: §III · p. 14

A. Bounds on Optimal Redundancy via the Joint Pair-Distance Matrices

The section uses joint pair-distance requirement matrices to express the separations needed for data protection and function protection. It gives a matrix-based redundancy construction and bounds for FCSPC redundancy.

A. Bounds on Optimal Redundancy via the Joint Pair-Distance Matrices

  • The section states that the data-protection distance dd cannot exceed the function-protection distance df.It attributes this constraint to the fact that a code's function minimum pair-distance cannot be smaller than its classical minimum distance.Source: A. Bounds on Optimal Redundancy via… · p. 15
  • A contradiction argument based on D(1) establishes a lower bound: any encoding with less redundancy would violate either data protection or function protection.The proof considers same-function pairs and different-function pairs separately.Source: A. Bounds on Optimal Redundancy via… · pp. 14–15
  • The construction uses a pair-distance requirement matrix to assign residual separation requirements to message pairs, then encodes vectors meeting those requirements.The supplied proof fragments verify the resulting encoding against within-class data-protection pairs and cross-class function-protection pairs.Source: A. Bounds on Optimal Redundancy via… · p. 15
  • The resulting FCSPC has redundancy Np(D(2)), yielding an upper bound on the optimal redundancy.The construction verifies both distance requirements for an (f : dd, df)p-FCSPC.Source: A. Bounds on Optimal Redundancy via… · p. 15

IV. EXPLICIT CONSTRUCTION OF FUNCTION-CORRECTING SYMBOL-PAIR CODES WITH DATA-PROTECTION

The section adapts a two-step construction to the symbol-pair setting: a linear pair-error-correcting code first supplies baseline data protection, and a function-correcting code then raises cross-class separation. It also develops coded pair-distance requirement matrices and gives a redundancy bound for FCSPC-DP.

IV. EXPLICIT CONSTRUCTION OF FUNCTION-CORRECTING SYMBOL-PAIR CODES WITH DATA-PROTECTION

  • Construction 1 extends the two-step FCC approach to the symbol-pair metric while incorporating data protection.The stated redundancy for the resulting FCSPC is n−k+r′.Source: §IV · pp. 16–17
  • The first-stage symbol-pair code fixes baseline data separation, while the second-stage FCSPC raises separation for pairs with different function values to df.The construction applies its second stage to codewords rather than directly to message vectors.Source: §IV · pp. 16–17
  • Coded pair-distance requirement matrices measure residual requirements against the first-stage codewords rather than the original messages.This change reflects that the first-stage codewords, not the messages, supply the available pair separation in Construction 1.Source: §IV · p. 17
  • The two-step construction yields an FCSPC-DP with redundancy (n−k)+r′′.Its first-stage code has minimum pair-distance at least dd, and the second stage is applied to the resulting codewords.Source: §IV · pp. 16, 18

A. Block-aware Analysis of Function-Correcting Symbol-Pair Codes with Data Protection

The section defines a function's pair-separation constant as the minimum pair-distance between distinct messages with the same function value. When this separation is at least the data-protection target, the optimal redundancy matches that of the corresponding FCSPC without data protection.

A. Block-aware Analysis of Function-Correcting Symbol-Pair Codes with Data Protection

  • The pair-separation constant δp(f) is the least pair-distance between distinct messages carrying the same function value.A function is d-pair-separated when δp(f) ≥ d.Source: A. Block-aware Analysis of… · pp. 18–19
  • For the Hamming weight function, the section establishes δp(f) ≥ 3, so it is 3-pair-separated.The argument uses the fact that distinct equal-weight vectors differ in at least two coordinates and bounds their pair-distance.Source: A. Block-aware Analysis of… · p. 19
  • If δp(f) ≥ dd, the optimal redundancy with data protection equals that of the corresponding FCSPC without data protection.The proposition also assumes df ≥ dd.Source: A. Block-aware Analysis of… · p. 19
  • The two-step construction's first-stage n−k redundancy can be overhead when function geometry already supplies the required within-class separation.The section characterizes this overhead as unnecessary for functions satisfying Proposition 6's hypothesis.Source: A. Block-aware Analysis of… · p. 19
  • When δp(f) ≥ dd+1, the pair-distance requirement matrices reduce to the corresponding matrices without data protection, and the stated redundancy bounds coincide.The proposition applies this condition for any ordering of the message vectors.Source: A. Block-aware Analysis of… · p. 20

f (dd, df; ·) respectively. The corresponding PDRM entries

The joint-pair distance and pair-distance requirement matrices coincide. Their diagonal entries vanish, and their cross-class entries agree.

B. Bounds from the Coded Distance-Requirement Matrix

The section relates coded distance-requirement matrices to joint matrices and gives a construction-based bound. It then uses connected components of the α-pair-distance graph to characterize when strict function protection is impossible or achievable.

B. Bounds from the Coded Distance-Requirement Matrix

  • The coded distance-requirement matrix is related back to the joint matrix, providing a route to bounds through scalar symbol-pair and Hamming quantities.Source: B. Bounds from the Coded… · p. 20

q} be an ordered D2

  • A construction yields a D1-code of length (n-k) + Np(D2), with its distance requirements supported by a D2-code whose pairwise distances are at least df - dd + 1.The stated bound follows because any M vectors with those pairwise distances form a D2-code.Source: q} be an ordered D2 · p. 21

A. The α-Pair-Distance Graph

  • A strict FCSPC-DP requires at least |Im(f)| connected components in the α-pair-distance graph; too few components rule out that protection.If the graph has Q components, the cited result excludes functions with at least Q + 1 image values.Source: A. The α-Pair-Distance Graph · p. 23
  • Strict protection is achievable when components of G^(df−1)_p(C) can be grouped into disjoint unions matching the function-fibre sizes.Source: A. The α-Pair-Distance Graph · p. 23

B. Linear codes: Cayley Structure and the Generation profile

For linear codes, α-pair-distance graphs have a Cayley-graph structure governed by low pair-weight codewords. Their generation profile and disconnection threshold characterize achievable strict protection levels and the associated function classes.

B. Linear codes: Cayley Structure and the Generation profile

H(C), respectively, and in the symbol-pair metric by γp

The paper compares generation thresholds in the Hamming and symbol-pair metrics. The resulting upper and lower bounds are both attained.

C. Consequences for optimal redundancy

A graph condition characterises which fixed-length codes provide strict function correction with data protection, while a linear-code criterion and pair-metric code bounds constrain the required length.

C. Consequences for optimal redundancy

  • For a linear [n,k]_q code, strict protection is equivalent to a proper subcode H with dp(C) ≥ dd and wp(c) ≥ df for every c outside H.The graph condition characterises the fixed-length case; optimal redundancy minimises length over codes satisfying it.Source: C. Consequences for optimal redundancy · p. 30
  • The code length must be at least both Np(q^k, dd) and Np(q^(k−γ), df), where γ is the dimension of the subcode generated by the specified low-weight codewords.The first bound comes from data protection across the code; the second comes from separating representatives of distinct cosets.Source: C. Consequences for optimal redundancy · pp. 30–31

VI. FCSPC-DP FOR SPECIFIC FUNCTION CLASSES

The constructions add pair-metric redundancy according to how many function values occur locally, with sharper results for pair-locally binary functions, including a regime where protection is free.

A. Pair-locally bounded function

  • A function is pair-locally binary when each pair-ball of the specified radius contains at most two function values, and such functions admit a pair-separating 2-colouring.For general pair-locally bounded functions, local function-value counts focus the construction on values visible within radius df−1.Source: A. Pair-locally bounded function · pp. 31–32
  • If f admits a (df−1)-pair-separating λ-colouring, df > dd ≥ 1, and a systematic linear [n,k]q code has dp(C) ≥ dd, the construction yields redundancy n−k+Np(λ, df−dd+1).Source: A. Pair-locally bounded function · pp. 32, 34
  • The binary construction uses two parity blocks differing in every coordinate, so their pair-distance is L and they can supply the required function separation.The construction combines this separation with a systematic code whose message protection distance is at least dd+1.Source: A. Pair-locally bounded function · pp. 33–34
  • When df ≤ dd+1, C itself is an (f:dd,df)p-FCSPC-DP; when df ≥ dd+2 under the stated pair-local binary condition, the construction has redundancy n−k+L, with L=df−dd−1≥1.Source: A. Pair-locally bounded function · p. 33

B. The Symbol-Pair Weight Function

The section constructs protection for the symbol-pair weight function and extends Plotkin-type bounds to the data-protected setting by using pairwise distance constraints.

B. The Symbol-Pair Weight Function

  • For the symbol-pair weight function with odd dd=2td+1 and df=2tf+1, the construction gives redundancy n−k+Np(df, df−dd+1).The result assumes k≥3, tf≥td, and a systematic linear code with dp(C)≥dd.Source: B. The Symbol-Pair Weight Function · p. 34

A. Plotkin-Type Bounds

  • The Plotkin-type bound uses the total pairwise separation imposed by data and function protection to bound the code length.The section also states that setting dd=1 specialises the bound to the FCPSC setting without data protection.Source: §VII · p. 35, A. Plotkin-Type Bounds · pp. 35, 37
  • A subsequent Plotkin-type bound reduces dependence on individual codeword-pair requirements to function-class sizes and the code parameters dd and df.The corresponding lemma also applies to the joint pair-distance requirement matrix.Source: A. Plotkin-Type Bounds · p. 35
  • Every systematic FCSPC has dp(Cf)≥2, so it also satisfies data protection with dd=2 and inherits the corresponding Plotkin-type bound.The broader section describes sphere-packing bounds through disjoint decoding regions for distinct function values.Source: §VII · p. 35, A. Plotkin-Type Bounds · p. 37

B. Sphere-Packing Bounds

Sphere-packing bounds follow from disjoint decoding regions for distinct function values, with data protection additionally separating the centres within each class. The conclusion gathers the paper's constructions, redundancy results, metric relations, and bounds.

B. Sphere-Packing Bounds

  • For an (f,t)_p-FCSPC, unions of radius-t pair-balls for distinct function values are disjoint, yielding a sphere-packing bound involving the number of function values and the smallest preimage class.Here ℓ is the smallest class size, and the bound uses the volume of a pair-ball.Source: B. Sphere-Packing Bounds · p. 37
  • With data protection, centres within each function class must also be pair-separated by at least dd, strengthening the lower bound on each class's ball union.The class unions remain disjoint because cross-class distances are at least df.Source: B. Sphere-Packing Bounds · p. 38
  • When f is a bijection, the stated data-protected sphere-packing bound reduces to the ordinary symbol-pair sphere-packing bound.In this case E=q^k, ℓ=1, and dd=df.Source: B. Sphere-Packing Bounds · p. 39

VIII. CONCLUSION

  • The paper introduces FCSPC-DP and extends the Hamming-to-symbol-pair metric relation to function minimum pair-distance, providing a two-way passage between metrics at the code level.Its contributions also include joint pair-distance requirement matrices, a pair-separation constant, graph invariants, explicit constructions, and Plotkin and sphere-packing bounds.Source: §VIII · p. 39
Loading 2609.10989v1…