一種低復雜度速率兼容極化碼

王 瓊，王 倫，羅亞潔

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.移動通信教育部工程研究中心，重慶 400065)

0 引 言

極化碼(polar codes，PC)是Arikan在其開創(chuàng)性的工作[1]中提出的一種在二進制輸入離散無記憶信道(binary-input discrete memoryless channel，B-DMC)下信道容量可達的前向糾錯編碼技術。極化碼不但具有理論最優(yōu)的極限性能，而且已證明其編碼和使用連續(xù)消除算法(successive cancellation，SC)譯碼的復雜度為O(NlbN)，相比目前常用的幾種比較強大的編碼技術，如Turbo碼或低密度奇偶校驗碼(low density parity check codes，LDPC)，有著突破性的進步。正因如此，極化碼已被3GPP采納成為5G eMBB場景下控制信道的編碼技術。

Arikan所描述的極化碼通過一個2×2的核矩陣來構造，這就限制了極化碼的碼長必須為2的冪次，即N=2n,n>0。雖然極化碼的速率還可以根據(jù)選擇凍結比特的數(shù)量來調(diào)整，但碼字長度的限制仍不利于適應實際應用中的不同信道狀態(tài)，極大地限制了極化碼的應用場景。為解決該問題，文獻[2]首次提出了一種基于“停止樹”的速率兼容極化碼，仿真表明，其譯碼性能優(yōu)于隨機打孔但仍不夠理想。緊接著，許多新的極化碼速率匹配方案相繼被發(fā)現(xiàn)，它們大多屬于啟發(fā)式方法，即通過極化碼的某些特點來設計打孔圖樣。Niu[3]等出于對SC類譯碼算法性能的保護提出了一種準均勻打孔(quasi-uniform puncturing，QUP)算法，其誤塊性能超過了同樣打孔長度的Turbo碼。Zhang[4]等發(fā)現(xiàn)對碼字中比特的打孔會使得相同數(shù)量極化子信道的容量退化為零，于是可以通過這種對應關系優(yōu)先選擇可靠性較差的子信道來反向確定打孔圖樣。此外，文獻[5]通過對極化碼生成矩陣的拆分，提出一種十分有效的低維度搜索算法。還有另外一類打孔算法由文獻[6]首次提出，與以上算法有著本質(zhì)的區(qū)別：該方法結合了極化編碼中凍結比特的選擇，首先將所有打孔涉及到的待編碼比特都選作凍結比特。由于凍結比特都是已知的，那么在譯碼端就可以認為被打孔的比特也全部為已知的。也就是說，接收端知道被打孔比特的全部信息。這2類速率匹配方案都有著較好的誤塊性能，而文獻[7]還用距離譜分析了各種打孔算法的性能，并指出QUP算法和文獻[6]方法都可以最大化距離譜。

但是，根據(jù)文獻[2]的部分結論可知，打孔會導致極化子信道不同程度的退化，必定會影響極化子信道的置信度排序。因此，在使用以上算法選擇好打孔圖樣以后，都需要對分離子信道的可靠性在該打孔圖樣下重新評估或?qū)⑺幸玫降拇蚩讏D樣的重排序序列進行離線計算并存儲。不管使用哪種方式，要么具有較高的計算復雜度，要么需要消耗大量的存儲空間，都非常不利于實際應用。本文在解決文獻[8]中存在的問題的基礎上提出了一種新的低復雜度速率兼容極化碼的設計算法。該算法僅使用一個預先存儲的子信道排序序列，并通過一個特殊設計的分段速率匹配交織器和一個環(huán)形緩存器將2類打孔模式用統(tǒng)一的結構實現(xiàn)，使得整個速率匹配處理過程簡單而易于實現(xiàn)；另一方面，本文設計的速率匹配交織器綜合了順序打孔和比特反轉(zhuǎn)打孔等算法的性能優(yōu)勢，在多種傳輸碼長下都有著較好的誤塊性能。

1 極化碼基本原理

圖1 信道聚合與分離過程Fig.1 Processing of channel combining and channel splitting

1.1 極化碼的構造

極化編碼與非系統(tǒng)的線性分組碼十分相似，都使用生成矩陣來編碼。Arikan所述極化碼有著特殊的生成矩陣GN=BNF?n，其中，BN為比特反轉(zhuǎn)交織矩陣，F(xiàn)={1,0;1,1}為極化核矩陣。為使編碼前后的比特對應關系更加明確，以便于打孔方案的設計，本文使用的編碼生成矩陣去掉了比特反轉(zhuǎn)交織矩陣，即GN=F?n。若用(N,K)分別表示極化碼的碼字長度和信息比特長度，那么完整的極化碼編碼可描述為以下3個步驟。

