基于關(guān)鍵翻轉(zhuǎn)集合的極化碼Fast-SSC-Flip譯碼算法

郭 銳 孫 荷 楊 沛

(杭州電子科技大學(xué)通信工程學(xué)院 杭州 310018)

1 引言

極化碼是目前唯一一種通過理論證明能夠達到香農(nóng)極限的信道編碼方案[1]。由于極化碼具有低復(fù)雜度的編譯碼結(jié)構(gòu)和優(yōu)良的糾錯性能，其已成為5G增強移動寬帶場景(Enhance M ob ile B road Band,EM BB)中控制信道的編碼方案。當極化碼的碼長趨近于無窮大時，串行抵消譯碼算法(Successive Cancellation,SC)被證明是一種可使極化碼的糾錯性能達到信道容量的譯碼算法。但SC譯碼算法在有限碼長情況下的譯碼性能并不理想，并且具有較高的譯碼時延。

為此，研究者提出了串行抵消翻轉(zhuǎn)(Successive Cancellation Flip,SC-Flip)譯碼算法[2]。該算法在首次SC譯碼失敗后，繼續(xù)嘗試多次SC譯碼，選擇易錯的候選比特(Candidate B it,CB)進行翻轉(zhuǎn)。Chandesris等人[3]提出了一種動態(tài)SC-Flip(Dynam ic-SC-Flip,D-SC-Flip)譯碼算法。該算法通過一種新的度量準則來權(quán)衡候選比特的譯碼順序和決策對數(shù)似然比(Log-Likelihood Ratio,LLR)對候選比特可靠性的影響，動態(tài)構(gòu)建及更新候選翻轉(zhuǎn)比特集合，同時翻轉(zhuǎn)多位錯誤比特。文獻[4]通過比較LLR計算得到的錯誤概率與高斯近似(Gaussian Approximation,GA)計算得到的錯誤概率，以此來縮小D-SC-Flip譯碼算法的候選翻轉(zhuǎn)比特集合。文獻[5]通過優(yōu)化候選翻轉(zhuǎn)集合的構(gòu)造，減少D-SC-Flip譯碼算法的搜索復(fù)雜度。文獻[6]提出了基于門限的候選翻轉(zhuǎn)集合構(gòu)造算法，進一步提升了譯碼性能。文獻[7]提出了一種新型的SC-Flip譯碼算法，同時利用奇偶校驗(Parity Check,PC)和循環(huán)冗余校驗(Cyclic Redundancy Check,CRC)的校驗作用，相比于CRC輔助的SC-Flip譯碼算法，獲得了更好的性能和復(fù)雜度的折中。

為了降低SC算法的譯碼時延，文獻[8]提出了簡化的SC(Sim p lified SC,SSC)譯碼算法。SSC譯碼算法能夠在Rate0節(jié)點以及Rate1節(jié)點直接進行硬判決譯碼，有效地降低了譯碼時延。隨后，Sarkis等人[9]進一步提出了單奇偶校驗(Sing le Parity Check,SPC)以及重復(fù)(REPetition,REP)節(jié)點，并提供了這兩種特殊節(jié)點的直接譯碼方法，使得改進后的快速簡化串行抵消(Fast-Sim p lified Successive Cancellation,Fast-SSC)譯碼算法相較于SC譯碼算法在不損失糾錯性能的前提下極大地降低譯碼時延。進一步地，文獻[10]對Fast-SSC譯碼算法中的各種特殊節(jié)點做了歸納總結(jié)，提出了更具一般性的Type-I,Type-II,Type-III,Type-IV以及Type-V節(jié)點，通過對這5種節(jié)點直接譯碼，從而極大地改善SC譯碼算法的譯碼時延。

