這篇文章我們講一下線性分組碼中的一種，稱為 Reed-Muller 碼，主要先講一下其編碼過程，背后的數(shù)學(xué)理論，將另辟文章來講解。本文需要的背景知識只有 "線性分組碼的基本定義和概念"。
(錄制的視頻：https://www.bilibili.com/video/BV1xx4y1L7Dc/ ）

Reed-Muller 碼是一種線性分組碼，我們知道，線性分組碼有兩個基本的參數(shù)，即 (n,k)，表示 輸入 k 個符號，產(chǎn)生 n? 個符號，則增加的冗余校驗符號有 n-k 個，當(dāng)然，如果是符號是二進制的情況，則是 輸入 k 個比特，產(chǎn)生 n 個比特。

Reed-Muller 碼用 (r,m) 來表示上面兩個基本參數(shù)，對應(yīng)編碼后輸出符號長度為：

例如 (2,3) 的 Reed-Muller 碼，其輸出的符號長度為? ， 即輸出符號長度為 8.

可以猜測到，輸入符號的長度與 (r,m) 中的 r 有關(guān)：

其中

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

所以 (2,3) 的 Reed-Muller，就是 (8,7) 的線性分組碼.

Reed-Muller 碼的編碼，有很多種描述的方法，本文先講一個基本的遞推(Recursive) 方法。

我們用 R(r,m) 來表示參數(shù)為 r 和 m 的 Reed-Muller 碼. 則遞推(Recursive)公式為：

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

其中 ，表示長度為? 的序列，是一個所有可能取值的全排列，例如：r=2


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

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

根據(jù)上圖，則需要先列出來所有的葉子節(jié)點:

以及

和


根據(jù)圖的遞推關(guān)系，則:

再根據(jù)圖示的遞推，則：


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