極化碼自適應(yīng)連續(xù)消除列表比特翻轉(zhuǎn)譯碼算法

劉 偉，段紅光

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

極化碼(polar code)是第一類被證明在無限碼長下利用連續(xù)消除(successive cancellation, SC)譯碼實(shí)現(xiàn)二進(jìn)制輸入無記憶對(duì)稱信道容量的糾錯(cuò)碼[1]。然而對(duì)于有限碼長，采用SC譯碼算法的誤塊率(block error ratio, BLER)高于低密度奇偶校驗(yàn)(low density parity check code ,LDPC)碼[2]。

比特翻轉(zhuǎn)是另一種改進(jìn)SC譯碼算法，SC-Flip譯碼算法最早在文獻(xiàn)[6]中提出，采用對(duì)數(shù)似然比(log-likelihood ratio, LLR)的絕對(duì)值作為評(píng)估信息比特的可靠性指標(biāo)，通過翻轉(zhuǎn)不可靠比特來糾正譯碼錯(cuò)誤；文獻(xiàn)[7]基于SC譯碼產(chǎn)生的第1個(gè)錯(cuò)誤估計(jì)分布，提出固定索引選擇和增強(qiáng)索引選擇來降低選擇比特翻轉(zhuǎn)索引的復(fù)雜度；文獻(xiàn)[8]提出基于錯(cuò)誤分布的分區(qū)串行消除比特翻轉(zhuǎn)算法，可以糾正至少一個(gè)比特錯(cuò)誤，并降低了計(jì)算復(fù)雜度；文獻(xiàn)[9]提出了一種更為準(zhǔn)確的判斷信息位決策可靠性的方法，并在文獻(xiàn)[10]中基于該可靠性度量方法提出了多比特翻轉(zhuǎn)算法，然而文獻(xiàn)[9-10]都需要對(duì)可靠性指標(biāo)進(jìn)行大量的排序來識(shí)別不可靠比特，導(dǎo)致較大譯碼延遲；文獻(xiàn)[11]引入了一種漸進(jìn)的多比特翻轉(zhuǎn)SC譯碼算法，并且通過構(gòu)造臨界集(critical set, CS)作為比特翻轉(zhuǎn)的索引集使用；文獻(xiàn)[12]將比特翻轉(zhuǎn)方法應(yīng)用到SCL譯碼算法中，提出一種連續(xù)消除列表比特翻轉(zhuǎn)(SCL flip, SCLF)譯碼算法，但該算法若要獲得更好性能，則需要較大的L值，導(dǎo)致復(fù)雜度提高。為了降低其譯碼復(fù)雜度，本文提出了一種自適應(yīng)連續(xù)消除列表比特翻轉(zhuǎn)譯碼算法(adaptive SCLF, AD-SCLF)，該算法最初設(shè)置較小的L值，如果沒有路徑通過CRC校驗(yàn)，則迭代地增加路徑保留數(shù)L，直到達(dá)到預(yù)設(shè)的最大值Lmax。

1 極化碼基本原理

1.1 極化碼構(gòu)造

1.2 極化碼譯碼

(1)

根據(jù)判決函數(shù)h判決比特ui

(2)

圖1給出碼長N=4時(shí)的SC譯碼樹，該算法只保留一條路徑，其中，黑色粗線表示經(jīng)過SC譯碼后保留的路徑，黑色節(jié)點(diǎn)表示被淘汰的節(jié)點(diǎn)。

SCL譯碼算法作為一種增強(qiáng)的譯碼算法，在譯碼算法中需要保存L條備選路徑，以減少丟失正確路徑的機(jī)會(huì)。根據(jù)文獻(xiàn)[16]定義一個(gè)路徑度量值(path metric, PM)為

(3)

