RM碼和Polar碼的連續(xù)消除譯碼和置信傳播譯碼研究

殷威 張艷 張曉剛 沈秋晨

摘 要 本文比較了無須迭代的連續(xù)消除（Successive Cancellation， SC）譯碼算法和置信傳播（Belief Propagation， BP）迭代算法對相同碼長和碼率的RM碼和Polar碼的譯碼性能和譯碼時間。仿真結(jié)果表明SC軟判決譯碼算法可對RM碼進行譯碼，且相比于BP譯碼算法，SC譯碼時間平均降低了98.98%。針對BP譯碼算法譯碼性能優(yōu)而譯碼時間長的特點，本文提出了基于似然值的絕對值差的提前終止迭代準則的改進BP譯碼算法，降低了該準則的計算復(fù)雜度。仿真結(jié)果表明本文提出的提前終止準則降低了計算復(fù)雜度，從而有效降低了譯碼時延和能耗，滿足了低復(fù)雜度和低功耗的譯碼需求。

關(guān)鍵詞 Polar碼;RM碼;SC譯碼算法;BP譯碼算法;提前終止迭代準則

引言

1954年，Muller從線性空間角度，提出可糾正多個差錯的二進制線性分組碼—Reed-Muller （RM）碼[1]。同年，Reed提出大數(shù)邏輯譯碼算法[2]解決其譯碼問題。RM碼構(gòu)造簡單，亦可通過Plotkin結(jié)構(gòu)[3]構(gòu)造，可采用硬判決[4]或軟判決算法對其進行譯碼。

2008年Arikan提出的基于信道極化的Polar碼是經(jīng)過精準的數(shù)學(xué)分析，能在廣泛的信源和信道編碼問題上達到信息論極限的編碼方式，相比較之前最好的低密度奇偶校驗碼（Low-density Parity-check Code， LDPC） 的編碼方式，在相同的條件下，Polar碼的糾錯性能要優(yōu)于LDPC碼，這表明Polar碼傳輸信息具有較高的可靠性。

Polar碼的軟判決譯碼方法通常有兩種：連續(xù)消除 （Successive Cancellation ， SC）譯碼算法和置信傳播（Belief Propagation， BP）譯碼算法。Forney指出RM碼可被認為是圖形表示碼（codes on graphs），可通過BP譯碼算法完成譯碼。Arikan指出Polar碼和RM碼的關(guān)系，并在文獻中驗證了基于BP譯碼算法的Polar碼的譯碼性能優(yōu)于RM碼。然而在一定碼長范圍外，信噪比較高的情況下，BP譯碼算法的優(yōu)勢不是很明顯，故Arikan在文獻中對基于網(wǎng)格的最大似然（maximum-likelihood， ML）譯碼算法的Polar碼和RM碼的譯碼性能進行了比較，結(jié)果表明由于RM碼的最小漢明距離的優(yōu)勢，使其在高信噪比下譯碼性能更優(yōu)，而在信噪比較低時，Polar碼的譯碼性能優(yōu)于RM碼。文獻中提出的最大后驗概率（maximum a-posteriori probability， MAP）譯碼算法利用了RM碼的最小漢明距離的優(yōu)勢，故基于該算法的RM碼譯碼性能優(yōu)于Polar碼。然而未有文章指出SC譯碼算法對RM碼譯碼的可行性，且未有研究基于SC譯碼算法下的兩種碼的譯碼性能和計算復(fù)雜度進行比較。出于該問題，本文分別通過對Polar碼和RM碼在BP和SC譯碼算法下的譯碼性能和計算復(fù)雜度進行比較，驗證SC譯碼算法可對RM碼譯碼。通過計算誤比特率（bit error rate， BER）和誤幀率（frame error rate， FER）比較Polar碼和RM碼的譯碼性能，通過計算譯碼時間比較兩種碼的計算復(fù)雜度。并通過分別比較Polar碼和RM碼在BP和SC譯碼算法下的譯碼時間，驗證相比于BP譯碼算法，SC譯碼算法滿足RM碼的快速譯碼需求，為RM碼的快速譯碼提供了一項工具。

