融合路徑度量值和行重特性的Polar碼SCL譯碼算法*

周 泉,陳海強,曾俏麗,廖蘭娟,孫友明,黎相成

(1.廣西大學 計算機與電子信息學院,南寧530004;2.廣西多媒體通信與網絡技術重點實驗室,南寧530004)

0 引 言

Polar碼是Arikan[1]提出的一種信道編碼方案,該方案在理論上可達到香農限。然而在信道極化不充分時,串行抵消(Successive Cancellation,SC)譯碼算法性能不理想。文獻[2]提出了串行抵消列表(Successive Cancellation List,SCL)譯碼算法,通過在列表中保留多條生存路徑提高譯碼性能。為了降低SCL譯碼算法的復雜度,文獻[3]提出了一種自適應快速SSCL譯碼算法;文獻[4]提出了基于SCL的CA-SCL譯碼算法,將循環冗余校驗(Cyclic Redundancy Check,CRC)碼與Polar碼進行級聯,從而準確識別路徑降低誤幀率?；赟C譯碼算法的另一種算法是串行抵消翻轉(Successive Cancellation Flip,SCF)譯碼算法[5],通過比特翻轉的方式進行額外的譯碼嘗試,提高了譯碼性能。在SCF譯碼算法基礎上,動態SCF譯碼算法[6]、近似度量值動態SCF譯碼算法[7]被提出,進一步提升了SCF譯碼性能。文獻[8]將比特翻轉的方法應用在CA-SCL譯碼算法中,提出了串行抵消列表比特翻轉(Successive Cancellation List Bit-flip,SCLF,SCLF)譯碼算法,有效提升了譯碼性能,但是具有較高的譯碼復雜度。為了降低譯碼復雜度,文獻[9]提出了基于關鍵集的比特選擇度量值的SCLF譯碼算法。為了提升短碼字的譯碼性能,文獻[10]提出了一種基于行權重的串行抵消列表翻轉(Row Weight Based SCL-F,RWB-SCL-F)譯碼算法,在保持長碼字譯碼性能的同時提高了短碼字的譯碼性能。類似的譯碼算法包括置信傳播(Belief Propagation,BP)譯碼算法[11]及其改進算法[12-13]等。

本文針對SCLF譯碼算法復雜度較高的問題,提出了PM-LLR-SCL(Path Metric and Log-likelihood Ration)譯碼算法,綜合考慮LLR和PM對譯碼性能的影響,通過重排PM值完成翻轉功能。為了進一步提高短碼字的譯碼性能,以支持在海量機器類型通信中的可靠短包傳輸,提出了PM-RW-SCL譯碼算法,綜合考慮最小碼距和極化比特信道可靠度,得到重排路徑度量值信息比特的關鍵集KHW。實驗仿真表明,所提算法相對于RWB-SCL-Flipping譯碼算法,進一步獲得了譯碼增益,同時也降低了譯碼復雜度。

1 系統模型和符號定義

(1)

2 SCF和SCLF譯碼算法

2.1 SC譯碼算法的錯誤傳輸現象

圖1 錯誤比特個數出現頻率

從圖1可知,由于信道噪聲的影響,SC譯碼過程中會發生一定的錯誤傳播;在不同的信噪比下,出現單個錯誤比特的頻率是最大的,并且錯誤個數越大,出現的頻率也越低;同時,隨著信噪比的增大,出現單個錯誤比特的概率逐漸變大,例如當Eb/N0=2.5 dB時,單個錯誤比特出現的頻率接近90%。

2.2 SCF譯碼算法

為了解決SC譯碼算法的錯誤傳播問題,文獻[5]提出了SCF譯碼算法,其譯碼過程為首先執行SC譯碼算法,若譯碼結果通過CRC校驗,則譯碼成功;若校驗失敗,則在翻轉集合中選擇易錯比特進行翻轉操作,并從此處重新開始譯碼;若譯碼再次失敗則繼續選擇下一個易錯比特進行譯碼嘗試,直到譯碼成功或者達到最大譯碼嘗試次數T。

