（信号与信息处理专业论文）低密度校验码的理论研究及其在工程中应用.pdf

摘要 摘要 低密度效验码的理论研究及其在工程中应用 硕士研究生：付明导师：赵力教授 东南大学信息科学与工程学院 低密度校验码( l o w - d e n s i t y p a r i t y - c h e c kc o d e s ) 是一类可以用稀疏的校验矩阵定义且 可用迭代方法译码的线性分组纠错码它最初由g a l l a g e r 于1 9 6 2 年提出，近来由于受到t u r b o 码研究的启发，l d p c 码被重新发现并受到编码界的极大关注，己成为目前最热门的研究领域 之一l d p c 码和t u r b o 码以各自的方式实现接近香农极限这一目标。l d p c 码具有较大灵活性， 描述简单，并且当码长足够长时，l d p c 码显示出比t u r b o 码更为良好的性能。 近年来l d p e 码作为一种性能优越且具有极大潜在应用价值的纠错编码越来越受到编码学 者和工程师们的关注。本文对l d p c 码进行了较系统的分析和研究。本文从线性分组码的理论 出发，延伸到l d p c 码，分析了l d p c 码的分类。图结构和性能影响因素。本文重点是l d p c 码在 中国啪系统中的应用，以及从代数码角度出发的l d p c 的编译码和设计方式，重点对各种编 码方式进行了研究并给出了编码复杂度分析。本文选用了多种典型码字，在各类信道和映射 方式下进行了大量的仿真和性能分析，研究了硬判决算法中的门限问题，以及噪声估计失配 对和积算法的影响。然后介绍了标准b p 译码算法，给出了该算法的理论基础和实现步骤，并 在a w g n 信道及衰落信道下对其进行性能仿真，研究不同因素对译码性能的影响。 针对中国d t t b 系统这一具体应用，本文仔细分析了系统中三种不同码率的码字的结构以 及行重列重分布规律，衰落信道下的译码方法，重点分析了多进制映射下的软判决软输出问 题。并在此基础上提出了新的分别基于软判决和硬判决的改进算法，仿真结果表明，上述算 法对d t r b 系统中的码字性能有明显的性能改善。 关键词：低密度奇偶码，t a n n e r 图，s a p 译码，b f 译码。几何码，准循环码，d t f b a b s t r a c t r e s e a r c ho n l o w - d e n s i t yp a r i t y - c h e c kc o d e st h e o r ya n dt h e i r a p p l i c a t i o n su p o nt h ee n g i n e e r i n gb a c k g r o u n d b ym i n g f u s u p e r v i s e db yp r o f l iz h a o d e p a r t m e n to fr a d i oe n g i n e e r i n g s o u t h e a s tu n i v e r s i t y t h el i n e a rb l o c kc o d ei sc a l l e dab i n a r yl o w - d e n s i t yp a r i t y - c h e c kc o d ef li t sp a r i t y - c h e c km a t r i x i ss p a r s e t h i ss o r to f c o d ew a s o r i g i n a n yp m p e s e db yd r g a l l a g e ri n1 9 6 2 ，w h i c hi sn o w r e d i s c o v e r e da n da t t r a c t sa l a r g ea m o u n t o f i n t e r e s t p a r t l yd u e t o t h ee x l l m es u c c e s s o f t u r b o c o d e s b o t hj nt h e o r ya n dp r a c t i c e l d p cc o d e sa n dt u r b oc o d e sa l es i m i l a ri nm a n ya s p e c t s b o t hc a n e x t r e m e l ya p p r o a c ht ot h es h a n n o nl i m i t sb yt h e i ru n i q u ew a y s m o r e o v e r ，l d p cc o d e sa r e r e l a t i v e l ye a s yt ob ec h a z a c t u r i z e d a n dc a no u t p e r f o r mt u r b oc o d e sw i t hs u f f i c i e n t l yl o n gb l o c k l e n g t h s t h i st h e s i sp r e s e n t sac o m p r e h e n s i v es t u d yo nt h ep e r f o r m a n c eo fl d p c c o d e s f i r s t ，w e b r i e f l yi n t r o d u c et h ee n c o d i n gs t n t c t u r eo fl d p cc o d e s ，i n c l u d i n gt a n n e rg r a p h ，s e v e r a l c o n s t r u c t i o n sa 砌r e s p o n d e de n c o d i n gm e t h o d s a n dr e l a t e dc o m p l e x i t yi s s u e s t h e nf o ri t sd e c o d i n g u s i n gs o - c a l l e ds t a n db e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h mt o g e t h e rw i t ht h eo t h e rm a j o rd e c o d i n g a l g o r i t h m s , b f , w b f , l p - w b f , a n da n o t h e ri m p r o v e db pa l g o r i t h m s t h ep e r f o r m a n c es i m u l a t i o n s a r ea l s oc a r r i e do u to v e ra na d d i t i v ew h i t eg a u s s i a nn o i s e ( a w g n ) a n d f a d i n gc h a n n e l st of i n do u t t h ec r u c i a lf a c t o r st h a tc a l ls e r i o u s l ya f f e c tt h ed e c o d i n gp e r f o r m a n c e a s o n eo f c o n t r i b u t i o n s o f t h i s d i s s e r t a t i o n ，a l l i m p r o v e dd e c o d i n ga l g o r i t h m b a s e d o n t h e b f a l g o r i t h m ( i t e r a t ef - b f ) i sp r o p o s e d c o m p a r e dw i t hb fa l g o r i t h m , i ta c h i e v e sc o n s i d e r a b l e i m p r o v e m e n tf o rl o w c o l u m nw e i g h tl d p c w i t ha l m o s tt h es a m ec o m p l e x i t y k e y w o n l s ：l d p c ，b pd e c o d i n g , t a n n e rg r a p h ，e g l d p c ，s p a r s em a t r i x ，t e r r e s t r i a ld i g i t a lt v 2 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个入在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：五母一日 期：j 生盟土 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：短盈盈 导师签名：垫盘 日期：上迸： 拿 第一章绪论 1 1 信道编码 第一章绪论 通信的目的是将载有信息的信号可靠的传送给对方，然而由于在传输过程中数字信号 受至q 干扰，使信号码元波形变坏，接收端可能发生错误判断。信道中乘性干扰引起的码问干 扰，通常可以通过均衡技术纠正，而对于加性干扰，除了要选择合适的调制解调方法以及调 节发射功率外，纠错编码也是必须考虑的环节。 一个基本的数字通信系统如图1 1 所示其中，信道编码器的作用是按某种算法，对信 源码适当的添加冗余比特，使得接收端信道译码器根据这些冗余比特尽量多地找出并纠正错 码。 臣 击 图1 - 1 数字通信系统得基本模型 由于信号在信道传输过程中将不可避免的受到噪声的干扰，使信号码元波形变坏，接收 端可能发生错误判断。信道中乘性干扰引起的码间干扰，通常可以通过均衡技术纠正，而对 于加性干扰，除了要选择合适的调制解调方法以及调节发射功率外，采用先进的信道编码技 术也是必须考虑的环节。 信道编码又称为差错控制编码，是通信系统设计中的关键技术之一。通常，在发送端由 信道编码器( 以下简称编码器) 根据某种规则对信源信息加以某种运算从而形成一定数量的 冗余信息( 即校验信息) ，与信源信息一起组成码字，经信道发送出去。而在接收端，则由 信道解码器( 以下简称解码器) 根据冗余信息，通过某种对应的运算尽量多地找出并纠正错 码，从而恢复信源信息。 1 9 4 8 年，香农发表的著名的 一文为信道编码技术的发展指明了方 向。首次阐明了在任何一种有扰信道中均存在一个确定的信道容量g 只要信息以小于此信 道容量的速率传输，传输错误概率就可以任意小。s h a n n o n 定理的完整表述是：没亓是信息 传输的速率，f 是离散无记忆信道的信道容量，s 是一个任意小正数，则只要f 3 ) 个1 ，每行有( 也 也) 个1 的正则码，将校验矩阵按行水平的分 割为d 。个大小相同的子矩阵，每个子矩阵的任一列都只包台一个1 ，第一个子矩阵按特定的 方式构造而成，所有列只包含一个1 ，g a l l a g e r 文中是甩的递减的形式排列，即第珩所有的 1 都分布在第到( f 1 ) j + l 到弦列。其它下面的- ，1 个子矩阵都是是第一个子矩阵的随机 列交换而成这种构造方法可如下表示 h 。为第一个子矩阵 h o = 整个h 阵为 h = l l l 1 屯 。：h ( h o 。) 7 d 。( h 。) 幽 d c 1 1 1 l 屯 ( 2 3 7 ) ( 2 3 8 ) 这里石代表对矩阵作列交换。 这种构造方法简单，易于实现和分析，但不能控制矩阵的t a n n e r 图中短环的出现，影 响了b p 译码性能。 2 3 2m a c k a y 的构造 为消除校验矩阵中的短环，h a c k a y 在g a l l a g a r 的基础上提山了臼己的构造思想 1 3 ， 通过删除一些列，达到消除短环的目的。当然，由于减少了一些州，在码率上也会有点损失， 并且行重不再是严格的相等。 东南大学硕士学位论文 具体的构造思想有如下四个： 构造法i a ：这是最基本的构造方法，该方法构造的矩阵每列的重量都为一固定值t ，而每 两列之间重叠的1 的个数不大于1 。 构造法2 a ：对于一个m n 矩阵，前m ，2 列的重量都为2 ，并且各列重复不超过1 ，这 些重为2 的列由两个m 2xm 2 的单位矩阵构成，一个在上，一个在下。其余如l a oo ( a ) o ( b ) 图2 - 1 2l i a c k a y 的构造方法( a ) 1 a ：( b ) 2 a 构造法1 b 。2 b ：由构造l a 或构造2 a 构造校验矩阵，然后从该矩阵中删除一些仔细选择的 列，使得结果矩阵对应的二分图中没有小于某个给定长度的环，例如1 = 6 。 上图中的圈代表，圈中的数字3 代表此矩形中有该数字个排列矩阵的叠加，对角线表示 单位矩阵。 2 3 3 p e g ( p r o g r e s s i v ee d g e - g r o w t h ) 码 构造思想是以增加g i r t h 为目的；p e g , 方法的具体操作：给定变量节点的数目、校验节点 的数目m 和变量节点的分布序列，边选择程序开始放置新的边，选择新边时尽可能萍f r a n n e r 图的g i r t h 有较小的影响；新边放置好后，继续搜索下一个边，直到结束。 2 3 4 有限几何构造 上述几种都是随机构造方法，是无结构的，在发送和接收端要刚人餐的空间来存储矩阵 信息，而且编码很复杂。而系统码有特定的结构，可以克服这些问题。l i ns h u 等人”1 提出 了基于有限几何( f i n i t eg e o m e t r i e s ) 的构造方法。这种码有如下优点：有很好的最小码 距；它的t a n n e r 图的g i r t h = 6 ；迭代译码的性能好，并且具有循环或i ，循环的性质，可以实 现线性时间编码，这是其它l d p c 码所不具备的性质。男外，硬判决性能较其它的码好，译码 收敛快，这个特点将在后面的仿真中体现。 为介绍这种码，我们需要先简单介绍一些有限儿何的有关概念。 有限几何的定义：改g 是一个由点、线构成的有限儿何，这些线点具有这些结构特点：1 ) 第二章典型信道编码的理论及其描述 每条线上有p 个点；2 ) 两点之间有且只有一条线：3 ) 每个点上有，条线通过；4 ) 两条线 或者平行，或者相交于一点。共有两种有限几何，分别是欧氏几何( e u c l i d e a ng e o m e t r i e s ) 和映射几何( p r o j e c t i v eg e o m e t r i e s ) 。 对于g f q ) 域上的m n 的校验矩阵h ，h 的行代表几何空间里的线，列代表几何空 问里的点第j 点在第，条线上，则矩阵中= 1 ，否则= 0 ；由有限空间的定义知，此 矩阵各行之间最多只有1 个位置重叠，因此不会有长度为4 的环。 l i ns h u 等人共提出四种e g - l d p c 码的构造方法6 。分别是1 ) t y p e - ie u c l i d e a ng e o m e t r y ( e o l d p c 码：2 ) t y p e - i ib g l d p c 码：3 ) t y p e - ip r o j e c t i v eg e o m e t r y ( p g ) 一l d p c 码： 和4 ) t y p e - i iw i r - l d p c 码。这里只介绍t y p e - ie g 的构造方法 e g ( m , 2 。) 是定义在g f ( 2 ) 域上的m 维欧氏几何，有2 “个点，每个点g f ( 2 。) 上的廖重， 全零向量o = ( o ，o ，o ) 称为几何空间的原点。在g 吨。) 上的2 “个口重矢量构成了g f ( z ) 上 的口维矢量空闻，因此在e g ( m ，z ) 上的一条线要么是e g 缸2 ) 的一维子空间，要么是一维 子空间的陪集。因此e g ( m ，2 ) 上的每一条线均包含包括2 。个点。在e g ( m ，2 ) 里共有 2 卜咖( 2 ”一1 ) ( 2 5 一1 ) 条线，每条线均有2 ( “。条线与之平行，每个点均有( 2 ”一1 ) ( 2 一1 ) 条线相交于此 g 唯一) 是g f ( 2 ) 的扩域，在g f ( 2 “) 里的每一个元素都可以表示g 雌t ) 上的厘。因此， 在g f ( 2 ”) 里的每个元素可以用来表示e g ( m ，2 ，) 上的点，有限域g f ( 2 一) 可以表示欧氏几何 e g ( m , 2 ) 。设口是g f q “) 里的本原元素，盯”，口。，口，口2 ，9 2 m 一2 就构成了e 6 b ，2 - ) 的2 “个点，这里0 = 口。是空间的原点，设o l 是非零点，则2 个点： 缸 - 缸：g f ( 2 ) 构成空间e g ( m ，2 s ) 中的一条线。设口，口，是e g ( m ，2 s ) 里的 两个线性独立的点，那么下面点的集合矗+ 肚 = 扛+ r i c e ，：g f ( 2 5 ) 就是在 e g ( m ，2 - ) 中通过点口的一条线，则线扛+ 触，) 和i 矗+ 膨) 相交r 点口。 假设h k 协，j ) 是g f ( 2 5 ) 域上的矩阵，矩阵的- 是e g b ，2 ) 中不过原点的线在g 雌8 ) 中的映射向量，列是e g ( m ，2 。) 中的2 ”一1 个非零点。第i 列对应予口7 。这样，h 共有 m = ( 2 啦一1 ) ( 2 ”一1 ) ( 2 一1 ) 行，2 ”一1 列。行重为p = 2 ，列重为 东南大学硕士学位论文 q ”一i ) ( 2 一1 ) - 1 ，因此，当码长很长时，矩阵就变得很稀疏；码字的最小距离至少是 e 厝一t 矽( 2 一1 ) 。 以e g ( 2 5 5 ，1 7 5 ) 的校验矩阵何k ( 2 ，4 ) 为例，说明第一类b g 码的构造过程。因为_ 2 ， s = 4 ，所以首先找出g 雌8 ) 域的本原多项式p ( 功= 1 + 工2 + ，+ 一+ j 8 ；其次，需要求出 经过某一点口的任意一条不过原点的直线上的所有点。已知通过点瑾的一条线上的点具有 k + 届口 = 缸+ 触：声a f ( 2 5 ) 形式，如果我们取f ：2 5 4 ，就要求满足形式为 缸“+ 触 的点，取y = 口( 2 m - 1 ) h r “，贝i f l e o , 1 ，y 2 ，4 ，根据运算可以得 到一条含1 6 个点的一条直线。之后，由所得的直线去求出该直线的关联矢量，该矢量由2 5 5 个点( 不包含原点在内) 组成，如果某点在直线上。则关联矢量该点处的值为1 ，不在此喜 线上则为0 。 最后，由所得的关联矢量作为校验矩阵的第一行，对该矢量向右循环移位2 5 4 次，每次 得到的矢量均作为校验矩阵的一行，就得到了二维欧氏几何l d p c 码的校验矩阵。码的参数 如下表所示： 表2 qt y p e ie 1 ；2 5 5 的参数 sn kd - i n p， 242 5 51 7 51 71 61 6 根据矩阵的构造知这个码具有循环特性，可用生成多项式g ( x ) 编码。求取它的生成多项式 之前先介绍一个符号，( ) 的定义和定理2 2 “。 定义：令h 是小于2 “的非负整数，我们能把h 展成如卜i 的以2 5 为基的形式 h = 磊+ 4 2 1 + + 瓯一1 2 册_ 1 p 式中0 参 2 ，其中0 i m 。则 ，( ) = 乙。m ：- 。1 点 ，( a ) 表示矗的2 3 重量。 ( 2 3 9 ) ( 2 4 0 ) 第二章典型信道编码的理论及其描述 定理2 _ 2 令口是0 ，) g 七5 ) 的本原元，这里：o 令i l 是小于2 “一l 的非负数。令j | i n 是2 ”一l 除2 1 h 所得余项，即 2 1 h = q ( 2 ”一1 ) + _ i | o ( 2 4 1 ) 这里o h o 2 。一l ，h = h 。长为2 ”一l 的0 ，j ) e g 码的生成多项式g g ) 以口为根 的充要条件是： o o 墨，( _ j l ) ( m 一一1 ) ( 2 一1 ) ( 2 4 2 ) 定理3 1 表征了阱码的生成多项式的根。下面给出生成多项式的求取算法： 1 ) 固定西是小于2 “的非负整数，当0 ， j 变化时，根据式( 3 3 ) 求取h ( o ； 2 ) 使h 在0 h 2 ”范围内变动，求出满足式( 3 - 4 ) 的所有h 。 3 ) 求出的k 个根两得到相应的盯，就是多项式g g ) 的根。 2 4 小结 我们简单介绍了线性分组码，循环码，准循环码和低密度奇偶校验码的定义及其描述方 法。重点在低密度奇偶校验码，还分析了其图结构和性能影响因素。那么，循环码，准循环 码和低密度奇偶校验码这三种同属于线性分组码范畴的码组之间又有什么关系呢? 如果把 线性分组码作为一个全集，我们可以得到下面这张图。 口线性分组码 。 低密度奇偶校验码 。准循环码 ，氟聊 图2 一1 3 线性分组码，循环码，准循环码和低密度奇偶校验码之间的关系圈 从图中可以看出，循环码是包含在准循环码范围内的，是准循环码的一个特例。注意 到准循环码和低密度奇偶梭验码之间重叠的部分。这部分码臻既有循环或准循环的特性，又 是低密度的码。通过后面章节的分析和介绍我们将会看到，这重叠部分的码组由丁其循环或 准循环性，在编译码上比较简单；又由于二其稀疏性，对丁存储空间的需求相对较小，因而_ l f 常实用，将是我们一f 面要研究分析和应删的重点。 本章主要介绍了l d p c 码的各种定义，表示法，结构，以及编码方法。土要介绍了来 东南大学硕士学位论文 两种编码方法，并重点介绍了其中一种的编码复杂度分析。这两种编码方法本质上是对 l d p c 的效验矩阵h 进行矩阵的某种初等变换，形成较易于实现编码的方式。除此之外，我 们还可以对h 进行g f ( 2 ) 的因子分解( 如满秩分解，三角分解，奇异值分解等) 实现快 速简洁的编码。生成了l d p c 码的效验矩阵，就可以进行编码和译码了。我们将在下一章 中详细的研究l d p c 码的各种译码算法。 东南大学硕士学位论文 第三章l d p c 码的译码算法 l d p c 码之所以能有这样好的性能，很重要的原因是在译码中采用迭代算法。并且由于 校验矩阵的稀疏性，使得译码的复杂度和码长成线性关系，克服了分组码在码长较长时所面 临的计算复杂度问题；另外，在码长很长时，相距很远的信息比特参与同一校验，这使得连 续的突发差错对译码的影响不大，也就是说编码本生就具有抗突发差错的特性，一般情况下 可以不需要引入交织器。 l d p c 码的译码算法主要有基于编码二分图结构的m e s s a g ep a s s i n g 算法类。算法的性能 随量化阶数的增加而提高，同时复杂度也随之增加。大致可以分为硬判决和软判决。硬判决 实现筒单，但性能不佳，软判决则正好相反。性能好，但实现复杂。 g a l l a g e r 最初就给出了两种迭代译码算法：硬判决( b i tf l i p p i n g ，b f ) 和软判决算法 ( f r o b a b i l i s t i cd e c o d i n g ) 。前者计算复杂度很低，但其译码性能不理想，后者虽然性能 更好，但复杂度太大。之后，研究者们对硬判决和软判决提出一系列改进算法。硬判决方面， 文献6 中提出了一种简单的改进算法( w e i g h t e db f ) ，采用信道的软信息对比特翻转的判 据进行加权，可以在译码复杂度增加不大的情况下，提高译码性能。为了进一步缩小与软判 决算法的差距，在w b f 算法的基础上，又出现了两类算法：l p w b f 算法”1 和w s 一耶f 算法， 它们在基本不增加译码复杂度的情况下，使w b f 算法的译码性能有了较大的提高。另外，针 对有限儿何码，还有大数逻辑译码，文献“1 中还提出了加权大数逻辑译码。 软判决方面，1 9 9 9 年m a c k a y 和n e a l 提出了将b p ( b e l i e fp r o p a g a t i o n ) 算法用于l d p c 译码“”，也称为s u m - p r o d u c t 算法，其译码性能比硬判决算法好的多。而相应的运算复杂度 也不犬。f o s s o t i e r 对低复杂度的b p 算法作了进一步研究，提出t b p b a s e d 算法”1 ，简化了 b p 算法。为了改善b p b a s e d 算法因为校验节点上的简化处理而造成的性能损失，j c h e n ”“” 提出了阿种改进算法：采用归一化的近似最佳b p b a s e d 算法( 亦称为n o r m a l i z e d b p b a s e d 算法) 和i 通过降低可靠性值来改善外附信息精度的o f f s e t8 p - b a s e d 算法。本章将主要研 究上面提纠的b f 、w b f 、l p w b f 和b p 、b p b a s e d 、n o r m a l i z e db p b a s e d 算法。 这里我们暇攻信道是二进制对称信道( b s c ) ，信道噪声为加性高斯自噪声( a w g n ) ， 噪卢均值为0 ，功率酱密度是n o 2 。_ h j b p s k 调制，能量为1 ，编码后序州v = ( v o ，v l ，v _ 一1 ) 被映射成x = ( ，。l ，一，x 一1 ) ，这里映射公式是= - 2 q + 1 ，( 0 f ) 。接收匹配滤波 3 2 第三章l d p c 码的译码算法 器的输出y = ( ，y l ，) ，_ 一i ) 作为软判决的输入，乃= + n j ，( o i 0 ( 3 一1 ) 这里先给出几个符号的定义：校验方程为h u 。，h j = ( h i o 一j ，h j , , v - i ) 代表行向 量，s 是校正子，s = ( s o ， ，置- i ) = z h 7 ，其中 s ，= z 乃= = z t h ( 3 - z ) s = 0 表示校验成功，s = l ，则校验失败。其中，下标i 代表第i 行。c ( i ) 表示第i 个比特参 与的校验式的集合，n ( j ) 表示参与第j 个校验式的比特的集合。 3 1 译码算法综述 广泛使用的l d p c 码的译码算法主要是基于t a n n e r 豳的消息传递算法( m e s s a g ep a s s i n g a l g o r i t h m ) o 集，是基于二分图结构的译码算法，由于在算法的运行过程中，可靠性信息 在二分图的变量节点和校验节点之间来回的传送，因此称为m e s s a g ep a s s i n g 算法。 邪算法译码过程中的每一步，消息都沿着二分图中的边在节点之间交换。算法的性能 随量化阶数的增加而提高，同时复杂度也随之增加。其中最常用的和性能最好的，但也是最 复杂的是和积算法( s u mp r o d u c ta l g o r i t h m ) z 4 1 ，是无穷阶量化也即连续性算法，通常又 称为置信传播算法b p ( b e l i e fp r o p a g a t i o n ) ”，它的性能在t a n n e r 图中没有氏为四的圈 时可等效于最大似然算法。为了在译码和复杂度之问达到更好的平衡，义出现了简化的和积 译码算法：最小和算法( m i ns u ma l g o r i t h m ) 1 以及基于最小和算法的改进算法。改进算 法使用较多，性能较为突出的是规一化最小和算法( n o r m a i l i z e ds u ma l g o r i t h m ) ”。另 外，s c h u n g ，t j r i c h a r d s o n 和r i j r b a n k e ”提出了一种基于迭代可靠性的算法， d ，b u r s h t e i n 和g m i l e r “”提出了基于扩张图观点的并行译码算法。由于直接使用了信道的 输出消息而没有做任何判决，上述译码算法统称为软削决译码算法。 m p 算法在运行过程中，可靠性信息在二分图的变鲑仃点和校验节点之间来【亓l 的传送， 当船算法中的信道输出符号集合和译码过程中发送的信息符号集相同，都为两元素符号集 卜1 ，+ 1 ，也就是采用两阶量化，且适当的选定映射函数时，这种算法就是g a l l a g e r 最初 提出的硬判决译码算法”，该算法具有最低的译码复杂度，但性能也是m p 算法中最筹的， 适合用于光纤通信等信道条件很好的情况，也可埘丁粗略的判断校验矩阵h 对应的l d p c 码 是否具有良好的纠错性能。在便判决中，实际采川的方法是“位翻转”( b i tf 1 i p p i n g ) ，因 此通常称为b f ”1 算法。该算法只需计算模2 校验和，井川计算结果进行判决，冈此计算复 3 3 卸以 蹙 东南大学硕士学位论文 杂度相当低，并且主要采用异或门和比较器，易于完成硬件实现。然而，与软判决算法相比， 硬判决算法的性能要远远不如，因此，出现了一些性能和复杂度都介与两者之间的算法，本 质上都是基于校验和的位翻转算法的加权，比较有代表性的有，w b f “，l p - w b f “1 ，w s - 骼f ”等。 3 1 i 硬判决算法及其性能 3 1 1 1 简单昨的算法 b f 算法是由g a l l a g e r 在6 0 年代”首先提出的。当传输过程中发生可检测错误时， s = ( s o ，墨，j - 1 ) 会反映出校验失败信息，s 中的部分元素等于l 。当接收序列z 中的一 个比特发生改变时，校正子向量s 会发生改变，两这种变化也正是b f 算法的基础。该算法首 先根据输入的z 计算校验字向量；然后根据校验结果，找出使得校验式不成立数目达到所设 门限( t h r e s h o l d ) 一参数j 的变量节点；随后翻转这些节点，至此完成一次迭代。整个译码 过程不断的重复前面的各个步骤，直到所有的校验式都成立或者到达了事先设定的最大迭代 次数。 假设h 是一个j 行n 列的校验矩阵，用h l ，h 2 ，h j 表示h 的各行，其中h i ( i i q ) ；( k o ，h j i ，j 谆i ) 。接收机接收到的码字的硬信息序列为z = ( z i ，稚i ) ，则校验 和s = ( s 0 ，s l ，s j ) = z l i t 给出了接收序列z 的校验向量，其中的每一个$ ( 1 j j ) 由下 列的校验方程的值所得到： 月一i o = z 一= 巧 ，j ( 3 3 ) i = 0 当且仅当产o 时表示接收到的码字z 是正确的，否则，在z 中存在可检测的错误。也就 是说，当接收到的码字中存在错误时，则s 中必有至少一位为l 。因此在译码的一次迭代过 程中，首先根据s 翻转z 中的某些比特位，锝到新的z 后，可以得到更新后的s 。由s 是否 为0 判断译码是否正确。b f 正是根据上述思想来进行迭代译码。下面给出实用的b f 的算 法步骤。 第一步：由接收序列z 根据式4 1 计算校验和s 。若s 为全零，表示接收正确，停止译 码并退出；否则转第二步。 第二步：计算每一位码字所对应的不满足校验和的校验方科的数日，记为，( i _ o ， 1 ，i l 一1 ) 。 第三步：对f o ，0 l 进行相应的从人到小的排序，得刮的最人值记为。 第四步：将e 。对应的码字比特进行翻转。 第五步：重复一至四步，直至所有的校验方样都得剑满足( 此时，译码止确并能在第一 步退出) 或超过了最大的迭代次数( 此时没有