在每次譯碼過程中，SCL的候選路徑數(shù)量將成倍增加，在路徑數(shù)量達(dá)到預(yù)設(shè)路徑保留數(shù)L時(shí)，通過剪枝過程從列表中選擇L條最佳路徑，直到譯碼結(jié)束。譯碼結(jié)束后譯碼器將從列表中選擇PM最小的路徑作為譯碼輸出。圖2給出碼長N=4，路徑保留數(shù)L=2時(shí)的SCL譯碼樹，其中，灰色路徑代表被剪枝的路徑。

圖1 N=4時(shí)SC譯碼樹Fig.1 SC decoding tree with N=4

圖2 N=4和L=2時(shí)SC譯碼樹Fig.2 SCL decoding tree with N=4 and L=2

1.3 SC-Flip算法和SCLF算法

SC-Flip譯碼算法的核心思想是由于SC譯碼過程中導(dǎo)致錯(cuò)誤傳播的第1個(gè)比特的判決錯(cuò)誤總是由信道噪聲引起的[6]，故如果能夠識(shí)別并糾正(翻轉(zhuǎn))該比特決策，則可以提升譯碼性能。文獻(xiàn)[11]將極化碼按照完全二叉樹進(jìn)行轉(zhuǎn)換，根據(jù)得到的可靠性位置，將最后一級(jí)子節(jié)點(diǎn)按照可靠性位置進(jìn)行標(biāo)記，接著標(biāo)記父節(jié)點(diǎn)，若子節(jié)點(diǎn)都是黑色則父節(jié)點(diǎn)標(biāo)記黑色，若都是白色則標(biāo)記白色，若一白一黑則標(biāo)記灰色，如圖3?；谠摻Y(jié)構(gòu)構(gòu)造一種CS來識(shí)別第1個(gè)判決錯(cuò)誤的比特，CS是通過選擇每個(gè)“速率為1”的節(jié)點(diǎn)中的第1個(gè)信息位的索引作為其元素。例如在圖3中，當(dāng)N=8時(shí)，CS={4，6，7}，這些索引位于虛線框中。文獻(xiàn)[12]中提出CS中對(duì)應(yīng)的信息比特往往是最不可靠的比特，可能是SC譯碼過程中引起錯(cuò)誤傳播的第1個(gè)錯(cuò)誤比特，并且驗(yàn)證了第1個(gè)錯(cuò)誤比特在CS集中的概率高達(dá)100%。

圖3 N=8時(shí)極化碼的臨界集Fig.3 Critical set of polar codes with N=8

SCLF算法基于SCL算法提出，將比特翻轉(zhuǎn)引入到SCL中，指出SCL譯碼中有3種分裂狀態(tài)的路徑，即“克隆狀態(tài)”、“刪除狀態(tài)”和“SC狀態(tài)”，并確定“SC狀態(tài)”的路徑可以用于比特翻轉(zhuǎn)。但是適用于SC-Flip算法的臨界集并不適用于SCLF算法，故文獻(xiàn)[12]通過刪掉部分不能用于比特翻轉(zhuǎn)的位置，重新獲得修正后的臨界集(revised critical set, RCS)來表示比特翻轉(zhuǎn)的位置，表示為

(4)

SCLF算法采用CRC-Polar級(jí)聯(lián)的方法。當(dāng)SCL譯碼完成后，使用CRC校驗(yàn)當(dāng)前譯碼結(jié)果，如果CRC校驗(yàn)成功，表示SCL譯碼成功并終止。如果CRC校驗(yàn)失敗，將處于“SC狀態(tài)”的路徑進(jìn)行比特翻轉(zhuǎn)，并開始重新再次嘗試SCL譯碼，在嘗試譯碼時(shí)，所選擇翻轉(zhuǎn)不可靠比特ui進(jìn)行反向決策，即如果在第1次譯碼失敗時(shí)ui=0(1)，在翻轉(zhuǎn)譯碼時(shí)ui被設(shè)置為1(0)。在每次SCL譯碼嘗試結(jié)束時(shí)進(jìn)行CRC校驗(yàn)，直到CRC校驗(yàn)成功為止。

