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

局所有界関数に対する関数訂正符号

基本情報

論文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 (情報理論)
発表日時: 2025年11月12日 (arXiv v3)
論文リンク: https://arxiv.org/abs/2504.07804

要約

本論文は、与えられたハミング ρ-球内で有限個のλ個の値のみを取る関数の新しいクラス——局所(ρ, λ)-有界関数を導入する。著者らは、このクラスの部分集合に対して関数訂正符号(FCC)を開発し、最小符号長に基づく冗長度の上界を提案する。特にλ=4の場合、十分な最適性条件を与える。論文はまた、任意の関数が局所(ρ, λ)-有界関数として表現可能であることを証明し、ハミング重み分布関数を例として示し、その関数に対する別のFCC構成方法を提供する。

研究背景と動機

問題定義

データ伝送と保存の過程において、従来の誤り訂正符号(ECC)は、メッセージベクトル全体を誤りから保護することに注力している。しかし、多くの実際のシナリオでは、受信者は完全なメッセージではなく、メッセージの特定の属性または関数値(機械学習出力、ハミング重みなど)のみに関心がある。関数訂正符号(FCC)は、この問題を解決するために設計されたものである。

研究の重要性

効率向上：メッセージが大きいが関数出力が小さい場合、関数値の保護はメッセージ全体の保護より効率的である
実際の応用：アーカイブデータ保存、機械学習アルゴリズム出力保護、文脈認識耐性などのシナリオで重要な価値を持つ
理論的意義：FCCは情報理論に新しい研究視点を提供し、符号理論と関数保護を結びつける

既存方法の限界

Lenzら1が最初にFCC理論を提案し、局所二値関数、ハミング重み関数などの特定の関数族に対して符号を設計した
既存の研究は主に特定の関数クラスに集中しており、統一的な理論的枠組みが不足している
一般的な関数の冗長度界限に関する研究が十分ではない
最適性条件の特性化が不完全である

本論文の革新点

本論文は局所二値関数を局所(ρ, λ)-有界関数というより一般的な枠組みに推広し、より広範な関数クラスに対して系統的なFCC構成方法と理論的分析を提供する。

核心的貢献

理論的枠組みの拡張：局所二値関数を局所(ρ, λ)-有界関数に推広し、より一般的な関数分類体系を提供する
冗長度上界：
- 局所(2t, 4)-有界関数に対して、rf(k,t) ≤ 3tを証明
- 一般的な局所(2t, λ)-有界関数に対して、rf(k,t) ≤ N(λ, 2t)を証明
最適性条件：λ=4のときFCCが最適に達する十分条件を与える(定理5)
関数表現定理：任意の関数が局所(ρ, λ)-有界関数として表現可能であることを証明し、ハミング重み分布関数を具体的に分析する
構成方法：着色写像と誤り訂正符号に基づく系統的なFCC構成方法を提供する
応用例：ハミング重み分布関数に対して簡潔な最適構成を与える

方法の詳細

タスク定義

関数訂正符号(f, t)-FCC：関数f: F₂ᵏ → Sが与えられたとき、系統符号C: F₂ᵏ → F₂ᵏ⁺ʳは、任意のu₁, u₂ ∈ F₂ᵏに対してf(u₁) ≠ f(u₂)のとき、以下を満たす場合(f, t)-FCCと呼ばれる： $d(C(u_1), C(u_2)) \geq 2t+1$

ここでdはハミング距離を表す。これにより、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)

補題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の場合(補題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}$

正確性の証明：

ケース1：d(u,v) ≥ 2t+1のとき、直接的にd(Enc(u), Enc(v)) ≥ 2t+1を満たす
ケース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：一般的なλの場合(定理6)

符号化関数：λ個の符号語、最小距離2t、長さN(λ, 2t)を持つ二元誤り訂正符号Cを使用する。符号語をC₁, C₂, ..., Cλとして定義： $Enc(u) = (u, u_p), \quad u_p = C_{Col_f(u)}$

冗長度上界：rf(k,t) ≤ N(λ, 2t)

主要な技術的ポイント：

着色写像を使用して関数値を有限集合λにマッピング
ECCを通じて異なる色に対応する冗長ビットが十分な距離を持つことを保証
情報ビット距離と冗長ビット距離を巧妙に結合

