李瀟云，侯 磊，張正平

（貴州大學大數(shù)據(jù)與信息工程學院，貴州貴陽 550025）

0 引言

一個簡單的通信系統(tǒng)模型包含信源、信道、信宿3 個部分，該通信系統(tǒng)模型被稱為香農(nóng)范式。在現(xiàn)實生活中，通信系統(tǒng)里的信道一般都是有噪信道，在有噪信道中使用信道編碼，可以極大提高通信系統(tǒng)的可靠性［1］。多年來，人們設計出了許多性能優(yōu)異且高效的信道編碼，比如LDPC（低密度奇偶校驗）碼［2］和Turbo 碼等，這兩種都是性能逼近香農(nóng)極限的信道編碼［3］。2008 年，Erdal Arikan 教授在國際信息論會議中，首次提出了信道極化這一概念，并在2009 年提出基于信道極化理論的極化碼，極化碼是目前確定的能被證明達到香農(nóng)極限的信道編碼，在SC（串行抵消）譯碼算法下，當碼長N 趨近于無窮大時會達到信道的信道容量［4］。但是在中短碼長下SC 譯碼算法的性能并不理想，極化碼自被提出以來，就引起了科研人員的廣泛關注，為了提高其性能，基于SC 譯碼算法的SCL（連續(xù)列表）譯碼算法［5］、增加了循環(huán)冗余校驗（CRC）輔助的SCL 譯碼算法［6］以及BP（置信度傳播）譯碼算法［7-8］相繼被提出。本文詳細描述SC譯碼算法的解碼結構，介紹加入了列表的SCL 譯碼算法與加入了循環(huán)冗余校驗的CA-SCL 譯碼算法，并提出一種低復雜度極化碼優(yōu)化譯碼算法PB-SCL，隨后將使用這幾種譯碼算法的極化碼進行性能比較并分析，使極化碼能在未來通信和實際生活中得到更加廣泛的應用。

1 信道極化現(xiàn)象與編碼原理

1.1 信道極化原理

極化碼構造的核心是信道極化，而信道極化原理可以簡單概括為信道合并與信道分裂。Arikan［9］在設計極化碼時，主要在二進制離散無記憶信道（B-DMC）中進行，極化思想即是N 的獨立不相關的B-DMC 信道經(jīng)過信道合并和信道分裂后形成N 個相關信道。

信道合并［10］：已知一個B-DMC 信道W:X→Y，轉(zhuǎn)移概率為W(y|x)，其中x∈X,y∈Y。在B-DMC 信道W經(jīng)過N次遞歸后，產(chǎn)生的信道WN:XN→YN：

其中，N為2 的冪次，N=2n，n≥0。

信道分裂：WN表示對信道合并后W的N次使用，然后將組合信道WN分裂成N 個獨立不相關信道的過程，W(i)N:X→YN×Xi-1,1 ≤i≤N,其轉(zhuǎn)移概率即：

根據(jù)極化碼的信道極化原理［11］，可知對任意N=2n,n≥0,1 ≤i≤N 2 的極化信道，都有奇序列分裂子信道與偶序列分裂子信道兩個遞歸式轉(zhuǎn)移概率：

1.2 信道極化現(xiàn)象

信道極化現(xiàn)象指當極化碼的碼長N=2n，以2 的冪次趨近于無窮大時，極化碼輸入比特序列信道的信道容量就會呈現(xiàn)出兩極分化現(xiàn)象，明顯地趨于兩個極端：一部分信道容量為0 的純噪聲信道，以及其余信道容量為1 的無噪聲信道［12］。二進制對稱信道（BSC）與二進制刪除信道（BEC）都是滿足對稱性的二進制離散無記憶信道（BDMC），假設在滿足BSC 信道中信道容量I(w)=1+p*logp+(1-p)*log1-p，在BEC 信道中I(w)=1-p，轉(zhuǎn)移概率p=1/2，隨著極化碼的碼長以2 的冪次逐漸增大，呈現(xiàn)出的兩個極端將會越來越明顯。

