（计算机软件与理论专业论文）删除信道下迭代译码的研究.pdf

摘要 低密度校验码是一种能逼近s h a n n o n 容量限的渐进好码，在长码时其性能甚 至超过了t u r b o 码，其译码采用具有线性时间复杂度的和积算法，复杂度大大低 于t u r b o 码。由于低密度校验码具有诸多优点，它在信息可靠传输中的良好应用 前景已经引起学术界和i t 业界的高度重视，成为当今信道编码领域最受瞩目的 研究热点之一。 作者在理解l d p c 码基本编译码理论的基础之上，研究了l d p c 码在二进制 删除信道下的译码。本文主要完成的工作有以下几个方面： 1 基于因子图模型，说明了l d p c 码的分类和特点。分析了l d p c 码消息 传递译码算法的原理，阐述了置信传播译码算法。 2 在分析停止集和环对l d p c 码迭代译码性能影响的基础之上，提出了一种 改进的译码算法，仿真实验表明改进的迭代译码算法能够有效的减少猜测次数并 提高了译码性能。 3 给出了利用密度进化方法确定删除信道下l d p c 码阈值的计算方法，仿 真实验表明所给的l d p c 码阈值的计算方法的正确性。 关键词：低密度校验码删除信道迭代译码停止集环 a b s t r a c t l o w - d e n s i t yp a r i t y c h e c k ( l d p c ) c o d e sa r eac l a s so fc a p a c i t ya p p r o a c h i n g e r r o r c o r r e c t i n gc o d e s b yu s i n gl o wc o m p l e x i t ys u m - p r o d u c ta l g o r i t h m ，l d p cc o d e s c a ng e tn e a rs h a n n o nl i m i td e c o d i n gp e r f o r m a n c e f o rl o n gc o d el e n g t h s ，l d p cc o d e s c a ne v e no u t p e r f o r mt u r b oc o d e s d u et ot h ea d v a n t a g e so fl d p cc o d e s ，t h e i r a 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 er 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 e o n eo fm o s ta t t r a c t i v ef i e l di nc h a n n e lc o d i n gc o m m u n i t y n o w , t h ea p p l i c a t i o no f l d p ch a sb e e np u to nt h ea g e n d a b a s e do na l l i n - d e p t hu n d e r s t a n d i n go fl d p cc o d e s b a s i ce n c o d i n ga n d d e c o d i n gt h e o r y , t h ed e c o d i n ga l g o r i t h mo fl d c po v e rt h eb i n a r ye r a s u r ec h a n n e l ( b e c ) i ss t u d i e d t h em a i nc o n t e n t sa n dr e s u l t sa r ea sf o l l o w s ： 1 b a s e do nf a c t o rg r a p hm o d e l ，t h ec l a s s i f i c a t i o na n df e a t u r e so fl d p cc o d e s a r ei l l u m i n a t e d t h ep r i n c i p l eo fm e s s a g e p a s s i n ga l g o r i t h mi sa n a l y z e d ，a n dt h e b e l i e fp r o p a g a t ea l g o r i t h mi se x p a t i a t e d 2 b a s e do nt h ea n a l y s i so ft h ei m p a c to fs t o p p i n gs e ta n dc i r c l eo nl d p cc o d e s i t e r a t i v ed e c o d i n gp e r f o r m a n c e ，a ni m p r o v e dd e c o d i n ga l g o r i t h mi sp r e s e n t e d t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h en e wa l g o r i t h mc o u l dd e c r e a s eg u e s st i m e se f f i c i e n t l y , t h u st h ed e c o d i n gp e r f o r m a n c ei sr a i s e d 3 t h ec a l c u l a t i o nm e t h o do fl d p cc o d e st h r e s h o l do v e re r a s u r ec h a n n e l 、 ，i t l l d e n s i t ye v o l u t i o nm e t h o di sp r e s e n t e d ，s i m u l a t i o nr e s u l t ss h o w st h a tt h i sc a l c u l a t i o n m e t h o do fi ，d p cc o d e st h r e s h o l di sc o r r e c t k e y w o r d s ：l o w - d e n s i t yp a r i t y - c h e c ko l d p c ) c o d e s i t e r a t i v ed e c o d i n g t h eb i n a r ye r a s u r ec h a n n e l ( b e c ) s t o p p i n gs e t c i r c l e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：盛因! 整 日期枷夕乡，口 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。( 保密的论文 在解密后遵循此规定) 本人签名：麴垒毛 导师签名： 日期枷罗；，9 日期乙。增、多、o 第一章绪论 第一章绪论 。本章中首先介绍数字通信系统的组成和信道编码定理。简单回顾5 0 多年来信 道编码技术的进步和发展，以及低密度校验码( l d p c ) 的提出、发展的历程及研 究现状，最后总结作者的主要工作，给出了全文的安排。 1 1 数字通讯系统 通信的目的在于消除传输信息的不确定性，通俗地讲就是实现信息传递。按 照传递信息形式的不同，通信系统可以分为模拟通信系统和数字通信系统。由于 数字通信具有模拟通信不可比拟的优点，如抗干扰能力强、便于差错控制、便于 使用现代数字信号处理、易于加密等等，因此数字通信更能适应于现代通信的要 求。这里仅讨论与数字通信有关的信道编码问题。 通信系统的质量评估有许多指标：有效性、可靠性、安全性、经济性、标准 性、可维护性等i l j 。其中有效性是指信息传输的速率问题，即单位时间能够传输 多少信息；而可靠性指的是信息传输的质量问题，即消息是否能够无误地从接收 端得到。由于噪声的存在，信息在信道中传输不可避免会发生错误。那么在有扰 信道中是否能实现通信的有效性和可靠性呢? 早期，人们普遍认为有效性与可靠 性是一对不可调和的矛盾，因而在有扰信道上实现可靠传输的唯一方法就是将传 输速率降为零【2 】。然而事实决非如此，1 9 4 8 年，3 2 岁的电子工程师、数学家c l a u d e s h a n n o n 在贝尔系统技术杂志上发表了题为“通信的数学理论 【3 】的文章，首次 否定了上述观点，为在有扰信道中实现可靠通信指明了方向信道编码。在这 篇论文中s h a n n o n 证明了数据压缩和传输的基本定律从而奠定了信息理论的基 石，s h a n n o n 也因此被称为“信息论之父。 s h a n n o n 在文 3 】中将通信系统分为五个部分：信源、编码器、信道、译码器 和信宿。其中编、译码器的实现是上述有效性与可靠性这对矛盾的集中体现。由 于信源和信道的统计特性不同，为了方便起见，编译码器可以进一步分割为信源 编译码器、信道编译码器和调制解调器，如图1 1 所示。信息理论已经证明， 在一般情况下这种分割并不会对系统性能产生影响【4 】。 一般的通信系统均可以用图1 1 来表示( 如果将存储介质看成信道的话，存 储系统也可以用上述模型表示，这时数字调制解调器分别对应于写入写出单 元) 。如图1 1 所示，发送端包含四个模块：信源、信源编码、信道编码和数字调 制器。信源编码就是用二进制( 或多进制) 序列来表示信源的输出的过程，它的 2 删除信道下迭代译码的研究 编码信遭 图1 1 数字通信系统模型 目的是除去信源的冗余以减少通信负担，因而也称为数据压缩。任何信源都有一 个被称为信源熵的量，它表征了信源的平均不确定程度。信源编码定理【4 j 指出信 源熵是数据压缩的下界；信道编码与信源编码正相反，它通过在信息序列中引入 冗余来实现通信的可靠性，任何信道都存在一个被称为信道容量的值，它表征了 信道的传输能力：数字调制就是将信息序列映射成适合信道传输的信号的过程。 对应地在接收端也有相应的四个模块用于实现相反的过程。 由于噪声是限制通信可靠性的关键因素，一个自然的想法是构建可靠的信道 以减少噪声。但是这种想法在很多情况下是无法实现的，而且也没有必要。 r e b l a h u t 曾指出“与其花费大量的金钱去建造一条好的通信信道不如采用信道 编码! ”。因此，从通信系统的经济性角度考虑信道编码也是必不可少的。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键，也是实现 通信系统经济性所必需的。但是，s h a n n o n 在【3 】中关于信道编码定理的证明是存 在性的，因而如何在实际系统中实现信道编码仍然是一个难题。 1 2 信道编码定理与纠错码的发展 通信的数学理论【3 】一文中定义了信息的概念，指出在不可靠信道传输最 大信息量的界。一个给定的信道，s h a n n o n 证明存在一个值，称之为信道容量， 记作c 。如果信息传输速率小于或任意接近该容量，可靠通信是可达的；但一旦 信息传输速率超过该容量，可靠通信将变为不可达。 定理1 1 有噪信道编码定理【5 】：设离散无记忆信道【x ，e ( yx ) ，卅，p ( yix ) 为 信道转移概率，信道容量为c 。当信息传输速率r ，x a = ，以= x 2 ) ，k = x l ，x 2 ，黾) ，= 黾，_ ) ， la l bl cl dj e 图2 4 函数的因子图表示 噩= 如，x 5 ，其因子图模型如图2 4 所示。求上式中的边缘函数g ( 而) 则可得出 式( 2 9 ) 。 g l ( 鼍 厶( 屯，矗) ) ( 如矗( 毛，屯) ) ) ) ( 2 - 9 ) 图2 5 ( a ) ( 2 1 0 ) 式右端表达树 图2 5 0 ) 以而为根节点的因子图 采用s u m 定义，则( 2 9 ) 可以重新写成( 2 1 0 ) 式。 g l ( x 1 ) = l ( x 1 ) ( 。厶( x 2 ) 厶( x 。，x ：，x ，) ( 巾，厶( x ，黾) ) ( - x 3 f g ( x 3 ，x 5 ) ) ) ) ( 2 。1 0 边缘函数g ，( ) 可以用如图2 5 ( a ) 所示的表示树清晰的表达出来。图2 4 可 以重新画成以x 。为根节点的因子图见( 图2 5 ( b ) ) 。从因子图与表示树之间的对应关 1 4删除信道下迭代译码的研究 系可知：当因子图为无环图时，它不仅可以有效表示一个函数的因式分解，而且 也可以表示一个边缘函数的数学计算表达式。 2 2 2 码结构表示 一个码长为、信息位数为k 的线性码由一个生成矩阵g h 定义，信息序列 分组而。通过g 被映射到码字x = s g 。线性码可以由一致校验矩阵日材。等效描 述，所有码字均满足h x r = 0 。校验矩阵的每一行表示一个校验约束z ，其中所 有非零元素对应的码元变量x ，构成一个校验集，由一个校验方程表示。校验矩阵 的每一列表示一个码元符号参与的校验约束。码元变量与校验方程之间的关系称 为结构【3 1 1 。下面，我们主要对二元l d p c 码进行讨论。 l d p c 码是一类线性码，由其校验矩阵具有的稀疏特点而命名，即日中的元 素几乎全部是0 ，只有极少量的非零元素。g a l l a g e r 最早定义的二元l d p c 码 ( ，d v ，d 。) 是码字长度为、设计码率为r 。= 1 一d ，d 。的线性码，其校验矩阵日 的每一列都包含正好d 。个“l ”、每一行都包含正好d 。个“l ”。由于满足这个结构条 件的校验矩阵并不唯一，所以具有参数( ，d 。，d c ) 的l d p c 码构成了一个码集合。 一般，日可以依上述结构条件随机生成，但所给码的性能差异较大。如果日 矩阵各行线性独立，则实际码率r = r 。；否则，实际码率r = ( 一m7 ) n r 。， 其中m 是日行空间的维数。 l0 10 o1 01 10 ol 10 o1 10 o l o l lo lo 01 10 o1 x l + x 3 + x 5 + x 72 0 而+ x 4 + x 6 + = 0 x 2 + x 3 + x 6 + x 720 x 2 + x 4 + x 5 + 黾2 0 ( a ) 校验矩阵和方程组 c o ) 因子图表示 图2 6 ( 8 ，2 ，4 ) l d p c 码的校验系统及因子图表示 设一个( ，d v ，d 。) 码c 具有校验矩阵日= ( ) 肘。，其因子图模型可以表示为 一个二部图。码字向量x = ( x l ，x 2 ，x ) 表示为一组变量节点 x j ：歹= 1 ， ， 校验约束表示为一组校验节点 毛：扛l ，m 。仅当= 1 时，节点_ 和乙之间由 第二章低密度校验码的编译码原理 一条边连接，节点x ，和z ，互称相邻节点，其间连接边称为这两个节点的相邻边。 因子图上每个变量节点具有d ，条入射边，即度数为d v ；每个校验节点具有d 。条入 射边，即度数为也，共有e = n d v = m d c 条边。令集合m ( ，) = f ：= 1 表示变 量x ，的受限范围；令( f ) = ：h 玎= 1 ) 表示校验z ，的约束范围。 图2 6 ( a ) 是一个( 8 ，2 ，4 ) 短码的校验矩阵及校验方程组，图2 6 是相应的因子 图表示。该图表示了校验约束结构码的全局函数f ( x l ，x s ) ，也称码特征函数。 每个校验节点z 。表示一个局部约束函数z ( 扛，：，( f ) ) ) 。全局函数因式分解为 厂( x l ，x 8 ) = 石( x l ，x 3 ，x 5 ，x 7 ) ( x l ，x 4x 6 ，x 8 ) 六( x 2 ，黾，x 7 ) 厶( x 2 ，x 4 ，x 5 ，x 8 ) ( 2 - 1 1 ) 定义指示函数为一个把布尔逻辑命题p 映射到g f ( 2 ) 上的二值函数【2 5 】： 唧= ；三恶+ 式( 2 1 1 ) 中的各个函数均为指示函数，其中全局函数的逻辑命题为“x 是一个 码字 ，每个局部函数的逻辑命题为图2 6 ( a ) 中的校验方程。式( 2 1 1 ) 又写作为 【x c 】= 【x l + 屯+ 黾+ 而= o 】i x , + & + 珞+ 黾= 0 】 【吻+ x 3 + + x 7 = 0 】 x 2 + x 4 + x 5 + = 0 】。1 ( 2 - 1 3 ) 图2 6 ( b ) 的因子图实际上是一个有环t a n n e r 图。注意到矩阵的第三列和第七 列中，1 出现在第一行和第三行两个两行位置上，对应在因子图中，依照无向边 连接关系，存在一个长度为4 的循环路径( x ，z 。) 、( z 1x ，) 、( x ，z ，) 、( z 3 而) 。 类似地，图中还存在另一个长度为4 的循环路径( x 。，z ：) 、( z ：，x s ) 、( x 。，z 。) 、 ( z 。，x 。) 。采用迭代置信传播算法译码时，这种短环路将极大地影响码性能。码的 最小汉明( h a i i m l i n g ) 距离及距离谱直接取决于环路的分布情况。因此构造码时， 应该尽量消除短环路【6 3 2 】。 2 3l d p c 码消息传递译码 消息传递( m e s s a g ep a s s i n g ) 算法p 5 j 是一种工作在图论基础上的译码算法，由 于在算法的运行过程中，可靠性信息在二部图的变量节点和校验节点之间来回的 传送，因此称为消息传递算法。该算法的前提假设是码对应的二部图中没有环， 如果图中有环的存在，算法的性能会有一定程度的损失。 不失一般性，假设信道的输出符号集即译码器的输入符号集为o ，译码过程 中发送消息的符号集为m ，通常0 c m 。消息传递算法的操作过程如下：在零时 刻，所有的变量节点1 ，。( f i ，z i ，聆为码长) 都接收到一个相关的信道输出消息， 即一取值范围在o 内的随机变量。在译码过程中，可靠度消息沿着图中的边在节 1 6删除信道下迭代译码的研究 点之间相互传递。首先，每个变量节点都给所有与之相邻的校验节点发送一个取 值范围在符号集m 内的消息。典型的情形是，零时刻，变量节点v ，将作为它的 第一个消息发送( 这要求oc m ) 。每一个校验节点c ，处理它接收到的消息，并 回送取值范围在m 内的相关消息给所有与之相邻的变量节点1 ，。然后每一个变 量节点v ，对刚接收到来的消息和信道输出消息进行处理，计算出新的可靠度消 息，然后将之发送给相关的校验节点。对算法的每一次迭代过程， ，n ，都包 括一个消息处理的循环：校验节点处理和发送消息，接着是变量节点处理和发送 消息。 1 一。 需要指出的是消息传递算法中重要的一点是沿某条边发送的消息的映射函数 的自变量不包含来自该边的消息，也就是某节点甜沿某边e 发送的消息应该与上 次材沿边e 接收的消息无关，这保证了发送消息与接收节点的消息相互独立，仅 仅发送接收节点的边信息。这是一个优秀的消息传递算法所必须具有的重要特性。 这个特性保证了l d p c 码的二部图中没有环的情况下，得到更好的概率保证，达 到好的性能。消息传递算法的意义可以理解为：每一个消息都表示对某一特定码 元的估计，它包括了对码元比特的估计和以及该估计的可靠度。 消息传递算法存在着一种特殊的译码门限现象。当信道的信噪比低于该门限 时，译码后的误码率能够任意的趋于0 ，而当信噪比高于门限时，译码后的误码 率将不能趋于0 。门限的大小由编码的度数分布对、消息符号集的大小、映射函 数的形式等因素确定。 由于消息传递算法工作在简单的二部图模型上，同时算法运行过程中发送的 消息都与目标节点的消息无关，对它的数学分析相对简单。在二部图中没有环的 假设条件下，算法的数学分析已经完整的给出。但是在图中有环的情况下，由于 算法经过一定度数的迭代后，环中节点接收到的信息与节点的信道输出消息不再 是相互独立的，形成了正反馈，从而导致译码算法性能的下降。 2 3 1 消息传递机制 消息的传递是在因子图上进行，消息在变量节点和校验节点之间沿着边相互 间进行传递。在进行第f 次迭代过程中；从变量节点向校验节点传递的消息依赖于 第i 一1 次迭代过程中校验节点集向该变量节点传递的消息，其中校验节点集由不包 括当前校验节点并且和该变量节点相连的其它节点组成，校验节点向变量节点传 递消息的情况类似。开始的时候：对每个变量节点赋一个先验概率消息p p r i o r ( x ) ， 从变量节点x 到校验节点珀勺消息用j l l 。，( 考) 表示，考表示变量节点的各种取值，通常 把取值限制在g f ( 2 ) 域上；即变量节点的取值为0 或者1 。在消息传递过程中 - l x - - ，f ( 考) 依赖于从校验节点到该变量节点的消息。即有 第二章低密度校验码的编译码原理1 7 j l l h ，g ) = p p r i o r ( x = 考) 兀 t f ，- + x g ) ( 2 1 4 ) 厂6 册“j 、沙 其中p p r i o r ( x = ) 是x = 毒的先验概率，册g ) 表示变量节点x 的邻近校验节点，集 合沙 表示不包括当前的校验节点从校验节点f 到变量节点x 的消息按照下面的 描述： ， j l i ，呻，q ) = 厂心，考。，髻。) n p 而呻，g ) ( 2 一1 5 ) 峨， 2 ，磊j 函数厂g ，考l ，一，考。) 表示码字满足的校验条件，消息就在这两种节点之间不断相互 传递，直到满足约束条件，即宣告结束。另方面，从变量节点的角度来讲，将 该变量节点的先验概率消息和从校验节点获得的外部消息相乘，即可获得该变量 节点的后验概率，由该后验概率即可获得变量节点所表示的码字比特消息，即有 下面的公式 尸础栅g = 考) = 印肿g = 考) 兀f - , x g ) ( 2 1 6 ) f e n b ( x ) 在这里，常数c 是归一化因子，也就是p 删胁心) = 1 。 善 上面关于消息传递机制可以用下面的原理图来解释：图中三表示从左边输入给变量 节点x 的所有消息，尺表示从右边输入给变量节点x 的所有消息，两者统称为变量 节点的外部消息，c 表示变量节点的先验概率。在消息传递过程中，变量节点x 传 递到校验节点厂的消息正比于x 和三的联合概率。另一方，在给定x 的情况下校验 节点厂传递给变量节点x 的消息和r 有关。上面的消息传递可以用下面 图2 7 消恩传递概率解释图 的数学公式来表示。即有： j l l h ，g ) = c p r g = 考，厶c ) ( 2 1 7 ) j l l ，。心) = c p r 俅ix = 考) ( 2 1 8 ) 图2 7 中的消息流动秩序如图2 8 所示。首先和变量节点相邻的校验节点( 不包括当 前校验节点) 向变量节点传递消息，与此同时和当前校验节点相邻的变量节点也 1 8 删除信道下迭代译码的研究 向当前的校验节点发送消息，这个过程是同时的，在图中用表示。当这个消息 传递完成后，当前的校验节点和变量节点互相传递更新后的消息，这个过程用 表示，经过这个阶段后，校验节点和变量节点的消息获得了更新。更新后的校验 节点和变量节点分别将当前的消息传递过和其相邻的变量( 校验) 节点，这样就完成 消息交换的第一次迭代过程。依此反复直到满足迭代停止条件。 图2 8 消息传递时序不恿图 在图2 7 中变量节点传递到校验节点的概率消息由下式给出： p r ( x ，l ，c ) = p r ( x ，c ) p r ( lix ，c ) = p r ( x ，c ) p r ( l i ，l 2 ，l six ) 一 3 = p r ( x ，c ) i - ip r ( l ，ix ) i = 1 为了和前面的公式( 2 - 1 4 ) 相对应，( 2 1 9 ) 式改写成 p x - f g ) = 尸肭g = 考) 1 7j l l 正_ ，g ) 让r ? 表示尺l ，r 2 和r 3 。# 表示x l ，x 2 和x 3 。 这样， ( 2 1 9 ) ( 2 - 2 0 ) p r ( r i ，小1 ，) ：f f l p r ( r ；ix , ) p r ( xx ? ) ( 2 - 2 1 ) l = l 因为r 表示从右边输入给变量节点x 的所有消息，包括尺。，r ：，r ，以及x 。，x ：，x ，根 据马尔可夫属性，则 p r ( r ，c ，x ) = e p r ( r ? ，c ig ) v r ) 彳 = 乏【卉p r 伍小，) p r ( x 川p r ( x ，c lx ? ) 爿f = l 第二章低密度校验码的编译码原理1 9 ：f ，f 1 p r q ，二，) p r g ，cix l s ) ( 2 2 2 ) 将最右边一项进行化简有 、 p r g ，clx 1 3 ) - - p r ( clx ) p r ( x x l ) = 印脚g 沙g ，x l ，x 2 ，x ，)( 2 2 3 ) 其中f ( x ，x ，x ：，黾) 描述输入的变量节点集合是否满足约束条件。比如在这里采用的 是偶校验约束，则有 几, x i , x 2 , x 3 ) ：仨姜嚣叭2 。铲。 这样，从校验节影发送到变量节点x 的消息可以用下面的公式描述： p r ( rix ) ：c 厂g ，x ，丫血p r 取) ( 2 - 2 5 ) 0f = l 为了和( 2 1 5 ) 式相对应，公式( 2 2 5 ) 口- i 以写成： - - , x 心) = s ( x ，而，x ：，屯) n p 而，g ，) ( 2 - 2 6 ) 在这里我们忽略了常数c ，因为在译码中，主要是根据消息的相对值来进行计算的， 而不是根据消息的绝对值来进行译码的，即考虑的是砉竺矧。g 黼上n n 公式计算出变量节点传递给校验节点的消息以及校验节点传递到变量节点的消 息，展0 - - i 计算出变量节点x 等于喜的后验概率。另一方面由于变量节点的后验消息 由它本身的先验消息、从左边输入给节点的汇集消息三和从右边输入给节点的汇集 消息r 等确定，因此该变量节点的后验概率消息的计算公式如下： p 舢7 g = 考) = c p r ( x = 专，厶r ，c ) = c p r ( x = 毒，三，c ) p r ( rix = 考，厶c ) = c p r ( x = 考，厶c ) p r ( rix = 孝) = c ，g 址，斗，化) ( 2 - 2 7 ) 其中常数一是归一化系数，即有。p 删晰g = 考) = l 。 删除信道下迭代译码的研究 2 3 2 置信度传播译码 当消息传递算法中的信道输出符号集合译码过程中发送消息的符号集相同， 都为实数集足，即采用连续性的消息传递时，适当地选择消息映射函数，算法将 等价于著名的置信度传播( b e l i e f p r o p a g a t i o n ) 算法，简称b p 算法【3 6 1 ，也即和积算 法。b p 算法如下： 若编码的校验矩阵为日，将参与第m 个校验的变量节点集合记为 锄) 兰伽：日册= 1 ) 。类似的，将第玎个变量节点参与的校验的集合记为 m g ) 兰m ：h m = l 。) 刀为如) 与第拧个比特的差集。算法中有两个交替执 行的部分，与校验矩阵中非零元相关的数值g 。和在算法的迭代中逐次更新。 数值g 三。是指在己知除第m 个校验节点外其它所有校验节点的消息时，x 的第n 个 变量节点取值为x 的概率( x 为发送的码字) 。数值是指在己知x 的第n 变量节 点值为x ，其它变量节点满足概率分布扫。：胛似) 丹 时第m 个校验节点得到 满足的概率。如果矩阵h 所对应的二部图没有环，在经过一定次数的迭代后，该 算法将给出每一变量节点取值的精确后验概率。 初始化：对每一个满足日。= l 的0 ，m ) ，变量节点的g 二和9 分别被初始化 为片和爿。这里爿= 1 【1 + e x p 【_ 2 毗( r 2 ) ) ，片= i - 爿，虬是时刻胛信道的输出。 第一步：这一步对每一校验节点m 及相应的每一个，z n ( m ) 计算两个概率测 度：第一个，礁其它的变量节点k ：胛7 刀) 服从相互独立的概率分布k ：。，g 二 ， 时，校验节点m 得到满足的概率，计算如下： 厂，、1 兹= ，h ，= o lx = oi 兀g 翥，l( 2 - 2 8 ) 矗，l e ( m ) ，h l l 疗e ( m ) ，月开e ( 肘) ，h i 第二个，艺。，当x n = 1 时，校验节点m 得到满足的概率，计算如下： r，、 如2 x n t , n 藐一尸l 蒹力。1 i x 叫l 骣黪，j p 2 9 ) 这里最外层的求和对集合 r 锄) 、刀中变量节点所有可能的取值集合进行，该集合 大小为2 1 ( ”州，i nm 】为集合锄) 刀中元素的个数。概率内的求和为模2 和。g ，为消息比特玎取值序列是否满足概率式中的和式。 第二步：这一步利用计算所得值吃和，更新概率值g 和g 二。对于每一 个n 计算： g ：= 口。p ：兀以 m e m ( n ) m g k = 口。p ：兀如 m e m ( n ) r n ( 2 - 3 0 ) ( 2 3 1 ) 第二章低密度校验码的编译码原理 2 1 其中a 。为归一化系数使得 q o m n + g 二= 1 。p ：和p ：分别为变量节点刀取值为0 和l 的后验概率。 兀兹为变量节点取值为0 时所有子校验节点得到满足的概率， t n f _ m ( n ) m 1 - i 以_ 为变量节点取值为1 时所有子校验节点得到满足的概率。 肼e f ( 打) 、卅 在任何一次迭代后，可依照下两式计算变量节点甩取值为0 和1 的伪后验概 率q o t f l l g ： ， g ：= p ：兀吃 肘e m 伽) g ：= 或兀如 m m 伽) ( 2 3 2 ) ( 2 3 3 ) 一然后对这些伪后验概率进行硬判决生成试验译码结果圣，用来判断译码算法 能否结束。进行试验译码。 若试验译码成功，则译码结束，否则，若迭代次数少于某预先设定的最大值， 则重复上述算法步骤。若迭代次数带到预先设定的最大值译码过程仍未结束，则 宣告译码失败。 试验译码：利用第二步中计算所得靠，可生成试验译码结果圣。译码程序在 g ： o 5 时令毛= 1 ，反之令曼。= 0 ，由此生成试验译码结果，并检验方程 硪= o m o d 2 是否成立。当该式成立时，译码过程结束，将曼作为译码结果输出； 而当迭代次数达到某一预先定义的最大迭代次数时仍未得到正确的译码，算法结 束，并声称译码失败。当译码失败时，上述试验译码结果曼可用来作为其它译码 算法有用的译码起点。 上面的译码算法中第一步计算可以适当简化。定义国删= g ：一g 二，且对任 意m ，拧计算 +， = n 却。， ( 2 - 3 4 ) 那么可以二元域上的傅立叶变换或归纳法得到艺和厂二。的计算式 嗉：华( 2 - 3 5 ) 经过上式简化后，的计算量大大减少。 如果将b p 算法转换到对数域上进行，可以极大的减少乘法运算的次数。令墨 为第f 个输入比特的信道输出，而m ，是如下的对数似然比： 1 0 9 剿乩g 矧 ( 2 - 3 6 ) 对数域上的b p 算法如下，迭代的执行如下两个步骤： 删除信道下迭代译码的研究 步骤1 ：对二部图中所有的边e = ( 哆，c ，) 并行的进行如下操作：如果是第一次 执行，令岛= m 。，否则 g l ，= m f + ( 2 - 3 7 ) k m o ) j 式中m ，为与变量节点哆相邻的校验节点下标集。然后变量节点q 将岛发送给校 验节点c j 。 步骤2 ：对二部图中所有的边g = h ，c ，) 并行的进行如下操作：校验节点c ，将 如下的消息厅，发送给变量节点q = 叫e n i d ( j ) 篙lm ) _ l 。g 等 b p 算法每次迭代大约需要m ，p ，+ 吐) 次浮点乘运算，每译出1 比特大约需要 t d ，瓴+ 吐) r ( t 为平均迭代次数) 次浮点乘运算，与码长无关，总的乘法次数 约为t n d ，p ，+ d 。) 。可以看到b p 算法的复杂度为码长的线性函数。并且b p 算法 是一种并行算法，在硬件中的并行实现能够极大的提高译码速度。b p 算法的迭代 过程中，如果试验译码得到成功，译码过程立即结束而不是进行固定次数的迭代， 有效地减少了算法的迭代次数。如果算法跑完预先限定的最大迭代次数后仍未找 到有效的译码结果，译码器将报错，这时的译码错误为可检测的，若算法找到 一个与x 不相等的宝满足方程臌= o m o d 2 时将产生可检测的的错误。不可检 测错误的出现概率基本可忽略不计。 2 4 本章小结 本章介绍了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 码的有效译码方法，充分利用了l d p c 码校验矩阵的稀疏性， 降低了译码复杂度，并且由于信息的迭代传递，带来了较佳的性能。 第三章删除信道下l d p c 码中迭代译码算法及改进 第三章删除信道下l d p c 码中迭代译码算法及改进 本章系统地分析了删除信道上的迭代译码算法，介绍了停止集的性质，分析 了停止集的成因。根据停止集的特点提出了改进的迭代译码算法，该算法有效地 提高了译码性能。得出的结果反映了停止集的一些特点。 删除信道 二进制删除信道( b i n qe r a s u r ec h a n n e l ，简称b e c ) ，输入集为 1 ，o ) 、输出集 为 1 ，e ，o ) 且参数为p 的二元删除信道如图3 1 所示，输出符号e 称为删除( 错误) ， p 称为删除概率，这类信道的信道容量为1 一p 。以后我们讨论的在删除信道下的 l d p c 码均指这类信道下。 o 图3 1 二迸制删除信道 0 e 在l 般的通信系统中，前向纠错码纠正的错误所在的位置事先通常是不知道 的，而当系统中的信道为删除信道时，错误的数据被遗弃，丢失的数据在数据流 中的位置是知道的，这样的错误纠正起来相对容易些。 删除信道在实际通信系统中是很常见的，如在互联网中进行的多点传输 ( m u l t i c a s t ) 和广播传输( b r o a d c a s t ) 【3 8 1 1 3 9 1 1 4 0 1 。当网络公司要通过互联网对众多 用户有效地传送大容量的数据( 如大型软件、图像等) ，一般都会使用多点传输或 广播传输。 一 在通信系统中前向纠错码纠正的误码所在的错误位置事先一般不知道，这里 假设接收者知道数据包流中每个包的位置，即所采用的信道模型是删除信道【3 7 】，此 信道中每个编码包丢失的概率均为p ，且在传输中编码包的丢失是相互独立的，这 样纠删码比纠错码处理起来容易些。互联网也许是这样的信道中最为引人关注的 典型例子。 删除信道下迭代译码的研究 3 2 迭代译码算法 3 2 1b e c 信道迭代译码算法 消息传递算法也称为迭代译码算法，因为在译码过程中，消息在变量节点和 校验节点之间迭代的传输直到得出结果，或过程停止。不同的消息传递译码算法 针对消息在节点上的不同操作形式而有不同的名字。在一些算法中，比如比特翻 转译码，消息的形式是二进制位；而其他的方面比如置信传播译码，消息的形式 是码的位的值在一定的水平上的可信程度的概率。当这种概率被对数似然比代替， 这时译码算法被称为和一积译码，因为应用对数似然比在变量节点和校验节点上的 操作只有和与积的形式。 在b e c 信道上一个被接收的节点要么一定被正确接收，要么完全被删除。被 接收的节点总是完全的正确，因为译码器的任务是决定未知节点的值。 以偶校验为例，在校验式中如果只包含一个被删除节点，被删除节点的正确 值能被恢复。在消息传递译码器中，当在校验式中仅有一个被删除节点的，校验 式能确定相应删除节点的值。为了与因子图对应起来，把校验式称为校验节点。 在因子图的边上，消息传递译码算法是易懂的：一个变量节点把相同的消息 m 传送给与它相邻的每个校验节点。第f 个变量节点发出的消息记住m ；，变量节 点被正确接收将发送一个值0 或。1 ，如果该节点被删除，它的值为x 。如果校验 节点仅收到一个x 。值，它能通过满足它的其他已知节点的值计算出该未知节点的 值。校验节点将发送不同的消息到与它相连的变量节点。从第，个校验节点发往 第i 个变量节点的消息用e ，；表示，e ，等于由第，个校验节点决定的值0 、1 或 x 。假如一个被删除的变量节点接收的消息是一0 或1 ，该变量节点就等于接收到 的消息的值，否则，不改变。这个过程一直重复，直到每个变量节点都被确定， 或到达译码器设置的一个最大值，译码器停止译码，宣布此次译码失败。 以上的消息传递译码算法用伪码描述如下。设输入的长为刀码字，= i n ，厶l ， 代表，中第f 位的值，其值有三种情况1 、0 或x ；输出长为门的码字是 m = 阻l 一，m 。】，m 。代表m 中第f 位的值，其值是1 、0 或。x 之一。 1 ：p r o c e d u r ed e c o d e ( y ) 2 ： 3 ： i = 0初始化 4 ：f o rf = 1 ：nd o 5 ： m f = r t 6 ：e n d f o r 7 ： r e p e a t 第三章删除信道下l d p c 码中迭代译码算法及改进2 5 8 ： 9 ：f o rj = 1 ：md o 步骤1 ：计算校验节点 1 0 ：f o ra l l f 色d o 1 1 ： i f 传给校验节点歹的值m ，是一x 1 2 ： e j j2 ，e 铀，m o d 2 ) 1 3 ： e l s e 1 4 ： e j ，f = x 1 5 ：e n di f 1 6 ：e n df o r 1 7 ：e n d f o r 1 8 ： 1 9 ：f o rf = 1 ：nd o 步骤2 ：更新变量节点 2 0 ：i fm i = jxt h e n 2 1 ： i f 存在歹a f 且e j f x t h e n 2 2 ： m f 2 e j j 2 3 ：e n d i f 2 4 ： e n d i f 2 5 ： e n df o r 2 6 ： 2 7 ：i f 所有的m ，都是已知的或者i = i m a x t h e n 检验 2 8 ：f i n i s h e d 2 9 ：e l s e 3 0 ：i = i + l 3 1 ：e n d i f 3 2 ：u n t i lf i n i s h e d 3 3 ：e n dp r o c e d u r e 3 2 2b e c 信道迭代译码过程 为说明迭代译码的过程，以简单的码长为6 的正则( 2 ，3 ) 码为例，其校验矩阵 和因子图表示如图3 2 所示，译码过程如下： 为叙述方便，以数字编号代表相应的节点。用b 代表与第，个校验节点相连 的变量节点的集合，易可表示如下： 删除信道下迭代译码的研究 b 1 = l ，2 ，4 ，b ：= 1 2 ，3 ，5 ) ，b 3 = 1 ，5 ，6 ) ，b 。= 3 ，4 ，6 ) 用4 代表与第i 个变量节点相连的校验节点的集合，4 有如下表示： 彳。= 1 , 3 1 ，a ：= 1 ，2 ) ，a ，= 2 ，4 ，a 。= 1 9 4 ，a ，= 2 ，3 ，a 。= 3 ，4 ) r 三1 圭10 ；1 三00；、 1234 图3 2 校验矩阵与因子图 设码c 是用以上矩阵编的码，其值为c = o01o11 1 ，c 通过删除信道发送。 f o01x xx 】是接收的码字。消息传递译码器被用来恢复被删除的变量节点。 初始化，m ，= t ，因此m = 【o01x xx 】。 第一步，计算校验节点。第1 个校验节点与第1 ，