步驟1對分離子信道按置信度排序，得到索引排序序列I。

其中，子信道的置信排序是最為重要的一步。極化碼是一種信道特性碼，不同B-DMC信道極化后的分離子信道的可靠度不完全相同，因此，采用的排序算法也不盡相同。常用的排序算法有適用于二進制刪除信道的巴氏參數(shù)法[1]；可在任何信道下使用但復雜度非常高的密度進化法[9]；適用于高斯信道的高斯近似法[10]以及基于通用偏序的β展開方法[11]。

1.2 極化碼的譯碼

盡管多種譯碼算法都可用于極化碼譯碼，但不可否認的是SC譯碼及其改進算法仍然是目前在復雜度和性能的折中下最為有效的譯碼算法。SC譯碼器的判決方法為

(1)

即首先考慮判決比特是否為凍結比特，然后再考慮對數(shù)似然比的正負情況。而判決函數(shù)hi:YN×Ui-1→U,i∈A定義為

(2)

(2)式中，子信道的對數(shù)似然比定義為

(3)

該似然比的值可以通過文獻[1]中(75)和(76)式的對數(shù)形式遞歸計算。為進一步提高譯碼性能，文獻[12]在SC算法的基礎上結合碼樹的路徑度量提出了SCL(successive cancellation list)算法，Liu[13]等又將循環(huán)冗余校驗用于SCL的輔助譯碼，提出了CA-SCL(CRC assist successive cancellation list)算法，該算法在可接受的復雜度下極大地提高了譯碼性能。

2 速率兼容極化碼

2.1 2種打孔模式

C0模式是最為常見的一種速率匹配方法，文獻[2-5]都采用這種模式。在C0模式下，接收端無法得到被打孔比特的任何信息，可認為這些比特是在一個容量為零的信道中傳輸，那么接收端的對數(shù)似然比為零。打孔后，極化碼的所有子信道的信道容量都將有一定程度的退化，而各子信道退化的程度隨具體打孔圖樣而不同。因此，根據(jù)可靠度選擇的信息比特位置也必將受到打孔影響，故必須考慮打孔圖樣和子信道選擇的聯(lián)合設計。一種有效的方法是在考慮打孔影響下重新使用排序方法估計子信道的可靠性，得到新的置信序列，然后再按照1.1節(jié)的3個步驟進行編碼。該方法可以得到近似最優(yōu)的譯碼性能，但其復雜度為O(NlbN)，大大高于其他信道編碼的速率匹配方案(Turbo碼的打孔復雜度僅為O(N))。

C1打孔模式由文獻[6]首次提出，由于此類打孔模式需要有凍結比特的支持，因此，這是一種僅適用于極化碼等GN陪集碼的特殊打孔模式。在這種模式下，與碼字中打孔比特有相同索引的待編碼比特都將首先被選作凍結比特，而極化碼中凍結比特是收發(fā)雙方協(xié)商好的，因而那些未傳輸?shù)拇蚩妆忍匾捕际且阎?。此時，可以認為打孔比特經(jīng)過一個信道容量為1的信道傳輸，對應的接收對數(shù)似然比設為無窮大(假設凍結比特全取0)。同樣地，C1打孔模式下子信道的信道容量也將發(fā)生變化，重新估計子信道可靠性的方法仍然適用。

2.2 低復雜度速率匹配方案

根據(jù)文獻[4]的部分結論，對碼字的打孔會使得相同數(shù)量的子信道的信道容量退化為零，如果首先選擇這些信道容量為零的子信道傳輸凍結比特，然后再根據(jù)子信道的初始置信序列來選擇剩下的凍結比特位置，就可以在無需重新估計子信道可靠性的同時一定程度上保證譯碼性能。但是，碼字中的打孔位置和退化為零的子信道位置通常并不是對應的，只有在一些特殊的打孔圖樣下才能保證兩者的一致性。此時，我們稱該打孔圖樣滿足一致性條件。判斷打孔圖樣是否滿足一致性條件可由文獻[5]中的算法A來計算。因此，構造一種即滿足一致性條件又可以獲得較好性能的打孔圖樣是設計低復雜度速率兼容極化碼的關鍵。文獻[8]就給出了2種滿足一致性條件的打孔圖樣，分別為C0和C1模式下的比特反轉(zhuǎn)打孔，但其并沒有給出完整的速率匹配方案。盡管文獻[8]將這2種打孔算法分別與QUP算法[3]及文獻[6]提出的算法進行了仿真對比，2種算法在性能上都體現(xiàn)出了一些優(yōu)勢。但其對比條件不夠充分，沒有考慮到不同打孔數(shù)量對打孔性能的影響。

