王秀敏,錢方磊,吳卓鋌

(中國計量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

如今是一個信息時代、智能時代,身邊到處是智能家居、智能手機(jī)、電腦等各類智能電子設(shè)備.這些設(shè)備不僅豐富了我們的生活也拉近了人與人,人與社會之間的距離.隨著人們對這種服務(wù)的要求越來越高,科技也被激發(fā)著急速的更新?lián)Q代,對信息傳輸?shù)挠行院涂煽啃蕴岢隽烁叩囊?信道編碼又稱作前向糾錯碼[1](Forward Error Correcting, 簡稱FEC)在整個通信系統(tǒng)中擔(dān)任著重要的角色,通常信道中含有大量的噪聲干擾,這些干擾會讓信息傳輸發(fā)生錯誤,因此非常需要信道編碼來讓系統(tǒng)具有一定的糾錯能力以及抗干擾能力.信道編碼理論[2]是Shannon在1948年發(fā)表的《A Mathematical Theory of Communication》(通信的數(shù)學(xué)理論)一文中提出的,這是現(xiàn)代信息論研究的開端,Shannon本人也被稱為“信息論之父”.隨著對信道理論的深入研究,越來越多優(yōu)秀的信道編碼方法紛紛出現(xiàn),在性能上盡可能地接近Shannon極限,且復(fù)雜度較低易于實現(xiàn),這就是實用好碼.而在這漫長發(fā)展和不停探索的歷史道路上最具有代表意義的就是1962年Robert G. Gallager首次提出的線性分組碼LDPC Codes[3]和1993年Claude Berrou等人提出的Turbo Codes[4]. LDPC碼在提出伊始,受限制于當(dāng)時較弱的信息處理能力并沒有受到大家的關(guān)注.但在三十多年后信息處理能力有了很大的提升,LDPC再次被學(xué)者提出,并給出了優(yōu)秀的譯碼方案.自此,LDPC碼的優(yōu)勢逐漸開始被開發(fā)利用.而Viterbi譯碼算法和網(wǎng)格編碼調(diào)制(Trellis Coded Modulation, TCM)技術(shù)的出現(xiàn)使得卷積碼被廣泛運(yùn)用.另一方面,2008年Erdal Arikan教授首次提出的信道編碼新說Polar Codes[5],為第一個在理論上被證明可以達(dá)到香農(nóng)極限的編碼方法,并且擁有可以實用的線性復(fù)雜度的編譯碼算法,也因此被國際移動通信標(biāo)準(zhǔn)化組織3GPP在5G增強(qiáng)移動寬帶場景的編碼技術(shù)方案中確定為控制信道的編碼方案.

1　LDPC碼和Polar碼級聯(lián)結(jié)構(gòu)研究現(xiàn)狀分析

1.1　LDPC碼和極化碼的研究現(xiàn)狀

首先LDPC碼的編碼方式是通過生成矩陣和信息序列相結(jié)合來進(jìn)行編碼,這種方法使得編碼復(fù)雜度與碼長的平方成正比,隨著碼長的增加這種復(fù)雜度很難被接受.針對編碼復(fù)雜度較高這個問題,學(xué)者們做了一系列的改進(jìn)研究.Mackay提出的下三角的編碼方法[6]充分利用了低密度的特性.Neal提出的基于LU分解的編碼方法[7]將矩陣進(jìn)行LU分解.Richardson提出的近似下三角形的編碼方法[8]則初步解決了高復(fù)雜度以及時延的問題.在編碼過程不斷被簡化的過程中,譯碼也在逐步向著高性能低復(fù)雜度的方向改善.譯碼算法在軟判決方向主要是BP算法,BP算法有著優(yōu)異的性能但是硬件消耗較大難以實現(xiàn).因此學(xué)者紛紛對BP譯碼算法中最為復(fù)雜的非線性計算過程的簡化方法進(jìn)行了研究.Fossorier提出了最小和(Min Sum, MS)算法[9],他用最小值代替了非線性計算,簡化了算法卻降低了性能.Jinhu Chen在最小和算法的基礎(chǔ)上對性能做了改進(jìn),提出了歸一化最小和算法(Normalized Min Sum, NMS)以及偏移最小和算法(Offset Min Sum, OMS)[10-11].學(xué)者對這兩種改進(jìn)的最小和算法中歸一化因子和偏移因子的選取方式也是不斷的創(chuàng)新,文獻(xiàn)[12]對歸一化因子的選取給出了理論上更加可行的方案.Mansour提出了TDMP算法(Turbo Decoding Message Passing)[13]對LDPC碼的發(fā)展也起到了至關(guān)重要的作用.

