LDPC-CRC-極化碼級聯(lián)碼及其比特翻轉(zhuǎn)譯碼算法

尹 超，潘志文,2，劉 楠，尤肖虎,2

(1. 東南大學(xué) 移動通信國家重點(diǎn)實(shí)驗(yàn)室， 江蘇 南京 210096；2. 網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室， 江蘇 南京 211100)

0 引言

極化碼[1]是唯一一種被理論證明在二進(jìn)制輸入無記憶對稱信道(Binary Input Discrete Memoryless Symmetric Channel, BI-DMSC)下達(dá)到香農(nóng)界的編碼方式[2]。然而，有限碼長下，極化碼在串行抵消(Successive Cancellation, SC)譯碼算法下的誤碼率性能不如低密度奇偶校驗(yàn)(Low-Density Parity Check, LDPC)碼[3]和Turbo碼[4]。

串行抵消列表[5](Succesive Cancellation List, SCL)譯碼器和串行抵消翻轉(zhuǎn)[6](Succesive Cancellation Flip, SCF)譯碼器都是在SC譯碼器基礎(chǔ)上的改進(jìn)，它們都表現(xiàn)出極好的誤塊率(Block Error Rate, BLER)性能。與循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check, CRC)碼級聯(lián)后，極化碼的譯碼性能超越了LDPC碼。由于SCL算法有很長的譯碼時延[7]，置信傳播(Belief Propagation, BP)譯碼算法因其并行計(jì)算的特征受到人們廣泛關(guān)注[8-10]。文獻(xiàn)[9]提出了置信傳播列表(Belief Propagation List, BPL)譯碼算法，選擇多個基于不同因子圖BP譯碼器并行譯碼。置信傳播比特翻轉(zhuǎn)算法[10](Belief Propagation Bit-flip, BPF)借用關(guān)鍵集合(Critical Set)的概念標(biāo)記易錯比特，在BP譯碼算法中引入比特翻轉(zhuǎn)的操作，提升了BLER性能。

除了對譯碼算法進(jìn)行改進(jìn)，也有一些針對極化碼的編碼做出的嘗試[11-13]。文獻(xiàn)[11]首先提出通過利用LDPC碼作為外碼保護(hù)極化碼中間信道(Intermediate Channel, IC)中傳輸?shù)谋忍匾垣@得更好的BLER性能。

本文提出了一個改進(jìn)的LDPC-極化碼比特翻轉(zhuǎn)譯碼算法，通過每次對關(guān)鍵集合內(nèi)的比特進(jìn)行比特翻轉(zhuǎn)，在給定的翻轉(zhuǎn)次數(shù)下，性能較LDPC-極化碼的置信傳播譯碼算法有了極大的提升。通過構(gòu)造LDPC-CRC-極化碼的三級級聯(lián)碼，在比特翻轉(zhuǎn)譯碼算法下的BLER性能得到了進(jìn)一步的提升。

1 預(yù)備知識

1.1 極化碼與置信傳播譯碼算法

BP譯碼算法依賴于極化碼編碼所形成的因子圖。對于碼長N=2n的極化碼，它的因子圖是由n+1階段的N×(n+1)個節(jié)點(diǎn)組成。當(dāng)N=8時，極化碼的BP因子圖如圖1所示。因子圖中每個階段包含N/2個如圖2所示的基本處理單元(Processing Element, PE)進(jìn)行信息計(jì)算，每個節(jié)點(diǎn)將其對數(shù)似然比(Log Likelihood Rate, LLR)信息存儲在N×(n+1)的矩陣L,R中。BP迭代譯碼的過程就是迭代的矩陣L和R之間傳遞信息的過程。

圖1 碼長為8的極化碼BP因子圖Fig.1 Factor graph of polar codes with length N=8

圖2 BP因子圖中的PE示意圖Fig.2 PE in factor graph of polar codes

1.2 LDPC-極化碼級聯(lián)碼

