arXiv:2507.17654cs.ITcs.DM2025-07被引 13

研究在Lee度量下函数纠错码的最优冗余,拓展了此前仅限于Z4的结论。

On Function-Correcting Codes in the Lee Metric

  • 提出不规则Lee距离码,通过长度分析推导冗余上下界
  • 给出局部有界、权重等特定函数的显式构造与性能边界
  • 首次建立线性码的Plotkin型界,可退化为二元情况下的经典结果

函数纠错码旨在最小化冗余的同时,保证对编码数据的特定函数计算可可靠恢复。度量的选择决定了需保护的计算类型及错误的度量方式。先前工作研究了在$\\(mathbb{Z}_{2^l}$, $l\geq 2$上使用同质度量的函数纠错码,该度量在$\\mathbb{Z}_4$上等价于Lee度量。本文将研究扩展至任意正整数 $m\geq 2$ 上的$\\mathbb{Z}_m$,在Lee度量下确定其最优冗余。为此,引入不规则Lee距离码,通过刻画此类码最短长度,推导出冗余的上下界,并将其应用于局部有界函数、Lee权重函数及分布函数等具体情形。扩展了刘和刘[6]在$\\mathbb{Z}_4$上的结果至更一般设置。此外,给出了Lee度量下函数纠错码的显式构造,并推导出线性码的Plotkin型界。由于Lee度量在二元域上等价于汉明度量,本界自然退化为$\\mathbb{Z}_2$上函数纠错码的Plotkin型界。

原文摘要 · Abstract (English)

Function-correcting codes are a coding framework designed to minimize redundancy while ensuring that specific functions or computations of encoded data can be reliably recovered, even in the presence of errors. The choice of metric is crucial in designing such codes, as it determines which computations must be protected and how errors are measured and corrected. Previous work by Liu and Liu [6] studied function-correcting codes over $\mathbb{Z}_{2^l},\ l\geq 2$ using the homogeneous metric, which coincides with the Lee metric over $\mathbb{Z}_4$. In this paper, we extend the study to codes over $\mathbb{Z}_m,$ for any positive integer $m\geq 2$ under the Lee metric and aim to determine their optimal redundancy. To achieve this, we introduce irregular Lee distance codes and derive upper and lower bounds on the optimal redundancy by characterizing the shortest possible length of such codes. These general bounds are then simplified and applied to specific classes of functions, including locally bounded functions, Lee weight functions, and Lee weight distribution functions. We extend the bounds established by Liu and Liu [6] for codes over $\mathbb{Z}_4$ in the Lee metric to the more general setting of $\mathbb{Z}_m$. Moreover, we give explicit constructions of function-correcting codes in Lee metric. Additionally, we explicitly derive a Plotkin-like bound for linear function-correcting codes in the Lee metric. As the Lee metric coincides with the Hamming metric over the binary field, we demonstrate that our bound naturally reduces to a Plotkin-type bound for function-correcting codes under the Hamming metric over $\mathbb{Z}_2$.

编码理论函数纠错Lee度量

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。