黃志亮 張施怡 周水紅

摘? 要： 提出一種基于修改的連續(xù)消去（MSC）譯碼算法的極化碼時(shí)延降低方法。在MSC譯碼算法中，可以降低類型-I和類型-II節(jié)點(diǎn)的時(shí)延。通過重新分配信息位，所提出的方法可以獲得一種較好的類型-I和類型-II節(jié)點(diǎn)的分布，在MSC譯碼算法下可以進(jìn)一步降低譯碼時(shí)延。仿真結(jié)果表明，在與原算法的譯碼性能相比可忽略的損失下，由該方法構(gòu)造的極化碼可以達(dá)到8.5%的時(shí)延降低。而且，該方法易于調(diào)整差錯(cuò)性能與譯碼時(shí)延之間的權(quán)衡。

關(guān)鍵詞： 極化碼; 修改的連續(xù)消去譯碼算法; 時(shí)延降低

中圖分類號(hào)：TN911.2? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）05-19-04

Abstract： A latency reduced method is proposed based on Modified Successive Cancellation （MSC） decoder for decoding polar codes. In the MSC decoder， it is shown that latencies for both the rate-zero and the rate-one nodes can be reduced. By redistributing the information bits， the proposed method can obtain a good rate-zero and rate-one nodes distribution， in which decoding latency can be further reduced with MSC decoder. Simulation results show that the new polar code （obtained by the proposed method） achieves 8.5% latency reduction with neglected error performance loss compared with the original polar code. Furthermore， it is easy to adjust the trade-off between the error performance and decoding latency by the proposed method.

Key words： polar code; modified successive cancellation decoder; latency reduction

0 引言

近年來，由于極化碼[1]是第一種漸近性能達(dá)到香農(nóng)限，同時(shí)有著低編譯碼復(fù)雜度，并且能廣泛適用于各種不同信道場(chǎng)景的信道編碼方案，從而引起了人們廣泛的關(guān)注。雖然極化碼有著豐富和完善的理論，但其在實(shí)際應(yīng)用中還存在著一些問題需要解決。由于連續(xù)譯碼的特性，傳統(tǒng)的連續(xù)消去（SC）譯碼產(chǎn)生一個(gè)很高的時(shí)延。文獻(xiàn)[2]表明了一個(gè)類型-II節(jié)點(diǎn)（稍后介紹）的時(shí)延可以降低為一個(gè)類型-I的節(jié)點(diǎn)，從而明顯地降低了譯碼時(shí)延，并且沒有損失譯碼性能。對(duì)于一個(gè)具有固定碼長(zhǎng)的極化碼，類型-I和類型-II節(jié)點(diǎn)的分布是由信息位集合確定的。我們提出一種對(duì)原始信息位集合進(jìn)行微調(diào)的方法，以獲得一種具有較好的類型-I和類型-II節(jié)點(diǎn)的分布的新的信息位集合，進(jìn)而降低譯碼時(shí)延，并且與原始的信息位集合相比，具有較小的性能損失。

1 準(zhǔn)備工作

1.1 極化碼

極化碼將N個(gè)獨(dú)立的二進(jìn)制輸入離散無記憶（B-DM）信道W轉(zhuǎn)化為其他N個(gè)B-DM位信道。構(gòu)造一個(gè)N維的極化碼是等價(jià)于尋找K個(gè)最好的位信道。在文獻(xiàn)[1]中，最好的位信道是有著最小的巴氏參數(shù)，而在文獻(xiàn)[3]中則是在最大似然（ML）譯碼下有著最小的誤碼率。在本文中，使用誤碼率評(píng)估位信道的好壞。然后，一個(gè)極化編碼方案是由三個(gè)參數(shù)唯一確定：碼長(zhǎng)N，碼率R=K/N和一個(gè)由K個(gè)最好的位信道構(gòu)成的信息位集合A。一個(gè)極化編碼方案僅僅傳輸K個(gè)最好的位信道和令N-K個(gè)位是已知的對(duì)于發(fā)送方和接收方。屬于集合A的位稱為信息位，屬于集合[N]＼A（[N]={1，…，N}）的位是稱為凍結(jié)位（在本文中凍結(jié)位是全0）。

