一種適用于嵌入式平臺的Raptor碼算法

梁 斌

（中國電子科技集團公司第五十四研究所，河北 石家莊 050081）

一種適用于嵌入式平臺的Raptor碼算法

梁 斌

（中國電子科技集團公司第五十四研究所，河北 石家莊 050081）

針對Raptor編／譯碼器在衛(wèi)星通信工程應(yīng)用中運算量過大的不足，提出一種新的稀疏矩陣方程求解算法。采用該算法求解Raptor編／譯碼方程，可簡化求解步驟。與3GPP描述的Raptor碼求解算法相比，該算法可有效降低基于嵌入式平臺的Raptor編／譯碼器的運算時間，滿足了實際工程中對時延限制和設(shè)備小型化的需求。

噴泉碼；Raptor碼；前向糾錯；嵌入式

0 引言

Raptor碼［1］是一種新型噴泉碼［2］，由shokrollahi于2006年提出。與此前Luby提出的噴LT碼（Luby Transform）［3］相比，Raptor碼具備更好的編譯碼性能［4］。因此，它被3GPP選定為多媒體組播多播服務(wù)（MultimediaBroadcast／Multicast Service，MBMS）中的前向糾錯（Forward Error Correc-tion，F(xiàn)EC）算法［5］。在通信設(shè)備中常用的嵌入式平臺上直接使用3GPP標(biāo)準(zhǔn)中的Raptor編／譯碼算法，由于其編譯碼過程的運算量大，且CPU性能有限，導(dǎo)致運算時間延遲過大，無法滿足需求。

為解決此問題，本文提出一種新的稀疏矩陣求解算法，對3GPP標(biāo)準(zhǔn)的Raptor編／譯碼算法中的計算量最大的方程系數(shù)矩陣降階過程進行優(yōu)化，使其能夠滿足工程應(yīng)用。

1 Raptor編譯碼原理

Raptor碼編碼和譯碼過程如圖1所示。Raptor編譯碼運算的基本單位為符號。符號指長度為若干比特的定長數(shù)據(jù)塊。

圖1 Raptor碼編譯碼過程

Raptor編碼過程可分為預(yù)編碼和LT編碼。在預(yù)編碼過程中，輸入的數(shù)據(jù)塊被分割為1～k個符號，并通過編碼矩陣運算轉(zhuǎn)化為中間符號。LT編碼過程則根據(jù)中間符號和編碼符號ID（Encoded Symbol ID，ESI）產(chǎn)生1～m個編碼符號。因噴泉碼為無率碼，m理論上可取無窮大的整數(shù)。在實際應(yīng)用中，則根據(jù)信道狀況確定m的取值。

編碼符號序列通過刪除信道后進入Raptor譯碼器。Raptor譯碼過程同樣可分為預(yù)譯碼和LT譯碼。預(yù)譯碼過程將收到的編碼符號序列恢復(fù)成中間符號。因Raptor碼為系統(tǒng)碼，前k個編碼符號與原始數(shù)據(jù)相同。LT譯碼過程只需根據(jù)中間符號生成1～k個編碼符號，即可恢復(fù)原始數(shù)據(jù)。

Raptor預(yù)編／譯碼過程可等價為模2線性方程組求解。其編／譯碼線性方程組的系數(shù)矩陣即為Raptor編／譯碼矩陣。3GPP推薦的Raptor編碼矩陣由LDPC［6，7］矩陣、Half矩陣、單位陣和前k個符號對應(yīng)的偽隨機數(shù)向量組成，其整體為一個方陣；譯碼矩陣則由LDPC［7，8］矩陣、Half矩陣、單位陣和n個偽隨機向量組成，其整體為一個長方形矩陣。其中n為1～m個編碼符號通過刪除信道后，被譯碼器接收到的符號個數(shù)。Raptor預(yù)編／譯碼過程就是將編／譯碼矩陣轉(zhuǎn)換為單位陣的過程。此操作完成后，中間符號就會被求取出來。然后，LT編碼過程則根據(jù)中間符號和ESI信息，通過一系列運算和查表操作，生成該ESI對應(yīng)的編碼符號。