SCF譯碼算法翻轉集合的獲取步驟為將初次譯碼時信息比特的對數似然比|LLR|按照升序進行排列,并得到與其對應的索引序號,最后根據設定的最大譯碼嘗試次數取出排序后的前T位索引序號構成翻轉集合。

2.3 SCLF譯碼算法

文獻[8]將比特翻轉的思想應用在CA-SCL算法中,提出了SCLF譯碼算法。該文獻分析了CA-SCL譯碼過程中路徑分裂的3種狀態:第一種為克隆狀態,此狀態由于保存了路徑分裂后的ui=0和ui=1的路徑無法進行比特翻轉;第二種為刪除狀態,此狀態由于刪除了ui=0和ui=1的路徑故也無法進行比特翻轉;第三種為SC狀態,此狀態由于只保存了ui=0和ui=1中的一條路徑故可以進行比特翻轉。SCLF譯碼算法提出了修訂的翻轉關鍵集:

(2)

通過RCS可以確定當CA-SCL譯碼失敗時應該翻轉的信息比特位。SCLF 譯碼算法的過程與SCF 譯碼算法相類似,增加了對路徑狀態的判斷,這里不再贅述。

3 PM-LLR-SCL譯碼算法

3.1 路徑度量值PM

在SCL譯碼算法中,定義路徑度量的計算公式為

(3)

(4)

3.2 關鍵集K的選取和重排路徑度量值

重排路徑度量值策略:當譯碼失敗,再次啟動譯碼嘗試時,遇到K中的信息位索引序號,則將對應的2L條路徑的度量值由原來的升序排列調整為降序排列,并從2L條路徑中選擇前L條路徑進入下一級的譯碼。由于PM值越大,該條路徑越不可靠,所以原始的PM值選取策略是將其中PM值最小的L條路徑選擇出來,但是由于在關鍵集K中的信息比特為易錯比特,故可以將PM值最大的L條路徑選擇出來進行下一級譯碼,從而實現比特翻轉的效果。

3.3 PM-LLR-SCL譯碼算法描述

根據上述描述,PM-LLR-SCL譯碼算法偽代碼如下:

3 執行CA-SCL譯碼,并進行CRC校驗

4 if CRC_Check=true then

5 輸出譯碼結果

6 else

7 根據K的選取策略,得到K

8 Fort

9 選擇第t個位置,從該比特處重新執行CA-SCL譯碼,并且對該比特執行重排路徑度量值策略

10t++,并進行CRC校驗

11 if CRC_Check=true then

12 輸出譯碼結果

13 Break

14 結束

3.4 PM-LLR-SCL譯碼算法的性能分析

本小節將提出的PM-LLR-SCL譯碼算法與CA-SCL和SCLF譯碼算法進行性能對比。仿真參數設置為CRC=12,碼率R=1/2,最大嘗試譯碼次數T=32,仿真結果如圖2和圖3所示。

圖2 L=8時不同譯碼算法性能對比

圖3 L=16時不同譯碼算法性能對比

由圖2可知,當碼長N=256,FER=10-4時,相比于CA-SCL譯碼算法和SCLF譯碼算法,PM-LLR-SCL譯碼算法分別獲得了約0.37 dB和0.15 dB的性能增益;當碼長N=512,FER=10-4時,相比于CA-SCL譯碼算法和SCLF譯碼算法,PM-LLR-SCL譯碼算法分別獲得了約0.25 dB和0.1 dB的性能增益。

由圖3可知,當碼長N=256,FER=10-3時,相比于CA-SCL譯碼算法和SCLF譯碼算法,PM-LLR-SCL譯碼算法獲得了分別約0.39 dB和0.23 dB的性能增益;當碼長N=512,FER=10-4時,相比于CA-SCL譯碼算法和SCLF譯碼算法,PM-LLR-SCL譯碼算法分別獲得了約0.23 dB和0.1 dB的性能增益。

