極化碼序列連續刪除譯碼算法的改進設計*

李 純，童新海

(解放軍理工大學 通信工程學院，江蘇 南京 210007)

?

極化碼序列連續刪除譯碼算法的改進設計*

李 純，童新海

(解放軍理工大學 通信工程學院，江蘇 南京 210007)

極化碼連續刪除譯碼算法性能和傳統的LDPC碼存在一定差距。序列連續刪除算法(SCL)的提出極大地改善譯碼性能，是極化碼推向實際應用中的重要一步。但是該算法復雜度較高，延遲大。改進的序列連續刪除(SCL)譯碼算法是基于改善極化碼碼長受限的情況，文中描述SCL算法是通過碼樹上的搜索序列路徑來表示譯碼過程。改進的算法通過減少譯碼算法在碼樹上的序列路徑來降低時間和空間復雜度。通過仿真表明，改進的算法有效地降低了譯碼的復雜度同時在性能上也接近最大似然(ML)譯碼算法。

極化碼 連續刪除算法 最大似然譯碼 序列譯碼

0 引 言

極化碼最核心思想是利用信道極化的過程進行編譯碼[1-3]。通過信道極化的理論分析，Arikan證明了極化碼可以獲得Shannon理論極限性能，并且保持對數編譯碼復雜度。然而研究表明，與傳統的Turbo碼、LDPC碼相比，極化碼在碼長有限時的誤碼性能還不是很理想，為了進一步提高極化碼的性能極限，許多高性能的譯碼算法被相繼提出。

連續刪除(SC)算法由Arikan首次提出，該算法利用比特信道似然概率的硬判決值輸出譯碼序列，根據信道的拆分來進行迭代計算。可見SC算法是一種串行迭代的過程，具有譯碼的時延較大，吞吐量不高等特點。為改善SC譯碼算法性能，人們提出序列SC譯碼(SCL)[2]、堆棧SC譯碼(SCS)[3]、循環冗余校驗輔助的SCL(CRC-SCL)[4]以及置信度傳播(BP)的并行譯碼等算法。特別是CRC-SCL算法，可以顯著提高SCL算法誤碼性能，在一定長度的碼長條件下，該算法的性能優于部分Turbo碼[4-7]。

SCL算法在序列足夠大時，該算法性能接近于最大似然(ML)算法性能，但是譯碼的時間復雜度和空間復雜度都會隨著L的增加而增加，本文提出的改進SCL算法就是通過聯合CRC校驗，保證譯碼性能的同時降低譯碼的復雜度。改進的算法分為兩部分，前半部分主要保證譯碼性能，后半部分是根據前半部分的譯碼路徑，降低譯碼的復雜度。

1 極化碼

極化碼是一種線性分組碼，基于信道的組合和分離的進行編碼，N個二進制離散無記憶信道(B-DMC)組合在一起然后分離，當N趨于無窮大時，部分信道的信道容量會趨近于1，相應的其他信道的信道容量趨近于0。利用信道容量高的信道傳送信息比特，信道容量低的信道傳送凍結比特。極化碼編碼的碼率能夠調節任意K/N，其中0≤K≤N編碼塊長度N的大小為2n，任意給定一個N，如下式對信息比特進行編碼：

(1)

式中，向量u表示長度為N的傳送信息比特，GN是N階次的生成矩陣，向量x是編碼后傳入信道的碼字。

2 序列連續刪除算法

SCL算法是在SC算法比特信道的轉移概率計算過程分析基礎之所提出的，基本思路是改變比特信道的譯碼輸出代替待編碼序列的方式。譯碼算法會根據路徑概率大小保留L條概率較大的路徑，當完成比特信道的轉移概率計算時，SCL選擇最大的路徑作為譯碼輸出。SCL算法可用下述步驟描述(如圖1所示)。

(2)

圖1 SCL譯碼算法流程Fig.1 Searching process of SCL decoder

1)初始化：假設碼樹的初始節點都是空值，碼樹的同層的節點概率之和為1，即

S(0)={?},P(?)=1

(3)

2)比特估計：比特通過連續的下標來進行索引：i=1,…,N

條件概率為：

(4)

6)序列檢測：在所有比特都被搜尋過，重新編碼計算每個序列中節點的似然概率，選擇其中一條最大的似然概率路徑作為輸出：

(5)

3 序列連續刪除算法的改進

在實際譯碼過程中出現譯碼錯誤的比特往往對應的是信道容量較低的信道，因此極化碼的性能主要是信道容量較小的信息位。對于碼長短的極化碼，極化速度慢，很多子信道的信道容量較低如圖2所示，在構造極化碼時會將一部分低信道容量的子信道用來傳送信息位，從而降低極化碼的性能。在SCL上述譯碼算法在L足夠大時，SCL算法性能接近于ML(最大似然)算法性能，譯碼時間復雜度和空間復雜度均為O(LNlbN)。SCL算法譯碼時，每次保留L條路徑值較大的譯碼序列，從而在信道容量較低的子信道上提高譯碼的精度，但是譯碼復雜度會隨著L的增大而增大，在L足夠大時，SCL算法性能接近于ML(最大似然)算法性能，但是這種窮盡搜索的方式復雜度呈指數增長，并且難以實現。

圖2 信道極化Fig.2 Channel polarization

基于上訴分析，本文在序列連續刪除算法的基礎之上，采取下列改動，在保證一定性能的條件降低原算法的復雜度：

