Reed-Muller码--第二种构造方法

这篇文章介绍 Reed-Muller 码的第二种构造方法， Reed-Muller 码是记为 R(r,m).
(录制的视频在：https://www.bilibili.com/video/BV1824y1q7VN/)

这个方法的大体思路是：

1) 找到 k 个基向量，每个基向量长度为 n，其中 k 是输入的长度，n 是编码后输出的长度。
2) 用这 k 个基向量做线性组合，产生 Reed-Muller 码的所有输出

编码的输出，相当于是在 k 维空间中的向量，如果是比特，那么每个维度有 2 种可能，因此，一共有  种输出。

例如 R(2,4),  则

所以，是在 11 维空间中，找 11 个基向量，然后线性组合出来  种输出，每个输出的长度是 16.

那么如何找这 k 个基向量呢？

首先我们找出 m 个基向量出来，

所以，对于 R(2,4) 码，我们可以得到 4 个基向量：

第一个基向量：

第二个基向量：

第三个基向量：

第四个基向量：

然后，再从 m 个基向量中，取两个基向量，做按位与的操作，则一共可以生成   个基向量。

然后，再从 m 个基向量中，取三个基向量，做按位与的操作，则一共可以生成   个基向量。

以此类推，

最后，从 m 个基向量中，取 r 个基向量，做按位与的操作，则一共可以生成   个基向量。

最后，再增加一个全 1 的基向量，记为

至此，我们生成了 k 个基向量.

那么，我们从这 4 个中，取两个做按位与，则可以得到下面 6 个基向量：

再把  放进来

则一共有下面 11 个基向量：

16个1 的情况，有一种：

8个1的情况，有四种：

4个1的情况，有六种：

所以，一共有 11 个基向量：

则一个 11 比特的数据: ，经过这个 R(2,4) 编码后的输出 c，可以表示为：

写成矩阵形式:

则

就是 R(2,4) 码的生成矩阵。