張文宇，郭 銳

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

0 引 言

由Arikan提出的極化碼是一種基于信道極化的信道編碼方案[1]，是目前理論上唯一能實(shí)現(xiàn)香農(nóng)容量的方法，適用于任意二進(jìn)制離散無(wú)記憶信道(Binary Discrete Memoryless Channel, B-DMC)，在加性高斯白噪聲信道(Additive White Gaussian Noise, AWGN)中也具有優(yōu)異的糾錯(cuò)能力，是未來(lái)6G通信的主要候選方案之一[2]。串行抵消(Successive Cancellation, SC)算法[1]譯碼復(fù)雜度較低，但譯碼性能不夠理想。串行抵消列表(Successive Cancellation List, SCL)算法[3]通過(guò)保留多條譯碼路徑并從中選取可靠性最高的路徑作為輸出，性能優(yōu)于SC算法[4]，但計(jì)算復(fù)雜度是SC算法的L倍，其中L代表列表數(shù)。在SCL算法中引入循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check, CRC)可以有效提升譯碼性能，CRC輔助的列表譯碼(CRC Aided SCL, CA-SCL)算法[5]將一段很長(zhǎng)的CRC比特連接在信息序列尾部。分段CRC輔助的極化碼[6]將校驗(yàn)比特均勻插入到信息序列中，可以更及時(shí)地檢測(cè)錯(cuò)誤的發(fā)生。將奇偶校驗(yàn)和極化碼級(jí)聯(lián)，在中短碼長(zhǎng)的情況下，可以提升一定的譯碼性能[7]。在SCL譯碼中引入奇偶校驗(yàn)和CRC，在擁有優(yōu)于SCL算法譯碼性能的同時(shí)還能實(shí)現(xiàn)更低的譯碼復(fù)雜度[8]。雙奇偶校驗(yàn)和CRC輔助的SCL算法[9]可以進(jìn)一步提升譯碼性能，該算法以每2個(gè)奇偶檢驗(yàn)比特為1組插入到極化碼中。減少路徑分裂次數(shù)的列表譯碼(Split Reduced Successive Cancellation List, SR-SCL)算法[10]提出一種新的路徑分裂規(guī)則，當(dāng)滿足該規(guī)則時(shí)，說(shuō)明極化子信道的可靠性足夠高，直接執(zhí)行硬判決而不是進(jìn)行路徑分裂。此外，在路徑分裂的過(guò)程中還設(shè)定了閾值，用于刪除那些分裂次數(shù)較少的路徑。SR-SCL算法還證明，假設(shè)在某個(gè)特定比特之前的所有譯碼比特全部正確，在該特定比特之后可以將原有算法替換為SC譯碼，進(jìn)而提出增強(qiáng)的SR-SCL(Enhanced Split-Reduced SCL, ESR-SCL)算法[10]，保持相似譯碼性能的同時(shí)降低了復(fù)雜度。

雖然SR-SCL算法的譯碼復(fù)雜度低于SCL算法，但譯碼性能較差。針對(duì)這一問(wèn)題，本文提出一種奇偶校驗(yàn)和CRC輔助的ESR-SCL算法，引入奇偶校驗(yàn)比特及時(shí)刪除部分錯(cuò)誤路徑，并通過(guò)CRC校驗(yàn)選取可靠性最高的譯碼路徑作為輸出，有效提升了譯碼性能，降低了譯碼復(fù)雜度。

1 極化碼的編譯碼方案

1.1 極化碼的構(gòu)造

1.2 譯碼原理

(1)

(2)

SC譯碼器采用的是硬判決方式。在中短碼長(zhǎng)情況下，信道極化不充分，導(dǎo)致一些信息比特發(fā)生譯碼錯(cuò)誤，發(fā)生錯(cuò)誤傳播。針對(duì)這一缺點(diǎn)，SCL譯碼算法將每個(gè)譯碼路徑分裂成2個(gè)候選路徑，通過(guò)列表保留L(L代表列表數(shù))條候選路徑，當(dāng)路徑數(shù)大于列表數(shù)時(shí)，選取路徑度量值最大的L條路徑存入列表。路徑度量值可通過(guò)遞歸計(jì)算得到：