由線性代數(shù)相關(guān)知識可知，線程方程組有解的充要條件是其系數(shù)矩陣滿秩。Raptor編碼矩陣的產(chǎn)生規(guī)則可保證其必然為滿秩方陣。但是Raptor譯碼矩陣與接收符號對應(yīng)的向量相關(guān)，因而導(dǎo)致其不一定滿秩。如譯碼矩陣不滿秩，則Raptor譯碼失敗。因此，Raptor譯碼存在失敗概率。人們經(jīng)過長期試驗，總結(jié)出Raptor碼譯碼失敗概率為：

式中，n為譯碼器收到的編碼符號數(shù)量；k為編碼原始數(shù)據(jù)包含的符號數(shù)量。當(dāng)n＜k的時候，譯碼矩陣的行數(shù)低于列數(shù)，必然不滿秩，譯碼失敗概率為1。當(dāng)n≥k的時候，譯碼系數(shù)矩陣行數(shù)大于等于列數(shù)，矩陣有可能滿秩。隨著（n－k）的增加，Raptor碼的譯碼失敗概率會降低。當(dāng)（n－k）＝30時，譯碼失敗概率為10－9量級。因此，要保證譯碼成功率，必須確保一定的接收符號冗余量。

由此不難發(fā)現(xiàn)，k越大，冗余量在接收符號中所占的比例（n－k）／n就越小，Raptor碼的傳輸效率就越高。單從這個角度看，Raptor碼的k取值越大越好。但隨著k的增加，編／譯碼矩陣也就變得越來越大，進而導(dǎo)致預(yù)編／譯碼的方程求解過程變的更加復(fù)雜。導(dǎo)致運算時間增加，編譯碼時間延遲增大，數(shù)據(jù)吞吐量降低。與之相比LT編碼過程的計算量幾乎可以忽略不計。因此，優(yōu)化Raptor編譯碼過程的重點是優(yōu)化預(yù)編／譯碼過程，而優(yōu)化預(yù)／編譯碼過程的本質(zhì)則是優(yōu)化模2線性方程組的求解過程，使用盡量少的步驟求解出Raptor編／譯碼方程。

2 3GPP描述的矩陣求解算法

求解線性方程組的基本方法是高斯消元法。但是直接使用高斯消元法求解方程組的復(fù)雜度非常高，約為k的3次方量級。且整個過程為串行處理過程，難以使用并行處理的方法提高效率。

為了解決編譯碼性能和計算復(fù)雜度的矛盾，3GPP提出了一種較為高效的求解方法。它利用Raptor編／譯碼矩陣為稀疏矩陣，先將其降階，然后再進行高斯消去，進而達(dá)到降低運算復(fù)雜度的目的。該處理過程如下［9］：令方程系數(shù)矩陣為A。定義行重為矩陣A某一行包含的1的個數(shù)。r為矩陣A中的非零最小行重值。如圖2（a）所示，令矩陣V＝A。令矩陣U為空矩陣。按照如下步驟運算，逐漸將矩陣V轉(zhuǎn)換成圖2（b）所示的分塊矩陣狀況。

圖2 3GPP算法求解示意

步驟1：在矩陣V中查找r最小的行。如果r≠2，則任選一行；如果r＝2，任選包含在矩陣V誘導(dǎo)的二分圖G中的最大尺度環(huán)的1行。

步驟2：將前一部中所選的行與V中的第1行進行交換，且V中的列進行重排，重排后的非零元素除了第1個放置在首列以外，其他非零元素全部放置在V的后部。

步驟3：V中的首列非零的行與首行執(zhí)行行加減操作，以使得V中除了第1行外的首列全部變成0。

步驟4：V的各行尾部元素移入矩陣U。跳回到步驟1。