Giard等人[11]將Fast-SSC譯碼算法與SC-Flip譯碼算法相結(jié)合，提出了Fast-SSC-F lip譯碼算法。Fast-SSC-Flip譯碼算法允許在初始Fast-SSC譯碼失敗之后，繼續(xù)嘗試執(zhí)行最多Tmax次Fast-SSC譯碼算法，且每次執(zhí)行Fast-SSC譯碼時選擇候選翻轉(zhuǎn)比特集合中的某個比特進行翻轉(zhuǎn)。然而傳統(tǒng)Fast-SSC-Flip譯碼算法在對SPC節(jié)點進行翻轉(zhuǎn)譯碼時會有輕微的性能損失，為此研究者提出了一種新的Fast-SSC-Flip[12](New-Fast-SSC-Flip,N-Fast-SSCF lip)譯碼算法，能取得優(yōu)異的譯碼性能。同一作者在文獻[13]中提出了一種適用于衡量Fast-SSC譯碼過程中候選比特可靠性的度量準則，該度量準則能夠更精確地定位到首位譯碼錯誤比特。文獻[14]提出了基于易錯比特列表和分段CRC校驗的Fast-SSC-F lip譯碼算法，進一步提升譯碼性能。文獻[15,16]提出了兩種增強型的多比特翻轉(zhuǎn)Fast-SSC譯碼算法來糾正Fast-SSC譯碼過程中的多位譯碼錯誤比特。

候選翻轉(zhuǎn)比特集合是影響Fast-SSC-Flip算法譯碼復(fù)雜度以及譯碼性能的關(guān)鍵因素之一，集合大小影響候選比特的搜索效率以及復(fù)雜度。當前Fast-SSC-Flip譯碼算法搜索候選翻轉(zhuǎn)比特的范圍與全部信息比特構(gòu)成的集合的維度一致。因此，本文在CS的基礎(chǔ)上提出了關(guān)鍵翻轉(zhuǎn)集合(Critical Flip Set,CFS)，將Fast-SSC-Flip譯碼中候選比特搜索范圍定位到CFS中，并提出了基于CFS的Fast-SSCFlip譯碼算法，從而降低傳統(tǒng)Fast-SSC-Flip譯碼算法的候選翻轉(zhuǎn)比特集合大小，減小搜索復(fù)雜度。

2 Fast-SSC-Flip譯碼算法

2.1 Fast-SSC譯碼算法

圖1 所示的極化碼S C 譯碼樹利用R a t e 0，Rate1，REP以及SPC節(jié)點進行剪枝之后，可以得到如圖2所示的Fast-SSC譯碼樹。Fast-SSC譯碼樹相較于最初的SC譯碼樹而言，其高度已經(jīng)大大降低，因此深度優(yōu)先遍歷的效率可以得到提升，相應(yīng)的譯碼時延也會降低。

圖1(N,K)=(8,4)的極化碼SC譯碼樹

圖2(N,K)=(8,4)的極化碼Fast-SSC譯碼樹

Rate0節(jié)點表示該節(jié)點有連續(xù) 2S個比特為凍結(jié)比特，因此將該節(jié)點的所有碼字比特硬判決為全0比特；Rate1節(jié)點表示該節(jié)點有連續(xù) 2S個比特為信息比特，在該節(jié)點直接利用硬判決方法進行譯碼。REP節(jié)點僅僅只有最右側(cè)的葉節(jié)點是信息比特，而其余的葉節(jié)點全是凍結(jié)比特。Fast-SSC譯碼算法在REP節(jié)點直接利用最大似然譯碼算法進行譯碼。SPC節(jié)點是指在以該節(jié)點為根節(jié)點的譯碼子樹中，只有最左側(cè)的葉節(jié)點是凍結(jié)比特，其余的葉節(jié)點全是信息比特。同理，F(xiàn)ast-SSC可以直接在SPC節(jié)點進行硬判決(Hard Decision,HD)，譯碼輸出結(jié)果為

其中，HD[i]表 示根據(jù)SPC節(jié)點內(nèi)的第i個比特的LLR值進行硬判決，判決方式如式(2)所示；p表示SPC節(jié)點內(nèi)所有比特的譯碼估計值的總和，計算方式如式(3)所示；iε表示SPC節(jié)點內(nèi)最不可靠的一位信息位的索引位置，選擇方法如式(4)所示

2.2 Fast-SSC-Flip譯碼算法

Fast-SSC-Flip算法通過找到Fast-SSC譯碼中不可靠的比特加入到候選翻轉(zhuǎn)比特集合中，并在額外譯碼中嘗試逐次翻轉(zhuǎn)不可靠的比特，直至譯碼輸出正確結(jié)果或者達到設(shè)置的最大額外嘗試譯碼次數(shù)Tmax。