(3)

1.3 SR-SCL譯碼算法

SR-SCL是一種基于SCL算法的改進(jìn)算法，在某些條件下不進(jìn)行路徑分裂，判決是否進(jìn)行分裂的公式為：

(4)

式中，Pe(ui)為第i個(gè)信息比特的錯(cuò)誤概率。當(dāng)譯碼比特的錯(cuò)誤概率較低時(shí)，將不進(jìn)行分裂。SR-SCL算法還引入了計(jì)數(shù)器對(duì)路徑進(jìn)行剪枝的操作，對(duì)路徑在不分裂情況下的生存階段數(shù)ωl[i]進(jìn)行計(jì)數(shù)。當(dāng)路徑數(shù)大于列表數(shù)時(shí)，如果ωl[i]達(dá)到預(yù)先設(shè)定的閾值ω，刪除計(jì)數(shù)器的計(jì)數(shù)值小于ω的路徑。

2 奇偶校驗(yàn)和循環(huán)冗余校驗(yàn)級(jí)聯(lián)的極化碼

2.1 奇偶校驗(yàn)和CRC級(jí)聯(lián)極化碼的結(jié)構(gòu)

2.2 奇偶校驗(yàn)位的構(gòu)造

(5)

式中，σ2表示噪聲方差，φ(x)為一個(gè)單調(diào)遞減函數(shù)，可以近似計(jì)算為：

(6)

取信噪比為1 dB，碼長(zhǎng)N為256，碼率R為0.5，計(jì)算得到未凍結(jié)比特信道的錯(cuò)誤概率如圖1所示。圖1中，垂直虛線代表根據(jù)錯(cuò)誤概率繪制的信息段邊界，極化碼被7條邊界分為8個(gè)信息段。通過(guò)不同信噪比劃分不同的突發(fā)錯(cuò)誤段來(lái)構(gòu)造奇偶校驗(yàn)位，能更好地檢測(cè)和刪除信道產(chǎn)生的錯(cuò)誤。

圖1 極化碼子信道的錯(cuò)誤概率分布圖

對(duì)于(N,K)的極化碼，假設(shè)共有8個(gè)信息段和16個(gè)奇偶校驗(yàn)比特，校驗(yàn)方式為奇校驗(yàn)，信息位的長(zhǎng)度為K，前i個(gè)信息段的長(zhǎng)度為Ki，xj表示第j個(gè)信息比特，所有的第1校驗(yàn)位由之前所有的信息比特決定，第i(i是奇數(shù))個(gè)奇偶校驗(yàn)比特表示為：

(7)

當(dāng)?shù)?奇偶校驗(yàn)位完成編碼后，由于預(yù)先設(shè)定為奇校驗(yàn)，為了保證第1奇偶校驗(yàn)位進(jìn)行校驗(yàn)時(shí)不受影響，則第2奇偶校驗(yàn)位的編碼結(jié)果為：

pi=0i=2,4,6,8

(8)

譯碼階段首先通過(guò)第1奇偶校驗(yàn)位進(jìn)行校驗(yàn)，若校驗(yàn)不通過(guò)則直接刪除譯碼路徑，而第2奇偶校驗(yàn)位的譯碼結(jié)果可直接通過(guò)硬判決得到，如果和預(yù)先已知的編碼結(jié)果不相符，說(shuō)明譯碼發(fā)生錯(cuò)誤，則調(diào)整該路徑的路徑度量值。采用二進(jìn)制相移鍵控(Binary Phase Shift Keying, BPSK)進(jìn)行調(diào)制，流程如圖2所示。

圖2 奇偶校驗(yàn)和CRC輔助的SR-SCL譯碼算法流程

2.3 奇偶校驗(yàn)和CRC級(jí)聯(lián)的極化碼譯碼

