🔢 mathematics

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

This paper introduces function-correcting symbol-pair codes with data protection (FCSPC-DP) for storage systems prone to adjacent symbol errors, establishing theoretical redundancy bounds, explicit constructions, and new invariants that characterize the trade-off between message protection and function recovery.

Original authors: Anamika Singh, Abhay Kumar Singh

Published 2026-09-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Anamika Singh, Abhay Kumar Singh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the hidden world of modern data storage, from the flash drives in our phones to the emerging promise of storing information in strands of DNA, the way errors occur is often more complex than a simple typo. In these dense systems, a single glitch rarely affects just one piece of information in isolation. Instead, the read mechanism often grabs a pair of neighboring symbols at once, meaning a single corruption can blur the boundary between two adjacent characters. To handle this, scientists use a specific way of measuring distance between data patterns that accounts for these overlapping pairs, rather than just counting how many individual letters are wrong. This approach is crucial for ensuring that the data we retrieve is actually the data we stored.

However, a new layer of complexity has emerged in how we think about what needs to be protected. Often, a computer system does not need to recover the entire original message perfectly; it only needs to recover a specific result derived from that message, such as a statistical average or a simple decision. For years, researchers have developed codes that prioritize this specific result, allowing the underlying raw data to be slightly more vulnerable in exchange for saving space. But in many real-world scenarios, this trade-off is unacceptable. If a network node needs to calculate a function of a stored file, that calculation must be correct, but the file itself also needs to remain intact for other users who might need the raw data. The challenge is to build a code that offers a higher level of protection for the specific result while still providing a solid, baseline level of protection for the raw data, all without wasting valuable storage space.

A team of researchers has now tackled this problem by creating a new framework called function-correcting symbol-pair codes with data protection. They have established the mathematical rules that govern how much extra space, or redundancy, is required to achieve this dual goal. Their work proves that the relationship between the old way of measuring errors and this new pair-based method holds true even when we are trying to protect a specific function of the data. They found that if the messages that share the same result are naturally far apart from each other in the data space, then protecting the raw data comes at no extra cost. In these cases, the system gets the stronger protection for the result and the baseline protection for the data for free, because the geometry of the data itself already provides the necessary separation.

The researchers also discovered a fundamental limit to how much stronger the protection for a result can be compared to the protection for the raw data. They introduced a way to map the connections between different pieces of data, showing that if the data is too tightly interconnected, it is impossible to create a code that offers significantly better protection for the result than for the data itself. This finding rules out the possibility of using certain highly efficient, perfect codes for this specific dual-purpose task. Instead, they showed that the ability to provide this extra protection depends on the specific structure of the code and how its components are arranged. By analyzing these structures, they identified a precise threshold: once the desired level of protection for the result crosses a certain point, the code must become disconnected in a specific way to allow the different results to be distinguished.

To make these ideas practical, the team developed explicit methods for building these codes for specific types of functions, particularly those where the result changes slowly across small groups of data. They also extended classic mathematical limits on how much data can be stored to this new setting, providing clear boundaries for what is possible. Their work confirms that while it is possible to have a code that protects a specific function more strongly than the data it comes from, this is only achievable if the data and the function are carefully matched. If the data is too uniform or the function too simple, the extra protection cannot be gained without a significant cost in storage space. This research provides the essential blueprint for designing storage systems that can handle the unique error patterns of modern technology while meeting the diverse needs of different users who rely on the same stored information.

Technical Summary: Data Protection in Function-Correcting Symbol-Pair Codes

Problem Statement
In high-density storage systems such as DNA storage and flash memory, errors often affect neighboring symbols jointly, rendering the classical Hamming metric inadequate. The symbol-pair read channel, introduced by Cassuto and Blaum, addresses this by reading consecutive pairs of symbols, necessitating the use of symbol-pair distance rather than Hamming distance. While function-correcting codes (FCCs) have been developed to recover specific functions of a message with reduced redundancy, existing frameworks typically leave the underlying message unprotected. In many practical scenarios, such as distributed computation or storage with critical attributes, it is insufficient to guarantee only the recovery of a function value; the raw data itself must also be protected against errors.

This paper addresses the gap between function protection and data protection within the symbol-pair metric. It introduces Function-Correcting Symbol-Pair Codes with Data Protection (FCSPC-DP). These codes simultaneously satisfy two distance requirements: a minimum symbol-pair distance $d_d$ between all distinct codewords (protecting the data) and a larger minimum symbol-pair distance $d_f$ between codewords whose messages map to distinct function values (protecting the function). The case where $d_f > d_d$ is termed "strict," implying the function receives genuinely stronger protection than the data without simply incurring the redundancy cost of a standard error-correcting code.

