LT碼的一種非階梯化高斯消元譯碼算法

賀 亮，雷 菁，黃 英

(國(guó)防科技大學(xué) 電子科學(xué)學(xué)院，湖南 長(zhǎng)沙 410073)

0 引言

為了避免多播系統(tǒng)中，多個(gè)終端向發(fā)端反饋重傳信息時(shí)的反饋風(fēng)暴，相關(guān)學(xué)者提出了噴泉碼的編碼方案[1-3]，通過(guò)噴泉編碼，可以生成理論上無(wú)窮多個(gè)編碼符號(hào)，因此噴泉碼也被稱為無(wú)碼率碼。Luby提出的LT碼[4]是首個(gè)可以具體實(shí)現(xiàn)的噴泉碼，其編碼符號(hào)是信息符號(hào)的線性組合。Shokrollahi提出Raptor碼[5],通過(guò)在LT碼前加上固定碼率的信道編碼，使其能夠在噪聲信道下發(fā)揮更出色的性能。目前噴泉碼在數(shù)字視頻廣播標(biāo)準(zhǔn)[6]以及3GPP中都有應(yīng)用。

LT碼最初建立在二元?jiǎng)h除信道(BEC)上，其譯碼屬于硬判決譯碼，主流的2種算法是置信傳播(BP)算法和高斯消元(GE)算法。原始的高斯消元并沒有實(shí)現(xiàn)實(shí)時(shí)譯碼，在文獻(xiàn)[7-9]中相關(guān)學(xué)者進(jìn)一步提出了可漸進(jìn)實(shí)現(xiàn)的高斯消元算法。針對(duì)BP算法譯碼開銷大的問題，有學(xué)者提出BP算法與高斯消元結(jié)合的方法[10-12]，國(guó)內(nèi)有人提出了增強(qiáng)型BP算法[13]，以及一種BP與最大似然譯碼結(jié)合的BPMLE算法[14]。

高斯消元算法是LT碼的一種最大似然譯碼方法，能夠最小化譯碼開銷，但其復(fù)雜度也較高。提出一種可以降低復(fù)雜度的高斯消元算法，在LT譯碼的過(guò)程中，使用該方法進(jìn)行矩陣化簡(jiǎn)，不需要實(shí)現(xiàn)階梯化，同時(shí)結(jié)合BP算法，使其能夠?qū)崟r(shí)漸進(jìn)的譯碼。

1 LT碼的硬譯碼

1.1 編碼原理

LT編碼器將固定數(shù)量的信息符號(hào)生成理論上無(wú)窮數(shù)目的編碼符號(hào)。編碼符號(hào)的度分布是設(shè)計(jì)LT碼的關(guān)鍵，符號(hào)的度，即該符號(hào)擁有的連接的數(shù)目。度分布可以用多項(xiàng)式表示為

(1)

G·sT=yT。

(2)

1.2譯碼原理

通常假定接收端已知編碼的生成矩陣，那么譯碼就是在接收到編碼符號(hào)的情況下，恢復(fù)出信息符號(hào)的過(guò)程。兩大主要方法為BP譯碼和高斯消元(GE)譯碼。

1.2.1 BP譯碼

在接收的編碼符號(hào)中，找到一個(gè)度數(shù)為1的符號(hào)yi，將其值賦給唯一相鄰的信息符號(hào)sj，即sj=yi，則該信息符號(hào)得到恢復(fù)，并將對(duì)應(yīng)的這條連接刪除。此后，所有與sj相連的編碼符號(hào)與sj異或，并隨后將連接刪除。在這之后，繼續(xù)在編碼符號(hào)中尋找度數(shù)為1的，重復(fù)上述步驟，若不存在度為1的編碼符號(hào)，則接收端需要更多的編碼符號(hào)，將接收到的符號(hào)與已經(jīng)恢復(fù)的信息符號(hào)異或更新后刪除連接，再按上述步驟進(jìn)行度數(shù)1符號(hào)搜索，使BP譯碼能夠繼續(xù)進(jìn)行，直至所有信息符號(hào)恢復(fù)。

1.2.2 GE譯碼

