【密码学】基于编码的密码学学习笔记(三) 检错、纠错的能力

本篇文章，我们接着来聊编码的相关知识，在之前的文章当中，我们已经了解了相关记号，以及了解了我们应该按照什么样的策略来进行解码。本篇文章呢，我们来看一下，对于一个编码，他所能够容忍的最多的错误数目，这里，我们用一个精确一点的来描述下。

e-错误检测码

一个编码，它最多能够检测e个错误，或者更少的错误，我们称这个编码为 e-错误检测码(e-error detecting code)。

来看一个例子，这个例子用我们之前提过的，重复码

显然，上面的编码是一个2-错误检测码，但不是一个3-错误检测码。

这里，我们需要考虑的是，对于给定的编码，他最多能检测多少个错误，读者不妨先自己思考一下，回顾一下，前面我们讲解过的知识可以用哪个量来衡量。

答案是码的汉明距离，对于一个编码，他的距离是d，那么他最多能够检测d-1个错误，而不能检测d个错误，这个结论其实比较显然，为啥呢，因为，如果发生了d个错误，那么他就能够从一个码字，改成另外一个码字，这种情况是无法被检测出来的。

e-错误修正码

同样的，我们可以来定义 e-错误修正码(e-error correcting code)，如果一个编码它能够纠正至多e个错误。

还是用上面提过的重复码的例子，

这里，上面的编码是一个1-错误修正吗，而不是2-错误修正码。

这里，同样的，我们考虑一个编码，最多能修正多少个错误，这个就没有那么显然了，实际上

这里，简单的来证明一下吧，假设, 最多发生了个错误，令收到的消息是，我们有

另一方面，对于任意的其他码字，我们有

因此，根据我们之前提到的解码的策略，c和r之间的距离是最小的，可以正确的纠正。为了更好的理解呢，这里我们用一个图来模拟一下，我们把编码看做二维平面上的点，那么具体的每一个点就是一个码字，然后，两个点直接的距离，就是两个码字之间的距离。

这里，我们考虑，对于每一个点，其实他都有一个半径，也就是，在这个半径之内，我们都可以纠错成为这一个点。

那么，我们考虑最大的半径，也就是我们任意两个点所在的圆不重叠，也就是最大的半径就是

了，从这里来看，每个点相隔的越远，那么实际上我们能够纠错的能力越强，但是，我们能够在单位空间当中，放置的消息也就越少。相反，码字距离越小，单位空间容纳的消息就越多，但是纠错能力就越弱。

实际上，这里，读者应该可以发现，这实际上是一个最密堆积的问题[4]，这里采用二维的密堆积，

显然，按照上面的排列来看的话，这个空间的利用率不会是最优的。

对于上面这更情况，整个编码的效果就会较好，上图只是演示，不代表具体的编码。

总结

本文，我们主要是讨论了对于一个编码，他的理论最大的纠错和检错的能力，对于编码理论的目标，应该是努力想着这个值来靠近(个人理解)，同时要兼顾效率。好了，有关于编码的基本的前置知识，到这里就讲解的差不多了，后面，我们会主要来看线性码，因为整个系列的核心是基于编码的密码学，而线性码是广为使用的，这里，对于后文，不再补充有关于线性代数以及抽象代数(近世代数)的知识了，读者自行查阅相关资料或者看下我之前的文章吧。好了，快乐的时光过的特别快，又到了说再见的时候了，咱们下次再见~~

参考资料

1. https://courses.smp.uq.edu.au/MATH3302/2010/files/codingnotes.pdf
2. https://link.springer.com/chapter/10.1007/978-3-540-88702-7_4
3. https://www.itsoc.org/sites/default/files/2021-11/Code-Based%20Cryptography.pdf
4. https://zh.wikipedia.org/zh-cn/%E6%9C%80%E5%AF%86%E5%A0%86%E7%A7%AF