局部译码与局部纠错

全局译码先重建整条消息，局部算法则把问题倒过来：目标索引先给出，算法只需从受损长码字中找到足够支撑这一符号的少量冗余关系。好的码会把每个目标分散到许多不同查询组合中，使 adversary 即使污染固定比例的位置，也难以同时破坏大多数可用视图。

Smoothness 正是在形式化这种分散性。查询少并不代表鲁棒；若所有随机路径都经过同一坐标，对手只改一个位置便能让它们一起失效。局部可恢复结构必须同时提供短关系和足够均匀的落点。

Repetition 的多数恢复 ​

编码一 bit $b$ 为 $C(b)=b^N$。取 $0<\gamma \le 1/2$ 与 $0<\eta <1/2$。若坏位置比例至多 $1/2-\gamma$，均匀独立查询奇数 $q$ 个位置并取多数。每个回答正确概率至少 $1/2+\gamma$；Hoeffding 界理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。给出

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

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

Hadamard 的二查询译码 ​

对 $a\in {\mathbb{F}}_2^k$，Hadamard 线性码理路线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。的码字以 $r\in {\mathbb{F}}_2^k$ 为坐标：

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

每个查询位置边缘均匀；坏位置比例为 $\delta$ 时，并合界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。给一次试验触碰污染的概率至多 $2\delta$；同一次试验的两个位置相关，并合界不要求它们独立。用独立重复与多数表决理路概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。，对 $0<\eta <1/2$，当 $\delta <1/4$ 时优势至少 $1/2-2\delta >0$，取 $O((1/2-2\delta {)}^{-2}\log \left(1/\eta \right))$ 次重复可把错误降至 $\eta$。只有半径与 $1/4$ 保持固定间隔时，这个优势损失才可藏进常数。

要纠正码字符号 $C(a{)}_z$，改为查询随机 $r$ 与 $r+z$ 并异或，因为两份正确符号之和为 $⟨a,z⟩$。当 $z=0$ 时，目标恒为零，可直接零查询返回；其余 $z$ 使用上述二查询。这个代数恒等式分别服务 message index $e_i$ 和 codeword index $z$，输出语义仍不同。

参数与失败边界 ​

LDC/LCC 要同时报告 code length $N(k)$、rate、相对距离、纠错半径 $\delta$、查询数 $q$、成功率和 alphabet。两种字母表不同时，归一化码率是 $k\log |\mathrm{\Sigma }|/(N\log |\mathrm{\Gamma }|)$，只有字母表相同才简化为 $k/N$。常数查询若要求指数 block length，仍是重要但不同的 trade-off。

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

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

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

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

局部可测试码理路局部可测试码Locally testable code · LTC通过少量码字符号查询区分合法码字与到整个码至少相距 ε 的接收词，并量化局部拒绝概率。要求接受合法码字、拒绝远离整个码的接收词；它不接收恢复目标 $i$，也不承诺输出数据。一个 tester 的拒绝 witness 不能直接变成正确符号，反过来一个 decoder 也未必能估计到整个码的距离。

局部译码还与多服务器的信息论 private information retrieval 有直接联系，但上述 smoothness 上界本身不提供隐私。例如 $N$ 为偶数，一个目标只在前半位置均匀查询，另一个只在后半位置均匀查询；每个位置的概率都至多 $2/N$，服务器却能由所在半区完全识别目标。完美的单服务器视图隐私要求：对每个服务器，其收到的查询分布与目标索引无关。[1]

Hadamard 的二查询给出具体实现。两台互不串通的服务器各保存同一码字，用户向第一台发送均匀 $r$，向第二台发送 $r+e_i$，收到两 bit 后异或。每台单独看到的地址都均匀分布，与 $i$ 无关；无错误码字上答案恰为 $a_i$。两台若合并地址，则能算出 $e_i$，所以不串通假设不可省略。这里还要计入两条地址各 $k$ bit、两条回答各一 bit，以及指数长度的共享编码；两次查询不等于两 bit 总通信。