TY - JOUR
T1 - Function-Correcting Codes
AU - Lenz, Andreas
AU - Bitar, Rawad
AU - Wachter-Zeh, Antonia
AU - Yaakobi, Eitan
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2023/9/1
Y1 - 2023/9/1
N2 - In this paper we study function-correcting codes, a new class of codes designed to protect the function evaluation of a message against errors. We show that FCCs are equivalent to irregular-distance codes, i.e., codes that obey some given distance requirement between each pair of codewords. Using these connections, we study irregular-distance codes and derive general upper and lower bounds on their optimal redundancy. Since these bounds heavily depend on the specific function, we provide simplified, suboptimal bounds that are easier to evaluate. We further employ our general results to specific functions of interest and compare our results to standard error-correcting codes, which protect the whole message.
AB - In this paper we study function-correcting codes, a new class of codes designed to protect the function evaluation of a message against errors. We show that FCCs are equivalent to irregular-distance codes, i.e., codes that obey some given distance requirement between each pair of codewords. Using these connections, we study irregular-distance codes and derive general upper and lower bounds on their optimal redundancy. Since these bounds heavily depend on the specific function, we provide simplified, suboptimal bounds that are easier to evaluate. We further employ our general results to specific functions of interest and compare our results to standard error-correcting codes, which protect the whole message.
KW - Forward error correction
KW - error correction codes
KW - information theory
UR - http://www.scopus.com/inward/record.url?scp=85161004062&partnerID=8YFLogxK
U2 - 10.1109/TIT.2023.3279768
DO - 10.1109/TIT.2023.3279768
M3 - Article
AN - SCOPUS:85161004062
SN - 0018-9448
VL - 69
SP - 5604
EP - 5618
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 9
ER -