2 AD-SCLF譯碼算法

AD-SCLF譯碼算法通過動(dòng)態(tài)選擇路徑保留數(shù)的方法，在中高信噪比時(shí)能大大減小路徑保留數(shù)，但同時(shí)需要解決在進(jìn)行比特翻轉(zhuǎn)時(shí)的2個(gè)問題，即如何從失敗的路徑中識(shí)別出最佳翻轉(zhuǎn)路徑，以及如何從最佳翻轉(zhuǎn)路徑中識(shí)別出最佳翻轉(zhuǎn)的位置。

2.1 翻轉(zhuǎn)路徑

根據(jù)(3)式可進(jìn)一步改寫為[16]

(5)

2.2 翻轉(zhuǎn)位置

文獻(xiàn)[11]采用CS尋找不可靠決策位置，一旦置信序列確定，那么CS也將確定，文獻(xiàn)[12]提出改進(jìn)的RCS，即刪除掉部分不能用于翻轉(zhuǎn)的位置，從而降低復(fù)雜度，提高譯碼性能。SC-Flip譯碼根據(jù)其LLR的絕對(duì)值排序作為翻轉(zhuǎn)位置。該準(zhǔn)則中LLR絕對(duì)值可以表示為

(6)

本文設(shè)計(jì)了一種結(jié)合RCS與度量值M(ui)的方法，將RCS中的元素通過對(duì)應(yīng)的LLR絕對(duì)值進(jìn)行排序得到RCS′，并選取其中前T個(gè)最小M(ui)對(duì)應(yīng)位置作為翻轉(zhuǎn)位置，然后根據(jù)新判決函數(shù)h′進(jìn)行判決

(7)

2.3 AD-SCLF算法

AD-SCLF算法是通過動(dòng)態(tài)規(guī)劃路徑保留數(shù)，從預(yù)設(shè)最小路徑保留數(shù)開始進(jìn)行譯碼。當(dāng)該路徑不能正確譯碼輸出時(shí)，則進(jìn)行SCLF譯碼，當(dāng)進(jìn)行T次比特翻轉(zhuǎn)的譯碼嘗試后也不能輸出正確譯碼時(shí)，則增大路徑保留數(shù)，直到達(dá)到預(yù)設(shè)路徑保留最大值。具體算法流程如圖4。

根據(jù)算法流程圖，當(dāng)路徑保留數(shù)L=1時(shí)，圖4中SCL算法即為SC算法，SCLF算法即為SC-Flip算法。編譯碼具體實(shí)現(xiàn)步驟如下。

圖4 AD-SCLF算法流程圖Fig.4 Algorithm flow chart of AD-SCLF

步驟1利用高斯近似法(DE-GA)生成置信序列，將信息比特與凍結(jié)比特混合進(jìn)行極化編碼；

步驟2設(shè)置初始路徑保留數(shù)L=1以及最大路徑保留數(shù)Lmax；

步驟3利用SCL進(jìn)行譯碼(當(dāng)L=1時(shí)即為SC譯碼)，將L條輸出路徑進(jìn)行CRC校驗(yàn)，若存在至少一條輸出路徑通過CRC校驗(yàn)，則直接執(zhí)行步驟6，否則執(zhí)行步驟4；

步驟4在失敗的路徑中選擇最小PM值對(duì)應(yīng)的路徑，作為SCLF翻轉(zhuǎn)的路徑(當(dāng)L=1時(shí)即為SC-flip)，依次翻轉(zhuǎn)臨界集RCS′的前T個(gè)比特位置分別進(jìn)行T次譯碼嘗試，將L條輸出路徑進(jìn)行CRC校驗(yàn)，若至少存在一條輸出路徑通過CRC校驗(yàn)，則直接執(zhí)行步驟6，否則執(zhí)行步驟5；

步驟5增大擴(kuò)展路徑保留數(shù)L，即L=2·L，若L≤Lmax，則返回步驟3，否則返回譯碼失敗并結(jié)束譯碼；

