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

基本信息

  • 论文ID: 2504.07804
  • 标题: Function-Correcting Codes for Locally Bounded Functions
  • 作者: Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti, Camilla Hollanti
  • 机构: Aalto University (Finland), Indian Institute of Science (India)
  • 分类: cs.IT, math.IT (Information Theory)
  • 发表时间: 2025年11月12日 (arXiv v3)
  • 论文链接: https://arxiv.org/abs/2504.07804

摘要

本文引入了一类新的函数——局部(ρ, λ)-有界函数，这类函数在给定的Hamming ρ-球内仅取有限个λ个值。作者为这类函数的子类开发了函数纠错码(FCCs)，并提出了基于最小码长的冗余度上界。特别地，当λ=4时，给出了充分最优性条件。论文还证明任意函数都可表示为局部(ρ, λ)-有界函数，并以Hamming权重分布函数为例进行了说明，同时提供了针对该函数的另一种FCC构造方法。

研究背景与动机

问题定义

在数据传输和存储过程中，传统的错误纠正码(ECCs)致力于保护整个消息向量免受错误影响。然而，在许多实际场景中，接收方仅关心消息的某个特定属性或函数值（如机器学习输出、Hamming权重等），而非完整消息。函数纠错码(FCCs)正是为解决这一问题而设计的。

研究重要性

  1. 效率提升：当消息很大但函数输出较小时，保护函数值比保护整个消息更高效
  2. 实际应用：在档案数据存储、机器学习算法输出保护、上下文感知弹性等场景中具有重要价值
  3. 理论意义：FCCs为信息论提供了新的研究视角，连接了编码理论和函数保护

现有方法局限

  • Lenz等人1首次提出FCCs理论，针对局部二值函数、Hamming权重函数等特定函数族设计了编码
  • 现有工作主要集中在特定函数类别，缺乏统一的理论框架
  • 对于一般函数的冗余度界限研究不够充分
  • 最优性条件的刻画不够完善

本文创新点

本文将局部二值函数推广到局部(ρ, λ)-有界函数这一更一般的框架，为更广泛的函数类别提供了系统的FCC构造方法和理论分析。

核心贡献

  1. 理论框架扩展：将局部二值函数推广为局部(ρ, λ)-有界函数，提供了更一般的函数分类体系
  2. 冗余度上界：
    • 对局部(2t, 4)-有界函数，证明了rf(k,t) ≤ 3t
    • 对一般局部(2t, λ)-有界函数，证明了rf(k,t) ≤ N(λ, 2t)
  3. 最优性条件：给出了λ=4时FCC达到最优的充分条件（Theorem 5）
  4. 函数表示定理：证明任意函数都可表示为局部(ρ, λ)-有界函数，并具体分析了Hamming权重分布函数
  5. 构造方法：提供了基于着色映射和错误纠正码的系统化FCC构造方法
  6. 应用实例：针对Hamming权重分布函数给出了简洁的最优构造

方法详解

任务定义

函数纠错码(f, t)-FCC：给定函数f: F₂ᵏ → S，系统编码C: F₂ᵏ → F₂ᵏ⁺ʳ称为(f, t)-FCC，如果对任意u₁, u₂ ∈ F₂ᵏ满足f(u₁) ≠ f(u₂)时，有： d(C(u1),C(u2))≥2t+1d(C(u_1), C(u_2)) \geq 2t+1

其中d表示Hamming距离。这确保在t个比特错误后仍能正确恢复函数值f(u)。

最优冗余度：rf(k,t)定义为存在(f, t)-FCC时编码C: F₂ᵏ → F₂ᵏ⁺ʳ的最小冗余度r。

核心概念

1. 局部有界函数

定义（函数球）：函数f: F₂ᵏ → S在u ∈ F₂ᵏ处半径ρ的函数球定义为： 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\}

定义（局部(ρ, λ)-有界函数）：如果对所有u ∈ F₂ᵏ，满足|Bf(u, ρ)| ≤ λ，则称f为局部(ρ, λ)-有界函数。

连续性条件：假设存在Im(f)上的全序≺，使得每个Bf(u, ρ)形成连续块（contiguous block）。

2. 着色映射（Coloring Mapping）

Lemma 1的核心思想：对于满足连续性条件的局部(ρ, λ)-有界函数，存在映射Colf: F₂ᵏ → λ，使得对任意d(u,v) ≤ ρ且f(u) ≠ f(v)的u,v，有Colf(u) ≠ Colf(v)。

构造方法：

  • 设Im(f) = {y₀ ≺ y₁ ≺ ... ≺ yₑ₋₁}
  • 定义γ: Im(f) → λ，γ(yⱼ) = 1 + (j mod λ)（循环着色）
  • 定义Colf(u) = γ(f(u))

