基于對數(shù)似然比與極化信道可靠度的SCF 譯碼算法

黃 勝，鄭秀鳳，曹志雄

（重慶郵電大學(xué)通信與信息工程學(xué)院光通信與網(wǎng)絡(luò)重點實驗室，重慶 400065）

0 概述

極化碼［1］是ARIKAN 于2008 年提出的一種在理論上可達信道極限容量的編碼方式。目前，極化碼被應(yīng)用在5G 增強移動寬帶場景中，作為5G 的信道控制編碼方式。極化碼的構(gòu)造依賴于一個特定的遞歸編碼過程，研究人員根據(jù)其編碼構(gòu)造的特點提出了復(fù)雜度低的串行抵消（Successive Cancellation，SC）譯碼算法［2］，但是在中短碼長的情況下該算法的性能不理想。為提高譯碼的性能，文獻［3-4］提出串行抵消列表（Successive Cancellation List，SCL）譯碼算法［3-4］，該算法提高了極化碼在有限塊長度的性能，使得其能與低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼［5］和turbo 碼［6］競爭。隨后，奇偶校驗碼（Parity Check Codes，PCC）［7］和循環(huán)冗余檢驗（Cyclic Redundancy Check，CRC）極化碼的自適應(yīng)SCL 譯碼算法［8］與CRC 輔 助SCL（CRCAssistant SCL，CA-SCL）譯碼算法［9］被提出，其 中CA-SCL 譯碼算法在搜索寬度L=32 時，譯碼性能可以接近最大似然（Maximum-Likelihood，ML）譯碼界［10］。并且，為降低時延，文獻［11］提出一種基于基本路徑替代的低時延自適應(yīng)列表連續(xù)刪除轉(zhuǎn)換算法，針對不同列表的連續(xù)刪除轉(zhuǎn)換間存在重復(fù)路徑的現(xiàn)象。雖然SCL 譯碼算法顯著降低了極化碼碼長為有限長時的BLER，但它具有較大的存儲開銷和較高的計算復(fù)雜度，且兩者都與列表大小呈線性增長的關(guān)系。

2014 年，AFISIADIS 等［12］提出具有較小存儲開銷和較低計算復(fù)雜度的SCF 譯碼算法。與SCL 的并行SC 譯碼算法相比，該譯碼算法依賴更多后續(xù)的解碼嘗試，通過依次翻轉(zhuǎn)不可靠的信息比特糾正SC 譯碼過程中發(fā)生的錯誤。雖然該算法最壞的譯碼情況為翻轉(zhuǎn)最大嘗試次數(shù)仍不能譯出正確的譯碼結(jié)果，但是在中高SNR 下，它產(chǎn)生的平均計算復(fù)雜度與SC解碼的平均計算復(fù)雜度近似，并且它的譯碼性能與L=2 時的SCL 譯碼算法相近。SCF 譯碼算法是用CRC 對譯碼結(jié)果進行校驗，因此CRC 檢錯能力會影響SCF 譯碼的性能。2018 年，KIM 等［13］提出交織輔助的SCF 譯碼算法。無論是用CRC 校驗的SCF 譯碼算法，還是用交織器輔助的ISCF 譯碼算法，SCF譯碼算法提升的性能都是有限的。為解決SCF 存在的問題，目前研究人員從2 個方面進行了改進：

通過求解SC 譯碼的首個判決錯誤（The First Decision Error，TFDE）的概率實現(xiàn)一位比特的翻轉(zhuǎn)。但是在實際中，準確求解出TFDE的概率很難，文獻［14］提出一種動態(tài)比特翻轉(zhuǎn)譯碼算法，它通過求解近似TFDE 的概率來動態(tài)生成比特翻轉(zhuǎn)列表，實現(xiàn)一位甚至是多位比特的翻轉(zhuǎn)，同時文獻［15］在此基礎(chǔ)上提出了誤碼率估計的SCF 譯碼算法，該譯碼算法通過縮小翻轉(zhuǎn)的集合，降低了計算度量值的復(fù)雜度。