由于極化碼的信道極化現(xiàn)象，比特信道ui,i∈{1,2,...,n}或者變成完全無噪聲(稱其為“好信道”)，要么變得完全噪聲(稱其為“壞信道”)。比特信道ui的質(zhì)量由對應(yīng)的巴氏參數(shù)(Bhattacharyya parameter)Z(ui)度量。Z值越低，對應(yīng)的比特信道錯誤概率越低，這些信道就是好信道，用來傳輸信息比特。另一方面，Z值越高，對應(yīng)的比特信道錯誤概率越高，這些信道就是壞信道，用來傳輸凍結(jié)比特。然而，由于有限碼長極化碼極化現(xiàn)象不充分，導(dǎo)致有一部分比特信道既不是完全無噪聲，又不是完全噪聲，(稱其為“中間信道”)。對于一個信息集合為A 的中間信道，中間信道對應(yīng)信息集合中那些有相對較大Z值的比特信道。文獻(xiàn)[11]提出使用短的LDPC碼作為外碼，對極化碼的中間信道提供額外保護(hù)，內(nèi)碼使用極化碼，以此構(gòu)成了LDPC-極化碼級聯(lián)碼。當(dāng)N=8時，LDPC-極化碼的BP聯(lián)合因子圖如圖3所示。

圖3 級聯(lián)極化碼的聯(lián)合因子圖Fig.3 Joint factor graph of concatenated polar codes

LDPC-極化碼根據(jù)聯(lián)合因子圖進(jìn)行置信傳播譯碼。聯(lián)合因子圖內(nèi)部是一個基于極化碼生成矩陣的極化碼因子圖，在信息傳輸?shù)诫A段1時，將階段1計(jì)算得到的信息傳入LDPC的變量節(jié)點(diǎn)(Variable Node, VN)。隨后根據(jù)LDPC因子圖進(jìn)行迭代次數(shù)為1的BP譯碼，變量節(jié)點(diǎn)將計(jì)算得到的信息再次傳入極化碼的因子圖。當(dāng)信息傳輸?shù)诫A段4時，一次聯(lián)合因子圖的BP譯碼就結(jié)束了。當(dāng)BP迭代次數(shù)達(dá)到設(shè)定好的最大迭代次數(shù)時，根據(jù)對信息集合A中比特信道的LLR做比特判決，得到信息比特ui,i∈{1,2,...,n}估計(jì)值。

1.3 關(guān)鍵集合與比特翻轉(zhuǎn)算法

極化碼的結(jié)構(gòu)可以表示為一顆二叉樹，其葉節(jié)點(diǎn)指向極化碼的信息比特和凍結(jié)比特的集合。在二叉樹表示法中，葉節(jié)點(diǎn)全是信息比特的節(jié)點(diǎn)被稱為Rate-1節(jié)點(diǎn)[14]。Rate-1節(jié)點(diǎn)中第一個比特的索引構(gòu)成了關(guān)鍵集合[15](Critical Sets, CS)。例如，對于極化碼P(32,16)，碼構(gòu)造算法使用高斯近似算法(Gaussian Approximation, GA)，信道信噪比Eb/N0=2.5 dB時，CS={12,14,15,20,22,23,25}。CS中的信息比特被證明是不可靠的。

比特翻轉(zhuǎn)首先被用于SC譯碼算法，隨后文獻(xiàn)[10]將其引用至BP譯碼算法中。文獻(xiàn)[10]用BPF-ω表示一個單次最大翻轉(zhuǎn)比特?cái)?shù)為ω的BPF譯碼過程，T表示構(gòu)造的關(guān)鍵集合CS-ω中元素的個數(shù)(也是比特翻轉(zhuǎn)的最大次數(shù))。當(dāng)ω=1時，CS-1退化為Rate-1節(jié)點(diǎn)中第一個比特的索引構(gòu)成的關(guān)鍵集合CS。在BPF-ω算法中，對于一個待翻轉(zhuǎn)比特，它的先驗(yàn)LLR被指定為+或者-，分別對應(yīng)猜測此信息比特為0或者1。因此，BPF-ω共包括多達(dá)2ω×T次額外的BP譯碼嘗試。BPF極大地提高了極化碼BP譯碼算法的BLER性能，但是，相比于中等列表長度的CA-SCL譯碼器，BPF算法的譯碼性能仍有差距。同時，它的譯碼時延也比BP算法高了很多。

