LT編譯碼算法的DSP實現(xiàn)

師 歌，高宏峰

(河南科技大學(xué)電子信息工程學(xué)院，河南 洛陽 471000)

LT(Lucy Transform)碼是第一類基于糾刪碼技術(shù)的高效率無碼率碼[1]，同時也是第一類Fountain碼。Fountain碼的設(shè)計思想來源于水噴泉:服務(wù)器可以隨機生成編碼信息包，一個客戶端從一個或者多個服務(wù)器接收編碼包，一旦接收到足夠的編碼包N就可以重構(gòu)出源信號，N的數(shù)量與信道特性無關(guān)。Fountain碼的特性決定其十分適合用于計算機網(wǎng)絡(luò)、廣播信道、無線傳感器網(wǎng)絡(luò)等信道的信息傳輸。2003年Lucy提出LT碼[2]，LT碼對于具有不同刪除概率的各種刪除信道均是逼近最優(yōu)的。

鑒于DSP技術(shù)精度高、速度快、成本低、靈活性強、可靠性好的特點，DSP技術(shù)被越來越多地運用于信道編碼領(lǐng)域。通過研究，Turbo 碼[3]、卷積碼[4]、LDPC 碼[5]等大部分早期碼的編譯碼器都通過DSP等技術(shù)得以實現(xiàn)。但由于LT編譯碼器的數(shù)據(jù)運算量和內(nèi)存使用量隨編碼長度的增加而快速增大[6]，使用DSP技術(shù)實現(xiàn)LT碼編譯碼器必須要解決兩個難題:1)如何設(shè)計編譯碼算法，簡化程序，減少CPU負擔(dān);2)如何建立信息儲存機制，存儲度鄰接信號表，合理利用DSP芯片片上內(nèi)存資源。

本文使用反饋控制信號，控制編碼信號的碼長，降低編碼器功耗;引入冗余信息處理程序，剔除編碼信號中的冗余，提高LT譯碼效率;建立度鄰接信號表的位置系數(shù)儲存機制，合理存儲度鄰接信號信息，減少DSP芯片片上內(nèi)存使用量。最終采用TI公司的TMS320VC5416芯片，在CCS(Code Composer Studio)集成開發(fā)環(huán)境下使用C語言編程[7]，設(shè)計和實現(xiàn)了LT編譯碼器。

1 LT編譯碼算法的DSP硬件實現(xiàn)

本文采用TI公司的TMS320VC5416芯片，整個系統(tǒng)的硬件結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)的硬件結(jié)構(gòu)框圖

在編碼器中，源信號通過串口(RS－232接口)傳入芯片。由于數(shù)據(jù)采用異步傳輸，可以采用DSP的McBSP結(jié)合DMA，在不擴展硬件的情況下，用軟件實現(xiàn)異步數(shù)據(jù)傳輸。但該方法軟件設(shè)計復(fù)雜，加大了CPU的負擔(dān)，因此添加TI公司的TL16C550異步串行通信收發(fā)器來實現(xiàn)異步數(shù)據(jù)傳輸。此外，使用TI公司的雙路低壓差電源調(diào)節(jié)器芯片TPS767D301給TMS320VC5416芯片供電，使用TI公司的Flash芯片AM29LV800保存編譯碼程序段，以便在系統(tǒng)啟動時將編(譯)碼程序裝載進DSP內(nèi)部DARAM運行。

譯碼器從通信信道異步接收到編碼信號后進行譯碼。譯碼過程中譯碼器通過通信信道發(fā)送反饋信息給編碼器，控制編碼器的工作。

2 LT編譯碼法的DSP軟件實現(xiàn)

2.1 LT編碼算法的DSP軟件實現(xiàn)

圖2為LT編碼算法的軟件流程圖。編碼器接收到k個信源信號后，根據(jù)信道刪除率設(shè)定編碼信號的數(shù)量N=B×k，1.0＜B＜2.0。根據(jù)穩(wěn)健弧波分布確定N個編碼信號的度值，隨機均勻選擇每個編碼信號的度鄰接信號，異或運算得到N個編碼信號，通過通信信道發(fā)送。

圖2 LT編碼算法的軟件流程圖

2.1.1 反饋控制信號ACK

使用反饋控制信號ACK，控制編碼器工作。ACK由譯碼器判定生成，初值設(shè)定為ACK=0。

當(dāng)譯碼器未成功譯碼時，譯碼器生成ACK=1，反饋到編碼器。編碼器在接收到ACK=1信號后，根據(jù)信源信號碼長k確定添加N=b ×k，0.01≤b≤0.10 個編碼信號。

當(dāng)譯碼算法結(jié)束，ACK=0，編碼器停止工作，LT編譯碼算法結(jié)束。

2.1.2 編碼信號度值的確定

