2.4 幾類常用的分組碼

在線性分組碼中，重復碼和單奇偶校驗碼都是比較簡單的碼，但是它們都非常實用。其他常用的分組碼包括Hamming碼、BCH碼、RS碼、RM碼等，它們都具有很好的代數結構并且獲得了廣泛應用。但由于在5G通信系統中，除RM碼之外，其他幾種碼均未使用，因此這里不再具體贅述。

2.4.1 重復碼和單奇偶校驗碼

重復碼和單奇偶校驗碼是兩種比較簡單的線性分組碼。在GF(2)上的長度為n的重復碼（repetition code）Crep(n,1)是只有一個信息比特的二元(n,1)線性碼，這種碼只是簡單地把單個信息比特重復n次。因此，在GF(2)上，它只有兩個碼字：全0碼字(00···0)和全1碼字(11···1)。很明顯，它的生成矩陣是

編碼運算是c=uG，其中u∈{0,1}。

在GF(2)上的長度為n的單奇偶校驗（Single Parity-Check, SPC）碼Cspc是一個二元(n, n-1)線性分組碼，它的每個碼字包含n-1個信息比特和1個校驗比特。令u=(u0, u1, · · ·, un-2)是未編碼信息，那么單校驗比特c被加進去就構成了n比特碼字(u0, u1, u2, · · ·, un-2, c)，這個單校驗比特c就是消息u中的n-1個信息比特的模2和，即

c=u0⊕u1⊕· · ·⊕un-2

因此，Cspc中的每一個碼字的重量都為偶數。Cspc包含GF(2)上所有重量為偶數的n維向量，所以它的最小距離為2。任何奇數個錯誤的錯誤圖樣將使得Cspc中的碼字變為一個非法碼字，任何非零偶數個錯誤的錯誤圖樣將使得Cspc中的碼字變為另一個合法碼字。這表明單奇偶校驗碼能檢測到任何包含奇數個錯誤的錯誤圖樣，但不能檢測到包含非零偶數個錯誤的錯誤圖樣。

(n, n-1)單奇偶校驗碼的校驗矩陣是H=[11 ··· 1]，其系統形式的生成矩陣如下

其中，In-1是一個(n-1)×(n-1)的單位陣。易知(n,1)重復碼的生成矩陣Grep和(n, n-1)單奇偶校驗碼的生成矩陣Gspc的任意一行的內積均為0，即（n-1維的零向量）。因此，(n,1)重復碼和(n, n-1)單奇偶校驗碼是對偶碼。

重復碼的軟判決譯碼

假定(n,1)重復碼的碼字c用映射x=1-2c在AWGN信道上傳輸，接收向量為y，則條件LLR為

其中，Lc=2/σ2是信道值。如果L(u) ＞ 0，則譯碼器判決u=0；否則判為u=1。因為Lc是常數，譯碼規則可簡化為

可以證明，(n,1)重復碼采用軟判決譯碼的比特錯誤概率是

即與未編碼系統相同。

2.4.2 循環冗余校驗（CRC）碼

循環冗余校驗（Cyclic Redundancy Check, CRC）碼是一類（縮短的）循環碼，因為其編譯碼非常簡單，并且具有優秀的突發錯誤檢測能力，所以CRC碼經常用于錯誤檢測系統。在5G通信系統中，CRC碼被用于控制信道級聯Polar編碼的外碼；在數據信道的編碼中，LDPC碼之前也使用了CRC碼。與普通循環碼一樣，CRC碼也有二元碼與多元碼之分，這里主要討論二元CRC碼。

由于CRC碼通常是通過縮短方法從循環碼導出的，因此CRC碼也用一個生成多項式g(x)來定義。關于g(x)的選擇，Gallager[68]指出，通常在實踐中選擇g(x)=(x+1)b(x)，其中b(x)是本原多項式。(x+1)項保證所有奇數重量的錯誤圖樣是可檢測的，因為在模2算術下，沒有一個奇數項多項式包含(x+1)因子。關于不同次數的不同多項式的詳細討論參見文獻[70]。

考慮信息位長度為k、碼長為n的系統CRC碼。令u(x)=u0+u1x+· · ·+uk-1xk-1是待編碼的消息向量u=(u0, u1, · · ·, uk-1)的多項式表示，c(x)=c0+c1x+· · ·+cn-1xn-1是碼字c=(c0, c1, · · ·, cn-1)的多項式表示。注意向量與多項式系數的對應關系，這里將最高次項系數放在最右邊，并且假定編碼時最高有效位先發送：cn-1, cn-2, · · ·。

令g(x)=g0+g1x+· · ·+gr-1xr-1+xr是次數為r=n-k的碼生成多項式，其系數gi∈GF(2)。令Rg(x)[f(x)]表示取多項式f(x)除以g(x)的余式的操作，則與普通循環碼一樣，CRC碼的系統形式編碼運算可描述為

其中xru(x)對應于向量u的移位運算

CRC校驗比特(p0, p1, · · ·, pn-k-1)由多項式p(x)=Rg(x)[xru(x)]給出。為方便起見，在本節中使用G=[P Ik]系統形式的生成矩陣表示。

式(2.31)中的多項式除法可用反饋移位寄存器實現，整個CRC碼的系統編碼器電路如圖2.5所示。編碼前，r=n-k個移位寄存器的初始狀態全清為0，門1開，輸出選擇開關接通A；然后輸入信息序列u(x)的系數，高次位系數首先進入電路，它一方面作為碼字的一部分送往信道；另一方面自動乘以xn-k后進入g(x)除法電路。k次移位后，移位寄存器中的內容為p(x)的系數，此時將門1關閉，輸出選擇開關接通B，再經過r次移位后，把寄存器中的校驗位全部輸出。這樣，送往信道的碼字c(x)為

