Function-correcting symbol-pair codes protect data with low redundancy
Data Protection in Function-Correcting Symbol-Pair Codes: Redundancy Bounds and Protection Profiles
Information Theory
Summary
Some storage systems make errors that affect pairs of neighboring symbols together, which regular error detection methods don't catch well. The authors study special codes that both recover certain functions of the stored data and protect the original data itself against these paired errors. They develop mathematical limits on how much extra data (redundancy) is needed and describe new ways to build such codes. They also connect properties of these codes to graph-based measures and extend classical coding theory bounds to this scenario.
What this means in practice
- •For dna storage engineers: Design error-correcting schemes that recover data functions while securing original DNA sequences from pair-based symbol errors.
- •For flash memory developers: Implement symbol-pair error protection codes to maintain data integrity and retrieve computations over stored data in flash devices.
A theory result. No direct application yet.
Authors
Anamika Singh, Abhay Kumar Singh
Abstract
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 $α$-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.