1.2 修改的連續(xù)消去譯碼算法的簡(jiǎn)要回顧

對(duì)于m>0，令Tm表示深度為m的完全二叉樹。因此，Tm有N=2m個(gè)葉子。一般方式下，樹的葉子節(jié)點(diǎn)的索引集為[N]，正如圖1（b）中m=3，使用這棵樹可以從頂部到底端執(zhí)行SC譯碼[2]。

給定一個(gè)節(jié)點(diǎn)v∈Tm，令Vv表示根節(jié)點(diǎn)為v的子樹和Iv表示所有葉子節(jié)點(diǎn)是節(jié)點(diǎn)v的后代構(gòu)成的索引集。令A(yù)?[N]是一個(gè)極化碼的信息位集合，如果Iv?A，那么我們稱在Tm上的一個(gè)節(jié)點(diǎn)v是類型-II節(jié)點(diǎn)。類似地，如果，則我們稱在Tm上的一個(gè)，節(jié)點(diǎn)v是類型-I節(jié)點(diǎn)。

給定一個(gè)節(jié)點(diǎn)v，分別用dv、pv、vl和vr表示它的深度、父節(jié)點(diǎn)和左、右節(jié)點(diǎn);見圖1（a）。對(duì)于每個(gè)節(jié)點(diǎn)v，有一個(gè)實(shí)向量αv和一個(gè)長(zhǎng)度為的二進(jìn)制數(shù)向量βv。如圖1（a）所示，當(dāng)激活一個(gè)非葉子節(jié)點(diǎn)v時(shí)，它立即由計(jì)算αv，然后激活vl并立即由αv計(jì)算。在執(zhí)行完節(jié)點(diǎn)的過程后，將傳遞到v。緊接著，激活節(jié)點(diǎn)vr和它立即由αv和計(jì)算。在執(zhí)行完節(jié)點(diǎn)的過程后，將傳遞到v。那么局部譯碼器根據(jù)和計(jì)算。在這點(diǎn)上，在節(jié)點(diǎn)v的局部譯碼器的操作終止。對(duì)于一個(gè)非凍結(jié)葉子節(jié)點(diǎn)，βv是由αv決定;對(duì)于一個(gè)凍結(jié)節(jié)點(diǎn)，βv直接設(shè)置為0。

SC譯碼程序是開始于根節(jié)點(diǎn)vroot，其中實(shí)向量是由接收信道輸出獲得。通過局部譯碼器和對(duì)葉子節(jié)點(diǎn)的處理，向量αv和βv是被計(jì)算對(duì)于每個(gè)節(jié)點(diǎn)v。對(duì)Tm上的葉子節(jié)點(diǎn)執(zhí)行判決。由于篇幅所限，本文不作評(píng)述，可以參考文獻(xiàn)[2]中對(duì)于一棵完全二叉樹上的SC譯碼過程。

在文獻(xiàn)[2]中，引入了一種對(duì)SC譯碼算法的修改，其中簡(jiǎn)化了類型-I和類型-II節(jié)點(diǎn)的操作。對(duì)于一個(gè)類型-I節(jié)點(diǎn)，它可以立即設(shè)置為全零向量而不用激活它的孩子節(jié)點(diǎn)，因?yàn)橐粋€(gè)類型-I節(jié)點(diǎn)的后代都是類型-I節(jié)點(diǎn)。對(duì)于一個(gè)類型-II節(jié)點(diǎn)，可以同時(shí)譯碼其節(jié)點(diǎn)的索引集合Iv里的所有位，而且不需要激活它的孩子節(jié)點(diǎn)。他們稱這種技術(shù)為修改的SC（MSC）譯碼算法。

1.3 給定的極化碼在MSC譯碼下的時(shí)延評(píng)估