穩(wěn)健弧波分布(Robust Soliton distribution)μ(k)是LT編譯碼算法中普遍使用的度分布函數(shù)。其將理想弧波分布ρ(i)和補充分布τ(i)相結(jié)合，并且通過統(tǒng)一化處理得到。如式(1)～(4)所示

根據(jù)穩(wěn)健弧波分布確定編碼信號的度分布率函數(shù)μ(k)。根據(jù)μ(k)將時隔[0，1]劃分成非重復(fù)且不等的k個子時隔，每個子時隔與每個度值一一對應(yīng)[8]。例如:0.0 ～μ(1)對應(yīng)度值1，μ(i)～μ(i+1)對應(yīng)度值 i+1。

本文使用srand函數(shù)設(shè)置隨機數(shù)發(fā)生器的初始化種子seed=s1。當(dāng)?shù)谝淮紊删幋a信號時，使用rand函數(shù)生成[0，1]區(qū)間長度為N的隨機數(shù)列。確定隨機數(shù)列中第i項值所處的子時隔，根據(jù)對應(yīng)關(guān)系確定第i個編碼信號的度值di。記M為添加編碼信號的次數(shù)，T為已生成的編碼信號的數(shù)量，T=B×k+(M－1)×b×k。當(dāng)添加編碼信號時生成[0，1]區(qū)間長度為T+N的隨機數(shù)列，確定隨機數(shù)列中第T+i項值所處的子時隔，根據(jù)對應(yīng)關(guān)系確定新加的第i個編碼信號的度值di。

2.1.3 編碼信號度鄰接信號的確定

編碼信號的度鄰接信號從k個信源信號中隨機均勻選擇，所以隨機均勻選擇的效果將直接影響到LT編譯碼算法的效率。

設(shè)置隨機數(shù)發(fā)生器的初始化種子seed=s2(s1≠s2)，當(dāng)?shù)谝淮紊删幋a信號時，生成[0，k]區(qū)間長度為di的不重復(fù)隨機數(shù)列{adi}。取出{adi}中第ai(i=1，2，…，di)個信源信號做為該編碼信號的度鄰接信號。當(dāng)添加編碼信號時，記前T個編碼信號的度值總和為n，先生成[0，k]區(qū)間長度為n的不重復(fù)隨機數(shù)列，再生成[0，k]區(qū)間長度為di的不重復(fù)隨機數(shù)列{bdi}。取出{bdi}中第bi(i=1，2，…，di)個信源信號做為該編碼信號的度鄰接信號。

2.2 LT譯碼算法的DSP軟件實現(xiàn)

在發(fā)送端和接收端建立seed表，接收端在接收編碼分組后根據(jù)seed表序列號確定seed值，進而得到編碼信號的度和度鄰接信號表，進行譯碼。圖3為LT譯碼算法的軟件流程圖。

將編碼信號及其度鄰接信號表存儲后，根據(jù)反饋控制信號ACK，對新添加的編碼信號及其度鄰接信號表進行冗余信號處理。尋找度為1的編碼信號開始進行譯碼。當(dāng)編碼信號被釋放后，刪除該編碼信號及其度鄰接信號表。重復(fù)以上步驟，至度為1的編碼信號耗盡。如信源信號未被完全恢復(fù)，則生成反饋控制信號ACK=1，編碼器添加編碼信號。

圖3 LT譯碼算法的軟件流程圖

2.2.1 度鄰接信號表的位置系數(shù)存儲機制

在LT譯碼算法中，存儲編碼信號的度鄰接信號表占用了大量的DSP芯片片上內(nèi)存空間，所以采用合理的度鄰接信號表存儲機制，可以減少DSP芯片片上內(nèi)存使用量。

若不經(jīng)處理直接對度鄰接信號表進行存儲，1個16 bit的整形數(shù)據(jù)中僅能存儲1位度鄰接信號表信息，對DSP片上內(nèi)存空間造成了極大浪費，極大地限制了信源信號數(shù)量k的選擇范圍。

為了克服原始存儲機制的缺點，可使用二進制位存儲機制。通過位操作在16 bit的整型數(shù)據(jù)中存儲16位的度鄰接信號表信息。這樣能夠?qū)⒋鎯Χ揉徑有盘柋硭璧膬?nèi)存縮小為原先的1/16左右。但當(dāng)k值較大時，使用該存儲機制存儲仍需占用很大的存儲空間。例如，當(dāng)k=1024時，每一個編碼信號的度鄰接信號表都需要占用約64×16 bit的內(nèi)存空間。

根據(jù)文獻[2]所述，編碼信號的平均度為

式中:當(dāng)k值較大時，編碼信號的度小于k/16，所以通過存儲度鄰接信號的位置系數(shù)可以減小度鄰接信號表的存儲空間。本文使用位置系數(shù)存儲機制將將每個編碼信號的度鄰接信號位置系數(shù)按順序存儲。

