一種多進(jìn)制噴泉碼短碼的編譯碼方法

陳莉華

（北京理工大學(xué)出版社有限責(zé)任公司，北京 100081）

?

一種多進(jìn)制噴泉碼短碼的編譯碼方法

陳莉華

（北京理工大學(xué)出版社有限責(zé)任公司，北京 100081）

摘 要：噴泉碼在碼長(zhǎng)較長(zhǎng)時(shí)，采用復(fù)雜度與碼長(zhǎng)呈近線(xiàn)性關(guān)系的置信傳播譯碼，可靠性接近香農(nóng)限，編碼效率接近1。由于噴泉碼在編碼效率和譯碼復(fù)雜度方面具有優(yōu)勢(shì)，因而在多媒體廣播多播、分布式存儲(chǔ)、容遲容斷網(wǎng)絡(luò)等領(lǐng)域得到廣泛應(yīng)用。但基于二進(jìn)制的傳統(tǒng)噴泉編碼，為了獲得較好的譯碼性能和編碼效率，碼長(zhǎng)比較長(zhǎng)，一般都需要達(dá)到幾千甚至幾萬(wàn)個(gè)符號(hào)；應(yīng)用于短文件的存儲(chǔ)、傳輸，編碼效率大為下降，帶來(lái)存儲(chǔ)和效率的急劇下降。文章介紹了一種多進(jìn)制噴泉編譯碼，其效率與二進(jìn)制編碼相比，在效率和性能方面得到顯著提升，但譯碼復(fù)雜度僅略有上升。

關(guān)鍵詞：噴泉碼短碼；LT碼；Raptor碼

1　概述

數(shù)字噴泉碼是一種應(yīng)用于刪除信道的糾錯(cuò)編碼技術(shù)，其典型應(yīng)用多媒體廣播多播、分布式存儲(chǔ)、容遲容斷網(wǎng)絡(luò)等［1］。該編碼的基本思想如下：在發(fā)送端，將需要發(fā)送的K個(gè)數(shù)據(jù)包進(jìn)行線(xiàn)性組合，按需生成N個(gè)編碼包；在接收端，接收到K個(gè)編碼包，求解線(xiàn)性方程組就可以求出信源數(shù)據(jù)包。每一個(gè)傳輸?shù)木幋a包可嵌入包編號(hào)、CRC校驗(yàn)等。接收端檢查CRC即可獲知某編碼包是否被正確傳輸，因而信道可等效為刪除信道。采用偽隨機(jī)的方法選取編碼系數(shù)，接收端根據(jù)包編號(hào)即可生成編碼系數(shù)，恢復(fù)編碼方程，因而無(wú)須傳輸編碼系數(shù)?；诖?，不管接收到哪些編碼包，無(wú)論噴泉包的順序如何，接收端都可以求解線(xiàn)性方程組恢復(fù)原始數(shù)據(jù)。這好比人們使用杯子接水來(lái)喝，飲水者只關(guān)心杯子是否裝滿(mǎn)；至于哪些水滴接入杯中，則不必關(guān)心。

基于噴泉碼的基本思想，M.Luby和A.Shokrollahi分別提出了兩種實(shí)用的噴泉碼，即LT碼和Raptor碼。目前，LT碼已經(jīng)在無(wú)線(xiàn)組播、分布式存儲(chǔ)等多個(gè)領(lǐng)域得到應(yīng)用［2-5］。但目前實(shí)用的噴泉碼在碼長(zhǎng)很長(zhǎng)時(shí)，其譯碼復(fù)雜度、譯碼性能和編碼效率表現(xiàn)優(yōu)異。但對(duì)于短噴泉碼，這些性能表現(xiàn)不佳。例如，采用LT碼，如果希望編碼開(kāi)銷(xiāo)小于5%，則信源長(zhǎng)度需要10000以上。如果編碼長(zhǎng)度小于1000，則編碼開(kāi)銷(xiāo)高于30%。實(shí)際的有線(xiàn)通信、無(wú)線(xiàn)通信及文件存儲(chǔ)系統(tǒng)，長(zhǎng)度很短的信息、短文件比較多；這些短信息、短文件不太適合碼長(zhǎng)很長(zhǎng)的噴泉碼編碼?；诖耍疚慕榻B一種高效率的多進(jìn)制噴泉碼。這種編碼基于有限域，其效率與二進(jìn)制編碼相比，在效率和性能方面得到顯著提升，但譯碼復(fù)雜度僅略有上升。

2　多進(jìn)制噴泉碼的編碼