c=(p0, p1, · · ·, pn-k-1, u0, u1, · · ·, uk-1)

現在考慮CRC譯碼器。令接收向量的多項式表示為r(x)=c(x)+e(x)，其中e(x)為錯誤圖樣，則伴隨多項式

如果s(x)=0，則e(x)=0，即檢測到r(x)中有一個或多個錯誤發生；否則，如果s(x)=0，則原來的消息向量u可從r(x)中立即提取得到。

在實踐上，循環碼（包括CRC碼）用于檢錯時，伴隨式計算可以很方便地用移位寄存器電路實現。考慮系統碼的情況，接收向量r可以寫為

在接收端，使用與發送端相同的編碼器對接收到的信息塊u′進行編碼，產生估計的校驗塊p′′。然后比較p′與p′′，如果它們不同，則說明r不是一個有效碼字，接收序列中有錯誤存在。這種檢錯方法使得發送端的編碼器與接收端的錯誤檢測電路基本相同，從而簡化了設計。

實際上，根據系統形式的校驗矩陣，則有伴隨式

s=rHT=p′-p′′

表2.1列出了一些常用的不同長度CRC碼的生成多項式[71]。

注意：循環碼的生成多項式g(x)是GF(q)上的多項式(xn-1)的因子，所以給定g(x)的次數為r, CRC碼的最大長度小于或等于g(x)定義的原循環碼的碼長n。例如，CRC-12碼的生成多項式g12(x)整除x2047-1，這樣g12(x)定義了一個碼長為2047，維數為2047-12=2035的循環碼，它能夠對多達2035比特的數據進行編碼。

CRC碼的檢錯性能如下。

（1）一個由次數為r=n-k的生成多項式定義的循環碼（或縮短循環碼，CRC碼）C能夠檢測長度b≤r比特的所有突發錯誤圖樣。

一個長為b的突發錯誤是這樣的錯誤圖樣：第一位錯誤符號和最后一位錯誤（含最后一位）符號之間的比特數是b。例如，“.....00001×××××1000.....”是一個長度為7的單突發錯誤圖樣，其中×為任意{0,1}符號。

（2）長度為b=n-k+1的不可檢測突發錯誤圖樣在整個b長錯誤圖樣中的占比是2-(n-k-1)，即碼C能夠檢測百分之(1-2-(n-k-1))× 100的長度為n-k+1的突發錯誤。

（3）長度為b＞n-k+1的不可檢測突發錯誤圖樣在整個b長錯誤圖樣中的占比是2-n+k。

例如，CRC-12碼能夠檢測所有長度≤12的單個突發錯誤，能夠檢測99.95%的長度為13的突發錯誤，還能夠檢測99.976%的長度大于13的突發錯誤。

2.4.3 Simplex碼

在5G通信系統中，對控制信息的編碼除了重復碼與Polar碼，還用到了單純形（Simplex）碼，在此對Simplex碼的概念進行簡要介紹。

GF(q)上碼長為n、維數為m的Simplex碼是GF(q)上碼長n=(qm-1)/(q-1)的(n, n-m,3) Hamming碼的對偶碼，其生成矩陣是一個m×n的矩陣，矩陣的列由來自于GFn(q)的每一個一維子空間的一個非零向量所組成。GF(q)上(n, m)Simplex碼中每一個非零碼字的重量為qm-1。

5G通信系統中使用了二元(3,2)Simplex碼，其生成矩陣為

2.4.4 Hadamard矩陣與Hadamard碼[57]

定義2.3 一個n階Hadamard矩陣H是一個由{+1, -1}作為元素組成的n×n矩陣，并且滿足HHT=nI。

由定義可知，Hadamard矩陣的任意兩行是正交的（內積為0）。為方便起見，下面將用Hn表示n階Hadamard矩陣。Hadamard矩陣的逆陣可簡單地用下式求得。

從上式可得HTH=nI。因此，Hadamard矩陣的任意兩列也是正交的。

下列定理給出了Hadamard矩陣階數n的有效取值。

定理2.1 如果一個n階Hadamard矩陣存在，則n取值為1、2、4或4的倍數。

關于Hadamard矩陣的構造，主要有兩種方法：Sylvester構造和Paley構造。Sylvester構造很簡單，即如果Hn是一個n階Hadamard矩陣，那么

其中?表示兩個矩陣的Kronecter積運算。例如

關于Paley構造，這里不做介紹，讀者可參見相關文獻[57]。

Hadamard碼

將Hadamard矩陣Hn中的1替換為0, -1替換為1，就得到一個二進制Hadamard矩陣An。基于An，我們能夠構造幾種不同類型的Hadamard碼。

（1）如果刪掉An的最左列，剩下的行形成一個長為n-1的Hadamard碼，它共包含n個碼字，最小距離dmin=n/2。該碼也稱為Simplex碼。

（2）如果將中的n個碼字的補集（complements）添加進來，則得到碼，它包含2n個長為n-1的碼字，最小距離dmin=n/2-1。

（3）如果將An的n行的補集補充進來，則得到碼，它包含2n個長為n的碼字，最小距離dmin=n/2。

注意，如果n等于2m，則由Sylvester構造的Hadamard矩陣而得到Hadamard碼是線性的。