一種基于極化碼APC-SCL的譯碼算法

李君玉， 王淑琴， 劉東海

(1. 中北大學(xué) 電子測試技術(shù)國家重點(diǎn)實(shí)驗(yàn)室， 山西 太原 030051；2. 中北大學(xué) 儀器科學(xué)與動態(tài)測試教育部重點(diǎn)實(shí)驗(yàn)室， 山西 太原 030051)

0 引 言

2008年， 土耳其教授Erdal Arikan最先提出極化碼這一概念， 它是第一種被證明了能夠在二進(jìn)制離散無記憶信道下達(dá)到香農(nóng)限的碼， 同時也被確定為5G eMBB場景下控制信道編碼， 被廣泛應(yīng)用于各個領(lǐng)域， 尤其是通信領(lǐng)域[1].

對于通信系統(tǒng)來說， 編碼和譯碼算法都是其研究的核心的內(nèi)容. 極化碼編碼選擇質(zhì)量好的信道傳輸信息比特， 選擇質(zhì)量差的信道傳輸固定比特， 其編碼方案依照信道極化的規(guī)則來進(jìn)行變換. 在譯碼方面， Arikan給出了極化碼的串行抵消(Successive Cancellation)譯碼算法[2]. I.Tal提出了基于SC譯碼算法的list算法[3]， 也就是SCL算法， SCL算法具有接近最大似然的性能， 所以被廣泛使用， 但由于繼承了SC算法的思想， 延遲高的問題并沒有得到解決， 并且復(fù)雜度較高[4]. 本設(shè)計在CRC-SCL算法的基礎(chǔ)上進(jìn)行改進(jìn)， 形成一種新的譯碼算法， 即APC-SCL(Adaptive Partitioned CRC-SC List)譯碼算法， 極化碼編碼時， 對信息比特分組， 并在每組信息比特的后面增加監(jiān)督位. 譯碼時， 先進(jìn)行SC譯碼， 再根據(jù)校驗(yàn)信息選擇， 得到最后的譯碼結(jié)果.

1 CRC-SCL譯碼算法

CRC是常見的輔助校驗(yàn)手段， 廣泛用于數(shù)據(jù)通信與網(wǎng)絡(luò)中. CRC-SCL譯碼即為在極化碼的SCL譯碼算法中加入 CRC監(jiān)督位， 改進(jìn)的SCL譯碼算法性能大大提升[5]， 同時編碼速率并沒有減少太多， 兩者處于一種比較平衡的狀態(tài). CRC-SCL編譯流程如圖 1 所示.

圖 1 CRC-SCL算法通信框圖Fig.1 Communication diagram of CRC-SCL algorithm

算法的基本思想為： 輸入k比特的信息位， 然后添加m位CRC碼， 將K=k+m比特輸入編碼器[6]， 對信息位進(jìn)行極化碼編碼， 得到N位信道輸入， 經(jīng)過添加噪聲后的信道(例如高斯白噪聲信道等)傳輸進(jìn)入譯碼器. 該譯碼器包含SCL譯碼器和解CRC碼單元. SCL譯碼器譯出L個候選序列之后， 將其對應(yīng)的路徑度量值進(jìn)行由大到小的排序， 輸出最有效的路徑結(jié)果. 發(fā)端和收端使用一致的CRC多項(xiàng)式g(X)， 根據(jù)CRC校驗(yàn)和是否為0判斷傳輸過程有無發(fā)生錯誤[7]. CRC-24條件下

g(x)=x24+x23+x18+x17+x14+x11+x10+

x7+x6+x5+x4+x3+x+1.

(1)

選取MATLAB平臺對CRC-SCL譯碼算法進(jìn)行仿真， 仿真條件如表 1 所示，
圖 2 所示為極化碼在不同列表長度CRC-SCL算法下的誤幀率比較， 表 2 為CRC-SCL譯碼算法平均搜索寬度.

表 1 仿真條件Tab.1 Simulation condition

表 2 CRC-SCL譯碼算法平均搜索寬度Tab.2 The mean of search width of the CRC-SCL decoding algorithm

