噴泉碼中半隨機(jī)生成法去短小環(huán)

劉立軍，謝紅，解武

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

噴泉碼中半隨機(jī)生成法去短小環(huán)

劉立軍，謝紅，解武

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

分析了噴泉碼中LT碼的生成原理及影響譯碼性能的因素，生成矩陣中的短小環(huán)是影響編譯碼性能的主要因素，其中，長(zhǎng)度為4的短小環(huán)對(duì)編譯碼的性能影響最大。提出了一種半隨機(jī)生成法去除長(zhǎng)度為4的短小環(huán)的方法。仿真結(jié)果表明：去除長(zhǎng)度為4的短小環(huán)之后，明顯改善了噴泉碼的性能，降低了譯碼復(fù)雜度，提高了系統(tǒng)性能。

噴泉碼；LT碼；串行置信傳播算法；短小環(huán)；半隨機(jī)生成法

1998年，M.Luby等人首次提出噴泉碼的概念，其主要是針對(duì)二進(jìn)制刪除信道而提出來(lái)的一種線性糾錯(cuò)碼［1］。噴泉碼名字的由來(lái)是因?yàn)閲娙a的編碼器能夠像噴泉向外面噴射出水滴一樣，能夠根據(jù)源信息產(chǎn)生無(wú)數(shù)個(gè)噴泉碼的編碼包。假設(shè)源文件的大小是K bits，噴泉碼的編碼器每次產(chǎn)生的編碼碼字大小是l bit，接收端就不斷地接收信源端發(fā)送過(guò)來(lái)的碼字，當(dāng)接收端接收的碼字?jǐn)?shù)目稍微大于K bits時(shí)，接收端就能夠準(zhǔn)確的譯碼［2］。

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

影響噴泉碼性能之一的因素就是生成矩陣的結(jié)構(gòu)，生成矩陣中的短小環(huán)的影響最大。所以，本文提出一種半隨機(jī)生成法去除短小環(huán)的方法。

1 LT碼與串行BP譯碼

1.1 LT碼編碼

LT碼是噴泉碼的一種，而且是第一種可以通過(guò)編碼設(shè)計(jì)能夠?qū)崿F(xiàn)的噴泉碼。LT碼的編碼原理是通過(guò)構(gòu)造噴泉碼生成矩陣，根據(jù)這個(gè)生成矩陣來(lái)實(shí)現(xiàn)噴泉碼的編碼。

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

式中Ωd表示校驗(yàn)節(jié)點(diǎn)是由d個(gè)源信息節(jié)點(diǎn)通過(guò)運(yùn)算而得到的概率。

下面分步討論LT碼編碼原理具體的實(shí)現(xiàn)步驟：

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

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

3）然后再根據(jù)式（1）的方式生成一個(gè)相應(yīng)的編碼符號(hào)cj，式（1）中的求和是二進(jìn)制的加法。

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

LT碼同樣是基于對(duì)稀疏矩陣構(gòu)造的一種線性的糾錯(cuò)碼，滿足二分圖論的表示方法要求，所以LT碼同樣能夠用二分圖論的方式來(lái)表示。圖1是一個(gè)噴泉碼編碼過(guò)程的具體表示方式，其中信息的長(zhǎng)度是4，編碼的長(zhǎng)度是5，圖1（a）是生成矩陣的表示形式，圖1（b）是與圖1（a）對(duì)應(yīng)的Tanner圖的表示方式。Tanner圖中的符號(hào)節(jié)點(diǎn)s1，s2，…，sk是相應(yīng)的源信息節(jié)點(diǎn)，c1，c2，…，cn是根據(jù)源信息節(jié)點(diǎn)生成的校驗(yàn)節(jié)點(diǎn)。

圖1 生成矩陣與Tanner圖

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

1.2 串行BP譯碼算法

信道狀態(tài)為高斯白噪聲時(shí)，噴泉碼的譯碼通常采用的是標(biāo)準(zhǔn)BP譯碼算法。這個(gè)算法在每一輪的迭代過(guò)程中，都是并行對(duì)所有符號(hào)節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)進(jìn)行相應(yīng)的更新，具體的迭代過(guò)程如圖2（a）所示。2001年，E.Yeo等人提出了串行BP譯碼算法（SBP）被用作LDPC碼的譯碼算法。這個(gè)算法是在每一輪的迭代過(guò)程中，對(duì)不同類(lèi)型的節(jié)點(diǎn)信息分步驟進(jìn)行更新。具體的更新過(guò)程如圖2（b）所示。根據(jù)選擇的節(jié)點(diǎn)類(lèi)型的差異，SBP算法同時(shí)又可以分為2種不同的算法。

圖2 2種譯碼算法的更新過(guò)程

下面討論串行BP譯碼算法的具體實(shí)現(xiàn)步驟：

1）首先，分別對(duì)下面2個(gè)數(shù)據(jù)進(jìn)行初始化處理：

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

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

b）把所有的符號(hào)節(jié)點(diǎn)傳遞給與每個(gè)符號(hào)節(jié)點(diǎn)相連的校驗(yàn)節(jié)點(diǎn)的信息初始化為

2）在每一輪的迭代過(guò)程中，按照編碼的順序?qū)γ恳粋€(gè)符號(hào)節(jié)點(diǎn)si迭代更新相應(yīng)的接收信息，按照下面的過(guò)程來(lái)更新每一個(gè)節(jié)點(diǎn)：

