極化碼：主要概念和實用譯碼算法

1、極碼：主要概念和實用譯碼算法摘要 極碼代表一類新興的糾錯碼,他的功率接近一個離散無記憶信道的容量。本文旨在說明其生成與解碼技術(shù)的原則。與傳統(tǒng)能力編碼策略不同,它試圖讓代碼盡可能隨機(jī),極性代碼遵循不同的原理,這也是由香農(nóng)通過創(chuàng)建一個典型共同組提出的。信道極化，一個概念的核心，就是極性代碼，在數(shù)字世界中的馬太效應(yīng)之中被直觀地闡述，對極性編碼的構(gòu)造方法進(jìn)行了詳細(xì)的概述。極性碼蝴蝶結(jié)構(gòu)介紹中，源位相關(guān)，證明SC算法的使用為有效的解碼。從概念和實踐的角度研究了供應(yīng)鏈解碼技術(shù)。最先進(jìn)的解碼算法，如BP和一些廣義的SC解碼，也在一個廣泛的框架下解釋了。仿真結(jié)果表明，極性碼的級聯(lián)與CRC碼的性能優(yōu)于Turbo

2、碼和LDPC碼。一些在實際情況下有前途的研究方向在最后也被討論。摘要1引言1通道極化2編碼和結(jié)構(gòu)4編碼原則4通道選擇6連續(xù)取消解碼7解碼原理8簡單SC譯碼過程9更有力的譯碼算法10提高的SC譯碼過程10CRC-AIDED解碼12置信傳播解碼12ML或MAP解碼12優(yōu)點和缺點13極性碼的缺點14未來的研究方向15結(jié)論16附錄16引言在過去的六年中見證了數(shù)字通信編碼理論的成功。克勞德·香農(nóng)著名的信道編碼定理斷言代碼的存在,信息可以在可靠的噪聲信道上傳輸速率信道容量。三個基本想法背后的信道編碼定理的證明是:(1) .隨機(jī)選擇的代碼(2) .對于大型代碼長度的聯(lián)合漸近等分(AEP)之間的傳輸

3、碼字和接收序列。(3) .最優(yōu)最大似然(ML)解碼或次優(yōu)聯(lián)合典型的解碼。聯(lián)合AEP在證明過程中扮演著重要的角色,在某種意義上,它保證接收到的序列與共同典型傳輸碼字相似,并且共同典型解碼錯誤的概率消失。當(dāng)然隨機(jī)編碼也很重要,但只是為了便于數(shù)學(xué)證明好的代碼的存在。逼近能力與實際編/解碼復(fù)雜度是編碼理論的一個主要挑戰(zhàn)。幸運的是,在過去的二十年里許多“turbo-like”代碼家族,如渦輪碼和低密度奇偶校驗(LDPC)碼,已經(jīng)被發(fā)現(xiàn)實現(xiàn)這一目標(biāo)。關(guān)鍵的問題是如何把實際實現(xiàn)的思想用于信道編碼定理的證明。在LDPC編碼中編碼引入隨機(jī)性窄在渦輪碼或偽隨機(jī)變量之間的連接和檢查節(jié)點?？煽亢陀行У慕獯a,渦輪碼采用

4、迭代BCJR算法(以它的發(fā)明者的名字命名的),而LDPC碼采用信念傳播(BP)算法。這兩個算法執(zhí)行僅略次于ML或最大后驗概率(MAP)算法。鑒于其優(yōu)秀的性能,渦輪碼已經(jīng)在3 gpp WCDMA和LTE標(biāo)準(zhǔn)先后被采用,并且LDPC碼也在IEEE WiMax和802.11 n標(biāo)準(zhǔn)中被采用。然而,并沒有從理論上嚴(yán)格證明的文獻(xiàn)顯示,傳輸通道AEP與這些代碼滿足聯(lián)合。相反,根據(jù)含蓄思想(1)和(3)在香農(nóng)編碼定理中的證明,它一直認(rèn)為獨特的方法來設(shè)計最優(yōu)capacity-achievable代碼是精心結(jié)合偽隨機(jī)編碼和ML / MAP譯碼算法。聯(lián)合AEP和典型的解碼的思想,另一方面,僅視為一種方法被證明了很

