噴泉碼中半隨機生成法去短小環

劉立軍，謝紅，解武

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱 150001

噴泉碼中半隨機生成法去短小環

劉立軍，謝紅，解武

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱 150001

分析了噴泉碼中LT碼的生成原理及影響譯碼性能的因素，生成矩陣中的短小環是影響編譯碼性能的主要因素，其中，長度為4的短小環對編譯碼的性能影響最大。提出了一種半隨機生成法去除長度為4的短小環的方法。仿真結果表明：去除長度為4的短小環之后，明顯改善了噴泉碼的性能，降低了譯碼復雜度，提高了系統性能。

噴泉碼；LT碼；串行置信傳播算法；短小環；半隨機生成法

1998年，M.Luby等人首次提出噴泉碼的概念，其主要是針對二進制刪除信道而提出來的一種線性糾錯碼［1］。噴泉碼名字的由來是因為噴泉碼的編碼器能夠像噴泉向外面噴射出水滴一樣，能夠根據源信息產生無數個噴泉碼的編碼包。假設源文件的大小是K bits，噴泉碼的編碼器每次產生的編碼碼字大小是l bit，接收端就不斷地接收信源端發送過來的碼字，當接收端接收的碼字數目稍微大于K bits時，接收端就能夠準確的譯碼［2］。

噴泉碼最大的特性就是與它的碼率無關性。由于噴泉碼的特性能夠讓任何一個刪除信道的性能都接近最佳，所以噴泉碼的用途十分廣泛。在刪除信道中，不論有多少編碼碼字被信道刪除，發送端都能夠發送足夠多的碼字，來讓接收端譯碼。接收端一旦能夠接收到N個碼字（N比K稍大），就可以準確地恢復源文件［3-4］。

影響噴泉碼性能之一的因素就是生成矩陣的結構，生成矩陣中的短小環的影響最大。所以，本文提出一種半隨機生成法去除短小環的方法。

1 LT碼與串行BP譯碼

1.1 LT碼編碼

LT碼是噴泉碼的一種，而且是第一種可以通過編碼設計能夠實現的噴泉碼。LT碼的編碼原理是通過構造噴泉碼生成矩陣，根據這個生成矩陣來實現噴泉碼的編碼。

假定想要發送的源文件信息為s1，s2，…，sk，k是信息的長度，并假定度分布為Ω1，Ω2，…，Ωk那么可以按照下式生成編碼碼字：

式中Ωd表示校驗節點是由d個源信息節點通過運算而得到的概率。

下面分步討論LT碼編碼原理具體的實現步驟：

1）根據上面介紹的度分布Ω1，Ω2，…，Ωk，隨機的選取一個度值d（d∈［1，k］）。

2）根據步驟1）得到的度值d，等概率的方式隨機生成一個列向量v，v＝（v1，v2，…，vk），這個向量中“1”的個數為d，其中vi∈｛0，1｝，i＝1，2，…，k。

3）然后再根據式（1）的方式生成一個相應的編碼符號cj，式（1）中的求和是二進制的加法。

4）不斷重復步驟1）～3），N次之后，就能夠得到生成矩陣的一個編碼之后的序列（c1，c2，…，cN），而生成矩陣G就是把對應的列向量v1，v2，…，vN按照固定的順序排列就可以得到。

LT碼同樣是基于對稀疏矩陣構造的一種線性的糾錯碼，滿足二分圖論的表示方法要求，所以LT碼同樣能夠用二分圖論的方式來表示。圖1是一個噴泉碼編碼過程的具體表示方式，其中信息的長度是4，編碼的長度是5，圖1（a）是生成矩陣的表示形式，圖1（b）是與圖1（a）對應的Tanner圖的表示方式。Tanner圖中的符號節點s1，s2，…，sk是相應的源信息節點，c1，c2，…，cn是根據源信息節點生成的校驗節點。

圖1 生成矩陣與Tanner圖

度分布在一定程度上決定了噴泉碼的性能，所以本文中采用Shokrollahi在文獻［10］中所提出的度分布，這個度分布的表示如下所示：

1.2 串行BP譯碼算法

信道狀態為高斯白噪聲時，噴泉碼的譯碼通常采用的是標準BP譯碼算法。這個算法在每一輪的迭代過程中，都是并行對所有符號節點和校驗節點進行相應的更新，具體的迭代過程如圖2（a）所示。2001年，E.Yeo等人提出了串行BP譯碼算法（SBP）被用作LDPC碼的譯碼算法。這個算法是在每一輪的迭代過程中，對不同類型的節點信息分步驟進行更新。具體的更新過程如圖2（b）所示。根據選擇的節點類型的差異，SBP算法同時又可以分為2種不同的算法。