在衡量Fast-SSC譯碼過程中候選比特可靠性時，需要根據(jù)不同節(jié)點類型分別計算各個節(jié)點內(nèi)候選比特的可靠性。由于Rate0節(jié)點內(nèi)包含的所有比特全是凍結(jié)比特，這些凍結(jié)比特在接收端和發(fā)送端也被假設(shè)是已知的。因此本文在構(gòu)建候選翻轉(zhuǎn)比特集合時，僅考慮Rate1，REP以及SPC 3種節(jié)點內(nèi)的信息比特。

Rate1節(jié)點內(nèi)的任意第i個CB的可靠性度量計算方式為

當需要翻轉(zhuǎn)的比特位于該節(jié)點內(nèi)時，相應(yīng)位置的比特進行翻轉(zhuǎn)。

REP節(jié)點內(nèi)僅含有一個信息比特，即在該節(jié)點內(nèi)有且僅有1個CB，且該CB位于末尾位置。該CB的可靠性度量計算方式為

其中，N v表示該節(jié)點的長度，即包含凍結(jié)比特以及信息比特的總數(shù)量。當需要翻轉(zhuǎn)的比特位于REP節(jié)點內(nèi)時，該節(jié)點內(nèi)的末尾比特進行翻轉(zhuǎn)。

SPC節(jié)點內(nèi)CB的可靠性度量計算及其無損翻轉(zhuǎn)譯碼方法為

其中，p以及iε計 算方式參見式(3)和式(4)，ε表示節(jié)點內(nèi)最不可靠的比特的決策LLR值，可用式(8)計算

在Fast-SSC-F lip譯碼算法中，無論是計算候選比特的度量值，還是選擇不可靠的候選比特執(zhí)行翻轉(zhuǎn)譯碼，都與候選翻轉(zhuǎn)比特集合的大小相關(guān)。然而大部分現(xiàn)存文獻中的Fast-SSC-Flip算法的候選翻轉(zhuǎn)比特集合的大小都等于信息比特集合的大小，因此若能有效縮小候選翻轉(zhuǎn)比特集合的大小，則可以有效減少度量值計算以及排序復(fù)雜度，并且可以提升候選比特的搜索效率。為此，本文利用極化碼的生成矩陣得到與CS中信息比特相應(yīng)的碼字比特，并用這些碼字比特構(gòu)建關(guān)鍵翻轉(zhuǎn)集合CFS作為候選翻轉(zhuǎn)比特集合。從而降低Fast-SSC-F lip譯碼算法的候選翻轉(zhuǎn)比特集合大小，減小搜索復(fù)雜度。

3 Fast-SSC譯碼算法中CS構(gòu)造及其有效性

為了降低Fast-SSC-F lip譯碼算法搜索候選翻轉(zhuǎn)比特的復(fù)雜度，一種直接的思想是縮小譯碼過程中首位錯誤比特的搜索范圍，文獻[16]提出的關(guān)鍵集合CS能夠?qū)C譯碼算法中首位錯誤比特定位到CS中，CS在SC譯碼算法中有極大概率包含首位錯誤比特。然而由于Fast-SSC并不是在SC譯碼樹的葉節(jié)點得到譯碼信息比特值，而是在Fast-SSC譯碼樹的各種特殊節(jié)點得到相應(yīng)的碼字比特序列。故本節(jié)首先研究了CS在Fast-SSC譯碼算法中的有效性。

3.1 CS構(gòu)造方法

構(gòu)建CS的方法簡述為：首先將SC譯碼樹裁剪為SSC譯碼樹，裁剪后的譯碼樹中編碼速率為1的葉節(jié)點(等效于Rate1節(jié)點)被稱為極化子塊，每個子塊都是一個僅包含信息比特序列的極化碼。將所有子塊中的首位比特依次放入到初始化為空集的CS中完成CS的構(gòu)建。CS詳細的構(gòu)建方法如算法1所示。

3.2 CS有效性