5、長一段時間。由于最近Arikan1發(fā)明的極性碼使得形勢發(fā)生變化,它打開了一個新前沿解釋的糾錯編碼來實現(xiàn)任意二進(jìn)制輸入離散無記憶信道的能力(B-DMC)。這些新代碼家庭植根于一個簡潔的效果,叫做通道極化,它可以被看作是數(shù)字世界的馬太效應(yīng)。起初相同的獨立渠道轉(zhuǎn)變成兩種稍微不同的可靠性綜合頻道:好的和壞的通道。通過遞歸地應(yīng)用這種極化變換產(chǎn)生的渠道,綜合頻道將顯示的可靠性顯著差異:“好的變得更好,壞的更糟。”最后,當(dāng)代碼長度足夠大,幾乎所有這些合成渠道將趨向兩個極端:吵鬧的渠道和那些幾乎沒有噪音的渠道。因此,一個自然的編碼策略是在無聲的渠道傳送自由比特(稱為信息比特)而在有噪聲的渠道分配固定的比特(稱

6、為固定比特)?；叵胍幌?聯(lián)合AEP允許我們把所有傳輸碼字和接收序列分成兩組,共同典型組（在樣本互信息是接近的能力）和無共同典型組（由其余可以忽略不計信息組成）。因此,聯(lián)合組典型的碼字可以可靠地通過通道極化產(chǎn)生的無聲的渠道傳輸。顯然,極性編碼是一個建設(shè)性的聯(lián)合AEP的實例。Arikan的開創(chuàng)性論文1提出了一種連續(xù)取消(SC)解碼作為基線算法其復(fù)雜度很低。SC解碼器的極性代碼,我們稱之為解碼器,可以評估和決定一點消息基于極性編碼器的遞歸結(jié)構(gòu)。原則上,SC解碼執(zhí)行一系列交錯循序漸進(jìn)決策的決定在很大程度取決于在前面的步驟中的每一步?jīng)Q策。由于其易受誤差傳播,SC解碼顯然是一種次優(yōu)算法。然而,SC解碼只要

7、代碼長度足夠大其錯誤概率可以任意小,并且編碼速率小于其能力。類似于典型聯(lián)合解碼,這種算法可以漸近獲得最優(yōu)性能,而不需要最優(yōu)ML /MAP算法或任何形式的迭代。除了通道極化的核心概念,解極性代碼其他技術(shù)關(guān)鍵理也包含在這篇文章中,如施工方法,BP譯碼,SC解碼和它的增強(qiáng)算法。本教程文章將引導(dǎo)讀者通過概念解釋這些重要問題,從實際應(yīng)用的角度進(jìn)行一個說明性的闡述。對一些相關(guān)性的進(jìn)一步研究的方向也進(jìn)行了討論。通道極化通道極化可以遞歸實現(xiàn)將多個獨立使用給定的B-DMC轉(zhuǎn)換為一組連續(xù)使用合成二進(jìn)制輸入通道。極化通道由于鏈?zhǔn)椒▌t的使用來擴(kuò)大在源塊與接收到的序列之間的交互信息。B-DMC作為一個例子,一個二進(jìn)制消

8、除信道(BEC)在圖1a,輸入二進(jìn)制比特x和輸出y值0或1。如果這個BEC擦除的概率是0.5,相應(yīng)的能力是I(W)= 1 - 0.5 = 0.5。結(jié)合兩個獨立使用的BEC,如圖1b所示,一個復(fù)合通道(W W)獲得兩個輸入位x1,x2,和兩個輸出位y1,y2。很明顯相關(guān)的能力是2I(W)。通過在兩個獨立的BEC之間使用一個模2運算,一個等價的復(fù)合渠道可以獲得兩個輸入位u1,u2和相同的輸出比特y1,y2。這個通道的能力仍然是2I(W)。通過應(yīng)用交互信息的鏈?zhǔn)椒▌t,這種復(fù)合通道可以分解為兩個綜合頻道:W -頻道(綠線所示，輸入u1和輸出位y1和y2),和W +頻道(粉色線所示,輸入u2和輸出比特u

9、1,y1,y2)。通道和通道分割相結(jié)合之后,兩個獨立的bec可靠性轉(zhuǎn)換為相同的兩個偏振通道和容量之和兩個渠道是不變的,也就是說,+= 2。上面的操作被稱為單級的變換。在1Arikan派生的交互信息中兩個渠道= 2-,=和證明壞通道W -容量小于給定的BEC ,而好的通道W +有一個更大的能力,也就是說,。特別的,在這個例子中BEC的情況下(= 0.5),兩個極化通道的能力分別是= 0.75和= 0.25。此外,四個獨立使用給定BEC的,我們可以不斷應(yīng)用單步變換兩種用法的和,如圖1c所示。在第二階段,四個副本的BEC 分為兩組,每組兩個BEC變成兩個偏振通道和。自從頻道屬于不同的組織是相互獨立的

10、,我們得到兩個獨立副本為每個BEC 或。在階段1中相同的操作可以分別申請這兩個bec。因此通道和(和)來自兩個通道()。在Arikan推導(dǎo)中，我們使用的通道而不是通道，獲得信道和的能力,也就是說,= = 0.0625,= 2- = 0.4375。同樣,頻道和的能力可以分別被認(rèn)為= 0.5625,= 2- = 0.9375。顯然的能力與相比進(jìn)一步減少,而 相對是進(jìn)一步擴(kuò)大。因此兩個渠道相比之下,四個渠道的極化效應(yīng)變得更加顯著。通過同樣的原理可以不斷進(jìn)行偏振轉(zhuǎn)換 獨立使用給定BEC的并且所有的極化通道的能力可以被遞歸地評估。圖1 d說明了進(jìn)化的通道極化編碼長度N = ,其中每個節(jié)點(黑色圓)表示一

