2.5 Reed-Muller码

Reed-Muller（RM）码是1954年提出的一类重要的线性分组码，长为32的一阶RM码在1969―1977年被应用于美国的Mariner-class深空探测系统，后来在许多任务中逐渐被RS码所取代。对于码长n≤32的码，RM码是目前已知的最小距离等于2的幂次的最好分组码。对于更大的码长，它们一般不是最好的码。但是由于RM码有相对简单快速的最大似然译码算法，至今在工程实践中仍有吸引力。最近，文献[72]证明RM码在BEC上能够达到容量限。在5G通信系统中，RM码被用作控制信道编码方法之一。

RM码是一类二元线性分组码，它能够使用大数逻辑译码算法进行译码。对任意整数m ≥ 0和0 ≤ r ≤ m，存在一个码长n=2m的r阶RM码，记为RM(r, m)，其最小Hamming距离dH, min=2m-r。关于RM(r, m)码的最小重量码字个数，有如下计算公式：

2.5.1 构造方法

1．基于分量乘积的构造

给定GF(q)上的两个向量a=(a0, a1, · · ·, an-1)和b=(b0, b1, · · ·, bn-1)，它们的分量式乘积（componentwise product）定义为

ab=(a0b0, a1b1, · · ·, an-1bn-1)

一个RM(r, m)码的生成矩阵G是

其中，G0=[g0]是1 × n的全1矩阵。

是m(×n)的矩阵，每一个二元m-重（tuple）作为矩阵的列向量且仅出(现一)次。G2是的矩阵，其行向量为G1中两行的分量式乘积。Gℓ是的矩阵，其行向量为从G1中取ℓ行进行分量式相乘的结果。

所以，生成矩阵G的总行数为。从而得到RM码的维数（信息位长度）为

作为一个例子，考虑n=8, m=3, r=2的RM码，其生成矩阵构造如下。

这样，码长为8的RM(2,3)码的生成矩阵为

2．长度加倍(length-doubling)构造(|u|u+v|构造)

RM(r, m)码可由RM(r-1, m-1)和RM(r, m-1)用如下方法获得。

其生成矩阵为

值得说明的是，|u|u+v|构造提供了一种从短码构造高性能长码的技术。其他从短分量码来构造好的长码的典型方法还有串（并）行级联码、乘积码和耦合码等。

3．Kronecker构造

令。定义G(2,2)的m-重(fold)Kronecker积为

这是一个大小为2m× 2m的矩阵。RM(r, m)码的生成矩阵G通过选择中那些重量大于或等于2m-r的行作为G的行而获得。

具有参数r=m-1的码是单奇偶校验码，最小Hamming距离dmin=2;r=m-2时的码是扩展Hamming码，其最小距离dmin=4。

对RM码进行打孔，可以得到码长为2m-1的循环RM码。对于0 ≤ r ≤m-1, RM(m-r-1, m)是RM(r, m)的对偶码。

2.5.2 一阶RM码的编码与译码

一般的RM码可以采用大数逻辑译码算法进行硬判决译码，而对于一阶RM码，我们有高效的软判决译码算法。RM(1, m)码是(2m, m+1,2m-1)分组码。

1．RM(1, m)码的编码

考虑一个RM(1,3)码，其码字c=(c0, c1, · · ·, c7)为

矩阵G的列由数字(1000)～(1111)组成，并以递增的二进制计数顺序排列。这个比特序列可以通过常规的二进制计数器获得，如图2.6所示。

2．RM(1, m)码的译码

译码器的基本思想是将接收序列y与RM(1, m)码中的每一个码字做相关运算，然后选择具有最大相关值的码字作为译码输出。因为RM(1, m)码的特殊性，该相关运算能够使用快速Hadamard变换来实现，从而获得一种高效的译码算法。

令c=(c0, c1, · · ·, cn-1)表示发送的码字，x=F(c)=1-2c是c的双极性表示（BPSK调制信号）, y=(y0, y1, · · ·, yn-1)表示对应的接收序列（取实数值）, z为y的硬判决值。定义相关函数

可以证明，最小距离译码等价于最大相关译码，即

因此，ML译码算法为：给定接收向量y，对所有2m+1个码字ci计算Ti=corr(y, xi)，其中xi=1-2ci，然后选择使corr(y, xi)最大的码字。对于一阶RM码，所有这些相关值可以通过y的快速Hadamard变换（FHT）同时计算得到：

其中，为2m阶Hadamard矩阵，它是基于用Sylvester方法构造的。

令i=(i1, i2, · · ·, im-1, im)2是i的二进制表示，其中im为最低有效位（LSB）。观察RM(1, m)码的生成矩阵与的列向量之间的关系，则有

这样，接收向量y的Hadamard变换就给出了y与所有码字{ci}的相关值，其中{ci}是{g1, g2, · · ·, gm}的线性组合。

因为-Yi是y与F(1+ci)=F(1+i1g1+· · ·+imgm)的运算结果，所以只需计算y与RM(1, m)中一半码字的相关值来确定最大似然码字。

基于FHT的译码算法小结如下。

（1）给定接收向量y∈Rn，计算Hadamard变换。

（2）找出Yi有最大幅度值的索引序号i，令i的二进制表示为(i1, i2, · · ·, im-1, im), ij∈{0,1}，其中im为最低位。

（3）如果Yi为正，则ML码字；如果Yi为负，则ML码字。

FHT有m级，每一级需要执行2m次加法/减法运算，所以总复杂度是m2m。使用FHT的RM(1, m)译码算法被称为“Green Machine”，以纪念喷气推进实验室（JPL）为1969 Mariner深空通信系统做出贡献的算法开发者。

例2.2 考虑RM(1,3)码的译码。RM(1,3)码的生成矩阵为

Hadamard矩阵H8为

如果译码器的输入接收向量y=(-1,1,1,1,1,1, -1, -1)，则Y=yH8=(2, -2,2, -2,2, -2, -6, -2)。第6个分量(6↔(110))有最大幅度值|-6|，故最大似然码字是。