在K=50時，C0模式和C1模式下的誤塊性能分為如圖2和圖3所示，圖2和圖3中的縱坐標為誤塊率在10-3時的信噪比。本文對文獻[8]中所述的2種比特反轉(zhuǎn)打孔以及文獻[3]和文獻[6]分別提出的前、后向順序打孔共4種打孔圖樣下的低復雜度算法進行了仿真對比，仿真基本參數(shù)如表1所示。同時，將同樣打孔圖樣下重新估計子信道可靠度的高復雜度算法作為對應低復雜度算法的最優(yōu)性能參考。仿真結果表明，在C0模式下，隨打孔數(shù)量的增大，前向順序打孔的性能會突然變差，而較少打孔時的性能卻非常接近甚至好于重估計算法的性能。相反，比特反轉(zhuǎn)打孔方法在少量打孔時的性能退化較明顯，隨著打孔數(shù)目增大，該方法和重估計方法的性能差異反而能夠維持在1 dB左右。C1模式下也有相同的結論，只是打孔的方向不同，即少量打孔下，后向順序打孔方式較好，而大量打孔時，反向比特反轉(zhuǎn)打孔方式更優(yōu)。除打孔數(shù)目的影響外，2種打孔模式之間的性能也有差異，C0模式在低碼率下的性能更好(有0.5 dB左右的增益)，而C1模式在高碼率下的性能相較C0模式有1～2 dB的增益。

圖2 K=50時，C0模式下的誤塊性能Fig.2 BLER performance of C0 pattern at K=50

圖3 K=50時，C1模式下的誤塊性能Fig.3 BLER performance of C1 pattern at K=50

由此可以分析：如果將這2種打孔圖樣結合起來，即在少量打孔時采用順序打孔，當打孔數(shù)目增大到一定數(shù)量時再轉(zhuǎn)換為比特反轉(zhuǎn)打孔，這樣的分段打孔圖樣可能會改善打孔數(shù)目對極化碼性能的影響。當然，該打孔圖樣也必須滿足上述一致性條件以避免整體性能的下降。進一步地，如果再能結合2種打孔模式，在低碼率下使用C0模式，而在高碼率下使用C1模式，理論上就能改善該打孔極化碼的整體譯碼性能?；谝陨戏治觯疚奶岢隽艘环N新的速率兼容極化碼的設計算法，如圖4所示，該算法包含以下幾個步驟。

Step1讀取存儲的初始子信道可靠度排序序列I(使用文獻[11]所述的β擴展方法計算)。

Step2通過計算單元計算交織向量Π和實際用于編碼的置信序列I′。

Step2.1交織向量Π由3部分組成，第1部分為長度為(3/8)N的順序序列π1=[1,2,…,(3/8)N]；第2部分為長度為N/4的比特反轉(zhuǎn)排序序列，即π2=[(3/8)N+1,(3/8)N+2,…,(5/8)N]·BN/4。其中，BN/4是比特反轉(zhuǎn)交織矩陣；第3部分也為長度為(3/8)N的順序序列π3=[(5/8)N+1,(5/8)N+2,…,N]。最后得到交織向量Π=[π1,π2,π3]。

Setp2.2令打孔比特數(shù)NP=N-M。取Π中前NP個數(shù)(C0模式)或后NP個數(shù)(C1模式)作為打孔的比特位置索引PI，那么信息比特索引A取I-PI中可靠度最高的K個位置，并進一步得到I′。而置信序列I′可定義為I′={xi}N，xi∈{0,1}，當且僅當i∈A時xi=1。

圖4 低復雜度速率兼容極化碼處理過程Fig.4 Processing of low complexity rate-compatible polar codes

圖5 2種打孔模式的誤塊性能對比Fig.5 Comparison of BLER performance of the two types of puncturing patterns