11、個極化通道在一定代碼長度,和節(jié)點的縱坐標(biāo)對應(yīng)通道的能力。此外,相鄰的兩個節(jié)點之間的線表示通道極化的演化軌跡。例如,當(dāng)代碼長度隨N = 至  N = ，一個BEC W演變成兩個BEC:和。我們用紅線標(biāo)記好的渠道和藍(lán)線標(biāo)記壞的渠道,如圖1d所示。好通道相對于壞通道能力的優(yōu)勢可以積累并且極化效應(yīng)不斷提高編碼長度增加到N = 。這種現(xiàn)象是一個典型的馬太效應(yīng):好的變得更好,壞的變得更糟。觀察好/壞通道的演化軌跡,我們發(fā)現(xiàn)大部分的極化通道的能力傾向于1(好渠道噪聲小)或0(壞的通道充滿噪音)。同樣,無噪聲通道的誤差概率或嘈雜的渠道趨于0或1。代碼長度N趨于無窮時,馬太效應(yīng)下的極化通道趨于兩個極端

12、(對應(yīng)的能力是0或1)。Arikan利用鞅理論證明了隨機(jī)收斂性質(zhì)的極化通道的能力1。尤其是對BEC在這個例子中,無聲的渠道的比例正好等于對稱能力I(W)= 0.5。直觀地說,在那些沒有噪聲的通道傳輸碼字是完全沒有錯差的。傳輸碼字和接收序列的概率是共同典型之一,如同AEP節(jié)點所示。另一方面,任何隨機(jī)選擇的碼字和接收到的序列共同典型只有一個概率約等于,這對于大型的代碼長度是可以忽略的。這讓我們可以斷言存在一對一的固定傳輸碼字和接收序列之間的映射,這大約的碼字可以可靠地傳輸這些通道。聯(lián)合典型性,在通道極化的行為,構(gòu)成了一個關(guān)鍵步驟的信道編碼定理的證明。作者的最好的知識,這可能是第一個建設(shè)性的例子來實

13、現(xiàn)B-DMC的能力。編碼和結(jié)構(gòu)自從無聲的渠道比嘈雜的通道能力的錯誤概率更高或更低,通道極化現(xiàn)象表明信道編碼的新理論,即選擇無聲的二進(jìn)制信息渠道傳播。因為編碼速率可以通過添加或刪除一個精細(xì)偏振通道調(diào)整,我們幾乎可以不斷改變極性碼的比率。與其他編碼方案相比,這個比率兼容屬性是一個重大優(yōu)勢。此外,與傳統(tǒng)的代碼結(jié)構(gòu)最大化最小漢明間距不同,極性編碼的目的是直接地使極化通道的誤差概率最小化。編碼原則一般來說,主要有三種極性編碼方案:非系統(tǒng)編碼，系統(tǒng)編碼和廣義連接編碼。在原來的極性編碼中、以非系統(tǒng)編碼的形式被使用。給定的代碼長度,N = 1,2,和信息長度K,二進(jìn)制源塊u =(u1,u2、uN)由K位信息位

14、和N - K固定位信息。代碼的碼字x速率可以獲得如下: (1)其中是生成矩陣,BN 是置換矩陣,是F2的第N個克羅內(nèi)克符號,并且被稱為內(nèi)核矩陣。顯然這個編碼過程類似于Walsh-Hadamard變換。今后,我們將使用一個N = 8, K = 4,R = 1/2的極性代碼作為一個例子。在這個非系統(tǒng)性的方案下,比特信息被分配給塊的來源。如圖2所示,當(dāng)固定比特分配給其余的不可靠渠道時，信息比特u4,u6,u7,u8被分配到的極化通道誤差概率越低。每個極化通道與一個特定的行相關(guān)聯(lián)的生成矩陣相關(guān)聯(lián)。固定比特通常取固定值0和被假定被編碼器和解碼器已知。對于非系統(tǒng)性極性代碼,生成矩陣對應(yīng)的信息位的行可以由最

15、低的錯誤概率組成。相比之下,Reed-Muller(RM)碼生成矩陣的相似,但行選擇規(guī)則是基于漢明重量的行。如上1所述,RM規(guī)則信息比特分配導(dǎo)致漸近在SC解碼下不可靠的代碼。在圖2中一個蝴蝶單元可以改變兩個獨立輸入比特(a,b)為兩個相關(guān)的輸出比特,這是由核心矩陣所左右并且與通道極化相適應(yīng)。這個操作還可以遞歸地應(yīng)用于整個碼字,也就是說,一個碼字x在第三階段分為兩個部分,其中每個反過來分裂階段又分為兩部分,這樣繼續(xù)下去,直到在階段1達(dá)到一個單一來源。所以極性編碼過程中N = 8包含一個信息逆轉(zhuǎn)和蝴蝶操作的三個階段。通常,給定一個代碼長度 ,極化變換可以分解成N和每個階段的蝴蝶操作,導(dǎo)致編碼復(fù)雜度