考慮二進(jìn)制編碼的線(xiàn)性方程組的系數(shù)矩陣只能選取0和1，因此希望矩陣的秩為K，比較有效的方法是增加方程組的數(shù)量N。這樣，當(dāng)碼長(zhǎng)較短時(shí)，增加N會(huì)造成編碼效率的下降。如果采用多進(jìn)制編碼，由于系數(shù)矩陣中每個(gè)元素的維度增加，容易達(dá)到滿(mǎn)秩?；诖耍捎枚噙M(jìn)制編碼可有效提高短碼的編碼效率。

對(duì)噴泉碼進(jìn)行編碼的方法如下：

選取非負(fù)整數(shù)di。一般地，該非負(fù)整數(shù)可基于魯棒孤子分布μ（d）隨機(jī)選取。稱(chēng)di為編碼符號(hào)Vi的編碼度。然后，隨機(jī)均勻地從K個(gè)信源符號(hào)中選di個(gè)符號(hào)，并基于有限域GF（q）隨機(jī)均勻地生成di個(gè)非零編碼系數(shù)。將選出的信源符號(hào)和這些非零系數(shù)對(duì)應(yīng)相乘，然后作和，就得到編碼符號(hào)Vi的值。

3　多進(jìn)制噴泉碼的譯碼算法

由上小節(jié)可知，多進(jìn)制噴泉編碼可表示成線(xiàn)性方程組w=A·m。只要矩陣A的秩為K，收到w=［w1，w2，…，wN］T后，譯碼器通過(guò)基于有限域GF（q）的高斯消元就能夠求解出信源矢量m=［m1，m2，…，wK］T，實(shí)現(xiàn)最大似然序列譯碼。但直接進(jìn)行高斯消元時(shí)，由于存在大量的行列置換及消元所需的乘法和加法運(yùn)算，復(fù)雜度為O（K2）到O（K3），難以實(shí)際應(yīng)用。事實(shí)上，注意到的w=A·m矩陣為稀疏矩陣。利用該特性，可大大降低譯碼復(fù)雜度?；诖?，給出低復(fù)雜度譯碼過(guò)程如下：

（1）對(duì)矩陣A進(jìn)行主元選擇。

主元選擇的步驟和常規(guī)的高斯消元法一致，包括K步前向迭代過(guò)程。在第K步，將第K行用（K，K）位置的元素歸一化，然后將該行的適當(dāng)倍數(shù)并疊加到下面各行，使下面各行第K列的元素全化成零。重復(fù)該過(guò)程K次，矩陣變成上三角形式。為了最小化局部填充元和局部操作量，選取最大填入和操作數(shù)最小的元素作為主元。

（2）主元原位高斯消元。

在常規(guī)的高斯消元法中，存在大量的行交換。由于行交換需要反復(fù)復(fù)制數(shù)據(jù)，造成譯碼計(jì)算和存儲(chǔ)量的上升。對(duì)于稀疏編碼矩陣，矩陣中存在大量的零元，這些零元參加運(yùn)算和存儲(chǔ)器的存取會(huì)造成存儲(chǔ)和計(jì)算資源的浪費(fèi)。實(shí)際上，不需要進(jìn)行實(shí)際的行列交換，用2K個(gè)存儲(chǔ)單元記錄迭代過(guò)程中主元行號(hào)和列號(hào)就可以了。

具體地，在迭代過(guò)程的每一步，基于稀疏存儲(chǔ)，每次消元，根據(jù)所存取的行，讀取非零元素，然后進(jìn)行消元操作，更新非零元素的存儲(chǔ)記錄。在此基礎(chǔ)上，根據(jù)步驟1選取主元，記錄其行號(hào)和列號(hào)。重復(fù)該過(guò)程，直到完成整個(gè)方程組的消元，將系數(shù)矩陣化為下三角矩陣。

最后，采用后向迭代，求解線(xiàn)性方程組w=A·m中的未知量m的元素，得到譯碼輸出序列m。這樣就完成了多進(jìn)制噴泉碼的編碼和譯碼過(guò)程。

4　仿真結(jié)果

采用魯棒孤子（Robust-Soliton）分布作為編碼度分布函數(shù)μ（d）。令信源長(zhǎng)度為K，設(shè)c和δ是滿(mǎn)足c＞0和c＜δ＜1的兩個(gè)參數(shù)，令其1n（x）表示自然對(duì)數(shù)。設(shè)d=1時(shí)，時(shí)，設(shè)當(dāng)時(shí)；當(dāng)d=K時(shí)，；對(duì)于其他的