此算法反復(fù)執(zhí)行后，使矩陣V逐漸變小直至消失，變?yōu)閳D2（c）所示狀況。將矩陣U的元素可劃分為矩陣UU和矩陣Ul，如圖2（d）所示，。Ul即為降階產(chǎn)生的稠密矩陣。使用高斯消去求解出Ul，然后用該結(jié)果求解出UU。最終求解中所有的結(jié)果。

本算法在X86平臺運行的效果尚可，但移植到嵌入式平臺后，因嵌入式CPU的處理能力有限，導(dǎo)致其數(shù)據(jù)吞吐量大幅降低，編譯碼時間顯著增加。要開發(fā)出具有實用價值的Raptor編／譯碼，必須對該算法進行優(yōu)化改進。

3 基于分組法降階的矩陣求解算法

線性方程組總是存在一個最優(yōu)求解步驟，依照該步驟對各行進行消元操作，可以用最少的步驟求解出方程。在每一步運算中，需執(zhí)行2個操作：決策和消元。3GPP算法在嵌入式平臺上之所以效率明顯降低，是因為其決策過程過于復(fù)雜。例如矩陣V誘導(dǎo)的二分圖G中的最大尺度環(huán)的求取過程，涉及了大量查找和排序操作。要降低決策時間，必須設(shè)法在不進行查找及排序的情況下完成決策過程。

分組求解法正是基于此思路設(shè)計，以分組代替排序和查找。先求解出一些易于求解的變量，當(dāng)求解決策代價增加到一定程度后，就放棄決策，改用高斯消元處理剩余方程。其基本步驟如下：

步驟1 如圖3（a）所示，以r為依據(jù)對矩陣各行分組r＝1組中的行每行只包含一個非零系數(shù)。r＝2組中的行包含2個非零系數(shù)。其余各行分為2組，即設(shè)定一個界限值Min，r小于等于該界限值的行組成r≤Min組。r大于該界限值的行組成r＞Min組。設(shè)置2個空組為最終組和接近最終組。

步驟2 如圖3（b）所示，指定r＝1組中的一行為操作行。用該行對其他各行進行行加減操作。如被處理行的r變化，則將其歸入對應(yīng)組。操作行歸入最終組。直到r＝1組中無元素。

步驟3 如圖3（c）所示，指定r＝2組中的一行為操作行。用該行對其他各行進行行加減操作。如被處理行的r變化，則將其歸入對應(yīng)組。操作行歸入接近最終組。如出現(xiàn)r＝1的行，則執(zhí)行步驟2。直到r＝2組中無元素。

步驟4 如圖3（d）所示，指定r≤Min組中的一行為操作行。用該行對其他各行進行行加減操作。如被處理行的r變化，則將其歸入對應(yīng)組。操作行歸入接近最終組。如出現(xiàn)r＝1的行，則執(zhí)行步驟2。如出現(xiàn)r＝2的行，則執(zhí)行步驟3。直到r≤Min組中無元素。

步驟5 如圖3（e）所示，用高斯消元法求解r＞Min組中的方程。

步驟6 如圖3（f）所示，用步驟5的結(jié)果求解接近最終組，進而求解出全部結(jié)果。

圖3 分組法求解示意

4 2種求解算法的比較

因節(jié)省了查找和排序時間，分組法的矩陣降階速度比3GPP算法快。但是分組法的產(chǎn)生的稠密矩陣比3GPP大。通過控制k和調(diào)整Min的取值，分組求解算法可保證其在嵌入式平臺上的處理時間滿足吞吐量指標(biāo)和時間延遲的要求。

分組求解算法的決策代價較低，可用行加減次數(shù)來衡量算法的運算復(fù)雜度。以k＝200為例，使用高斯消元法，需要執(zhí)行約16 000次行加減操作，而使用分組法只需要執(zhí)行5 125次行加減操作。分組法求解法較高斯消元法的計算效率明顯提高。