16、為。根據(jù)編碼理論,每個線性分組碼都可以轉(zhuǎn)化為一個等價的系統(tǒng)代碼。然后2系統(tǒng)的介紹了系統(tǒng)極性編碼方案。與非系統(tǒng)編碼不同，信息比特表現(xiàn)為顯然碼字的一部分。與這些信息比特和固定比特在源塊端位,另一位在碼字端可以由一些代數(shù)運算。系統(tǒng)極性編碼的主要優(yōu)勢是,他們是更健壯的對抗在SC解碼錯誤傳播。與原(非系統(tǒng)性)極地代碼相比,系統(tǒng)的極性代碼具有相同的塊錯誤率(BLER),但優(yōu)于前者的比特誤碼率(BER)性能。當(dāng)從廣義連接的框架代碼觀察,極地代碼可以分解為一組外部/內(nèi)部代碼3。即在極地的遞歸結(jié)構(gòu)代碼,第一個l階段可以被視為外碼長度為，剩下的n-l階段內(nèi)部編碼長度。這些外部/內(nèi)部代碼都是極性較小的代碼的代碼長度

17、。由于基于塊ML譯碼是用于外部代碼，SC解碼用于內(nèi)部代碼,錯誤傳播限制在內(nèi)部的內(nèi)部代碼。與SC解碼整個碼字相比,這個解碼策略有利于BLER的性能。通道選擇SC解碼的BLER極性碼的性能上限的錯誤概率信息極化通道1的總和。這樣的一個重要步驟構(gòu)造一個極地代碼,代碼長度N和K位長度信息,從本質(zhì)上講,選擇K最可靠的渠道,這樣BLER上界最小化。因此可靠性計算和通道選擇是碼字構(gòu)造的兩個中心問題。在他的論文1Arikan計算提出了一種遞歸算法基于巴氏參數(shù)的可靠性評價參數(shù)。如果原始B-DMC是 BEC,消除極化通道的概率通過使用這種遞歸算法可以被跟蹤的低復(fù)雜度。同樣,在BEC的情況下相應(yīng)的能力也可以遞歸地計

18、算出來,如圖1所示。復(fù)雜性可以進(jìn)一步簡化為如果使用中間巴氏參數(shù)而不是4。然而,對于渠道除了BEC,計算復(fù)雜性呈指數(shù)級增長的代碼長度和輸入字母的大小。構(gòu)建一個極地代碼在任意對稱B-DMC,森和田中4提出的使用密度進(jìn)化(DE)工具跟蹤的概率密度函數(shù)(PDF)對數(shù)似比率(LLRs)變量和檢查節(jié)點解碼圖像的極地代碼(例如圖3)。LLR PDFs文件執(zhí)行的變量和檢查節(jié)點。DE技術(shù)被廣泛用于設(shè)計LDPC碼,并且同樣適用于極地代碼設(shè)計?；贚LP PDFs的第一階段變量節(jié)點,所有的極化通道的誤差概率可以被獲得。使用相同的參數(shù)作為如此巴氏參數(shù),卷積的數(shù)量級也是。在實際實現(xiàn)中,為了保持一個可接受的水平的復(fù)雜性,

19、LLR pdfs應(yīng)該被量化成q水平。因此,量化密度演化的計算復(fù)雜度是。然而,q的典型值是,這意味著在實際應(yīng)用中的一個巨大的計算負(fù)擔(dān)。積累了多個極化階段的困難進(jìn)一步加劇了量化錯誤。的確,正如4很難找到最佳的實現(xiàn)復(fù)雜度和計算精度之間的權(quán)衡。Tal和Vardy5通過控制量化誤差提出了一種有效的方法來解決這個問題。他們明智地介紹了兩種近似方法,稱為增加和減少量化,來得到每個通道的更低或更高的錯誤概率。兩種方法相關(guān)頻道對于而言轉(zhuǎn)換成一個新的和更小的輸出。然后建筑復(fù)雜性的算法可以被評價為。一個典型的m的值是256,所以它比DE更復(fù)雜。雖然密度函數(shù)的精度可以通過增加產(chǎn)出的字母的大小提高該算法,算法復(fù)雜性也增