構成3：ハミング重み分布関数(定理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。

技術的革新点

統一的枠組み：局所有界性と連続性条件を通じて、複数の関数クラスを一つの枠組みに統一
着色技術：循環着色方法を創新的に使用し、関数値マッピング問題を組合せ着色問題に変換
モジュール化設計：FCC構成を着色写像とECCの2つの独立したモジュールに分解し、柔軟性を向上
理論と構成の結合：上界を与えるだけでなく、上界に達する明示的な構成を提供
パラメータ最適化：異なるパラメータ範囲に対して精細な界限分析を提供

実験設定

本論文は純粋な理論的研究であり、従来の意味での実験は含まない。主に数学的証明と理論的分析を通じて方法の有効性を検証する。

理論的検証方法

構成的証明：条件を満たす符号化関数を明示的に構成することにより、冗長度上界の達成可能性を証明
下界分析：Plotkin界と距離要求行列理論を使用して冗長度下界を確立
最適性検証：上界と下界を一致させることにより、特定のパラメータ下での構成の最適性を証明

ケース分析

例1-3：距離要求行列

具体的な関数f: F₂² → {0,1}を通じてDRMとFDMの計算プロセスを示し、理論的枠組みの操作可能性を検証。

例4：辞書式順序並べ替え関数

連続性条件を満たす具体的な関数を示す： $f(u) = 0^{k-wt(u)}1^{wt(u)}$

その関数球Bf(u, ρ) = {0ᵏ⁻ʲ1ʲ : j ∈ Wu,ρ}が連続ブロックを形成することを証明。

実験結果

主要な理論的結果

1. 冗長度上界(核心的結果)

定理6：局所(2t, λ)-有界関数に対して、 $r_f(k,t) \leq N(\lambda, 2t)$

補題3：N(4, 2t) = 3t(精確な値)

推論：局所(2t, 4)-有界関数に対して、rf(k,t) ≤ 3t

2. 最適性条件

定理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. ハミング重み分布関数

定理7：∆ₜは局所(2t, ⌊4t/T⌋ + 2)-有界関数

推論：

T > 4t：∆ₜは2t-局所二値関数
4t ≥ T > 2t：∆ₜは局所(2t, 3)-有界関数
t ≥ T > 2t/3：r∆ₜ(k,t) ≤ 3t

系2：ハミング重み関数は局所(2t, 4t+2)-有界関数

界限の比較

関数タイプ	λ値	冗長度上界	最適性
2t-局所二値	2	2t	最適1
局所(2t,3)	3	N(3,2t)	-
局所(2t,4)	4	3t	条件付き最適
一般的な局所(2t,λ)	λ	N(λ,2t)	-

理論的発見

普遍性：任意の関数f: F₂ᵏ → Sは局所(ρ, λ)-有界関数として表現可能であり、λ = max_{u∈F₂ᵏ} |Bf(u, ρ)|
パラメータ関係：ハミング重み分布関数に対して、λと閾値Tは反比例関係：Tが大きいほど、λが小さく、符号化効率が高い
符号長関係：N(4, 2t) = 3tの精確な結果がλ=4の場合に理論的保証を提供
連続性の重要性：連続性条件は構成方法の鍵となる仮定であり、着色写像の有効性を保証

結論と考察

主要な結論

理論的枠組み：局所(ρ, λ)-有界関数の理論体系を成功裏に確立し、局所二値関数の概念を推広
冗長度界：連続性条件を満たす局所(2t, λ)-有界関数に対して、rf(k,t) ≤ N(λ, 2t)を証明。特にλ=4のときrf(k,t) ≤ 3t
最適性：λ=4の場合に最適に達する十分条件を与え、N(4, 2t) = 3tを証明
普遍性：任意の関数が局所(ρ, λ)-有界関数として表現可能であることを証明し、FCCの適用範囲を拡大
応用例：ハミング重み分布関数に対して簡潔な最適構成を提供

限界

連続性仮定：すべての構成は関数球が連続ブロックを形成するという仮定に依存し、適用範囲を制限
- すべての局所有界関数がこの条件を満たすわけではない
- 連続性を満たさない関数に対しては方法が適用不可
二元体の制限：現在の理論はF₂ᵏのみを対象とし、一般的な有限体Fqᵏへの拡張はまだ完了していない
最適性条件：λ=4の場合のみ十分条件を与え、他のλ値の最適性特性化は不完全
ECC依存性：冗長度上界はN(λ, 2t)の存在性に依存し、最適ECCの構成自体が困難な問題
実用性検証：実際の応用シナリオにおけるパフォーマンス評価と複雑度分析が不足