a）首先，計(jì)算與這個(gè)符號(hào)節(jié)點(diǎn)連接的每個(gè)校驗(yàn)節(jié)點(diǎn)cj傳遞給符號(hào)節(jié)點(diǎn)si的信息L（l）（rji），按照式（3）進(jìn)行更新。

式中：P（j）為所有跟校驗(yàn)節(jié)點(diǎn)cj連接的符號(hào)節(jié)點(diǎn)的集合，而i′∈P（j）＼i表示P（j）中除si之外所有的符號(hào)節(jié)點(diǎn)。

b）計(jì)算節(jié)點(diǎn)si傳遞給節(jié)點(diǎn)cj的信息L（l）（qji），按照式（4）所示的方式進(jìn)行計(jì)算。

式中：M（i）代表的是所有與符號(hào)節(jié)點(diǎn)si相連接的校驗(yàn)節(jié)點(diǎn)的集合，而j′∈M（i）＼j表示M（i）中除cj之外的所有校驗(yàn)節(jié)點(diǎn)。

3）當(dāng)譯碼迭代過(guò)程都結(jié)束時(shí)，根據(jù)式（5）計(jì)算所有的符號(hào)節(jié)點(diǎn)迭代譯碼后的信息大小，然后再根據(jù)式（6）對(duì)所有的符號(hào)節(jié)點(diǎn)進(jìn)行判定，并得到最終的譯碼結(jié)果，譯碼結(jié)束。

2 噴泉碼中短小環(huán)的影響與去小環(huán)算法

2.1 短小環(huán)的危害

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

2.2 半隨機(jī)生成法去小環(huán)

由于低密度奇偶校驗(yàn)碼LDPC的研究比較早，LDPC碼的去小環(huán)方法的研究也相當(dāng)成熟，在規(guī)則的LDPC碼的檢驗(yàn)矩陣去小環(huán)的研究中，已經(jīng)研究出了很多方法，例如列分裂方法、根據(jù)校驗(yàn)矩陣檢測(cè)環(huán)的方法等，但這些方法都不適用于LT碼。這些方法都是通過(guò)調(diào)整生成矩陣的方式來(lái)實(shí)現(xiàn)的，都在一定程度上影響了生成矩陣度的分布，而且這些方法實(shí)現(xiàn)起來(lái)也比較困難。本文提出一種可以方便去除長(zhǎng)度為4的短小環(huán)的方法，即半隨機(jī)生成法。該方法的步驟為：

1）生成一個(gè)K－1行K－1列的全零矩陣（K為符號(hào)節(jié)點(diǎn)個(gè)數(shù)），按照?qǐng)D3的方式給矩陣賦值；

2）編碼第i個(gè)校驗(yàn)節(jié)點(diǎn)，按照度分布隨機(jī)選取一個(gè)d的值作為這個(gè)校驗(yàn)節(jié)點(diǎn)的度；

3）如果d＝2，隨機(jī)生成一個(gè)數(shù)N（N＜K－1）；

4）在圖3矩陣中對(duì)應(yīng)的列c，隨機(jī)生成一個(gè)數(shù)r（c＜r＜K－1）；

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

6）把第c個(gè)符號(hào)節(jié)點(diǎn)和第r個(gè)符號(hào)節(jié)點(diǎn)作為第i個(gè)校驗(yàn)節(jié)點(diǎn)的編碼符號(hào)；

7）重復(fù)步驟2）～6），完成編碼。

圖3 去環(huán)矩陣

3 仿真分析

圖4、5分別是標(biāo)準(zhǔn)BP譯碼去小環(huán)和串行BP譯碼去小環(huán)前后的性能仿真對(duì)比圖。假定信道為高斯白噪聲信道，設(shè)置相應(yīng)的仿真條件如下：噪聲的平均能量設(shè)定為1，噪聲的方差設(shè)定為2；源信息的長(zhǎng)度是1 000，調(diào)制方式采用BPSK調(diào)制，譯碼時(shí)設(shè)定迭代次數(shù)為10，圖中的每個(gè)點(diǎn)是100幀數(shù)據(jù)仿真計(jì)算出來(lái)的平均值。

圖4 標(biāo)準(zhǔn)BP譯碼算法去小環(huán)前后的性能對(duì)比

圖5 串行BP譯碼算法去小環(huán)前后的性能對(duì)比

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

4 結(jié)束語(yǔ)

本文首先分析了LT碼的編碼原理和LT碼的串行BP譯碼算法，之后主要分析了影響LT碼性能的主要因素，得出短小環(huán)是影響LT碼的性能的重要因素，基于此，提出一種半隨機(jī)生成法去除LT碼短小環(huán)的方法，并且詳細(xì)闡述了這個(gè)方法的實(shí)現(xiàn)過(guò)程。通過(guò)仿真對(duì)比得出去除LT碼的短小環(huán)之后，應(yīng)用標(biāo)準(zhǔn)BP譯碼算法和串行BP譯碼算法時(shí)，LT碼的性能都能夠得到提高。由于本文提出的方法是去除長(zhǎng)度為4的小環(huán)，進(jìn)一步的工作可以針對(duì)去除長(zhǎng)度更大的小環(huán)展開(kāi)相關(guān)研究。

［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，F(xiàn)rance，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.

黑龍江省自然科學(xué)基金資助項(xiàng)目（F201339）.

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

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