20、加。二進(jìn)制輸入加性高斯白噪聲(AWGN)頻道,主要與編碼理論相關(guān),另一種方法3稱為高斯近似(GA)可應(yīng)用于極地規(guī)范的建設(shè)。GA復(fù)雜度低于Tal和Vardy的方法應(yīng)用于二進(jìn)制輸入AWGN信道,但收益率精度幾乎相同。從實用的角度來看GA比其他方法更有吸引力。連續(xù)取消解碼回想一下,蝴蝶在極性編碼器引入源比特之間的相關(guān)性,以便每個編碼比特與給定索引依賴于它的所有指數(shù)較小的前位。這種相關(guān)性在概念上可以視為干涉source-bit域,利用時,會導(dǎo)致一個更好的譯碼性能,從而構(gòu)成了一個基本的中心思想解碼算法,稱為SC解碼。連續(xù)取消引起的“干涉”前位提高可靠性的檢索源位。由于常規(guī)的結(jié)構(gòu),由于極性的常規(guī)結(jié)構(gòu)編碼,

21、SC算法可以描述的框架或代碼樹結(jié)構(gòu)。 (2)解碼原理SC解碼可以看作是一個軟/硬消息傳遞算法的框架極性代碼。框架由n階段和N水平組成。每個階段包括N / 2個蝴蝶單位并且每個單元包含一對檢查和變量節(jié)點。SC解碼器逐步更新消息從而通過順序決定評估。圖3顯示了代碼的框架結(jié)構(gòu)的長度N = 8。硬盤信息傳播的框架是估計比特對應(yīng)變量節(jié)點指定為,i和j表明框架的階段和水平指數(shù),分別,。相對應(yīng)的軟信息比特LLR值表示。在這個例子中源塊在框架左邊的位值,也就是 ，相應(yīng)的軟信息是。讓 位逆轉(zhuǎn)排列后接收信號,相應(yīng)的LLR用。更新和決策規(guī)則可以表示如下。軟信息更新規(guī)則-看到上面的Eq。2,i= 1,2,n,j =

22、1,2,n,是雙曲正切函數(shù),是底層功能?？傊?軟信息在檢查節(jié)點級別指數(shù)滿足是通過使用第一個公式Eq.2更新,這類似于在LDPC碼的校驗節(jié)點計算;而變量節(jié)點的消息是通過更新的第二個方程執(zhí)行的,這需要變量的知識節(jié)點約束和硬消息。硬信息更新規(guī)則- (3)其中模2運算，并且其他符號與Eq.是相同的。總之,在檢查節(jié)點帶有特定級別指數(shù)的硬消息是通過使用第一個公式Eq。3更新的;否則,硬消息通過第二個公式更新消息。決策規(guī)則-在階段1的決策規(guī)則如下:對于一個信息位,如果軟信息,然后,否則;對于固定位,簡單地將其設(shè)置為一個預(yù)先確定的值,例如。在圖3中所示的框架的例子中,SC解碼器執(zhí)行軟信息計算并且從右到左穿過框

23、架;然后計算硬信息,并且在相反的方向傳播。實際上,在第三階段的第一蝴蝶單元(框架頂部),軟信息是通過使用和計算的。此外,作為另一個實例,在階段1的第二個蝴蝶單位(從框架頂部)軟信息和在相關(guān)步驟1和2(以箭頭所示和數(shù)字表示)之后分別發(fā)送到檢查節(jié)點的。步驟3 6之后,軟消息是通過Eq.2獲得。然而,無論多么重要,相應(yīng)的硬消息發(fā)送回檢查節(jié)點，因為位是固定位。然后軟消息是在第7步中通過使用帶有硬消息()和軟信息(和)的Eq.2計算的。相應(yīng)的硬消息s1,4是在步驟8和9中分別被發(fā)送回檢查節(jié)點。在步驟10和11中,硬消息和通過使用Eq.3計算。一個SC譯碼器的直接實現(xiàn)是通過一個一個地激活蝴蝶單位來實現(xiàn)的。

24、但這種調(diào)度順序吞吐性能非常低。通過同時激活多個蝴蝶單元,可以實現(xiàn)更高的處理吞吐量,這在硬件設(shè)計被廣泛關(guān)注。軟消息在一個蝴蝶單元計算可以算作是SC解碼的一個基本操作?？蚣苡梢院麊挝唤M成,整個SC解碼器的時間復(fù)雜度是并且它需要內(nèi)存單元存儲LLR值。簡單SC譯碼過程從實際的觀點出發(fā)，降低譯碼復(fù)雜度是一個重要的問題。簡單連續(xù)消除譯碼器旨在在不影響錯誤性能的情況下減少SC譯碼過程中的冗余計算。根據(jù)先進(jìn)的極化理論的特征，極化碼可以由合同級的編碼樹表現(xiàn)出來，正如圖3b所示。在第三階段由于所有的信道都被極化成兩大類，所以只有兩級保持著。類似地，在其他兩個階段也分別有四級和八級。編碼樹中的所有節(jié)點都分成了三種

