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

師 歌，高宏峰

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 反饋控制信號(hào)ACK

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

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

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

2.1.2 編碼信號(hào)度值的確定

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

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

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

2.1.3 編碼信號(hào)度鄰接信號(hào)的確定

編碼信號(hào)的度鄰接信號(hào)從k個(gè)信源信號(hào)中隨機(jī)均勻選擇，所以隨機(jī)均勻選擇的效果將直接影響到LT編譯碼算法的效率。

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

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

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

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

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

2.2.1 度鄰接信號(hào)表的位置系數(shù)存儲(chǔ)機(jī)制

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

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

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

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

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

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

表1 3種度鄰接信號(hào)表存儲(chǔ)機(jī)制的性能參數(shù)

2.2.2 冗余信息處理程序

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

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

3 實(shí)驗(yàn)數(shù)據(jù)與結(jié)論

圖4 LT譯碼器譯碼碼長(zhǎng)的分布柱狀圖

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

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

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

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

4 結(jié)論

本文使用反饋控制信號(hào)，控制編碼信號(hào)的長(zhǎng)度，降低了LT編碼算法功耗;使用C語(yǔ)言函數(shù)生成隨機(jī)數(shù)列，改善了編碼信號(hào)的度和度鄰接信號(hào)的隨機(jī)選擇效果;建立位置系數(shù)儲(chǔ)存機(jī)制、縮小了儲(chǔ)存信息所需的DSP芯片片上內(nèi)存空間，提高了LT編譯碼器的性能;引入冗余信息處理程序，剔除編碼信號(hào)的冗余，提高了譯碼效率。通過(guò)實(shí)驗(yàn)表明，當(dāng)信源信息碼長(zhǎng)為1536時(shí)，本文提出的基于DSP技術(shù)實(shí)現(xiàn)的LT編譯碼算法的譯碼碼長(zhǎng)均值為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實(shí)現(xiàn)[D].成都:電子科技大學(xué)，2007.

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

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

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

[7]張勇.C/C++語(yǔ)言硬件程序設(shè)計(jì)——基于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.