一種改進的重復比特輔助極化譯碼

張 開，馬秀榮，單云龍，沈園園

(天津理工大學電氣電子工程學院，天津 300384)

1 引言

極化碼(Polar Codes)是Arikan提出的一種新的信道編碼方案。該方案主要是以信道極化(Channel Polarization)現象為基礎設計的。通過嚴格的數學方法可以得證這種方案可以達到二進制離散無記憶信道(Binary-Discrete Memoryless Channel，B-DMC)下的信道容量。譯碼可以采用連續取消(Successive Cancellation，SC)譯碼算法，由于其具有較低的編碼和譯碼復雜度，它已成為普遍使用的一種譯碼算法。當碼長是無限長時，極化碼的性能可以達到理論上的最佳值。當為短碼和中長碼時，在低碼率的情況下，極化碼可以顯示出比低密度奇偶校驗碼(Low Density Parity Check code，LDPC)和turbo碼更好的整體性能，因此第五代移動通信(5th-Generation communication，5G)增強型移動寬帶(Enhanced Mobile Broadband，eMBB)場景的控制信道選擇極化編碼作為編碼方案。

在擴展路徑時，SC算法僅保留一條擴展路徑，這很容易丟失正確的路徑從而譯碼失敗。因此，Ido Tal等人提出了一種可以用廣度優先代替深度優先的算法——連續取消列表(Successive Cancellation List，SCL)算法。SCL算法最多可以保留L條候選路徑，因此正確路徑具有更多的可能性被保留，并且可以擴展到下一層。SCL算法及其派生算法構成了一系列功能強大且不斷改進的算法。當在最終候選路徑中選擇譯碼輸出序列時，循環冗余校驗碼(Cyclic Redundancy Check code，CRC)和極化碼級聯會使譯碼性能更深入提高，即采用CRC輔助的SCL譯碼算法(CRC-Aided SCL，CA-SCL)。但在某些特定的碼率和比特長度下，極化碼的性能仍無法勝過最新的LDPC碼。

為了進一步提高高碼率Polar編碼器的性能，Rowshan M等人提出了重復比特輔助CA-SCL譯碼算法(Repetition-Assisted CA-SCL，RA-CA-SCL)，將在可靠度最低的比特信道中傳輸的信息比特重復傳輸一次，這些重復比特用于在連續的譯碼回合中輔助譯碼。在高碼率下，該算法可獲得更好的譯碼性能。但該算法未分析重復比特長度與CRC比特長度占比對Polar編碼器性能與復雜度的影響，因此本文提出一種改進的重復比特輔助CA-SCL譯碼算法(Improved Repetition-Assisted CA-SCL，IRA-CA-SCL)，在保證校驗比特長度不變的前提下，并滿足CRC校驗有效長度大于信息比特長度條件時，采用CRC比特的最適長度，以使得重復比特盡可能多。該算法在保證平均復雜度的條件下，進一步提升了譯碼性能。

2 極化碼基本原理

構造極化碼需要通過對比特信道先聯合(Channel Combining)后分裂(Channel Splitting)的方式來實現。信道聯合等效于先通過M次復用使獨立比特信道W轉化為矢量信道，然后分裂虛擬信道以獲得N個子信道，其中M=N，以使得獨立比特信道具有相關性。。由信道極化原理易知，當碼長為無限長時，信道分裂后的子信道將出現極化現象。一些子信道的信道容量趨近于“1”，這被稱作無噪聲信道。其它信道容量趨近于“0”的子信道被稱作純噪聲信道，所有子信道中無噪聲信道的占比為I(W)。在進行數據傳輸時，在無噪聲信道上傳輸信息比特，在純噪聲信道上傳輸凍結比特(或稱為固定比特，通常為“0”)，這種傳輸速率理論上可以達到香農極限。然而在實際應用中，編碼是在有限的碼長條件下執行的。因而，在有限長度的極化子信道中，通常選用具有較高可靠度的子信道傳輸信息比特，選用具有較低可靠性的子信道傳輸凍結比特。