25、類型：0-比率節(jié)點、1-比率節(jié)點、R-比率節(jié)點，其中它們的擴(kuò)展分別是全部凍結(jié)位、全部信息位、部分凍結(jié)和信息位。SSC譯碼過程的操作可以總結(jié)如下：對于包括0-比率節(jié)點和1-比率節(jié)點的成分代碼來說，直接經(jīng)過硬消息，或沒有執(zhí)行操作；相反，對于R-比率節(jié)點來說，標(biāo)準(zhǔn)SC譯碼過程的運算被處理。與最初的SC譯碼相比，R-比率節(jié)點的復(fù)雜度比0-比率節(jié)點和1-比率節(jié)點的簡單化減少了大約220倍。更有力的譯碼算法雖然極化碼漸漸地能夠達(dá)到香農(nóng)容量，但在碼長有限的情況下，SC譯碼器的性能仍然不理想。為了提高極化碼的有限長的性能，提出了幾種可選擇的譯碼算法，例如連續(xù)消除列表算法和置信傳播譯碼算法。提高的SC譯碼過程合

26、同階段代碼樹-我們可以使用稱為合同階段編碼樹的統(tǒng)一框架來形容SC譯碼過程和升級算法，例如SCL/SCS譯碼過程。圖4a給出了SC譯碼過程中合同階段編碼樹的例子，其中包括八級，每一級都與一塊塊的格子框架有關(guān)，這種格子框架被彩色破折線的盒子圈出來了。在這個代碼樹中，除了葉子節(jié)點和凍結(jié)節(jié)點，每個節(jié)點都有兩個子孩子，對應(yīng)的分叉分別標(biāo)著0和1。包括從根節(jié)點到其中一個葉子節(jié)點的分支序列的譯碼路徑和相應(yīng)的可靠性可以用APP來測量。圖4中每個節(jié)點相鄰的數(shù)字提供了從根節(jié)點到該節(jié)點的譯碼路徑的APP度量標(biāo)準(zhǔn)。黑色的圈代表該節(jié)點被訪問，灰色的圈代表在訪問過程中未被訪問的節(jié)點?；貞浺幌率菍?yīng)的在i階段和j級的變量節(jié)點

27、的位估計，這些位估計被一塊塊地格子覆蓋，同時與確定的譯碼路徑有關(guān)。與等式2類似，APP度量標(biāo)準(zhǔn)也可以由一種遞歸方式計算出來。根據(jù)實際觀點，對數(shù)APP度量標(biāo)準(zhǔn)比其他的形式在數(shù)字穩(wěn)定性方面更強(qiáng)，具體的細(xì)節(jié)在7中闡述。SCL和SCS-極化碼的SC譯碼過程與合同級代碼樹相比，被稱為渴望搜索算法。在與確定級的信息位結(jié)合的這兩種分支中，概率被用來進(jìn)一步處理。不論何時一個位被錯誤地確定，在以后的譯碼過程中糾正錯誤將成為不可能。圖4a中的紅色黑色的分支解釋了SC譯碼路徑“00000011”。顯然由于級與級的決定策略，這種譯碼路徑并不是最佳的。SC的一個升級版本，在8中提出的SCL譯碼器通過級搜索到了代碼樹，與

28、SC譯碼器具有相同的方式。但是，不像SC譯碼器，經(jīng)過每一級的處理后僅有一種路徑被保留，SCL被稱作是廣度優(yōu)先算法，并且允許最大L個候選路徑進(jìn)一步探索。在與信息位有關(guān)的每一級中，SCL算法通過在每個候選路徑上附加位0或1使候選路徑的數(shù)量加倍。通過最佳度量標(biāo)準(zhǔn)挑選出了L條最佳候選路徑并將它們存儲在列表中。圖4b給出了列表大小L = 2的SCL譯碼算法例子。在每一級中，兩條候選路徑（藍(lán)邊和紅黑邊）被保留，最可靠路徑“000100000”被發(fā)現(xiàn)。9中提到的SCS譯碼器使用了一種順序堆棧來保存候選路徑，通過在堆棧中搜索最佳路徑試圖發(fā)現(xiàn)最佳估計方法。不論何時堆棧中的有著最大路徑度量標(biāo)準(zhǔn)的頂層路徑到達(dá)一個葉

29、子節(jié)點，譯碼過程會停止并且輸出路徑。不像SCL的候選路徑，總是有相同的長度，在SCS算法堆棧中的候選路徑具有不同的長度。圖4c給出了關(guān)于SCS譯碼過程的例子。與SCL譯碼過程相比較，SCS算法同樣可以發(fā)現(xiàn)相同的最佳路徑，但是由于兩種候選路徑的長度不同，路徑擴(kuò)展的數(shù)量會減少。實施方面,spaceefficient結(jié)構(gòu)建議8為了實施SC解碼器spaceefficient結(jié)構(gòu)在8中被建議以及時間和空間復(fù)雜性分別是O(NlogN)和O(N)。SCL解碼器的直接實現(xiàn)需要計算指令。在8中一個所謂的“懶復(fù)制”技術(shù)基于候選路徑之間的內(nèi)存共享結(jié)構(gòu)為了減少冗余復(fù)制操作而被提出。因此,SCL解碼器可以通過時間復(fù)雜度