本節(jié)主要驗證CS集合在Fast-SSC譯碼算法下是否能夠有效地包含F(xiàn)ast-SSC譯碼算法的首位錯誤比特。本節(jié)的仿真參數(shù)如下：極化碼編碼方式為非系統(tǒng)編碼，接收端采用Fast-SSC譯碼算法。設(shè)置極化碼碼長N=1 024，信息比特長度K=512，碼率R=0.5，蒙特卡羅仿真次數(shù)為Tsim=106。

仿真結(jié)果見表1，“譯碼錯誤幀數(shù)”表示采用Fast-SSC譯碼得到的錯誤譯碼總幀數(shù)；“首錯在CS中”表示Fast-SSC譯碼中的首位錯誤信息比特在由算法1構(gòu)造的CS中的總幀數(shù)；“準確性”由兩者的比值得到；“CS的維度”表示CS集合的大小。

表1 N =1 024, K =512 T sim =106, 時CS的有效性驗證

仿真結(jié)果驗證了CS在Fast-SSC譯碼過程中仍然有效，即CS有接近100%的概率能夠包含F(xiàn)ast-SSC譯碼過程中的首位譯碼錯誤比特，且CS的維度小于信息比特集合的大小。

4 關(guān)鍵翻轉(zhuǎn)集合CFS的構(gòu)造

4.1 基礎(chǔ)理論及結(jié)論證明

圖3給出了SC譯碼樹轉(zhuǎn)換成Fast-SSC譯碼樹的過程。{u1,u2,u3,u5}表 示凍結(jié)序列，{u4,u6,u7,u8}表示信息序列。右邊的譯碼樹表示該極化碼的Fast-SSC譯碼樹。其中左邊葉節(jié)點為REP節(jié)點，該節(jié)點可以描述成一個長度為4，包含{u1,u2,u3,u4}的子極化碼。同理，右邊葉節(jié)點為SPC節(jié)點，可以描述為一個長度為4，包含{u5,u6,u7,u8}的子極化碼。

圖3 極化碼SC譯碼樹以及Fast-SSC譯碼樹

當進行Fast-SSC譯碼時，利用硬判決方法對REP以及SPC節(jié)點直接譯碼得到的結(jié)果稱為碼字序列。在Fast-SSC譯碼過程中，只有翻轉(zhuǎn)首位錯誤碼字比特才能避免錯誤傳播對Fast-SSC譯碼過程的影響。然而CS是相對于信息比特序列而言的，因此對于Fast-SSC譯碼，需要尋找與CS中的信息比特相應(yīng)的候選比特(碼字比特)才能構(gòu)建候選翻轉(zhuǎn)比特集合。

對于一個碼長為N=2n的極化碼，其生成矩陣G N=(g1,g2,...,g N)=F?n，其中GN的列向量gi中元素1的位置構(gòu)成的集合為Ωi。若葉節(jié)點l長 度為L，當前子極化碼對應(yīng)于極化碼的索引為(τ+1,τ+2,...,τ+L)，l由包含的信息比特序列經(jīng)過極化編碼構(gòu)成，在節(jié)點l處可得到碼字序列為

其中，G L為 該子極化碼的生成矩陣。當譯碼樹的葉節(jié)點l為Rate1或者REP節(jié)點時，在2元域下，本文給出如下命題：

命題1若Fast-SSC譯碼中首位錯誤信息比特uτ+i在 譯碼樹的葉節(jié)點l內(nèi)，且是由l譯碼得到的部分碼字比特x?Φ錯誤導(dǎo)致的，則必然有Φ?Ωi且有極大概率|Φ|=1，其中Φ表示為候選翻轉(zhuǎn)比特集合。

證明 若節(jié)點l得到的譯碼碼字序列為，則該節(jié)點包含的信息序列為

其中，第2步等式是根據(jù)文獻[1]中給出的G N=，故可以得到首位錯誤比特uτ+i的估計值為