2 改進(jìn)的LDPC-極化碼比特翻轉(zhuǎn)譯碼算法

盡管基于BP譯碼算法的LDPC-極化碼BLER性能相比極化碼在中高信噪比處有0.3 dB左右的提升，但是其BLER性能仍不足以用于現(xiàn)實(shí)的數(shù)據(jù)傳輸。在這部分，提出一種改進(jìn)的LDPC-極化碼比特翻轉(zhuǎn)譯碼算法，在對聯(lián)合因子圖進(jìn)行BP譯碼失敗后，通過對CS中信息比特的翻轉(zhuǎn)，LDPC-極化碼獲得很大的性能提升。

2.1 中間信道的選取

在LDPC-極化碼級聯(lián)碼中，使用LDPC對中間信道傳輸?shù)男畔⒈忍剡M(jìn)行額外保護(hù)。選擇一部分信息比特進(jìn)行LDPC編碼，將經(jīng)過編碼的LDPC碼字送入中間信道傳輸，將未編碼的信息比特送入極化碼的“好信道”傳輸。因此，需要選擇易錯的信道作為被保護(hù)的中間信道。

文獻(xiàn)[11]中選擇巴氏參數(shù)值δ1

中間信道的選取步驟如下：

① 首先將信息集合A中所有元素分成不同的子集Ai,Aj...，其中，同一個子集中的元素對應(yīng)GN中的行有相同的行重w，且wi=wj。

② 在同一個子集Ak內(nèi)，按信道對應(yīng)的Pe(ui)從高到低排列元素。

③ 選擇{Ai,Aj...}中前n1個信道作為中間信道。(n1是中間信道的個數(shù)，也等于選用的LDPC碼字的碼長)。

2.2 聯(lián)合因子圖BP算法早停機(jī)制

對LDPC-極化碼使用聯(lián)合因子圖譯碼時，為了減少平均迭代次數(shù)以及譯碼時延，需要設(shè)定合理的早停機(jī)制。極化碼常見的早停機(jī)制有：CRC判決和G矩陣判決。由于沒有使用CRC級聯(lián)，并且G矩陣判決只能幫助判斷BP譯碼過程是否收斂，無法判斷收斂結(jié)果的正確性。為了進(jìn)行可靠且高效的早停判斷，充分利用LDPC-極化碼級聯(lián)碼的結(jié)構(gòu)特征，結(jié)合LDPC碼的H矩陣和極化碼的G矩陣，進(jìn)行早停判斷的雙重保護(hù)。

聯(lián)合因子圖BP譯碼的流程圖如圖4所示，從圖中可以看出：在LDPC的BP譯碼結(jié)束后開始早停判斷，只有當(dāng)LDPC的H矩陣校驗(yàn)和極化碼的G矩陣校驗(yàn)都成功，才進(jìn)行早停；否則繼續(xù)迭代更新信息，直到達(dá)到最大迭代次數(shù)。

圖4 聯(lián)合因子圖的BP譯碼Fig.4 Flow chart of proposed joint factor graph BP decoding algorithm

2.3 比特翻轉(zhuǎn)譯碼算法

在聯(lián)合因子圖的BP譯碼失敗后，使用比特翻轉(zhuǎn)算法對易錯集合CS中的元素的先驗(yàn)LLR翻轉(zhuǎn)。如圖5所示，此時設(shè)定一個最大迭代次數(shù)m，任意一次翻轉(zhuǎn)成功或者達(dá)到最大迭代次數(shù)都會導(dǎo)致譯碼結(jié)束。

圖5 LDPC-極化碼比特翻轉(zhuǎn)譯碼算法Fig.5 Flow chart of proposed LDPC-Polar codes bit-flipping decoding algorithm

基于比特翻轉(zhuǎn)算法的LDPC-極化碼級聯(lián)碼有很好的譯碼性能，與較低的平均迭代次數(shù)與時延，但是，由于該級聯(lián)結(jié)構(gòu)還有大量的信息比特只是經(jīng)過G矩陣校驗(yàn)，而G矩陣只能驗(yàn)證極化碼是否收斂，無法判斷收斂的正確性。因此，此級聯(lián)碼極易在多次迭代后收斂到錯誤的碼字。在下一部分，通過與CRC構(gòu)成三級級聯(lián)碼來幫助校驗(yàn)所得碼字的正確性。

