極化碼自適應(yīng)信道譯碼算法

葉茂林，譚曉青，許麗卿，呂善翔

暨南大學(xué)信息科學(xué)技術(shù)學(xué)院/ 網(wǎng)絡(luò)空間安全學(xué)院，廣東廣州510632

在二進制無記憶對稱信道中，使用極化碼的串行抵消（successive cancellation，SC）譯碼可令信道容量理論上達到香農(nóng)極限［1］，因此極化碼成為目前5G的編碼標(biāo)準(zhǔn)之一，且在未來的多種無線通信應(yīng)用場景下有巨大潛力［2-3］.然而，在編碼長度有限情況下，SC 譯碼的性能低于低密度奇偶校驗（low density parity check，LDPC）碼［4］，需研究更可靠譯碼方法.

ARIKAN［5］提出置信傳播（belief propagation，BP）譯碼方法，利用置換因子圖方式進行譯碼，迭代計算多次后，該方法性能高于SC 譯碼方法.TAL 等［6］提出連續(xù)抵消列表法譯碼，通過在譯碼時保留多條路徑提高了算法的可靠性.NIU 等［7］基于串行抵消列表（successive cancellation list，SCL）提出循環(huán)冗余校驗輔助（cyclic redundancy check-aided SCL，CA-SCL）譯碼算法，利用循環(huán)冗余校驗（cyclic redundancy check，CRC）檢查SCL算法產(chǎn)生的譯碼分支，準(zhǔn)確率比BP譯碼方法高［8］，但SCL算法復(fù)雜度高且譯碼復(fù)雜度不會隨信道條件變化而變化，每次譯碼都會計算大量分支的值，顯著的增加了譯碼過程的時間步數(shù)［9］，但在信道條件較好的時候，SC 算法有較好的性能，不必額外開分支使用SCL算法.在效率優(yōu)化方面，SARKIS 等［10］根據(jù)凍結(jié)位數(shù)量和分布特點將譯碼樹分割出4 種特殊節(jié)點類型，提出快速串行抵消（Fast-SC）譯碼算法.ANIF等［11］將Fast-SC中的特殊節(jié)點進行了更詳細(xì)的分類，并給出了確定特殊節(jié)點方法，進一步降低了譯碼時延.CAVATASSI 等［12］將Fast-SC 譯碼算法拓展到多核情況，增加了Fast-SC 譯碼的靈活度.然而，F(xiàn)ast-SC 譯碼搜索特殊節(jié)點返回中間碼字的迭代過程均與SC 譯碼相同，存在可靠性能偏低的問題.為兼顧極化碼譯碼時間效率和準(zhǔn)確率上的性能，LI等［13］提出自適應(yīng)SCL（adaptive-SCL）算法，通過動態(tài)選取保留路徑數(shù)目，提高了譯碼效率，其實質(zhì)為SC 聯(lián)合SCL 算法譯碼.本研究基于聯(lián)合譯碼的思想，提出preFast-SCL 譯碼方法，進一步提高譯碼效率.該方法首先使用Fast-SC 譯碼算法，快速得到一組譯碼結(jié)果，對得到的譯碼結(jié)果進行校驗，通過校驗則作為結(jié)果輸出，不通過校驗則繼續(xù)迭代使用SCL譯碼算法保證譯碼算法的可靠性.仿真結(jié)果表明，新算法的正確率與SCL算法基本相同，在中高信噪比條件下可有效降低譯碼復(fù)雜度.

1 極化碼譯碼算法

為便于描述極化碼常見和本研究提出的譯碼方法，表1給出了部分參數(shù)說明.

表1 參數(shù)說明Table 1 Parameters description

1.1 SC譯碼算法

極化碼的SC 譯碼使用對數(shù)似然比（logarithm likelihood ratio，LLR）進行譯碼運算.對于長度N=2n(n∈N*)的極化碼，設(shè)u=(u1，u2，…，uN)為發(fā)送信號.SC 譯碼算法先使用接收到的信號序列的對數(shù)似然比計算u1對應(yīng)的估計值，隨后利用估計，再用估計，以此類推并最終得到估計的發(fā)送信號其中，為信道序號1 到i的譯碼結(jié)果.信道序號值為i的節(jié)點的估計值為

SC 譯碼算法結(jié)構(gòu)如圖1.其中，信道i接收到的信號ri轉(zhuǎn)換為LLR值的轉(zhuǎn)換公式為