通過使用位置系數(shù)存儲機制，減小了用于儲存編碼信號度鄰接信號表的內(nèi)存，提高了可選信源信號數(shù)量k的上限值。表1為3種度鄰接信號表存儲機制的性能參數(shù)。采用二進制存儲機制可以在原始存儲機制的基礎(chǔ)上提高k的上限4倍，而采用位置系數(shù)存儲機制又可以在二進制存儲機制的基礎(chǔ)上再提高k的上限3倍。

表1 3種度鄰接信號表存儲機制的性能參數(shù)

2.2.2 冗余信息處理程序

當(dāng)ACK=1時，譯碼程序已經(jīng)恢復(fù)了部分源信號，新添加的編碼信號帶有冗余信息，需要進行處理，刪除冗余信息，提高節(jié)點攜帶信息質(zhì)量，加快譯碼算法。

經(jīng)過譯碼，信源信號si已經(jīng)被恢復(fù)。譯碼端接收到N個新編碼信號，其中一部分編碼信號攜帶了信源信號si的信息(該編碼信號的度鄰接信號表中存儲有信源信號si的位置系數(shù)i)，則將該編碼信號與源信號si進行異或運算，并將其度鄰接信號表中的位置系數(shù)i置0。重復(fù)上述操作，至N個新編碼信號及其度鄰接信號表都得到處理。

3 實驗數(shù)據(jù)與結(jié)論

圖4 LT譯碼器譯碼碼長的分布柱狀圖

本文設(shè)置信源信號數(shù)量 k=1536，c=0.01，δ=0.05，B=1.05，b=0.01，即第一次生成編碼信號數(shù)量為 N=1.05×k≈1612，添加的編碼信號數(shù)量為 N=0.01 × k≈15，進行100次實驗。

圖4顯示了該LT譯碼器譯碼碼長N的分布柱狀圖。通過觀察發(fā)現(xiàn)，譯碼碼長集中于1672～1717，當(dāng)N的值增加至1717時，LT譯碼器的譯碼成功率達到了86%。通過分析，修改設(shè)置 B=1.12，b=0.01，可以在不添加編碼信號的情況下使譯碼器以很高的概率恢復(fù)信源信號，降低譯碼延時，提高LT碼的傳輸效率。

圖5顯示當(dāng)B=1.12，b=0.01時LT譯碼器譯碼成功率與添加編碼信號次數(shù)M的關(guān)系曲線。通過觀察發(fā)現(xiàn)當(dāng)?shù)谝淮紊删幋a信號的數(shù)量為N=1.12×k≈1720時，譯碼成功率已經(jīng)達到89%，即使譯碼不成功也只需添加很少數(shù)量的編碼信號就能保證譯碼成功率達到100%。通過計算得到，通過重新設(shè)置，當(dāng)信源信號長度k=1536時，LT譯碼器譯碼碼長的均值為1726，編碼效率達到0.890。

圖5 譯碼成功率與添加編碼信號次數(shù)的關(guān)系曲線

4 結(jié)論

本文使用反饋控制信號，控制編碼信號的長度，降低了LT編碼算法功耗;使用C語言函數(shù)生成隨機數(shù)列，改善了編碼信號的度和度鄰接信號的隨機選擇效果;建立位置系數(shù)儲存機制、縮小了儲存信息所需的DSP芯片片上內(nèi)存空間，提高了LT編譯碼器的性能;引入冗余信息處理程序，剔除編碼信號的冗余，提高了譯碼效率。通過實驗表明，當(dāng)信源信息碼長為1536時，本文提出的基于DSP技術(shù)實現(xiàn)的LT編譯碼算法的譯碼碼長均值為1726，編碼效率為0.890。

[1]MACKAY D J C.Fountain codes[C]//Proc.IEEE Communications.[S.l.]:IEEE Press，2005:1062－1068.

[2]LUBY M.LT Codes[C]//Proc.43rd Annual IEEE Symposium on Foundations of Computer Science.[S.l.]:IEEE Press，2002:271－280.

[3]彭玉吉.Turbo碼編譯碼技術(shù)的研究及DSP實現(xiàn)[D].成都:電子科技大學(xué)，2007.

[4]張博.卷積碼的譯碼研究及DSP實現(xiàn)[D].天津:天津大學(xué)，2008.

[5]陳蓉.LDPC編譯碼的DSP實現(xiàn)[D].蘇州:蘇州工業(yè)大學(xué)，2009.

[6]侯登峰，朱曉晶，崔慧娟，等.Raptor碼在TMS320C55X DSP上的實現(xiàn)及優(yōu)化[J].電視技術(shù)，2010，34(S2):26－30.

[7]張勇.C/C++語言硬件程序設(shè)計——基于TMS320C5000系列DSP[M].西安:西安電子科技大學(xué)出版社，2003.

[8]ZHOU Qian，CHEN Zengqiang.Application of chaos in digital fountain codes[C]//Proc.the 9th International Conference for Young Computer Scientists.[S.l.]:IEEE Press，2008:2786－2791.