一種改進(jìn)的重復(fù)比特輔助極化譯碼

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

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

1 引言

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

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

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

2 極化碼基本原理

構(gòu)造極化碼需要通過對(duì)比特信道先聯(lián)合(Channel Combining)后分裂(Channel Splitting)的方式來實(shí)現(xiàn)。信道聯(lián)合等效于先通過M次復(fù)用使獨(dú)立比特信道W轉(zhuǎn)化為矢量信道，然后分裂虛擬信道以獲得N個(gè)子信道，其中M=N，以使得獨(dú)立比特信道具有相關(guān)性。。由信道極化原理易知，當(dāng)碼長為無限長時(shí)，信道分裂后的子信道將出現(xiàn)極化現(xiàn)象。一些子信道的信道容量趨近于“1”，這被稱作無噪聲信道。其它信道容量趨近于“0”的子信道被稱作純?cè)肼曅诺?，所有子信道中無噪聲信道的占比為I(W)。在進(jìn)行數(shù)據(jù)傳輸時(shí)，在無噪聲信道上傳輸信息比特，在純?cè)肼曅诺郎蟼鬏攦鼋Y(jié)比特(或稱為固定比特，通常為“0”)，這種傳輸速率理論上可以達(dá)到香農(nóng)極限。然而在實(shí)際應(yīng)用中，編碼是在有限的碼長條件下執(zhí)行的。因而，在有限長度的極化子信道中，通常選用具有較高可靠度的子信道傳輸信息比特，選用具有較低可靠性的子信道傳輸凍結(jié)比特。

2.1 極化碼構(gòu)造

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

圖1 極化信道容量

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

2.2 極化碼譯碼

(1)

根據(jù)式(1)得到的對(duì)數(shù)似然比進(jìn)一步判決該比特的取值，判決規(guī)則如式(2)

(2)

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

(3)

(4)

(5)

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

(6)

圖2 SCL譯碼樹與SC譯碼樹

3 改進(jìn)的重復(fù)比特輔助CA-SCL譯碼算法

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

3.1.1 CA-SCL算法

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

3.1.2 RA-CA-SCL算法

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

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

3.2 IRA-CA-SCL算法

IRA-CA-SCL算法基于CA-SCL和RA-CA-SCL算法，根據(jù)校驗(yàn)比特長度L，通過CRC選擇器，從3GPP 38.212協(xié)議中選擇合適CRC比特長度

L

的生成多項(xiàng)式，進(jìn)而確定重復(fù)比特長度

L

，

L

=

L

+

L

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

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

在有限長度的極化碼中，存在很多尚完全極化的比特信道，如圖1所示。在信息比特信道中，將可靠性較低的信道稱為易受攻擊的比特信道，因?yàn)樗鼈兏菀壮鲥e(cuò)。易受攻擊比特信道的索引收集在集合

A

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

R

=0

.

8的極化碼進(jìn)行統(tǒng)計(jì)分析，首次譯碼錯(cuò)誤發(fā)生在長度為

L

ln =|

A

ln |=

L

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

圖4 首次譯碼錯(cuò)誤發(fā)生在不同長度最易受攻擊比特信道內(nèi)的概率

根據(jù)圖4可知，當(dāng)信噪比

SNR

≤3

dB

，首次譯碼錯(cuò)誤發(fā)生在長度

L

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

%

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

L

ln 為16時(shí)，概率可達(dá)77

%

以上。從非凍結(jié)比特集合中選擇由

CRC

部分保護(hù)的比特索引集合

A

，

CRC

校驗(yàn)有效長度

L

=|

A

|滿足

L

≤(2-1-1)-

L

(7)

其中，

L

為

CRC

比特長度。

CRC

未檢測到錯(cuò)誤的概率

P

滿足

P

=2-

(8)

表1列出了不同CRC比特長度與CRC校驗(yàn)有效長度

L

和

CRC

未檢測到錯(cuò)誤的概率

P

之間的關(guān)系。

表1 不同CRC比特長度Lcrc對(duì)應(yīng)的有效校驗(yàn)長度Lprotect與未檢測到錯(cuò)誤的概率Pud

根據(jù)表1可知，當(dāng)校驗(yàn)比特長度

