Reed-Muller码 -- 构造

这篇文章我们讲一下线性分组码中的一种，称为 Reed-Muller 码，主要先讲一下其编码过程，背后的数学理论，将另辟文章来讲解。本文需要的背景知识只有 "线性分组码的基本定义和概念"。
(录制的视频：https://www.bilibili.com/video/BV1xx4y1L7Dc/ ）

Reed-Muller 码是一种线性分组码，我们知道，线性分组码有两个基本的参数，即 (n,k)，表示 输入 k 个符号，产生 n  个符号，则增加的冗余校验符号有 n-k 个，当然，如果是符号是二进制的情况，则是 输入 k 个比特，产生 n 个比特。

Reed-Muller 码用 (r,m) 来表示上面两个基本参数，对应编码后输出符号长度为：

例如 (2,3) 的 Reed-Muller 码，其输出的符号长度为  ， 即输出符号长度为 8.

可以猜测到，输入符号的长度与 (r,m) 中的 r 有关：

其中

例如：(2,3) 的 Reed-Muller 码：

所以 (2,3) 的 Reed-Muller，就是 (8,7) 的线性分组码.

Reed-Muller 码的编码，有很多种描述的方法，本文先讲一个基本的递推(Recursive) 方法。

我们用 R(r,m) 来表示参数为 r 和 m 的 Reed-Muller 码. 则递推(Recursive)公式为：

( &  表示 把前后两个连在一起，例如 01 & 10 = 0110 )

其中 ，表示长度为  的序列，是一个所有可能取值的全排列，例如：r=2


上面的递推，要么递推到 R(r,m), r=m ，或者递推到 R(0,m).

我们举个例子，R(2,3)，递推图如下：

根据上图，则需要先列出来所有的叶子节点:

以及

和


根据图的递推关系，则:

再根据图示的递推，则：


公式(5) 的所有排列如下图所示：