圖2 2種譯碼算法的更新過程

下面討論串行BP譯碼算法的具體實現步驟：

1）首先，分別對下面2個數據進行初始化處理：

a）根據式（2）計算，可以得到接收到的信息初始化值。

式中：yj為接收端接收到的編碼符號序列的一個編碼符號，σ2為高斯信道中噪聲的方差。

b）把所有的符號節點傳遞給與每個符號節點相連的校驗節點的信息初始化為

2）在每一輪的迭代過程中，按照編碼的順序對每一個符號節點si迭代更新相應的接收信息，按照下面的過程來更新每一個節點：

a）首先，計算與這個符號節點連接的每個校驗節點cj傳遞給符號節點si的信息L（l）（rji），按照式（3）進行更新。

式中：P（j）為所有跟校驗節點cj連接的符號節點的集合，而i′∈P（j）＼i表示P（j）中除si之外所有的符號節點。

b）計算節點si傳遞給節點cj的信息L（l）（qji），按照式（4）所示的方式進行計算。

式中：M（i）代表的是所有與符號節點si相連接的校驗節點的集合，而j′∈M（i）＼j表示M（i）中除cj之外的所有校驗節點。

3）當譯碼迭代過程都結束時，根據式（5）計算所有的符號節點迭代譯碼后的信息大小，然后再根據式（6）對所有的符號節點進行判定，并得到最終的譯碼結果，譯碼結束。

2 噴泉碼中短小環的影響與去小環算法

2.1 短小環的危害

生成矩陣的結構對噴泉碼的性能影響非常大，特別是生成矩陣中的短小環，是主要的影響因素之一。例如，在圖2（b）中，符號c3-s3-c4-s2-c3相互連接之后就構成了一個長度為4的短小環。短小環對噴泉碼的性能影響主要體現在2個方面。編碼時，總是希望編碼后的碼字能夠包含盡可能多的原始信息，從而使編碼后的碼字能夠包含所有的原始信息，而小環的存在，使編碼后的碼字里面包含了更多的重復信息，影響編碼后的碼字信息量。譯碼時，由于短小環的存在，節點之間傳遞信息時相互獨立的性質遭到破壞。一個節點傳遞出去的信息，通過組成小環節點之間的相互傳遞，又把這個信息傳遞到自己本身，導致信息的迭代更新速度降低，譯碼的復雜度提高。由于這2方面的影響，找到一種去除噴泉碼的短小環的方法就顯得尤為重要。

2.2 半隨機生成法去小環

由于低密度奇偶校驗碼LDPC的研究比較早，LDPC碼的去小環方法的研究也相當成熟，在規則的LDPC碼的檢驗矩陣去小環的研究中，已經研究出了很多方法，例如列分裂方法、根據校驗矩陣檢測環的方法等，但這些方法都不適用于LT碼。這些方法都是通過調整生成矩陣的方式來實現的，都在一定程度上影響了生成矩陣度的分布，而且這些方法實現起來也比較困難。本文提出一種可以方便去除長度為4的短小環的方法，即半隨機生成法。該方法的步驟為：

1）生成一個K－1行K－1列的全零矩陣（K為符號節點個數），按照圖3的方式給矩陣賦值；

2）編碼第i個校驗節點，按照度分布隨機選取一個d的值作為這個校驗節點的度；

3）如果d＝2，隨機生成一個數N（N＜K－1）；

4）在圖3矩陣中對應的列c，隨機生成一個數r（c＜r＜K－1）；

5）如果矩陣的第c列中的第r個數是零，則重復步驟4），否則把這個數變成零；

6）把第c個符號節點和第r個符號節點作為第i個校驗節點的編碼符號；

7）重復步驟2）～6），完成編碼。

圖3 去環矩陣

3 仿真分析

圖4、5分別是標準BP譯碼去小環和串行BP譯碼去小環前后的性能仿真對比圖。假定信道為高斯白噪聲信道，設置相應的仿真條件如下：噪聲的平均能量設定為1，噪聲的方差設定為2；源信息的長度是1 000，調制方式采用BPSK調制，譯碼時設定迭代次數為10，圖中的每個點是100幀數據仿真計算出來的平均值。