這里，σ為噪聲方差.圖1 中虛線和實現(xiàn)箭頭分別為式（5）和式（6）的f操作和g操作；每個節(jié)點代表1個LLR 值，最右側(cè)節(jié)點的LLR 值與接收端信道的LLR值相等，既，其余節(jié)點的LLR值可通過遞歸公式計算得到，再使用式（1）估計對應(yīng)節(jié)點的值，則最左側(cè)節(jié)點組成的序列即譯碼結(jié)果.

圖1 SC譯碼算法結(jié)構(gòu)Fig.1 Structure of SC decoding algorithm.

每個計算基本單元如圖2所示.基本單元運算可分為兩部分：

圖2 SC譯碼基本單元Fig.2 Basic unit of SC decoding.

1）f操作.從右往左計算左上節(jié)點的LLR 值，并使用式（1）估計該節(jié)點的比特值為u1.

其中，L1和L2為圖2中右邊2個節(jié)點的LLR值.

2）g操作.采用式（6）計算左下節(jié)點的LLR值，再使用式（1）估計該節(jié)點的比特值.

為減少仿真計算的復(fù)雜度，將式（2）簡化［14］為

圖3 SC譯碼算法的偽代碼Fig.3 Pseudocode of SC decoding algorithm.

1.2 SCL譯碼算法

SCL譯碼在SC譯碼的基礎(chǔ)上保留了L條具有最小路徑度量（path metric，PM）值的路徑，增加了譯碼的可靠性.對于長度為N=2n(n∈N*)的極化碼，SCL 譯碼中第l條(l=1，2，…，L)路徑上的第i位(i=1，2，…，N)的路徑度量為

PM 值越小，路徑越可靠.每個節(jié)點譯碼最多保留L條路徑，拓展路徑條數(shù)超過L后將保留L條具有最小PM 值的路徑，其余路徑將被剪枝刪除.因此，迭代完成后會得到L條分支，再按照PM 值從小到大排序，取第1條分支作為結(jié)果并輸出.

CA-SCL 是信道傳輸中差錯檢驗的常見技術(shù)，通過加入冗余校驗位，可更充分利用SCL的譯碼路徑.CA-SCL譯碼算法將譯碼路徑按PM值從小到大排序，再依次進行校驗，并取第1個通過路徑作為譯碼結(jié)果輸出，若都不通過則譯碼失敗.CA-SCL算法的準(zhǔn)確性比SCL算法有明顯提高［7］.

2 自適應(yīng)信道譯碼算法

傳統(tǒng)的SCL譯碼雖然準(zhǔn)確性高，但缺乏對信道條件的判斷和利用，且在時間復(fù)雜度上仍有較大優(yōu)化空間.本研究通過優(yōu)化Fast-SC 算法和探究保留路徑L對SCL 算法的影響，選擇適當(dāng)?shù)谋Ａ袈窂綌?shù)，譯碼時通過1次預(yù)快速譯碼檢測信道情況，提高極化碼譯碼效率.

2.1 Fast-SC譯碼算法及優(yōu)化

Fast-SC 算法將譯碼樹分成若干種特殊節(jié)點，然后根據(jù)節(jié)點的長度，迭代計算出相應(yīng)層數(shù)的對數(shù)似然比值.圖4 展示了4 種特殊節(jié)點的結(jié)構(gòu)，使用該結(jié)構(gòu)時其準(zhǔn)確性與SC 譯碼算法基本相同［15］.特殊節(jié)點包含但不限于以下4種結(jié)構(gòu)：

圖4 SC快速譯碼特殊節(jié)點Fig.4 Special nodes of Fast-SC decoding.

1）碼率0（rate 0，R0），所有信源比特全是凍結(jié)比特，所有比特譯碼為0，即β=（0，0，…，0）.

2）重復(fù)（repetition，Rep）碼，除最后一位外其他位全為凍結(jié)位.記，若S≥0，則β=(0，0，…，0)；否則，β=(1，1，…，1).

3）單偶校驗（single parity check，SPC）碼，除了u1是凍結(jié)比特，其余都是信息比特.硬判決為

當(dāng)SPC 譯碼結(jié)果β=(β1，β2，…，βN)的異或和為1，即時，使用比特翻轉(zhuǎn)思想［16］，取進行βp=βp⊕1 操作，得到的β為譯碼結(jié)果.

4）碼率1（rate 1，R1），所有的信源比特都為信息比特，直接使用式（8）進行硬判決.

這4種節(jié)點都可由LLR序列(y1，y2，…，yN)直接估計極化碼碼字序列β=(β1，β2，…，βN)，無需使用SC 譯碼迭代至葉節(jié)點.但是，R0節(jié)點的譯碼沒有使用接收序列，在優(yōu)化后的Fast-SC 譯碼算法中，需先辨認(rèn)特殊節(jié)點是否為R0 節(jié)點，若是，則返回全0比特；否則，計算下一層LLR時再使用對應(yīng)的譯碼規(guī)則.