圖1、圖2 分別為在BSC 信道或BEC 信道下碼長N=64和N=128 的信道極化仿真圖，此時信道極化現(xiàn)象并不是那么明顯。

Fig.1 N=64 channel polarization diagram圖1 N=64 信道極化圖

當碼長N≥512 時，大部分信道都得到了充分極化，圖3-圖4 分別為碼長N=512 和N=1 024 的信道極化仿真圖，此時信道極化現(xiàn)象已經(jīng)得到充分證實，當碼長趨近于無窮時信道容量會呈現(xiàn)兩級分化［13］。因此，可以利用該信道極化現(xiàn)象，將部分信道容量趨近于0 的純噪聲信道用來存儲凍結比特，而將其余信道容量趨近于1 的無噪聲信道用來存儲信息比特。

Fig.3 N=512 channel polarization diagram圖3 N=512 信道極化圖

Fig.4 N=1 024 channel polarization diagram圖4 N=1 024 信道極化圖

1.3 極化碼編碼原理

極化碼編碼原理是利用極化現(xiàn)象進行構造的編碼，選擇合適承載信息比特的信道和放置凍結比特的信道，隨后進行數(shù)字邏輯運算的過程。給定原始比特序列=(u1,u2,…,uN)，編碼后的比特序列=(x1,x2,x3,…,xN)，因此可以顯式地將編碼原理表示出來：

其中，GN為N階生成矩陣，N=2n［14］，體現(xiàn)了對信息比特序列承載信道的選擇與固定比特序列承載信道的選擇，進而可以將上式表示為：

其中，∧代表承載信息比特序列的集合，∧c代表承載固定比特序列的集合，GN(∧)代表N 階生成矩陣中取與∧中元素對應信道組成的生成矩陣，GN(∧c)則表示取與∧c（固定序列比特集合）中對應元素構成的生成矩陣。只需要確定存放信息比特和固定比特的信道，就可輕松得到編碼后的比特序列［15］。

2 極化碼譯碼算法

2.1 SC 譯碼算法

SC 譯碼算法的數(shù)學模型，即進行遞歸譯碼的過程，從以上極化碼編碼原理可知，存在一個選擇存放信息比特信道和存放固定比特信道的過程，由此可以定義出一種線性陪集碼(N,K,∧,u∧c)［16］。其中，K 表示信息比特數(shù)量，∧為信息位指定存放位置、元素數(shù)量為信息比特數(shù)量K，u∧c為固定位、元素數(shù)量為凍結比特數(shù)量N-K。通常固定比特統(tǒng)一取值為0，因此固定比特u∧c取值不會出現(xiàn)錯誤，將其恒定為0，因此SC 譯碼算法的譯碼原理就是對信息位∧的估值。

進而可以直接通過計算對數(shù)似然比LLR 值對比特進行估值判決：

根據(jù)式（4）與式（5）這兩個奇序和偶序分裂子信道，SC譯碼器的復雜度為O(NlogN)，則每個LLR 值也可通過奇偶性進行計算，則可得到對數(shù)似然比LLR 值的奇偶性公式［16］。

其中，α，β ∈R，u ∈(0,1)。

當N=8 時，SC 譯碼柵格圖如圖5 所示。

Fig.5 SC decoding grid map圖5 SC 譯碼柵格圖

圖中灰色箭頭和黑色箭頭分別表示f-與f+從右端開始遞歸的過程，且右端開始λ 表示處于的層級，從右向左λ=(1,2,3,…,n)，總共有l(wèi)ogN層。圖中每一個節(jié)點代表一個LLR 值，則LLR 值從上到下表示為，i=(1,2,3,…,N)，從而可以通過上述遞歸式對進行計算，最后對比特進行估值判決，若≥1，則判決為=0，其他則判決為=1。SC 譯碼算法以LLR 為判決準則，對每一個比特進行硬判決，按比特序號從小到大的順序依次判決譯碼［17］。