4 PM-RW-SCL譯碼算法

4.1 極化碼的最小碼距

給定Polar碼,則其最小碼距可以計算為

(5)

式中:wt(i)表示漢明距離。根據文獻[1]可知,2wt(i)

等于Polar碼生成矩陣GN的第i行行重,故式(5)可以進一步推導為

(6)

4.2 關鍵集KHW的選取和重排路徑度量值

本文通過高斯近似的方法計算極化子信道的可靠度,從而得到信息位集合A。根據式(6)將A中信息比特劃分為3部分,第一部分為最小碼距集合ΦM,第二部分為次小碼距集合ΦS,第三部分為A中剩余的信息位集合ΦR,即

(7)

式中:dsmin為次小的極化碼距。

在本次的設計工作開展過程中，充分地將城市的建筑開發與自然生態環境的保護進行了有效融合。從設計區域至外部交通以及空間層面都十分符合生態建筑理念，濕地公園水岸與周邊城市居民之間相互呼應的效果十分貼合于城市可持續發展的目標[1]。具體而言，在進行景觀設計時，使用的是一種幾何抽象的折線形湖水紋樣斑塊，然后在其中融入了工程當地的文化符號以及生態環境形象。另外一方面，在進行生態濕地設計時，需充分與城市的發展理念相融合，為城市的發展創造了良好的休閑與綠化空間，同時也為當地的旅游、綠化生態帶以及經濟活力提供了有效的發展活力。

2 輸出KHW={K1,K1,…,KT}

3 ifT≤|ΦM|,then

Ki=ΦM[i],i=1,2,…,T

4 if|ΦM|

5 if|ΦM|+|ΦS|

7 返回KHW

PM-RW-SCL譯碼算法的重排路徑度量值策略與PM-LLR-SCL譯碼算法類似,當第一次CA-SCL譯碼結果未通過CRC校驗時,再次啟動譯碼嘗試;當譯碼信息比特為KHW中索引序號時,則將對應的2L條路徑的度量值由原來的升序排列調整為降序排列,并從2L條路徑中選擇前L條路徑進入下一級的譯碼。

4.3 PM-RW-SCL譯碼算法描述

本節提出的PM-RW-SCL算法將沿用3.3節 PM-LLR-SCL譯碼算法的譯碼框架,但是對需要重排的路徑度量值集合進行了重新選取,即將關鍵集K替換為關鍵集KHW。

4.4 PM-RW-SCL譯碼算法性能分析

本小節將提出的PM-RW-SCL譯碼算法與CA-SCL和RWB-SCL-F算法進行性能對比。仿真參數設置為CRC=12,碼率R=1/2,列表長度L=8。

首先,考慮PM-RW-SCL譯碼算法在短碼字長度下的糾錯性能,采用兩個典型的短碼字長度N=64,N=128進行仿真,結果如圖4所示。由圖可知,在T=16,N=64,FER=10-3時,與RWB-SCL-F譯碼算法和CA-SCL譯碼算法相比,PM-RW-SCL譯碼算法實現了大約1.5 dB和0.25 dB的性能增益;在T=16,N=128,FER=10-3時,與RWB-SCL-F譯碼算法和CA-SCL譯碼算法相比,PM-RW-SCL譯碼算法實現了大約0.9 dB和0.4 dB的性能增益;當T增加到32時,相比于CA-SCL譯碼算法,可提高大約0.5 dB性能增益。

圖4 N=64,128時不同譯碼算法性能對比

為了進一步研究碼字長度對于PM-RW-SCL譯碼算法的影響,將碼字長度拓展到圖5中的N=256。如圖4和圖5所示,在不同的碼字長度下,本文提出的PM-RW-SCL譯碼算法始終優于RWB-SCL-F譯碼算法,但其性能增益隨著碼字長度的增長而下降,如在N=256,T=16時,增益大約僅為0.35 dB;隨著最大嘗試譯碼次數T的增加,譯碼性能增益也會逐漸增大。

