一種基于BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼算法

奚珍珍，劉順蘭

（杭州電子科技大學(xué)電子信息學(xué)院，浙江杭州 310018）

0 引言

極化碼是一種新型的編碼方式［1-2］，也是目前3GPP 標(biāo)準(zhǔn)制定中的一種信道編碼技術(shù)方案。學(xué)者們對(duì)極化碼的構(gòu)造算法［3-4］、碼率兼容算法［5-9］、編譯碼算法展開了深入研究。極化碼在有限的碼長(zhǎng)下信道極化現(xiàn)象并不完全，譯碼的準(zhǔn)確性嚴(yán)重影響通信質(zhì)量。連續(xù)消除譯碼（Successive Cancellation，SC）是基于極化碼最早提出的低復(fù)雜度譯碼算法，但是該譯碼容易存在錯(cuò)誤傳播現(xiàn)象［10］；連續(xù)消除列表（Successive Cancellation List，SCL）譯碼是連續(xù)消除譯碼的改進(jìn)算法，通過(guò)多路徑貪心搜索方法可減少丟失正確碼元的可能性［11-12］；CRC 輔助校驗(yàn)的SCL 譯碼（CRC-Aided SCL，CA-SCL）［13］利用CRC 校驗(yàn)碼檢錯(cuò)的特性，進(jìn)一步提高了譯碼的正確率，使極化碼相比低密度奇偶校驗(yàn)碼（Low-Density Parity-Check，LDPC）［14］具有更好的性能。

隨著候選路徑數(shù)量L 的增加，譯碼準(zhǔn)確率有明顯提升，但計(jì)算的內(nèi)存也急劇增加，對(duì)此，文獻(xiàn)［15］提出了CRC 輔助校驗(yàn)的分段譯碼，能在不降低譯碼性能的前提下對(duì)硬件的內(nèi)存需求更低。而CRC 只能檢錯(cuò)，BCH 碼不僅可以檢錯(cuò)又可以糾錯(cuò)。文獻(xiàn)［16］進(jìn)一步改良，提出了BC-SCL 分段譯碼，對(duì)一段碼元進(jìn)行糾錯(cuò)，進(jìn)而使譯碼性能得到改善；將polar 碼與其他碼字級(jí)聯(lián)也是改進(jìn)譯碼準(zhǔn)確性的有效方法：極化碼與卷積碼級(jí)聯(lián)的譯碼方法誤塊率，在各種編碼率下隨碼率增長(zhǎng)呈指數(shù)衰減［17］；Saber 等［18］建議與極化碼級(jí)聯(lián)時(shí)，外碼的碼長(zhǎng)小于等于8，并通過(guò)密度演化算法來(lái)計(jì)算子信道的錯(cuò)誤概率，該方法不但改善了極化碼性能，而且計(jì)算復(fù)雜度較低。

為了進(jìn)一步提高極化碼在有限碼長(zhǎng)時(shí)的極化碼譯碼準(zhǔn)確性，本文利用BCH 可糾正多個(gè)錯(cuò)誤的特性［19］，實(shí)現(xiàn)由BCH 級(jí)聯(lián)極化碼并進(jìn)行分段編碼與譯碼。為有效彌補(bǔ)錯(cuò)誤傳播現(xiàn)象造成的性能損失，對(duì)BCH 譯碼也進(jìn)一步改進(jìn)，選擇錯(cuò)誤概率較小且校驗(yàn)成功的路徑作為輸出。仿真顯示，在相同條件下，系統(tǒng)極化碼［20］性能優(yōu)于極化碼。因此，本文將該分段譯碼方法擴(kuò)展應(yīng)用到BCH 級(jí)聯(lián)系統(tǒng)極化碼。

1 極化碼概述

1.1 極化碼與系統(tǒng)極化碼

極化碼是一種基于信道極化理論的信道編碼方式。當(dāng)碼長(zhǎng)不斷增加時(shí)，編碼端通過(guò)碼字構(gòu)造方法后，各個(gè)子信道的信道容量呈現(xiàn)出兩級(jí)分化現(xiàn)象，將信道容量趨近于1 的完美信道用來(lái)傳輸有用信息，從而達(dá)到信道容量。

對(duì)于給定的碼長(zhǎng)N，極化碼編碼方式如下：

其中，A為信息位位置索引集合，AC為凍結(jié)位位置索引集合，uA為有用信息序列為凍結(jié)信息序列，通常置為0，GN(A)表示由A中元素對(duì)應(yīng)的行構(gòu)成的GN的子矩陣，GN(Ac)同理，⊕表示模2 加。

