局部译码与局部纠错

两个恢复目标 ​

设编码公理库信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。 $C:{\mathrm{\Sigma }}^k\to {\mathrm{\Gamma }}^N$，接收词 $w$ 满足

$$d_H(w,C(m))\le \delta N$$

对某个消息 $m$。Locally decodable code（LDC）算法接收消息索引 $i\in [k]$，查询 $w$ 的至多 $q$ 个位置，并输出 $m_i$。要求对每个 $m$、每个上述 $w$ 和每个 $i$，

$$\text{Pr}[D^w(i)=m_i]\ge 1-\eta .$$

Locally correctable code（LCC）则接收码字坐标 $j\in [N]$，目标输出 $C(m{)}_j$。译码恢复原消息，纠错恢复未污染码字；若编码不是 systematic，两类坐标没有直接对应。

错误位置由 adversary 在算法随机币揭示前固定。若对手能看到查询后临时污染被问位置，任何少查询保证都可能失效；这属于 adaptive corruption 的另一模型。

查询与平滑性 ​

算法在坐标 oracle公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。中本地计算免费，成本是读取 $w_j$ 的次数。查询可自适应，也可一次预选；答案字母表大小决定每次返回多少 bit。

许多 LDC 还要求 smoothness：对每个目标 $i$，任一接收词位置被查询的边缘概率至多 $O(q/N)$。这样 adversary 污染 $\delta N$ 个位置时，少量随机查询不易集中撞上坏点。仅有 $q$ 小而查询总盯同一位置，不足以抗 adversarial errors。

Repetition 的多数恢复 ​

编码一 bit $b$ 为 $C(b)=b^N$。若坏位置比例至多 $1/2-\gamma$，均匀独立查询 $q$ 个位置并取多数。每个回答正确概率至少 $1/2+\gamma$；Hoeffding 界给出

$$\text{Pr}[\text{多数错误}]\le e^{-2q{\gamma }^2}.$$

所以 $q=O({\gamma }^{-2}\log \left(1/\eta \right))$ 可恢复消息 bit。算法不读取全部接收词，但 code rate 只有 $1/N$；简单局部恢复是用巨大冗余换来的。

如果错误恰好达到一半，接收词可能同时离 $0^N$ 与 $1^N$ 一样近，任何算法都无法知道原消息。半径条件不是浓缩证明的技术余项，而是唯一译码的可识别边界。

Hadamard 的二查询译码 ​

对 $a\in {\mathbb{F}}_2^k$，Hadamard 码字以 $r\in {\mathbb{F}}_2^k$ 为坐标：

$$C(a{)}_r=⟨a,r⟩(\mathrm{mod}2).$$

要恢复消息 bit $a_i$，均匀抽 $r$，查询 $w_r$ 与 $w_{r+e_i}$，输出二者异或。若两个位置都未污染，则

$$C(a{)}_r+C(a{)}_{r+e_i}=⟨a,e_i⟩=a_i.$$

每个查询位置边缘均匀；坏位置比例为 $\delta$ 时，union bound 给一次试验触碰污染的概率至多 $2\delta$。独立重复并多数表决，可在 $\delta <1/4$ 等固定半径内把错误降到常数以下，再按对数次数放大。

要纠正码字符号 $C(a{)}_z$，改为查询随机 $r$ 与 $r+z$ 并异或，因为两份正确符号之和为 $⟨a,z⟩$。同一代数恒等式分别服务 message index $e_i$ 和 codeword index $z$，输出语义仍不同。

与全局译码和测试的区别 ​

全局 unique decoder 读取足够多接收词并输出整个 $m$；LDC 每次只恢复指定符号，连续询问全部 $k$ 个消息位可能总计 $kq$ 次查询，也可能因复用样本有不同 trade-off。单次 local guarantee 不等于存在同样成本的全消息译码。

局部可测试码公理库局部可测试码Locally testable code · LTC通过少量码字符号查询区分合法码字与到整个码至少相距 ε 的接收词，并量化局部拒绝概率。只判断接收词是否接近某个码字，不知道目标 $i$，也不承诺输出数据。一个 tester 的拒绝 witness 不能直接变成正确符号，反过来一个 decoder 也未必能估计到整个码的距离。

参数与失败边界 ​

LDC/LCC 要同时报告 code length $N(k)$、rate、相对距离、纠错半径 $\delta$、查询数 $q$、成功率和 alphabet。常数查询若要求指数 block length，仍是重要但不同的 trade-off。

若接收词同时接近两个码字，目标消息不唯一；半径通常需小于码的相对距离一半。List decoding 允许输出多个候选，local list decoding 还需 advice 或候选索引，不能冒充 unique local decoder。

查询地址本身通常由随机币和目标索引决定，不能依赖未知原消息。证明若在构造查询时使用 $m$，就假设了要恢复的对象。

参考资料

• Jonathan Katz and Luca Trevisan, “On the Efficiency of Local Decoding Procedures for Error-Correcting Codes,” STOC, 2000, pp. 80–86.
• Sergey Yekhanin, “Locally Decodable Codes,” Foundations and Trends in Theoretical Computer Science 6(3), 2012, pp. 139–255.
• Oded Goldreich, Howard Karloff, Leonard J. Schulman, and Luca Trevisan, “Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval,” Computational Complexity 15, 2006, pp. 263–296.