該打孔算法首先能夠滿足一致性條件并具有結構簡單明確，復雜度低的優(yōu)點。然后，使用速率匹配交織器和虛擬環(huán)形緩存器，使得C0和C1 2種打孔模式可以用同一結構實現(xiàn)，非常適用于硬件設計和實際應用。為了更易理解，下面用一個例子來說明：對于(N,K,M)=(16,4,10)的極化碼，若計算并存儲的初始排序序列為I=[1,2,3,5,9,4,6,7,10,11,13,8,12,14,15,16]。求交織向量時，首先通過比特反轉(zhuǎn)交織得到π2=BitRev([7,8,9,10])=[7,9,8,10]。那么，Π=[1,2,3,4,5,6,7,9,8,10,11,12,13,14,15,16]。對于C0模式，Π中前面6個位置被打掉，即PI={1,2,3,4,5,6}，從I中去掉PI后的剩余位置中選擇可靠性最高的4個位置映射信息比特，即A={12,14,15,16}；對于C1模式，Π中后面6個位置將被去掉，即PI={11,12,13,14,15,16}，從I中選擇信息比特映射位置時同樣應該跳過PI包含的位置索引，得到A={6,7,10,8}。

3 仿真性能和復雜度分析

通過以上對本文低復雜度速率匹配算法的描述可知，本文所構造的速率兼容極化碼的復雜度僅為O(N)。并且，該算法中每個譯碼塊使用的置信序列和交織向量相同，那么計算單元只需要在每次編譯碼之前執(zhí)行一次就可以重復使用。相比在打孔后需要每次對子信道的可靠性重新估計的各類算法(單次計算復雜度為O(NlbN))而言，所提方案在算法時間復雜度方面優(yōu)勢明顯。空間復雜度方面，本文方案只需要多存儲一個交織向量Π，復雜度也是O(N)，這已是任何速率匹配算法都無法避免的最低空間復雜度。

為比較所提算法的性能，圖6和圖7分別在不同碼率、打孔數(shù)量下對本文算法和文獻[3]提出的QUP算法及文獻[6]提出的算法進行了仿真對比。由于文獻[8]并沒有給出完整的方案,且圖2的仿真結果也顯示其在大量打孔下存在較大的性能缺陷，因此，本文不將其作為對比參考。仿真所涉及的參數(shù)如表1所示。

表1 仿真參數(shù)

圖6表明，在R=1/4的低碼率下，不同的打孔數(shù)目導致3種算法的性能有0.2 dB左右的差異。在打孔數(shù)目較多時，QUP算法較優(yōu)，而本文算法和文獻[6]給出的算法的性能基本相當；而少量打孔時，本文算法更有優(yōu)勢，相比QUP有0.1 dB左右的增益，比文獻[6]所提算法提高了約0.2 dB。在R=3/4的高碼率下的仿真結果如圖7所示，圖7顯示無論在大量打孔還是少量打孔下，本文方案得性能都處于QUP和文獻[6]給出的方案之間。而且，在誤塊率為10-3時，本文方案和性能最好的算法的性能差異也僅有不到0.1 dB，基本可以認為此時3種算法性能相當?？梢?，本文算法不僅具有相對較低的復雜度，而且無論在何種碼率、打孔數(shù)量下都有著與重新估計子信道可靠性類高復雜度算法相當?shù)男阅堋?/p>

圖6 R=1/4時的誤塊性能對比Fig.6 Comparison of BLER performance at R=1/4

圖7 R=3/4時的誤塊性能Fig.7 Comparison of BLER performance at R=3/4

4 結束語

本文提出了一種新的低復雜度的速率兼容極化碼的設計算法。該算法下得到的速率匹配結構僅使用一個預存置信序列而無需重新估計子信道可靠性，極大地降低了打孔算法的復雜度。同時，虛擬環(huán)形緩存器的使用，使得C0和C1 2種模式可用同一結構實現(xiàn)，保證了不同碼率下的譯碼性能。而特殊設計的速率匹配交織器汲取了順序打孔和比特反轉(zhuǎn)打孔的優(yōu)勢，避免了大量打孔導致低復雜度打孔算法性能普遍驟降的現(xiàn)象。仿真結果表明，相比QUP以及文獻[6]提出的高復雜度方案，本文構造的低復雜度打孔結構在各種碼率、打孔數(shù)量下都沒有明顯性能損失。綜上所述，本文所提的速率兼容極化碼結構是一種性能和復雜度綜合較優(yōu)的方案，可以很好地滿足實際應用需要。