30、O(LNlogN)實現(xiàn)。類似于SC和SCL解碼器,這些特性也可以應(yīng)用在實現(xiàn)SCS解碼器。SCS的實際計算,假設(shè)棧的深度D是足夠大的,比SCL在中度或工作時高信噪比(SNR)變的更少?；旌辖獯a-SCL和SCS結(jié)合的原則,在10中提出了一種新的解碼算法稱為連續(xù)取消混合(SCH)。這個算法可以提供一個靈活的配置,其時間和空間復(fù)雜性是有限的。在適當(dāng)?shù)呐渲孟?所有三個改進(jìn)SC解碼算法,如SCL,SCS,SCH,可以接近ML譯碼的性能,但有接受的復(fù)雜性。在提出的修剪技術(shù)的幫助下,在高信噪比下這些解碼器的時間和空間復(fù)雜性可以顯著減少。CRC-AIDED解碼為了進(jìn)一步提高極性碼的性能,CRC(循環(huán)冗余校驗)輔

31、助SCL/SCS解碼方案,如CASCL / CA-SCS,最近已經(jīng)在7被提出。在這些計劃中SCL / SCS解碼器輸出候選路徑CRC檢測器,檢查結(jié)果被用來檢測正確的碼字。為了降低時間復(fù)雜度的SCL解碼帶來的一個大列表的大小,通過逐步擴(kuò)大尺寸列表提出了一種自適應(yīng)CRC-aided SCL解碼器(aCA-SCL)11。在這些CRC-aided解碼方案中,極性碼的性能大幅提高,優(yōu)于在ML譯碼下的情況。置信傳播解碼基于因子圖表示相當(dāng)于極性代碼的框架圖3.a所示、極性的BP譯碼器代碼被Arikan在1中被首次引入。不是交換硬消息,在BP譯碼中，在檢查和變量節(jié)點之間傳輸軟消息。因此BP譯碼器可以大大超越了

32、SC解碼器。然而,消息傳遞時間表在BP中發(fā)揮著重要作用，除了BECs由于冗余循環(huán)因素圖,并且最優(yōu)進(jìn)度很難確定。除此之外,很難提高BP譯碼器的并行性。因此,一個實際的BP譯碼器遭受更高的實現(xiàn)復(fù)雜性，并且提供了一個比SC解碼器更低得吞吐量。ML或MAP解碼理論上最優(yōu)極性碼解碼算法是ML或MAP解碼器,可以分別通過維特比和BCJR算法框架實現(xiàn)。但這些眾所周知的算法對于中長代碼實際應(yīng)用過于復(fù)雜,所以他們只是被視為參考其他極性碼的解碼算法的性能比較。優(yōu)點和缺點關(guān)于編碼的實現(xiàn),極性編碼器利用一個中等復(fù)雜度O(NlogN)的遞歸結(jié)構(gòu)編碼。此外,給出的代碼長度N = 2n,通過添加或刪除一個極化通道可以細(xì)微調(diào)

33、整極性編碼的編碼速率。由于渦輪編碼器由兩個卷積組件代碼組成,代碼中相應(yīng)的復(fù)雜性是線性長度N。相反,基于隨機(jī)的不規(guī)則LDPC碼結(jié)構(gòu),編碼復(fù)雜度非常高。幸運的是基于一個 upper-triangulation過程可以有效的降低這種復(fù)雜性。在實踐中一個LDPC碼進(jìn)一步收益率通常會限制于一個簡單的編碼,如準(zhǔn)循環(huán)LDPC碼(QC)。所有三個編碼效率編碼器結(jié)構(gòu),但是極性代碼有更好的速率兼容性質(zhì)幾乎不斷改變編碼速率。在實踐中GA算法是一個更好的選擇,因為它可以提供足夠精確的評估誤差性能有著最低的復(fù)雜性。另一方面,為了優(yōu)化渦輪碼我們使用外在信息變換(退出)12作為一種半解析工具來預(yù)測誤差性能。此外,作為核心構(gòu)

34、建塊的分界渦輪編碼器應(yīng)該基于計算機(jī)搜索優(yōu)化。渦輪碼的設(shè)計顯然是比極性代碼更復(fù)雜的。以同樣的方式LDPC編碼的優(yōu)化也是一個非常耗時的過程。變量和檢查程度分布只能由計算機(jī)優(yōu)化搜索12。并且主要方法生成奇偶校驗矩陣圖(或因子圖)的LDPC碼也是一個計算機(jī)輔助施工過程,如先進(jìn)的邊緣增長(PEG)算法12?？傊?建設(shè)極性代碼比其他代碼更直接和更簡單。理論上所有三個代碼代碼長度是趨于無限時有相同的漸近性能。極性代碼基于SC解碼對稱B-DMC實現(xiàn)的能力得到證實,因為建設(shè)符合聯(lián)合AEP屬性的代碼。相反,渦輪/ LDPC碼基于BCJR / BP譯碼顯示由計算機(jī)模擬逼近能力的傾向,而不是理論證明。因此極性碼比其他