對(duì)于極化碼而言，有許多影響時(shí)延計(jì)算的因素。為了使問題更清晰，我們假定：①一旦激活一個(gè)節(jié)點(diǎn)v時(shí)，它需要一個(gè)時(shí)鐘計(jì)算αv同時(shí)使用個(gè)并行處理器;②忽略所有的二進(jìn)制操作。

為了計(jì)算時(shí)延，基于以上的假設(shè)，需要考慮三種情況分別對(duì)應(yīng)三種不同類型的節(jié)點(diǎn)。①對(duì)于一個(gè)類型-I節(jié)點(diǎn)，不需要假設(shè)，因此沒有時(shí)延對(duì)于一個(gè)類型-I節(jié)點(diǎn)和沒有激活這個(gè)節(jié)點(diǎn)的所有后代。②對(duì)于一個(gè)類型-II節(jié)點(diǎn)v，它需要一個(gè)時(shí)鐘計(jì)算αv，并且在索引集合Iv的所有位僅僅需要譯碼二元操作符而不需要激活它的孩子節(jié)點(diǎn)。因此對(duì)于一個(gè)類型-II節(jié)點(diǎn)，它需要1個(gè)時(shí)延（一個(gè)時(shí)鐘），并且將不會(huì)激活所有的后代。③對(duì)于類型-III節(jié)點(diǎn)，它需要1個(gè)時(shí)延（一個(gè)時(shí)鐘）計(jì)算αv，并且將會(huì)連續(xù)激活它的左右孩子節(jié)點(diǎn)。首先，激活左孩子節(jié)點(diǎn)，然后，在處理完左孩子節(jié)點(diǎn)的子樹后激活右孩子節(jié)點(diǎn)。注意根節(jié)點(diǎn)不會(huì)產(chǎn)生時(shí)延。

接下來，我們提供了一個(gè)例子解釋圖2中極化碼的時(shí)延計(jì)算。如圖2（a）所示，信息位集合是A1={6，7，8}，圖2（b）中信息位集合是A2={4，6，8}。通過上述討論，對(duì)應(yīng)信息位集合A1和A2的極化碼的時(shí)延（L）分別是4和8。

2 提出的方法

對(duì)于固定的碼長(zhǎng)N和碼率R，大小為NR的集合[N]的任意子集（為了簡(jiǎn)便假定NR是一個(gè)整數(shù)）可以是一個(gè)信息位集合。每個(gè)信息位集合對(duì)應(yīng)一種極化碼和它們的時(shí)延互不相同。由K個(gè)最好的位信道構(gòu)成的信息位集合A在MSC譯碼算法和所有可能的信息位集合下有最好的糾錯(cuò)性能。我們觀察到，相鄰位信道之間的差異是非常小的。因此，存在一個(gè)信息位集合B與由信息位集合A構(gòu)成的極化碼有類似的糾錯(cuò)性能，而在MSC譯碼算法下前者比后者有較小的時(shí)延是極其可能的。

更準(zhǔn)確的說，基于一個(gè)閾值δ（δ>0），在第NR個(gè)較好的位信道（用誤碼率評(píng)估N個(gè)位信道）截止點(diǎn)附近選擇一個(gè)小集合。然后信息位集合在S中重新分布，并且每一種在集合A＼S中的原始信息位的重新分布對(duì)應(yīng)著一種信息位集合（和A具有相同的元素?cái)?shù)目）。最后，在所有可能的信息位集合中挑選一個(gè)具有最小的時(shí)延的信息位集合。

在數(shù)學(xué)上，令Pe（i）表示第i層位信道的誤碼率。令A(yù)s表示由A＼S中的信息位構(gòu)成的集合。令表示一個(gè)n-元素集的r-組合數(shù)。那么可以將提出的方法描述如下。

輸入：一個(gè)底層的B-DM信道，碼長(zhǎng)N和碼率R。

輸出：一個(gè)有著NR個(gè)元素個(gè)數(shù)的信息位集合B。

步驟1 用文獻(xiàn)[3]的方法計(jì)算N個(gè)位信道的誤碼率和將這N個(gè)位信道按照升序排序。令n表示升序的映射關(guān)系。

