外文翻译译文-LDPC的磁化性能降低复杂度

LDPC的磁化性能降低复杂度摘要低密度奇偶校验（LDPC）码是在有噪声的信道中可靠地进行通信的非常有效的方法。N.Sourlas1表明，LDPC码，其革命性的码域和使用的许多通信标准，可以被映射到一个伊辛自旋系统中。此外，已经表明置信传播（BP）算法，即所述LDPC码的解码算法，也叫ThoulessAnderson-帕尔默（TAP）算法2。不幸的是，没有已取得其他解码算法的研究。在本文中，我们开发了Log-LikelihoodRatios-BeliefPropagation（LLR-BP）算法及其简化的BP-Based算法和-Min算法与TAP算法。我们利用统计物理学的方法来表示这些译码算法的性能，用它的性能来表示磁化的功能。关键词：LDPC码，伊辛自旋，LLR-BP算法，基于BP算法，-Min算法，TAP途径1.引言低密度奇偶校验（LDPC）码首次由Gallager3在他的论文中提出，在1962年被麦凯和尼尔3,4重新发现。这些代码可以通过被称为BeliefPropagation（BP）算法5的迭代解码算法非常接近香农极限这一性能加上其相对简单的解码算法使这些代码对下一代数字传输系统非常有吸引力。事实上，这些代码已被选择作为第二代卫星数字视频广播正常化（DVB-S2）的一个标准。因此，寻求高效的解码算法成为一个挑战。BP算法的实现是困难的。这就是为什么有许多这个算法的简化算法被发现。BP算法可以通过BP-Based算法6和分钟算法7被简化N.Sourlas在1989年表示,有一个对应于一些自旋玻璃模型理论的纠错码的数学等价。这个分析对目前的统计物理学和信息理论做出了贡献。因此,统计物理学在无序系统里面的应用被证明是有效的学习这些代码的性能的方法。其中一个方法就是由kabashima等提出的接近BP算法的Thouless-AndersonPalmer(TAP)算法.不幸的是,还没有其他解码算法。在本文中，我们开发了Log-LikelihoodRatiosBeliefPropagation（LLR-BP），BP-Based和-min解码算法与TAP的方法。他们的性能被评价为统计物理的功能参数，也就是磁化。本文组织如下。第二部分部对应LDPC码的一般描述和他们的解码算法。第三节描述BP算法和TAP方法之间的相似性。在第4节，我们开发的LLR-BP算法简化了BP-Based算法和min算法与TAP的方法。最后，总结之前，磁化功能的仿真结果示于第5节。2.LDPC码的译码算法2.1低密度奇偶校验码二进制LDPC码，是由一个稀疏奇偶校验矩阵AMN来描述的，其中N表示所定义的线性分组码码字长度,M表示paritycheck方程的数目。使用类似于4,6的矩阵的符号，让Lj/Aj1表示j位的节点参与到u的校验，同样，我们定义一个校验节点，其中j位代入Mj/Aj1。我们通过排除Lj表示一个节点L与j位，通过排除Mj来表示一个节点Mj和同样的校验。最后，S=(s1，.,sN)表示所发送的码字2.2置信传播算法本节根据4,5矩阵，说明了基于BP算法的LDPC码的迭代译码。s的可能性是由和fjaP(sj=a).得出。让表示s的j位的概率是a,通过所给的信息完成校验，而不是校验。的数量意味着校验的概率是满意的，如果s的第j位被认为是固定在a中，并且由ql:lLj6得到的其它位的概率是分离分布的。基于BP算法的标准迭代译码算法包括以下主要步骤。初始化：变量和分别被初始化为和迭代处理：1)定义，对每一个,jL,a0,1,计算：2)对每一个j和Mj,a0,1j和j被选择如下3)创建一个字用来检测所发送的码字，使得：如果，译码处理结束。否则，我们传递给BP另一次迭代。，如果迭代次数超过迭代的最大数目，就宣告失败并且译码处理结束s不是一个有效的码字。3.从统计物理学的角度看译码3.1.统计物理学类比在上一节，我们用添加的布尔组0,1，+描述了LDPC码。然而，为了应用统计物理学的方法，引入等效基团是很方便的，即乘法二进制组1,1,1。从统计物理学的角度来看，此代码可以被视为一个自旋系统。每一位叫做一个自旋，在1中取值，字可以被视为N个自旋的集合，叫做构造，所述奇偶校验矩阵，引起自旋1之间的相互作用。译码问题取决于后天的像PSJ，其中J是证据（收到的消息或综合征载体）通过运用贝叶斯定理可以写成如下形式1。在统计物理学描述中，（1）的概率在逆温度9下可表示为一个波尔兹曼分布HSJ是系统的汉密尔顿函数，在这个汉密尔顿函数中，我们定义两个组件，它们对LDPC码的分析是必要的。一个条件，保证所有的奇偶校验都满意。可以被写入Kronecker增量1中根据9，可以通过一个软约束来代替前一个条件，它提供了动态变量S的一些统计信息。它可以通过现有的分布来表示。F是外磁场，它是由信道噪声的翻转率f定义的，因此，汉密尔顿函数HSJ书写如下J是多重自旋耦合。3.2.在统计物理学中译码该译码处理对应于寻找本地逆温度下的磁化强度，j估算为1。在统计物理中的译码性能逼近，可以通过磁化1来测定，由实际的消息和估量之间的迭代来定义：在这里，超出的由矩阵A完成。该值将提供有关代码的典型的性能信息。磁化强度是具有判断整个系统是否有一个有序状态的标准的有序参数。如果m1，系统处于一个有序相，称为铁磁相如果m0，系统处于一个无序相，称为顺磁相有两种主要方法可用于计算磁化值：稀释系统9的摹本方法和TAP逼近8。在本文中，我们只对TAP逼近方法感兴趣。3.3TAP逼近Kabashima，等人。8已经表明了从TAP2逼近方法推导的公式和由BP方法获得的公式的相似性，区域对应的除了节点j之外的其他节点的平均影响。区域代表j对系统作用区域10的影响。它们之间的相似性正比于玻尔兹曼重量11，可以通过观察PJS发现。条件概率可以看作是由固定的比特的Sj10而获得的归一化的有效波尔兹曼重量（有效波尔兹曼概率）10由于自旋变量Sj只有两个值1，用和的自旋均值是很方便的表达BP/TAP算法的，而不是用分布的和本身。我们使用qjmj来表示类似的符号被用来表示此外，以下的陈述已经在10中展示。计算伪验证提供了一种计算贝叶斯最优译码算法，如下qjmj的证明结果如下4.LLR-BP算法与其TAP逼近的简化4.1LLR-BP算法和TAP逼近在LLR-BP算法中，我们处理LLRs而不是处理3,5矩阵中的概率。在实际中，使用LLRs作为消息实现，优于使用概率或似然比，因为，乘法被加法替换，并且，归一化步骤11.也被消除。在本节中，我们尝试用TAP逼近开发LLR-BP算法，用和作为LLRs的j位，这分别是从位节点j到校验节点和从校验节点到位节点j，从统计物理学定义，所述LLR的定义如下12：我们还需要如下的结果在（12）中，变量也可以写成：因此，从方程（5）（12）（13）我们可以得到同样可以被写为：最后，后验，Sj的LLR位是：以乘积的形式实现（15）并不容易，我们的想法是分解校验节点转换成对符号和幅值的处理，就想在（13）中一样，我们有（15）的形式：在（17）中，用替换J，用替换xl：ft定义为：（19）的两边分别取对数：验证（20）方程：方程（21）可表示为：从（18）到（24）对校验节点在物理统计学上的处理可表示为：4.2BP-Based的TAP逼近在本节中，我们尝试开发BP算法的逼近：BP-Based6算法的TAP逼近。该算法的关键思想是，函数ft的描绘如图1，明显不平均。方程（24）近似为：所以，写入在TAP方程的BP-Based算法中的非本征信息如下因此，在BP-Based算法的TAP逼近中存在一个重要的简化，当校验节点被替换为选择的最小的输入值时。4.3-Min算法的TAP逼近在这一部分，我们尝试做一个-min算法的TAP逼近，在校验节点修改（25），用（20）中的函数实现对幅值的处理。在图1中描绘这个函数时，很明显，当取最小值的时候，ft取最大值，此时，可以近似为。因此，像Guilloud，等，只有位参与校验时，我们计算出（24）有最小的幅值：图1.函数f的波形包含位的Lj0,.,j1参与校验，是L的子集，有最小的幅值-min算法的TAP方程的非本质信息由（29）给出会出现两种情况：如果j位属于L子集,yj被进行Lj处理1次，否则，yj被进行Lj处理次，第二种情况下，计算必须被执行一次13.5.模拟结果仿真已经被使用长度为N1008的矩阵为（3,6）的LDPC码长度为N1008的正则LDPC码迭代译码20次。我们队10个码进行平均。这些LDPC码的集合被同一个块的长度特征化，在每一行和每一列。对于每次运行，一个固定的码被用来从504位的消息中产生1008位码字。损坏的码字，然后用LLR-BP，BP-Based和-min译码算法译码。从统计物理学的观点观察（27）和（29）的简化对结果的影响，我们已计算出每个固定码和算法的实际的消息和估计值（磁化）之间的重叠。之后，我们对得到的10个不同的码进行平均。图2描述了LLR-BP，BP-Based和-min算法的磁化性能。通过图2的结果，我们可以得出-min算法的有效性，在磁化强度为0.9的情况下，BP-Based算法在20次迭代后下降了0.5db2-min算法在20次迭代后下降了0.3db,3-min算法的性能比LLR-BP算法略差，降低了仅仅0.08分贝。图2的另一个要点，在高信噪比的情况下，磁化集中在值V=1时。这个值对应于统计物理学和信息论中完美解码的铁磁态。误码率性能和磁化性能之间的相似性能在14中被检查出来。6.总结在本文中，我们一直对LDPC从统计物理学方法的解码感兴趣。首先，我们研究LDPC码和伊辛自旋系统之间的对应关系。对BP算法和TAP逼近之间的关系进行了研究，。然后，我们展示了LLR-BP算法及对它的简化等。在统计物理学中，利用伊辛自旋系统的TAP逼近可以得到BP-Based算法和-min算法。此外，我们已经用统计物理学的参数表现了译码算法的性能，即磁化。最后，我们得出，BP-Based算法降低了更新外在信息的复杂度，但其性能相比于LLR-BP算法有所下降。-min算法降低了更新外在信息的复杂度，但其性能相比于LLR-BP算法没有下降，尤其当增大时。这些结果证实了信息理论中获得的结果。图2所示为，当=2,3,(1008,3,6)的LDPC码合凑迭代20次时，LLR-BP，BPBased和-min算法的磁化性能。从我们工作的角度来看，我们建议学习复制法。这是一种将统计物理学应用到磁化的方法。此外，为了比较分析结果与实验结果，我们提出通过相同的近似法来简化BP-Based算法和-min算法中的方程。参考文献1N.Sourlas,“Spin-GlassModelsasError-CorrectingCodes,”Nature,Vol.339,No.6227,1989,pp.693-695.2D.J.Thouless,P.W.AndersonandR.G.Palmer,“SolutionofSolvableModelofASpinGlass,”PhilosophicalMagazine,Vol.35,No.3,1977,pp.593-601.3R.G.Gallager,“Low-DensityParity-CheckCodes,”M.I.T.Press,Cambridge,Massachusetts,1963.4D.J.C.MackayandR.M.Neal,“NearShannonLimitPerformanceofLowDensityParityCheckCodes,”ElectronicsLetters,Vol.32,No.18,1996,pp.1645-1646.5D.J.C.Mackay,“GoodError-CorrectingCodesBasedonVerySparseMatrices,”IEEETransactionsonInformationTheory,Vol.45,No.2,1999,pp.399-431.6M.P.C.Fossorier,M.MihaljevicandI.Imai,“ReducedComplexityIterativeDecodingofLowDensityParityCheckCodesBasedonBeliefPropagation,”IEEETransactionsonCommunications,Vol.47,No.5,1999,pp.673-680.7F.Guilloud,E.BoutillonandJ.L.Danger,“-MinDecodingAlgorithmofRegularandIrregularLDPCCodes,”Proceedingsof3rdInternationalSymposiumonTurboCodes&RelatedTopics,Brest,2003,pp.451-454.8Y.KabashimaandD.Saad,“BeliefPropagationvs.TAPforDecodingCorruptedMessages,”EurophysicsLetters,Vol.44,No.5,1998,pp.668-674.9T.Murayama,Y.Kabashima,D.SaadandR.Vicente,“StatisticalPhysicsofRegularLow-DensityParity-CheckError-CorrectingCodes,”PhysicalReviewE,Vol.62,No.2,2000,p