郭 銳 孫 荷 楊 沛

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

1 引言

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

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

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

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

候選翻轉(zhuǎn)比特集合是影響Fast-SSC-Flip算法譯碼復(fù)雜度以及譯碼性能的關(guān)鍵因素之一，集合大小影響候選比特的搜索效率以及復(fù)雜度。當(dāng)前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 譯碼樹(shù)利用R a t e 0，Rate1，REP以及SPC節(jié)點(diǎn)進(jìn)行剪枝之后，可以得到如圖2所示的Fast-SSC譯碼樹(shù)。Fast-SSC譯碼樹(shù)相較于最初的SC譯碼樹(shù)而言，其高度已經(jīng)大大降低，因此深度優(yōu)先遍歷的效率可以得到提升，相應(yīng)的譯碼時(shí)延也會(huì)降低。

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

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

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

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

2.2 Fast-SSC-Flip譯碼算法

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

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

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

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

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

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

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

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

在Fast-SSC-F lip譯碼算法中，無(wú)論是計(jì)算候選比特的度量值，還是選擇不可靠的候選比特執(zhí)行翻轉(zhuǎn)譯碼，都與候選翻轉(zhuǎn)比特集合的大小相關(guān)。然而大部分現(xiàn)存文獻(xiàn)中的Fast-SSC-Flip算法的候選翻轉(zhuǎn)比特集合的大小都等于信息比特集合的大小，因此若能有效縮小候選翻轉(zhuǎn)比特集合的大小，則可以有效減少度量值計(jì)算以及排序復(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ù)雜度，一種直接的思想是縮小譯碼過(guò)程中首位錯(cuò)誤比特的搜索范圍，文獻(xiàn)[16]提出的關(guān)鍵集合CS能夠?qū)C譯碼算法中首位錯(cuò)誤比特定位到CS中，CS在SC譯碼算法中有極大概率包含首位錯(cuò)誤比特。然而由于Fast-SSC并不是在SC譯碼樹(shù)的葉節(jié)點(diǎn)得到譯碼信息比特值，而是在Fast-SSC譯碼樹(shù)的各種特殊節(jié)點(diǎn)得到相應(yīng)的碼字比特序列。故本節(jié)首先研究了CS在Fast-SSC譯碼算法中的有效性。

3.1 CS構(gòu)造方法

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

3.2 CS有效性

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

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

表1 N =1 024, K =512 T sim =106, 時(shí)CS的有效性驗(yàn)證

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

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

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

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

圖3 極化碼SC譯碼樹(shù)以及Fast-SSC譯碼樹(shù)

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

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

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

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

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

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

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

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

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

圖4 譯碼樹(shù)SPC節(jié)點(diǎn)對(duì)應(yīng)子樹(shù)結(jié)構(gòu)

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

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

4.2 CFS構(gòu)造算法

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

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

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

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

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

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

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

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

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

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

當(dāng)設(shè)置極化碼的參數(shù)N=512,R=0.5時(shí)，上述各個(gè)譯碼算法的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譯碼算法并沒(méi)有明顯的BER性能損失。相較SC,Fast-SSC譯碼算法在BER=10-3條件下有0.78 dB的性能增益。

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

類似地，圖5(b)表示N=1 024,R=0.5時(shí)上述的各個(gè)譯碼算法的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譯碼算法并沒(méi)有明顯的BER性能損失。

類似地，圖6(b)表示在極化碼參數(shù)N=1 024,R=0.5時(shí)上述的各個(gè)譯碼算法的FER性能數(shù)值仿真圖。通過(guò)觀察兩圖可以發(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譯碼算法的性能開(kāi)銷以及譯碼延遲，本節(jié)利用翻轉(zhuǎn)譯碼算法的平均迭代次數(shù)Iave來(lái)表示每一幀需要進(jìn)行譯碼的次數(shù)，其最小和最大的迭代次數(shù)分別為1和Tmax+1。Iave的計(jì)算方法為

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

由于所對(duì)比的幾種不同算法均基于Fast-SSC，在保持參數(shù)一致的情況下，譯碼過(guò)程中消耗的CFast-SSC，CCRC一致。因此，譯碼一幀中消耗的CC數(shù)量取決于CSort。傳統(tǒng)的Fast-SSC-Flip譯碼算法對(duì)K個(gè)信息比特的LLR值進(jìn)行排序，而CFS-Fast-SSC-Flip僅對(duì)CFS中η個(gè)信息比特的LLR值進(jìn)行排序。在排序過(guò)程中消耗的時(shí)鐘周期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譯碼算法的一個(gè)直觀優(yōu)勢(shì)是在候選比特的搜索效率。傳統(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)比特集合大小。在極化碼的碼長(zhǎng)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ā)來(lái)提升Fast-SSC-Flip的候選比特搜索效率，由此提出了CFS-Fast-SSCFlip。本文所提的CFS能夠有效地包含候選翻轉(zhuǎn)比特，但集合大小遠(yuǎn)小于全部信息比特集合大小，從而減小搜索復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，本文提出的基于CFS的Fast-SSC-F lip算法在和N-Fast-SSCF lip取得相近的譯碼性能和平均迭代次數(shù)的情況下，顯著地縮小了候選翻轉(zhuǎn)比特集合的大小，減小了搜索復(fù)雜度，提升了候選比特的搜索效率。