步驟6選擇通過CRC校驗(yàn)的路徑作為譯碼輸出，返回譯碼成功并結(jié)束譯碼。根據(jù)置信序列取出信息比特并去除CRC校驗(yàn)比特，得到凈信息比特，進(jìn)行誤碼統(tǒng)計(jì)。

3 仿真分析

3.1 參數(shù)設(shè)置

本文仿真分別在AWGN信道和瑞利(Rayleigh)信道下進(jìn)行，SCLF算法和AD-SCLF算法均采用12位CRC校驗(yàn)，生成多項(xiàng)式為g(x)=x12+x11+x3+x2+1，2種算法的最大允許比特翻轉(zhuǎn)數(shù)為32。

設(shè)置初始路徑保留數(shù)為1，相當(dāng)于SC譯碼算法。為了對(duì)算法性能進(jìn)行仿真對(duì)比，分別采用N=256和N=512碼長，且在每一個(gè)碼長下設(shè)置3種最大路徑保留數(shù)Lmax=4，Lmax=8和Lmax=16。文中涉及其他參數(shù)如表1。

表1 仿真參數(shù)

3.2 性能分析

圖5和圖6分別給出在AWGN信道下，碼長N=256和N=512時(shí)，SCLF算法和AD-SCLF算法的BLER性能比較；圖7和圖8分別給出在Rayleigh信道下，碼長N=256和N=512時(shí)，SCLF算法和AD-SCLF算法的BLER性能比較。仿真結(jié)果表明，在AWGN信道和Rayleigh信道下，本文提出的AD-SCLF算法的譯碼與SCLF算法在同一路徑保留數(shù) (L=Lmax)下曲線接近重疊，表示BLER性能相當(dāng)。

圖5 高斯信道下AD-SCLF和SCLF的BLER性能比較(N=256)Fig.5 BLER performance comparison of AD-SCLF and SCLF over AWGN channel (N=256)

圖6 高斯信道下AD-SCLF和SCLF的BLER性能比較(N=512)Fig.6 BLER performance comparison of AD-SCLF and SCLF over AWGN channel (N=512)

圖7 瑞利信道下AD-SCLF和SCLF的BLER性能比較(N=256)Fig.7 BLER performance comparison of AD-SCLF and SCLF over Rayleigh channel (N=256)

圖8 瑞利信道下AD-SCLF和SCLF的BLER性能比較(N=512)Fig.8 BLER performance comparison of AD-SCLF and SCLF over Rayleigh channel (N=512)

3.3 復(fù)雜度分析

圖9 高斯信道下AD-SCLF和SCLF的復(fù)雜度對(duì)比(N=256)Fig.9 Complexity comparison of AD-SCLF and SCLF over AWGN channel (N=256)

圖10 高斯信道下AD-SCLF和SCLF的復(fù)雜度對(duì)比(N=512)Fig.10 Complexity comparison of AD-SCLF and SCLF over AWGN channel (N=512)

圖11 瑞利信道下AD-SCLF和SCLF的復(fù)雜度對(duì)比(N=256)Fig.11 Complexity comparison of AD-SCLF and SCLF over Rayleigh channel (N=256)

圖12 瑞利信道下AD-SCLF和SCLF的復(fù)雜度對(duì)比(N=512)Fig.12 Complexity comparison of AD-SCLF and SCLF over Rayleigh channel (N=512)

4 結(jié)束語

針對(duì)SCLF譯碼算法需要較大路徑保留數(shù)帶來譯碼復(fù)雜度增加，本文提出一種自適應(yīng)的SCLF算法，其路徑保留數(shù)可以隨著信噪比的增大而減小，從而降低平均復(fù)雜度。通過在AWGN信道和Rayleigh信道下仿真分析可知，在中高信噪比條件下，本文提出的AD-SCLF譯碼算法在不影響譯碼性能的條件下降低SCLF譯碼算法的復(fù)雜度。