通過提取不可靠的信息位組成一個較小的翻轉(zhuǎn)集合使得在有限的翻轉(zhuǎn)次數(shù)上優(yōu)先翻轉(zhuǎn)認為錯誤概率更高的比特。例如，文獻［16］研究平均對數(shù)似然比（Log-Likelihood-Ratio，LLR）與錯誤比特信道的分布，提出閾值SCF 譯碼算法，并運用比較器代替LLR 的選擇和排序，降低了計算的復(fù)雜度。文獻［17］提出一種基于錯誤分布的SCF 譯碼算法，該算法包含兩個譯碼算法，一種算法是根據(jù)錯誤分布選取最大錯誤率的T位信息位組成固定的翻轉(zhuǎn)集合，另一種譯碼算法則是設(shè)置錯誤分布閾值實現(xiàn)一個動態(tài)翻轉(zhuǎn)集合，并運用LLR 作為翻轉(zhuǎn)的度量。同時為提升一位翻轉(zhuǎn)SCF 譯碼算法的性能，文獻［18］提出分段的SCF 譯碼算法。

為提升SCF 譯碼算法的性能，本文基于串行抵消譯碼算法，分析對數(shù)似然比、極化信道可靠度、信息位所在的位置與SC 譯碼算法發(fā)生TFDE 之間的關(guān)系，并給出一個度量公式衡量SC 譯碼結(jié)果的可靠度。

1 SCF 譯碼算法

本節(jié)首先對SC 譯碼算法［2］進行分析。在SC 譯碼算法中，解碼器輸入端的數(shù)據(jù)表示為，解碼器的輸出表示為，其 中表 示ui的譯碼硬判決估計。在SC 解碼中，每個硬判決估計都取決于Y和前i-1 個硬判決估計，LLR 的表達式如式（1）所示：

根據(jù)Li估計SC 譯碼算法的譯碼結(jié)果如式（2）所示：

其中：I為信息位集合，當(dāng)Li≥0 時，sign(Li)=1，否則sign(Li)=-1。

然后對SCF 譯碼算法原理進行闡述。傳統(tǒng)的SCF 譯碼算法的步驟為：1）對接收信號執(zhí)行SC 譯碼過程，得到極化碼信息比特的譯碼估計值，其中K+r為原極化碼的信息比特位數(shù)與CRC 位數(shù)之和；2）用CRC 去校驗，如果校驗結(jié)果為0，則說明譯碼正確，輸出譯碼結(jié)果并結(jié)束譯碼，否則再次執(zhí)行SC 譯碼過程，并設(shè)置最大的翻轉(zhuǎn)次數(shù)T，對翻轉(zhuǎn)次數(shù)初始化t=1；3）如果t>T，說明經(jīng)過了T次比特翻轉(zhuǎn)后仍不能得到正確的譯碼結(jié)果，結(jié)束譯碼；如果t

為改進SCF 譯碼算法，本文研究極化碼在執(zhí)行SC 譯碼過程中由于信道條件不理想造成比特錯誤譯碼的情況。圖1 所示為由信道條件引起比特錯誤譯碼的個數(shù)造成塊錯誤譯碼的分布。

圖1 不同信噪比下由信道引起錯誤的頻率Fig.1 Frequency of channel-induced errors in different SNR

圖1 所示是仿真1 000 000 次SCO-1［12］譯碼算法去識別和記錄SC 譯碼過程中塊發(fā)生錯誤時，由信道條件引起比特錯誤譯碼個數(shù)的概率分布，即該仿真不考慮譯碼過程中錯誤傳播情況。其中SCO-1 譯碼算法的工作原理是：該譯碼器預(yù)先知道原始輸入序列，在執(zhí)行SC譯碼的過程中發(fā)現(xiàn)譯出的信息比特與原始的信息比特結(jié)果不一致時，將該信息比特的判決進行翻轉(zhuǎn)并記錄這個位置。因此，執(zhí)行SCO-1 譯碼算法可以糾正SC 譯碼過程中由信道引起錯誤的第一個信息位。由圖1 可知，在執(zhí)行SC 譯碼算法過程中大于58%的塊發(fā)生錯誤是由TFDE 造成的。圖2 所示為正確翻轉(zhuǎn)一位發(fā)生錯誤譯碼的信息比特獲得的最佳性能，與SC 譯碼算法相比最大可獲得約0.7 dB 的增益。

圖2 SCO-1 譯碼算法與SC 譯碼算法性能比較Fig.2 Performance comparison between SCO-1 decoding algorithm and SC decoding algorithm

從圖2 可以看出，準確地翻轉(zhuǎn)TFDE 可以明顯降低BLER，但是SCO-1 譯碼器是一個模擬仿真工具，在實際中還沒有一個度量能百分之百地正確預(yù)測TFDE 的位置。因此，下文將分析與TFDE 相關(guān)的參數(shù)去確定執(zhí)行SC 譯碼過程中不可靠的信息比特譯碼。

2 改進的SCF 譯碼算法

