Reed-Muller 码--递推编码过程举例说明

2023-02-22 08:24 作者:乐吧的数学 0人读过 | 我要投稿

录制的视频在：https://www.bilibili.com/video/BV1xx4y1F7UB/

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

$R(r%2Cm)%20%3D%20%5Cbegin%7Bcases%7D%0A%20Z_2%5E%7B2%5Er%7D%20%26%20%5Ctext%7B%20if%20%7D%20m%3Dr%20%5C%5C%0A%20%5C%7B%20(u%5C%20%20%5C%26%5C%20%20u%2Bv)%2C%20u%5Cin%20R(r%2Cm-1)%2C%20v%5Cin%20R(r-1%2Cm-1)%5C%7D%20%26%20%5Ctext%7B%20if%20%7D%20m%3Er%0A%5Cend%7Bcases%7D$

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

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

所有排列如下图所示：

例如输入比特为 $%20b_1%20b_2%20b_3%20b_4%20b_5%20b_6%20b_7$
则左侧分支的R(2,2) 分配 4 个比特，即输入比特为 $%20b_1%20b_2%20b_3%20b_4$ ，输出也是 $b_1%20b_2%20b_3%20b_4$
右侧分支的R(1,2) 分配 3 个比特，即输入比特为 $b_5%20b_6%20b_7$ ，再继续分解下去，给 R(1,1) 分配两个比特 $b_5%20b_6$ ，给 R(0,1) 分配一个比特 $b_7$ .

R(1,1) 的输入是 $b_5%20b_6$ ，输出就是

R(0,1) 的输入是 $b_7$ ，输出是 $b_7%20b_7$
则 R(1,2) 的输出为： $c_1%20c_2%20c_3%20c_4%20%3D%20b_5%20b_6%20%5C%26%20(b_5%20b_6%20%2B%20b_7%20b_7)$
那么 R(2,3) 的输出为： $b_1%20b_2%20b_3%20b_4%20%5C%26%20(%20b_1%20b_2%20b_3%20b_4%20%2B%20c_1%20c_2%20c_3%20c_4)%20$

例如：输入是 1101 001

R(2,2) 分配 4 个比特 1101

R(1,2) 分配 3 个比特 001

R(1,1) 的输入是 00，则输出为 00

R(0,1) 的输入为 1，则输出为 11

那么 R(1,2) 的输出为 $%2000%20%5C%26%20(00%20%2B%2011)%20%3D%200011$
那么 R(2,3) 的输出为 $1101%20%5C%26%20(1101%20%2B%200011)%20%3D%201101%20%5C%26%201110%20%3D%201101%201110$

表格中 u , 就是对应 $b_1%20b_2%20b_3%20b_4$ 的取值。

表格中的 v :

R(1,2) 输入为 000, R(1,1) 输入 00，输出为 00 ， R(0,1) 输入为 0，输出为 00，则 R(1,2) 输出为 00 & (00 + 00) = 0000

R(1,2) 输入为 001, R(1,1) 输入 00，输出为 00 ， R(0,1) 输入为 1，输出为 11，则 R(1,2) 输出为 00 & (00 + 11) = 0011

R(1,2) 输入为 010, R(1,1) 输入 01，输出为 01 ， R(0,1) 输入为 0，输出为 00，则 R(1,2) 输出为 01 & (01 + 00) = 0101

R(1,2) 输入为 011, R(1,1) 输入 01，输出为 01 ， R(0,1) 输入为 1，输出为 11，则 R(1,2) 输出为 01 & (01 +11) = 0110

R(1,2) 输入为 100, R(1,1) 输入 10，输出为 10 ， R(0,1) 输入为 0，输出为 00，则 R(1,2) 输出为 10 & (10 + 00) = 1010

R(1,2) 输入为 101, R(1,1) 输入 10，输出为 10 ， R(0,1) 输入为 1，输出为 11，则 R(1,2) 输出为 10 & (10 + 11) = 1001

R(1,2) 输入为 110, R(1,1) 输入 11，输出为 11 ， R(0,1) 输入为 0，输出为 00，则 R(1,2) 输出为 11 & (11 + 00) = 1111

R(1,2) 输入为 111, R(1,1) 输入 11，输出为 11 ， R(0,1) 输入为 1，输出为 11，则 R(1,2) 输出为 11 & (11 + 11) = 1100