Existence and Constructions of Strict Function-Correcting Codes with Data Protection
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917447017168896 |
|---|---|
| author | Rajput, Charul Rajan, B. Sundar Freij-Hollanti, Ragnar Hollanti, Camilla |
| author_facet | Rajput, Charul Rajan, B. Sundar Freij-Hollanti, Ragnar Hollanti, Camilla |
| contents | Function-correcting codes with data protection simultaneously protect both the data and a function of the data at distinct error-correction levels. When the function receives strictly stronger protection than the data, such a code is called a strict function-correcting code with data protection. While prior work showed that perfect and MDS codes cannot serve as strict function-correcting codes, which codes can serve this role, and how to construct them, has remained open. In this paper, we address the existence and construction of strict function-correcting codes for linear codes through three main contributions. First, using the $α$-distance graph framework from our prior work, we establish a graph-theoretic existence condition under which a code can serve as a strict function-correcting code. For linear codes, we prove this distance graph is isomorphic to a Cayley graph, which implies the connected components are cosets of the subcode generated by low-weight codewords. This transforms the existence problem into a subcode generation problem. Second, a classical result of Simonis shows any linear code can be transformed into one with the same parameters whose basis consists entirely of minimum-weight codewords. We develop a converse construction: under certain conditions on the weight distribution, a linear code can be transformed into a new code with the same parameters but fewer independent minimum-weight codewords, thereby producing codes suitable for use as strict function-correcting codes. As a source of codes satisfying these conditions, we introduce chain codes, an infinite family of linear codes generated by their minimum-weight codewords. Third, we present an independent construction of strict function-correcting codes from narrow-sense BCH codes with designed distance three, by proving the minimum-weight codewords of such codes are contained in a proper subcode. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26397 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Existence and Constructions of Strict Function-Correcting Codes with Data Protection Rajput, Charul Rajan, B. Sundar Freij-Hollanti, Ragnar Hollanti, Camilla Information Theory 94B05 Function-correcting codes with data protection simultaneously protect both the data and a function of the data at distinct error-correction levels. When the function receives strictly stronger protection than the data, such a code is called a strict function-correcting code with data protection. While prior work showed that perfect and MDS codes cannot serve as strict function-correcting codes, which codes can serve this role, and how to construct them, has remained open. In this paper, we address the existence and construction of strict function-correcting codes for linear codes through three main contributions. First, using the $α$-distance graph framework from our prior work, we establish a graph-theoretic existence condition under which a code can serve as a strict function-correcting code. For linear codes, we prove this distance graph is isomorphic to a Cayley graph, which implies the connected components are cosets of the subcode generated by low-weight codewords. This transforms the existence problem into a subcode generation problem. Second, a classical result of Simonis shows any linear code can be transformed into one with the same parameters whose basis consists entirely of minimum-weight codewords. We develop a converse construction: under certain conditions on the weight distribution, a linear code can be transformed into a new code with the same parameters but fewer independent minimum-weight codewords, thereby producing codes suitable for use as strict function-correcting codes. As a source of codes satisfying these conditions, we introduce chain codes, an infinite family of linear codes generated by their minimum-weight codewords. Third, we present an independent construction of strict function-correcting codes from narrow-sense BCH codes with designed distance three, by proving the minimum-weight codewords of such codes are contained in a proper subcode. |
| title | Existence and Constructions of Strict Function-Correcting Codes with Data Protection |
| topic | Information Theory 94B05 |
| url | https://arxiv.org/abs/2604.26397 |