圖 2 極化碼在不同列表長度CRC-SCL算法下 的誤幀率性能對比圖Fig.2 Frame error rate comparison of CRC-SCL algorithm under diffent list length

仿真表明， 極化碼的CRC-SCL譯碼算法可以通過增大列表長度的方式獲得譯碼性能的持續(xù)提升， 而且列表長度越大， 所獲得的性能增益也越大[8]. 例如， 當(dāng)FER性能為10-2時， 列表長度為32和8所需的信噪比分別為1.60 dB和1.87 dB， 性能增益提升了0.27 dB. 由表 2 可看出： CRC-SCL譯碼平均搜索寬度隨著信噪比的增大而減小， 可見， CRC-SCL譯碼算法在高信噪比區(qū)間性能較好、 譯碼復(fù)雜度較低； 在低信噪比區(qū)間性能較差、 譯碼復(fù)雜度較高.

2 APC-SCL譯碼算法

通過分析CRC-SCL譯碼算法， 發(fā)現(xiàn)其譯碼復(fù)雜度隨信噪比減小而增大， 在低信噪比區(qū)間的性能不理想， 所以提出自適應(yīng)性分段循環(huán)冗余校驗(yàn)輔助串行抵消列表(APC-SCL)譯碼算法[9].
圖 3 所示為算法編譯框圖.

圖 3 APC-SCL算法編譯框圖Fig.3 Compilation diagram of APC-SCL algorithm

2.1 編碼結(jié)構(gòu)

APC-SCL算法在編碼時采用分段編碼[10]， 不僅在性能上與CRC校驗(yàn)?zāi)軐?shí)現(xiàn)同樣的效果， 而且在結(jié)構(gòu)上易于實(shí)現(xiàn).

算法的基本思想是： 首先確定分段的數(shù)量， 然后根據(jù)信息位和監(jiān)督位的制約關(guān)系， 確定監(jiān)督位位數(shù)， 在每個子段信息比特后增加監(jiān)督位， 最后將子段序列拼接起來再進(jìn)行極化碼的編碼[11].

在確定分段P時， 需要考慮如下的制約關(guān)系：

假設(shè)碼長為N， 其中K個位置上傳輸來自信源的消息比特， 剩余的N-K的位置傳輸不含信息量的固定比特， 碼率R=K/N，K為有用比特數(shù)， 分為P組， 則每組K/P個比特，K/P=k+C.k和C必須滿足2C≥k+C+1，k是信息比特的位數(shù)，C是CRC監(jiān)督位的位數(shù). 隨著P的增加， CRC-SCL譯碼算法的編碼效率會變小， 為保證傳輸?shù)拇a率不變， 應(yīng)考慮每段CRC的位數(shù)CP， 也就是C/P的關(guān)系，CP越小， 校驗(yàn)性能越差， 漏檢率越高， 譯碼性能降低[12].

2.2 譯碼結(jié)構(gòu)

譯碼時對該段先采用SC譯碼， 如果校驗(yàn)成功則進(jìn)行下一段譯碼； 如果校驗(yàn)失敗， 則對該段進(jìn)行SCL譯碼， 同時將搜索寬度直接賦值為最大搜索寬度， 減少譯碼時間. 如果可以通過CRC校驗(yàn)， 則進(jìn)行下一段譯碼， 否則校驗(yàn)失敗.

以P=1為例， 假如每個時鐘為1個周期， CRC-SCL譯碼算法完成譯碼需要2N-2+RN個時鐘， 但SC譯碼算法完成譯碼僅需要2N-2個時鐘周期[13].

改進(jìn)后的譯碼算法， 初始化時i=1，L=1， 先走SC算法譯碼， 進(jìn)行CRC校驗(yàn)， 當(dāng)譯碼不成功時不再逐漸增大L， 而是直接令L=Lmax， 走SCL譯碼算法， 進(jìn)行CRC校驗(yàn)， 完成譯碼[14]. 改進(jìn)后的譯碼算法最大搜索寬度不變， 譯碼性能不受影響. 譯碼器在SC和SCL兩種譯碼模式下切換， 完成譯碼工作. 大部分碼字可以用2N-2個時鐘完成譯碼， 很少一部分會需要(2N-2)+(2N-2+RN)=4N-4+RN個時鐘， 隨著信噪比的增高， 譯碼周期平均值趨于2N-2. 具體譯碼流程如圖 4 所示.

