Function-Correction with Optimal Data Protection for the General Hamming Code Membership
For coding theorists, this paper offers a novel theoretical framework and optimal construction for function-correcting codes, though it is domain-specific to Hamming code membership.
This work provides a systematic construction of single-error-correcting function-correcting codes for the Hamming code membership function, achieving optimal data protection by reducing the problem to a max-cut problem and establishing a connection to bent Boolean functions for even n.
This paper investigates single-error-correcting function-correcting codes~(SEFCCs) for the $[2^n-1,\,2^n-1-n,\,3]$-Hamming code membership function~(HCMF) for general $n\geq 2$. Necessary and sufficient conditions for valid parity assignments are established, and the distance-$3$ codeword graph is shown to induce a connected bipartite structure for all $n\geq 2$, which is exploited to develop a systematic SEFCC construction achieving the largest possible minimum distance of~$2$. A novel framework is then developed that reduces the minimization of distance-$2$ codeword pairs to a max-cut problem on the distance-$4$ graphs of the two partite sets. Eigenvectors corresponding to the minimum eigenvalue of these graphs are shown to directly yield optimal parity assignments. We reduce the problem of finding these eigenvectors to an optimization problem involving moments of the Walsh coefficients of a related function, which we solve for even~$n$ by deriving a tight lower bound shown to be attained by bent functions, establishing a precise connection between optimal SEFCC design and bent Boolean functions.