Methodology and Framework
The authors develop a theoretical framework that unifies the function-correcting paradigm with the symbol-pair channel model. Key methodological components include:

Metric Relationships: The paper establishes the relationship between the Hamming and symbol-pair metrics for function-correcting codes. It proves that for a systematic encoding, the function minimum pair-distance $d_f^p$ is bounded by $1 + d_f^H \leq d_f^p \leq 2d_f^H$ , where $d_f^H$ is the function minimum Hamming distance. This allows for the translation of constructions and bounds between the two metrics.
Redundancy Bounds via Matrices: The authors define Joint Pair-Distance Matrices (J-PDM) to characterize the redundancy requirements. They derive upper and lower bounds on the optimal redundancy $r_f^p(k, d_d, d_f)$ using these matrices, relating the problem to the existence of irregular pair-distance codes.
Two-Step Construction: Adapting the Hamming-metric two-step construction, the paper proposes a method where a systematic linear symbol-pair code first ensures the baseline data protection ( $d_d$ ), followed by a second encoding step applied to the codewords (rather than the messages) to enforce the stronger function protection ( $d_f$ ).
Graph-Theoretic Characterization: To determine the existence of strict FCSPC-DPs, the paper introduces the $\alpha$ -pair-distance graph, where vertices are codewords and edges connect those with pair-distance $\leq \alpha$ $\leq α$ . For linear codes, this graph is isomorphic to a Cayley graph. The authors define two new invariants:
- Generation Profile ( $\gamma_p^C(\alpha)$ ): The dimension of the subspace spanned by codewords of pair-weight at most $\alpha$ .
- Disconnection Threshold ( $\alpha_p^*(C)$ ): The maximum $\alpha$ for which the graph remains disconnected.
  These invariants characterize the trade-off between the strength of function protection and the number of function classes a code can support.
Pair-Separation Constant: A new metric, $\delta_p(f)$ , is introduced to measure the minimum pair-distance between messages sharing the same function value. The paper shows that if $\delta_p(f) \geq d_d$ , data protection is "free," requiring no additional redundancy beyond that needed for function protection alone.

Key Results and Contributions

Optimal Redundancy Bounds: The paper derives explicit bounds on the optimal redundancy for FCSPC-DP. It demonstrates that the redundancy is bounded by the length of irregular pair-distance codes defined by the J-PDM.
Strictness Conditions: Using the generation profile and disconnection threshold, the authors provide necessary and sufficient conditions for a linear code to serve as a strict FCSPC-DP. They trace the Pareto frontier between the function protection distance $d_f$ and the maximum number of protectable function values.
Explicit Constructions:
- For pair-locally bounded functions (where the number of distinct function values in a pair-ball of radius $\rho$ is bounded), the paper provides constructions with reduced redundancy.
- For the symbol-pair weight function, a specific construction is given that leverages the arithmetic structure of the weight to achieve stronger bounds than the general case.
Extension of Classical Bounds: The Plotkin and sphere-packing bounds are extended to the FCSPC-DP setting. The Plotkin-type bound depends on the sizes of the function's level sets, while the sphere-packing bound is refined to account for the disjointness of decoding regions for distinct function values and the separation of codewords within the same function class.
Metric Translation: The paper establishes that every Hamming-metric FCSPC-DP induces a symbol-pair code with strictly stronger protection, and conversely, every symbol-pair code yields a Hamming-metric code with roughly half the protection, providing a bidirectional bridge between the metrics.

Significance and Claims
The paper claims to present the first framework unifying data protection and the symbol-pair metric within the function-correcting code literature. Its primary significance lies in demonstrating that stronger protection for a function value does not necessarily require the full redundancy cost of protecting the entire message, provided the code's structure (specifically its generation profile) and the function's geometry (pair-separation constant) align favorably.

The authors emphasize that the problem is non-trivial because the symbol-pair distance is sensitive to the cyclic arrangement of coordinates, meaning standard Hamming-metric intuitions regarding distance graphs and connectivity do not transfer directly. By introducing the generation profile and disconnection threshold, the paper provides the necessary tools to characterize exactly which linear codes can support strict function protection and to what extent. The results show that for certain functions and codes, data protection can be achieved with zero additional redundancy, while for others, a precise trade-off between protection strength and the number of function classes is unavoidable.

More like this