雖然SC譯碼算法的計算復(fù)雜度較低，但該算法因其固有的串行譯碼特點而造成長延時的問題。不同于SC譯碼算法，BP譯碼算法因其并行處理和數(shù)據(jù)吞吐量高的特點，使該算法適合高吞吐量低延遲的應(yīng)用。文獻提出與傳統(tǒng)BP譯碼算法有相同性能而復(fù)雜度較低的縮放最小和BP（scaled min-sum， SMS）譯碼算法，文獻引入了一種基于子因子圖凍結(jié)的復(fù)雜度降低的BP解碼器。但以上的BP譯碼算法仍需要進行多次迭代過程，大大地增加了時延和能耗。在不影響譯碼性能的基礎(chǔ)上，設(shè)計合理的提前終止迭代準則可有效地降低BP譯碼算法的平均迭代次數(shù)。提前終止迭代準則已廣泛適用于LDPC碼和Turbo碼。文獻提出了基于生成矩陣和基于最小似然值（minimum log-likelihood ratio， minLLR）的提前終止迭代準則，這兩種提前終止準則雖在一定程度減少了迭代次數(shù)，但其迭代次數(shù)仍較高?；谠搯栴}，有學(xué)者提出了基于似然值的方差的提前終止迭代準則。該種提前終止迭代準則雖減少了迭代次數(shù)，但其運算復(fù)雜度較高，在碼長越長的情況下，該種提前終止迭代準的時延和能耗會成碼長的倍數(shù)增加，極大的消耗了能量，增加了譯碼時間，因此在一定程度減少迭代次數(shù)的基礎(chǔ)上降低BP譯碼算法提前終止迭代條件的運算復(fù)雜度是很有必要的。本文在基于似然值的方差的提前終止迭代準則的基礎(chǔ)上，提出了基于似然值的絕對值差的提前終止迭代準則，在保證減少迭代次數(shù)與基于方差的準則一致的基礎(chǔ)上，通過降低準則的運算復(fù)雜度，有效降低了時延和能耗的問題。并通過計算兩種準則的計算復(fù)雜度和比較基于兩種準則的譯碼時間驗證本文提出的準則具有更低的計算復(fù)雜度。

1RM碼和Polar碼

對于，的RM碼一般表示為，對應(yīng)碼字長度為，最小漢明距離為，信息位長度為，因此RM碼也可以表示為。對于，可使用Plotkin結(jié)構(gòu)獲得：

其中，表示的階Kronecker積。階的RM碼可被定義為生成矩陣為的線性碼，通過選擇矩陣中漢明重量大于等于的行向量獲得RM碼的生成矩陣。

Polar碼的參數(shù)一般表示為，對應(yīng)的碼字長度為，信息位長度為K，信息比特集合為A，凍結(jié)比特（frozen bit）為，其中集合Ac是信息比特集合A的補集。Polar碼的編碼方式不同于RM碼，的Polar碼的生成矩陣是矩陣的一個的子矩陣。當信道為二進制擦除信道（Binary Eraser Channel， BEC）時，可以根據(jù)以下遞歸方式計算巴特查理亞（Bhattacharyya）參數(shù)，根據(jù)的值從矩陣中選擇行向量。由于信道的可靠性越高值越小，所以選擇參數(shù)值較小的信道用于傳輸信息。

由于對和的排列和與漢明重量的排列相同，所以在和時，Polar碼和RM碼的生成矩陣一樣。當在時，以開始計算，根據(jù)式（3）計算出。對進行重新排序，得到序列（32，16，24，28，30，31，8，12，20，14，22，26，15，23，27，4，29，6，10，7，18，11，19，13，21，2，25，3，5，9，17，1），而對應(yīng)的行向量的漢明重量為（32，16，16，16，16，16，8，8，8，8，8，8，8，8，8，4，8，4，4，4，4，4，4，4，2，4，2，2，2，2，1）。因此的Polar碼的生成矩陣與采用矩陣中漢明重量大于等于的行向量組成的RM碼的生成矩陣不同，且當碼長越長，兩種碼的生成矩陣差別越大。

2Polar碼和RM碼的SC譯碼和BP譯碼比較

Polar碼和RM碼的編碼具有共同結(jié)構(gòu)，但編碼方式具有差別，本章則對Polar碼和RM碼的SC譯碼和BP譯碼性能和譯碼時間進行比較。

2.1 連續(xù)消除譯碼（SC）算法

編碼后的碼字經(jīng)過AWGN信道傳輸后，接收碼字為。SC譯碼算法通過計算的LLR得出的估計值 。每比特的LLR由下式得到：

SC譯碼算法具有較低的運算復(fù)雜度。

2.2 置信傳播（BP）譯碼算法