由于每个函数球是大小≤λ的连续块，循环着色在其上是单射的，从而保证了分离性质。

FCC构造方法

构造1：λ=4的情况（Lemma 2）

编码函数：Enc(u) = (u, uₚ)，其中uₚ = (u'ₚ)ᵗ，且

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}$$ **正确性证明**： - **Case 1**：d(u,v) ≥ 2t+1时，直接满足d(Enc(u), Enc(v)) ≥ 2t+1 - **Case 2**：d(u,v) ≤ 2t时，由Colf性质知Colf(u) ≠ Colf(v)，故d(u'ₚ, v'ₚ) = 2，从而d(uₚ, vₚ) = 2t，加上d(u,v) ≥ 1，总距离≥2t+1 **冗余度**：rf(k,t) ≤ 3t #### 构造2：一般λ的情况（Theorem 6） **编码函数**：使用二元错误纠正码C，具有λ个码字、最小距离2t、长度N(λ, 2t)。设码字为C₁, C₂, ..., Cλ，定义： $$Enc(u) = (u, u_p), \quad u_p = C_{Col_f(u)}$$ **冗余度上界**：rf(k,t) ≤ N(λ, 2t) **关键技术点**： - 利用着色映射将函数值映射到有限集合[λ] - 通过ECC保证不同颜色对应的冗余位有足够距离 - 巧妙结合信息位距离和冗余位距离 #### 构造3：Hamming权重分布函数（Theorem 8） 对于∆ₜ(u) = ⌊wt(u)/T⌋，当(4t)/(m-1) ≥ T > (4t)/m时： **编码函数**：设a = ⌈m/2⌉ + 1，使用a个码字、最小距离2t的ECC C，定义： $$Enc(u) = (u, u_p), \quad u_p = C_{\Delta_T(u) \mod a}$$ **冗余度上界**：r∆ₜ(k,t) ≤ N(⌈m/2⌉ + 1, 2t) 特别地，当t ≥ T > 2t/3时，r∆ₜ(k,t) ≤ 3t。 ### 技术创新点 1. **统一框架**：通过局部有界性和连续性条件，将多种函数类别统一到一个框架下 2. **着色技术**：创新性地使用循环着色方法，将函数值映射问题转化为组合着色问题 3. **模块化设计**：将FCC构造分解为着色映射和ECC两个独立模块，提高了灵活性 4. **理论与构造结合**：不仅给出上界，还提供了达到上界的显式构造 5. **参数优化**：对不同参数范围给出了精细的界限分析 ## 实验设置 本文是纯理论性工作，不涉及传统意义上的实验。主要通过数学证明和理论分析验证方法的有效性。 ### 理论验证方法 1. **构造性证明**：通过显式构造满足条件的编码函数，证明冗余度上界的可达性 2. **下界分析**：使用Plotkin界和距离需求矩阵理论建立冗余度下界 3. **最优性验证**：通过匹配上下界证明特定参数下构造的最优性 ### 案例分析 #### Example 1-3：距离需求矩阵 通过具体函数f: F₂² → {0,1}展示了DRM和FDM的计算过程，验证了理论框架的可操作性。 #### Example 4：词典序重排函数 展示了满足连续性条件的具体函数： $$f(u) = 0^{k-wt(u)}1^{wt(u)}$$ 证明了其函数球Bf(u, ρ) = {0ᵏ⁻ʲ1ʲ : j ∈ Wu,ρ}形成连续块。 ## 实验结果 ### 主要理论结果 #### 1. 冗余度上界（核心结果） **Theorem 6**：对局部(2t, λ)-有界函数， $$r_f(k,t) \leq N(\lambda, 2t)$$ **Lemma 3**：N(4, 2t) = 3t（精确值） **推论**：对局部(2t, 4)-有界函数，rf(k,t) ≤ 3t #### 2. 最优性条件 **Theorem 5**：对局部(2t, 4)-有界函数，若|Im(f)| ≥ 3且存在u₁, u₂, u₃满足： - f(ui) ≠ f(uj) (i ≠ j) - d(u₁, u₂) = 1, d(u₃, u₁) = 1, d(u₃, u₂) = 2 则rf(k,t) = 3t为最优。 **证明思路**：通过Plotkin界得到下界rf(k,t) ≥ 3t，结合上界得到紧致性。 #### 3. Hamming权重分布函数 **Theorem 7**：∆ₜ是局部(2t, ⌊4t/T⌋ + 2)-有界函数 **推论**： - T > 4t：∆ₜ是2t-局部二值函数 - 4t ≥ T > 2t：∆ₜ是局部(2t, 3)-有界函数 - t ≥ T > 2t/3：r∆ₜ(k,t) ≤ 3t **Corollary 2**：Hamming权重函数是局部(2t, 4t+2)-有界函数 ### 界限比较 | 函数类型 | λ值 | 冗余度上界 | 最优性 | |---------|-----|-----------|--------| | 2t-局部二值 | 2 | 2t | 最优[1] | | 局部(2t,3) | 3 | N(3,2t) | - | | 局部(2t,4) | 4 | 3t | 条件最优 | | 一般局部(2t,λ) | λ | N(λ,2t) | - | ### 理论发现 1. **普遍性**：任意函数f: F₂ᵏ → S都可表示为局部(ρ, λ)-有界函数，其中λ = max_{u∈F₂ᵏ} |Bf(u, ρ)| 2. **参数关系**：对于Hamming权重分布函数，λ与阈值T呈反比关系：T越大，λ越小，编码效率越高 3. **码长关系**：N(4, 2t) = 3t的精确结果为λ=4情况提供了理论保证 4. **连续性重要性**：连续性条件是构造方法的关键假设，保证了着色映射的有效性 ## 相关工作 ### FCC基础理论 **Lenz et al. [1] (2023)**：首次系统提出FCC理论框架 - 定义了距离需求矩阵(DRM)和函数距离矩阵(FDM) - 针对局部二值函数、Hamming权重函数给出构造 - 建立了基本的上下界理论 ### 扩展与应用 **Xia et al. [12] (2024)**：扩展到符号对读取信道 - 提出函数纠错符号对码(FCSPCs) - 针对特定信道模型优化 **Premlal & Rajan [13] (2025)**：冗余度下界研究 - 提供了FCC冗余度的一般下界 - 证明了线性函数情况下的紧致性 **Ge et al. [14] (2025)**：Hamming权重函数优化 - 改进了Hamming权重函数的冗余度界 - 提供了达到下界的最优构造 **Singh et al. [15] (2025)**：b-符号读取信道 - 扩展到有限域上的b-符号读取信道 - 引入不规则b-符号距离码 ### 本文相对优势 1. **理论普遍性**：提供了统一的局部有界函数框架，涵盖更广泛的函数类别 2. **构造系统性**：基于着色映射的构造方法具有模块化和可扩展性 3. **参数精细化**：对不同λ值给出了精确的冗余度界限 4. **应用灵活性**：证明了任意函数都可纳入该框架，增强了理论的适用性 ## 结论与讨论 ### 主要结论 1. **理论框架**：成功建立了局部(ρ, λ)-有界函数的理论体系，推广了局部二值函数的概念 2. **冗余度界**：对满足连续性条件的局部(2t, λ)-有界函数，证明了rf(k,t) ≤ N(λ, 2t)，特别地λ=4时rf(k,t) ≤ 3t 3. **最优性**：给出了λ=4情况下达到最优的充分条件，并证明了N(4, 2t) = 3t 4. **普遍性**：证明了任意函数都可表示为局部(ρ, λ)-有界函数，扩展了FCC的适用范围 5. **应用实例**：为Hamming权重分布函数提供了简洁的最优构造 ### 局限性 1. **连续性假设**：所有构造依赖于函数球形成连续块的假设，限制了适用范围 - 不是所有局部有界函数都满足此条件 - 对于不满足连续性的函数，方法不适用 2. **二元域限制**：当前理论仅针对F₂ᵏ，对一般有限域Fqᵏ的扩展尚未完成 3. **最优性条件**：仅给出了λ=4时的充分条件，对其他λ值的最优性刻画不完整 4. **ECC依赖**：冗余度上界依赖于N(λ, 2t)的存在性，而最优ECC的构造本身是困难问题 5. **实用性验证**：缺乏实际应用场景的性能评估和复杂度分析 ### 未来方向 1. **有限域扩展**：将理论推广到一般有限域Fqᵏ（作者提到正在进行中） 2. **连续性放松**：研究不满足连续性条件的局部有界函数的FCC构造 3. **最优性完整刻画**：给出一般λ值情况下的必要充分最优性条件 4. **计算复杂度**：分析编码和解码算法的计算复杂度 5. **实际应用**：在机器学习、数据存储等实际场景中验证方法的有效性 6. **非系统码**：研究非系统FCC是否能进一步降低冗余度 ## 深度评价 ### 优点 #### 1. 理论创新性（★★★★★） - **概念推广**：从局部二值函数到局部(ρ, λ)-有界函数的推广自然且有意义 - **统一框架**：提供了处理多种函数类别的统一视角 - **技术新颖**：着色映射方法巧妙地将函数保护问题转化为组合问题 #### 2. 数学严谨性（★★★★★） - 所有定理都有完整严格的证明 - 逻辑链条清晰，从基本概念到主要结果层层递进 - 使用了组合学、编码理论的多种工具 #### 3. 结果完整性（★★★★☆） - 提供了上界和最优性条件 - 给出了显式构造方法 - 通过具体函数类别验证了理论 - 缺少下界的系统研究（主要依赖已有结果） #### 4. 写作清晰度（★★★★★） - 结构清晰，从预备知识到主要结果组织合理 - 通过具体例子帮助理解抽象概念 - 符号系统一致，定义明确 ### 不足 #### 1. 适用范围限制 **连续性假设**：Lemma 1及后续所有构造都依赖于函数球形成连续块的假设。虽然Example 4展示了满足该条件的函数，但： - 未系统刻画哪些函数满足此条件 - 对不满足条件的函数没有替代方案 - 连续性检验的复杂度未讨论 #### 2. 理论完整性 - **最优性条件**：Theorem 5仅给出λ=4的充分条件，对λ>4的情况没有类似结果 - **下界研究**：主要使用已有的Plotkin界，缺少针对局部有界函数的专门下界 - **参数优化**：N(λ, 2t)的精确值仅对λ=4给出，其他情况依赖ECC理论 #### 3. 实用性评估 - **计算复杂度**：未分析编码和解码的时间复杂度 - **实际应用**：缺少在具体应用场景（如数据存储、机器学习）中的性能评估 - **与ECC比较**：Remark 1虽然指出FCC优于ECC，但缺少定量比较 #### 4. 技术细节 - **着色映射**：循环着色是否最优？是否存在其他着色方案？ - **ECC选择**：如何选择合适的ECC以最小化N(λ, 2t)？ - **参数依赖**：冗余度对k（信息长度）的依赖关系未明确 ### 影响力 #### 对领域的贡献（★★★★☆） 1. **理论扩展**：为FCC理论提供了重要的推广，填补了局部二值函数和一般函数之间的空白 2. **方法论**：着色映射方法为后续研究提供了新工具 3. **应用潜力**：证明任意函数可表示为局部有界函数，扩大了FCC的适用范围 #### 实用价值（★★★☆☆） - **理论导向**：当前主要是理论贡献，实际应用需要进一步工作 - **构造可行**：提供的构造方法可直接实现，具有实用基础 - **参数灵活**：不同λ值对应不同应用场景，提供了设计灵活性 #### 可复现性（★★★★★） - 所有构造都有显式算法 - 证明完整，可独立验证 - 例子具体，便于理解和实现 ### 适用场景 #### 1. 理想场景 - **函数特性**：函数球形成连续块（如Hamming权重分布函数） - **参数范围**：λ较小（如λ≤4），可获得紧致界 - **应用需求**：仅需保护函数值而非完整消息 #### 2. 具体应用 - **数据存储**：档案数据的元数据保护（如文件大小、校验和） - **机器学习**：分类结果、置信度等输出保护 - **分布式计算**：中间计算结果的函数值保护 - **物联网**：传感器数据的统计量保护 #### 3. 不适用场景 - 函数球不形成连续块 - 需要保护完整消息（此时ECC更合适） - λ非常大（接近|Im(f)|），FCC优势不明显 ## 参考文献（关键文献） [1] A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, "Function-correcting codes," IEEE Trans. Inf. Theory, 2023. - **FCC开创性工作**，建立基本理论框架 [13] R. Premlal and B. S. Rajan, "On function-correcting codes," IEEE Trans. Inf. Theory, 2025. - **冗余度下界研究**，为本文提供理论基础 [14] G. Ge, Z. Xu, X. Zhang, and Y. Zhang, "Optimal redundancy of function-correcting codes," arXiv preprint, 2025. - **Hamming权重函数最优构造**，与本文构造可比较 [17] M. Plotkin, "Binary codes with specified minimum distance," IRE Trans. Inf. Theory, 1960. - **Plotkin界**，用于证明下界 --- ## 总体评分 - **理论创新**: ★★★★★ - **技术深度**: ★★★★☆ - **实用价值**: ★★★☆☆ - **写作质量**: ★★★★★ - **综合评价**: ★★★★☆ 这是一篇高质量的理论性论文，在FCC领域做出了重要的理论贡献。局部有界函数框架的提出和着色映射方法的应用都具有创新性。虽然在实用性验证和理论完整性方面还有提升空间，但作为基础理论研究，本文为后续工作奠定了坚实基础。特别适合对编码理论、信息论感兴趣的研究者阅读。