極化碼的編碼研究主要分為兩個方向,一是選取合適的信息位,二是構(gòu)造優(yōu)秀的生成矩陣. E. Arikan教授在提出極化碼的同時,提出的信息位選取方式為巴氏參數(shù)(Bhattacharyya Parameter)法,Shengmei Zhao[14]對巴氏參數(shù)的構(gòu)造也進(jìn)行了進(jìn)一步的深入研究.另一種信息位選取方式為2009年Mori Ryuhei提出的密度進(jìn)化[15]方法.極化碼譯碼也分兩種主要的研究方向,一個是SC譯碼算法,另一個是BP譯碼算法.同樣,E.Arikan教授在提出極化碼的同時提出并詳盡地描述了SC譯碼算法.2011年Ido Tal等人提出的SCL譯碼算法[16]是對SC譯碼算法在譯碼過程中出現(xiàn)的單向性無法糾錯的弊端的一種改進(jìn),引入L個最優(yōu)路徑作為候選,這極大地改善了SC譯碼算法的性能,但也因此使得復(fù)雜度有所增加.Amin Alamdar-Yazdi等人提出的SSC譯碼算法[17]則通過對節(jié)點進(jìn)行分類計算大大減少了譯碼計算的復(fù)雜度同時也降低了時延.隨著BP算法通過圖論理論引入到極化碼譯碼算法之中,學(xué)者們對極化碼迭代譯碼算法開始了深入的研究,張青雙和劉愛軍提出的改進(jìn)BP譯碼算法[18]降低了誤碼率,Yuan Bo[19]等人提出了MS算法以及SMS(Scaled MS)算法,讓其在譯碼算法的硬件上更容易實現(xiàn).

1.2　基于LDPC和極化碼的級聯(lián)結(jié)構(gòu)的研究現(xiàn)狀分析

1966年Forney提出級聯(lián)碼[20],其基本結(jié)構(gòu)如圖1所示.

圖1　級聯(lián)系統(tǒng)基本結(jié)構(gòu)Figure 1　Concatenated coding system

它有效地通過短分量碼構(gòu)造出了人們更希望的長碼.在LDPC碼和Turbo碼出現(xiàn)之前,級聯(lián)碼常常采用RS(Reed-Solomon)碼作為外碼,用卷積碼作為內(nèi)碼.這種拆分開的編譯碼方式大大縮減了級聯(lián)碼譯碼器的復(fù)雜度.在此之后也有學(xué)者在Forney的基礎(chǔ)上提出了多級級聯(lián)碼[21],是對經(jīng)典級聯(lián)碼的一種推廣,它通過嵌套多個內(nèi)碼,或者說分割多次內(nèi)碼來使多級級聯(lián)碼可以達(dá)到最小漢明距離.級聯(lián)碼在糾正隨機(jī)錯誤和突發(fā)錯誤的混合錯誤方面有著出色的表現(xiàn).

2010年Bakshi M提出了Polar Codes的級聯(lián)結(jié)構(gòu)[22],其中以RS碼為外碼,Polar碼為內(nèi)碼.2011年Eslami A緊跟著提出了用LDPC碼替代RS碼作為外碼的級聯(lián)結(jié)構(gòu)[23].2017年Takumi Murata以及Qingshuang Zhang等人提出了基于CRC與極化碼的級聯(lián)[24-25].國內(nèi)也有許多學(xué)者對極化碼的級聯(lián)做了較深入的研究[26-28].

2　級聯(lián)系統(tǒng)的構(gòu)造方法

