一種低時延的極化碼設計方法

黃志亮 張施怡 周水紅

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

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

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

1 準備工作

1.1 極化碼

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

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

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

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

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

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

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

1.3 給定的極化碼在MSC譯碼下的時延評估

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

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

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

2 提出的方法

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

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

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

輸入：一個底層的B-DM信道，碼長N和碼率R。

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

步驟1 用文獻[3]的方法計算N個位信道的誤碼率和將這N個位信道按照升序排序。令n表示升序的映射關系。

步驟2 選擇一個小集合S。對于1

步驟3 產(chǎn)生個信息位集合。對于，產(chǎn)生一個S的l-組合數(shù)并將它表示為Ei。那么可以將看成碼長為N、碼率為R的極化碼的信息位集合。總共有個S的l-組合數(shù)。因此有個信息位集合。

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

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

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

3 仿真結果

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

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

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

4 總結

本文提出了一種極化碼在MSC譯碼算法下的差錯性能與譯碼時延之間達到折衷的方法。引入了δ控制這種折衷。對于碼長為256、碼率為1/2的碼，仿真結果表明當δ=0.02時，所提方法達到了8.5%的時延降低，并且有著可忽略的性能損失。而且，通過調整δ，控制差錯性能與譯碼時延間的權衡是容易的。

參考文獻（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