【密码学】基于编码的密码学学习笔记(八) 线性码的距离

在上一篇的文章当中，我们讲解了如何利用编码来设计一个加密体系，但是目前，我们还遗留了一些问题，首先，我们先来看一下对于线性码，如何计算计算它的距离。

知识回顾

首先，我们还是先来简单回顾一下，有关于编码距离的知识。

汉明距离

「比较两个」长度相同的二进制序列（我们称为“码字”），看看它们有多少个位置上的数字不一样。这个不一样的位置数量，就是它们的「汉明距离」。

线性码的最小距离d

一个线性码包含许多有效的码字。线性码的最小距离d是指在这个码中，「所有不同码字对之间汉明距离的最小值」。

距离的计算

对于一般的编码来说，距离的计算是一个比较困难的过程，比如，下面这个编码。

我们，如果需要来计算他们之间的距离，我们只能两两的距离做一个计算，然后找到他们最短的一个距离。

可以发现，对于上面这个编码，如果要计算距离，我们需要比较的次数可以根据组合数来计算。

可以发现，比较的次数还是非常多的，我们以之前用过的汉明码为例，码字的数量是个，因此，如果我们要挨个比较，我们需要比较

次，显然，随着码字数量的增加，这个方案来计算，显得不是特别的优雅。

线性码的特点

我们考虑，线性码的特点，也就是，在线性组合之后，依然是一个码字，因此，我们想要计算一个线性码的最短距离，我们只需要枚举所有的码字即可，因此，对于上面的汉明码的例子，我们需要计算的次数仅仅为次

但是，这个方案，对于一般的编码来说，还是可以用的，比如对于一个字节的编码，但是这种方案在k特别大的时候，计算的复杂度还是非常高的，因此我们需要找到一个方案来快速的计算其距离。

校验矩阵计算法

在之前的文章当中，我们学习了在线性码当中的一个非常重要的概念，也就是校验矩阵，这里，我们来看一个定理。

❝

令H是线性码的校验矩阵，则如果对于H中每s-1列线性无关。

❞

那么，我们来证明一下吧，不感兴趣的读者，可以自行跳过蛤。

设是H的最小线性相关列组()，也就是存在不全为0的系数使得

因此，我们可以构造码字，其中（若）否则，根据由于

因此，我们有，且，由于上文所说的线性码的特点，我们有

然后，我们令，并且，根据校验矩阵的性质，我们有

这里，必定有列线性相关，因为和为0，因此我们有，综上所述，我们有.

样例

接下来，我们来看一个例子，还是用之前文章当中的例子来讲解，对于汉明码，我们有生成矩阵

以及他的校验矩阵

从上面，我们不难看出，对于汉明码，他最小的线性相关的列数为3，因此.

总结

本文，我们讲解了如何来计算线性码距离的一个方案，由于线性码的特殊性，对于一些线性码，我们还是有一定的方案来快速计算他的距离的，这对于后续我们设计基于编码的密码体系非常有用，好了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见~~

参考资料

1. https://en.wikipedia.org/wiki/Linear_code
2. https://courses.smp.uq.edu.au/MATH3302/2010/files/codingnotes.pdf
3. https://link.springer.com/chapter/10.1007/978-3-540-88702-7_4
4. https://www.itsoc.org/sites/default/files/2021-11/Code-Based%20Cryptography.pdf