2.1 極化碼構造

構造極化碼主要包括3個步驟：①極化子信道選擇；②比特混合；③極化碼編碼。其中子通道的選擇最為重要。由于適用于不同信道的子信道排序算法不同，因此置信序列也不同。目前慣用的子信道可靠性排序方法包括：Arikan提出了針對二進制擦除信道(Binary Erasure Channel，BEC)的巴氏參數方法；Mori等人根據LDPC碼發布的密度演化(Density Evolution，DE)；吳道龍等人提出了一種基于DE的高斯信道高斯近似方法(Density Evolution-Gaussian Approximation，DE-GA)；Schurch指出了極化子信道之間的偏用通序關系，華為發表了一種使用極化權重(PW)且進行參數擴展來計算AWGN信道中子信道可靠性的算法。圖1呈現了當使用巴氏參數方法將碼長N=2用于刪除概率為0.5的BEC時，傳輸信道生成的子信道的對稱信道容量分布。可以從圖1中看出，在進行信道轉換操作(信道聯合和信道分裂)之后，大部分比特子信道的信道容量接近1或0，但還有一些子信道的容量介于0和1之間，無法簡單地區分好壞，這是由于碼長不足和極化不足導致的極化不完全現象。

圖1 極化信道容量

獲得置信序列后，可以根據極化碼的原理對信息比特和凍結比特進行混合，即將信息比特放置在可靠性較高的位置，將其它位置設置為0，來使序列混合。

2.2 極化碼譯碼

(1)

根據式(1)得到的對數似然比進一步判決該比特的取值，判決規則如式(2)

(2)

在進行SCL譯碼算法時，為選出需保留的L條候選路徑，故定義了路徑度量值(Path Metric，PM)

(3)

(4)

(5)

在實際的硬件實現過程中，為簡便處理，可以將式(3)的更新策略替換為

(6)

圖2 SCL譯碼樹與SC譯碼樹

3 改進的重復比特輔助CA-SCL譯碼算法

3.1 CA-SCL算法與RA-CA-SCL算法

3.1.1 CA-SCL算法

CA-SCL算法選用可靠性最高的極化信道來傳輸K個信息比特，選用可靠性略差的極化信道來放置CRC校驗比特。在執行SCL譯碼時，將CRC比特看作信息比特來譯碼，最終保留譯碼后路徑度量值最小且通過CRC校驗的備選路徑。當極化碼為中短碼長時，CA-SCL算法可顯著提高誤碼率性能，但是在高碼率時，極化碼并不優于最新的LDPC碼。

3.1.2 RA-CA-SCL算法

RA-CA-SCL算法通過重復傳輸最易受攻擊的8個比特一次，并與CRC比特一起對信息比特進行了部分保護。在進行RA-CA-SCL譯碼時，首先進行CA-SCL譯碼，如果CRC校驗未通過，則從重復比特索引集合A中提取本次譯碼后的重復比特，并用于凍結易受攻擊的比特。第二次CA-SCL譯碼時采用重復比特的值，這樣可以避免由信道噪聲引起的易受攻擊比特中的錯誤。但是，有些重復比特可能會在第一次譯碼時發生錯誤，所以，如果第二次譯碼時，CRC校驗仍未通過，則僅使用重復比特索引集合A中前二分之一最可靠的重復比特。如果第三次譯碼CRC校驗依然未通過，則僅使用前四分之一最可靠的重復比特。當僅替換一個重復的比特時，該過程將結束。RA-CA-SCL算法較CA-SCL算法，在高碼率下，該算法可獲得更好的譯碼性能，但在校驗比特長度不變的情況下，未進一步分析重復比特長度與CRC比特長度占比對Polar編碼器性能與復雜度的影響。

因此本文提出IRA-CA-SCL算法。本算法結合了CA-SCL算法中的CRC比特輔助譯碼和RA-CA-SCL算法中的重復比特輔助譯碼策略，使得在高碼率有限碼長極化的情況下，其性能達到最優。

