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)正是为解决这一问题而设计的。

研究重要性

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

现有方法局限

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

本文创新点

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

核心贡献

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

方法详解

任务定义

函数纠错码(f, t)-FCC：给定函数f: F₂ᵏ → S，系统编码C: F₂ᵏ → F₂ᵏ⁺ʳ称为(f, t)-FCC，如果对任意u₁, u₂ ∈ F₂ᵏ满足f(u₁) ≠ f(u₂)时，有： $d(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₂ᵏ处半径ρ的函数球定义为： $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'ₚ)ᵗ，且 $u'_p = \begin{cases} 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