表2 對比了當(dāng)N=1 024 時，SC、Fast-SC 和優(yōu)化Fast-SC譯碼算法中f函數(shù)執(zhí)行次數(shù)和對應(yīng)的誤幀率（frame error rate，F(xiàn)ER）.由表1 可見，優(yōu)化Fast-SC譯碼比Fast-SC算法在效率上約有7%的提升.

表2 不同譯碼算法f函數(shù)執(zhí)行效率和誤幀率（N=1 024）Table 2 Comparison of f function execution efficiency of different algorithms (N=1 024)

2.2 選擇CA-SCL譯碼算法合適的分支數(shù)

若CA-SCL 算法保留的路徑數(shù)L太大，會產(chǎn)生很大時延，但若L太小，則可選擇的譯碼器很少，且算法誤幀率高、可靠性低.圖5 給出了CA-SCL算法中保留路徑數(shù)對誤幀率的影響.其中，圖注中括號內(nèi)數(shù)值分別為碼長和信息值；信噪比（signal to noise ratio，SNR）分別為1.5、2.0、2.5 dB.由圖5可見，隨著L的增大，算法譯碼的準(zhǔn)確性上升，特別是在L=[2，16]時，F(xiàn)ER 下降最快.當(dāng)L≥8時，F(xiàn)ER 的變化趨于平緩.因此，本研究取L=8作為保留路徑數(shù).

圖5 CA-SCL譯碼算法保留路徑數(shù)與誤幀率的關(guān)系Fig.5 The relationship between reservation path and frame error rate of CA-SCL decoding algorithm.

2.3 preFast-SCL譯碼算法

自適應(yīng)信道的preFast-SCL 譯碼算法流程和主要模塊如圖6.

圖6 preFast-SCL譯碼流程圖Fig.6 Flow chart of preFast-SCL.

得到對數(shù)似然比序列后，配合信息位集合A和使用的特殊節(jié)點類型node_type 進行Fast-SC 譯碼中，得到譯碼序列，并對該結(jié)果進行CRC 校驗.若通過校驗，則作為最終結(jié)果輸出；否則，使用CA-SCL 譯碼器進行譯碼，提高譯碼結(jié)果可靠性.當(dāng)信道條件較好時候，F(xiàn)ast-SC 有較高通過率，可大幅提升譯碼效率.當(dāng)Fast-SC譯碼結(jié)果出現(xiàn)差錯，校驗不通過時，仍有CA-SCL 譯碼器兜底，有效提升了譯碼結(jié)果的可靠性.preFast-SCL譯碼算法的偽代碼見圖7.其中，進行CRC 校驗，存儲了所有L條路徑的譯碼結(jié)果；為第l條路徑的譯碼結(jié)果.

圖7 preFast-SCL譯碼算法偽代碼Fig.7 PreFast-SCL decoding algorithm pseudo code.

下面將討論的最大和平均時間復(fù)雜度，以及空間復(fù)雜度的推導(dǎo).

1）preFast-SCL最大復(fù)雜度是O(LNlbN)

Fast-SC 算法的時間復(fù)雜度為O(NlbN)；CASCL譯碼時間復(fù)雜度為O(NlbN)；CRC校驗時間復(fù)雜度O(m).其中，L為CA-SCL算法的保留路徑數(shù)；m為CRC校驗位長度.最差的情況是執(zhí)行快速譯碼后，檢驗失敗，而在執(zhí)行CA-SCL 譯碼算法時候，檢測到最后一條路徑才結(jié)束進行輸出，此時有最大時間復(fù)雜度為

2）平均時間復(fù)雜度是O(1 +Pe(γ)L)NlbN

Pe(γ)是SC 算法在信噪比Eb/N0=γ時的誤幀率.其中，Eb為平均比特符號能量；N0為噪聲功率頻譜.算法總會執(zhí)行1次Fast-SC譯碼算法，但僅在不通過CRC 校驗情況下才執(zhí)行CA-SCL 算法，因此，平均時間復(fù)雜度為

其中，Pe(γ)為極化碼誤幀率滿足Pe≤O(2-Nβ)，β為極化率［17］，即碼長越長，preFast-SCL的譯碼時間復(fù)雜度比起SCL算法，下降得明顯.

3）preFast-SCL算法的空間復(fù)雜度為O(LN)

Fast-SC譯碼算法與SC算法的空間復(fù)雜度相同，只需O(N)空間，而CA-SCL 算法使用懶復(fù)制（lazy copy）策略［6］，只需O(LN)空間.preFast-SCL 空間復(fù)雜度為