根據(jù)文獻(xiàn)［20］可知，系統(tǒng)極化碼與極化碼相比在SC 譯碼下錯(cuò)誤傳播更少，兩者在編碼階段及譯碼階段都存在著差異。

系統(tǒng)極化碼定義為：

其中,x=(xB,)為系統(tǒng)極化碼的編碼碼字，B為{1,…,N}的任意子集，也稱為信息位位置索引集合，BC為B在{1,…,N}集合的補(bǔ)集，也稱為凍結(jié)位位置索引集合。GAB為G 的子矩陣，由i∈A,j∈B的元素(Gi,j)組成，，定義同上。

在編碼階段，極化碼的信息比特被分配到碼源序列，而系統(tǒng)極化碼是由編碼后的碼字?jǐn)y帶信息比特。在譯碼階段，用于極化碼的譯碼算法都適用于系統(tǒng)極化碼，不同的是極化碼的誤碼率和誤塊率的統(tǒng)計(jì)是通過(guò)比較uA和而系統(tǒng)極化碼是通過(guò)比較xB和因此系統(tǒng)極化碼譯碼得到譯碼判決結(jié)果后，還需再進(jìn)行編碼才能得到

1.2 SCL 譯碼

SC 譯碼過(guò)程是串行進(jìn)行，因此存在容易錯(cuò)誤傳播現(xiàn)象，且SC 譯碼碼樹形式的譯碼最終僅選出一條路經(jīng)，容易丟失最佳路徑。為了降低該情況出現(xiàn)的概率，SCL 譯碼引入了保留多條譯碼路徑的思想。在譯碼準(zhǔn)備階段，設(shè)定一個(gè)備選路徑數(shù)目的最大值L，在每一層譯碼過(guò)程中，最多可保留L 條備選路徑。在SCL 譯碼過(guò)程中有一個(gè)重要的參數(shù)，即基于LLR 的路徑度量值（Path Metric，PM）［21］，定義為：

2 BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼

BCH 級(jí)聯(lián)極化碼方案，是將BCH 碼作為外碼，極化碼為內(nèi)碼，基于BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼詳細(xì)流程如圖1 所示。在極化碼編碼前，將信息比特分為兩段，每段分別通過(guò)BCH 編碼在每組信息比特的后面增加校驗(yàn)位。SCL譯碼后對(duì)譯碼比特進(jìn)行分段校驗(yàn)，利用BCH 碼糾錯(cuò)特性進(jìn)行糾錯(cuò)。

Fig.1 Flow of BCH cascaded polar code segment check decoding algorithm圖1 BCH 級(jí)聯(lián)極化碼分段校驗(yàn)譯碼算法流程

通常，傳統(tǒng)的校驗(yàn)方法是在信息序列的末尾添加一段校驗(yàn)碼，而分段校驗(yàn)與傳統(tǒng)檢驗(yàn)的最大不同在于分段校驗(yàn)是在信息序列中相對(duì)分散地插入較短的校驗(yàn)碼。通過(guò)采用分段校驗(yàn)輔助方法可實(shí)現(xiàn)提前終止譯碼，以省去不必要的譯碼時(shí)間。

2.1 編碼系統(tǒng)模型

如圖2 所示，BCH 級(jí)聯(lián)極化碼編碼系統(tǒng)模型主要包括BCH 編碼和極化碼編碼。假設(shè)采用（n，k，t）BCH 碼和（N，K）極化碼進(jìn)行級(jí)聯(lián)，其中k 為參與BCH 編碼的信息比特序列長(zhǎng)度，n 為BCH 編碼后得到的碼字長(zhǎng)度，t 為糾錯(cuò)能力，N表示極化碼長(zhǎng)度，K 表示參與極化碼編碼的信息比特序列長(zhǎng)度，BCH 碼字中包含了r=n-k 個(gè)校驗(yàn)比特。

Fig.2 BCH cascaded polar code coding system model圖2 BCH 級(jí)聯(lián)極化碼編碼系統(tǒng)模型

2.2 分段校驗(yàn)譯碼算法

BC-SCL 譯碼算法是在SCL 譯碼后，分別進(jìn)行BCH 譯碼和CRC 校驗(yàn)，因此只有第一段可以進(jìn)行糾錯(cuò)。本文提出的譯碼算法是兩段都進(jìn)行BCH 譯碼，每段都有糾正t 個(gè)錯(cuò)誤的機(jī)會(huì)，在較低的內(nèi)存需求下，提高了整體的譯碼性能。

