.png){kind=icon}
.png){kind=icon}
Return
Optimal Redundancy of Function-Correcting Codes
.png){kind=icon}
PRE
AI
DOI：10.1109/TIT.2025.3626715.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Function-correcting codes (FCCs), introduced by Lenz, Bitar, Wachter-Zeh, and Yaakobi, protect specific function values of a message rather than the entire message. A central challenge is determining the optimal redundancy-the minimum additional information required to recover function values amid errors. This redundancy depends on both the number of correctable errors t and the structure of message vectors yielding identical function values. While prior works established bounds, key questions remain, such as the optimal redundancy for functions like Hamming weight and Hamming weight distribution, along with efficient code constructions. In this paper, we make the following contributions. First, for the Hamming weight function, we improve the lower bound on optimal redundancy from 10/(t-1)3 to 4t-4/3 root 6t+2+2 . On the other hand, we provide a systematical approach to constructing explicit FCCs via a novel connection with Gray codes, which also improve the previous upper bound from 4t-2/1-2 root ln(2t)/(2t) to 4t-inverted right perpendicularlog tinverted left perpendicular. Consequently, we almost determine the optimal redundancy for Hamming weight function. Second, the Hamming weight distribution function is defined by the value of Hamming weight divided by a given integer T is an element of N . Previous work established that the optimal redundancy is 2t when T>2t , while the case T <= 2t remained unclear. We show that the optimal redundancy remains 2t when T >= t+1 . However, in the surprising regime where T=o(t) , we achieve near-optimal redundancy of 4t-o(t) . Our results reveal a significant distinction in behavior of redundancy for distinct choices of T .
Keywords:
Redundancy
Codes
Hamming weight
Vectors
Radio frequency
Encoding
Germanium
Zirconium
Systematics
Hamming distances
Function-correcting code
optimal redundancy
Hamming weight function
Hamming weight distribution function
Journal
I
IF:
2.9
Papers:
317
Citations:
0
Organization
View more organizations