2.2 SCL 譯碼算法

SC 譯碼算法是對比特進行硬判決的過程，只選擇一條其認為最優(yōu)的路徑進行探索。但是在極化碼碼長有限的情況下，信道極化現(xiàn)象不明顯，如果直接對子信道的比特序列進行硬判決，會由于信息量不夠而導致錯誤譯碼。針對這一現(xiàn)象，引進了SCL 算法，SCL 算法是在SC 算法的基礎上，通過保存L 條具有PM（路徑度量）值的路徑進行下一層解碼，在算法的最后選取一條具有最小PM 值的路徑，即相對于SC 算法，SCL 算法增加了路徑保存和回退功能［18］。

即對于SCL 譯碼算法，存在L 條路徑同時進行遍歷，同時也要對L 條路徑進行PM 值評估，選擇最優(yōu)路徑進行譯碼，PM 值的定義為：

其中，l∈{1,2,…,L} 為路徑索引，第l條路徑，i∈{1,2,…,N}為第i個比特位，對數(shù)似然比LLR，=

圖6 為極化碼的一種二叉樹表示方法。

Fig.6 Polarization code decoding binary tree圖6 極化碼譯碼二叉樹

搜索寬度L=2，從上到下進行遍歷，包含PM 初始化、路徑擴展、路徑選擇、路徑刪除和判決輸出的過程。圖中每一個節(jié)點的譯碼路徑都對應一個PM 值，首先對PM 值進行初始化，使L(1)=?,PM(1)=0。使其向下搜索并擴展，當譯碼到第i個比特時，對列表Li-1里的每一條路徑進行擴展，分別根據(jù)左右路徑進行擴展，將擴展后的路徑記錄在列表Li中。如果Li中路徑數(shù)目大于列表L，根據(jù)LLR 值計算出PM 值刪除或保留相應路徑，保留PM 值最小的L 條路徑，其余路徑刪除［18］。

最后根據(jù)PM 值選出最優(yōu)路徑，對比特序列判決后譯碼輸出。

循環(huán)冗余校驗（CRC）輔助編碼是通信系統(tǒng)中的常用技術。其目的是對傳輸信道上傳輸?shù)臄?shù)據(jù)進行校驗和檢測，加入了CRC 的串行消去列表解碼（SCL），可以刪除掉與CRC 不符合的路徑［19］。首先將CRC 與極化碼共同進行編碼，隨后與SCL 譯碼方式相同，將SCL 譯碼序列交給CRC 進行校驗、篩選。對于確定的信息位P，其中包含了CRC 校驗位p 和信息比特位K，則P=K+p。

SCL 譯碼算法結束時列表中存有一組候選的譯碼結果，因而便于將極化碼與CRC 進行聯(lián)合檢測譯碼，即將通過CRC 校驗且PM 值最小的序列作為譯碼輸出結果。CASCL 譯碼算法相較于SCL 譯碼算法，加入CRC 輔助路徑校驗選擇，提高了極化碼譯碼算法的性能。

3 低復雜度極化碼優(yōu)化譯碼算法PB-SCL

與SC 譯碼算法相比，SCL 譯碼算法可以大幅度提升極化碼譯碼性能，但是同時增加了復雜度和時延［20］。SC 譯碼算法的時間復雜度為O(NlogN)，而SCL 譯碼算法的時間復雜度為O(LNlogN)，會隨著L 列表寬度的增大而增大。因此，為了降低SCL 譯碼算法復雜度，引入優(yōu)化的剪枝PBSCL 譯碼算法。