35、兩個碼有理論優(yōu)勢。然而,對于一個有限的代碼長度三個代碼可以統(tǒng)一在圖像上由相關(guān)的因子圖和執(zhí)行類似消息傳遞算法。渦輪碼的迭代譯碼,譯碼器每個組件執(zhí)行BCJR算法和通過襯墊/ 解交織交流外在信息。LDPC碼的BP算法在因子圖運行并且軟消息在變量和檢查節(jié)點之間進(jìn)行消息傳遞。經(jīng)過多次迭代兩種解碼器也能奏效,并且接近ML譯碼性能。然而,對于極性碼BP算法的性能是有限的短循環(huán)因素圖劣于ML譯碼。因此一些改進(jìn)的SC極性碼代碼樹是更好的選擇,如SCL / SCS / CASCL CA-SCS等等。圖5給出了各種BLER編碼和解碼方案的性能比較。所有的編碼方案的代碼長度N = 1024(除了LDPC碼,N = 1

36、056)和編碼速率R = 1/2,并且AWGN信道上傳輸二進(jìn)制輸入。此外,24 CRC校驗位連接到每一塊編碼器的輸入。渦輪碼的兩個編碼方案分別稱為WCDMA和LTE標(biāo)準(zhǔn),Log-MAP解碼算法(在對數(shù)域BCJR解碼)最大的八個迭代被應(yīng)用。同樣,LDPC碼是根據(jù)WiMax標(biāo)準(zhǔn)構(gòu)造的,李永樂標(biāo)準(zhǔn)BP算法和最多200次迭代。構(gòu)建極性代碼時,極化通道選擇攜帶信息比特在5中使用的方法。CA-SCL的列表大小是 L = 32并且最大尺寸aCA-SCL是L = 1024。最大迭代數(shù)極性碼的BP譯碼器是。我們可以看到SCL /BP的塊誤碼率優(yōu)于SC算法。幸運的是,有足夠大的極地代碼列表CRC輔助下解

37、碼算法可以比渦輪/ LDPC碼。此外,沒有跡象表明極地編碼方案模擬的誤差地板信噪比,這是在渦輪/ LDPC碼另一個優(yōu)勢。為了評估所有這些編碼的解碼算法的復(fù)雜度,我們可以用LLR、對數(shù)似然概率,或APP作為基本單位計算。因此,SC解碼器最低復(fù)雜度O(NlogN),但是相應(yīng)的性能很差。同樣,turbo譯碼器執(zhí)行基本操作為一個迭代,占2m框架，每個框架有四個指標(biāo)的計算節(jié)點。假設(shè)變量的平均值(檢查)LDPC碼的分布程度是，因子圖包含N變量節(jié)點和檢查節(jié)點,BP譯碼器執(zhí)行為一個迭代基本操作。一般來說,一個LDPC碼的結(jié)構(gòu)限制,例如,QCLDPC,BP譯碼器的復(fù)雜度略低于turbo譯碼器。然而,兩種算法的復(fù)

38、雜性是高于CA-SCL / CA-SCS極性編碼解碼器帶有適當(dāng)?shù)膮?shù)。詳細(xì)的比較可以在7,10找到。因此,極性碼CA-SCL / CA-SCS可以達(dá)到比其他更好的性能和復(fù)雜性之間的權(quán)衡。最后我們發(fā)現(xiàn)極性編碼理論相比渦輪/ LDPC碼在許多方面如理論性能性能，構(gòu)造方法,和編碼/解碼方案有明顯的好處。極性碼的缺點當(dāng)然,極性代碼有一些缺點,因為天下沒有免費的午餐?；叵肫饋?通道選擇極性編碼,信道可靠性計算應(yīng)根據(jù)特定的通道類型或通道條件。因此,代碼結(jié)構(gòu)是通道的依賴,盡管編碼器結(jié)構(gòu)是普遍存在的。但在實踐中這不是一個嚴(yán)重的問題。因為極性編碼的誤差性能是不明智的輕微變化的信息通道,在一個固定的信噪比我們可以優(yōu)化通道選擇。頻道組是統(tǒng)一在一個廣泛的信噪比下但性能也許有一些小的損失。自SC及其改進(jìn)算法分級解碼順序執(zhí)行的代碼樹,這些解碼器本質(zhì)上擁有一個串行架構(gòu)。由于這種結(jié)構(gòu)約束,譯碼器設(shè)計與高吞吐量現(xiàn)在已經(jīng)成為一個挑戰(zhàn),這是在實踐中極性編碼的一個主要缺點