Locally decodable codes (LDCs)

本文主要是介绍Locally decodable codes (LDCs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LDCs是一类特殊的纠错码，出自复杂理论（complexity theory），后来应用于信息理论、密码学和容错计算（fault tolerant computation）等。纠错码用于在有噪信道下可靠地传输信息，或在可能出现损坏的介质上可靠地存储信息。纠错码通常先对消息（messages）分组，再对每组（block）编码得到若干码字。这种编码策略允许高效的随机访问（random-access）信息，也就是只需要解码一个码字就可以恢复消息中想要的某个符号，缺点是对噪声的抵抗能力较弱，若是一整个码字都出现错误则完全丢失一部分信息。将整个消息编码为一个码字（不分组）的方法可提高编码的抗噪声能力，但为恢复某个符号就得解码整个码字，解码复杂度非常高。LDCs在保证一定纠错能力的同时，将恢复单个符号的时间减少到sublinear-time。

Classical LDC将 $n$ 个符号组成的消息编码为 $N$ 个码符号组成的码字，在码字与消息的汉明距离不超过 $\delta N$ （容错）的前提下，保证能从至多 $k$ 个码符号中，在误码概率小于 $\epsilon$ 的同时，恢复某个消息符号。值得一提的是，解码单个消息符号的 $k$ 个码符号构成这个消息符号的一个解集（decoding set），一个消息符号的解集数目可以不止一个，它的所有解集构成这个消息符号的解超集（decoding superset）。通常不同消息符号的解超集的重叠度越高，这个LDC的保密性越强。对于一个LDC，若所有消息符号的解超集完全相同，即任意消息符号的所有解集同时也是其他任意消息符号的解集，这个LDC可用于构造Private Information Retrieval (PIR) scheme。

Perfectly Smooth LDC (SLDC) 要求任意消息符号的解集可均匀选择，即每个码符号构成的任意消息符号的解集的数量与其构成的其他任意消息符号的解集的数量相同。

Universal LDC (ULDC)要求每个码符号用于构成的任意消息符号的至少一个解集。

LDC问题的与Information Retrieval问题之间存在很强的联系。任意ULDC可用于构造Repudiative Information Retrieval （RIP）scheme，任意SLDC可用于构造PIR scheme。若定义一个LDC的速率（rate）为每个消息符号的比特数与每个码符号的比特数的比值，定义该速率可取到的最大值（supremum）为LDCs的容量。部分容量可达的PIR scheme也可用于构造SLDC，进而确定了SLDC的速率的一个下界，由于SLDC是ULDC的特殊情况（special case），SLDC的速率的下界也是ULDC的速率的下界，此外，ULDC的速率的上界也一定是SLDC的速率的上界，否则违背论点：任意SLDC也是ULDC。利用这些论点（argument），文章[2]证明了ULDC和SLDC的容量同为 $N(1+1/N+1/N^2+\ldots+1/N^{K-1})^{-1}$ （该容量定义下的）。