由于傳統(tǒng)的SCF 譯碼算法過于依賴LLR 值，降低BLER 的力度會存在限制。為對傳統(tǒng)的SCF 譯碼算法進行改進，本節(jié)將研究造成TFDE 可能的因素，下文將研究當(dāng)發(fā)生TFDE 時，對數(shù)似然比、極化信道的可靠度等的分布情況。

由第1 節(jié)可知，SC 譯碼算法的譯碼估計公式如式（2）所示，使用這種硬判決機制去估計SC 譯碼結(jié)果，再加上噪聲的影響，使得|LLR|值越接近0，那么被誤判的概率就越高。為進一步驗證|LLR|值與TFDE 之間的關(guān)系，圖3 仿真了1 000 000 次SCO-1 譯碼算法來識別和記錄TFDE 的位置，并統(tǒng)計了TFDE發(fā)生在各個信息位的平均|LLR|值和所有信息位的平均|LLR|值。其中圓代表TFDE 發(fā)生在各個信息位的平均|LLR|值，方形表示所有信息位的平均|LLR|值。

圖3 平均 ||LLR 值和錯誤位置平均 ||LLR 值的關(guān)系Fig.3 Relationship of average ||LLR value and average ||LLR value of error location

從圖3 可以看出，發(fā)生TFDE 的信息位的|LLR|值總是很小，因此可以得出|LLR|值在一定程度上是可以作為衡量某個信息位發(fā)生TFDE 的指標。然而，僅根據(jù)|LLR|值來確定需要翻轉(zhuǎn)的位置還不夠準確。因此，還需要探討一些參數(shù)去進行優(yōu)化。

在中短碼長情況下，SC 譯碼算法性能不理想，主要是因為有限的碼長信道極化不完全。由公式（用衡量極化信道可靠性的指標，見求解式（3）［19］）可知與TFDE 有關(guān)，即某個信息位的值越小，該信息位為首個比特錯誤譯碼的概率也就越小。因此，初步認為極化信道可靠度與TFDE 有關(guān)。為進一步驗證極化信道可靠度和TFDE 之間的關(guān)系，圖4 和圖5 統(tǒng)計了兩者在不同信息位上的分布情況。

圖4 在SNR=2 dB 時 的分布Fig.4 Distribution of at SNR=2 dB

圖5 在SNR=2 dB 時TFDE 的分布Fig.5 Distribution of TFDE at SNR=2 dB

圖4 表示各個信息位的分布，圖5 表示各個信息位發(fā)生TFDE 的頻率分布。由圖4 和圖5 可知，在越大時TFDE 的頻率越高，因此證明了通過可以預(yù)估各個信息位發(fā)生TFDE 的概率情況。

根據(jù)上述分析可以得出，判斷一個信息比特發(fā)生錯誤譯碼的情況，可以綜合考慮|LLR|值、極化信道可靠度等因素。又因為極化碼的SC 譯碼算法是一個串行譯碼的過程，即在SC 譯碼過程中，會先對前面的信息比特進行譯碼，并且前面信息位的譯碼結(jié)果會影響后面信息位的譯碼結(jié)果。因此，當(dāng)2 個信息位為TFDE 的概率相差不多時，需要先對前面的信息位進行比特翻轉(zhuǎn)，所以將信息位的索引值作為判斷TFDE 的一個因素。

根據(jù)上述分析，下面分別對這3 個參數(shù)取一定的權(quán)重，使得3 個參數(shù)在不同的程度上共同決定信息位發(fā)生錯誤譯碼的程度。假設(shè)度量Mi表達式如式（8）所示：

其中：Ai表示第i信息位的索引值i所占的權(quán)重；Pi表示第i信息位的極化信道可靠度所占的權(quán)重；Ri表示LLR 值所占的權(quán)重，本文Ri的取值為|Li|。Pi所占的權(quán)重表達式如式（9）所示：

式（9）表示的是一個極化程度，但式（9）得到的值相對較大，為減少Pi所占權(quán)重，式（10）為進一步處理后Pi所占的權(quán)重。

為得到Mi的表達式，對Ai取值進行說明，該權(quán)重的取值依據(jù)是：在2N的碼長中，前面信息比特發(fā)生錯誤的概率比后面的信息比特發(fā)生錯誤的概率要高。又因為極化碼碼長為2 的N次方，所以Ai的取值規(guī)則具有碼長的特點，如式（11）所示：

其中：floor（）表示一個向下取整函數(shù)；i表示信息比特的索引值，即第一個信息比特i=1，本文i的最大值為K+r。

綜上，本文在傳統(tǒng)SCF 譯碼算法的基礎(chǔ)上提出一個改進的度量公式，如式（12）所示：

