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|，故最大似然碼字是。