級聯(lián)碼的總體結(jié)構(gòu)基本類似,不過在大多數(shù)的級聯(lián)系統(tǒng)中都不可或缺的需要交織器和解交織器,解交織是交織的逆過程,交織過程也可以理解為一種編碼過程.級聯(lián)碼一個重點就是,如果外層編碼后的碼字之間有較多的相關(guān)性緊接著傳輸給內(nèi)碼編碼器得到的最終碼字在經(jīng)過信道傳輸時產(chǎn)生的隨機(jī)錯誤可能會對最終的結(jié)果造成成塊的誤碼.因此,降低外碼編碼后碼字序列間字符的相關(guān)性尤為重要.交織器采用簡單短碼來構(gòu)造隨機(jī)碼長,這樣就可以有效地讓碼字序列間的相關(guān)性得到下降.并且讓編譯碼序列在不經(jīng)過刪除的碼長范圍內(nèi)有著無記憶性.

極化碼的編碼原理是基于信道極化理論,N個相互獨立的信道經(jīng)過信道合并和信道分解后,N個信道呈現(xiàn)了極化現(xiàn)象,一部分信道的信道容量趨近于1而另一部分趨近于0.

這種信道極化現(xiàn)象可以用互信息鏈?zhǔn)椒▌t解釋[8]，如圖2.

圖2　二元傳輸機(jī)制Figure 2　Transmission mechanism basedon GF (2)

在把u1和u2傳輸進(jìn)入信道之前,首先經(jīng)過一個二元域運(yùn)算得到x2=u1⊕u2和x2=u2.互信息如式(1)所示[8]：

(1)

l(u2:y1,y2,u1)=

l(u2:y2)+l(u2:y1,u1|y2)=

l(W)+l(u2:y1,u1|y2)≥l(W).

(2)

結(jié)合式(1)很容易可以得到

(3)

圖3中由兩個以及一個比特翻轉(zhuǎn)構(gòu)造而成.

圖3　信道合并4階示例圖Figure 3　Example diagram of channel combine, N=4

因此,極化碼的本質(zhì)上依然是一種線性分組碼,其生成矩陣[5]可以表示為

(4)

GN=BNF?n.

(5)

由于其特殊的生成矩陣的構(gòu)造方法,可以讓生成矩陣最短環(huán)不小于12(當(dāng)n≥3)[22],極化碼編碼后的碼字間沒有相關(guān)性,因此它是級聯(lián)碼外碼的理想編碼方案.

級聯(lián)碼的編碼是先由極化碼編碼器對信息位進(jìn)行編碼得到中間碼字,再傳入LDPC碼編碼器.這里可以直接傳輸中間碼字給LDPC碼編碼器,也可以根據(jù)常用的LDPC碼標(biāo)準(zhǔn)對中間碼字進(jìn)行補(bǔ)位處理.通常,級聯(lián)方案需要面對外碼編碼后的碼字是否足夠隨機(jī)的問題;而體現(xiàn)其隨機(jī)性的標(biāo)準(zhǔn)就是外碼的最短環(huán),如果外碼編碼后碼字對于信息較為集中,即最短環(huán)較小,則會在級聯(lián)系統(tǒng)加入交織器和解交織器,來降低碼字間信息的關(guān)聯(lián)度.交織過程也可以看作是一個編碼過程,它將經(jīng)過糾錯編碼后的碼字進(jìn)行一定的排列組合,提高原有糾錯編碼的突發(fā)糾錯的能力.本文采用極化碼為外碼LDPC為內(nèi)碼的級聯(lián)方式,充分利用了極化碼生成矩陣最短環(huán)最少為12的特性,不僅為LDPC碼提供了很好的譯碼前提,也在結(jié)構(gòu)上省去了交織解交織的過程.

譯碼過程則是編碼過程的逆過程,利用LDPC碼優(yōu)秀的糾錯性能先對信道傳來的信息進(jìn)行譯碼,接著將軟信息LLR值傳遞給極化碼譯碼器進(jìn)行BP譯碼.理論上極化碼譯碼器的輸入值和輸出值是沒有線性關(guān)系的,通過BP譯碼進(jìn)行雙向迭代不斷修正LLR值,將達(dá)到BP譯碼算法迭代次數(shù)前一次的輸入端的LLR值傳回給LDPC譯碼器.譯碼器之間迭代譯碼將會大大提高譯碼性能.