因此對于Rate1及REP節(jié)點而言，若確定首位錯誤信息比特uτ+i，則其相應(yīng)的候選比特集合Φ可由命題1得到。當譯碼樹的葉節(jié)點l為SPC節(jié)點時，若首位錯誤信息比特uτ+i在該節(jié)點內(nèi)，則根據(jù)文獻[17]可知，SPC節(jié)點有極大概率僅存在兩位錯誤比特，一位為固定翻轉(zhuǎn)碼字比特(由于該比特是固定翻轉(zhuǎn)比特，因此并沒有被包含于該文獻中的節(jié)點內(nèi)錯誤比特數(shù)量統(tǒng)計結(jié)果)，另一位為待確定的由信道噪聲導(dǎo)致譯碼錯誤的某個候選碼字比特e。由于命題1是在2元域討論下得到的結(jié)論，則兩位錯誤比特必然不可能同時在xΩi中，否則根據(jù)式(11)可知，兩位錯誤比特將導(dǎo)致uτ+i正確譯碼。將uτ+i相應(yīng)的固定翻轉(zhuǎn)位記作με，且計算為

綜上所述，對于Rate1，REP以及SPC 3種特殊節(jié)點，若確定首位錯誤信息比特uτ+i，則都能夠利用命題1來構(gòu)建uτ+i相應(yīng)的候選比特集合。

為了便于理解命題1，本文以圖2中的SPC節(jié)點為例。該SPC節(jié)點為一個碼長N=4的子極化碼，包含信息比特序列(u6,u7,u8)，u5為凍結(jié)比特且設(shè)置為0，該子極化碼對應(yīng)的子樹結(jié)構(gòu)如圖4所示，其中藍色節(jié)點表示SPC節(jié)點，白色葉節(jié)點表示凍結(jié)比特，黑色葉節(jié)點表示信息比特。當利用Fast-SSC算法進行譯碼時，在SPC節(jié)點得到的正確譯碼碼字為

圖4 譯碼樹SPC節(jié)點對應(yīng)子樹結(jié)構(gòu)

其中，G4為該子極化碼的生成矩陣。假設(shè)上述的極化碼在Fast-SSC譯碼中首位錯誤比特為u6，則根據(jù)式(13)有

根據(jù)式(14)可知，導(dǎo)致u6譯碼錯誤的原因是x2或x4譯碼錯誤，即有Φ={2}或Φ={4}；顯然Ω2={2,4}，故Φ?Ωi成立。證畢

4.2 CFS構(gòu)造算法

基于上述的命題1，在Fast-SSC譯碼過程中，首位錯誤信息比特一般都是由其所在的子極化碼的某位碼字比特xΦ譯碼錯誤導(dǎo)致的；同時根據(jù)Fast-SSC譯碼中首位錯誤信息比特有接近100%的概率在CS中的結(jié)論，本文將CS中的每個信息比特對應(yīng)的xΦ收集起來構(gòu)成一個關(guān)鍵翻轉(zhuǎn)集合CFS。不同于CS的構(gòu)建方法，CFS在CS的基礎(chǔ)上，需要利用LLR以及生成矩陣完成，其不僅與極化碼的結(jié)構(gòu)有關(guān)還與譯碼過程有關(guān)。

CFS構(gòu)建方法如算法2所示：注意到算法2所述算法的第1行利用的是算法1所述的CS構(gòu)造函數(shù)；第3行根據(jù)Fast-SSC譯碼樹結(jié)構(gòu)確定CS(i)相應(yīng)的Ω，先確定C S(i)所 在的子極化碼生成矩陣GN以及其相對節(jié)點內(nèi)的首位信息比特的位置i，根據(jù)GN以及i確定相應(yīng)的Ω；第4行描述的衡量碼字比特可靠性的度量準則，所使用的度量準則為碼字比特的決策LLR。表示碼字比特序列相應(yīng)的決策LLR向量。

算法2 CFS構(gòu)造算法

CFS構(gòu)造算法一個直觀的解釋是，F(xiàn)ast-SSC譯碼過程中首位錯誤比特一般是由于該比特所在的子極化碼某位譯碼錯誤導(dǎo)致的，且該比特必然屬于因此本文選擇xΩ中最不可靠的碼字比特作為CFS集合中的一員。同時，由于CS集合有極大概率包括Fast-SSC譯碼的首位錯誤比特，故為了減少復(fù)雜度，本文僅考慮在CS基礎(chǔ)上構(gòu)建相應(yīng)的CFS。

5 CFS-Fast-SSC-Flip譯碼算法及性能

5.1 CFS-Fast-SSC-Flip譯碼算法