文獻提出采用BP譯碼算法對Polar碼和RM碼進行譯碼，提高了其譯碼性能。的Polar碼的編譯碼可由個節(jié)點組成的因子圖表示，其因子圖有層，每層有個基本處理單元（processing elements， PE），其基本處理單元如圖1所示。

每個節(jié)點（，）包含兩種似然信息：向左傳遞的信息和向右傳遞的信息，其中表示當前迭代的次數(shù)。在譯碼過程中，這些信息在相鄰節(jié)點之間進行傳遞和更新。每個PE中節(jié)點信息更新公式如下：

2.3 Polar碼和RM碼的SC譯碼和BP譯碼的比較

本文的仿真平臺為Windows 7系統(tǒng)，CPU為Intel（R） Core，利用C++語言進行編程實現(xiàn)。本節(jié)展示了基于SC、BP譯碼算法下的相同碼長和碼率的RM碼和Polar碼的譯碼性能和譯碼時間仿真與分析。與對應(yīng)的Polar碼的信息位長度為，對應(yīng)關(guān)系如下表所示：

本節(jié)給出了碼長，和的RM碼和Polar碼在AWGN信道下的BER和FER仿真結(jié)果和基于兩種譯碼算法的譯碼時間。其中采用二進制移相鍵控（BPSK）進行調(diào)制，仿真結(jié)果如附錄Ⅰ所示。給出的仿真結(jié)果的結(jié)論與其他碼長和碼率的實驗結(jié)果具有一致性。

表2是（256，93）和（256，163）的RM碼和Polar碼基于BP、SC譯碼算法下的時間比較表，圖2是（256，93）和（256，163）的RM碼和Polar碼基于BP、SC譯碼算法下的性能比較圖，其中BP譯碼算法的設(shè)定的固定迭代次數(shù)為60次。由圖2看出RM碼和Polar碼的BER和FER隨著碼率的增加而變大，說明碼率越大，RM碼和Polar碼的譯碼性能越差。且在小于0dB時，經(jīng)過SC譯碼的RM碼和Polar碼的譯碼性能較差;相比于BP譯碼算法，SC譯碼算法譯碼性能較差。由表2中可看出，相比于BP譯碼算法，基于SC譯碼算法的Polar（256，93）、Polar（256，163）的譯碼時間分別降低了98.64%，99.2%;基于SC譯碼算法的RM（8，3）、RM（8，4）的譯碼時間分別降低了98.73%，99.34%，平均降低了98.98%。仿真結(jié)果表明相比BP譯碼算法，SC譯碼算法的譯碼性能雖較差，但其大大降低了譯碼時間，譯碼過程中節(jié)省了大量的存儲空間、時間和能量，在快速譯碼方面占有更多優(yōu)勢。

3基于似然值的絕對值差的提前終止迭代準則的改進BP譯碼算法

BP譯碼算法的固定次數(shù)是根據(jù)信噪比最差的情況設(shè)定的，但在信噪比未達到最差情況下，BP譯碼算法運行到固定次數(shù)需要消耗大量的能量和時間，則降低了譯碼效率，而根據(jù)不同的信噪比適度地降低迭代次數(shù)可達到有效的收斂。

3.1 基于似然值的絕對值差的提前終止迭代準則

早期的迭代準則在現(xiàn)有的LDPC碼和Turbo碼中具有廣泛的應(yīng)用，根據(jù)不同的信噪比范圍，提前停止迭代。提前終止準則分為多種類型，其中最重要的是檢測類型，用于檢測有效輸出是否已被譯碼。若被譯碼，則表示譯碼成功，譯碼器將提前終止迭代。文獻中提出的基于生成矩陣的方法就是檢測類型的方法，但該種方法仍需要較多的迭代次數(shù)。文獻中提出的基于似然值的方差的提前終止準則，基于似然值的方差的提前終止準則算法如下所示：

上述的基于似然值的方差的提前終止迭代準則的改進BP譯碼算法雖減少了迭代次數(shù)，但該種算法的計算復(fù)雜度仍較高。本文基于這個問題，提出了基于似然值的絕對值差的提前終止準則?；谠摻K止準則的改進BP譯碼算法如下：

基于似然值的絕對值差的提前終止迭代改進BP譯碼算法

3.2 仿真結(jié)果與分析

本節(jié)對Polar碼的基于似然值的絕對值差的提前終止迭代改進BP譯碼算法進行仿真，選用碼長，碼率的Polar碼，譯碼過程中設(shè)定的固定迭代次數(shù)為40。圖3展示了本文提出的提前終止迭代準則和基于方差的準則的譯碼性能比較，圖4展示了兩種準則在平均迭代次數(shù)上的比較。