該度量弱化了對|LLR|值的依賴，綜合多個參數(shù)決定了信息位發(fā)生TFDE 的程度。

PLR-SCF 譯碼算法的步驟如下：

1）對接收信號執(zhí)行SC 譯碼過程，得到極化碼的信息比特譯碼估計值。

3）如果t>T，說明經(jīng)過T次比特翻轉(zhuǎn)后仍不能得到正確的譯碼結(jié)果，結(jié)束譯碼；如果t

4）如果經(jīng)過步驟3）以后譯出的信息比特序列通過CRC 校驗，則譯碼結(jié)束；否則翻轉(zhuǎn)次數(shù)t=t+1，繼續(xù)執(zhí)行步驟3）選擇另一個信息比特ui進行翻轉(zhuǎn)。

3 仿真結(jié)果與分析

3.1 誤塊率分析

本節(jié)給出的所有仿真結(jié)果都假設(shè)在AWGN 信道中。極化碼級聯(lián)CRC 使用的參數(shù)為：N=512，K=256，r=16 和N=1 024，K=512，r=16，分別表示為PC（512，256，16）和PC（1 024，512，16）。信息位選擇的構(gòu)造方法有極化重量（PW）構(gòu)造方法［20］、密度進化構(gòu)造方法［21］和高斯近似（Gaussian Approximation，GA）［19］構(gòu)造方法。在不同的信道條件下，最優(yōu)的信道估計方法不同。由于本文的仿真是在AWGN 信道中，因此選擇GA 的構(gòu)造方法。CRC 的生成多項式為g(x)=x16+x15+x2+1。下文對PLR-SCF 譯碼算法、SCF 算 法［12］、SC 譯碼算法［2］和SCO-1 譯碼器［12］（一種模擬理想一位比特翻轉(zhuǎn)的譯碼器，該譯碼器總能準確地識別出第一個發(fā)生錯誤的比特）的誤塊率進行比較，如圖6 所示。

圖6 T=16 時不同算法BLER 性能的比較Fig.6 Comparison of BLER performance of different algorithms with T=16

由圖6 可知，在PC（512，256，16）的情況下，本文提出的PLR-SCF 譯碼算法相比于SCF 譯碼算法獲得了大約0.12 dB 的信噪增益，與SCO-1 譯碼算法的BLER 幾乎相同。并且，在PC（1 024，512，16）的情況下，PLR-SCF 譯碼算法相比于SCF 譯碼算法也獲得大約0.1 dB 的信噪比增益，同時，在高SNR 時與理想的SCO-1 譯碼算法的BLER 很接近，這說明本文提出的度量公式可以提高翻轉(zhuǎn)到發(fā)生TFDE 信息位的概率，進一步提高了譯碼的性能。

3.2 計算復(fù)雜度分析

為衡量本文提出的度量值在翻轉(zhuǎn)方面的復(fù)雜度，如表1 所示為Tmax=16 時，PLR-SCF 譯碼算法與文獻［12］SCF 譯碼算法的平均額外翻轉(zhuǎn)次數(shù)的比較。

由表1 可知，與文獻［12］SCF 算法相比，本文的譯碼算法得到正確的譯碼結(jié)果，所需的比特翻轉(zhuǎn)嘗試次數(shù)最多可獲得13.6%的降低，并且SNR 越高該算法翻轉(zhuǎn)到錯誤譯碼的信息比特的速度就越快，說明了PLR-SCF 譯碼算法在識別一位錯誤信息比特的能力得到了增強。

表1 額外解碼嘗試的平均次數(shù)Table 1 Average number of additional decoding attempts

4 結(jié)束語

本文提出一種基于對數(shù)似然比與極化信道可靠度的SCF 譯碼算法PLR-SCF，通過仿真觀察信息位發(fā)生TFDE 時對數(shù)似然比、極化信道可靠度和信息位位置的分布情況，并根據(jù)觀察到的結(jié)果為不同的參數(shù)設(shè)定權(quán)重值，使得設(shè)計出的度量公式能夠更精確地衡量信息位譯碼結(jié)果可靠度。仿真結(jié)果表明，與SCF 譯碼算法相比，PLR-SCF 譯碼算法能夠有效提高算法性能，降低利翻轉(zhuǎn)的嘗試次數(shù)。由于本文PLR-SCF 譯碼算法主要實現(xiàn)一位比特翻轉(zhuǎn)，下一步將研究多位比特翻轉(zhuǎn)的譯碼算法，使譯碼算法性能得到更大提升。