3 系統(tǒng)仿真分析

3.1 參數(shù)設(shè)置

為探究preFast-SCL 算法譯碼性能，本研究在加性高斯噪聲信道下進行仿真，仿真參數(shù)設(shè)置如下：CA-SCL、adaptive-SCL［13］和preFast-SCL算法使用的CRC 生成多項式均為g(x)=x16+x15+x2+1，采用二進制相移鍵控（binary phase shift keying，BPSK）調(diào)制方式，極化碼構(gòu)造采用改進高斯估計法［18］，碼率為0.5，BP譯碼最大迭代數(shù)為50次.

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

圖8對比了preFast-SCL、adaptive-SCL［13］和CASCL譯碼算法在N分別為512和1 024，信息位分別為256 和512 時的性能.其中，圖注中括號內(nèi)容表示信息比特序列長度和碼長，如(512，1 024)表示信息比特序列長度為512，碼長為1 024.

圖8 信道適應(yīng)譯碼算法與CA-SCL性能對比（a）可靠性；（b）耗時Fig.8 Performance comparison between channel adaptive decoding algorithm and CA-SCL for(a)reliability and(b)time consuming.

由圖8（a）可見，信道適應(yīng)算法preFast-SCL 和adaptive-SCL 都不會造成FER 性能損失，可靠性與CA-SCL算法基本相等.由圖8（b）可得，在Eb/N0=0～1.5 dB 時，preFast-SCL 和adative-SCL 算法的復(fù)雜度比CA-SCL 算法更高，但在Eb/N0＞1.5 dB 時，preFast-SCL和adative-SCL算法的時間復(fù)雜度比CASCL算法都有大幅降.其中，preFast-SCL算法的時間性能優(yōu)于adaptive-SCL算法.

圖9對比了preFast-SCL譯碼算法在不同碼長和信噪比條件下的FER 和時間效率性能.由圖9 可見，在低信噪比條件下，preFast-SCL譯碼算法的長碼譯碼速率低于短碼譯碼速率.碼長為N的碼字，單位比特譯碼時間的復(fù)雜度為O(lbN)，即碼字越長，譯碼速率越低.但另一方面，當(dāng)相同信噪比時，碼長增長，則碼長較長的極化碼的Pe(γ)值會降低.由式（12）可得，preFast-SCL譯碼算法的平均復(fù)雜度會下降，隨著信噪比提升，長碼譯碼的復(fù)雜度會有很大改善.

圖9 信噪比與碼長對preFast-SCL性能影響（a）可靠性；（b）譯碼耗時Fig.9 Influence of SNR and code length on the performance of preFast-SCL for(a)reliability and(b)time consuming.

圖10為preFast-SCL算法、BP算法和SC算法的在碼長N分別為256、512 和1 024 時的可靠性仿真對比.由圖10 可見，preFast-SCL 算法比傳統(tǒng)的SC和BP算法，可靠性能上有較大提升.

圖10 PreFast-SC與傳統(tǒng)算法可靠性對比Fig.10 Reliability comparison between preFast SC and traditional algorithms.

圖11 給出了在碼長N分別為512 和1 024 時，preFast-SCL、SC、CA-SCL 和Fast-SC 算法的復(fù)雜度比較.N=512，Eb/N0=2.0 dB 時，preFast-SCL 算法需執(zhí)行的操作數(shù)約為CA-SCL 算法的45%，而在N=1 024，Eb/N0=2.0 dB 時，preFast-SCL 算法需執(zhí)行的操作數(shù)僅是CA-SCL 算法的30%，且該值隨著信噪比和碼長的增加仍會繼續(xù)降低.

圖11 PreFast-SCL與傳統(tǒng)算法時間性能對比（a）N=512；（b）N=1 024Fig.11 Time performance comparison between preFast-SCL and traditional algorithms for(a)N=512 and(b)N=1 024.

結(jié)語

提出通過CRC 的輔助對傳統(tǒng)的Fast-SC 譯碼算法進行了進一步優(yōu)化，并聯(lián)合Fast-SC和CA-SCL譯碼算法，提出preFast-SCL 極化碼譯碼方法.仿真結(jié)果表明，新算法保持了相對較低的誤幀率，而且可以在信道環(huán)境較好的時候，有效的降低譯碼所需的時間.

在低信噪比（Eb/N0＜1.5 dB）條件下，preFast-SCL算法在時間復(fù)雜度上的表現(xiàn)并不理想.未來仍需將新算法跟其他同類算法做比較，探尋提升preFast-SCL在低信噪比性能的新方法.