本文基于提出的CFS設(shè)計了一種單比特翻轉(zhuǎn)Fast-SSC譯碼算法，命名為CFS-Fast-SSC-Flip譯碼算法。CFS-Fast-SSC-Flip譯碼算法詳細的描述見算法3。所提算法與傳統(tǒng)的Fast-SSC-Flip譯碼算法的主要區(qū)別為：所提算法選擇候選比特進行翻轉(zhuǎn)譯碼時僅從CFS中選擇，相較于傳統(tǒng)的Fast-SSCFlip使用整個信息比特集合的搜索范圍而言，減小了搜索復(fù)雜度，有效提升候選比特的搜索效率。

5.2 CFS-Fast-SSC-Flip譯碼器性能分析

為了研究提出的CFS-Fast-SSC-Flip譯碼算法譯碼性能，本節(jié)將算法3中第4行的度量準則設(shè)置為根據(jù)候選比特的決策LLR升序排序，并與Fast-SSC-Flip(s=0.5，算法補償系數(shù))，N-Fast-SSCFlip,Fast-SSC以及SSC-Oracle譯碼算法進行性能比較。由于本文所提的CFS-Fast-SSC-Flip譯碼算法的CFS是基于CS構(gòu)建的，因此本文同時比較了基于CS的Fast-SSC-Flip(Fast-SSC-Flip-CS)譯碼算法的性能。SSC-O racle譯碼算法是一種理想的Fast-SSC譯碼算法，該算法能夠完美糾正Fast-SSC譯碼過程中由信道噪聲導(dǎo)致的單個錯誤比特，即該算法的性能代表單比特翻轉(zhuǎn)Fast-SSC算法的譯碼性能上限。

算法3 CFS-Fast-SSC-Flip譯碼算法

當設(shè)置極化碼的參數(shù)N=512,R=0.5時，上述各個譯碼算法的BER性能曲線如圖5(a)所示。從圖5(a)可以看出所提的CFS-Fast-SSC-F lip譯碼算法與N-Fast-SSC-Flip譯碼算法的BER性能曲線幾乎保持一致，相較于傳統(tǒng)的Fast-SSC-Flip譯碼算法以及Fast-SSC-Flip-CS譯碼算法，所提的CFSFast-SSC-F lip譯碼算法并沒有明顯的BER性能損失。相較SC,Fast-SSC譯碼算法在BER=10-3條件下有0.78 dB的性能增益。

圖5 CFS-Fast-SSC-Flip譯碼算法與各種譯碼算法在R =0.5時BER性能比較圖

類似地，圖5(b)表示N=1 024,R=0.5時上述的各個譯碼算法的BER性能數(shù)值仿真圖。綜合圖5(a)與圖5(b)可得，所提的CFS-Fast-SSC-Flip譯碼算法與N-Fast-SSC-Flip譯碼算法的BER性能曲線幾乎保持一致，相較于傳統(tǒng)的Fast-SSC-Flip譯碼算法以及Fast-SSC-F lip-CS譯碼算法，所提的CFSFast-SSC-Flip譯碼算法并沒有明顯的BER性能損失。

類似地，圖6(b)表示在極化碼參數(shù)N=1 024,R=0.5時上述的各個譯碼算法的FER性能數(shù)值仿真圖。通過觀察兩圖可以發(fā)現(xiàn)，提出的CFS-Fast-SSC-Flip算法的譯碼性能略優(yōu)于傳統(tǒng)的Fast-SSCFlip譯碼算法以及Fast-SSC-Flip-CS譯碼算法，且與N-Fast-SSC-Flip譯碼算法的性能幾乎相同。

為了研究CFS-Fast-SSC-Flip譯碼算法的性能開銷以及譯碼延遲，本節(jié)利用翻轉(zhuǎn)譯碼算法的平均迭代次數(shù)Iave來表示每一幀需要進行譯碼的次數(shù)，其最小和最大的迭代次數(shù)分別為1和Tmax+1。Iave的計算方法為