由圖3和圖4可看出基于絕對值差的提前終止迭代條件的閾值越小，Polar碼的譯碼性能越優(yōu)，但其平均迭代次數(shù)較多?；诜讲畹奶崆敖K止迭代條件的閾值越大，平均迭代次數(shù)越少，但Polar碼的譯碼性能較差。本文選擇的基于絕對值差的提前終止迭代條件和的基于方差的提前終止迭代條件進行譯碼性能和運算復(fù)雜度的比較。由圖3和圖4看出，的基于方差的提前終止迭代條件和的基于絕對值差的提前終止迭代條件的改進BP譯碼算法的譯碼性能與平均迭代次數(shù)效果大體上一致，表明本文提出的基于似然值的絕對值的提前終止迭代改進BP譯碼算法沒有導(dǎo)致性能丟失，且兩種準則的平均迭代次數(shù)減少的幅度隨著信噪比的增大而明顯。提前終止迭代準則可有效地降低能耗和延時問題，但提前終止迭代仍然需要消耗能量，因此需要選擇計算復(fù)雜度較低的提前終止迭代準則。表3給出了兩種提前終止迭代準則的運算復(fù)雜度的比較，表4給出了兩種提前終止迭代準則的譯碼時間的比較。

由表3可知本文提出的基于似然值的絕對值差的提前終止迭代算法的運算復(fù)雜度比基于似然值的方差的提前終止迭代算法平均減少了至少一半的計算復(fù)雜度，即每次迭代過程中減少了次乘法和除法的計算量，仿真結(jié)果表明在碼長越長的情況下，本文提出的準則運算復(fù)雜度更低，在降低時延和能耗方面更具有優(yōu)勢。表4則通過比較基于兩種終止準則的譯碼時間驗證了上述結(jié)論。在碼長的情況下，本文提出的準則的譯碼時間比基于似然值的方差的提前終止迭代準則平均減少了5.584%，在傳輸碼字越多，碼長越長的情況下，本文提出的提前終止準則可節(jié)省更多的譯碼時間，降低更多能耗。

4結(jié)束語

本文在描述RM碼和Polar碼的編碼方式差異的基礎(chǔ)上，首先通過比較基于無須迭代的SC譯碼算法和BP迭代譯碼算法的RM碼和Polar碼的譯碼性能和譯碼時間，驗證了無須迭代的SC軟判決譯碼算法對RM碼的譯碼的可行性;其次在基于似然值的方差的提前終止迭代的改進BP譯碼算法的基礎(chǔ)上，提出了基于似然值的絕對值差的提前終止準則。

基于SC、BP譯碼RM碼和Polar碼的譯碼性能和譯碼時間比較的仿真結(jié)果驗證了SC譯碼算法對RM碼譯碼的可行性。表明了在經(jīng)過AWGN信道下，基于兩種相同譯碼算法的Polar碼在譯碼性能上都可獲得更好的誤比特性能。相比于SC譯碼算法，BP譯碼算法（其中設(shè)定的固定迭代次數(shù)為60次）雖具有更好的譯碼性能，但RM碼和Polar碼在該算法下的譯碼時間比SC譯碼算法平均增加了98.98%，所以SC譯碼算法在計算復(fù)雜度和能耗方面具有更大的優(yōu)勢?；趦煞N提前終止迭代準則的仿真結(jié)果表明本文提出的基于似然值的絕對值差的準則與基于方差的提前終止準則在平均減少迭代次數(shù)和譯碼性能上具有一致性，而本文提出的基于絕對值差的準則通過降低運算復(fù)雜度降低能量和時間的消耗，減少了時延，是一種功耗和復(fù)雜度均低的提前終止迭代準則。

參考文獻

[1] Muller，D.E.Application of Boolean algebra to switching circuit design and to error detection[J].Transactions of the I.r.e.professional Group on Electronic Computers，2013，EC-3（3）：6-12.

[2] Reed I S.A class of multiple-error-correcting codes and the decoding scheme[J].Transactions of the IRE Professional Group on Information Theory，2003，4（4）：38-49.

[3] Plotkin M.Binary Codes with Specified Minimum Distance[J]. Information Theory，IRE Transactions on，1960，IT-6（4）：445-450.

[4] Arikan E，Kim H，Markarian G，et al.Performanceof short polar codes under ML decoding[J]. ICT MobileSummit ，2009，（1）：10-12.