资源描述：
《关于LDPC码的BP译码算法以及改进算法尝试》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、LDPCLDPC码码BPBP译码算法译码算法目录•LDPC码编译码基础。•硬判决译码算法。•软判决译码算法•后验概率。•Gallager定理。•BeliefPropagation(BP)算法。•因子图。•具体算法。•BeyondBP算法。2014-2-252LDPC码编译码基础•1962年，Gallager提出低密度奇偶校验码(LowDensityParityCheckCodes,LDPCCodes)[1]。•优点：•线性分组码。•AWGN信道下性能接近香农限。•校验矩阵H具有稀疏性，便于实现。[1]R.G.Gallager,“Low-densityparitychec
2、kcodes,”IRETrans.Inf.Theory,vol.39,no.1,pp.37–45,Jan.1962.2014-2-253LDPC码编译码基础•对于一个正确的LDPC码c，其必定满足校验方程(H·cT=0)的要求。这是译码算法的理论基础。•这里H称为校验矩阵。2014-2-254硬判决译码算法•比特反转译码算法：•利用接收到的硬判决码字计算校验方程。•统计每个比特参与的校验方程不成立的个数，当数量超过门限值时反转该比特。•特点：•便于理解，易于实现，译码速度快。•纠错能力有限。2014-2-255软判决译码算法•后验概率•Pr(c=1
3、y,S)表示，当接收
4、的符号为y=[y，y，···，i01y]，码字集合为S时，传输的码字c=[c，c，···，cn-101n-]中c=1的概率。1i•边沿后验概率的大小反映了码字比特置信度(Belief)的大小。•Pr(c=0
5、y,S)+Pr(c=1
6、y,S)=1；ii•我们用如下方式计算码字比特的置信度：kPr[cy=−0
7、,]SP1j⎡1(+−∏12P)⎤ii=∏⎢l=1dl⎥kPr[cyii=1
8、,]SPd=1⎢⎣1(−−∏l=112Pdl)⎥⎦2014-2-256Gallager定理[1]•P表示经过信道传输后，第i个比特为1的初始概i率，其与信道有关。对于变量点度为j，校验点度为
9、k的规则LDPC码，P表示第d个校验方程中第ldl个变量点为1的概率，由此可得：kPr[cy=−0
10、,]SP1j⎡1(+−∏12P)⎤ii=∏⎢l=1dl⎥kPr[cyii=1
11、,]SPd=1⎢⎣1(−−∏l=112Pdl)⎥⎦•问题：此定理在k个比特独立的情况下成立，若比特之间不独立呢？2014-2-257BeliefPropagation(BP)算法[2]•1982年由Pearl提出，用于计算贝叶斯网络(Bayesnets)的边沿概率。•此算法除了用于贝叶斯网络，同样可以用于马尔科夫随机场(Markovrandomfields,MRF)，图模型(Graphicalm
12、odels)与因子图(Factorgraph)。•Bayesnets，MRF,Graphicalmodels,Factorgraph的共同特点：•一个多变量的联合概率问题能够被分解成多函数的形式。[2].J.Pearl,“ProbablisiticReasoninginIntelligentSystems,”SanFrancisco,CA:Kaufmann,1988.2014-2-258因子图[3]k1−Pj⎡1(+−∏12P)⎤=il⎢=1dl⎥Pr(,,,PjkPidl)∏kPid=1⎢⎣1(−−∏l=112Pdl)⎥⎦[3]F.R.Kschischang,B.J.
13、Frey,H.-A.Loeliger,“Factorgraphsandthesum-productalgorithm,“,IEEETrans.Inform.Theory,vol.47,no.2,pp.498,519,Feb20012014-2-259Tanner图[4]与LDPC码[4]R.M.Tanner,“Arecursiveapproachtolowcomplexitycodes,”IEEETrans.Inform.Theory,vol.27,no.9,pp.533–547,Sep.1981.2014-2-2510面向LDPC码的BP算法•采用BP译码算法，能够有
14、效的完成对Pr(,,,PjkPidl)的计算。•如果因子图中无环形结构(树形结构)，BP算法将计算得出最优解，否则BP仅能够提供次优解。•BP算法能够用于多种领域，这里我们主要对应用于LDPC码的BP译码算法[5]进行讨论。[5]W.E.Ryan,“AnIntroductiontoLDPCCodes,”CRCHandbookforCodingandSignalProcessingforRecordingSystems,Ed.,B.VasicandE.Kurtas,CRCPress,2004.2014-2-2511LDPC码的BP译码算法•