與3GPP算法相比，由于分組求解法的決策過程簡單，使得其在實際運算中的整體耗時有所降低。在計算機模擬測試中，k值取512及以下參數(shù)中，分組法的數(shù)據(jù)處理能力普遍高于3GPP算法，而在嵌入式平臺上，分組求解法的優(yōu)勢更加明顯。

分組求解法在S3C6410上運行的結(jié)果打印如圖4所示。S3C6410是三星公司生產(chǎn)的一款基于ARM11體系結(jié)構(gòu)的精簡指令集處理器［10］，其運算能力并不突出。采用分組法算法，k取320，編碼符號長度為31 bytes，編碼420個符號的情況下，S3C6410芯片可在60 ms左右時間完成Raptor碼編碼操作。該速度較基于3GPP算法的程序約提高了2倍左右。

圖4 S3C6410計算k＝320矩陣的結(jié)果

5 結(jié)束語

本文介紹的適用于嵌入式平臺的Raptor碼算法，有效降低了Raptor編譯碼算法中矩陣降階的運算復(fù)雜度，進而降低了總運算時間，使得在嵌入式CPU上，能夠?qū)崿F(xiàn)較高速度，較低時延的Raptor編／譯碼運算邏輯。這使得Raptor碼編譯碼器的硬件體積顯著降低，能夠方便地集成在設(shè)備中。該算法為Raptor編／譯碼技術(shù)的應(yīng)用與推廣提供了一種可行的解決方案。

［1］SHOKROLLAHI A.Raptor Codes［R］.Digital Fountain，Technical Report，2003：1－37.

［2］LUBY M，MITZENMACHER M，SHOKROLLAHI A.Prac-tical Loss-resilient Codes［C］∥Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science，1997：150－159.

［3］LUBY M.LT-codes［C］∥Proceedings of the 43rd Annual IEEESymposiumontheFoundationsofComputer Science，2002：271－280.

［4］LUBY M，MITZENMACHER M，SHOKROLLAHI A，et al.Efficient Erasure Correcting Codes［J］.IEEE Transa-ction on Information Theory，2001，47（2）：569－584.

［5］3GPP TS 26.346 V7.0.0.Technical Specification Group Services and System Aspects：Multimedia Broadcast／Mul-ticast Service：Protocols and Codes［S］，2007.

［6］吳 瓊，梅進杰.改進Min sum的LDPC譯碼算法研究［J］.無線電通信技術(shù)，2012，38（2）：27－29.

［7］陳遠(yuǎn)友.一種用于短猝發(fā)通信的LDPC短碼設(shè)計［J］.無線電通信技術(shù)，2014，40（1）：32－33.

［8］趙建功，劉香玲.準(zhǔn)循環(huán)LDPC碼的部分并行譯碼算法［J］.無線電工程，2012，42（2）：55－57.

［9］3GPP TS 26.346 version 6.3.0.FEC encoder specification［S］，2005.

［10］孫連文，朱正禮，馬艷婷.基于S3C6410處理器的嵌入式Linux系統(tǒng)的構(gòu)建［J］.計算機與現(xiàn)代化，2013（11）：155－157.

A Raptor Code Algorithm for Embedded Platform

LIANG Bin
（The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China）

To solve the problem that the calculations of Raptor encoder／decoder is too complex to apply in satellite communication project，a novel sparse matrix rank reduction method is proposed.The method used to solve Raptor encoding／decoding equation can sim-plify the process of solution.Compared with the algorithm recommended by 3GPP，the method can effectively reduce the running time of Raptor encoder／decoder based on embedded platform，and can meet the requirements of time delay and equipment miniaturization in practical engineering.

fountain codes；Raptor code；FEC；embedded

TP391.4

A

1003－3106（2015）10－0077－04

10.3969／j.issn.1003－3106.2015.10.21

梁 斌.一種適用于嵌入式平臺的Raptor碼算法［J］.無線電工程，2015，45（10）：77－80.

梁 斌男，（1982—），碩士，工程師。主要研究方向：衛(wèi)星通信與廣播電視。

2015-07-28