本文提出的適用于BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼算法可分為兩個(gè)部分：第一部分是SCL 譯碼算法，譯碼結(jié)束后，按照路徑度量值由小到大的順序保留L 條路徑；第二部分是BCH 分段校驗(yàn)譯碼算法，依次對(duì)L 條候選路徑進(jìn)行校驗(yàn)，若校驗(yàn)失敗再進(jìn)行糾錯(cuò)。選擇路徑度量值最小且校驗(yàn)成功的路徑作為輸出，有效彌補(bǔ)了錯(cuò)誤傳播現(xiàn)象造成的性能損失。

圖3 為BCH 分段校驗(yàn)譯碼算法流程。該算法的輸入值是SCL 譯碼后的L 條路徑中存放拆分后的譯碼比特序列的，其 中表示第L 條路徑中存儲(chǔ)的n個(gè)譯碼比特，輸出序列默認(rèn)為第一條路徑存儲(chǔ)的n 個(gè)譯碼比 特首先通過(guò)校驗(yàn) 矩陣對(duì)第一條路徑進(jìn)行BCH 校驗(yàn)，若校驗(yàn)成功則直接輸出該序列，進(jìn)行下一段BCH 校驗(yàn)譯碼；若校驗(yàn)失敗，則對(duì)該路徑進(jìn)行BCH糾錯(cuò)并進(jìn)行校驗(yàn)。若成功，直接輸出當(dāng)前糾錯(cuò)后的結(jié)果，進(jìn)行下一段BCH 校驗(yàn)譯碼；若糾錯(cuò)失敗，繼續(xù)對(duì)下一條路徑進(jìn)行判定。此算法利用BCH 碼的檢錯(cuò)與糾錯(cuò)特性，自列表的第一條路徑開始，檢測(cè)到首條可通過(guò)校驗(yàn)的路徑即立即終止本段的譯碼算法。若直至最后一條路徑都校驗(yàn)失敗，則輸出默認(rèn)序列。該算法通過(guò)層層嚴(yán)格篩選，輸出能夠通過(guò)BCH 糾錯(cuò)校驗(yàn)的路徑且錯(cuò)誤概率相對(duì)最小的路徑，由此進(jìn)一步提高了BCH 級(jí)聯(lián)極化碼的誤碼性能。

Fig.3 BCH segment check and decoding algorithm flow圖3 BCH 分段校驗(yàn)譯碼算法流程

BCH 級(jí)聯(lián)極化碼分段校驗(yàn)譯碼流程如下：①初始化。給定（N，K）系統(tǒng)polar 碼，（n，k，t）BCH 級(jí)聯(lián)polar 碼，其中BCH 碼的校驗(yàn)位數(shù)量r=n-k，候選路徑的數(shù)量L，凍結(jié)信息序列置0；②BCH 編碼。將長(zhǎng)度為K-2r 的輸入信息序列分為兩段，對(duì)每段分別進(jìn)行BCH 編碼，完成編碼后將兩段BCH 碼合并碼字，并進(jìn)行混合比特；③polar 碼編碼。利用公式（2）對(duì)得到的混合比特進(jìn)行編碼得到極化碼的碼字；④輸入信道。使用BPSK 對(duì)接收到的碼字進(jìn)行調(diào)制，調(diào)制后添加噪聲并傳輸?shù)浇邮斩耍虎輕olar 碼譯碼。對(duì)接收到的信息執(zhí)行SCL 譯碼，得到按照錯(cuò)誤概率由小到大的順序保留的L 條路徑；⑥BCH 譯碼。首先將SCL 譯碼得到的L 條序列拆分，得到兩段L 條子序列；其次，按順序依次對(duì)每段的L 條信息序列的估計(jì)值進(jìn)行校驗(yàn)與糾錯(cuò)，檢測(cè)到首條可通過(guò)校驗(yàn)的路徑即立即終止本段的BCH 譯碼；若直至最后一條路徑都校驗(yàn)失敗，則本段輸出默認(rèn)的序列。兩段都完成BCH 譯碼后，將兩段譯碼結(jié)果合并作為最后的輸出結(jié)果。

由于系統(tǒng)極化碼性能比非系統(tǒng)極化碼更優(yōu)異，因此本文將提出的譯碼算法推廣應(yīng)用到BCH 級(jí)聯(lián)系統(tǒng)極化碼。在整個(gè)編譯碼過(guò)程中，系統(tǒng)碼的編碼稍有不同，按照式（3）、式（4）進(jìn)行編碼，譯碼部分完全適用。

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

基于以上理論分析進(jìn)行MATLAB 仿真。AWGN 信道下，采用SCL 譯碼并加入文獻(xiàn)［16］的BC-SCL（BCH-CRCaided segmented SCL decoding）算法，與本文所提的BCH 級(jí)聯(lián)極化碼分段校驗(yàn)譯碼算法進(jìn)行對(duì)比。