為了更好地分析所提算法的譯碼延遲[18]，對各種算法的時鐘周期(C lock Cycles,CC)進行比較。為了便于表述每個譯碼階段所消耗的CC數(shù)，其中Fast-SSC譯碼算法消耗的CC數(shù)、排序操作消耗的CC數(shù)、CRC校驗消耗的CC數(shù)以及一輪額外迭代的CC數(shù)分別用CFast-SSC，CSort，CCRC以及CExtra進行表示。假設(shè)在第1次譯碼過程中，首先進行Fast-SSC譯碼操作，然后執(zhí)行排序操作，其中CRC校驗和排序操作同時執(zhí)行。因此在第1次譯碼過程中消耗的C1=CFast-SSC+CSort。在額外的迭代譯碼過程中仍然先執(zhí)行Fast-SSC譯碼操作，與第1次譯碼不同的是，后續(xù)的迭代譯碼過程不需要進行排序操作。因此，每一輪額外的迭代譯碼消耗的CExtra=CFast-SSC+CCRC。綜上，譯碼一幀所需CC數(shù)量的計算表達如式(16)所示

由于所對比的幾種不同算法均基于Fast-SSC，在保持參數(shù)一致的情況下，譯碼過程中消耗的CFast-SSC，CCRC一致。因此，譯碼一幀中消耗的CC數(shù)量取決于CSort。傳統(tǒng)的Fast-SSC-Flip譯碼算法對K個信息比特的LLR值進行排序，而CFS-Fast-SSC-Flip僅對CFS中η個信息比特的LLR值進行排序。在排序過程中消耗的時鐘周期CSort(η)＜CSort(K)。由表2可以得到，本文所提的CFS-Fast-SSC-Flip譯碼算法的平均迭代次數(shù)Iave要小于等于目前現(xiàn)存的Fast-SSC-Flip譯碼算法。綜上，本文所提算法的譯碼延遲要優(yōu)于Fast-SSC-Flip算法、且與N-Fast-SSC-Flip譯碼算法的譯碼延遲接近。

表2 各種譯碼算法的平均迭代次數(shù)

本文所提的CFS-Fast-SSC-F lip譯碼算法相較于傳統(tǒng)Fast-SSC-Flip以及N-Fast-SSC-Flip譯碼算法的一個直觀優(yōu)勢是在候選比特的搜索效率。傳統(tǒng)的Fast-SSC-Flip譯碼算法在搜索候選比特方面的復(fù)雜度為O(Klog2K)，而CFS-Fast-SSC-F lip譯碼算法的搜索復(fù)雜度為O(ηlog2η)。其中K表示信息比特集合大小，η表示CFS集合的大小。

表3比較了本節(jié)所提的CFS相較于傳統(tǒng)的Fast-SSC-Flip所使用的候選翻轉(zhuǎn)比特集合大小。從表3可以得到本文所提的CFS集合的大小在不同極化碼編碼參數(shù)以及信噪比的情況下都要小于傳統(tǒng)的Fast-SSC-Flip譯碼算法所使用的候選翻轉(zhuǎn)比特集合大小。在極化碼的碼長N=1 024，碼率R=0.5，本文所提的CFS-Fast-SSC-Flip譯碼算法相較于傳統(tǒng)Fast-SSC-Flip(N-Fast-SSC-F lip與傳統(tǒng)Fast-SSC-Flip兩種譯碼算法的候選翻轉(zhuǎn)比特集合大小相同)，至少能縮小77.93%的候選翻轉(zhuǎn)比特集合大小。

表3 CFS與傳統(tǒng)Fast-SSC-Flip譯碼算法的候選翻轉(zhuǎn)比特集合大小比較

6 結(jié)論

本文從縮小Fast-SSC-Flip譯碼算法中的候選翻轉(zhuǎn)比特集合大小出發(fā)來提升Fast-SSC-Flip的候選比特搜索效率，由此提出了CFS-Fast-SSCFlip。本文所提的CFS能夠有效地包含候選翻轉(zhuǎn)比特，但集合大小遠小于全部信息比特集合大小，從而減小搜索復(fù)雜度。實驗結(jié)果表明，本文提出的基于CFS的Fast-SSC-F lip算法在和N-Fast-SSCF lip取得相近的譯碼性能和平均迭代次數(shù)的情況下，顯著地縮小了候選翻轉(zhuǎn)比特集合的大小，減小了搜索復(fù)雜度，提升了候選比特的搜索效率。