2025-11-17T17:10:13.329885

Function-Correcting Codes for Locally Bounded Functions

Rajput, Rajan, Freij-Hollanti et al.
In this paper, we introduce a class of functions that assume only a limited number $λ$ of values within a given Hamming $ρ$-ball and call them locally $(ρ, λ)$-bounded functions. We develop function-correcting codes (FCCs) for a subclass of these functions and propose an upper bound on the redundancy of FCCs. The bound is based on the minimum length of an error-correcting code with a given number of codewords and a minimum distance. Furthermore, we provide a sufficient optimality condition for FCCs when $λ= 4$. We also demonstrate that any function can be represented as a locally $(ρ, λ)$-bounded function, illustrating this with a representation of Hamming weight distribution functions. Furthermore, we present another construction of function-correcting codes for Hamming weight distribution functions.
academic

Function-Correcting Codes for Locally Bounded Functions

Basic Information

  • Paper ID: 2504.07804
  • Title: Function-Correcting Codes for Locally Bounded Functions
  • Authors: Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti, Camilla Hollanti
  • Institutions: Aalto University (Finland), Indian Institute of Science (India)
  • Classification: cs.IT, math.IT (Information Theory)
  • Publication Date: November 12, 2025 (arXiv v3)
  • Paper Link: https://arxiv.org/abs/2504.07804

Abstract

This paper introduces a novel class of functions called locally (ρ, λ)-bounded functions, which take at most λ distinct values within any given Hamming ρ-ball. The authors develop function-correcting codes (FCCs) for subclasses of these functions and propose redundancy upper bounds based on minimum code length. Particularly, when λ=4, sufficient optimality conditions are provided. The paper proves that any function can be represented as a locally (ρ, λ)-bounded function and illustrates this with Hamming weight distribution functions, while providing an alternative FCC construction method for this function class.

Research Background and Motivation

Problem Definition

In data transmission and storage, traditional error-correcting codes (ECCs) aim to protect entire message vectors from errors. However, in many practical scenarios, receivers are only concerned with specific attributes or function values of messages (such as machine learning outputs, Hamming weights, etc.) rather than complete messages. Function-correcting codes (FCCs) are specifically designed to address this problem.

Research Significance

  1. Efficiency Improvement: When messages are large but function outputs are small, protecting function values is more efficient than protecting entire messages
  2. Practical Applications: Valuable in archival data storage, machine learning algorithm output protection, context-aware resilience, and other scenarios
  3. Theoretical Significance: FCCs provide new research perspectives for information theory, bridging coding theory and function protection

Limitations of Existing Methods

  • Lenz et al. 1 first proposed FCC theory, designing codes for specific function families such as locally binary functions and Hamming weight functions
  • Existing work primarily focuses on specific function categories, lacking a unified theoretical framework
  • Research on redundancy bounds for general functions is insufficient
  • Characterization of optimality conditions is incomplete

Innovations of This Paper

This paper generalizes locally binary functions to the more general framework of locally (ρ, λ)-bounded functions, providing systematic FCC construction methods and theoretical analysis for a broader class of functions.

Core Contributions

  1. Theoretical Framework Extension: Generalizes locally binary functions to locally (ρ, λ)-bounded functions, providing a more general function classification system
  2. Redundancy Upper Bounds:
    • For locally (2t, 4)-bounded functions: rf(k,t) ≤ 3t
    • For general locally (2t, λ)-bounded functions: rf(k,t) ≤ N(λ, 2t)
  3. Optimality Conditions: Provides sufficient conditions for FCCs to achieve optimality when λ=4 (Theorem 5)
  4. Function Representation Theorem: Proves that any function can be represented as a locally (ρ, λ)-bounded function, with specific analysis of Hamming weight distribution functions
  5. Construction Methods: Provides systematic FCC construction methods based on coloring mappings and error-correcting codes
  6. Application Examples: Provides concise optimal constructions for Hamming weight distribution functions

Methodology Details

Task Definition