譯碼凍結(jié)比特和信息比特的過(guò)程和SR-SCL算法相同，不同之處在于增加了奇偶校驗(yàn)和CRC校驗(yàn)，譯碼階段分為2種情況，當(dāng)譯碼信息比特時(shí)，遵循式(4)的分裂規(guī)則，若滿足條件則進(jìn)行路徑分裂，若分裂后的路徑數(shù)大于L，將保留L條路徑度量值較小的路徑，同時(shí)在第i階段譯碼完成后根據(jù)計(jì)數(shù)器中記錄的值進(jìn)行剪枝。由于正確的譯碼路徑只在極少情況下分裂甚至不進(jìn)行分裂，計(jì)數(shù)器的閾值ω的大小將直接影響最終的譯碼性能，因此引入路徑分裂次數(shù)相對(duì)數(shù)的概念[13]，其定義為：

(9)

式中，m為路徑編號(hào)。設(shè)定只有在Sl[i]≥T的情況下才會(huì)刪除路徑，T為閾值。當(dāng)譯碼校驗(yàn)比特時(shí)，若為奇偶校驗(yàn)比特，對(duì)于第1奇偶校驗(yàn)比特，校驗(yàn)并刪除那些錯(cuò)誤的譯碼路徑；對(duì)于第2奇偶校驗(yàn)位，硬判決如下：

(10)

如果譯碼結(jié)果不為0，說(shuō)明譯碼發(fā)生錯(cuò)誤，則根據(jù)式(3)調(diào)整該條路徑的度量值，最后通過(guò)CRC校驗(yàn)列表中幸存的L條路徑。如果只有1條路徑通過(guò)檢測(cè)，將其作為最終輸出；如果有多條路徑通過(guò)了檢測(cè)，選擇其中路徑度量值最大的一條作為最終輸出；如果沒(méi)有路徑通過(guò)檢測(cè)，則直接在所有路徑中選擇路徑度量值最大的一條作為最終輸出。為了進(jìn)一步降低譯碼復(fù)雜度，把一段較長(zhǎng)的CRC比特序列插入第N-K/4+1個(gè)比特之后，將剩余的信息比特連接在該段CRC比特之后，記錄通過(guò)CRC校驗(yàn)后的路徑，之后的信息比特采用逐位譯碼的SC譯碼算法。本文提出的奇偶校驗(yàn)和CRC輔助的ESR-SCL(Parity Check and CRC Aided ESR-SCL, PC-CA-ESR-SCL)譯碼算法的具體流程描述如下。

輸入:信息比特和凍結(jié)比特的索引集合B,信息位碼長(zhǎng)K,列表大小L,閾值T,碼長(zhǎng)N for i=1 to N-K/4+1 do if i∈B then 執(zhí)行SR-SCL譯碼,判斷路徑是否分裂并根據(jù)L和T對(duì)路徑進(jìn)行剪枝; else 執(zhí)行雙奇偶校驗(yàn),刪除沒(méi)有通過(guò)檢測(cè)的候選路徑; end if end for 執(zhí)行CRC校驗(yàn),如果第k條路徑通過(guò)了校驗(yàn)則終止算法,僅保留第k條譯碼路徑;如果沒(méi)有路徑通過(guò)CRC校驗(yàn),保留列表中路徑度量值最大的一條譯碼路徑; for i=N-K/4+2 to N do 執(zhí)行SC譯碼 end for輸出:u ^N1

3 仿真實(shí)驗(yàn)與分析

仿真實(shí)驗(yàn)采用AWGN信道和BPSK調(diào)制，實(shí)驗(yàn)仿真幀數(shù)為105，信噪比的范圍設(shè)定為0.5～2.5 dB，閾值T=7，列表大小L=8。對(duì)于仿真參數(shù)，保證所有仿真的有效碼率是一致的。例如，對(duì)于(512,256)的極化碼，R=0.5，校驗(yàn)位的總數(shù)目固定為24，奇偶校驗(yàn)比特的數(shù)目為P，CRC比特的數(shù)目為C，滿足P+C=24，則K=232，所有算法中的信息比特?cái)?shù)目都是232個(gè)，即有效碼率Re=232/512。

3.1 仿真實(shí)驗(yàn)結(jié)果