步驟2 選擇一個(gè)小集合S。對(duì)于1

步驟3 產(chǎn)生個(gè)信息位集合。對(duì)于，產(chǎn)生一個(gè)S的l-組合數(shù)并將它表示為Ei。那么可以將看成碼長(zhǎng)為N、碼率為R的極化碼的信息位集合?？偣灿袀€(gè)S的l-組合數(shù)。因此有個(gè)信息位集合。

步驟4 利用前一節(jié)的方法計(jì)算所有個(gè)信息集合的時(shí)延和選擇具有最小時(shí)延的集合作為輸出信息位集合B。

一般來說，中元素的個(gè)數(shù)是小的。因此利用我們的方法可以計(jì)算所有生成的個(gè)信息位集合的時(shí)延。

注意原始的信息位集合是由K個(gè)最好的位信道構(gòu)成，而使用提出的方法所產(chǎn)生的信息位集合通常不是由K個(gè)最好的位信道構(gòu)成。隨著δ值的變大，挑選的個(gè)位信道的質(zhì)量變得越差。因此，隨著δ的變大，挑選的信息位集合（對(duì)應(yīng)一種極化碼）的譯碼性能越差。

3 仿真結(jié)果

考慮二進(jìn)制相移鍵控（BPSK）調(diào)制和一個(gè)加性高斯白噪聲（AWGN）信道。特別的，二進(jìn)制碼字c=（c1，…，cN）基于xn=1-2cn映射到一個(gè)傳輸序列x=（x1，…，xN）。在接收端，獲得接收向量y=（y1，…，yN），其中yn=xn+vn，vn是獨(dú)立同分布隨機(jī)變量，它們都滿足均值為0和方差為N0/2的高斯分布。

圖3給出了不同δ的極化碼利用系統(tǒng)編碼方法[4]在MSC譯碼算法下的誤碼率和誤幀率曲線。注意文獻(xiàn)[4]中提出的系統(tǒng)編碼方法比原始的非系統(tǒng)編碼方法有著較優(yōu)的譯碼性能。碼長(zhǎng)N=256，碼率是1/2。利用文獻(xiàn)[3]中的方法評(píng)估N個(gè)位信道。

圖3展示了δ=0.02的極化碼有8.5%（（106-97）/106?8.5%）的時(shí)延降低相比于原始的極化碼（δ=0.0），并且二者在利用系統(tǒng)編碼方法的MSC譯碼算法下具有幾乎相同的譯碼性能。圖 3 也表明了隨著δ的增大，極化碼的時(shí)延逐漸降低，并且譯碼性能損失隨之相應(yīng)的增加。因此通過調(diào)整δ，控制差錯(cuò)性能與譯碼時(shí)延間的權(quán)衡是容易的。

4 總結(jié)

本文提出了一種極化碼在MSC譯碼算法下的差錯(cuò)性能與譯碼時(shí)延之間達(dá)到折衷的方法。引入了δ控制這種折衷。對(duì)于碼長(zhǎng)為256、碼率為1/2的碼，仿真結(jié)果表明當(dāng)δ=0.02時(shí)，所提方法達(dá)到了8.5%的時(shí)延降低，并且有著可忽略的性能損失。而且，通過調(diào)整δ，控制差錯(cuò)性能與譯碼時(shí)延間的權(quán)衡是容易的。

參考文獻(xiàn)（References）：

[1] Arikan E. Channel polarization： a method for constructing?capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Trans. Inform. Theory，2009.55（7）：3051-3073

[2] Alamdar-Yazdi A， Kschischang F R. A simplifiedsuccessive-cancellation decoder for polar codes[J]. IEEE Commun. Lett.，2011.15（12）：1378-1380

[3] Tal I， Vardy A. How to construct polar codes[J]. IEEETrans. Inform. Theory，2013.59（10）：6562-6582

[4] Arikan E. Systematic polar coding[J].IEEE Commun. Lett.，2011.15（8）：860-862