2025/05/14 by Verma, Gyanendra K., Singh, Anamika, Singh, Abhay Kumar · 4 citations
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2505.09473
The family of functions plays a central role in the design and effectiveness of function-correcting codes. By focusing on a well-defined family of functions, function-correcting codes can be constructed with minimal length while still ensuring full error detection and correction within that family. In this work, we explore the concept of locally (λ,ρ)-functions for b-symbol read channels and investigate the optimal redundancy of the corresponding function-correcting b-symbol codes (FCBSC) by introducing the notions of locally (λ,ρ,b)-functions. First, we discuss the values of λ and ρ for which a function can be considered as a locally (λ,ρ)-function in b-symbol metric. The findings improve some known results in the Hamming metric and present several new results in the b-symbol metric. Then we investigate the optimal redundancy of (f,t)-FCBSCs for locally (λ,ρ,b)-functions. We establish a recurrence relation between the optimal redundancy of (f,t)-function-correcting codes for the (b+1)-symbol read and b-symbol read channels. We present an upper bound on the optimal redundancy of (f,t)-function-correcting b-symbol codes for general locally (λ,ρ, b)-functions by associating it to the minimum achievable length of b-symbol error-correcting codes and traditional Hamming-metric codes, given a fixed number of codewords and a specified minimum distance. We derive some explicit upper bounds on the redundancy of (f,t)-function-correcting b-symbol codes for locally (λ,2t,b)-functions. Moreover, for the case where b=1, we show that a locally (3,2t,1)-function achieves the optimal redundancy of 3t. Additionally, we explicitly investigate the locality and optimal redundancy of FCBSCs for the b-symbol weight function and weight distribution function for b≥1.