一種多進制噴泉碼短碼的編譯碼方法

陳莉華

（北京理工大學出版社有限責任公司，北京 100081）

?

一種多進制噴泉碼短碼的編譯碼方法

陳莉華

（北京理工大學出版社有限責任公司，北京 100081）

摘 要：噴泉碼在碼長較長時，采用復雜度與碼長呈近線性關系的置信傳播譯碼，可靠性接近香農限，編碼效率接近1。由于噴泉碼在編碼效率和譯碼復雜度方面具有優勢，因而在多媒體廣播多播、分布式存儲、容遲容斷網絡等領域得到廣泛應用。但基于二進制的傳統噴泉編碼，為了獲得較好的譯碼性能和編碼效率，碼長比較長，一般都需要達到幾千甚至幾萬個符號；應用于短文件的存儲、傳輸，編碼效率大為下降，帶來存儲和效率的急劇下降。文章介紹了一種多進制噴泉編譯碼，其效率與二進制編碼相比，在效率和性能方面得到顯著提升，但譯碼復雜度僅略有上升。

關鍵詞：噴泉碼短碼；LT碼；Raptor碼

1　概述

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

基于噴泉碼的基本思想，M.Luby和A.Shokrollahi分別提出了兩種實用的噴泉碼，即LT碼和Raptor碼。目前，LT碼已經在無線組播、分布式存儲等多個領域得到應用［2-5］。但目前實用的噴泉碼在碼長很長時，其譯碼復雜度、譯碼性能和編碼效率表現優異。但對于短噴泉碼，這些性能表現不佳。例如，采用LT碼，如果希望編碼開銷小于5%，則信源長度需要10000以上。如果編碼長度小于1000，則編碼開銷高于30%。實際的有線通信、無線通信及文件存儲系統，長度很短的信息、短文件比較多；這些短信息、短文件不太適合碼長很長的噴泉碼編碼。基于此，本文介紹一種高效率的多進制噴泉碼。這種編碼基于有限域，其效率與二進制編碼相比，在效率和性能方面得到顯著提升，但譯碼復雜度僅略有上升。

2　多進制噴泉碼的編碼

考慮二進制編碼的線性方程組的系數矩陣只能選取0和1，因此希望矩陣的秩為K，比較有效的方法是增加方程組的數量N。這樣，當碼長較短時，增加N會造成編碼效率的下降。如果采用多進制編碼，由于系數矩陣中每個元素的維度增加，容易達到滿秩。基于此，采用多進制編碼可有效提高短碼的編碼效率。

對噴泉碼進行編碼的方法如下：

選取非負整數di。一般地，該非負整數可基于魯棒孤子分布μ（d）隨機選取。稱di為編碼符號Vi的編碼度。然后，隨機均勻地從K個信源符號中選di個符號，并基于有限域GF（q）隨機均勻地生成di個非零編碼系數。將選出的信源符號和這些非零系數對應相乘，然后作和，就得到編碼符號Vi的值。

3　多進制噴泉碼的譯碼算法

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

（1）對矩陣A進行主元選擇。

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

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

在常規的高斯消元法中，存在大量的行交換。由于行交換需要反復復制數據，造成譯碼計算和存儲量的上升。對于稀疏編碼矩陣，矩陣中存在大量的零元，這些零元參加運算和存儲器的存取會造成存儲和計算資源的浪費。實際上，不需要進行實際的行列交換，用2K個存儲單元記錄迭代過程中主元行號和列號就可以了。

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

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

4　仿真結果

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

為了說明使用魯棒孤子分布選取編碼度時多進制噴泉碼的性能，選取噴泉短碼長度K=100，C=0.05，改變參數δ，編碼度采用魯棒孤子分布，使用多進制噴泉碼編譯碼方法。選取q=2和q=16兩種情況。經驗證，在譯碼失敗概率為10-2時，碼長為100的16進制短碼，其編碼開銷只需要5%。對于二進制編碼，若實現這樣低的編碼開銷，如第1節所述，其編碼長度需要10000以上。

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

5　結語

二進制噴泉碼在碼長很長時具有很高的效率和優異的譯碼性能。但碼長較短時，編碼效率急劇下降。基于此，本文介紹了一種多進制噴泉碼，給出了噴泉短碼的編碼，并利用編碼矩陣的稀疏特性，討論了主元原位消元和稀疏存儲和計算的低復雜度譯碼方法。經仿真驗證，與二進制編碼相比，多進制編碼在效率和性能方面得到顯著提升，但譯碼復雜度僅略有上升。

［參考文獻］

［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

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