（通信与信息系统专业论文）低密度校验码的性能分析和应用研究.pdf

摘要 信道编码技术可以带来编码增益，节省宝贵的功率资源，已成为现代数字通 信系统中必不可少的关键技术。l d p c 码采用低复杂度的迭代译码算法，且具有 逼近香农限的性能。由于l d p c 码具有诸多优点，它在信息可靠传输中的良好应 用前景已经引起学术界和i t 界的高度重视，成为当今信道编码领域最受瞩目的研 究热点之一，被列为4 g 关键技术。 作者在理解l d p c 码基本编译码理论的基础上深入研究了改进的和积译码算 法，并参考d v b s 2 标准，着重分析了b c h 码和l d p c 码级联系统的性能。本 文首先阐述了数字通信系统模型和香农定理，给出了常见的几种信道模型及容量 计算，分析了基于图模型低密度校验码的研究现状及其研究方向：基于t a n n e r 图 模型，详细介绍了l d p c 码的表示和构造；介绍了l d p c 码的和积译码算法和最 小和译码算法；简单分析了其迭代译码的性能。然后给出了两种改进的译码算法。 l d p c 码的译码可并行进行，但直接采用和积译码进行并行实现复杂度太大，为 此我们给 “了复杂度低、性能接近和积算法的并行泽码算法。在和积译码算法中， 其核心运算为超正切函数的运算，本文给出了其两种近似的简化方法，易于硬件 实现。l d p c 码的和积译码算法是最大后验概率译码算法，当单个节点传递信息 相互独立时( 即无环路情况下) 它是最优的，而在有环路时该算法并非最优。我 们首先针对有环路的l d p c 码提出了改进的译码算法，通过引入校正因子尽可能 消除环路对译码性能的影响，从而提高了译码性能。仿真验证了以上两种改进算 法的有效性。最后介绍了级联码的基本原理，b c h 码的定义和编译码方法。参考 d v b s 2 的标准提出了b c h 码和l d p c 码级联系统模型，采用理论分析和仿真相 结合的方法研究了级联系统的性能。仿真结果表明，级联码在达到低误码率时的 性能优于单纯的l d p c 码。 关键词：低密度校验码迭代译码b c h 码级联码 a b s t r a c t c h a n n e lc o d i n gi saf u n d a m e n t a lt e c h n i q u ei nm o d e md i g i t a lc o m m u n i c a t i o n s y s t e m s l o wd e n s i t yp a r i t yc h e c k ( l d p c ) c o d e sc a na p p r o a c ht h es h a n n o n sc a p a c i t y l i m i t ，w h e nd e c o d e dw i t ht h ei t e r a t i v ed e c o d i n ga l g o r i t h mw i t hl o wc o m p l e x i t y d u et o t h ea d v a n t a g e so fl d p cc o d e s ，t h e i ra p p l i c a t i o n si nr e l i a b l ec o m m u n i c a t i o n sh a v e r e c e i v e dg r e a ti n t e r e s t sa n dh a v eb e c o m eo n eo ft h em o s ta t t r a c t i v ef i e l d si nc h a n n e l c o d i n gc o m m u n i t y l d p cc o d e sa r er e g a r d e da sak e yt e c h n i q u ei nt h e4 g t h eo r g a n i z a t i o no ft h et h e s i si sa sf o l l o w s ：f i r s t l y , t h ed i g i t a lc o m m u n i c a t i o n s y s t e ma n dc h a n n e lc o d i n gt h e o r ya r ei n t r o d u c e da n dt h eb a c k g r o u n da n dt h ec u r r e n t s t u d i e so fl o wd e n s i t yp a n t yc h e c kc o d e sa r es u m m a r i z e d ；b a s e do nt a n n e rg r a p h ，t h e r e p r e s e n t a t i o na n dc o n s t r u c t i o no fl d p c c o d e sa r ea d d r e s s e d t h ep e r f o r m a n c eo ft h e i t e r a t i v ed e c o d i n ga l g o r i t h mi sa n a l y z e d s e c o n d l y ，t w oi m p r o v e dd e c o d i n ga l g o r i t h m s a r ep r o p o s e d c o n s i d e r i n gt h a tt h ep a r a l l e li m p l e m e n t a t i o no fs u m - p r o d u c ta l g o r i t h mi s o fh i g hc o m p l e x i t y , w ep r o p o s e dal o w - c o m p l e x i t yp a r a l l e ld e c o d i n ga l g o r i t h mw i t h p e r f o r m a n c ec l o s e dt os u m - p r o d u c ta l g o r i t h m t h ec o r eo p e r a t i o no ft h es p ai st h e h y p e r b o l i ct a n g e n tf u n c t i o n ，w h i c hi sk n o w nt ob ed i f f i c u l tt oi m p l e m e n ti nh a r d w a r e am o d i f i c a t i o nt ot h eh y p e r b o l i ct a n g e n tf u n c t i o ni sp r o p o s e dt oi m p r o v et h eb i te r r o r r a t e ( b e r ) p e r f o r m a n c eo fl d p cc o d e s f u r t h e r m o r e ，t w oa p p r o x i m a t i o n sb a s e do n p i e c e w i s el i n e a rf u n c t i o na n dc o a r s eq u a n t i z a t i o no ft h et a n hf u n c t i o ni su s e dt or e d u c e i t sc o m p u t a t i o n a lc o m p l e x i t y a sam a x i m u mp o s t e r i o r ip r o b a b i l i t yd e c o d i n gm e t h o d ， t h eo p t i m u mo fs u m - p r o d u c ta l g o r i t h mi sb a s e do nt h ei n d e p e n d e n c eo fi n f o r m a t i o n s e n tb e t w e e nn o d e s w i t ht h ee x i s t e n c eo fc y c l e si nt a n n e rg r a p h ，s u m - p r o d u c t a l g o r i t h mi sn o to p t i m u m f o rt h el d p cc o d e sw i t hc y c l e s ，ac o r r e c t i o nf a c t o r i s i n t r o d u c e dt oe l i m i n a t et h ea f f e c t i o no fc y c l e s s i m u l a t i o nr e s u l t sv e r i f yt h et w o i m p r o v e da l g o r i t h m s f i n a l l y , t h ep r i n c i p l eo fc o n c a t e n a t e dc o d e si sd i s c u s s e da n dt h e d e f i n i t i o no fb c hc o d ea n di t sc o d i n ga n dd e c o d i n ga l g o r i t h ma r ei n t r o d u c e d b a s e d o nd v b - s 2 t h ec o n c a t e n a t e ds y s t e mo fb c hc o d e sa n dl d p cc o d e si sp r e s e n t e d b y t h e o r e t i c a la n a l y s i sa n ds i m u l a t i o n ，t h ep e r f o r m a n c eo fc o n c a t e n a t e ds y s t e mi ss t u d i e d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h ec o n c a t e n a t e dc o d e si ss u p e r i o r t ot h eo n l yl d p cc o d e sw h e nt h eb e ri sl o w e r k e y w o r d ：l o wd e n s i t yp a r i t yc h e c k ( l d p ac o d e s i t e r a t i v ed e c o d i n gb c h c o d e sc o n c a t e n a t e dc o d e s 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别 加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写 过的研究成果；也不包含为获得西安电子科技大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确地说明并表示了谓 意。 本人签名：日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的 论文在解密后遵守此规定) 本人签名： 导师签名：日期：型互生坌乡 第一章绪论 第一章绪论 本章首先阐述了数字通信系统模型和香农( s h a n n o n ) 定理，并以此为基础引 入了信道编码的性能度量标准一香农限；其次给出了常见的几种信道模型及容量 计算；然后分析了基于图模型低密度校验码的研究现状及其研究方向；最后指出 了本文所做的主要研究工作及全文的内容安排。 1 1 数字通信模型与香农定理 现代社会是一个信息社会，它依赖于电子通信技术的信息传播来实现许多社 会功能。在2 0 世纪的上半叶，模拟通信是通信的主要技术手段，而到了2 0 世纪 下半叶则是数字通信大发展的年代。通信的基本目的在于将信息由信源高效且可 靠地传到信宿。由于信息在传输过程中，不可避免地受到各种噪声的干扰，2 使得 在信宿方接收到不同程度的错误信息。传统的观念认为：功率受限的情况下，为 了在有扰信道上实现无差错信息传输，唯一办法是使传输的速率为零。1 9 4 8 年， 贝尔实验室年轻科学家c l a u d ee s h a n n o n ( 香农) 发表了一篇题为通信的数学理 论的论文改变了人们看法，从而为现代通信和信息论的发展奠定了理论基础 【1 捌。 图1 - 1数字通信模型1 香农将通信系统分成信源、编码器、信道、译码器和信宿五个部分i “，如图 1 - 1 所示，其中编译码器是整个通信系统的核心部分。由于信源和信道的统计特 性不同，为使分析问题方便，编译码器又分别被分成了信源编码器、信道编码器 以及信源译码器和信道译码器四个部分。如果把信道再加以细化，整个通信系统 的详细模型可由图1 - 2 表示表示 ”。 由于噪声是影响通信可靠性的关键因素，一个自然的想法是构建可靠的信道 以减少噪声。但是这种想法在很多情况下是无法实现的，而且也没有必要。r e b l a h u t 曾指出“与其花费大量的金钱去建造一条好的通信信道不如采用信道编 码! ”。因此，从通信系统的经济性角度考虑信道编码也是必不可少的。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键，也是实现 通信系统经济性所必需的。但是，s h a n n o n 在1 1 l 中关于信道编码定理的证明是存在 性的，因而如何在实际系统中实现信道编码仍然是一个难题。 2 低密度校验码的性能分析和应用研究 编码信道 f 刊 图1 2 数字通信系统框 定理1 1 ( 信道编码定理) 1 8 】 任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值c ，它标志 着信道传输能力的上限，只要信息传输速率r s c ，就存在一种编码方式，当平 均码长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方 式也不可能保证错误概率任意小。 信道编码定理和信源编码定理、率失真理论一起构成了s h a n n o n 三大编码定 理。s h a n n o n 在证明上述信道编码定理时采用了三种技术： 1 ) 编码采用了随机编码思想； 2 1 让码长趋于无穷； 译码采用了最大似然译码。 1 ) 、2 ) 使得码本身具有卓越的纠错性能，而3 ) 中的最大似然译码使得码的纠 错性能得以充分发挥。但是，采用随机编码，使码长趋于无穷大并且采用最大似 然译码将会使系统的复杂度和延时变得太大，因而无法在实际中使用。在半个多 世纪的编码发展历程中，从h a m m i n g 码、b c h 码、r s 码、r m 码、卷积码、级 联码、代数几何码到逼近容量限的t u r b o 码和l d p c 码，数学家和信息理论专家 们为了达到s h a n n o n 容量限作了不懈的努力。在编码理论的最初阶段，人们一直 倾向于用代数方法来实现差错控制编码，有限域、数论和有限几何等数学理论成 了编码理论的主要工具。然而有趣的是，最终能够逼近s h a n n o n 容量限的t u r b o 码和l d p c 码都部分地引入了随机编码的思想：t u z b o 码的交织器和l d p c 码的 稀疏校验矩阵，并且它们的码长都较长，译码均采用了近似最大后验概率译码( 当 输入等概时，最大后验概率译码等价于最大似然译码) 的迭代译码算法。换句话 说，s h a n n o n 在证明信道编码定理的三种技术在最终逼近容量限的t u r b o 码和 l d p c 码中都有所体现。 第一章绪论 1 2 信道模型与信道容量 信道就是信息传输的媒质。如图1 2 所示，按照功能不同，信道可以分为调制 信道和编码信道。这里只考虑编码信道。 假定平稳无记忆信道的输入取自m 元符号集合，信道的输出取自q 元符号集 合。在数字通信的接收端，解调器对接收波形进行处理，将受扰波形转换成一个 标量或向量作为对传输数据的估计值，并将它送入判决器进行判决，判决输出q 元 符号。实际上，可以将判决过程看成是一种量化过程，而判决器输出所采用符号 集的大小对应为量化级数。当量化级数q 。m 时，称判决器作了一次硬判决；当 量化级数q ，m 时，我们称判决器作了一次软判决。判决器的输出将作为译码器 的输入。 1 2 1 几种常见的信道模型 1 ) 二元对称信道 考察一个二元输入加性噪声信道，令判决器作硬判决。如果信道噪声造 成的错误是统计独立的，平均错误概率为p ，那么可以用如下的转移概率来 描述这个信道的统计特性： 嚣：1 裟二0 二嚣二0 1 ：z x ：p 1 - p m - ， _ p ( y i j 一1 ) 一p ( 1 ，一io 一 、 我们称这种信道为二进制对称信道，其信道模型可以用图1 2 表示。 o 1 图1 3 二进制对称信道 o 1 2 ) 离散输入连续输出信道 假定信道编码器的输出符号取自x 一 x o ，而，一l 】，译码器输入为连续值 y = r ，我们称这类信道为离散输入连续输出信道，典型的有二元输入高斯白噪 声信道( b i a w g n ) 和二元拉普拉斯( l a p l a c e ) 信道1 9 1 。 二元输入高斯白噪声信道的输出可以用下式表示： y x + ( 1 2 ) 4 低密度校验码的性能分析和应用研究 其中，n 为加性高斯白噪声。其均值为零，方差为盯2 。给定一个输a x 一五， k = o ，1 ，g - 1 ，则y 是均值为溉，方差为盯2 的高斯变量： p ( y l x - 诹) 。而1 e x p 一( ) ，一甄) 2 仃2 ) ( 1 - 3 ) 如果信道是无记忆的，则满足 p ( ) ，y 2 ，y i x , - ，x - 。) 一垂p ( 卫i x , - 峨) ( 1 - 4 ) 1 2 2 信道容量 信道容量定义为信道输入与信道输出的互信息，它表征了信道可靠传输的最 大速率。最常见的信道容量计算式就是带宽、功率受限下的加性高斯白噪声 ( a w g n ) 信道容量计算式。设a w g n 信道带宽受限于卜，形】，噪声双边功率 谱密度为0 2 ，信号功率为p ，则 。眦g 【“南j ( b i t s 曲( 1 - 5 ) 这个容量仅在输入服从高斯分布的情况下可以达到。如果输入信号调制受限， 那么容量将会小于上面这个值。下面我们考察其他几种典型信道的容量计算。 1 ) 离散无记忆信道的信道容量 考虑一个离散无记忆信道，它的输入符号集为x 一 x o ，五，。) ，输出符 号集为y - y o ，y l ，y o - - ，并且转移概率为p i 工，) 。假定传输符号为而， 接收到符号为y t ，则事件x 一而和事件y - 弘的互信息是 l o g p ( y , z ，) p ( 弘) ，其中 p ( y j ) 一p ( y y 1 ) 一p ( 甄) p t y , i 五)( 1 6 ) 因此，输入集x 和输出集y 之间的平均互信息为【5 】 般y ) _ 宝芝肌，) p r y , i x i ) l 0 9 1 - 0 t - i帮 ( 1 7 ) r i v 。i 由上式可知，( z ；y ) 的值取决于输入符号集的概率分布 p o ，) ) 和信道的特 性，即转移概率 p “j _ ) ) 。令j ( x ；y ) 在所有输入分布 p ) ) 中取得最大值，则 这个最大值只与信道的特性 p ( 弘l _ ) ) 有关，它标志着信道的传输能力，称为信 道容t 萝( c a p a c i t y ) ，记为c 。这样我们就得到了离散无记忆信道的容量计算式： 第一章绪论 l 。黼。u ；j 荟q - iq 善- 1 p ( z j ) p ( x , ) e ( y , i x , ) l o g 等 。固 一缸荟善p 错字 ” 对转移概率为p 的二进制对称信道而言，当输入等概时，互信息取得最大值， 信道容量为 c 一1 + p l 0 9 2 p + ( 1 一p ) l 0 9 2 0 - t , ) 一l - h ( p ) ( 1 - 9 ) 其中，h ( p ) 是二元熵函数 2 ) 离散输入连续输出信道的信道容量 对于离散输入连续输出信道，记输入符号集为z - ，x l , - , x q 。 ，输出符 号集为y 一( 一m ，+ m ) 。在式( 1 8 ) 中，将对输出符号的求和换成积分，相应的概率 p ( 咒i ) 换成概率密度p ( y i 鼍) ，这样就得到了离散输入连续输出信道的容量计 算式【3 j c t 珊萎仁删郴甓净 m ， 按照式( 1 1 0 ) ，对二元输入高斯白噪声信道而言，信道容量为 “拉p ( y i 周蝇啦m ， + z p 仆周b g z 警一 其中e 为每符号能量。 若对二元输入高斯信道的输出作硬判决，则信道等效为一个b s c ，其转移概 率为 p f 古唧t 一学协 。f 击州一峄 一f 去c x p 一坠卑笋盥n 4 而o 2 ) ( 1 2 ) 一j ：两了导c x p 一三) 出( 令，一( y + 、= 甬丽) 一q ( 压云两) 其咧小f 去c x p ( 一等卜 6 低密度校验码的性能分析和应用研究 将式( 1 - 1 2 ) 的转移概率代入式( 1 - 9 ) 就可以计算得出硬判决时的信道容量。图 1 , 4 给出了b i a w g n 信道的软判决容量，硬判决容量与s n r = 磊，0 的关系。图1 5 给出了a w g n 信道的b p s k 容量限和调制不受限的s h a n n o n 容量限。 e 堋t y ms 冁_ 鲋删咖m d c 叫，籼日帅m 附w 朝曲州 i 一! 。意，：圳i 7 li 一一”。j ，7 。r r r ；，“ ， j；。y 一 - 一 p 十 一 ，算善 i； ； 一夕j l i ；，j i-一-b”k b o u n d l ； ：；： z ： l ； 1 ；! i ；! i j 刁：， ： 矿 | e 图1 4b i a w g n 信道的软判决与硬判决容量 图1 5b p s k 容量限与s h a n n o n 容量限 由图1 4 可知调制器采用软输出比硬输出有2 d b 左右的附加增益，这也就解 释了为什么软判决译码一般要优于硬判决译码。由图1 5 可以看出随着码率的增 加b p s k 容量限离s h a n n o n 容量限越来越远，而当码率较小时b p s k 容量限基本 与s h a n n o n 容量限致。因此b p s k 调制下，系统一般工作在中低噪比，同时码 率也较小( 小于等于1 2 ) 。若系统工作在高信噪比，则可以选择更高维的调制以提 高容量。 由图1 4 可得常见码率的s h a n n o n 容量限，例如1 2 码率时s h a n n o n 容量限 为o d b ，相应的b p s k 容量限约为0 2 d b ：1 3 码率时s h a n n o n 容量限约为m 5 5 d b ， 相应的b p s k 容量限约为一o 5 d b 。 1 2 3 误比特p b 与单位比特信噪比毛o 给定信道容量c ，由信道编码定理可知，只要传输码率尺低于c ，就可以获 得任意小的误比特率见。但是如果允许n 大于零，那么可获得更大的编码增益( 即 尾o 可以进一步减小) 。由信道编码逆定理f 5 l ， 以l o g ( m 一1 ) + 日( 见) 日。缈) 一二c ( 1 1 3 ) r f 其中，m 为信源字母表的大小，日。) 为信源熵，信源每秒产生一个字母， 信道容量为c ，每t 秒产生一个信道符号，则码率r 一。对b p s k 调制信号 有m 一2 ，h 。( u ) 一1 ，式( 1 1 3 ) 化为 c 乏r ( 1 一日( a ) ) ( 1 - 1 4 ) 驴鄞：扣e铲如 第一章绪论 7 上式也可以从另外一个角度得到。通常，为了考察特定码的性能，可以通过仿真 画出其误比特率和信噪比的关系曲线图，再与相同条件下的其它码作比较从而判 断码的性能。下面讨论给定码率条件下误比特率和信噪比的理论最佳曲线的作法。 接收端译码后误比特率为p 的情形等效于发送端对信源作误比特率为p 的编码 而接收端译码无误的情形。由率失真理论可知，对二元输出信源作误比特率为风 的编码所需的信源编码速率为1 一( 以) 。令信道编码速率为r ，则实际需要的 b i a w g n 信道容量为月( 1 一日( 磊) ) ，由信道编码定理即可得式( 1 - t 4 ) 。图1 5 为 b i a w g n 信道下码率为1 2 时，误比特率与单位比特信噪比的曲线图。 矿 1 矿 1 矿 矿 誉未k 臻； 。： 1 i e 删| ) 图1 6b i a w g n 信道卜| 误比特率和信噪比 的理论展佳曲线图( 码率= 1 2 ) 1 3 低密度校验码的历史和发展现状 1 3 1l d p c 码的提出 l d p c 码的概念及其迭代译码算法的提出要追溯到1 9 6 2 年【l o l 。g a l l a g e r 在他 的论文中定义了o ，七) ( ，k ，j , k ，的g a l l a g e r 码类而言，当码长趋于无穷时，图2 4 中 ti p 低密度校验码的性能分析和应用研究 的曲线逼近阶跃函数( 跃变点处的坐标值与码长的比值是一个固定值，记为靠) 。 因此，当码长抨足够长时，实际上g a l l a g e r 类中的所有码的最小距离至少为n 靠。 2 1 5l d p c 码的构造 l d p c 码是一种随机码，没有特定的生成多项式和校验多项式。描述该码的参 数为码长和稀疏校验矩阵中比特节点和校验节点的次数分布。构造方法是根据通 信系统中要求的码长和码率来确定校验矩阵的维数，然后通过线性编程工具p 2 l 等 获得性能优异的次数分布表达式。最后根据优异的次数分布填充非零元素的位置。 目前已有多项技术来具体构造校验矩阵，主要分为代数构造和随机构造两类。最 常用的随机构造方法为： 1 ) 根据给定的列和度分布，采用( 2 8 ) 式计算出校验矩阵的行； 定义一个m x n 全零矩阵，并根据矩阵的度分布采用( 2 4 ) 和( 2 - 5 ) 式计算n 列和 m 行中的重量分布： 3 ) 对矩阵中的第k 列( 1 s ks n ) ，从n 个列中不放回的随机抽出一个做为该列的重量， 设为t ；随后，从该列的m 行中随机选取厶行，并将对应位置的非零元素置为1 如 果这一置换使矩阵产生如图2 - 3 所示周期为4 的短环路，则删除这一列所有非零元素 并重新选取行进行非零元素置换，直到该列不产生周期为4 的短环路为止： 一1一】一 一1 1一 图2 3t a n n e r 图中环为4 的校验阵 钔列方向上的非零元素生成完成以后，需在m 行方向所对应的非零元素进行调 整，使得非零元素在行方向上也达到p ( x 1 所规定的分布。调整方法为在保持列位 置不变的条件下将非零元素从数量过多的行调整到数量过少的行，在这一过程中 同样要避免产生周期为4 的短环路： 通过以上步骤所生成的校验矩阵通常具有很好的随机性，保证了l d p c 码迭代 译码中两个子码之问的独立性，从而使得迭代译码具有优越的纠错性能。 另一种常用的随机构造方法是h u 采用“步步最优”的策略，构造出具有较大围 长的l d p c 码的有效方法渐进边增长( p r o g r e s s i v ee d g e g r o w t h ；p e g ) g 法 3 3 1 。 他通过在已有t a n n e r 图上依次添加边，使得每次添加边时都尽可能减少对己有 t a n n e r 图的围长的影响，来构造最终的t a n n e r 图。该算法不但适用于正j j l d p c 码 的构造，也适用于非正贝j j l d p c 码的构造。 第二章低密度校验的基本原理 1 9 2 2l d p c 码的译码算法 l d p c 码译码时，t a n n e r 图上各局部约束子集并行地进行计算，并在相邻子 集合间进行信息传递，经过多次迭代充分利用外信息，从而能够较准确地译码， 根据校验节点和变量节点消息收集方式、修正内容的区别，可将译码算法分为和 积译码算法和最小和译码算法。和积译码算法和最小和译码算法分别等效于最大 边界后验概率译码( a p p ) 和最大似然译码( m l ) ，在网格译码中，和积译码算法退 化为b c i r 前向，后向算法，最小和译码算法退化为v i t e r b i 译码算法。根据传递信 息内容，和积算法将演化为涉及人工智能和信号处理等不同领域的特定算法，如 贝叶斯网络的p e a l 置信传播算法、快速傅立叶变化算法等，在l d p c 译码中，和 积译码算法也被称为置信传播( b e l i e fp r o p a g a t i o n , b p1 译码算法。 下面，我们主要讨论二元l d p c 码的译码，信道模型为二元平稳无记忆a w g n 信道。假设采用b p s k 调制方式，噪声具有高斯密度( o ，2 ) 。 p r y l x 1 ) x 1 h 蟛彤 圈2 4l d p c 码的译码因子翻模型 考虑时日j 离散信道上的一个分组码c ，设传输码字为石一瓴，石：，“) ，接收 序列为y 一( ) ，y 2 - y ) 。根据全概率公式，信道输入和输出向量的联合概率 p ( x ，y ) 一p ( x ) p ( y i x ) ，其中e ( x ) 是发送码字x 的先验概率，p ( y i j ) 是发送码字x 时 接收y 的条件概率。对于时间离散的平稳无记忆信道，似然函数具有如下的乘积 形式 驯x ) - p ( y y ，y , vh ，x s ) 。兀附小，) ， 其中p ( y ，i x ，) 的值可以通过等式p ( ) ，i 以) 一7 ；e 电1 r 位一得到。根据全概率公 丑。 式可知，h 五y ) - p ( y ，j ) ，其中p ( y ，z ) - e ( y ) p ( x l y ) ，p ( x l y ) 表示已知接收信号y 时， 2 0 低密度校验码的性能分析和应用研究 发送码孚并的条件概率，因此可以得到 m 一器驯d 。 码字x 允许服从任何分布，如果假定所有码字等概选取，即先验概率p ) 为一个 常数，则给定信道观察y 时，z c 的后验概率为 e ( x i y ) 。a n p o 小) 其中是使。m l y ) 一1 的归一化因子，即后验概率正比于条件概率函数。 l d p c 码的译码可以通过t a n n e r 图进行描述，为了使叙述的方便，我们增加 了接收节点y t 饥，y 2 ，y _ ) 和条件状态节点e ( y i ，) - ( p o l i x 。) ，v ( y i h ) ) ，将 t a n n e r 图扩展为带接收节点的因子图模型( 标准因予图不带接收节点) ，如图2 4 所示。已知信道输出y 时，图2 4 中的条件状态节点e ( y ，k ) 只需进行一次计算， 将其作为信道先验信息储存起来。，? 是一个正比于p ( y 。i x ，) 的量，称为初始消息。 在这里，我们设m ( f ) 表示与变量节点x ，相邻的校验节点集合；a ) 表示与校验 节点z ；相邻的变量节点集合。在因子图模型中，q ：是变量节点工；向校验节点z ，发 送的变量消息，它表示变量节点名，根据，? 及从相邻校验节点 孔，k i , k m ( ，) 所得的信息，得出“x ，* 4 ”的可信度值：群是校验节点z ；向变量节点工，发送的校 验消息，它表示校验节点z 。根据其它变量节点 屯，k j , k ( f ) 目前的状态，得 到“工；t a 使z ；节点满足”的可信度值。娥和群是译码过程的中间消息，在每次 迭代译码中进行更新，当迭代结束后，变量节点通过对，? 和更新后的群值进行 判断来实现译码。 2 2 。1 基于概率侧度的和积译码算法 和积( s h m 跏d u d ) 算法( s p a ) 是l d p c 码最常用的译码算法，其“和( s u r n ) ”指 每个校验节点向相邻变量节点发送的消息，是对该校验节点的其它相邻变量节点 所发送消息的求和运算；“积( p r o d u c t ) ”指每个变量节点向相邻校验节点发送的消 息，是对该变量节点的其它相邻校验节点所发送消息的求积运算。 根据上面对l d p c 码的译码分析，我们可以将变量消息和校验消息分别定义 为q i a ，p ，t 4 i ， 4 ：k i , k 肘( j ) ) 和蟛一p ( z ti 善f 一4 ) 。在平稳无记忆 a w g n 信道，b p s k 调制下，传输信号a + 1 一1 是传输比特 o ，1 ) 的映射。二 元输入信道中，对码符号“e o ，q 和信道输入符号石 + 1 ，一l 的讨论是等价的， 因此我们在下文中不致混淆时，将在适当场合等效使用集合 o 1 和 + 1 ，一1 ) 。在 等概传输 o ，1 比特时，设，? - p ( j ，一口l y f ) - a i p ( y ，l 。f 一，口，是归一化因子，保 第二章低密度校验的基本原理 证1 + ，1 - 1 整个和积译码算法可分为三个步骤： 初始化：将初始消息厅送入q ；，彤初始化为1 。 高斯信道的似然函数为 m i x - a ) = 、，覆1 叶艺茅 、加：【幻：j 给定信道输出，对，- 1 ，n ，算得 ，一y ( 1 + e x p 一2 缈，s ： ) ，4 + 1 ，- 1 。 ( 2 - 1 2 ) 蟛a 和彤迭代更新信息： 蟛是校验节点毛向变量节点工j 发送的校验消息，其在迭代译码中的更新等式 为 彤- 弛l z ，- n ) 一盹，x l x j 一口) - 弛i _ 鸭x ) p ( x l x j 一口) 一盹i x ) , ( x i x j 一4 ) - 。：篆，盹i 呱，盹) _ ，：娶( 乙l x ) 职( 2 q 3 ) 其中o ) 表示与校验节点毛相邻的变量节点集合，o ) 、，表示该集合不包括变量 节点- q ；是变量节点x f 向校验节点z 。发送的变量消息，其在迭代译码中的更新等 式为 蟛- 尸h - a y j ，瓴：七m ( m ) p ( z ，_ 口，y j ， 气：后h o ) v ) p ( y i ，瓴：七肘( ) v ) p ( x j a l y ，) p ( z t ：七m ( ，) 、f ) ) ，j ，工- 4 ) p ( 协：k m ( ，) f ) y ，) e ( x j a l y j ) p ( z t ：七 f ( j ) 、f 壮，一) p ( z t ：k m ( j ) 、f ) p ( x ，l y e ) 。瓢e ( z t k ，叫) p ( 仁。：k 肘( ，) f ) - a 镕f ；n r ； 任1 4 ) 低密度校验码的性能分析和应用研究 其中m ( j ) 表示与变量节点膏，相邻的校验节点集合，m ( ，) f 表示该集合不包括校 验节点z t ；是归一化因子，它保证了。饼一1 。 译码尝试： 在步骤二完成群和弼的更新计算后，可以对码字z - 瓴，x 2 ，h ) 进行译码 尝试，每个码字比特译码值为 扣a 矾r g m a n xf ；毋( 2 - 1 5 )叫+ l n 矗盘f 、 设l d p c 码的校验矩阵为h m x n ，i 一 。，岛，式) 为译码所得的码字序列， 如果满足。量一0 ，译码成功，否则回到步骤二进行新一轮的信息更新计算。 2 2 2 最小和译码算法 和积译码算法通过考察满足局部约束子集合z 的所有有效组合，来保证每个 码字比特的最小错误概率；最小和译码算法则是在网格图中寻找一条最可靠的有 效路径来实现最小化码字错误概率的译码。在l d p c 码中，最小和算法可以看作 是退化的和积算法，其性能比和积算法略差。 根据最小和算法，我们可以定义蟛一一l o g ( p ( x ，一a 1 ) ，瓴：七，i , k m ( ，) ” 和群- 一l o g ( e ( z ，l x ，一4 ) ) 。同样，在平稳无记忆a w g n ，b p s k 调制下，等概 传输信号a + l 一1 ， + 1 ，1 是二元比特 o ，1 的映射，设初始消息 彤- l o g ( p ( x ，- 4 i y ，”- - 口j i o g ( e ( y jl 。，一4 ) ) ，口j 是归一化因子，则最小和译码算法 通过以下三个步骤实现。 初始化：将初始消息疗送入掰，r v 初始化为0 。 q ：和群迭代更新信息： 聪的信息更新公式为【1 2 ，1 9 珈3 4 l 群一m i n 卜l o g ( p ( z 。l z ) ) + 罗( 臻】 ( 2 1 6 ) ，”i 口) 、o q ：的信息更新公式为【2 1 m 9 9 ，1 1 川 蟛叫v 【+ 主予1 ( 2 彻 其中，是归一化因子，它保证了。铹一0 。 译码尝试： 当彤和饼信息更新完成，我们可以将码字工一瓴，z ：，h ) 进行译码尝试， 每个码字比特译码值为 第二章低密度校验的基本原理 i ，- a r g m i n i ，? + 罗r ；l ( 2 1 8 ) 雁l + 一h i e 研，) 设译码所得码字序列为膏- 。，童：，氛) ，对于l d p c 码的校验矩阵h m x n ，满足 口。x j 一0 则译码成功，否则回到步骤二进行新一轮的信息更新计算。 由于和积算法的译码性能好于最小和算法，而译码复杂度增加不大，因此 l d p c 码的译码大多数采用和积算法，在下面章节的讨论中，我们把和积译码算 法作为主要讨论对象。 2 3l d p c 译码的性能分析 对l d p c 码的性能进行理论分析比较困难，目前最主要的成果是r i c h a r d s o n 等人采用密度进化理论来讨论l d p c 码的渐进平均性能1 3 5 ，3 叩7 l 。和积算法和最小 和算法译码目的是通过消息迭代传递使得码字比特的消息朝正确的方向进化，从 而使译码收敛于正确的码字。在消息的迭代传递进化过程中，存在不动点的情况， 即对于l d p c 码有一个固定的译码阈值，当信嗓比大于固定阈值时，随着译码迭 代次数的增加和码长的增长，码字的平均错误率总能趋于零，如果信噪比小于固 定阈值，则无论采用多长的码长和多少次迭代译码，其平均错误率总是大于某一 常数。r i c h a r d s o n 等通过对无环t a n n e r 图上变量节点和校验节点发送信息的研究， 建立了密度进化理论，用于分析迭代译码过程中l d p c 译码器对发送消息概率密 度函数进化的影响。应用密度进化理论可以准确地计算出u ) p c 码的译码阈值， 从而可用于测度l d p c 码的渐进平均性能。r i c h a r d s o n 等同时提出的中心定理证 明了建立在满足一定条件的有环t a n n e r 图上l d p c 码，当码长趋于无穷大时，其 迭代译码算法的性能收敛于无环图上l d p c 码p q 。 l u b y 等人在t o m a d o 码的研究中发现，引入随机非规则图可以有效提高译码 性能 7 6 , 7 8 , 7 9 。r i c h a r d s o n 等应用密度进化理论对非规则l d p c 码的性能进行了分 析，发现基于随机非规则t a n n e r 图构造的l d p c 码能有效地改善译码阈值，进而 提高u ) p c 码的渐进平均性能。同时，密度进化理论可用于指导非规则l d p c 码 的最佳度序列分布搜索，最大化非规则u ) p c 码的译码阈值，优化l d p c 码的译 码性能。 c h u n g 等人在密度进化理论的基础上，提出了采用高斯逼近原理来简化 a w g n 信道上l d p c 码的译码分析【3 7 删。在a w g n 信道上，c h u n g 等用高斯密 度均值的进化来代替信息密度的进化，在不牺牲太多精度的情况下，实现了译码 阈值的计算由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高 斯逼近模型。应用高斯逼近原理，可以有效地简化u ) p c 译码分析和非规则u ) p c 码的最佳度序列的搜索 低密度校验码的性能分析和应用研究 2 4 本章小结 本章首先讨论了l d p c 码的三种编码方法及其对l d p c 码性能的影响，介绍 了l d p c 码的码重和构造方法；其次介绍了概率消息空间的和积译码算法和最小 和译码算法；最后，根据密度进化理论和高斯逼近原理对l d