3 LDPC-CRC-極化碼三級級聯(lián)碼

CA-SCL譯碼器利用CRC優(yōu)秀的糾錯能力獲得了非凡的BLER性能。在這部分，通過將LDPC-極化碼與CRC的級聯(lián)構(gòu)成一個三級串行級聯(lián)碼，通過CRC優(yōu)秀的糾錯性能，結(jié)合上一部分提出的比特翻轉(zhuǎn)譯碼算法，進(jìn)一步提升了BLER性能。LDPC-CRC-極化碼三級級聯(lián)碼的編譯碼流程如圖6所示。

圖6 LDPC-CRC-極化碼的編譯碼流程圖Fig.6 Flow chart of encoding and decoding for LDPC-CRC-Polar codes

信息比特首先經(jīng)過LDPC編碼，CRC編碼，極化碼編碼，然后將得到的編碼碼字送入信道，信號接收端通過聯(lián)合BP比特翻轉(zhuǎn)譯碼算法進(jìn)行譯碼。

3.1 LDPC-CRC-極化碼的編碼

碼長為N，信息比特?cái)?shù)為K的級聯(lián)碼編碼過程如圖7所示，編碼步驟為：

圖7 LDPC-CRC-極化碼三級級聯(lián)碼編碼Fig.7 Encoding of concatenated LDPC-CRC-Polar codes

① 取出K個待編碼信息比特中的前k1個比特，使用(n1,k1) LDPC碼編碼。

② 將n1個LDPC碼字比特輸入中等信道，將剩余K-k1個待編碼信息比特輸入好信道的前K-k1個信道。

③ 將極化碼的信息集合A中已輸入的k2個信息比特(中等信道中所有比特與好信道中前K-k1個信道中的比特)進(jìn)行(k2+r,k2) CRC碼的編碼，得到的r個校驗(yàn)比特輸入好信道中未使用的最后r個信道(r是CRC的校驗(yàn)比特?cái)?shù))。

④ 將極化碼的凍結(jié)集合Ac中的凍結(jié)比特置0，得到極化碼信息比特uN1=(u1,u2,...,uN)。使用(N,k2+r)極化碼對uN1=(u1,u2,...,uN)進(jìn)行編碼，得到了碼長為N的LDPC-CRC-極化碼三級級聯(lián)碼的碼字xN1=(x1,x2,...,xN)。

3.2 LDPC-CRC-極化碼的譯碼算法

使用第2部分提出的改進(jìn)的比特翻轉(zhuǎn)譯碼算法對三級級聯(lián)碼進(jìn)行譯碼。與LDPC-極化碼的譯碼算法區(qū)別在于，在三級級聯(lián)碼中，使用CRC校驗(yàn)與LDPC的H矩陣進(jìn)行早停判斷，這種情況下早停判斷的可靠性得到了極大地提高。

4 仿真結(jié)果

對上文提出的2種級聯(lián)碼的譯碼算法性能進(jìn)行仿真,為了保證各譯碼算法之間對比的公平性，保持碼字的碼長和有效碼率不變，即：N=2 048,K=1 024。

對于LDPC-極化碼級聯(lián)碼P(2048,1024+32)使用(64,32)的Mackay碼作為LDPC外碼，此時k1=32,n1=64，中等信道的個數(shù)為64，好信道的個數(shù)為1 024-32=992。對于LDPC-CRC-極化碼三級級聯(lián)碼P(2048,1024+32+24)，使用生成矩陣為g(x)=x24+x23+x6+x5+x+1的CRC-24碼作為CRC編碼，此時好信道的個數(shù)為1 024-32+24=1 016。極化碼的構(gòu)造算法選擇高斯近似算法，設(shè)計(jì)信噪比為2.5 dB。所有BP譯碼算法的最大迭代次數(shù)都是100。