實(shí)驗(yàn)1：將文獻(xiàn)［16］提出的BC-SCL 與本文提出的級(jí)聯(lián)極化碼分段校驗(yàn)譯碼在相同信噪比條件下進(jìn)行比較，仿真參數(shù)如表1 所示，不同碼長(zhǎng)情況下的兩種譯碼誤碼率性能比較如圖4 所示。

Table 1 Simulation parameters（based on fig.4）表1 仿真參數(shù)（基于圖4）

表1 中BCH-polar（128）代表本文提出的分段校驗(yàn)譯碼算法，極化碼碼長(zhǎng)為128，BC-polar（128）代表BC-SCL 算法極化碼碼長(zhǎng)為128，SCL 譯碼的列表長(zhǎng)度L 為8。

由圖4（彩圖掃OSID 碼可見(jiàn)，下同）的仿真結(jié)果可見(jiàn)，在碼長(zhǎng)相同的情況下對(duì)兩種譯碼方法的誤碼性能進(jìn)行比較，本文提出的基于BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)算法在譯碼性能上比BC-SCL 譯碼效果更好。當(dāng)誤碼率為10-3、極化碼碼長(zhǎng)為64 時(shí)，本文提出的譯碼算法相比BC-SCL 獲得了約0.25dB 增益；極化碼碼長(zhǎng)為128 時(shí)，本文提出的譯碼算法相比BC-SCL 獲得了約0.1dB 增益。采用本文提出的分段校驗(yàn)譯碼算法，當(dāng)極化碼碼長(zhǎng)較短時(shí)，子信道極化程度低，誤碼率明顯降低。

實(shí)驗(yàn)2：在相同信噪比條件下，將本文提出的算法擴(kuò)展到BCH 級(jí)聯(lián)系統(tǒng)極化碼，同BCH 級(jí)聯(lián)極化碼比較。具體仿真參數(shù)為：極化碼與系統(tǒng)極化碼碼長(zhǎng)分別為256、64，碼率為0.5，與之級(jí)聯(lián)的BCH 碼分別為（63，57，1）、（15，11，1）。

如圖5 所示，BCH-syspolar（256）與BCH-polar（256）分別代表本文提出的BCH 級(jí)聯(lián)極化碼分段校驗(yàn)譯碼算法與擴(kuò)展到BCH 級(jí)聯(lián)系統(tǒng)極化碼的分段校驗(yàn)譯碼算法，極化碼與系統(tǒng)極化碼的碼長(zhǎng)都為256。

相同碼長(zhǎng)情況下，BCH 級(jí)聯(lián)系統(tǒng)極化碼的分段校驗(yàn)譯碼性能均比級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼性能更好。當(dāng)誤碼率為10-3，碼長(zhǎng)為256 時(shí)，BCH 級(jí)聯(lián)系統(tǒng)極化碼的分段校驗(yàn)譯碼算法比級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼算法獲得了約0.2dB 增益。碼長(zhǎng)為64 時(shí)，前者比后者獲得了約0.2dB 增益。碼長(zhǎng)越長(zhǎng)，子信道極化越完全，極化碼與系統(tǒng)極化碼自身的性能會(huì)有所提升，BCH 級(jí)聯(lián)系統(tǒng)極化碼的譯碼算法與級(jí)聯(lián)極化碼的譯碼算法的誤碼性能會(huì)越好，并且前者比后者的誤碼性能更好。

Fig.4 Comparison of bit error rate performance of two decodings under different code lengths圖4 不同碼長(zhǎng)情況下的兩種譯碼誤碼率性能比較

Fig.5 Comparison of the bit error rate performance of the decoding algorithm of the cascaded polar code and the cascaded system polar code under different code lengths圖5 不同碼長(zhǎng)情況下，級(jí)聯(lián)極化碼與級(jí)聯(lián)系統(tǒng)極化碼譯碼算法的誤碼率性能比較

4 結(jié)語(yǔ)

本文提出了基于BCH 級(jí)聯(lián)極化碼的分段校驗(yàn)譯碼算法，利用對(duì)SCL 譯碼序列進(jìn)行BCH 分段校驗(yàn)，選擇首條可通過(guò)校驗(yàn)且錯(cuò)誤概率相對(duì)較小的路徑作為輸出，更好地降低了誤碼率。仿真分析結(jié)果表明，相同碼長(zhǎng)下，本文提出的譯碼算法性能明顯優(yōu)于BC-SCL 譯碼算法。將該分段譯碼算法推廣應(yīng)用到BCH 級(jí)聯(lián)系統(tǒng)極化碼，有限碼長(zhǎng)的性能有進(jìn)一步提升。下一步研究重點(diǎn)是在保證有限碼長(zhǎng)性能的前提下降低譯碼的復(fù)雜度。