On Optimal Encodings and Systematicity in Function-Correcting Codes
Abstract
Function-correcting codes (FCCs) protect the value of a function f of the message against t errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of 2t on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs 2t. For a linear function f and a fixed linear code C, let df denote the minimum distance between codewords of messages with different function values. Different generator matrices of C assign different codewords to the messages and can give different values of df. We study which generator matrix of C gives the largest df. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of C. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of C alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic (f,t)-FCC of length n exists if and only if a condition depending on f only through the size of its smaller preimage holds. For t=1, redundancy $1$ is sufficient for every nonconstant two-valued function on 𝔽2k with k≥ 10. For general t, redundancy $1$ suffices for all two-valued functions once k is large enough, and for each s<2t we give an upper bound on the threshold in k beyond which redundancy s suffices.
Related
- On systematicity of linear function-correcting codes
- Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
- Plotkin-type Bound on Function-Correcting Codes for Monomial Mappings
- Order-Optimal Systematic Permutation Codes for Correcting t Deletions
- On Function-Correcting Lee Metric Codes with Data Protection
BibTeX
@misc{rajput2026optimal,
title = {{On Optimal Encodings and Systematicity in Function-Correcting Codes}},
author = {Charul Rajput and Kanchana Lokshmii Jagatti and B. Sundar Rajan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09011},
eprint = {2610.09011},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09011},
}
RIS
TY - UNPB
TI - On Optimal Encodings and Systematicity in Function-Correcting Codes
AU - Charul Rajput
AU - Kanchana Lokshmii Jagatti
AU - B. Sundar Rajan
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09011
UR - https://arxiv.org/abs/2610.09011
AB - Function-correcting codes (FCCs) protect the value of a function f of the message against t errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of 2t on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs 2t. For a linear function f and a fixed linear code C, let d_f denote the minimum distance between codewords of messages with different function values. Different generator matrices of C assign different codewords to the messages and can give different values of d_f. We study which generator matrix of C gives the largest d_f. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of C. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of C alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic (f,t)-FCC of length n exists if and only if a condition depending on f only through the size of its smaller preimage holds. For t=1, redundancy $1$ is sufficient for every nonconstant two-valued function on 𝔽_2^k with k≥ 10. For general t, redundancy $1$ suffices for all two-valued functions once k is large enough, and for each s<2t we give an upper bound on the threshold in k beyond which redundancy s suffices.
ER -