Function-Correcting Code (f, t)-FCC: Given a function f: F₂ᵏ → S, a systematic encoding C: F₂ᵏ → F₂ᵏ⁺ʳ is called an (f, t)-FCC if for any u₁, u₂ ∈ F₂ᵏ satisfying f(u₁) ≠ f(u₂): d(C(u1),C(u2))≥2t+1d(C(u_1), C(u_2)) \geq 2t+1

where d denotes Hamming distance. This ensures correct recovery of function value f(u) even after t bit errors.

Optimal Redundancy: rf(k,t) is defined as the minimum redundancy r of an encoding C: F₂ᵏ → F₂ᵏ⁺ʳ when an (f, t)-FCC exists.

Core Concepts

1. Locally Bounded Functions

Definition (Function Ball): The function ball of function f: F₂ᵏ → S at u ∈ F₂ᵏ with radius ρ is defined as: Bf(u,ρ)={f(u′)∣u′∈F2k and d(u,u′)≤ρ}B_f(u, \rho) = \{f(u') | u' \in \mathbb{F}_2^k \text{ and } d(u, u') \leq \rho\}

Definition (Locally (ρ, λ)-Bounded Function): A function f is called locally (ρ, λ)-bounded if for all u ∈ F₂ᵏ, |Bf(u, ρ)| ≤ λ.

Continuity Condition: Assume there exists a total order ≺ on Im(f) such that each Bf(u, ρ) forms a contiguous block.

2. Coloring Mapping

Core Idea of Lemma 1: For locally (ρ, λ)-bounded functions satisfying the continuity condition, there exists a mapping Colf: F₂ᵏ → λ such that for any u,v with d(u,v) ≤ ρ and f(u) ≠ f(v), we have Colf(u) ≠ Colf(v).

Construction Method:

  • Let Im(f) = {y₀ ≺ y₁ ≺ ... ≺ yₑ₋₁}
  • Define γ: Im(f) → λ, γ(yⱼ) = 1 + (j mod λ) (cyclic coloring)
  • Define Colf(u) = γ(f(u))

Since each function ball is a contiguous block of size ≤λ, cyclic coloring is injective on it, ensuring the separation property.

FCC Construction Methods

Construction 1: Case λ=4 (Lemma 2)

Encoding Function: Enc(u) = (u, uₚ), where uₚ = (u'ₚ)ᵗ, and

000 & \text{if } Col_f(u) = 1\\ 110 & \text{if } Col_f(u) = 2\\ 101 & \text{if } Col_f(u) = 3\\ 011 & \text{if } Col_f(u) = 4 \end{cases}$$ **Correctness Proof**: - **Case 1**: When d(u,v) ≥ 2t+1, directly d(Enc(u), Enc(v)) ≥ 2t+1 - **Case 2**: When d(u,v) ≤ 2t, by Colf property Colf(u) ≠ Colf(v), thus d(u'ₚ, v'ₚ) = 2, hence d(uₚ, vₚ) = 2t, and combined with d(u,v) ≥ 1, total distance ≥ 2t+1 **Redundancy**: rf(k,t) ≤ 3t #### Construction 2: General λ Case (Theorem 6) **Encoding Function**: Use a binary error-correcting code C with λ codewords, minimum distance 2t, and length N(λ, 2t). Let codewords be C₁, C₂, ..., Cλ, define: $$Enc(u) = (u, u_p), \quad u_p = C_{Col_f(u)}$$ **Redundancy Upper Bound**: rf(k,t) ≤ N(λ, 2t) **Key Technical Points**: - Use coloring mapping to map function values to finite set [λ] - Ensure sufficient distance between codewords corresponding to different colors via ECC - Cleverly combine information bit distance and redundancy bit distance #### Construction 3: Hamming Weight Distribution Function (Theorem 8) For ∆ₜ(u) = ⌊wt(u)/T⌋, when (4t)/(m-1) ≥ T > (4t)/m: **Encoding Function**: Let a = ⌈m/2⌉ + 1, use ECC C with a codewords and minimum distance 2t, define: $$Enc(u) = (u, u_p), \quad u_p = C_{\Delta_T(u) \mod a}$$ **Redundancy Upper Bound**: r∆ₜ(k,t) ≤ N(⌈m/2⌉ + 1, 2t) In particular, when t ≥ T > 2t/3, r∆ₜ(k,t) ≤ 3t. ### Technical Innovations 1. **Unified Framework**: Through local boundedness and continuity conditions, unifies multiple function categories under one framework 2. **Coloring Technique**: Innovatively uses cyclic coloring method, transforming function value mapping problems into combinatorial coloring problems 3. **Modular Design**: Decomposes FCC construction into two independent modules: coloring mapping and ECC, enhancing flexibility 4. **Theory-Construction Integration**: Not only provides upper bounds but also explicit constructions achieving these bounds 5. **Parameter Refinement**: Provides fine-grained bound analysis for different parameter ranges ## Experimental Setup This is a purely theoretical work without traditional experiments. Validity of methods is verified primarily through mathematical proofs and theoretical analysis. ### Theoretical Verification Methods 1. **Constructive Proofs**: Prove achievability of redundancy upper bounds through explicit construction of encoding functions satisfying conditions 2. **Lower Bound Analysis**: Establish redundancy lower bounds using Plotkin bound and distance requirement matrix theory 3. **Optimality Verification**: Prove optimality of constructions for specific parameters by matching upper and lower bounds ### Case Studies #### Examples 1-3: Distance Requirement Matrix Demonstrates computation of DRM and FDM for concrete function f: F₂² → {0,1}, verifying operability of the theoretical framework. #### Example 4: Lexicographic Reordering Function Shows concrete function satisfying continuity condition: $$f(u) = 0^{k-wt(u)}1^{wt(u)}$$ Proves that its function ball Bf(u, ρ) = {0ᵏ⁻ʲ1ʲ : j ∈ Wu,ρ} forms a contiguous block. ## Experimental Results ### Main Theoretical Results #### 1. Redundancy Upper Bounds (Core Results) **Theorem 6**: For locally (2t, λ)-bounded functions, $$r_f(k,t) \leq N(\lambda, 2t)$$ **Lemma 3**: N(4, 2t) = 3t (exact value) **Corollary**: For locally (2t, 4)-bounded functions, rf(k,t) ≤ 3t #### 2. Optimality Conditions **Theorem 5**: For locally (2t, 4)-bounded functions, if |Im(f)| ≥ 3 and there exist u₁, u₂, u₃ satisfying: - f(ui) ≠ f(uj) (i ≠ j) - d(u₁, u₂) = 1, d(u₃, u₁) = 1, d(u₃, u₂) = 2 then rf(k,t) = 3t is optimal. **Proof Strategy**: Obtain lower bound rf(k,t) ≥ 3t via Plotkin bound, combine with upper bound to achieve tightness. #### 3. Hamming Weight Distribution Function **Theorem 7**: ∆ₜ is a locally (2t, ⌊4t/T⌋ + 2)-bounded function **Corollaries**: - T > 4t: ∆ₜ is a 2t-locally binary function - 4t ≥ T > 2t: ∆ₜ is a locally (2t, 3)-bounded function - t ≥ T > 2t/3: r∆ₜ(k,t) ≤ 3t **Corollary 2**: Hamming weight function is a locally (2t, 4t+2)-bounded function ### Bound Comparison | Function Type | λ Value | Redundancy Upper Bound | Optimality | |---------------|---------|------------------------|------------| | 2t-locally binary | 2 | 2t | Optimal [1] | | Locally (2t,3) | 3 | N(3,2t) | - | | Locally (2t,4) | 4 | 3t | Conditionally optimal | | General locally (2t,λ) | λ | N(λ,2t) | - | ### Theoretical Findings 1. **Universality**: Any function f: F₂ᵏ → S can be represented as a locally (ρ, λ)-bounded function, where λ = max_{u∈F₂ᵏ} |Bf(u, ρ)| 2. **Parameter Relationships**: For Hamming weight distribution functions, λ is inversely related to threshold T: larger T yields smaller λ and higher coding efficiency 3. **Code Length Relationships**: The exact result N(4, 2t) = 3t provides theoretical guarantee for the λ=4 case 4. **Importance of Continuity**: The continuity condition is key to the construction method, ensuring validity of the coloring mapping ## Related Work ### FCC Foundational Theory **Lenz et al. [1] (2023)**: First systematic FCC theory framework - Defines distance requirement matrix (DRM) and function distance matrix (FDM) - Provides constructions for locally binary functions and Hamming weight functions - Establishes basic upper and lower bound theory ### Extensions and Applications **Xia et al. [12] (2024)**: Extension to symbol-pair read channels - Proposes function-correcting symbol-pair codes (FCSPCs) - Optimizes for specific channel models **Premlal & Rajan [13] (2025)**: Redundancy lower bound research - Provides general lower bounds for FCC redundancy - Proves tightness for linear functions **Ge et al. [14] (2025)**: Hamming weight function optimization - Improves redundancy bounds for Hamming weight functions - Provides optimal constructions achieving lower bounds **Singh et al. [15] (2025)**: b-symbol read channels - Extends to b-symbol read channels over finite fields - Introduces irregular b-symbol distance codes ### Advantages of This Paper 1. **Theoretical Universality**: Provides unified locally bounded function framework covering broader function categories 2. **Systematic Construction**: Coloring mapping-based construction method is modular and extensible 3. **Parameter Refinement**: Provides exact redundancy bounds for different λ values 4. **Application Flexibility**: Proves any function can be incorporated into this framework, enhancing theoretical applicability ## Conclusions and Discussion ### Main Conclusions 1. **Theoretical Framework**: Successfully establishes theory of locally (ρ, λ)-bounded functions, generalizing the concept of locally binary functions 2. **Redundancy Bounds**: For locally (2t, λ)-bounded functions satisfying continuity condition, proves rf(k,t) ≤ N(λ, 2t), particularly rf(k,t) ≤ 3t when λ=4 3. **Optimality**: Provides sufficient conditions for achieving optimality in λ=4 case, proves N(4, 2t) = 3t 4. **Universality**: Proves any function can be represented as locally (ρ, λ)-bounded function, expanding FCC applicability 5. **Application Examples**: Provides concise optimal constructions for Hamming weight distribution functions ### Limitations 1. **Continuity Assumption**: All constructions depend on function balls forming contiguous blocks, limiting applicability - Not all locally bounded functions satisfy this condition - No alternative methods for functions violating continuity 2. **Binary Field Restriction**: Current theory only addresses F₂ᵏ; extension to general finite fields Fqᵏ remains incomplete 3. **Optimality Conditions**: Only provides sufficient conditions for λ=4; optimality characterization for other λ values is incomplete 4. **ECC Dependence**: Redundancy upper bounds depend on existence of N(λ, 2t), while optimal ECC construction itself is a difficult problem 5. **Practical Verification**: Lacks performance evaluation and complexity analysis in actual application scenarios ### Future Directions 1. **Finite Field Extension**: Generalize theory to arbitrary finite fields Fqᵏ (authors mention ongoing work) 2. **Relaxing Continuity**: Study FCC constructions for locally bounded functions not satisfying continuity condition 3. **Complete Optimality Characterization**: Provide necessary and sufficient optimality conditions for general λ values 4. **Computational Complexity**: Analyze time complexity of encoding and decoding algorithms 5. **Practical Applications**: Verify method effectiveness in real scenarios such as machine learning and data storage 6. **Non-Systematic Codes**: Investigate whether non-systematic FCCs can further reduce redundancy ## In-Depth Evaluation ### Strengths #### 1. Theoretical Innovation (★★★★★) - **Concept Generalization**: Generalization from locally binary functions to locally (ρ, λ)-bounded functions is natural and meaningful - **Unified Framework**: Provides unified perspective for handling multiple function categories - **Novel Technique**: Coloring mapping method cleverly transforms function protection into combinatorial problem #### 2. Mathematical Rigor (★★★★★) - All theorems have complete rigorous proofs - Clear logical progression from basic concepts to main results - Employs multiple tools from combinatorics and coding theory #### 3. Result Completeness (★★★★☆) - Provides upper bounds and optimality conditions - Offers explicit construction methods - Validates theory through specific function classes - Lower bound research is systematic but relies on existing results #### 4. Writing Clarity (★★★★★) - Clear structure progressing from preliminaries to main results - Concrete examples aid understanding of abstract concepts - Consistent notation and clear definitions ### Weaknesses #### 1. Limited Applicability **Continuity Assumption**: Lemma 1 and all subsequent constructions depend on function balls forming contiguous blocks. While Example 4 demonstrates functions satisfying this condition: - Lacks systematic characterization of functions satisfying this condition - No alternative methods for non-satisfying functions - Complexity of continuity verification not discussed #### 2. Theoretical Completeness - **Optimality Conditions**: Theorem 5 only provides sufficient conditions for λ=4; no similar results for λ>4 - **Lower Bound Research**: Primarily uses existing Plotkin bound; lacks specialized lower bounds for locally bounded functions - **Parameter Optimization**: Exact values of N(λ, 2t) only provided for λ=4; other cases depend on ECC theory #### 3. Practical Evaluation - **Computational Complexity**: Time complexity of encoding and decoding not analyzed - **Real Applications**: Lacks performance evaluation in concrete scenarios (data storage, machine learning) - **ECC Comparison**: Remark 1 claims FCC superiority over ECC but lacks quantitative comparison #### 4. Technical Details - **Coloring Mapping**: Is cyclic coloring optimal? Do alternative coloring schemes exist? - **ECC Selection**: How to choose appropriate ECC to minimize N(λ, 2t)? - **Parameter Dependence**: Relationship between redundancy and k (information length) not explicit ### Impact #### Contribution to Field (★★★★☆) 1. **Theoretical Extension**: Provides important generalization of FCC theory, filling gap between locally binary functions and general functions 2. **Methodology**: Coloring mapping method provides new tools for subsequent research 3. **Application Potential**: Proves any function representable as locally bounded function, expanding FCC applicability #### Practical Value (★★★☆☆) - **Theory-Oriented**: Currently primarily theoretical; practical applications require further work - **Construction Feasibility**: Provided construction methods are directly implementable with practical foundation - **Parameter Flexibility**: Different λ values correspond to different application scenarios, providing design flexibility #### Reproducibility (★★★★★) - All constructions have explicit algorithms - Complete proofs allow independent verification - Concrete examples facilitate understanding and implementation ### Applicable Scenarios #### 1. Ideal Scenarios - **Function Characteristics**: Function balls form contiguous blocks (e.g., Hamming weight distribution functions) - **Parameter Range**: Small λ (e.g., λ≤4) achieves tight bounds - **Application Requirements**: Only function value protection needed, not complete message #### 2. Concrete Applications - **Data Storage**: Metadata protection for archival data (file size, checksums) - **Machine Learning**: Classification results and confidence score protection - **Distributed Computing**: Intermediate computation result function value protection - **IoT**: Sensor data statistical quantity protection #### 3. Inapplicable Scenarios - Function balls do not form contiguous blocks - Complete message protection required (ECC more suitable) - λ very large (approaching |Im(f)|), FCC advantage minimal ## Key References [1] A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, "Function-correcting codes," IEEE Trans. Inf. Theory, 2023. - **Pioneering FCC work**, establishes basic theoretical framework [13] R. Premlal and B. S. Rajan, "On function-correcting codes," IEEE Trans. Inf. Theory, 2025. - **Redundancy lower bound research**, provides theoretical foundation for this paper [14] G. Ge, Z. Xu, X. Zhang, and Y. Zhang, "Optimal redundancy of function-correcting codes," arXiv preprint, 2025. - **Optimal Hamming weight function construction**, comparable with this paper's constructions [17] M. Plotkin, "Binary codes with specified minimum distance," IRE Trans. Inf. Theory, 1960. - **Plotkin bound**, used for proving lower bounds --- ## Overall Rating - **Theoretical Innovation**: ★★★★★ - **Technical Depth**: ★★★★☆ - **Practical Value**: ★★★☆☆ - **Writing Quality**: ★★★★★ - **Comprehensive Evaluation**: ★★★★☆ This is a high-quality theoretical paper making important theoretical contributions to the FCC field. The introduction of the locally bounded function framework and application of the coloring mapping method are both innovative. While there is room for improvement in practical verification and theoretical completeness, as foundational theoretical research, this paper establishes solid ground for subsequent work. Particularly recommended for researchers interested in coding theory and information theory.