同時，使用BP譯碼算法下的P(2048,1024)，文獻(xiàn)[13]中提到的中間信道LDPC-極化碼P(2048,1024+32)，文獻(xiàn)[10]中提到的CS-1譯碼算法下的P(2048,1024+24)，CA-SCL譯碼算法[5]下的極化碼P(2048,1024+24)的BLER性能進(jìn)行對照。

根據(jù)圖8可以看出，文中提出的改進(jìn)的LDPC-極化碼比特加強(qiáng)譯碼算法的BLER性能優(yōu)于文獻(xiàn)[13]中BP譯碼算法下的中間信道LDPC-極化碼，例如，在BLER=10-4處的P(2048,1024+32)，比BP譯碼算法下的中間信道的LDPC-極化碼有0.3 dB的增益。但是由于缺少了CRC優(yōu)秀的糾錯性能，其BLER性能不如文獻(xiàn)[10]中提出的基于CS-1譯碼的P(2048,1024+24)。

圖8 P(2048,1024) 各譯碼算法的BLER性能對比Fig.8 BLER performance of different decoding algorithms for P(2048,1024)

然而，文中提出的LDPC-CRC-極化碼三級級聯(lián)碼P(2048,1024+32+24)在比特翻轉(zhuǎn)譯碼算法下?lián)碛袠O其優(yōu)異的性能。在BLER=10-5處的P(2048,1024+32+24)，比基于CS-1譯碼的P(2048,1024+24)有0.7 dB的增益。在中高信噪比區(qū)間，接近基于CA-SCL(L=16)譯碼器的P(2048,1024+24)的BLER性能。

除了優(yōu)異的BLER性能，本級聯(lián)碼在比特翻轉(zhuǎn)譯碼算法下有較低的平均譯碼迭代次數(shù)。從圖9可以看出，在BP譯碼器的最大迭代次數(shù)都設(shè)為100的情況下，在中高信噪比區(qū)間，本文提出的2種基于比特翻轉(zhuǎn)譯碼算法的級聯(lián)碼P(2048,1024+32)和P(2048,1024+32+24)平均迭代次數(shù)相近，且都比文獻(xiàn)[10]中提出的極化碼的CS-1譯碼算法的平均迭代次數(shù)要低很多。

圖9 P(2048,1024)各譯碼算法的平均迭代次數(shù)對比Fig.9 Average numbers of iterations of different decoding algorithm for P(2048,1024)

相較于文獻(xiàn)[10]中的CS-1算法與CA-SCL算法，本算法還有較低的譯碼時延。表1比較了不同算法的譯碼時鐘周期數(shù)，在中高信噪比區(qū)間，LDPC-CRC-極化碼三級級聯(lián)碼P(2048,1024+32+24)在比特翻轉(zhuǎn)譯碼算法下的譯碼時鐘數(shù)與CS-1算法相比，降低了30%～50%。

表1 P(2048,1024)極化碼的譯碼時鐘數(shù)比較Tab.1 Average decoding clock cycles of different decoders for P(2048,1024)

5 結(jié)論

與BPF和BPL等通過增加譯碼復(fù)雜度提高BLER性能的算法不同，本文尋求對極化碼的編碼進(jìn)行改進(jìn)，通過級聯(lián)其他優(yōu)異的碼字，在保持低時延的同時，獲得更優(yōu)異的譯碼性能。在對LDPC-極化碼級聯(lián)碼進(jìn)行比特翻轉(zhuǎn)譯碼時，其BLER性能較BP譯碼算法下的LDPC-極化碼有0.3 dB的增益。在此基礎(chǔ)上，本文首次將LDPC-極化碼與CRC級聯(lián)形成一種LDPC-CRC-極化碼三級級聯(lián)碼，比特翻轉(zhuǎn)譯碼算法下BLER性能比極化碼的CS-1譯碼算法有0.7 dB的增益。盡管級聯(lián)碼帶來不錯的譯碼性能，也不能忽視級聯(lián)碼的劣勢，即額外的編譯碼復(fù)雜度以及額外的硬件開銷。但是，在某些對性能和時延要求較高的場景下，本級聯(lián)碼的優(yōu)勢是突出的。