3.2 IRA-CA-SCL算法

IRA-CA-SCL算法基于CA-SCL和RA-CA-SCL算法，根據校驗比特長度L，通過CRC選擇器，從3GPP 38.212協議中選擇合適CRC比特長度

L

的生成多項式，進而確定重復比特長度

L

，

L

=

L

+

L

。之后根據比特信道可靠度排序、信息比特、CRC比特長度與重復比特長度完成比特混合。經過信道傳輸后，進行RA-CA-SCL譯碼。具體算法流程圖如圖3所示。

圖3 IRA-CA-SCL算法流程圖

在有限長度的極化碼中，存在很多尚完全極化的比特信道，如圖1所示。在信息比特信道中，將可靠性較低的信道稱為易受攻擊的比特信道，因為它們更容易出錯。易受攻擊比特信道的索引收集在集合

A

ln 中。使用蒙特卡羅模擬對長度為1024且碼率

R

=0

.

8的極化碼進行統計分析，首次譯碼錯誤發生在長度為

L

ln =|

A

ln |=

L

的最易受攻擊比特信道內的概率隨信噪比變化的情況如圖4所示。

圖4 首次譯碼錯誤發生在不同長度最易受攻擊比特信道內的概率

根據圖4可知，當信噪比

SNR

≤3

dB

，首次譯碼錯誤發生在長度

L

ln 為5、8和10的最易受攻擊比特信道的概率均可達47

%

以上且彼此之間相差不大；

L

ln 為16時，概率可達77

%

以上。從非凍結比特集合中選擇由

CRC

部分保護的比特索引集合

A

，

CRC

校驗有效長度

L

=|

A

|滿足

L

≤(2-1-1)-

L

(7)

其中，

L

為

CRC

比特長度。

CRC

未檢測到錯誤的概率

P

滿足

P

=2-

(8)

表1列出了不同CRC比特長度與CRC校驗有效長度

L

和

CRC

未檢測到錯誤的概率

P

之間的關系。

表1 不同CRC比特長度Lcrc對應的有效校驗長度Lprotect與未檢測到錯誤的概率Pud

根據表1可知，當校驗比特長度

L

=16時，最易受攻擊比特信道長度

L

ln 為5、8和10分別對應

CRC

比特長度

L

為11、8和6。由于首次譯碼錯誤發生在長度

L

ln 為5、8和10的最易受攻擊比特信道的概率彼此之間相差不大，所以對于長度為1024且碼率

R

=0

.

8的極化碼，此時信息比特長度

K

=820，為了使得

CRC

比特有效檢驗長度

L

≥820并降低

CRC

比特未檢測到錯誤的概率

P

，采用

CRC

比特長度

L

=11為最佳。故

CRC

選擇器主要滿足以下三個公式

L

≤

L

(9)

K

≤min((2-1-1)-

L

)

(10)

L

+

L

=

L

(11)

CRC選擇器執行流程如圖5所示。

圖5 CRC選擇器

比特混合模塊主要是根據重復比特索引集合

A

、CRC比特索引集合

A

、部分保護比特索引集合

A

與易受攻擊比特索引集合

A

ln 生成CRC比特與重復比特，然后將信息比特、CRC比特與重復比特映射到對應的比特信道上，完成比特混合，具體映射方式如圖6所示。

圖6 比特混合映射方式

由算法流程圖易知，若想順利進行譯碼，則在構造極化碼時需要向信息比特添加重復比特和CRC比特。另外，因為在構造極化碼時，比特之間添加了特殊的結構，譯碼期間的第i個比特與前i-1個比特有關，所以在進行譯碼時，需要留意易受影響比特索引集合的比特信道中信息的傳輸。編譯碼的具體實現方法如下：

步驟1：根據碼率

R

與凈信息比特的長度

K

′，得到校驗比特長度

L

；步驟2：根據校驗比特長度

L

，通過

CRC

選擇器(如圖5)設置

L

，重復比特長度

L

=

L

-

L