整體的級聯(lián)碼結(jié)構(gòu)如圖4.文獻(xiàn)[23]則是描述了極化碼與偶校驗碼的一種級聯(lián)方式,其編碼方式采用偶校驗碼為外碼,極化碼作為內(nèi)碼,其級聯(lián)結(jié)構(gòu)如圖5.

圖4　Polar-LDPC級聯(lián)結(jié)構(gòu)Figure 4　Structure of concatenation based on Polar codes and LDPC codes

圖5　極化碼與偶校驗碼級聯(lián)的編譯碼系統(tǒng)Figure 5　Block diagram of encoding and decoding of PCC polar codes

其編碼過程如下:

1)偶校驗編碼;

2)外碼碼字映射將外碼碼字中個比特一次映射到極化碼信息位中,得到極化碼編碼器的輸入信息;

3)極化碼編碼.

其譯碼過程為基于偶校驗輔助的SCL譯碼算法,與經(jīng)典的SCL譯碼算法相比,譯碼校驗比特所根據(jù)的是其所在偶校驗方程中信息比特的判決結(jié)果得到,而非概率.其步驟如下:

1)初始化輸入,i=1保留路徑數(shù)量L;

2)判斷i≤N是否成立,成立則執(zhí)行步驟3,否則執(zhí)行步驟8;

3)判斷是否為凍結(jié)位,是則執(zhí)行步驟4,否則執(zhí)行驟5;

4)設(shè)置當(dāng)前路徑上ui判決值為0,令i=i+1,返回步驟2;

5)判斷是否為凍結(jié)位,是則執(zhí)行步驟6,否則執(zhí)行步驟7;

7)統(tǒng)計當(dāng)前路徑數(shù)量L′并對其進(jìn)行分支擴(kuò)展.當(dāng)前每條路徑在ui處可取值0或1,從而得到條備選路徑,2L′條路徑的度量值分別為該路徑在ui處取值0或1的概率.判斷2L′和L的大小,2L′≤L則保留2L′條路徑;2L′>L則保留條度量值最大的路徑;然后令i=i+1并返回步驟2;

9)結(jié)束譯碼.

另外對LDPC碼和極化碼以及基于二者的級聯(lián)等未來發(fā)展的方向可以做出一定的預(yù)期,隨著5G標(biāo)準(zhǔn)對信道編碼標(biāo)準(zhǔn)的確定,LDPC碼和極化碼的研究必將進(jìn)入新的階段,如何針對極化碼在二進(jìn)制刪除信道和二進(jìn)制對稱信道理論上可以達(dá)到Shannon極限的優(yōu)勢,設(shè)計出更加優(yōu)秀更加簡易的編碼方案依然值得分析研究,相比較LDPC碼歷經(jīng)了幾十年的研究,多項技術(shù)已趨于成熟,相比之下,極化碼像是一顆編碼界的新星,還需要更深層次的探究.隨著多入多出(Multiple-Input Multiple-Output, MIMO)技術(shù)的深入發(fā)掘,碼長可以更長,對譯碼器硬件的實現(xiàn)可行性要求會更高,級聯(lián)的方式會被更多的考慮.因此更多的極化碼和級聯(lián)碼技術(shù)會被引用到其中.

3　發(fā)展趨勢探討

目前各大通信標(biāo)準(zhǔn)制定方對5G標(biāo)準(zhǔn)的制定依然在不斷的起草更新中,LDPC碼和極化碼的研究和應(yīng)用則是信道編碼研究的主題.級聯(lián)等方案依然需要被考慮,其優(yōu)異的特性必然會被發(fā)揮出百分之百的作用.目前對于LDPC-Polar級聯(lián)碼的研究更多是在較高碼率和各種特殊環(huán)境下,因此,尋找較低碼率的級聯(lián)方案和更適合商用的級聯(lián)方案值得去探索.另外,在硬件方面,對復(fù)雜計算的簡化,以及因此產(chǎn)生的修正因子的獲取方案將會是而且一直會是研究的熱點.