（通信与信息系统专业论文）低密度校验码理论及其译码研究.pdf

摘要 设计性能逼近信道容量、编译码复杂度较低的实用好码是信道编码领域中最 重要的工作之一。基于图模型的l d p c 码是一种有较低的迭代译码复杂度和接近 s h a n n o n 容量限的渐近好码。作者在深刻地理解了l d p c 码的基本原理基础之上， 对l d p c 码基于因子图的和积算法做了深入的研究，给出了一种双向信息传递策 略的实现算法，著且基于矩阵分解，提出了l d p c 码的串行级联译码算法。通过 理论分析和计算机仿真的方法得出了串行级联译码算法具有较快的收敛速度和 优异性能的结论。 本论文主要完成了以下几个方面的工作： 1系统地阐述了l d p c 码的图模型表示方法及基于图模型的译码原理；详 细地介绍了l d p c 码的构造方法及其线性编码理论；介绍了用于l d p c 码阈值分析和度序列设计的密度进化理论； 2在深入地研究了l d p c 码的基于因子图模型的和积算法基础之上，给出 了一种双向信息传递策略的实现方案，提出了一种l d p c 码的串行级联 译码算法。在详细阐述了新算法的基本原理、译码结构及实现步骤之后， 利用理论分析和计算机仿真的方法，对串行级联译码算法和传统的置信 传播算法的性能做了比较，得出了一些有用的结论。 3 深入讨论了l d p c 码作为分量码的多层编码调制系统的基本原理及其密 度进化理论的分析方法。介绍了l d p c 码的多层编码调制系统中，分量 码码率与度序列分布联合最优的设计准则，并给出了相应的理论分析。 关键词：低密度校验码图模型和积算法密度进化理论多层编码调制 a b s t r a c t d e s i g n i n gc o d e sw i t ha p p r o a c h i n gs h a n n o n sc a p a c i t yp e r f o r m a n c e a n dl o w c o d i n ga n dd e c o d i n gc o m p l e x i t yi s ac h a l l e n g i n ga n dm e a n i n g f u li s s u ei nc h a n n e l c o d i n gf i e l d l o w d e n s i t yp a r i t y c h e c kc o d e ( l d p cc o d e s ) i sak i n do fa s y m p t o t i c g o o dc o d e st h a t c a na p p r o a c hs h m m o n sc a p a c i t yw i t hl o wc o m p l e x i t yi t e r a t i v e d e c o d i n g i nt h i st h e s i s ，t h e a u t h o rp r o p o s e da na l g o r i t h mt or e a l i z et h et w o - w a y s c h e d u l ea n dan e wl d p cd e c o d i n ga l g o r i t h mc a l l e ds e r i a lc o n c a t e n a t e dd e c o d i n g a l g o r i t h mb a s e d0 1 1t h o r o u g h l ys t u d y i n gt h ep r i n c i p l e so fd e c o d i n gf o rl d p c c o d e s s o m es i m u l a t i o nr e s u l t sa n dv a l u a b l ec o n c l u s i o n sh a v eb e e ni n t e r p r e t e di nt h et h e s i s t o o t h e f o l l o w i n ga s p e c t sa r ei n v e s t i g a t e di nt h i st h e s i s 1t h eb a c k g r o u n da n dr e s e a r c hs i t u a t i o no fl d p cc o d e sa r ep r e s e n t e da n dt h e c u r r e n tr e s e a r c hr e s u l t sa r ei n t r o d u c e di nt h ef i r s tp a r to ft h et h e s i s ，g r a p h p r e s e n t a t i o n a n d s u m - p r o d u c ta l g o r i t h m a r e i n t e r p r e t e d i nd e t a i l l i n e a r c o d i n gt h e o r y a n de f f i c i e n t c o n s t r u c t i n g m e t h o d so nl d p cc o d e sa r e s y s t e m i c a l l yi n t e r p r e t e dl a t e r at o o lo fa n a l y z i n g t h ep e r f o r m a n c eo fl d p c d e c o d e ra n dd e s i g n i n gt h ed e g r e ed i s t r i b u t i o no fl d p cc o d e si si n t r o d u c e d t o o 2 a f t e rab r i e f i n t r o d u c t i o nt ob e l i e f p r o p a g a t i o na l g o r i t h ma n dac l o s er e s e a r c h o nt h em e s s a g e f l o w i n gs c h e d u l e ，an e w s e r i a lc o n c a t e n a t e dd e c o d i n gm e t h o d o fl d p cc o d e sb a s e do nt h em a t r i xd e c o m p o s i t i o na n dt h et w o w a ys c h e d u l e i sp r o p o s e di nt h i st h e s i s i ta i m sa tg a i n i n gf a s tc o n v e r g e n c ew i t ht h es a m e c o m p l e x i t y a st h ec o n v e n t i o n a lb e l i e f p r o p a g a t i o na l g o r i t h m d e n s i t y e v o l u t i o nt h e o r ya n a l y s i sa n dp r o g r a m m i n gs i m u l a t i o nr e s u l t ss h o wt h a tt h i s n e w a l g o r i t h m h a sf a s tc o n v e r g e n c e s p e e d a n dg o o d p e r f o r m a n c e 3 i nt h ea c t u a lc o m m u n i c a t i o ne n v i r o n m e n t ，c h a n n e lb a n d w i d t hi so f t e n1 i m i t e d b a n d w i d t he f f i c i e n tm u l t i l e v e lc o d e dm o d u l a t i o ns y s t e mb a s e do nl d p c c o d e si sd e s c r i b e di nt h el a s tp a r to ft h i st h e s i s ，f u r t h e r m o r e ，t h ed e s i g n i n g r n e t h o do f c o m b i n i n gc o m p o n e n t c o d er a t ea n d d e g r e e d i s t r i b u t i o ni s i n t r o d u c e d k e ，- a o r d s ：l d p cc o d e s g r a p h i c a lm o d e l ss u m p r o d u c ta l g o r i t h m d e n s i 哆e v o l u t i o nt h e m t m u l t i l e v e lc o d e dm o d u l a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 蒌缘日期：丝缱! ! 丝 关于论文使用权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。( 保密的论文 在解密后遵循此规定) 本人签名 导师签名： 圣望 曰期：7 护韩，名 第一章绪论 第一章绪论 本章首先阐述了数字通信系统的模型和信道编码定理；其次介绍了几种对称 信道模型及相应的信道容量；再次简要介绍了本文中心议题一一l d p c 码的发展简 史及其未来的研究方向；最后给出了本文的主要工作和以后章节的行文安排。 1 1 数字通信系统和信道模型 当今社会是一个信息化的社会，大量形式多样的信息传递对通信技术的要求 越来越高a 电子技术的发展使通信的质量变得越来越好，速率变得越来越快。通 信技术从2 0 世纪上半叶以模拟系统占主要地位走到了2 0 世纪下半叶数字通信系 统的迅猛发展，对数字通信系统的研究也步入了崭新的阶段，为人们提供方便、 快捷、高效的通信手段是广大通信领域工作者的目标。 i i i 数字通信系统 通信系统的作用在于提供信源与信宿之间条快速、可靠、安全地交换信息 的通道。由于数字信息本身处理的灵活性、易加密性以及快速存取、恢复等特性 使数字通信系统倍受人们的青睐。但是，通信系统中电子设备以及传输媒质等引 入的各种噪声和干扰降低了通信的可靠性。在各种限制条件及噪声干扰下如何实 现可靠而高效的传输信息是通信系统设计的关键问题【6 j 。通信历史中，人们曾一 度认为：传输的可靠性与高效性是一对不可调和的矛盾，有干扰信道上实现无错 误传输的唯一途径是使信息传输速率降到零。直到1 9 4 8 年，香农篇名为通信 的数学理论论文的发表，给现代通信带来了曙光，奠定了信息论及编码理论的 基础。香农证明：只要传输的信息速率小于信道容量，就可以通过编码方式实现 信息的可靠传输嘲【3 】【4 1 。 根据香农信息传输理论，点对点数字通信系统的基本组成如图1 1 所示： 图1 i通信系统模型 编码信道 2低密度校验码理论及其译码研究 信息论从通信系统整体的最优化来研究信息的传输和处理。信息论中，建立 了衡量通信系统中信息的量度信息量的概念。信息论中给出的信息处理定理 表明对所观测到的数据做任何方式的处理都会带来信息损失。因此在通信的系统 设计中，在允许的设备复杂度和处理时间下应使数据信息处理尽可能细致些。发 送端对信息的处理分解成三部分：信源编码、加密和信道编码。信源编码也称数 据压缩它是将信源输出信号有效地映射成符号序列的过程。任意给定的信源都 有一个表征其不确定性的称之为熵的量，它是无失真数据压缩的下限。信源编码 定理指出：在允许一定的失真情况下，存在最小数量的比特描述独立同分布的信 源输出。与信源编码的数据压缩相反，信道编码是人为的按照定规则增加冗余， 以克服信息传递过程中受到的噪声和干扰的影响，使恢复的信源信息错误概率尽 可能小。信道编码研究中，主要关心的是图中信道编、译码器两个单元，为了方 便研究，可以将信源、编码器和加密部分看成信源单元，信宿、信源译码器和解 密部分看成信宿单元，调制器、物理信道、干扰和解调器看作编码信道。这样， 数字通信系统模型就简化为图1 2 所示的模型。 图1 2 通信系统简化模型 任意给定的信道都存在称之为信道容量的信息传递速率上确界。它表示信道 传送信息的最大能力，信道编码研究的中心问题之一就是在给定的性能指标下构 造一个速率达到信道容量的码。即信道编码定理及其逆定理是信道编码理论中两 个最重要的定理l j j 。 信道编码定理：任意给定信道容量c ，对于任意小于c 的码率r 。存在一对 编、译码器，使译码错误概率p 随着编码长度的增加而变得任意小。 信道编码定理是存在性定理，它证明了在有扰信道中，只要传输速率小于信 道容量，就有可能通过信道编码的方法实现任意可靠的信息传输。信道编码逆定 理则指出如果信源的信息速率大于信道容量，不论采用何种编译码方法都不可能 使平均译码错误概率为零。 1 1 2 信道模型 设计信道编、译码方案之前，必须了解传输信息的信道特性。由于噪声和干 扰的存在，输入信道的事件总是以一定的概率转换成输出事件。信道的特性可以 用一个转移概率空间来描述。可以根据不同的方法对信道进行分类。根据信道的 第一章绪论 特性随时间的变化关系可将信道分为恒参信道和随参信道；按输出对输入的时f n j 依赖关系可将信道分为无记忆信道和有记忆信道；按信道的转移概率对输入端是 否有对称性可将信道分为对称信道和非对称信道。实际的信道情况往往很复杂， 0 弯 图1 3 ( a ) b s c 信道( b ) b e c 信道( c ) b i a w g n 信道( d ) 非相干r a y l e i g h 信逍 很难用封闭的数学表达式精确的描述它，但针对一些简单的信道，人们已经建立 了相应的信道模型。下面介绍信道容量的概念及编码设计中经常使用的几种信道 模型。 设时间离散无记忆平稳信道具有输入集和输出集l 其概率密度函数分别为 厶( x ) 、 ( ，) ( 若输入集为离散集，则概率密度函数厶( x ) 和 ( y ) 用概率p ( y ) 和 p ( x ) 代替) 信道特征决定了转移概率密度函数f ( y lx ) ，其中x x ，y y 。s h a n n o n 信道容量定义为( 1 1 ) 式所示的输入集和输出集的最大互信息。 c 2 然。( z ；y ) ( h ) 1 二元输入对称信道 二元输入对称信道( s b i c ) 是时间离散无记忆平稳信道，满足以下特性： ( 1 ) 输入集：x = + 1 ，一l ； ( 2 ) 输出集：y 亡r ； ( 3 ) 信道输出y 与信道输入x 之间满足无记忆性； ( 4 ) 转移概率满足对称条件：尸p lx = + 1 ) = p ( 一y f x = 一1 ) 转移概率函数简记为只( y ) ，对于离散集y ，只( y ) 是条件概率，对于连续集l ， 只( y ) 是条件概率密度。根据s b i c 信道的对称特点，信道特征可以用一个特定的 概率密度函数f ( y ) = 只，( y ) 表示，即 p ( y fx = + 1 ) = f ( y ) p ( y ix = 一1 ) = ( 一y ) 。 ( 1 2 ) ( 1 ) 二元对称信道( b s c ) ，占是信道转移概率，a ( x ) 是标准冲激函数： ( y ) = ( 1 一e ) a ( y 一1 ) + c s ( y + 1 ) 。 ( 1 3 ) ( 2 ) 二元删除信道( b e c ) ，占是信道转移概率，a ( x ) 是标准冲激函数： 4低密度校验码理论及其译码研究 f ( y ) = ( 1 5 ) 5 ( y 一1 ) + 8 8 ( y ) 。 f 3 ) 二元输入高斯( b i a w g n ) 信道： 厂( ，) ：ke x p ( 一( y 一1 ) 2 2 0 - 2 ) ，其中k = 1 2 舾2 “) 非相干瑞；和j ( r a y l e i g h ) 快衰落信道： m ) = k e x p ( - y a ) , ，菘 ( 1 - 4 ) ( 卜5 ) f 1 6 ) 其中常数a = e 。n 。，k = ( 1 + a ) ( a ( 2 + 爿) ) 。 s b i c 信道当输入是等概分布即p ( x = + 1 ) p ( x1 ) = 1 2 时，输入输出的互 信息最大。s b i c 的信道容量不超过1 比特信道使用。当信道为b s c 信道时，香 农容量限为c w ( f ) = i 一 ( s ) ，自( x ) = - x l 0 9 2 ( x ) 一( 1 一x ) l 0 9 2 ( 1 - x ) 。当信道为二元输 入a w g n 信道时，采用相干b p s k 调制，a w g n 噪声服从n ( 0 ，盯2 ) 分布，信道特 征参量是噪声方差口2 ，设信道编码器输出“ 0 ，1 ) ，经过映射x = 1 2 u ，调制器 输入x + 1 ，一1 ) ，输出信号设为x + 巨，一e ) 。信噪比通过( 卜7 ) 式调整噪声 方差进行匹配计算。 竺= -( 卜7 ) n o 2 r o - 该模型下信道容量为( 卜8 ) 式所示。 c 。= 一j 厶( x ) l o g ：厶( x ) a x 一丢l o g ：( 2 脚0 - 2 ) ，( 1 - s ) 其中输出概率密度厶( x ) = ( ( 1 ，口2 ) + ( 一1 ，盯2 ) ) 2 是信道特征参量仃的函数，即 一击h 等h 一譬) ) o 2 非二元输入对称信道 所有不满足二元对称信道条件的信道都称为非二元对称信道( n s b i c ) ，其中包 括多元输入信道、转移概率函数非对称信道、多用户信道和有记忆信道等等。对 于这样的信道，很难给出信道的最佳分布表达式及相应的信道容量。 1 2l d p c 码的发展历程与现状 l d p c ( l o w d e n s i t yp a r i t y - c h e c k ) 码是一类校验矩阵为稀疏矩阵的线性分组码， 它是g a l l a g e r 在1 9 6 2 年提出的 ”。g a l l a g e r 把l d p c 码校验矩阵对应到计算树上， 校验矩阵中每列对应于图的一个变量节点，每行对应于一个校验节点，校验矩阵 第一章绪论 中的非零元素所在的行和列对应的变量节点和校验节点之i 刨有边相连。g a l l a g e r 证 明l d p c 码的最小汉明距离随着码长的增加而线性增加，并且，在计算树上进行 后验概率迭代译码可获得随码字长度增加而降低的比特错误概率。虽然g a l l a g e r 证明了l d p c 码是具有渐近特性的好码，但受到当时计算能力的限制，l d p c 码曾 一度被认为是一种不实用码，很长的一段时间内被人们所忽视。 1 9 8 1 年，t a n n e r 在广泛研究图码的基础上提出规范图码的表示方法t a n n e r 图，把校验约束建立在局部码元集合上。他证明无环图上，和积算法和最小和算 法是最优的1 4 ”。w i b e r g 等人结合t u r b o 码和网格图的研究，将t a n n e r 图推广为含 有隐含状态变量的w i b e r g 图，网格图是w i b e r g 图的一个特例，这样使基于网格图 的译码算法都包含在消息传递算法当中。w i b e r g 证明最小和算法与和积算法实质 的一致性，无环图上，它们分别等效于最大似然译码和最大后验概率译码；在格 图上，最小和算法退化为v e i t e r b i 算法，和积算法退化为b c j r 算法【伸1 1 3 8 。在 w i b e r g 等人研究基础之上，f o m e y 等人提出标准图的概念，符号变量度数为l ， 状态变量度数为2 的w i b e r g 图称为标准广义状态实现。标准广义状态实现对应于 一个自然的标准图模型，其中，状态转移用顶点表示，状态变量用普通边表示， 符号变量用半边表示。他证明和积算法同样适用于广义状态实现的标准图模型； 同时，给定的任意系统，有环标准图比无环标准图的复杂度更低 2 0 】。 在t a n n e r 等人的研究基础上，k s c h i s c h a n g 等人在对比分析一系列图模型和相 应算法之后，建立了因子图( f a c t o r g r a p h ) 模型1 1 9 1 。他们发现所有的图模型本质上足 要表达一个全局函数到一组局部函数乘积的有效分解，而相关算法则是通过局部 函数的迭代计算给出全局函数的边界函数的过程。贝叶斯网络、马尔可夫随机域 ( m r f ) 、t a n n e r 图等图模型都包含在因子图模型中，p e m - 1 置信传播鲫、b c j r 酊向 后向算法1 26 j 以及l d p c 码的迭代大数判决算法都可归结为基于因子图的和积算 法。码的因子图表示提供了一个关于迭代译码的一般性框架【1 8 【”1 。 1 9 9 6 年，m a c k a y 和n e a l 随机构造的l d p c 码在码长很长时的性能超过了 t u l b o 码，激起了编码界进一步研究l d p c 码的浪潮。此后，d a v e y 和m a c k a y 从 减少t a n n e r 图上小环的理念出发，提出了基于g f ( q ) ，q 2 的l d p c 码，进一步提 高了l d p c 码的译码性能【1 4 j 【” 。在m a c k a y 和n e a l 重新发现l d p c 码具有优异性 能的同时，s p i l e l m m a 和s i p s e r 提出了基于二部扩展图的扩展码。他们证明了基于 随机构造的t a n n e r 图的l d p c 码以大概率为渐近好码。l u b y 等人则证明基于精心 构造的非规则t a n n e r 图的扩展码性能优于规则l d p c 码 3 4 1 1 3 5 1 3 6 1 1 3 训。 在研究过程中，人们发现l d p c 码迭代译码存在阈值现象，即在消息进化过程 中存在一个或多个不动点。r i c h a r d s o n 和u r b a n k e 建立了无环图上的密度进化理论 ( d e n s i t ye v o l u t i o n t h e o r y ) ，分析了不动点的存在性和收敛性，证明了含有大环随机 图的阈值逼近无环图的闽值的收敛性定理 3 6 1 。除了用于译码性能分析之外，密度 6 低密度校验码理论及其译码研究 进化理论也用来指导非规则码的度序列设计【4 8 】。随后，他们与c h u n g 给出了密度进 化的高斯逼近算法，简化了二元输入a w g n 信道下置信传播算法译码性能的分析。 密度进化的高斯逼近算法将信息密度无限维的迭代计算问题转化为计算高斯密度 平均数的一维问题【42 | 。这一近似能较快的计算阈值，利于对译码器工作原理的理 解。密度进化理论为l d p c 码长码设计提供了有效工具，在和积算法下获得较好的 译码性能。针对中短码长的l d p c 码，x i a o y uh u 等人提出了渐进边增长算法 ( p e g ) ，获得了性能优于随机构造的l d p c 码。此后，人们对控制图中环长和环分 布做了大量的工作1 5 o j p “。 目前，对于l d p c 码的研究除了上述的成果之外，l d p c 码线性编码m 儿3 3 儿”i i ”】、 以l d p c 码为分量码的多层编码调制系统【2 1 】【2 3 1 4 9 】以及可变速率l d p c 码【1 l 】等方面 都有了一些的研究。但是，关于l d p c 码，仍有许多尚待解决的问题。 ( 1 ) 对于l d p c 码本身，因子图中环以怎样的机制影响译码性能现在一般还局 限在直观的理解范围内，缺少定性和定量的分析： ( 2 ) 从信道模型方面，非二元对称性道下，l d p c 码结构优化设计和迭代译码 算法的改进以及相应的有效分析工具也是有待深入研究的课题； ( 3 ) 从应用方面出发，将l d p c 码应用到高速率传输环境下，要解决l d p c 码的 选择和译码算法优化问题；另步b l d p c 码与其它码级联、l d p c 码编码调制、 自适应编码等都是实际而又具有挑战性的问题。 1 3 本文研究内容及安排 作者结合国家自然基金项目( 6 0 2 7 2 0 5 7 ) 和国家自然基金委和香港科技局联 合资助项目( 6 0 1 3 11 6 0 7 4 2 ) ，在深刻理解l d p c 码基本编、译码原理基础之上， 提出了l d p c 码串行级联译码算法；利用理论分析和计算机仿真相结合的方法， 获得了一定的研究成果。全文共分为六章，其它章节安排如下： 第二章总结了l d p c 码的图模型理论及其因子图上的和积算法，为深入研究 基于因子图模型的l d p c 码译码算法提供了理论依据。 第三章首先说明因子图上的和积算法的两种信息传递策略，着重阐述l d p c 码的置信传播算法和作者设计的串行级联译码算法，在仿真分析的基础上得出了 串行级联译码算法收敛速度较快的结论。 第四章首先介绍了目前l d p c 码线性编码方面的成果及常用的几种l d p c 码 的构造方法，其次介绍了满足独立性假设和对称性条件下，l d p c 码性能分析和度 序列分布的工具密度进化理论。 第五章中介绍了带限信道下，以l d p c 码为分量码的多层编码调制系统的编 译码原理及其分量码的构造方法。 第六章对全文工作进行总结，并且提出了下步的研究工作。 第二章l d p c 码的图模型理论与和积算法 7 第二章l d p c 码的图模型理论与和积算法 本章详细叙述了l d p c 码的几种图模型表示方法，包括因子图，t a n n e r 图、 t r e l l is 图和w i b e r g t y p e 图。说明了基于不同因子图的和积算法分别等价于前 向后向算法、v i t e r b i 算法等。本章中，还给出了不同测度下和积算法的消息更 新规则，为l d p c 码的译码算法分析提供了理论基础。 2 1l d p c 码的图模型表示 l d p c 码是线性分组码，可以用生成矩阵和校验矩阵表示。l d p c 码之所以 称为低密度校验码是因为其校验矩阵中“l ”所占的比例很小。正是由于其校验矩 阵的稀疏特性，使得l d p c 码可以用图模型更为直观的表示出来。l d p c 码的图 模型有多种，包括因子图、t a n n e r 图、t r e l l i s 图和w i b e r g - - t y p e 图等。研究表明 因子图模型与其它图模型之间有着极其密切的关系，其它图模型可以看成因子图 模型对不同系统模型的表示。 2 2 1 因子图模型定义 因子图模型【1 9 】【2 0 1 是当前较为常用的表示l d p c 码的图模型，它归纳了目前 所有的图模型定义，提供了一个关于迭代译码的一般性框架。因子图模型实质上 是表达一个全局函数到一组局部函数乘积的有效分解。 定义：因子图是表达一个形如式( 2 1 ) 的函数因式分解结构的二部图。 g ( x l ，x ：，x 。) = y l 。f x ，) ( 2 _ 1 ) ，是离散下标集，j ，是扛一，矗) 的一个子集，( 巧) 是以子集j ，中元素为变量 的函数。因子图中，有对应于t 的变量节点和对应于工的因子节点，当且仅当 是厂t 的自变量时，变量节点墨和因子节点乃之间有边相连。 含有n 个变量的实值函数g ( x 1 ) 一，x 。) 有n 个边缘函数g i ( x , ) 。对任意口4 ， 爿。是鼍取值域，边缘函数璺( 口) 等于占( x 】一，x 。) 在所有( _ ，x 2 ，x ，= 口，x 。) 上的 和。 定义式( 2 2 ) 的运算为为s u m 运算，即第i 个边缘函数是g 对的s u m 运算。 g i ( ) 2 如 ，( x 1 ，x 2 茁，一，z 一) r 1 。、 = ，。 x z e a z 。 g ( z ，x ：z ，z 。) 、。 利用广义分布率4 1 1 和重复利用中间函数值，基于因子图模型可以有效计算边缘函 低密度校验码理论及其译码研究 数。下面是一个简单例子。设全局函数为( 2 3 ) 所示。 g ( x 1 ，x 2 ，x 3 ，x 4 ，x 5 ) = 厶( x 1 ) 厶( x 2 ) 五，( x 】，x 2 ，工3 ) - 厂( x 3 ，x 4 ) 厶( x 3 ，x 5 )( 2 - 3 ) 其中j = 爿、b ，c ，d ，毋，x a = x 。 ，瓦= 扛2 ，忍= x ，z 2 ，x 3 ，x d = 毛，五 ， x r = 屯，x ， ，其因子图模型如图2 1 所示。求上式中的边缘函数g ( 而) 则可得出 式( 2 4 ) 。 g l ( x 1 ) 2 兀( x - ) ( 。g ( x 2 ) ( 。 ( x l , x 2 , x 3 ) ( ，。f 1 ) ( x 3 , x 4 ) ) ( ，。f e ( x 3 ，x 5 ) ) ) ) ( 2 4 ) 采用s k i m 定义，则( 2 4 ) 可以重新写成( 2 5 ) 式。 g l ( x 1 ) = l ( x 1 ) + ( 巾厶( x ：( x i , x 2 , x 3 ) ( 啪 厶( x 3 ，x 4 ) ) ( 坩疋( 屯，z ，) ) ) ) ( 2 5 ) 图2 ，1 函数的因子图表示 边缘函数g ，瞒) 可以用如图2 2 ( a ) 所示的表示树清晰的表达出来。图2 1 可以 重新画成以x 为根节点的因子图见( 图2 2 ( b ) ) 。从因子图与表示树之i 刨的对应关系 可知：当因子图为无环图时，它不仅可以有效表示一个函数的因式分解，而且也 可以表示一个边缘函数的数学计算表达式。 图2 2f a ) ( 2 5 ) 式右端表达树图2 2 ( b ) 以一为根节点的网子剀 第二章l d p c 码的图模型理论与和积算法 9 2 1 2 因子图在不同系统模型上的实现 在信道编码理论中，常用的译码算法是最大后验概率译码。这种方法将给定 的信道观测值与码字的后验概率结合起来考虑，给出最佳译码。在译码研究过程 中，人们已经建立了各种系统模型如行为模型、后验概率模型来有效描述译码过 程。从模型观点出发，最大后验概率译码就是将一个码的行为模型 3 8 1 与后验概率 模型结合起来，进行最佳译码。下面介绍行为模型和后验概率模型的定义及其建 立在他们基础上的因子图模型，说明t a n n e r 图、t r e l l i s 图和w i b e r g t y p e 图模型 都可以看成是因子图在不同系统模型上的实现。 1 行为模型 行为模型中，定义一个如( 2 6 ) 式的布尔型函数 用。 p = 悟；嫣 ( 2 h s ) 定义n 为逻辑与运算，则kn 最 只 _ 陋】+ 只 h t 阮】。设x 。，x ：，l 是构 造空阳j s = a 1 a 2 a 。中的向量，x 。a ，。s 中的行为b 是s 的一个子集。行 为b 的特征函数定义为耽( x l ，x 2 ，b ) ：= ( x l ，x 2 ，矗) b ，显然，确定z 8 和确 定曰是等价的。对一个线性分组码来说，若每个变量都在有限符号集爿中取值， 则其构造空间为s = a ”，行为c c s 称为定义在a 上长度为n 的线性分组码，有 效的向量称为码字。向量是否是一个有效的码字可以通过系列奇偶校验来确定， 每组校验包含一个变量的子集，这样，对一个码字是否为一个线性分组码字的判 断就转变成一系列简单校验的与运算，特征函数变成一系列子特征函数的乘积， 每个子特征函数定义一个特定子集的行为。这样，任意一个r 行维校验矩阵h 定 义的线性分组码都可以用含有h 个变量节点和r 个因子节点的因子图表示。在因 子图模型提出之前，基于行为模型的t a n n e r 图模型和t r e l l i s 图模型在编码理论研 究中起着重要的作用。 2 t a n n e r 图模型 设c 是一个二元非规则l d p c 码，其校验矩阵如( 2 7 ) 所示。c 是由满足 h x 7 = 0 的二元3 维向量x = k ，x ：，z 。 构成的线性分组码。 ：1 1 10 l 0 1h00 0 7 = j1l1f 1 0110 0 l。，、 c 中的合法码字必需满足式( 2 _ 8 ) 等号右边的一系列校验关系。 段( x l ，x 2 ，x 6 ) = 眠，x 2 ，x 6 ) 】 、 = x 】o x 2o x 5 = o x 20 工30 x 6 = 0 x 】0 x 30 2 4 = 0 、 o 定义g f ( 2 ) 上加法运算，相应因子图如图2 , 3 所示，其中方框表示校验关系 l o 低密度校验码理论及其译码研究 圆圈表示码字比特，这样得到的因子图叫做t a n n e r 图。显而易见，校验矩阵为 h = 眠 的l d p c 码可以直接用t a n n e r 图表示，变量节点对应于校验矩阵中的列， 到2 3 二进制l d p c 码的t a n n e r 图 图2 5w i b e r g t y p e 图 因子节点( 校验节点) 对应于矩阵中的行，当且仅当h ，不为零时，对应的变量节 点和因子节点之间有边相连。 3 t r e l l i s 图模型 t r e l l i s 图是一个边做标记、有确定根节点和目标节点的有向图，从根节点到目 标节点的有向路径对应的标记序列是c 中的一个码字。t r e l l i s 图的一个特性是任 意给定的顶点到根节点都有一个固定的距离d ，称为该顶点的深度。深度为d 的 顶点的状态空间为s 。，可将t r e l l i s 图自然分解成”个单元，第f 个单元r 是由深 度为i 和，一1 的节点及相连的边组成的子图，z 中边的标记集合可以看作是可见节 点取值集合。实际上，每个z 单元定义了一个s 。，x js ，) 上局部行为。从整体上 看，t r e l l i s 图是定义在行为s o ，s 1 ，- 一，晶，x ，t ，矗上的图模型。当且仅当这些变量 满足所有t r e l l i s 单元约束时，一，x2 ，- x 。才是码字。最早，t r e l l i s 图用来描述一类 卷积码的编译码过程。同样，t r e l l i s 也可以用来描述线性分组码l d p c 码。 上例中的l d p c 码的t r e l l i s 图如图2 4 所示。 0 0 x = 0 邕警耋“：娶堡( 4 - 1 9 ) 1 ，x = 0 ，以概率1 2 取值 l ，x 0 第，次迭代，校验节点消息的更新表达式为( 4 2 0 ) 所示。 m 。“= r - i ( ，钏，( 删) ) ( 4 2 0 ) 式中函数r ( x ) 的加法运算定义为r ( x ) + r ( x ) = ( ( x ) + _ i x ) ，r d x ) + 巧( z ) ) ，其中 _ ( x ) 在g f ( 2 ) 上的模2 加，如( z ) 为普通意义上的加法。校验消息用r q ) 的形式之 后也可写成求和运算，这样校验节消息分布函数的计算也可以使用傅立叶变换使 卷积运算变为乘积运算。第f 次迭代所得的校验消息的概率分布为式( 4 2 1 ) 。 q = f 。( 矿( p 。1 ) )( 4 - 2 1 ) 9 r ( p n ) = ：2p ，r ( p ”) 。1 ( 4 2 2 ) r ( 只) 是定义在g f ( 2 ) o ，+ 叫上的y = ，( x ) 的概率分布函数，r - 1 是工的反变换， 即当y 服从g 。分布时，x = g ，的分布为r 。1 ( g 。) ，详细见 4 3 4 7 】 4 8 。 注意到消息概率密度的进化与信道特性和度分布相关。s b i c 信道模型可以 用一个特征参数来描述( 绪论中所述) ，密度进化理论中，初始信息是信道特征参 数的函数，初始信息直接影响着密度进化的收敛特性。当信道满足 4 8 1 中定义的单 凋性时，划值是使l i r a ，。或”= o 成立的最大的信道参数值。 g a l l a g e r 在规则l d p c 码的研究当中已经发现了阈值现象【3 】，给出了几种规则 第四章l d p c 码编码设计及密度进化理论 4 3 l d p c 码在b s c 信道下时的译码容量。给定设计码率r 使信道容量c = r 。的信 道特征参数上限断就是该码率时的s h a n n o n 限。译码容量a + 与信道特征参数具有 同样的量纲，它与上限郎之间的差异表征了码集合的最佳性能与s h a n n o n 限的距 离。如a w g n 信道，设n o = 2 盯：为单边噪声功率谱密度，其中o - ，是上限参数， 双极调制幅度为矗= - + 1 ，则比特信噪比s h a n n o n 限为毛0 = x ；2 e , o - c 。泽码器 容量口与口，的距离定义为。= 2 0 l o g ，。( 仃，o 。) d b 。表4 3 给出了几利- 规则l d p c 码的置信传播译码器容量及其与s h a n n o n 限的距离”4 j 一方面，若信道参数a 口，给定足够大的码长，当迭代次数趋于无穷大时， 任意( ，d 。d ，) 规则码均可以实现信息的可靠传输。另一方面，设定预期译码错误 概率，经过相应的迭代次数后，当码长n 趋于大时，任意( n ，d 。矿) 规则码的性能 按码长n 指数地依概率1 界定于该错误概率，这就是所谓的集中定理【4 7 l 。 表4 3a w g n 信道下译码器容量及其与s h a n n o n 限的距离 d 。d 。心o - c e b n 0 ( d b ) a s ( d b ) 36o 50 8 80 9 7 90 】8 409 2 6 480 50 ，8 30 9 7 90 1 8 41 4 3 4 51 00 50 7 90 9 7 90 1 8 418 6 3 35o 41 0 0 1 1 4 8o 2 3 0 l1 9 9 460 3 3 31 0 11 2 9 50 4 8 421 5 9 34o ，2 5l ，2 61 5 4 907 9 01 7 9 4 密度进化理论最重要的贡献在于分析了l d p c 码的阔值现象。r i c h a r d s o n 把上 述基于规则码的密度进化理论推广到非规则码的分析和设计。任意一个给定的度 序列分布对( 五，力，总存在一个相应的闽值g + m ，p ) ；优化的码设计就是基于一个 特定的s b i c 信道，搜索最佳的对序列分布对，使闽值最大化。g a l l a g e r 在他的工 作中已经指明了接近容量的必要条件，那就是最大校验度数d ，必须趋于无穷大。 对于其它s b i c 信道，容量接近或逼近度序列的搜索问题是相当复杂的。4 6 1 还推 广了l u b y 等基于b e c 信道下的稳定条件，给出了一般s b i c 信道的阈值上限，并 通过局部最佳化的方法，找出了一些好的度分布序列。 虽然，对b e c 信道以外的s b i c 信道，目前还没有一个明确的关于最佳度分 布序列的结论。但是，基于对称条件和独立性假设的密度进化，却明确地给出了 逼近容量的低密度编码设计的工具。4 2 c h u n g 等人在密度进化的理论基础之上， 提出了高斯逼近原理简化a w g n 信道上的l d p c 码的分析。使用高斯逼近原理以 后，多参数动态系统的密度进化模型转化成只有一个参数的高斯逼近模型。使用 高斯逼近原理，可以有效的简化非规则l d p c 码最佳度序列的搜索。 竺 堡童堕堡墅堡望堡墨基堡里堕至一 4 4 本章小节 l d p c 码作为一类线性分组码，可使用信息向量与生成矩阵相乘的形式来编 码，其编码复杂度与码长平方成正比。理论研究证明优化设计的l d p c 码长码的 性能可以超过t u r b o 码，但是当码长较大时，编码复杂度大，限制了l d p c 码实 际应用。降低l d p c 码的编码复杂度一直是该领域工作者的努力解决的问题之一。 本章主要介绍了类三角结构的l d p c 码的线性编码方法以及复杂度的分析。然后 叙述了规则和非规则l d p c 码的设计方法以及有效