；步驟3：生成置信序列。將置信序列前

L

個元素的值賦值給

A

，將置信序列中索引在[

L

+1，

L

+

L

]中且為整數的元素的值賦值給

A

，將置信序列中索引在[

L

+

L

+1，

L

+

L

+

K

′]中且為整數的元素的值賦值給

A

，將置信序列中索引在[

L

+

L

+

K

′-

L

ln +1，

L

+

L

+

K

′]中且為整數的元素的值倒序賦值給

A

ln ；步驟4：將信息比特根據置信序列映射到對應比特信道位置，其中該位置不屬于

A

且不屬于

A

，根據

A

中的元素，找到對應比特信道中的信息，利用該信息生成

CRC

比特。根據圖6所示的比特混合方法可知，重復比特和

CRC

比特被映射到對應的比特信道位置上。 整個數據都作為信息比特發送，信息比特長度變為

K

=

K

′+

L

+

L

。將凍結比特與信息比特混合后進行極化編碼；步驟5：設置

L

=32，初始化一條空路徑；步驟6：根據校驗比特長度

L

，通過

CRC

選擇器(如圖5)設置

L

，利用RA-CA-SCL譯碼算法對接收比特進行譯碼；

步驟7 譯碼后的信息比特需去掉重復比特和CRC比特，以獲得凈信息比特并執行錯誤統計。

4 仿真分析

4.1 仿真參數設置

本文的仿真是在加性高斯白噪聲信道，碼長N=1024，校驗比特長度L=16，CA-SCL算法使用16位CRC比特，RA-CA-SCL算法使用8位重復比特和8位CRC的情況下進行的，IRA-CA-SCL算法通過CRC選擇器來選取適合的CRC位長度。假定這三種算法的凈信息比特數K′相等，則在計算編碼率時，將重復比特和CRC比特記為信息比特，即

R

=(

K

′+

L

)

/N

=0

.

816。

在進行比特信道置信序列構造時，可靠性計算選用巴氏參數方法，并得出置信序列。

本文中涉及的其它參數如表2所示。

表2 仿真參數

4.2 結果分析

4.2.1 性能分析

圖7給出在碼率R=0.816下，CA-SCL算法(L=16)、RA-CA-SCL算法(L=6)、RA-CA-SCL算法(L=8)與本文的IRA-CA-SCL算法(L=11)的性能比較。

圖7 R=0.816時，IRA-CA-SCL與RA-CA-SCL誤碼性能比較

由仿真結果可知，在BER=10時，IRA-CA-SCL較CA-SCL算法性能提升了約0.09dB，IRA-CA-SCL較RA-CA-SCL算法(L=6)性能提升了約0.34dB，IRA-CA-SCL較RA-CA-SCL算法(L=8)性能提升了約0.06dB。

4.2.2 復雜度分析

圖8 IRA-CA-SCL與RA-CA-SCL復雜度對比

由圖8可知，在SNR=6.7dB時，IRA-CA-SCL較CA-SCL算法復雜度增加了約17.4%，IRA-CA-SCL較RA-CA-SCL算法(L=6)復雜度增加了約7.2%，IRA-CA-SCL較RA-CA-SCL算法(L=8)復雜度增加了約4.4%。隨著SNR不斷增大，IRA-CA-SCL的復雜度與CA-SCL的復雜度幾乎一致。

5 結論

針對RA-CA-SCL算法在校驗比特長度不變的情況下，未進一步分析重復比特長度與CRC比特長度占比對Polar編碼器性能與復雜度的影響問題，本文提出IRA-CA-SCL算法。通過提前對CRC進行選擇可實現增加CRC校驗有效長度，減少了CRC未檢測到錯誤的概率。仿真分析表明，在信噪比較低時，IRA-CA-SCL算法與RA-CA-SCL算法相比，可以提高性能，且復雜度增加較少。在信噪比較高時，與RA-CA-SCL算法相比，IRA-CA-SCL算法可以在不改變平均復雜度的情況下，得到更好的性能。