圖 4 APC-SCL譯碼算法流程圖Fig.4 The flow chart of APC-SCL decoding algorithm

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

仿真基于MATLAB平臺， 取碼長為1 024， 列表長度統(tǒng)一設(shè)置為32， 分別對P取不同值的APC-SCL算法譯碼性能進(jìn)行分析， 仿真配置見表 3. 由于在碼長為1 024時， 分成32組和64組， 編碼效率η分別為68.75%和50%， 由于這兩種分段方式的編碼效率太低， 因此這兩種分組不予考慮.

由圖 5 的仿真結(jié)果可看出， 在碼長為1 024條件下， 誤幀率為10-2，P=16時APC-SCL譯碼算法相比CRC-SCL譯碼獲得了0.1 dB的增益， 隨著信噪比的增加， 誤幀率逐漸降低， 在大信噪比下， 優(yōu)異性更加明顯. 由于過多的分組會導(dǎo)致編碼效率降低， 大量的監(jiān)督比特會占用可靠信道， 降低信息比特數(shù)量[15]. 綜合硬件條件， 取P=2或P=4都是不錯的選擇. 由于CRC-SCL算法編碼效率為95%， 所以本譯碼算法選擇P=2，
圖 6 為APC-SCL算法和CRC-SCL算法在不同列表長度下的誤幀率比較. 表 4 為APC-SCL譯碼算法平均寬度.

表 3 仿真參數(shù)Tab.3 Simulation parameterR

圖 5 不同P值下的FER比較Fig.5 Comparison of FER under different P values

圖 6 極化碼在APC-SCL和CRC-SCL算法下的FER比較Fig.6 Comparison of FER of polarization codes under APC-SCL and CRC-SCL algorithms

從圖 6 的對比中可以看出： APC-SCL譯碼算法相對于CRC-SCL譯碼算法基本無性能損失， 曲線走向一致， 隨著搜索寬度L的增加， 分兩段APC-SCL譯碼逐漸和CRC-SCL譯碼拉開差距， 而且在不同誤幀率的情況下， 均獲得了0.05～0.1 dB 的增益. 對比表 2 和表 4 中的數(shù)據(jù)， 可以得到改進(jìn)的算法相對于之前的譯碼算法平均搜索寬度減少的百分比，
圖 7 所示為不同信噪比之下兩種譯碼算法的平均搜索寬度減少的百分比. 結(jié)合圖表可以分析出APC-SCL譯碼算法在低信噪比區(qū)間平均搜索寬度減小了26.8%， 譯碼復(fù)雜度減小.

表 4 APC-SCL譯碼算法平均搜索寬度Tab.4 The mean of Search width of the APC-SCL decoding algorithm

圖 7 APC-SCL算法相對于CRC-SCL算法平均 搜索寬度減少百分比Fig.7 The average search width reduction of APC-SCL algorithm compared to CRC-SCL algorithm

著眼于譯碼復(fù)雜度， 本文的設(shè)計比現(xiàn)有技術(shù)更加的簡便. 使用所提出的分段編碼， 降低了譯碼的空間復(fù)雜度， 而自適應(yīng)的譯碼算法則降低了原有譯碼的時間復(fù)雜度.

4 結(jié)束語

本文提出的APC-SCL極化碼譯碼算法， 通過仿真分析， 在降低譯碼復(fù)雜度上明顯優(yōu)于CRC-SCL譯碼算法， 在同等條件下， 能夠降低算法在低信噪比區(qū)間的平均搜索寬度. 關(guān)于列表長度與監(jiān)督位， 增加監(jiān)督位比特的確會使糾錯能力增強(qiáng)， 但同時也會降低極化碼的編碼效率； 增加列表長度的確會使算法性能更加優(yōu)良， 但是過大的列表長度會帶來更大的復(fù)雜度以及延遲等問題， 如何在兩者之間取得平衡也是接下來需要研究的問題.