您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 资本运营 > LDPC密度进化和稳定性收敛性分析.
密度进化和稳定性条件LDPC码的定义噪声门限的定义BP译码方法基于密度进化方法的稳定性条件EXIT图分析LDPC是线性分组码的一种,由其校验矩阵所定义。由于校验矩阵一般为稀疏矩阵,所以称其为“低密度奇偶校验码”。H为校验矩阵,x为码字。故有如下关系:𝐻=10…000…010…1𝐻𝑥𝑇=0𝑇规则LDPC码主要参数码长n信息位k码率r=k/n变量节点度dv校验节点度dcE.g.10,3,6,𝑟=0.5码字集合(Ensemble):𝐶𝑛(𝑑𝑣,𝑑𝑐)11110110000011111100010101011110101001111100101011HChecknodesVariablenodes变量节点度dv表示每一个变量节点参与了dv个校验方程,即有dv个限值条件。这些限值条件都给该变量节点一定的(外)信息量。进而估计也就越准确,迭代译码时收敛得也就越快。校验节点度dc校验节点度数越小,表明变量节点提供给它的信息越有价值。先从校验节点向变量节点发送的信息角度出发,即沿有向边𝑒𝑖=𝑐𝑖,𝑣𝑖的信息。该信息反映了该变量节点参与的校验方程的所包含的限值条件,反映了其他节点对该节点上的随机变量是+1/-1的看法。E.g.针对第一个校验节点的方程𝑥1+𝑥2+𝑥3+𝑥4+𝑥6+𝑥7=0𝑥𝑖=𝑥𝑗𝑗≠𝑖𝑗∈𝜋(1)其中,𝜋(k)为连接第k个校验节点的变量节点的集合Nodesqueryneighboringnodestocollectopinions,processthisinformation,andforwardtheircurrentestimatetotheirneighbors.对于变量节点译码器,会首先询问校验节点的意见进行参考。Informationflowsupthetree.TheRenaissanceofGallager’sLow-DensityParity-CheckCodes从校验方程上可以看出,第一个校验节点传递给第i个变量节点的信息,应该只与其他变量节点的信息有关,与第i个变量节点给校验节点的信息无关。故将传递给第i个变量节点的信息称“外信息”。因此,在Tanner图中就不希望存在短环,因为短环会引入错误的过时信息,理想状态下是无环。在同一条边上传递的信息𝑚(𝑙)并不依赖于以前在这条边上传递的信息𝑚(𝑙−1),故在变量节点和校验节点间只相互传递外信息。其间信息传递的映射关系为:Ψ𝑣(0):𝒪→ℳ,𝑙=0Ψ𝑣(𝑙):𝒪×ℳ𝑑𝑣−1→ℳ,𝑙0Ψ𝑐(𝑙):ℳ𝑑𝑐−1→ℳ𝒪:inputalphabet⊂ℳ:messagealphabetChecknodesVariablenodesinput针对一定的编码和译码算法,在不同信道模型下会有对应信道条件的信道参数,而门限(threshold)值则对应最大的可译码的信道参数。例如,在BIAWGN(binaryAWGN)下,该对应着可译码的最大归一化的噪声能量。在BSC(binarysymmetricchannel)中信道参数为probabilityofcrossover。当信道的信道参数大于门限,意味着无论怎样迭代,错误概率始终会大于一个常数。如何才能确定该译码算法在信道容量下的门限值?当信道参数为𝜎≤𝜎∗(门限),经过无限次迭代后,错误概率趋向于零。在上述条件下,假定我们发送的码字为“全一码字”,则在经历迭代译码的时候,码字被判为“零”的概率(概率密度)应该趋向于零。该概率密度在迭代译码过程的变化被称为“密度进化(DensityEvolution)”。Channelsymmetry:Thechannelisoutput-symmetric,i.e.𝑝𝑦𝑡=𝑞𝑥𝑡=1=𝑝𝑦𝑡=−𝑞𝑥𝑡=−1Checknodesymmetric:Signsfactoroutofchecknodemessagemaps,i.e.Ψ𝑐(𝑙)𝑏1𝑚1,…,𝑏𝑑𝑐−1𝑚𝑑𝑐−1=Ψ𝑐(𝑙)𝑚1,…,𝑚𝑑𝑐−1𝑏𝑖𝑑𝑐−1𝑖=1Variablenodesymmetry:Ψ𝑣(𝑙)−𝑚0,−𝑚1,…,−𝑚𝑑𝑣−1=−Ψ𝑣(𝑙)𝑚0,𝑚1,…,𝑚𝑑𝑣−12001_Thecapacityoflow-densityparity-checkcodesundermessage-passingdecoding当上述的对称性条件满足时,假设我们发送的二元码字为𝒙,则对于message-passing译码算法,在第l次迭代时的错误概率𝑃𝑒𝑙𝒙与码字𝒙相互独立。故而可以用全一码字代替。证明:接收端收到的值为𝑦=𝒙𝑧,𝑧为独立的随机变量从译码节点与变量节点之间所传递的信息满足𝑚𝑖𝑗𝑙+1𝑦=𝒙𝑚𝑖𝑗𝑙+1𝑧让我们考虑BSC信道模型crossover的概率为ϵ𝒪=ℳ=+1,−1,m∈ℳ发送为全一码字,故有初始概率分布▪𝑝1(0)=1−ϵ𝑝−1(0)=ϵ译码方法Ψ𝑣0𝑚0=𝑚0,初始的发送信息为直接观测得到值Ψ𝑣(𝑙)𝑚0,𝑚1,…,𝑚𝑑𝑣−1=−𝑚0,𝑖𝑓𝑚1=⋯=𝑚𝑑𝑣−1−𝑚0𝑚0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒Ψ𝑐(𝑙)=𝑚𝑖𝑑𝑐−1𝑖=1上述模型和译码算法均满足对称性条件𝜖𝑙1−𝜖𝑙在每次迭代中,其相应的+1/-1概率密度可以计算得到,Ψ𝑐∗为面向信息概率分布进行的映射:校验节点的概率分布对▪𝑞−1(𝑙),𝑞1(𝑙)=Ψ𝑐∗𝑝−1(𝑙−1),𝑝1(𝑙−1),…,𝑝−1(𝑙−1),𝑝1(𝑙−1)=121−1−2𝑝1𝑙−1𝑑𝑐−1,1+1−2𝑝1(𝑙−1)𝑑𝑐−1变量节点的概率分布对▪𝑝−1(𝑙),𝑝1(𝑙)=Ψ𝑣∗𝑝−1(0),𝑝1(0),𝑞−1(𝑙),𝑞1(𝑙),…,𝑞−1(𝑙),𝑞1(𝑙)=𝑝1(0)𝑞−1(𝑙)𝑑𝑐−1+𝑝−1(𝑙)1−𝑞1(𝑙)𝑑𝑐−1,𝑝−1(0)𝑞1(𝑙)𝑑𝑐−1+𝑝1(𝑙)1−𝑞−1(𝑙)𝑑𝑐−1合并两个迭代方程,消去q,可以得到回归的密度进化公式▪𝑝−1(𝑙)=𝑝−1(0)−𝑝−101+1−2𝑝−1𝑙−1𝑑𝑐−12𝑑𝑣−1+1−𝑝−1(0)1−1−2𝑝−1𝑙−1𝑑𝑐−12𝑑𝑣−1当𝑝−1(0)=ϵ增大时,𝑝−1(𝑙)也会增大,合乎逻辑。可由lim𝑙→∞𝑝−1(𝑙)=0的充分性确定threshold门限ϵ*。置信传播译码(BP)也称作和积译码算法(sum-product),仍是message-passing信息传播译码算法的范畴之内。针对信息字母表ℳ:messagealphabet将具体的离散的字母表替换为表示概率密度分布之比的连续的字母表(软信息soft)。𝑚=log𝑝𝑥=1|𝑦𝑝𝑥=−1|𝑦=log𝑝𝑦|𝑥=1𝑝𝑦|𝑥=−1=log𝑝1𝑝−1▪相较之前的离散的信息,该方案有更好的精确度。对于变量节点译码器,在给定码字的条件下各个节点得到有关该码字的似然比应该是条件独立的。其原因是由码字间相互独立,输入变量条件独立给出的。𝑙𝑘=𝑝𝑥′=+1|𝑥∈𝜋(𝑘)𝑝𝑥′=−1|𝑥∈𝜋(𝑘)第k个校验节点的信息𝑚=log𝑝𝑥′=+1|𝒙𝑝𝑥′=−1|𝒙=log𝑙𝑖𝑑𝑣−1𝑖=1=𝑚𝑖𝑑𝑣−1𝑖=1Ψ𝑣(𝑙)𝑚0,𝑚1,…,𝑚𝑑𝑣−1:=𝑚𝑖𝑑𝑣−1𝑖=0Ψ𝑣∗𝑃0,𝑃1,…,𝑃𝑑𝑣−1=𝑃0⨂𝑃1⨂…⨂𝑃𝑑𝑣−1在随机变量独立的假设下,校验节点输出的log似然比为:𝑚=log𝑝1𝑝−1,𝑝−1=Pr𝑥𝑖𝑑𝑐−1𝑖=1=−1是相关随机变量乘积为-1的概率。通过变换到GF(2)域,卷积映射到傅立叶变换DFT得到:𝑝0−𝑝1=𝑝0𝑖−𝑝1𝑖𝑑𝑐−1𝑖=1=tanh𝑚𝑖2𝑑𝑐−1𝑖=1Ψ𝑐(𝑙)𝑚1,…,𝑚𝑑𝑐−1:=log1+tanh𝑚𝑖2𝑑𝑐−1𝑖=11−tanh𝑚𝑖2𝑑𝑐−1𝑖=1概率密度对𝑝0,𝑝1既可以表示为log𝑝0𝑝1似然比形式,也可以表示为如下形式:𝐥𝐠𝑠𝑔𝑛(𝑝0−𝑝1),log|𝑝0−𝑝1|∈GF2×0,∞令γ表示上述变换:γ:−∞,∞⟼GF2×0,∞则上述映射关系等价为:Ψ𝑐(𝑙)𝑚1,…,𝑚𝑑𝑐−1:=γ−1γ𝑚𝑖𝑖非规则的LDPC码有更多的自由度,故而性能较规则码更好。变量节点度分布——𝜆𝑥:=𝜆𝑖𝑥𝑖−1𝑑𝑣𝑖=2校验节点度分布——𝜌𝑥:=𝜌𝑖𝑥𝑖−1𝑑𝑐𝑖=2▪𝜆𝑖(𝜌𝑖)代表度为i的节点所连接边的个数占总的边数的比例。▪码率:𝑟𝜆,𝜌=𝑛−𝑚𝑛=1−𝜌𝑖/𝑖𝑑𝑐𝑖=2𝜆𝑗/𝑗𝑑𝑣𝑗=2=1−𝜌𝑥10𝑑𝑥𝜆𝑥10𝑑𝑥为什么采用边的分布?▪可以解释为信息是沿着边传播的,故而以边的比例作为度分布更为合理。𝑚𝑣𝑐(𝑙)=𝑚0𝑚0+𝑚𝑐′𝑣(𝑙)𝑐′∈𝐶𝑣\𝑐if𝑙=0if𝑙0𝑚𝑐𝑣(𝑙)=γ−1γ𝑚𝑣′𝑐(𝑙)𝑣′∈𝑉𝑐\𝑣从变量节点发向校验节点的信息的概率分布为其加和单元的概率分布的卷积和。𝑃𝑧1+𝑧2=𝐹𝑧1⨂𝐹𝑧2//𝑧𝑖相互独立然而,从校验节点向变量节点传递的信息分布需要在另一个域GF2×0,∞中刻画。γ(𝑧)=𝐥𝐠𝑠𝑔𝑛𝑧,log|tanh(𝑚2)|定义GF2×0,∞上的概率分布有如下形式:▪𝐺𝑠,𝑥≔𝛿𝑠𝐺0𝑥+𝛿𝑠−1𝐺1𝑥对于分布在(−∞,∞]上的随机变量𝑧,对应的γ(𝑧)的概率分布函数为Γ𝐹𝑧𝑥=𝛿𝑠Γ0𝐹𝑧𝑥+𝛿𝑠−1Γ1𝐹𝑧𝑥其中(注意为反函数)▪Γ0𝐹𝑧𝑥=1−𝐹𝑧−−ln𝑡𝑎𝑛ℎ𝑧2=Pr{γ1𝑧=0,γ2𝑧≤𝑥}▪Γ1𝐹𝑧𝑥=𝐹𝑧(ln𝑡𝑎𝑛ℎ𝑧2)=Pr{γ1𝑧=1,γ2𝑧≤𝑥}z−ln𝑡𝑎𝑛ℎ|𝑧2|由上述的在GF2×0,∞域中的概率分布函数可知,从校验节点发出的信息分布可如下表示:对应从度为i的校验节点发出的𝑚𝑐𝑣(𝑙)的概率分布卷积和为Γ−1(Γ𝑃𝑙−1⨂(𝑖−1))各个校验(变量)节点平均下来得到▪𝑄𝑙=Γ−1𝜌𝑖Γ𝑃𝑙−1⨂𝑖−1𝑖≥2=Γ−1(𝜌Γ𝑃𝑙−1)▪𝑃𝑙=𝑃0⨂𝜆𝑖Γ𝑄𝑙⨂𝑖−1𝑖≥2=𝑃0⨂𝜆(𝑄𝑙)Recursionfuntion:𝑃𝑙=𝑃0⨂𝜆Γ−1𝜌Γ𝑃𝑙−1对于可擦除信道而言,在迭代过程中信息的取值为离散值𝑚=log𝑝𝒚|𝑥=1𝑝𝒚|𝑥=−1=log𝛿𝑦+11−𝜖+𝛿𝑦𝜖𝛿𝑦−11−𝜖+𝛿𝑦𝜖=𝛿𝑦+1+∞+𝛿𝑦∙0+𝛿𝑦−1−∞如果我们用全一码字,则其初始密度分布为𝑃0=𝜖𝛿𝑚+(1−𝜖)𝛿𝑚−∞由于BEC的特殊性,第l次迭代时的概率密度为𝑃𝑙=𝜖𝑙𝛿𝑚+(1−𝜖𝑙)𝛿𝑚−∞𝜖𝑙1−𝜖𝑙带入上述的回归方程,我们得到了BEC的密度进化公式:𝜖𝑙=𝜖0𝜆(1−𝜌(1−𝜖𝑙−1))可以看出,选
本文标题:LDPC密度进化和稳定性收敛性分析.
链接地址:https://www.777doc.com/doc-2883765 .html