設(shè)定碼長(zhǎng)N=256，奇偶校驗(yàn)比特的數(shù)目P分別為8，12，16，對(duì)應(yīng)的CRC比特?cái)?shù)目C分別為16，12，8，組成3種校驗(yàn)比特組合(8，16)，(12，12)，(16，8)，PC-CA-ESR-SCL和CRC輔助的SR-SCL(CA-SR-SCL)算法的譯碼性能如圖3所示，其中EbN0表示信噪比。從圖3可以看出，當(dāng)信噪比較低時(shí)，無(wú)論奇偶校驗(yàn)比特組合和CRC比特的分配方式如何，PC-CA-ESR-SCL算法的譯碼性能都優(yōu)于CA-SR-SCL算法；且在3種組合中，P=16，C=16的組合得到的譯碼性能最好；與P=8，C=16的組合相比較，在誤塊率(Block Error Rate, BLER)為10-2處可以獲得0.2 dB的性能增益，這是因?yàn)樵黾悠媾夹ｒ?yàn)比特的數(shù)目有助于在譯碼過(guò)程中提前檢測(cè)和刪除錯(cuò)誤的譯碼路徑。

圖3 N=256時(shí)，不同校驗(yàn)比特組合下的譯碼性能

設(shè)定奇偶校驗(yàn)位和CRC的組合為P=16，C=8，CA-SR-SCL算法的CRC比特?cái)?shù)為24，保證了2種算法信息比特的數(shù)目相同，碼長(zhǎng)N=256，閾值T分別為4和7時(shí)，PC-CA-ESR-SCL和CA-SR-SCL算法的譯碼性能如圖4所示。從圖4可以看出，和CA-SR-SCL譯碼算法相比，碼長(zhǎng)N=256，T=4的情況下，BLER為10-2時(shí)，PC-CA-ESR-SCL算法可以獲得的性能增益大約為0.25 dB；碼長(zhǎng)N=256，T=7的情況下，BLER為10-2時(shí)的性能增益約為0.21 dB。

圖4 N=256時(shí)，不同譯碼算法的性能

取和圖4實(shí)驗(yàn)相同的參數(shù)，碼長(zhǎng)分別為512和128時(shí)，PC-CA-ESR-SCL和CA-SR-SCL算法的譯碼性能如圖5所示。從圖5可以看出，在相同信噪比和碼長(zhǎng)的情況下，閾值T=7的譯碼性能好于T=4，這是因?yàn)樵龃箝撝禃?huì)在列表中保留更多條路徑，從而更有可能得到正確的譯碼路徑；在相同閾值、相同碼長(zhǎng)和信噪比的情況下，PC-CA-ESR-SCL算法譯碼性能優(yōu)于CA-SR-SCL算法，這是因?yàn)镻C-CA-ESR-SCL算法使用了奇偶校驗(yàn)比特和CRC校驗(yàn)，能及時(shí)刪除錯(cuò)誤的譯碼路徑。

圖5 不同碼長(zhǎng)下，不同算法的譯碼性能對(duì)比

3.2 譯碼復(fù)雜度分析

為了描述譯碼復(fù)雜度，譯碼每個(gè)信息比特的時(shí)延用W表示，假定每個(gè)階段幸存的譯碼路徑數(shù)為L(zhǎng)i，則CA-SR-SCL算法的平均譯碼延遲為WS=W×Li×Nlog2N，PC-CA-ESR-SCL算法的平均譯碼延遲為：

(11)

式中，V表示信息比特的段數(shù)，經(jīng)過(guò)奇偶校驗(yàn)刪除部分錯(cuò)誤路徑，并在第N-K/4+1個(gè)比特之后將譯碼算法替換為SC算法，這意味著有25%的信息比特通過(guò)SC算法譯碼，顯然可以得出Wm

表1 不同算法的平均列表大小

4 結(jié)束語(yǔ)

本文提出一種奇偶校驗(yàn)和循環(huán)冗余校驗(yàn)級(jí)聯(lián)的極化碼編譯碼方案。采用雙奇偶校驗(yàn)和CRC相結(jié)合的方式，在一定程度上提升了譯碼性能；并在某個(gè)特定比特之后將原有算法替換為SC算法，降低了算法的譯碼復(fù)雜度。但是，本文是在AWGN信道下進(jìn)行的仿真實(shí)驗(yàn)，其實(shí)際應(yīng)用價(jià)值有待進(jìn)一步探討，后續(xù)將針對(duì)本文算法在更多通信系統(tǒng)中的應(yīng)用展開(kāi)進(jìn)一步研究。