高斯消元譯碼首先對(duì)生成矩陣和接收符號(hào)構(gòu)成的增廣矩陣進(jìn)行三角化，若成功，則回代方程組可求解出信息符號(hào)。三角化是將增廣矩陣轉(zhuǎn)化為上三角形式，若該過(guò)程失敗，說(shuō)明需要更多的編碼符號(hào)，然后三角化需要重新進(jìn)行。原始的GE失敗后，并不保留處理后的矩陣，實(shí)際上，文獻(xiàn)[7]中增量的高斯消元算法(incGE)才是實(shí)用的高斯消元譯碼。設(shè)信息符號(hào)的數(shù)目為k，增量高斯消元在剛接收到k個(gè)編碼符號(hào)后，僅執(zhí)行一次三角化，將原始的生成矩陣G簡(jiǎn)化為G′，若三角化不完全，譯碼失敗，但保留G′。在G′中，“優(yōu)行”指那些最左方“1”在對(duì)角線上的行，“劣行”則是不符合該情況的行。首次三角化中以及之后在接收更多編碼符號(hào)時(shí)，增量高斯消元通過(guò)行變換，盡可能地將劣行轉(zhuǎn)換為優(yōu)行。當(dāng)接收到足夠多的符號(hào)時(shí)，三角化將完全實(shí)現(xiàn)，此時(shí)再對(duì)方程回代，即可恢復(fù)出所有的信息符號(hào)。

定義譯碼開銷

ε=1-n/k，

(3)

式中，n為譯碼成功時(shí)接收的編碼符號(hào)數(shù)目。實(shí)驗(yàn)驗(yàn)證已經(jīng)表明，對(duì)于任意的k，incGE算法的譯碼開銷均明顯大于BP算法，且其開銷隨著k的增大收斂于0的速度更快。在譯碼復(fù)雜度方面，BP算法的較低，為O(klb(k))，incGE的復(fù)雜度則相當(dāng)于一次高斯消元，為O(k2)。

1.3 非階梯化高斯消元

本文提出的高斯消元是一種非行階梯化的消除方法，非階梯化高斯消元(NEGE)在BP算法遇到停止集時(shí)，將所有未消除連接符號(hào)對(duì)應(yīng)的矩陣，進(jìn)行矩陣簡(jiǎn)化，簡(jiǎn)化符號(hào)之間的連接，使得簡(jiǎn)化后的矩陣有再次進(jìn)行BP譯碼的可能。

（2）高校教師數(shù)據(jù)知識(shí)。根據(jù)調(diào)查結(jié)果顯示：數(shù)據(jù)基礎(chǔ)知識(shí)掌握方面，利用統(tǒng)計(jì)數(shù)據(jù)進(jìn)行相關(guān)知識(shí)的教學(xué)占比76.6%，經(jīng)常、偶爾通過(guò)書籍等渠道了解或者專門學(xué)習(xí)數(shù)據(jù)如何分析占比分別為63.3%與20%；對(duì)于數(shù)據(jù)工具使用情況，60%的高校教師使用數(shù)據(jù)分析工具超過(guò)三個(gè)，而Excel、SPSSS 使用率高達(dá)63%以上，相反地，SAS、R、Python、Stata 等軟件使用極低，其中最高占比16.7%。從這兩方面來(lái)看，內(nèi)蒙古高校教師使用統(tǒng)計(jì)軟件的能力較弱，使用工具較單一。但數(shù)據(jù)基礎(chǔ)知識(shí)方面情況良好，單這一方面可看出，內(nèi)蒙古高校教師數(shù)據(jù)知識(shí)在逐步積累。

該算法在矩陣層面的實(shí)現(xiàn)是：譯碼開始時(shí)首先應(yīng)用BP算法，找到權(quán)重為1的行，對(duì)應(yīng)的編碼符號(hào)的值將被賦予給其唯一的鄰接信息符號(hào)，此后這些行上的1置0，表示連接刪除；而這些新恢復(fù)的信息符號(hào)，將要與它們的鄰接編碼符號(hào)異或，進(jìn)一步刪除這些連接，即將1置0；然后，將在尋找權(quán)重為1的行重復(fù)上述步驟。當(dāng)找不到權(quán)重為1的行時(shí)，再利用高斯消元，完畢后尋找權(quán)重為1的行，進(jìn)行BP譯碼。若經(jīng)過(guò)上述所有步驟，信息未完全恢復(fù)，則接收更多的編碼符號(hào)，將接收的符號(hào)與已經(jīng)恢復(fù)的編碼符號(hào)之間可能存在的連接消除，并更新編碼符號(hào)，依上面步驟進(jìn)行BP和高斯消元的聯(lián)合譯碼。非階梯化高斯消元算法如下：

其中，M(i,j)表示M的第i行第j列元素，用“：”表示對(duì)矩陣或向量整行、整列的引用。函數(shù)isemtpy(·)判斷變量是否為空，為空則返回1，“～”表示邏輯非，’row’代表按行求和，函數(shù)size(·)為返回矩陣的行列數(shù)，sum(·)為求和函數(shù)。