圖5 N=256,T=16,32時不同譯碼算法性能對比

5 復雜度分析

本文提出的兩種譯碼算法的譯碼復雜度指的是總的列表大小,即平均執行SCL譯碼的次數。例如列表大小為L的CA-SCL譯碼算法執行一次譯碼過程的譯碼復雜度為L,如果PM-LLR-SCL譯碼算法、PM-RW-SCL譯碼算法以T次重新嘗試譯碼結束,則復雜度為(T+1)L。

5.1 PM-LLR-SCL譯碼復雜度分析

仿真參數設置為N=256,R=1/2,T=32,CRC=12,圖6展示了3種譯碼算法在不同信噪比下的平均譯碼復雜度。

圖6 PM-LLR-SCL譯碼算法與其他譯碼算法的平均復雜度對比

PM-LLR-SCL譯碼算法不僅考慮了初始譯碼時信息比特的LLR值,并且對譯碼時分裂路徑的度量值進行了重新排序,所以在信噪比小于2.5 dB時比SCLF譯碼算法具有更低的譯碼復雜度。隨著信噪比的逐漸增大,兩種譯碼算法的譯碼復雜度逐漸降低,并且當信噪比大于2.5 dB后,都收斂于CA-SCL算法的列表大小L。當信噪比為2 dB時,PM-LLR-SCL譯碼算法較SCLF譯碼算法在L=4,8,16的復雜度分別降低了約57%,62%,54%。

5.2 PM-RW-SCL譯碼復雜度分析

仿真參數設置為N=256,R=1/2,T=16,CRC=12,圖7展示了3種譯碼算法在不同信噪比下的平均譯碼復雜度。PM-RW-SCL譯碼算法比RWB-SCL-F需要更少的譯碼次數,尤其在低信噪比區域。這是由于PM-RW-SCL譯碼算法不僅考慮了Polar碼的最小碼間距和極化信道可靠度對譯碼性能的影響,還綜合判斷每一次譯碼過程中關鍵集KHW對應的信息比特在進行路徑分裂時路徑度量值對下一級譯碼的影響,從而能夠在重新嘗試譯碼時能夠更加準確的將易錯比特進行校正。同樣地,當信噪比大于2 dB時,PM-RW-SCL譯碼算法的譯碼延遲可以忽略不計,這是因為所有需要重排的信息比特的復雜度都收斂于CA-SCL譯碼復雜度L。當信噪比為1 dB時,PM-RW-SCL譯碼算法較RWB-SCL-F譯碼算法在L=4,8,16的復雜度分別降低了37%,38%,39%。

圖7 PM-RW-SCL譯碼算法與其他譯碼算法的平均復雜度對比

6 結 論

為了降低Polar碼SCLF譯碼算法在低信噪比區域的譯碼復雜度,提升譯碼性能,本文提出了一種PM-LLR-SCL譯碼算法。該算法建立初始LLR和PM值之間的映射關系,并通過重排完成翻轉功能,進一步提高了嘗試譯碼的成功率,從而減少了譯碼次數。仿真結果表明,PM-LLR-SCL譯碼算法較于SCLF譯碼算法在低信噪處降低了約62%的譯碼復雜度,同時獲得了最大約為0.23 dB性能增益。為了提升Polar碼在短碼傳輸時的譯碼性能,進一步提出了基于生成矩陣行重特性和PM值的PM-RW-SCL譯碼算法,不僅考慮了Polar碼的最小碼距和極化子信道可靠度,同時將路徑分裂每一層的PM值引入到譯碼策略中,從而提高了譯碼性能。仿真結果表明,PM-RW-SCL譯碼算法在短碼字場景中比RWB-SCL-F譯碼算法獲得了最大約1.5 dB的性能增益,并且在低信噪比區域降低了約39%的譯碼復雜度。