針對極化碼置信度傳播算法的低復雜度早期停止準則

張小軍 李 娜 董雁飛 崔建明 郭 華

①(山東科技大學電子信息工程學院 青島 266590)

②(高效能服務器和存儲技術(shù)國家重點實驗室 濟南 250101)

1 引言

2019年9月，芬蘭奧盧大學6G旗艦研究計劃組發(fā)布了全球首個6G白皮書，該白皮書認為6G的大多數(shù)性能指標相比5G將提升10～100倍。其中通信時延可低至0.1 ms，將是5G的1/10，并且具有超高可靠性[1]。這些需求對移動通信中的信道編解碼的延遲特性和譯碼性能提出了更高的要求。極化碼是第1種被證明在二進制離散無記憶信道下能夠達到信道容量的糾錯碼[2]，具有較高的可靠度和實用價值，已經(jīng)成為5G控制信道的編碼方案，并有望成為6G通信中主要的信道編碼方案。在極化碼的譯碼算法方面，串行抵消(Successive Cancellation, SC)算法[3,4]和串行抵消列表(Successive Cancellation List, SCL)[5]作為極化碼的低復雜度譯碼方案，具有較高的可靠性，但在譯碼時均需遍歷譯碼二叉樹的每個節(jié)點，導致譯碼延遲較高。與SC, SCL算法不同，置信度傳播算法(Belief Propagation, BP)是一種并行迭代的譯碼算法，可獲得較低的譯碼延遲。然而，大量的迭代次數(shù)仍造成BP較高的計算復雜度。由于大部分BP譯碼器在到達最大迭代次數(shù)之前已經(jīng)收斂于原始碼字，因此需要引入迭代早期迭代停止準則提前判斷。為了減少迭代冗余，Yuan等人[6]提出了G矩陣(G-matrix)和最小對數(shù)似然比 (minimum Log Likelihood Ratio, minLLR)兩個準則。其中，G-Matrix包含 N log N次二進制操作，而minLLR需要進行大量的比較運算。Yan等人[7]提出一種基于局部固定比特的早期停止準則，將固定位作為提前停止的準則。為降低資源消耗，文獻[8]提出一種有效節(jié)省資源消耗的提前迭代終止準則，與基于閾值的算法相比，該準則可降低資源消耗且不會造成譯碼性能損失。Ren等人[9]提出了LLR輔助(LLR-Magnitude Aided, LMA)和循環(huán)冗余校驗輔助(CRC Aided, CA)兩種早期停止準則，當信噪比為4 dB、最大迭代次數(shù)為30時，LMA和CA分別能減少72.6%和84.5%的迭代次數(shù)。此外，Simsek等人[10]提出一種基于最壞信息位(Worst of Information Bits, WIB)的早期停止準則，它只需檢測一部分LLR的符號位，可使譯碼復雜度有所降低，但譯碼性能低于G-Matrix。Simsek等人[11]通過去除冗余加法器陣列對WIB進行了優(yōu)化。另外，Albayrak等人[12]提出了一種基于Luby變換的提前停止準則，通過觀察譯碼器中LLR信息的符號位變化，確定譯碼輸出是否收斂到原始序列。文獻[13]于2017年提出了一種檢測凍結(jié)位誤碼率(Frozen Bit Error Rates, FBER)的早期停止準則，該準則只檢測在最可靠的凍結(jié)子信道中傳輸?shù)膬鼋Y(jié)位。受到早期停止準則的啟發(fā)，Giard等人[14]提出了基于極化碼BP譯碼算法的盲檢測法。上述準則都取決于或與對應的對數(shù)似然比(Log Likelihood Ratio,LLR)。

2 基本理論

2.1 極化碼

2.2 BP譯碼算法

圖1 (8, 4)極化碼的因子圖

3 提出的早期迭代停止準則

3.1 X-tolerance早期迭代停止準則

圖2 T d, T u和 T x的大小關(guān)系

圖3 中符號變化和中錯誤位數(shù)

3.2 比較空間的構(gòu)造

圖4 (8, 4)極化碼的Tanner圖

4 性能分析

采用二進制相移鍵控(Binary Phase Shift Keying, BPSK)調(diào)制，在二進制加性高斯白噪聲(Binary-Input Additive White Gaussian Noise,BI-AWGN)信道下，對(1024, 512)極化碼進行BP算法仿真，其中 α=0.9375，最大迭代次數(shù)設置為40次。

算法1 (N, K) X-tolerance BP譯碼器

4.1 譯碼性能分析

如圖5所示，當Q=128, X=2時，所提出的準則在誤幀率和誤碼率上與40次固定迭代(fixed 40),WIB和FBER譯碼性能相似。如果Q降低到64，則需將X至少增加到3，以彌補性能損失。每當X增加1時，它將至少導致平均迭代次數(shù)上升一次。同樣可觀察到Q值越大，譯碼性能越好。然而，較高的Q值增加了計算復雜度。因此，可通過仿真選擇合適的(X,Q)來權(quán)衡硬件復雜度和平均迭代次數(shù)。

4.2 對迭代次數(shù)的分析

4.3 硬件結(jié)構(gòu)

圖5 不同迭代終止準則的極化碼譯碼性能比較

圖6 不同迭代終止準則的平均迭代次數(shù)比較

圖8中給出了(8, 4)極化碼的BP譯碼流程。虛線部分表示處理單元的階段和停止準則之間的數(shù)據(jù)依賴關(guān)系。采用X-tolerance時，在第t次迭代的第3個時鐘中，譯碼器輸出,i ∈[N]，然后確定。接下來，和被發(fā)送到相等檢測器。第5個時鐘，計算X比較器的結(jié)果。如果滿足X-tolerance，譯碼器將計算,i ∈[N]，終止譯碼，否則繼續(xù)下一次迭代。對于大多數(shù)具有實際長度 (n ≤10000)的極化碼，相等檢測器和X比較器的關(guān)鍵路徑延遲總是小于PE[7]。因此，X-tolerance不會增加整個譯碼器的關(guān)鍵路徑延遲。此外，G-Matrix, WIB和FBER只能在得到后開始早期停止準則的判決，由于譯碼器和早期停止準則并行運行，在得到早期停止準則的結(jié)果前，譯碼無法終止，這會導致額外的延遲和復雜度。如圖8所示，在第t次迭代的第6個時鐘中譯碼器計算輸出,i ∈[N]，之后的第7個時鐘其他準則才會開始判斷是否終止譯碼，相對于X-tolerance會多出部分時鐘譯碼延遲。當 n>2時，X-tolerance不會導致額外的延遲，因為X-tolerance的檢測在獲得之前已完成。

4.4 計算復雜度和資源消耗分析

圖7 X-tolerance的硬件結(jié)構(gòu)

圖8 采用X-tolerance的BP譯碼流程

表1 早期停止準則的計算復雜度比較

表2 不同早期停止準則的綜合結(jié)果

5 結(jié)束語

為了降低極化碼置信度傳播算法的譯碼延遲，減少迭代次數(shù)，本文提出一種基于碼字估值的早期迭代停止準則。通過構(gòu)造比較空間，只需檢測碼字估值中的部分位置，進一步降低計算復雜度，且不會引入額外的延遲。仿真表明，當最大迭代次數(shù)為40，信噪比為3.5 dB時，與G-Matrix相比，X-tolerance平均迭代次數(shù)上升了29.98%，與WIB,FBER相比，X-tolerance平均迭代次數(shù)分別降低39.44%和27.67%。綜合結(jié)果表明，與G-Matrix,WIB和FBER相比，X-tolerance可節(jié)省90%以上的ALM資源。