维普资讯 http://www.cqvip.com
第22卷第4期 信号处理 SIGNAL PR0CESSING Vol_22. No.4 2006年8月 Aug.2006 构造短码长不规则LDPC码 敬龙江 林竟力 成先涛 朱维乐 (电子科技大学电子工程学院1603教研室,四川成都610054) 摘要:在给定长度和度数分布对情况下,不规则短码长LDPC码的性能差别很大。本文给出了一种低复杂度的基于 树的贪婪搜索算法(GTS),此算法通过调整校验矩阵中环的分布情况,尽量减少短长度环,获得最大的平均最小环,从而 构造性能很好的短码长不规则LDPC码。 关键词:不规则LDPC码;短码长;最小环;搜索法 Construction of Short Block Length I rregular Low--Density Parity--Check Codes Jing Longjiang Lin Jingli Cheng XianTao Zhu Weile (College of Electronic Engineering of UESTC,Chengdu 610054,China) Abstract:For a igven block length and given degree sequences,the ensemble of short irregular low—density parity—check codes can have considerable variation in performance.A low—complexity greedy search algorithm based on tree is proposed.This algorithm Can be used to get the maximum average girth by adjusting the cycle distirbution of check matirx and decreasing the short length cycles,thus resulting in good short block length iregular LDPC codes. Key words:iregular LDPC codes;short block length;gitrh;search algorithm 1 引言 由于低密度校验(LDPC)码拥有逼近香农限的性能和线 性复杂度的解码算法,近年来引起了人们的极大兴趣。在 BP解码情况下,不规则LDPC码能获得离香农限0.0045 dB 降[4][5]。另一方面,二分图的最小环与码的最小距离有 关,最小环越大,码的最小距离也随之增大[6]。而码的最小 距离是它在高信噪比区域性能情况的决定因素之一。当码 长较短时,码集中各个码的环分布将远不如长码长码均匀, 这造成了码长和度数分布对相同的同一个码集中的各个码 性能上的巨大差异。由此,近年来人们致力于构造具有更好 环分布结构和更大最小环(girth)的不规则LDPC码。Mao和 Banihashemi提出了平均最小环的概念,通过在随机生成的码 的纠错能力,仿真中也找到离香农限仅0.04 dB码长为10, 000,000比特的不规则LDPC码[1]。直到现在,为获得很好 的编码性能,一般都要求LDPC码有大于100,000比特的码 长。而实时通信应用中,我们却经常需要长度在几千比特的 短码。怎样才能构造好的短码长不规则LDPC码呢? 当给定码长和度数分布对,通过随机连接二分图的变量 节点和校验节点,我们可得一个随机LDPC码码集[2]。就 长码长LDPC码而言,在BP解码算法下,此码集平均性能可 由Richardson等提出的密度进化算法分析[2],随码长增加, 码集中的单个码性能将趋近于平均性能。而对于短码长码 而言,码集中的各个码性能差异很大[3]。BP算法是基于树 形拓扑结构的,在无环情况下LDPC码才能获得最优解,而现 实中码字长度有限,这必然形成环,导致在有限次迭代后出 现相关,算法无法收敛或收敛速度减慢,造成解码性能的下 集中搜索最大平均最小环来选择性能更好的码[3]。文献 [7]通过选择大的停止集(stopping sets),从而获得拥有更大 最小码间距的LDPC码。文献[8]给出了一种最小环条件的 方法,在构造校验矩阵时逐列添加列向量来保证校验矩阵 对应的二分图拥有尽量大的平均最小环,从而得到好的码。 由于每增加一个列向量,就要对整个校验矩阵进行一次平 均最小环的计算,所以这种算法复杂度较高,在变量节点 度数较大时不易实现。针对上述情况,本文提出一种基于 树的贪婪搜索法来构造短码长不规则LDPC码。仿真表明, 这种方法能有效降低计算复杂度,提高码的性能,在高信 噪比情况下尤其如此。 收稿日期:2004年12月6日;修回日期:2005年4月30日 维普资讯 http://www.cqvip.com
590 信号处理 第22卷 2码的构造算法 假定校验矩阵有m行、n列,即对应一个有m个校验 0 0 0 1 0 0 1 1 1 I C0 0 0 1 1 0 1 0 l 0 l Cl 0 1 0 0 1 1 0 0 0 l c2 1 1 0 0 1 0 0 0 0 I C 节点、 个变量节点的二分图。 :∑ : 为二分图的平均 l|k 最小环,gj为第i个节点的最小环。给定节点u,其最小环 计算方法很简单:我们以U为根,经过厂步(厂大于或等于 k),所有与根节点U距离为厂的节点都包含在树中。假定在 0 0 1 1 0 1 0 0 1 l c4 1 1 0 0 0 0 1 0 1 V0V1 V2 V3 V4 V5 V6 V7 V IC 第k步,树中第一次出现了相同节点叶子,则2k便是U的 最小环。对于短码长而言,这个算法的复杂度较低。实际 上,我们很容易得出上述二分图平均最小环的计算复杂度 是O(n )。 :设定搜索级别L; 初始化各消息节点(列向量)的最小环g :2(L+1);; ;f0r(i=n一1; ≥0; 一一) ; : begin count=0; ; ;redo: ; II jcount*--count+1; 生成列向量 ; ;if n—m !I :begin j 重排列向量 的各行,形成一个由 和 ,}(i< <n) 阻成的矩阵;对H进行高斯消去计算,使它形成下三角矩阵 I并获得 ; j if i是零向量goto reod; iend j ! ・ ; 对 进行GTS搜索得到 ; I j 以 为根节点,构造树; i! for( =1; ;k++) i beign ;将与第k一1级节点相邻的节点加入树中构成第k级;i for每个k级节点U i begin ;i if; ̄E s 级出现的节点M 与M 为同一节点M 和M j及其各上级节点的最小环g =2(&+ ); i if上述节点最小环g,>g g:一g ; j; 删除M ,节点; ; ;: end i ・end i 用g:替代甑计算 ; ; i if( >a or count_>countmax) : ;拥有最大 的列向量 加入样验矩阵; ! j 对应的g,一 else goto redo ! 。 d 1 6×9维的校验矩阵 在给定码长n、度数分布对( ,P)后,我们这样构造校验 矩阵:首先设定一个m×n维的全零校验矩阵日(其中m=n r1 . ,1 J O I P( )rd/IJ 0 ( )dr),再将列向量按重量非递减顺序依次从 右至左添入校验矩阵日中。如 、 分别表示第i和第 个列 向量,当i> 时, 的列重不大于 的列重。对于前n—m次 列添加,我们都要对日进行高斯消去计算,使这n—m个列向 量线性,以保证校验矩阵行满秩。添人校验阵日中的所 有列向量都是在满足度数分布对条件下随机生成,当准备添 人的某一列向量通过贪婪树搜索法(GTS)所得校验阵的平均 最小环达到某一设定门槛时,此次扩展完成。为保证算法收 敛且便于控制,我们引入了记数器,当记数器达到设定最大 值而校验矩阵的平均最小环还没达到我们要求时,此次计算 自动中断,并从先前计算中选出拥有最大平均最小环的列向 量添人校验矩阵中。算法的具体细节如左所述。 第0级 第1级 第2级 第3级 第4级 图2以 节点出发的GTS搜索法,生存路径由粗实线表示 图1是一个6×9维的校验矩阵。图2是以 节点为根 展开的树,其中 表示变量节点,c表示校验节点。GTS搜索 法是指:设定校验阵中各列向量的最小环为一固定值2(L+ 1),每当选择一列向量(如节点 )准备加入矩阵时,以 节 点为根展开L级树,逐级搜索树中所有环,确定环中各变量 节点因节点 引入对它们最小环的影响,如最小环值降低, 则此次所得值代替原值,反之则不改变原值。在树的逐级拓 展中,重复节点只保留一个,保证在生存路径上的节点得以 成长,而其它路径上的节点枯萎。这样可避免大量节点的最 小环重复计算,从而将计算复杂度从与节点数成指数级关系 降为线性关系。以拥有4级节点树的图2为例,实线表示生 存路径。在树的逐级拓展中,只有生成路径上的节点才需要 计算其最小环。从图中我们很容易看出各节点的最小环,其 中 , , , 的最小环为4, 。的最小环为6, 的最小环 为8,而当L设定为4时, , 的最小环为10。 3仿真与比较 我们将GTS算法应用到构造度数分布为 =0.2390 维普资讯 http://www.cqvip.com
第4期 构造短码长不规则LDPC码 591 =0.7610,P =0.7793,P =0.2207,码长为1268的不规则 为变量节点下标i的函数,既 =14—2.2×((1268一i)/ 码。将它与最小环条件法和Mao提出的简单搜索法进行了 比较,仿真结果表明,GTS法在性能上优于Mao提出的简单 LDPC码中[3]。在此设定搜索级别L为6,平均最小环门槛 1268) ,记数器门槛为150。通过此算法,我们找到了平均 搜索法[3],特别是在高信噪比区域表现更加明显,在算法复 杂度上优于最小环条件法[8]。 最小环约为11.82的码。与此相比,用文献[3]提出的简单 筛选法,从随机生成的2000个码中选出码的最大平均最小环 约为9.38。用文献[8]提出的最小环条件算法,能获得平均 最小环约为11.63的码。图3是这3个码在AWGN信道、 BPSK调制方式下的性能比较图。 10一 --g-Mao 10 10。 盘 ∞l0一, 10 10一’ 重rClE匡I .;;;j-7…=-7!=薹 T1|】』i薹-7!=;;!…-7!= ;;;1舅]Jj囊i =…;薹 -7!=一 ;;flcL=禹I ir-7!… =-7:!;j; |】J=1i7一!-;薹 ;:7!=‘- ;];詈Jj毫i一 …=。-7:、3=蠹;; 一’! ;;;lfrlI…兰=壁呈 i=皇1§:j’ i …=!一, =巴-l.1莹]詈I 10。 ∞ E~ 旺~¨ ~琵 ~鳇E~畦 ~一墟 图3 AWGN信道下(1268,456)码的3种构造算法性能比较 从图3中可见,相对于简单搜索法,GTS算法拥有较大的 性能增益,这种现象在高信噪比区域尤其突出。相对于最小 环条件算法,GTS法的性能增益并不明显,但应该注意的是: 为得到每增加一个列向量后校验矩阵的平均最小环,前者的 计算复杂度是O((n—i) ),而本算法仅是O((n—i))。由 于GTS算法简单易行,我们可以将其应用在变量节点度数稍 ●一 争flI!==■lI_=_=■三=Il■lll_一=三l=■-●■■= =一!l!¨l=,¨l=II=.!一■ =一tl-■==S一=l-!:一I1ll= -_大的LDPC码构造中。我们以构造一个可传输MPEG2信源 RⅡ 眦S棚TGr 1●l 1 lt_-lI-J『llI】=兰Il一!三l=,!l■ll■;=l_】■!:‘!¨l=IJ,llI一IlllI:暑丰J ●,,,1●} ,¨l=■毫■i=一■i=、-lll_l三 !l!;=●!:一¨=ll;I_llll:一 ■ = 一 数据的LDPC码为例:MPEG2每码包数据大小为188字节,● ●.■lI1=!==■!::!llIll_E=一,¨1= 我们按码率为1/2,整MPEG2码包进行数据传输,即要求构 造(3008,1504)的LDPC码。根据文献[1]给出的离散密度 进化及优化算法,我们从所得结果中选取一组性能相对较 好,变量节点度数适中的度数分布对来进行仿真。具体的度 数分布为≈( )=0.2484x+0.4203x +0.3312x ,P( )= , 其中变量节点最大度数为16。在设定搜索级别L为4,平均 最小环门槛 =10—3.3×((3008一i)/3008) ,记数器门槛 为100情况下,我们通过GTS算法,得到平均最小环为6.59 的码。图4给出了它在AWGN信道、BPSK调制方式下的性 能情况。为了便于比较,图中也列出了从该码集中随机选取 的一个平均最小环为5.71的码。从图4我们可看出,用GTS 算法找到的LDPC码在信噪比为1.7dB情况下,能达到误码 率低于l0 的较好性能,能达到MPEG2数据无线传输误码 率要求。另一方面,由此算法构造的码在信噪比大于1.6dB 的高信噪比区域其性能大大优于从码集中随机挑选的码。 4结论 本文针对短码长不规则LDPC码在给定长度和度数分布 对情况下,码集中各码字性能差异较大的问题,给出一种基 于树的贪婪搜索算法(GTS),通过此算法获得校验矩阵最大 的平均最小环,从而构造出性能很好的短码长不规则LDPC ! ]= 王 ●- 千 -i- 望 1一 === 赛 = 擎 ali j= :: 三{三 詈! 三! 塞 SNR(dB) 图4 AWGN信道下(3008,1504)码随机构造算法 与GTS构造算法性能比较 参考文献 [1] Sac—Young Chung,G.David Forney,Thomas J.Richard— son.On the design of low—density parity—check codes with— in 0.0045 dB of the Shannon limit『J].Communications Letters,IEEE,2001,5:58—60. [2]Thomas J.Richardson,Rudiger L.Urbanke.The capacity of low -density pariyt check codes under message-・passing deco-・ ding[J],IEEE Trans.Inf.Theory,2001,47:599-618. [3] Yongyi Mao,Amir H.Banihashemi.A heuristic search for good lowdensity parity—check codes at short block lengths 『C].Proc.IEEE Int.Conf.Communications,Helsinki, Finland,2001,1:11—14. [4] Robert G.Gallager.Low—Density Parity—Check Codes [J].IRE Trans on Ifnorm Theoyr,1962,8(1):21—28. [5] MacKay D J C.Good Error—Correcting Codes Based on Very Sparse Matirces[J].IEEE Trans on Ifnorm hTeory, 1999,45(2):399—431. [6]Haotian Zhang,Jos’e M.F.Moura.The desing of struc— tured regulra LDPC codes with lrage gitrh[C].in IEEE Globecom 2003,Dec 2003,7:4022—4027. [7]Tao Tian,Chris Jones,John D.Villasenor,et a1.Con— struction of irregulra LDPC codes with low error floors [C].Proc.IEEE Int.Conf.Communications,Anchor— gae,AK,USA,2003,5:3125—3129. [8] Y.一J.Ko,J.一H.Kim.Girth conditioning for construction of short block length iregulra LDPC codes[J].in IEE E— lectronics Letters,2004,40(3):187—188. 作者简介 敬龙江:男,1974年生,信号与信息处理博士研究生, 研究方向为新一代移动通信中的编码调制技术。