基于级联稀疏二部图的右边正则纠删码精确阈值

基于级联稀疏二部图的右边正则纠删码精确阈值 基于级联稀疏二部图的右边正则纠删码精 确阈值 596自.美科荸j锺,展第18卷第5期2008年5月 基于级联稀疏二部图的右边正则纠删码精确阈值* 慕建君王新梅 1.西安电子科技大学教育部计算机网络与信息安全重点实验室,西安710071; 2.西安电子科技大学综合业务网国家重点实验室,西安710071 摘要提出了确定删除恢复算法下右边正则纠删码阈值的一个简单方法. 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 了计算右边正 则 纠删码阈值的一个精确公式.这个新方法可避免求度分布 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 的微分和逆这些复杂的运算. 数值 结果表明所提出新方法的有效性. 关键词--NIl1除信道{aEc)右边正则纠删码阈值 1955年Elias提出的二元删除信道(binaryera- surechannel,BEC)[1由于其可用来模型化互联网 传输系统而最近变得日益流行起来.近年来,人们 已对删除信道下低密度校验码(1ow—densityparity— check,LDPC码)进行了广泛的研究[2].通过级 联二部图,Luby等设计了可任意逼近删除信道容 量限而且具有线性时间编译码算法的级联型纠删 码.这种码属于LDPC码类[8].这些良好特性使得 级联型纠删码(包括Tornado码)在可靠多播传 输,多源并行下载和分布式存储系统[n等 方面具有广泛的应用. 级联型纠删码可由一度分布(以,P)来刻划[2], 其中 以(z)一?z,P(z)一?zr., f?zl?2 ()表示二部图中左边(右边)度数为i的边的比 率.而且Luby等提出了译级联型纠删码的一简 单恢复算法,同时证明了对于初始删除概率为和 度分布为(以,P)的随机图,如果对于所有z?(0, )有 8A(1一P(1一z))<z(1) 2007—09—20收稿,2007一l1—12收修改稿 *国家自然科学基金资助项目(批准号;60573034,60572149) **E—mail:jimu@xidian.edu.ca 成立,那么该删除恢复算法可成功译码. 对于给定的度分布(以,p)E?],经过次迭代之 后删除信息的比率z可以递归表示为 z=z()一8A(1一P(1一z,广1))(2) 其中?1,z.为信道的初始删除概率.我们对使 得趋于无穷大时z()趋于零的所有(<1)感兴 趣.对给定的参数(以,P),满足(1)式的最大称 为级联型纠删码的阈值并用.(以,P)表示.这就 是说与度分布(以,P)相关的阈值(以,P)定义 为 .(以,P)一sup{8l0<<1, limx()一0,zo一}.—?? 删除信道下LDPC码渐近理论的最新进展已表 明适当地选取二部图中信息和校验结点的度分布可 产生逼近删除信道Shannon容量限的码.从渐 近的角度出发,校验结点度分布的最好选择是右边 正则度分布(以,a)E:对给定整数n?3, 自显科荸.越展第18卷第5期2008年5月597 因此,研究删除恢复算法下右边正则纠删码的阈值 是重要的. 通过分析外信息转移(extrinsicinformation transfer,EXIT)图,Hehn等提出了确定删除信道 下非正则LDPC码阈值的一方法m].然而,这种方 法需要求度分布的微分和逆函数运算.通过将计算 阈值问题归结为确定仅依赖于右边正则度分布的一 个函数的最小值后,本文提出了确定右边正则纠删 码阈值的一简单方法,新方法可克服Hehn等所给 以上方法中为了计算右边正则纠删码的阈值而必须 求度分布函数的微分和逆运算这些缺点. 本文证明了计算右边正则纠删码阈值的一个精 确公式.而且给出了证明这一新方法的有效性的一 些数值结果. 1几个引理 如果对所有的z?(0,)有3A(1,P(1--x))< z成立,那么删除恢复算法下级联型纠删码的译码 器可纠比率为的删除错误.对于右边正则度分布 (A,n),这个条件转化为a<x/A(1,(1一z)一). 为了确定右边正则纠删码的阈值,对整数n?5定 义函数 一 (3) 其中(z)一z一++…+z+1. 本节中证明函数厂的若干特性和用来确定右 边正则纠删码阈值的一个结论,这些引理概括如 下. 0<m— in一{厂(z))?1.依据条件(n一1)>1得C-fo.1 因此,可得m, {厂(z))<1.由厂(0)一1和厂(1)< tlu’1 1得厂(z)在[0,1]上的最小值在x=OE(0,1]上取 得.于是有min{. 厂(z))一min{.厂(z)).因此 ?(O,1]?[O,1] 0<min ,] {厂(z)): ? m [ in o1o.1] {厂(z))<1? ?(,]?[.] 引理2设(A,P)为给定度分布,其初始删除 概率为?(0,1).定义函数 g(z)一3A(1一P(1一z))(z?[0,1]). 像(2)式中那样序列{())定义为 z一()一(1一P(1一z,r1)), 那么对每一?(0,1)limx()一.成立当且仅当对 所有z?(0,1]有g(z)<z成立. 证明(i)假如对每一?(0,1)有limx()一 n—+.. 0成立,那么容易看到对每一?(0,1)极限limx() 存在.现在证明对所有z?(0,1]有g(z)<z成 立.为了得出矛盾,假如存在某一z?(0,1]且 z?1使得g(z)?z.这时固定一z后根据 g(z)?37.和函数g(z)在(0,1)上的单调递增性得 z1一g()一g(x)?z一一zo 引理1设函数f如(3)式中所定义.如果和 -- ? 1)>1, 脯一z,. (i)厂(z)在[0,1]上的最小值m一 {厂(z))存..一 在; (ii)0<min{厂(z))一min{厂(z))<1. ?(O,1]?[O.1] 证明(i)根据函数厂的定义,容易看到厂(z) 是[0,1]上的连续函数.于是得厂(z)在[0,1]上的 最小值min{厂(z))存在口. (ii)根据函数厂的定义和f(0)一1,容易看到 注意到对每一?(0,1)极限limx()存在,利用H—-.. 归纳法知对序列{z())有limx()一limx(z)?n—’?n—-.. z?0成立.这与假设条件对每一?(0,1)有 limx()一0成立相矛盾.— -.. (ii)反之,假如就每一?(0,1),对所有z? (0,1]有g(z)<z成立.根据函数g和序列 598自.驻科学遗展第18卷第5期2008年5月 {z())的定义知对所有整数n>j1有和 z:=:(1,P(1一z,r1))<z,卜lg(sc)一(1一P(1一sc))(sc?Eo,1]). 成立.注意到A(0)一P(0)一0和A(1)一P(1)一1, 容易看出O<z一(1一P(1一z))<.这两个 结果意味着对每一?(O,1)序列{z())是一个严 格单调递减的有界序列,从而得极限limzr()存在 n一.. 和limx()?1. 设limx()一,下面我们证明对每一?(0, n—’.. 1)有limx()一O成立.为此只要证明一0.利用 n—+00 z=g(sc)和函数g(sc)在[O,1]上的连续性可得 g()一.假如?O,利用与引理2(a)的证明中 类似的讨论可得序列{Xn())满足()一?0( ?(0,1)).这与上面所得对每一?(0,1)序列 {z())是一个严格单调递减的有界序列这一事实 相矛盾.于是,我们得到一0.因此对每一? (0,1)有limx()一0成立. 2右边正则纠删码的精确阈值 主要目的是证明删除恢复算法下右边正则纠删 码的阈值(以,口)等于,()在[O,1]上的最小值 rain{f(sc)).利用引理1和引理2,我们得如下定 z?EO?1J 理. 定理1对整数?2和口?5设[O,1]上的函 数 一 其中h(z)一++…+z+1.对于度分布为 (A,口)和初始删除概率为?(0,1)的右边正则纠 删码,如果:(口一1)>1,那么其阈值为 (以,口)一ra 0’1 in ] {厂())=rain xE- {,())? z?(O,1][O,1] 根据引理2和函数厂的定义得 {10<<1,limx()一0)一 {l0<<1,g(sc)<z,Vz?(O,1])一 {l0<<1,<厂(z),Vz?(O,1]). 于是得S一{fO<1,.厂(z),Vz?(O,1]). 注意到条件:(a一1)>1成立,依据引理1得 极限rain{f(sc))存在和0<rain{f(sc))<1.由 f(sc)在[O,1]上连续性,我们可选取充分小的e> 0,使得 0<l—rain{f(sc))一e/2<1. ?(0,1] 因此存在?(O,1)使得对所有z?(0,1]有< m!n一{f(sc))?f(sc)成立.这就是说对任意充分小 e>O存在l?S使得l>rain{f(sc))一e成立. 于是,我们得到对所有?S有??1in{f(sc))成 z?tO?lJ 立以及对于每个充分小e>0都存在?s使得> m!n一{f(sc))一e.由此可得sups—rain一{f(sc))[]. 根据阈值的定义得(A,口)一rain{f(sc)),根据 z?(0?1j 引理1(ii)得 (A,口)一rain. {f(sc))一min{f(sc)). z?(0,1]z?Eo,1J 在文献[4]中提出了一类可逼近删除信道容量 限的右边正则纠删码,即其阈值(A,a)可任意 逼近1一R(R为右边正则纠删码的码率).对于具有 给定整数口?5和N?2的这类码: N P(sc)一z,A(sc)一?z,i一2 证明设这里 s一..<<z一1一=_二(二)(一1)’H一..,n,,一1, 自盟科荸遗展第18卷第5期2008年5月599 其中a一1/(n一1),对实数a和自然数P, ()一. 推论1对具有与上面定理相同假设的右边正 则纠删码,若取如上所给的右边正则度分布为(A, n),则 ]{ 证明容易看出 ()cN(一)… (1一号)(1一a)>0. 利用这一结果和a—I/(a--1)可得 2 (n一1)一=_二—N(;)(一1)一口一f1(一1)…\N, ———————— ._——————一,1 一 ()c一?+1口\N, (4) 结合.(n一1)>1,由定理1即得所要证明的结论. 3数值结果 为了证明本文所提出方法的正确性和精确性, 下面给出一些数值结果.考虑具有文献[4]提出的 如上右边正则纠删码.根据推论1知计算阈值问题 归结为求解[0,1]上函数厂(z)的最小值.这个结论 可用(4)式中所给的公式表示. 例如,图1中给出了n一8和N一60时(4)式中 函数厂的示意图,其中参数N一60经过优化使得具 有这样参数的右边正则纠删码的码率逼近1/2.易 见厂(z)是[0,1]上的单调递减函数.因此,根据推 论1易得右边正则纠删码的阈值(A,8)一厂(1) 一1/(2(8—1))一0.495446. 图1口=8和N=60时f()的示意图 表1给出了码率R逼近1/2时一些右边正则纠 删码的阈值,其中参数N经过优化使得其对应的右 边正则纠删码的码率逼近1/2.容易验证对于具有 表1中参数n和N的度分布对应的函数f(z)是[0, 1]上单调递减函数.因此,根据推论1知右边正则 纠删码的阈值(A,n)一f(1)一1/(2(n一1)). 表1最后两列的数据表明所给新方法的正确性和精 确性.容易看出此方法可避免Hehn等所给方法中 为了计算码的阈值而必须求的度分布函数的微分和 逆函数运算n. 对于经过验证的具有表1中参数a和N的度分 布(A,n),f(x)是[0,1]上的单调递减函数.于 是,容易计算厂(z)在[0,1]上的最小值.对于其他 的右边正则度分布(A,n),可将数值解方法或 Mathematca工具软件应用于(4)式求得厂(z)在[0, 1]上的最小值.因此,依据推论1容易确定正则纠 删码的阈值. 表1利用所给方法确定的一些右边正则 纠删码的阈值.其码率R逼近l/2 口N1一R2(口一1)ExactThr. 0.500897 0.501639 0.499648 0.499847 0.50O004 0.500019 0.499987 0.499988 2.079452 2.028946 2.018387 2.008682 2.003891 2.001839 2.000998 2.000516 0.480896 0.492867 0.495446 0.497839 0.499029 0.499541 0.499751 0.499871 一 , } \, z / ,,1 ,1 .一? 一一一 ,,??(, l An朋(.nH 6OO自.燕科荸遗展第18卷第5期2008年5月 4结论 通过将计算阈值问题归结为确定仅依赖于右边 正则度分布(A,n)的[o,1]上函数-厂()的最小值 的方法,证明了计算右边正则纠删码阈值的一个精 确公式.这种方法可避免Hehn等所给方法中为了 计算码的阈值而必须求的度分布函数的微分和逆函 数运算. 应该指出的是本文提出的计算右边正则纠删码 阈值的公式仅对于满足条件.(n一1)>1的右边正 则度分布(A,n)成立.猜想对所有右边正则度分布 这一结果仍然正确.然而,这一问题有待于进一步 证明.本文给出的理论结果将有助于确定级联型纠 删码的阈值. 参考文献 1EliasP.Codingfortwonoisychannels.In:ProceedingsofInfor— marionTheory.ThirdLondonSymp,London,Butterworths, September,NewYork:AcademicPress,1955,61—74 2LubyM..MitzenmacherM.ShokrollahiMA,eta1.Practical loss—resilientcodes.Procofthe29thACMSymposiumonTheo— ryofComputing,ElPaso,Texas,UnitedStates,May,New York.USA:ACM,1997,15O一159 3LubyM.MitzenmacherM,ShokrollahiMA,eta1.Efficient erasurecorrectingcodes.IEEETransInform.Theory.2001, 47(2):569—584 4ShokrollahiMA.Newsequencesoflineartimeerasurecodes approachingthechannelcapacity.In:Proceedingsofthe13th InternationalSymposiumonAppliedAlgebra,AlgebraicAlgo— rithms,andError—CorrectingCodes,Berlin,Germany:Springer— Verlag,1999,1719:65—76 5OswaldP,ShokrollahiMA.Capacity—achievingsequencesfor theerasurechanne1.IEEETransInformTheory,2002,48(12): 3O17—3O28 DiC,ProiettiD,TelatarIE,eta1.Finitelengthanalysisoflow— densityparity—checkcodesonthebinaryerasurechanne1.IEEE TransInformTheory,2002,48(6):157O一1579 Pishro-NikH.FekriF.Ondecodingoflow—densityparity—check codesoverthebinaryerasurechanne1.IEEETransInformTheo— ry,2004,50(3):439—454 GallagerRG.LowDensityParityCheckCodes.Cambridge. Massachusetts:MITPress,1963 ByersJW,LubyM,MitzenmacherM,eta1.Adigitalfountain approachtoreliabledistributionofbulkdata.ACMSIGCOMM ComputerCommunicationReview,1998,28(4):56—67 MaymounkovP.MazoeresD.Ratelesscodesandbigdownloads. In:Proceedingsofthe2ndIntWorkshopPeer—to-PeerSystems (IPTPS’03),Berkeley,USA,February,Germany:Springer- Verlag.USA.2003,1—6 Aguilera,MK,JanakiramanR,XuL.Usingerasurecodeseffi— cientlyforstorageinadistributedsystem.In:Proceedingsofthe 2005internationalConfonDependableSystemsandNetworks, Pennsylvania,USA:IEEEPress,2005,336—345 PlankJS..ThomasonMGA.Practicalanalysisoflow—density parity—checkerasurecodesforwide-areastorageapplications.In: Proceedingsofthe2004InternationalConferenceonDependable SystemsandNetworks,Florence,Italy,June,2004,1O1—11O RichardsonT,ShokrollahiA,UrbankeR.Designofcapacity approachingirregularlow—densityparity—checkcodes.IEEE TransInformTheory,2001.47(2):619—637 HehnT.DOnmezA.HuberJB.ExactthresholdsforLDPC codestransmittedoverbinaryerasurechannels.In:Proceedings of43rdAnnualAllertonConferenceonCommunication,Control, andComputing.Allerton.Monticello,USA,September,USA: Illinois.2005.43—56 IlyinVA.PoznyakEG.FundamentalsofMathematical Analysis.MOSCOW:MIRPublisher,1982,Volume1,55—56 6789uM