梁 斌

（中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081）

一種適用于嵌入式平臺(tái)的Raptor碼算法

梁 斌

（中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081）

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

噴泉碼；Raptor碼；前向糾錯(cuò)；嵌入式

0 引言

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

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

1 Raptor編譯碼原理

Raptor碼編碼和譯碼過(guò)程如圖1所示。Raptor編譯碼運(yùn)算的基本單位為符號(hào)。符號(hào)指長(zhǎng)度為若干比特的定長(zhǎng)數(shù)據(jù)塊。

圖1 Raptor碼編譯碼過(guò)程

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

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

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

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

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

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

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

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

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

圖2 3GPP算法求解示意

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

步驟2：將前一部中所選的行與V中的第1行進(jìn)行交換，且V中的列進(jìn)行重排，重排后的非零元素除了第1個(gè)放置在首列以外，其他非零元素全部放置在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平臺(tái)運(yùn)行的效果尚可，但移植到嵌入式平臺(tái)后，因嵌入式CPU的處理能力有限，導(dǎo)致其數(shù)據(jù)吞吐量大幅降低，編譯碼時(shí)間顯著增加。要開(kāi)發(fā)出具有實(shí)用價(jià)值的Raptor編／譯碼，必須對(duì)該算法進(jìn)行優(yōu)化改進(jìn)。

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

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

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

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

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

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

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

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

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

圖3 分組法求解示意

4 2種求解算法的比較

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

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

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

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

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

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

本文介紹的適用于嵌入式平臺(tái)的Raptor碼算法，有效降低了Raptor編譯碼算法中矩陣降階的運(yùn)算復(fù)雜度，進(jìn)而降低了總運(yùn)算時(shí)間，使得在嵌入式CPU上，能夠?qū)崿F(xiàn)較高速度，較低時(shí)延的Raptor編／譯碼運(yùn)算邏輯。這使得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］吳 瓊，梅進(jìn)杰.改進(jìn)Min sum的LDPC譯碼算法研究［J］.無(wú)線電通信技術(shù)，2012，38（2）：27－29.

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

［8］趙建功，劉香玲.準(zhǔn)循環(huán)LDPC碼的部分并行譯碼算法［J］.無(wú)線電工程，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］.計(jì)算機(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

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

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

2015-07-28