LDC——Locally Decodable Code

1. 纠错码

纠错码(error correcting code)，在传输过程中发生错误后能在收端自行发现或纠正的码。
仅用来发现错误的码一般常称为检错码。检错码与其他手段结合使用，可以纠错。
为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别 ，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后，可以根据编码规则是否满足以判定有无错误。当不能满足时，按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。

上图中的译码过程，会恢复出所有的原码。当仅需要恢复一个原码而不是完整的所有原码时，---->于是有了LDC（Locally Decodable Code）。

2. LDC

微软的研究报告Locally Decodable Codes中指出:
Locally decodable codes are a class of error-correcting codes. Errorcorrecting codes help ensure reliable transmission of information over noisy channels. Such codes allow one to add redundancy, or bit strings, to messages, encoding them into longer bit strings, called codewords, in a way that the message can still be recovered even if a certain fraction of the codeword bits are corrupted. In typical applications of errorcorrecting codes the message is first partitioned into small blocks, each of which is then encoded separately. This encoding strategy allows efficient random-access retrieval of the information, since one must decode only the portion of data in which one is interested. Unfortunately, this strategy yields poor noise resilience, since, when even a single block is completely corrupted, some information is lost. In view of this limitation it would seem preferable to encode the whole message into a single codeword of an error-correcting code. Such a solution improves the robustness to noise but is hardly satisfactory, since one needs to look at the whole codeword in order to recover any particular bit of the message. Locally decodable codes are codes that simultaneously provide efficient random-access retrieval and high noise resilience by allowing reliable reconstruction of an arbitrary bit of the message from looking at only a small number of randomly chosen codeword bits. Local decodability comes at the price of certain loss in terms of code efficiency. Specifically, locally decodable codes require longer codeword lengths than their classical counterparts. This book introduces and motivates locally decodable codes, and discusses the central results of the subject, with the main focus on the recent constructions of codes from families of “matching” vectors.

2.1 LDC定义

LDC的具体定义如下：

2.2 Smooth LDC定义

根据queries的次数，当前的研究成果主要有：

3. LDC vs PIR(私有信息检索)

4. Hadamard code

$C_{HAD}$CHAD​的译码流程为：

$C_{HAD}$CHAD​为2-query $(2,\delta,2\delta)$(2,δ,2δ)-LDC，证明如下：

参考资料：
[1] https://baike.baidu.com/item/纠错码/2277072?fromtitle=error%20correcting%20code&fromid=11311379&fr=aladdin
[2]
[3] Locally Decodable Codes