1)首先通過信道的合并與分解，算出N個子信道的信道容量，選出k個信道容量低的信息位和m個信道容量高的固定位，其中對k個比特位進行CRC編碼，通過編碼后的冗余位來進校驗。本文采用的CRC—24，用(j1,j2,…,j24)校驗位的下標。

2)經過CRC編碼之后，對整個發送信息序列進行極化編碼。譯碼時，在沒有經過校驗位j24之前，所有位采用序列連續刪除算法。

3)按照每個信息位取0和1的概率，分別計算轉移概率，按照概率的大小保留L條大的路徑作為參考路徑，在譯碼位大于j24時，用CRC對L條路徑進行判斷，如果有一條或多條路徑通過了CRC校驗，保留概率最大的路徑作為輸出，然后繼續譯后面的信息位置；如果沒有通過校驗，則發出指令重新譯碼。

4)對于j4后面的所有位譯碼，拋掉剩余路徑，將通過校驗的序列繼續往下進行譯碼，同時將L值固定到1(即連續刪除算法)，直接通過概率大小值來判斷信息位為0還是為1，降低算法的復雜度，同時性能上和原算法也相近。

4 仿真結果與性能分析

在AWGN信道下，本文采用碼長N=1 024，碼率R=0.5，L=32，CRC-24生成多項式為g(D)=D24+D23+D6+D5+D+1對于m=24CRC校驗比特放在發送信息比特的中間，所有的K=k+m送入編碼器中。結果表明，改進算法的FER和SCL算法的性能想接近，同時在理論上很接近ML算法的誤幀率。改進的SCL算法性能如圖3所示。

圖3 改進SCL算法性能Fig.3 Performance of modified SCL algorithm for polar codes

分析譯碼器復雜度通過調用遞歸路徑節點概率計算的次數為標準。因此碼長1 024，碼率0.5的SC譯碼算法的復雜度為1 024×8=8 192。表1對比了各個信噪比條件下算法的復雜度，可見改進的SCL算法比較原算法，相應的復雜度降低了很多。

表1不同譯碼復雜度統計

5 結 語

極化碼是編碼領域較新的一個課題，目前在國際上是一個研究的熱點，代表了未來通信發展的一個方向。本文中在譯碼時分為兩部分，前半部分通過SCL算法，加上CRC校驗，選出一條概率乘積大的路徑；后半部分把L固定為1，降低復雜度，同時性能上也與原算法近似。在后半部分算法的復雜度從O(LNlogN)降為O(NlogN)。本文所提出的前半部分利用CRC校驗選取最優路徑，后半部分拋掉多余路徑精簡算法，降低譯碼復雜度，仿真結果表明，本算法可以在相對較低復雜度下保持極化碼在中短碼長的性能。

[1] ARIKAN.E. Channel polarization: A method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels [J].IEEE Trans.Inf. Theory,2009,52(07):3051-3073.

[2] ARIKANE. Channel Combining and Splitting for Cutoff Rate Improvement [J].IEEE Trans. Inf. Theory, 2006,52(02):628-639.

[3] 李斌，王學東，王繼偉.極化碼原理及應用[J].通信技術，2012，45(10):21-23. LI Bin，WANG Xue-dong，WANG Ji-wei. Theory and Application of Polar Code[J]. Communications Technology,2012,45(10):21-23.

[4] Tal I,VardyA. List decoding of polar codes[C]. USA: IEEE ISIT 2011,2011:1-5.

[5] NiuK, chen K. CRC-Aided decoding of polar codes [J].IEEE Communications Letters,2012,16(10):1668-1671.

[6] Niu K, chen K. Stack decoding of polar codes [J].Electronics Letters,2012,48(12):695-697.

[7] Huang Z L, Diao C J, Chen M. Latency reduced method for modified successive cancellation decoding of polar codes [J].Electronics Letters,2012,48(23):1506-1506.

[8] Leroux C, Raymond C J, Sarkis G. Hardware implementation of successive-cancellation decoders for polar codes [J]. Journal of Signal Processing Systems,2012,69(3):305-315.

LI Chun(1989-),male,M.Sci.,mainly engaged in satellite communication technology.

童新海(1971—)，男，教授，主要研究方向為現代通信技術.

TONG Xin-hai(1971-),male, professor, mainly engaged in modern communication technology.

Modified Successive Cancellation List Decoding Algorithm for Polar Codes

LI Chun, TONG Xin-hai

(Institute of Communication Engineering, PLAUST, Jiangsu Nanjing 210007, China)

The decoding performance of polar codes successive cancellation (SC) algorithm could hardly match with that of traditional LDPC. The proposal of successive cancellation list (SCL) greatly improves the decoding performance,and thus is an important step to put the polar codes into practical application, and however, this algorithm is of high complexity and long latency.Modified SCL decoding algorithm aims to improve the finite-length performance of polar codes.This paper describes the decoding process with searching sequence of paths on code tree. This proposed algorithm can reduce the time and space complexity by reducing unnecessary path searching operations. Simulations indicate that the modified SCL decoding algorithm decreses the decoding complexity while approaching the performance of maximum likelihood (ML) decoding algorithm.

polar code; successive cancellation; maximum likelihood decoding; list decoding

10.3969/j.issn.1002-0802.2015.01.004

2014-08-13；

2014-12-08 Received date:2014-08-13；Revised date：2014-12-08

TN911.3

A

1002-0802(2015)01-0019-04

李 純(1989—)，男，碩士，主要研究方向為衛星通信；