圖4 標準BP譯碼算法去小環前后的性能對比

圖5 串行BP譯碼算法去小環前后的性能對比

從圖4、5仿真結果可以看到：在譯碼開銷較小的時候，2種算法的誤碼率性能都不是很好。這是因為譯碼端需要接收到更多的碼字才能夠正確進行譯碼。隨著譯碼開銷的不斷增大，每一種算法在譯碼開銷相同的情況下，去環之后譯碼算法的誤碼率明顯低于去環之前。去除短小環之后，誤碼率降低，提高了碼的性能。這是由于去除小環之后噴泉碼編碼包含的原始信息更多，譯碼時迭代更新速度更快，所以性能比去除小環之前提高了。

4 結束語

本文首先分析了LT碼的編碼原理和LT碼的串行BP譯碼算法，之后主要分析了影響LT碼性能的主要因素，得出短小環是影響LT碼的性能的重要因素，基于此，提出一種半隨機生成法去除LT碼短小環的方法，并且詳細闡述了這個方法的實現過程。通過仿真對比得出去除LT碼的短小環之后，應用標準BP譯碼算法和串行BP譯碼算法時，LT碼的性能都能夠得到提高。由于本文提出的方法是去除長度為4的小環，進一步的工作可以針對去除長度更大的小環展開相關研究。

［1］LUBY M.LT codes［C］//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.To-ronto，Canada，2002：271-282.

［2］MACKAY D JC.Good error correcting codes based on very sparsematrices［J］.IEEE Transactions on Information Theo-ry，1999，45（2）：399-431.

［3］ZHANG Kai，HUANG Xinming，SHEN Chen.Soft decoder architecture of LT codes［J］.IEEE Signal Processing Sys-tems，2008，41（7）：210-215.

［4］ABOUEI J，BROWN J D.On the energy efficiency of LT codes in proactive wireless sensor networks［J］.IEEE Trans-actions on Signal Processing，2011，59（3）：1116-1127.

［5］ABDULHUSSEIN A，OKA A，LAMPE L.Decoding with early termination for raptor codes［J］.IEEE communication letters，2008，12（6）：444-446.

［6］ABDULHUSSEIN A，OKA A，LAMPE L.Decoding with early termination for rateless codes［C］//IEEE WCNC.New Orleans，USA，2008：249-254.

［7］PETERSONW，BROWN D T.Cyclic codes for error detec-tion［J］.Proceedings of the IRE.2008，37（8）：228-235.

［8］BRINK T S.Convergence of iterative decoding［J］.IEEE E-lectron.Letter，1999，35（10）：806-808.

［9］PAKZAD P，SHOKROLLAHIA.Exit function for LT and raptor codes，and asymptotic ranks of random matrices［C］//IEEE International Symposium on Information Theo-ry.Nice，France，2007：411-415.

［10］SHOKROLLAHIA.Raptor codes［J］.IEEE Trans Inf The-ory，2006，52（6）：2551-2567.

［11］BRINK T S.Convergence behavior of iteratively decoded parallel concatenated codes［J］.IEEE Trans Comin，2001，49（10）：1727-1737.

［12］ASHIKHMIN A，KRAMER G，BRINK T S.Extrinsic in-formation transfer functions：a model and two properties［C］//Conf Information Sciences and Systems.Princeton，USA，2002：742-747.

A sem i-random generation method for removing the short ring of a fountain code

LIU Lijun，XIE Hong，XIEWu
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

The generation principle and factors affecting decoding performance of LT codes in a fountain code were analyzed，and itwas found the short ring of the generatormatrix is a major factor affecting the performance of the encoding and decoding，among which a short ring whose length is 4 has the biggest impact on encoding and deco-ding performance.This article presents a semi-random generation method for removing the short ringwith a length of 4.Simulation results show that the removal of the short ringwith a length of 4 significantly improves the performance of the fountain codes，reduces the decoding complexity and improves the system performance.

fountain code；LT code；serial belief propagation algorithm；short ring；semi-random generationmethod

TM461

：A

：1009-671X（2015）01-041-04

10.3969／j.issn.1009-671X.201404001

http：//www.cnki.net／kcms／detail／23.1191.U.20150112.1530.012.htm l

2014-04-02.

日期：2015-01-12.

黑龍江省自然科學基金資助項目（F201339）.

劉立軍（1989-），男，碩士研究生；謝紅（1962-），女，教授，博士生導師.

謝紅，E-mail：xiehong＠hrbeu.edu.cn.