王 瓊，王 倫，羅亞潔

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

0 引 言

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

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

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

1 極化碼基本原理

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

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

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

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

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

1.2 極化碼的譯碼

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

(1)

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

(2)

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

(3)

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

2 速率兼容極化碼

2.1 2種打孔模式

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

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

2.2 低復(fù)雜度速率匹配方案

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

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

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

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

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

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

Step2通過計(jì)算單元計(jì)算交織向量Π和實(shí)際用于編碼的置信序列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令打孔比特?cái)?shù)NP=N-M。取Π中前NP個(gè)數(shù)(C0模式)或后NP個(gè)數(shù)(C1模式)作為打孔的比特位置索引PI，那么信息比特索引A取I-PI中可靠度最高的K個(gè)位置，并進(jìn)一步得到I′。而置信序列I′可定義為I′={xi}N，xi∈{0,1}，當(dāng)且僅當(dāng)i∈A時(shí)xi=1。

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

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

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

3 仿真性能和復(fù)雜度分析

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

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

表1 仿真參數(shù)

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

圖6 R=1/4時(shí)的誤塊性能對(duì)比Fig.6 Comparison of BLER performance at R=1/4

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

4 結(jié)束語

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