LDPC-CRC-極化碼級聯碼及其比特翻轉譯碼算法

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

(1. 東南大學 移動通信國家重點實驗室， 江蘇 南京 210096；2. 網絡通信與安全紫金山實驗室， 江蘇 南京 211100)

0 引言

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

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

除了對譯碼算法進行改進，也有一些針對極化碼的編碼做出的嘗試[11-13]。文獻[11]首先提出通過利用LDPC碼作為外碼保護極化碼中間信道(Intermediate Channel, IC)中傳輸的比特以獲得更好的BLER性能。

本文提出了一個改進的LDPC-極化碼比特翻轉譯碼算法，通過每次對關鍵集合內的比特進行比特翻轉，在給定的翻轉次數下，性能較LDPC-極化碼的置信傳播譯碼算法有了極大的提升。通過構造LDPC-CRC-極化碼的三級級聯碼，在比特翻轉譯碼算法下的BLER性能得到了進一步的提升。

1 預備知識

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

BP譯碼算法依賴于極化碼編碼所形成的因子圖。對于碼長N=2n的極化碼，它的因子圖是由n+1階段的N×(n+1)個節(jié)點組成。當N=8時，極化碼的BP因子圖如圖1所示。因子圖中每個階段包含N/2個如圖2所示的基本處理單元(Processing Element, PE)進行信息計算，每個節(jié)點將其對數似然比(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-極化碼級聯碼

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

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

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

1.3 關鍵集合與比特翻轉算法

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

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

2 改進的LDPC-極化碼比特翻轉譯碼算法

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

2.1 中間信道的選取

在LDPC-極化碼級聯碼中，使用LDPC對中間信道傳輸的信息比特進行額外保護。選擇一部分信息比特進行LDPC編碼，將經過編碼的LDPC碼字送入中間信道傳輸，將未編碼的信息比特送入極化碼的“好信道”傳輸。因此，需要選擇易錯的信道作為被保護的中間信道。

文獻[11]中選擇巴氏參數值δ1

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

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

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

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

2.2 聯合因子圖BP算法早停機制

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

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

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

2.3 比特翻轉譯碼算法

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

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

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

3 LDPC-CRC-極化碼三級級聯碼

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

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

信息比特首先經過LDPC編碼，CRC編碼，極化碼編碼，然后將得到的編碼碼字送入信道，信號接收端通過聯合BP比特翻轉譯碼算法進行譯碼。

3.1 LDPC-CRC-極化碼的編碼

碼長為N，信息比特數為K的級聯碼編碼過程如圖7所示，編碼步驟為：

圖7 LDPC-CRC-極化碼三級級聯碼編碼Fig.7 Encoding of concatenated LDPC-CRC-Polar codes

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

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

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

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

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

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

4 仿真結果

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

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

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

根據圖8可以看出，文中提出的改進的LDPC-極化碼比特加強譯碼算法的BLER性能優(yōu)于文獻[13]中BP譯碼算法下的中間信道LDPC-極化碼，例如，在BLER=10-4處的P(2048,1024+32)，比BP譯碼算法下的中間信道的LDPC-極化碼有0.3 dB的增益。但是由于缺少了CRC優(yōu)秀的糾錯性能，其BLER性能不如文獻[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-極化碼三級級聯碼P(2048,1024+32+24)在比特翻轉譯碼算法下擁有極其優(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性能，本級聯碼在比特翻轉譯碼算法下有較低的平均譯碼迭代次數。從圖9可以看出，在BP譯碼器的最大迭代次數都設為100的情況下，在中高信噪比區(qū)間，本文提出的2種基于比特翻轉譯碼算法的級聯碼P(2048,1024+32)和P(2048,1024+32+24)平均迭代次數相近，且都比文獻[10]中提出的極化碼的CS-1譯碼算法的平均迭代次數要低很多。

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

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

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

5 結論

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