L

=16時(shí)，最易受攻擊比特信道長度

L

ln 為5、8和10分別對(duì)應(yīng)

CRC

比特長度

L

為11、8和6。由于首次譯碼錯(cuò)誤發(fā)生在長度

L

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

R

=0

.

8的極化碼，此時(shí)信息比特長度

K

=820，為了使得

CRC

比特有效檢驗(yàn)長度

L

≥820并降低

CRC

比特未檢測到錯(cuò)誤的概率

P

，采用

CRC

比特長度

L

=11為最佳。故

CRC

選擇器主要滿足以下三個(gè)公式

L

≤

L

(9)

K

≤min((2-1-1)-

L

)

(10)

L

+

L

=

L

(11)

CRC選擇器執(zhí)行流程如圖5所示。

圖5 CRC選擇器

比特混合模塊主要是根據(jù)重復(fù)比特索引集合

A

、CRC比特索引集合

A

、部分保護(hù)比特索引集合

A

與易受攻擊比特索引集合

A

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

圖6 比特混合映射方式

由算法流程圖易知，若想順利進(jìn)行譯碼，則在構(gòu)造極化碼時(shí)需要向信息比特添加重復(fù)比特和CRC比特。另外，因?yàn)樵跇?gòu)造極化碼時(shí)，比特之間添加了特殊的結(jié)構(gòu)，譯碼期間的第i個(gè)比特與前i-1個(gè)比特有關(guān)，所以在進(jìn)行譯碼時(shí)，需要留意易受影響比特索引集合的比特信道中信息的傳輸。編譯碼的具體實(shí)現(xiàn)方法如下：

步驟1：根據(jù)碼率

R

與凈信息比特的長度

K

′，得到校驗(yàn)比特長度

L

；步驟2：根據(jù)校驗(yàn)比特長度

L

，通過

CRC

選擇器(如圖5)設(shè)置

L

，重復(fù)比特長度

L

=

L

-

L

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

L

個(gè)元素的值賦值給

A

，將置信序列中索引在[

L

+1，

L

+

L

]中且為整數(shù)的元素的值賦值給

A

，將置信序列中索引在[

L

+

L

+1，

L

+

L

+

K

′]中且為整數(shù)的元素的值賦值給

A

，將置信序列中索引在[

L

+

L

+

K

′-

L

ln +1，

L

+

L

+

K

′]中且為整數(shù)的元素的值倒序賦值給

A

ln ；步驟4：將信息比特根據(jù)置信序列映射到對(duì)應(yīng)比特信道位置，其中該位置不屬于

A

且不屬于

A

，根據(jù)

A

中的元素，找到對(duì)應(yīng)比特信道中的信息，利用該信息生成

CRC

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

CRC

比特被映射到對(duì)應(yīng)的比特信道位置上。 整個(gè)數(shù)據(jù)都作為信息比特發(fā)送，信息比特長度變?yōu)?p>K

=

K

′+

L

+

L

。將凍結(jié)比特與信息比特混合后進(jìn)行極化編碼；步驟5：設(shè)置

L

=32，初始化一條空路徑；步驟6：根據(jù)校驗(yàn)比特長度

L

，通過

CRC

選擇器(如圖5)設(shè)置

L

，利用RA-CA-SCL譯碼算法對(duì)接收比特進(jìn)行譯碼；

步驟7 譯碼后的信息比特需去掉重復(fù)比特和CRC比特，以獲得凈信息比特并執(zhí)行錯(cuò)誤統(tǒng)計(jì)。

4 仿真分析

4.1 仿真參數(shù)設(shè)置

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

R

=(

K

′+

L

)

/N

=0

.

816。

在進(jìn)行比特信道置信序列構(gòu)造時(shí)，可靠性計(jì)算選用巴氏參數(shù)方法，并得出置信序列。

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

表2 仿真參數(shù)

4.2 結(jié)果分析

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時(shí)，IRA-CA-SCL與RA-CA-SCL誤碼性能比較

由仿真結(jié)果可知，在BER=10時(shí)，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 復(fù)雜度分析

圖8 IRA-CA-SCL與RA-CA-SCL復(fù)雜度對(duì)比

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

5 結(jié)論

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