為了說(shuō)明使用魯棒孤子分布選取編碼度時(shí)多進(jìn)制噴泉碼的性能，選取噴泉短碼長(zhǎng)度K=100，C=0.05，改變參數(shù)δ，編碼度采用魯棒孤子分布，使用多進(jìn)制噴泉碼編譯碼方法。選取q=2和q=16兩種情況。經(jīng)驗(yàn)證，在譯碼失敗概率為10-2時(shí)，碼長(zhǎng)為100的16進(jìn)制短碼，其編碼開(kāi)銷(xiāo)只需要5%。對(duì)于二進(jìn)制編碼，若實(shí)現(xiàn)這樣低的編碼開(kāi)銷(xiāo)，如第1節(jié)所述，其編碼長(zhǎng)度需要10000以上。

使用魯棒孤子分布，選取N=1250，K=1000，C=0.05，δ =0.05構(gòu)造二進(jìn)制和十六進(jìn)制的LT碼，基于稀疏矩陣的高斯消元法實(shí)現(xiàn)了最大似然序列譯碼。經(jīng)仿真驗(yàn)證，多進(jìn)制噴泉碼的最大似然譯碼遠(yuǎn)遠(yuǎn)快于常規(guī)的高斯消元法，計(jì)算復(fù)雜度僅為BP算法的4倍。作為比較，通過(guò)仿真驗(yàn)證常規(guī)的高斯消元法對(duì)該編碼譯碼的復(fù)雜度，發(fā)現(xiàn)采用常規(guī)高斯消元法時(shí)，計(jì)算復(fù)雜度為BP算法的170倍，不具實(shí)用價(jià)值。這說(shuō)明，多進(jìn)制噴泉碼比二進(jìn)制編碼在復(fù)雜度方面只略有提高，但短碼性能獲得顯著提升。

5　結(jié)語(yǔ)

二進(jìn)制噴泉碼在碼長(zhǎng)很長(zhǎng)時(shí)具有很高的效率和優(yōu)異的譯碼性能。但碼長(zhǎng)較短時(shí)，編碼效率急劇下降?；诖?，本文介紹了一種多進(jìn)制噴泉碼，給出了噴泉短碼的編碼，并利用編碼矩陣的稀疏特性，討論了主元原位消元和稀疏存儲(chǔ)和計(jì)算的低復(fù)雜度譯碼方法。經(jīng)仿真驗(yàn)證，與二進(jìn)制編碼相比，多進(jìn)制編碼在效率和性能方面得到顯著提升，但譯碼復(fù)雜度僅略有上升。

［參考文獻(xiàn)］

［1］LUBY M.CODES LT.In Proceeding of the 43rd Annual IEEE Symposium［J］.Foundations of Computer Science ，2002（10）：271-282.

［2］Mitzenmacher M.Digital Fountains:A Survey and Look Forward［J］.Information Theory Workshop，2004（10）：271-276.

［3］LUBY M.CODES LT.［J］.In Proceeding of the 43rd Annual Symposium［J］. Foundations of Computer Science，2002（6）：271-282.

［4］PALANKI R，Yedidia J S.Rateless codes on Noisy Channels［J］.International Symposium on Information Theory，2004（6）：1008-1010.

［5］CASTURA J，MAO Y.Rateless Coding over Fading Channels［J］.Communications Letters，2006（1）：46-48.

A Kind of Multi-band Fountain Code Short Code Decoding Method

Chen Lihua
（Beijing Institute of Technology Press，Beijing 100081，China）

Abstract:The fountain code when the code length is longer，the complexity and code length is nearly linear relationship of belief propagation decoding，reliability is close to shannon limit，coding efficiency is close to 1. Because of fountain codes have an advantage in terms of coding efficiency and decoding complexity，therefore in the multimedia broadcast multicast，distributed storage，let ChiRong broken network in areas such as widely used. But traditional fountain based on binary coding，in order to obtain better performance of decoding and encoding efficiency，code length is longer，usually need to reach thousands or even tens of thousands of symbols；Used in short file storage，transmission，coding efficiency decrease，bring the efficiency of storage and fell sharply. This paper introduces a fountain of multi-band compiled code，its efficiency compared with binary encoding，received a significant boost in terms of efficiency and performance，but only slightly higher decoding complexity.

Key words:fountain code short code；LT codes；raptor code

作者簡(jiǎn)介：陳莉華（1976-），女，北京，碩士；研究方向：通信技術(shù)。