散文網(wǎng) » 科技 »學(xué)習(xí) » Reed-Muller 碼--遞推編碼過(guò)程舉例說(shuō)明

Reed-Muller 碼--遞推編碼過(guò)程舉例說(shuō)明

2023-02-22 08:24 作者:樂(lè)吧的數(shù)學(xué) 0人讀過(guò) | 我要投稿

錄制的視頻在：https://www.bilibili.com/video/BV1xx4y1F7UB/

我們用 R(r,m) 來(lái)表示參數(shù)為 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$

( &? 表示把前后兩個(gè)連在一起，例如 01 & 10 = 0110 )

我們舉個(gè)例子，R(2,3)，遞推圖如下：

所有排列如下圖所示：

例如輸入比特為 $%20b_1%20b_2%20b_3%20b_4%20b_5%20b_6%20b_7$
則左側(cè)分支的R(2,2) 分配 4 個(gè)比特，即輸入比特為 $%20b_1%20b_2%20b_3%20b_4$ ，輸出也是? $b_1%20b_2%20b_3%20b_4$
右側(cè)分支的R(1,2) 分配 3 個(gè)比特，即輸入比特為 $b_5%20b_6%20b_7$ ，再繼續(xù)分解下去，給 R(1,1) 分配兩個(gè)比特 $b_5%20b_6$ ，給 R(0,1) 分配一個(gè)比特 $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 個(gè)比特 1101

R(1,2) 分配 3 個(gè)比特 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 , 就是對(duì)應(yīng)?? $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