如圖6 所示，用Dv表示節(jié)點v的深度，Vv表示以節(jié)點v為根節(jié)點的子樹中所有節(jié)點的集合，其中變量節(jié)點記為Iv，圖中黑色節(jié)點表示信息比特，白色節(jié)點表示凍結比特，灰色節(jié)點表示C 除去信息比特與凍結比特的其他類型的子碼。表示在第l條譯碼路徑中輸入以v為根節(jié)點的子碼的軟信息向量。SCL 譯碼算法在對第i個比特進行譯碼時，必須要對i-1 個前的整個譯碼樹進行搜索，因此可以從二叉樹的角度理解，縮小需要串行遍歷的二叉樹結構。對于以節(jié)點v為根節(jié)點的子碼，如果葉子節(jié)點都是凍結比特，在譯碼時就要直接略過這些凍結比特的節(jié)點。

利用優(yōu)化的剪枝SCL 譯碼算法進行譯碼，可以對極化碼中所有的凍結比特略過不計，這時就可以縮小需要串行遍歷的二叉樹，如圖7 所示。

Fig.7 SCL decoding pruning freeze BIT圖7 SCL 譯碼剪枝凍結比特

Fig.8 SCL decoding algorithm final optimized binary tree圖8 SCL 譯碼算法最終優(yōu)化二叉樹

算法優(yōu)化主要是對二叉樹所需遍歷的節(jié)點進行縮減，以減少遍歷過程中需要運行的節(jié)點數(shù)，通過這種優(yōu)化的剪枝PB-SCL 方法可以顯著降低極化碼SCL 譯碼算法復雜度且不損失傳統(tǒng)SCL 譯碼算法的性能。

4 仿真結果與分析

基于MATLAB R2018b 仿真平臺，在AWGN（加性高斯白噪聲）信道下，取碼長N=256，碼率為0.5，進行極化碼仿真。選用列表搜索寬度L=8 進行譯碼，采用CRC-16 將D16+D15+D2+1 作為生成多項式。如圖9 所示，橫坐標為信噪比（彩圖掃OSID 碼可見），縱坐標分別為誤碼率和誤幀率。結果表明，SC 譯碼算法在進行譯碼時性能要低于其他幾種譯碼算法性能，因為SC 譯碼算法在譯碼過程中如果對其中一個比特進行了錯誤判決，將會導致整條譯碼路徑錯誤。因此級聯(lián)了CRC 的CA-SCL 譯碼算法由于搜索寬度的增加而對譯碼路徑存在較高的容錯率，則譯碼性能較SC 譯碼算法得到提升。優(yōu)化的剪枝PB-SCL 譯碼算法與傳統(tǒng)SCL譯碼算法譯碼性能相當，但通過剪枝的方法減少了需要遍歷的總節(jié)點數(shù)，傳統(tǒng)SCL譯碼算法的機器運行時間為16 217.6s，優(yōu)化的剪枝PB-SCL 譯碼算法機器運行時間為12 407.14s，較傳統(tǒng)的SCL 譯碼算法而言降低了譯碼算法復雜度。

Fig.9 Performance simulation of polarization code decoding algorithm圖9 極化碼譯碼算法性能仿真

5 結語

極化碼是可以達到香農(nóng)信道容量的編碼方式，SC 譯碼算法在碼長趨于無窮大時會達到信道容量，但是由于SC 譯碼算法存在局限性，容錯率較低。鑒于此，本文提出SCL 譯碼算法，雖然隨著L 搜索寬度增加譯碼性能得到提升，但譯碼復雜度也隨之增加。本文對極化碼的編譯碼原理作詳細介紹與解析，引入優(yōu)化的剪枝PB-SCL 譯碼算法，并對幾種譯碼算法進行仿真分析。結果表明，SC 譯碼算法性能在中短碼長情況下的性能要低于其他幾種譯碼算法性能，加入了循環(huán)冗余校驗的CA-SCL 譯碼算法性能得到提高［21］。優(yōu)化后的剪枝PB-SCL 譯碼算法以較低的譯碼復雜度獲得了與傳統(tǒng)SCL 譯碼算法相當?shù)男阅?。因此，在不損失譯碼性能的情況下，降低譯碼復雜度和解碼時延需作進一步研究，以便其能更好地應用于現(xiàn)實生活中。