所提的NEGE相比原始的方法在復(fù)雜度上有明顯的降低。首先，選取某一行對(duì)其他行作消除時(shí)，采用了選取權(quán)重最小行的策略。在高斯消元過(guò)程中，對(duì)行的處理是從頂行到底行進(jìn)行，對(duì)列則是從最左至最右。傳統(tǒng)的高斯消元，在選取基準(zhǔn)行對(duì)其他行做消除時(shí)，選取是均勻隨機(jī)的。而所提的NEGE則選取權(quán)重最低的作為基準(zhǔn)，這樣可以降低其他行在消除后的權(quán)重，進(jìn)而減少行操作的次數(shù)。其次，由于高斯消元后會(huì)應(yīng)用BP譯碼，因此行階梯的特點(diǎn)可以舍棄。原始的高斯消元使得每行最左方的1依次呈階梯狀，這樣就需要對(duì)基準(zhǔn)行進(jìn)行行交換。NEGE在選取基準(zhǔn)行后，保持其位置不變，可以避免行交換操作。

NEGE譯碼示例如圖1所示。

圖1 NEGE譯碼示例

以Tanner圖表示符號(hào)之間的連接關(guān)系，圓形為信息符號(hào)，方形為編碼符號(hào)。在圖1(a)中，Y1，Y2，Y6是新接收到的符號(hào)，S6，S7是已經(jīng)恢復(fù)的信息符號(hào)。新符號(hào)首先與S6，S7異或更新連接，然后進(jìn)行BP譯碼直到圖1(b)遇到停止集BP無(wú)法繼續(xù)。提取剩余連接，進(jìn)行NEGE如圖1(c)所示。在圖1(d)中，可以觀察到符號(hào)之間的連接已經(jīng)簡(jiǎn)化，BP譯碼可以再次展開。

2 仿真結(jié)果

不失一般性，令1個(gè)符號(hào)代表1 bit。仿真信道為二元?jiǎng)h除信道，同樣假設(shè)信道刪除率為0。本節(jié)給出BP算法、incGE算法以及NEGE算法的仿真結(jié)果。度分布采用文獻(xiàn)[4]中的魯棒孤子分布(RSD)，RSD的δ參數(shù)設(shè)置為0.05,所有結(jié)果都在1 000次蒙特卡洛仿真下平均得到。

圖2給出了3種算法的開銷ε與信息符號(hào)長(zhǎng)度k的關(guān)系，且RSD的c參數(shù)有3個(gè)不同值0.01,0.1,0.5?？梢钥闯?，NEGE的譯碼開銷與incGE相同，因?yàn)槎叨甲畲笙薅鹊乩昧松删仃?。此外，NEGE和incGE隨著k的增大開銷趨于0的收斂速度顯著快于BP算法。在c=0.01及c=0.1的情況下，BP算法2條曲線的差距顯著大于NEGE之間的，且BP算法最上方的曲線在k較小時(shí)還出現(xiàn)了波動(dòng)。因此NEGE算法的性能對(duì)度分布的選擇敏感性遠(yuǎn)遠(yuǎn)小于BP算法的，若選擇NEGE算法，度分布的精細(xì)設(shè)計(jì)可以在較大程度上忽略。

圖2 RSD下不同參數(shù)c的開銷

圖3給出了3種算法的復(fù)雜度，以異或操作、行交換的總數(shù)作為指標(biāo)，RSD的參數(shù)選為δ=0.05，c=0.1。3種算法均在剛接收到符號(hào)時(shí)就開始譯碼?？梢钥闯?，BP算法的復(fù)雜度是最低的，與k成線性增長(zhǎng)。而incGE的復(fù)雜度最高，相比之下，NEGE的復(fù)雜度明顯降低。若對(duì)于接收方來(lái)說(shuō)，計(jì)算能力能夠支持高斯消元的負(fù)擔(dān)，同時(shí)最大限度地降低譯碼開銷，那么提出的NEGE是一個(gè)不錯(cuò)的選擇。

圖3 BP,incGE,NEGE的復(fù)雜度

3 結(jié)束語(yǔ)

提出了非階梯化的高斯消元算法，在選擇某一行作為基準(zhǔn)行對(duì)其他行進(jìn)行消除時(shí)，采取了選擇權(quán)重最小行的策略，該策略減小了后續(xù)行操作的數(shù)量，相比原始的高斯消元，復(fù)雜度大大減小。當(dāng)BP算法遇到停止集無(wú)法繼續(xù)進(jìn)行時(shí)，提取出未處理的符號(hào)，進(jìn)行非階梯化高斯消元，簡(jiǎn)化后的連接關(guān)系使得再次BP譯碼成為可能。從而對(duì)LT碼譯碼，能夠顯著降低譯碼開銷，使得度分布的設(shè)計(jì)在該算法下居于次要。在接收端計(jì)算能力能夠保證的前提下，NEGE算法是一種較好的選擇。