Optimal Redundancy of Function-Correcting Codes

Zhang, Yijun

doi:10.1109/TIT.2025.3626715

2025-12-01

PRE

DOI：10.1109/TIT.2025.3626715

原文链接

原文求助

摘要

En 中文

函数纠错码（FCCs），由Lenz、Bitar、Wachter-Zeh和Yaakobi引入，保护的是消息的特定函数值而非整个消息。核心挑战在于确定最优冗余度——即在有误码情况下恢复函数值所需的最小附加信息量。该冗余度取决于可纠正的错误数t以及产生相同函数值的消息向量的结构。尽管先前工作建立了界限，但仍存在关键问题，例如对于汉明重量和汉明重量分布等函数的最优冗余度以及高效码构造。在本文中，我们做出以下贡献。首先，针对汉明重量函数，我们将最优冗余度的下界从10/(t-1)³改进为4t-4/√(6t+2)+2。另一方面，我们通过一种新颖的与格雷码的联系，提供了一种系统化的显式FCC构造方法，该方法也将先前上界从4t-2/(1-2√(ln(2t)/(2t)))改进为4t-⟨log t⟩。因此，我们几乎确定了汉明重量函数的最优冗余度。其次，汉明重量分布函数定义为汉明重量值除以一个给定的自然数T。先前工作已确立当T>2t时最优冗余度为2t，而T≤2t的情况尚不明确。我们证明当T≥t+1时最优冗余度仍为2t。然而，在令人惊讶的T=o(t)区间，我们实现了近最优的4t-o(t)冗余度。我们的结果表明，对于不同的T选择，冗余度的行为存在显著差异。

Keyword:

Redundancy

Codes

Hamming weight

Vectors

Radio frequency

Encoding

Germanium

Zirconium

Systematics

Hamming distances

Function-correcting code