（通信与信息系统专业论文）ldpc码译码算法研究.pdf

摘要 低密度饺验( l o w d e n s i t y p a r i t y c h e c k ，l d p c ) 码是具有稀疏饺验 矩阵的分组纠错码，它具有逼近香农极限的性能特性。但l d p c 码在长 码h 寸，具有较高的译码复杂度，并带来一定的时延。 针对l d p c 码长6 马译码复杂度高的问题，先后提出了置信传播( b p ) 算法与经典的比特反转( b f ) 算法结合、b p 算法与标准权重比特反转 ( s l a n d a r dw b f ) 算法结台、b p 算法与改进的标准权重比特反转 ( m o d i n c dw b f ) 算法结合、b p 张! ；i ! i 算法。仿真结梨表明，与b p 算法 相比，上述几利，钟：法刘l d p cf i 马译码性能改善j 附挣有限。 在上述j l 种算法的丛m l ，又捉：u 了混合比特反转( h b f ) 算法。 该筇法充分利，f j 了l d p c 码b p 算法输出的软信息捉商了经典的8 f 算 法的可椎性，改善丁误码性能。a w g n 信道下的仿真结果表l 吼在棚同 的译码复杂皮1 晰况下h b f 算法的性能明显优于b p 算法，并呈现出更 低的误码平台。 【关键词】低密度校验码。置信传播算法，比特反转算法 混合比特反转算法 a b s t r n c t l d p c ( l o w e rd e n s i t yp a r i t yc h e c k ) c o d e sa r e ak i n do fb l o c k e r r o r - c o r r e c t i n gc o d e sa n dt h e yc a na p p r o a c hs h a n n o n sl l m i tw h e np r o p e r l y d e s i g n e d w h i l ei n l p l e m e n t a t i o nc o m p l e x i t ya n dd e c o d i n gd e l a yb e c o n l e i n v o l v e df or l o n gl d p cc o d e s h 1o r d e rt os o i v et h ep r o b i e n l s ，i h r e ec o m b i n a t i o na l g o “t h m s ，i n c i u d i n g b e l i e p m p a g a t i o l l( b p ) c o m b i n e dw i i h b i l f l i p( b f )a l g o r i 【h m ， b p c o n l b i n c dw j l l ls i a l l d a r d w e i g h t c db f ( w b f ) a l g o r i t h ma n db pw i l h m o i i n c d 、v b fa r cp i o p o s c da sw e i la sr e l a x a i i o n - b a s e db p a l g or i i l l n l t h e s i l l l l i l a t i o l lr c 乳l i l ss 1 1 0 wt h a io n l yal j t i l ci m p r o v e m c n tc a nb em a d ef o r1 1 1 e a i g o r “h n l sj nc o n l p a r i s o i l 、v ic h 1 eb pa l g o r i l h n l 8 a s c d0 1 1i h cf o r c g o i n ga l g o r i l l l m s ，h y br i db i tf i i p ( h b f ) d e c o d i n g a l g o m 1i st 1 1 e 1 1p l o p o s e d ，w 1 1 i c l lm a k e sf l l l lu s eo f l l l es o ni 1 1 f 0 咖a t i o no f 1 1 1 e o l l l ) l i t o rb pd c c o d i n ga l g o 洲1 n 1f o rl d p cc o d e s ，l h u si 1 1 c r e a s i l l g r e i j a b i l i t yo f l l l ec l a s s i c a lb fa i g o r i t l m la 1 1 da c c e l e r a i i n gt h ec o n v e 唱e n c eo f b pa l g or i l l 】m t 1 1 es i ml i l a l j o nr e s l 】l s na w g nc h a n n e 】s h o wl h a ct h eh b f a l g o 咖1 mo l l t p e r f b n u s m eb p a l g o r i l l l i l l w i t ha l m o s tt h es a n l e c o i n p u t a t i o n a lc o n l p l e x i t ya n dc a ng e tn l u c hl o w e re r r o rn o o rt h a nt h eb p a l g o r i t l m l 【k e yw o r d s 】l o w - d e n s i t ) rp a r i t y - c h e c k ( l d p c ) c o d e s ； b e l 主e f p r o p a g a 巧o n ( b p ) a l g o t l n ； b i tf 1 l p ( b f ) a l g o r i t h m ； h y b r i db i t f 1 i p ( f ) a l g o r i t m 北京变通人学碗i 毕业论文 l d p c 玛泽驾算：三，：目竞 1 1 信道编码简介 第1 章概述 1 9 4 8 年，香农( s h a m l o n ) 在论文通信的数学理论中提出并证 明了：对于一个信道容量为c 的有扰信道消息源产生信息的速率为凡， 只要月耋c ，则总可以找到一种信道编码和译码方式使编码错误概率p 随 着码氏，t 的增加按指数下降到侄意小的值，三个必要条仲足： ( 1 ) 采用随机编、译码方式： ( 2 ) 编译k 度，一一。即分组的码组长度无限； ( 3 ) 译码采用盯壶他的最大似然译码法： 在以上三个必要条件下，s 1 1 a 1 1 n o l l 证明了在信道巾司以实现无茇锵 f 输。后来1 9 6 5 至1 9 6 8 年，r g g a l l a g c r 给出了误码率p cn 0 指数界 表示) ( ；邓1 ：乒 c ，则不存在编译码方式来实现无误传输。这 结论为信道编码指出了方向但它仅是一个存在性定理，并未给出怎样 去寻找这种性能优良的码。 信息论诞生5 0 年来，构造好码基本上是按照s h 枷o n 所引用的三个 基本条件。在信息技术发展和实际需要的不断推动下，人们一直在寻求 实现复杂度合理的更优秀的编译码方法去逼近s h a n n o n 理论的理想界 限。令人鼓舞的是，在这个过程中，已经取得了许多伟大的进展，从早 北京交迪：掌6 i ! l j 毕业沦上l d p c 玛i 鸿算注斟充 期的分组码、代数码，到r s 码，到后来的卷积码，以及今天的t u r b 0 ， l d p c 码，所能达到的性能和s h 锄o n 限间的距离被不断缩小。这些方 法也已经投入到多个领域的商用中，如卫星通信和深空通信，数据存储， 数据传输，移动通信，数字音频和视频传输等。 1 2 l d p c 码简介 l d p c ( l o wd e n s i t y p a r i f yc 1 1 e c k ) 码是g a l l a g e r 于1 9 6 2 年提出的一 种具有稀疏校验矩阵的分组纠错码，也称g a l l a g e r 码l 川。l d p c 码具有能 够逼近香农极限的性能特性；拙述和实现简单，对严格的理论分析具有 可验融肚；编码的泽码算法本质上足并行算法有利于l | ! 件的并行实现， 减少潆码时延；它能够在迭代过程中确定码字是否已译出，减少迭代次 数：译码后的i 炅码率可以随信噪比的增加任意减少，没有误码率下降a 成 迎| | 勺e r r o rn o o r 现织在编码的数学模型上，l d p c 码有自己简单的数 学模型：二分图。l d p c 码的主要问题足译码的复杂度较高，另外，在 长码长时必须在接收到所有的信息比特后才能进行译码，会给译码带 来一定的时延。 l d p c 码具有良好的性能，但译码所需计算量较大。限于当n q 的硬 件条件，再加上r s 码的出现人们普遍认为r s 码与卷积码组成的级i 陕 码性能会更好，且易于实现实用化l d p c 码没有继续成为研究重点。 到八十年代和九十年代初，纠错编码理论和技术取得了很大的发展， 但是离香农理论的极限性仍然有一定的距离，难以找到能够逼近香农极 限的编玛方案。法国的c - b e n _ 0 u 等人在卷积码和级联码的基础上，于1 9 9 3 年提出了种全新的编码方案：并行级联卷积码p 】。这种码的编码器通 过交织器把两个递归系统卷积码并行级联，译码器在两个分量码译码器 北京交通大学面! 上毕业i l d p c 码译玛算注研究 之间进行迭代译码译码之间传递去掉正反馈的外信息，整个译码过程 类似涡轮( t u 通o ) 工作，所以又形象的称为t u r b o 码。在加性自高 斯噪声的环境下，采用编码效率r = 1 2 、交织长度为6 5 5 3 6 的t m o 码， 经过1 8 次迭代译码后，在e 们= 0 7 d b 时，其误码率己低于1 0 ，与香 农极限只相差o 5 d b l 。这种编码能够在长码长时逼近香农的理论极限， 同时译码复杂度也是可以接受的，t l 服b o 码在信道编码理论和应用中取 得了突破性的进展。 1 9 9 6 年，m a c k a y 的研究，使l d p c 码的研究跨入了一个新的阶段阢 昂近几年的研究表明，l d p c 码性能要好于t u r b o 码。它的性能非常 接近香农限。d a v i dj c m a c k a y 证明当l d p c 码经过最优译码时， 可以十分接近s 1 1 a 1 1 n o n 极限，这个结沦适用于二进伽对称信通和列称的 平稳遍历嵘声信_ i 踅j5 】。2 0 0 1 年。t j r i c l a i d s o n 汪洌，非规则低密度奇f _ | ； 校验码( i n e 卧l l a rl d p c 码) 能够煨大限度地接近s 1 1 a 1 1 1 1 0 n 极限【6 1 。在二 元输入：c j 性商j 9 自噪声( b i a w g n ) 信道上。1 ，2 码率的好码距离s 1 1 a 1 1 1 1 0 n 限不到o 0 6 d b 。例如。当码长为1 07 r = l 时，距s 1 1 a 1 1 n o l l 眼仪麓 o 0 4 d b 【5 1 。 近年来l d p c 码以其优异的性能、简洁的形式及良好的应用前景阿 益备受青睐，可以应用于空间通信、光纤通信、个人通信系统、a d s l 和磁记录设备等。t l 丌m o 码的出现将纠错编码领域推向了一个新境界， 而l d p c 码又给编码领域带来了一个新的高潮。对l d p c 码结构及其优 化、译码算法改进、l d p c 码的应用等方面正在不断地探索。 北京交通人学坝l 毕业迨上l o p c 玛译避算注研究 1 3 当前l d p c 码的研究热点 1 3 1 码结构及其优化 l d p c 码结构可采用几何方法、图论方法、实验设计方法、重排 ( p e m l u t a t i o n ) 方法来设计。好的l d p c 码关键在于要有好的译码性能 和需要较少的编码时间。迄今找到的好码都是借助于大量的计算和筛选 生成的，因为尚未提出构建l d p c 码的系统( 或代数) 方法。在设计实 验和统汁分撕干h 结合n 0 实验殴讣方法中，b i b d ( b a i a n c e di 1 1 c o m p i e l eb l o c k d c s j g l l ) 方法较为腆型”。在寻找好的f 冯结构方面，d j c m a c k a y 等呐赴 小别非难则码采用先选择轮廓再选择结构的两步选择方法，验弧了 s l i p e 卜p o i s s o n 结构只有较好性能，并指出：能快述编码的l d p c 矩阵通常 具有下三们形( 1 0 w c r - t 1 i a l l g u l a r ) 结构。 1 3 2 译码性能分析 g ：l l l a g c r 1 3j 曾给出了两种l d p c 码的迭代译码算法：硬判决和软判决 算法。后者虽有好的性能，但太复杂；文献一j 中提出的消息传递算法 ( n l e s s a g e p a s s i n ga l g o r i t l l m ) 可认为是二者的折衷。消息传递算法有时 也称信度传播( b e i i e f p r o p a g a t i o n ，b p ) 算法。在m e s s a g ep a s s i n g 译码算 法中，节点到节点的消息是通过t a n n e r 图传递的。m p l c f o s s o r i e r l l o 川 研究了降低复杂度的u ) p c 码的基于信度传播( b p - b a s e d ) 的迭代译码， 提出了基于可靠性译码与信度传播译码相结合的l d p c 译码算法，以获 取译码性能和译码复杂性的折衷。 北言之运j ：筝颞f 阜业蛇上 l d p c 蚂译玛算法埘梵 1 3 3 软硬件实现 l d p c 码的实现通常需考虑性能、复杂性和灵活性等因素。包括选 择有效的编，译码算法和优化设计：可扩缩的结构支持：宽范围的吞吐量 和各种设计需要；高的编码增益和低的差错平底特性：能与各种调制方 式兼容：译码收敛的早期检测：支持宽范围数据速率和硬件规模：可编 程的码率和灵活的码块长度，支持客户化应用：通过固件( f j m l w a r e ) 对 码进行快速下载和交换( s w a p p i n g ) 等。b l e v j n e 等则给出了一种可 以t 丑胁商用f p g a 实现的l d p c 码验证性设计。 1 3 4 应用 l d p c 码只有巨大的应用潜力将在深空通信、光纤通信、卫星数 字规捌和声频广插、磁光全息存储、移动和固定无线通信、电缆调制 斛i i i 器和数字用户线( d s l ) r h 导到广泛应用i ”i 。 e e l c n l l e r i o l l 等1 1 4 啪1 提出基于二元l d p c 码的多电平编码，并研究 了用于宽带接入网巾不对称数字用户线( a d s l ) 的传输性能，给出了在 a w g n 信道上采用l d p c 编码调制( 从4 - q a m 至1 6 3 8 4 一q a m ) 的性能 仿真结果和在规定编译码时延( c o d i n g - l a i e n c y ) 约束下l d p c 编码采用 d l l a l - 1 a i e n c yp a t h 结构时的性能。 1 4 主要研究内容 ： l d p c 玛经过数十年的沉寂，随着计算机能力的增强和相关理论的 发展，m a c k a y 和n e a l 重新发现了它的重要性，并证明它在与基于b p ( b e l i e f p r o p a g a t i o n ) 的迭代译码相结合的条件下具有逼近s h 锄o n 限的 7 北衷z 通大学顽i ：毕业论上l d p c 鹾泽玛算注辨宽 性能。l d p c 码在许多情况下将取代t u 出o 码的趋势已很明显，研究 l 工) p c 玛的学术意义、商业价值和对通信领域相关技术发展的推动维用 是巨大的。近几年来，国际上对l d p c 码的理论研究已取得重要进展， 在应用基础、工程应用和超大规模集成电话方面的研究正在全方位开展。 本文的研究工作主要是基于北京交通大学科技基金项目“无线数据 通信的可靠性研究”而进行的，该项目的研究目标是：在l d p c 码的码 结构及其优化、译码算法分析研究、译码算法改进等方面有新的突破。 本文研究的主要内容有： ( 1 ) 对l d p c 码编码结构、译码算法等方面进行理论分析；主要包 括l d p c 码的分类、表示方法、软判决与硬判决译码算法等。 ( 2 ) l d p c 编弼、译码算法仿真实现： 川c 浯高进行算法实现，使用m a t l a b 进行数掘图佗化。 ( 3 ) l d p c 译码锋法仿真结果分析： 主要分析了迭代过程巾，比特节点、校验节点的变化规律以及影响 碳冯的各种因素等，j f f f i 码k 对误比特率的影响，迭代次数对误比特率的 影响以及信源对误比特率的影响等。 ( 4 ) 对译码算法的探索。提出了混合比特反转( h b f ) 算法译码； 在译码算法的改进方面进行了大量的仿真分析了b p 算法与经典 b f 算法结合：b p 算法与标准权重b f 算法结合：b p 算法与改进的w b f 算法结合；b p 张弛算法等仿真结果，对今后进行b p 算法与其它算法相 结合，起到了一定的借鉴作用。 通过对l d p c 码的编码、译码算法方面的理论分析与仿真实现在 译码算法方面有所突破，提出了新的译码算法。即混合比特反转( h b f ) 算法。h b f 算法结合了b f 算法与b p 算法，充分利用了b p 算法的软输 出信息，将软输出与一定的门限比较，把比较结果作为比特反转的条件 s 北京交通上学颤l ：毕业i 2 上l d p c 婵详鸦葬注! ：fj ： 之一，一定程度上避免了在临界值附近发生误判的情况，从而降低了误 比特率，大大提高了经典b f 算法的译码性能。在相同的译码复杂度， 即运算量相等的情况下，设定适当的迭代次数，h b f 算法的性能明显优 于b p 算法，并且呈现出更低的误码平台。 北京交通j ：学顾i ：毕业论上l d p c 玛弹玛算；主研克 2 1 定义 第2 章l d p c 码基本原理 根据g a l l a g e r 的论述【3 】j 一个长为l 的l d p c 码由它的校验矩阵h 来定义，浚矩阵的特点是其中的元素o 特别多，l 特别少，即所谓的“低 密度”。一个参数为( 厶r ，r ，t ) 的h 表示该矩阵中每列有d ，个1 每行有r r 个1 ，矩阵大小为m ，l 代表码字长度m 代表校验子的个数。 l d p c 码校验阵i i 的一些性质归纳如下： 每列有f ，个l ，f f ，为任意取他的整数值，且d ，2 3 ； 倚行有f t 个l ，f 为任意取值的整数值，且f ，三f ，； 任何两列的元索同为l 的行数不超过l ，即矩阵中找不到四个，j l i | 是l 的矩形也即没有所谓的“四线循环”； f ， m ，d ， l ： 低密度奇偶校验码是以一个奇偶校验矩阵为特征，对于确定的编码 效率和校验矩阵列向量的重量( 砟) ，l d p c 码的最小距离会随着分组 长度线性增加。当在平稳噪声的二进制输入对称信道上使用最大似然译 码时，对于确定的码率和d ，译码错误的概率会随着分组长度按指数规 律递减。l d p c 码的信道译码是按后验概率设计的，设备的复杂度和译 码器的速度随着分组长度近似线性增加。由于校验矩阵的稀疏性，l d p c 码译码的复杂度只与码长成线性关系，在长码的时候，仍然可以有效地 进行译码。 o 北衰交通人掌顾l 。毕业论上l d p c 玛滞驾算注研究 2 2 表示方法 2 2 1h 矩阵表示 根据校验矩阵h 中行和列中l 的数目是否变化，分为规则码和非 舰则码。 o0l001 110o0o ll00looo0ool o00lo00oll lo 0loo ol l 00 l0o lolo00ol00l0 0 001 io 00l0ol 10o1 1oloo oo o o oo 0o10l0 oil 011ooo o01io 0 ( a ) 规则l d p c 码矩阵； l = l2 dr = 3 dc = 4 0o o0 oo l0 0lol 0oo0 0lo01l00 1o 0 0l 0 o o0l00 ol0lo 0l0 oo0o 0oo0 0 o0l lol0 llo o 00 0o oolo o 0lo1001 1o 0 o 0 0l 10 0 0 0o 0l1 o oo 0o11l0 0 0l ( b ) 非规则l d p c 码矩阵 = ，2 图2 1l d p c 码的矩阵 规则l d p c 码：如图2 1 ( a ) 所示，在每一列上包含固定的d ，个1 ， 在每一行上1 的数目为d ，= 以上m ，l 为信息码的长度，4 ”，所 以d 。 乱。要想获得好的码字，必须满足d ，3 。由于h 是稀疏矩阵， 所以码字间有很大的最小距离1 1 7 1 。 非规则l d p c 码：每一列中1 的数目不固定，如图2 1 ( b ) 所示。 北京交通j 、学颇i 。毕业i 芑上l d p c 妈详玛箅i 主：z i r 咒 2 2 2 双向图表示 l d p c 作为线性分组码可以由双向图表示。假设低密度奇偶校验 码h 由列、吖行组成，码率为| r = l 一此亿，那么相关的双向图由上个 比特节点、吖个校验节点以及一定数目的边组成。每个比特节点称为左 节点，代表一比特的信道编码码字。每个校验节点称为右节点，代表一 比特的校验码字。 规则l d p c 码，相同类型的节点具有相同的度，即一个节点与相邻 节点相适的边的数曰。在图2 1 ( a ) 中，比特节点的度为3 ，校验节点 的度为4 。图2 2 ( a ) 是此规则l d p c 码的双向图表示，图中的粗线表 示节点n 勺度的f ￥况。 ：i l ：舰则l d p c 码每个比特节点有不同的度，校验节点也是如此。 度的分砷t * 况可以用( ，p ) 表示， 删：窆矿 ” 以n i “ 蒯= 缪。 i = 2 ( 2 2 ) 其中，丑是左节点中与校验节点相连的边( 即约束条件) 所占的比例d 、 是左节点中最大的度。只，以一是同样的道理。图2 2 ( b ) 是此非规则 l d p c 码的双向图表示，图中的粗线表示节点的度的变化情况。 在通常的情况下，非规则码的性能要优于规则码，因为在非规则 图构造的码字中，度数较大的信息节点很快得到它的正确傻，这样它就 可以给校验节点更加正确的概率信息，而这些校验节点又可以给度数较 小的信患、节点更多信息，从而产生波浪效应，加速收敛。 1 北亲交通大学唢j 。毕业论上 l d p c 玛译玛算汪讲究 校验节点 ( 曲j 删l j u ) i 6 马( b ) ! | i = 趋呗0l d p c 码 闺2 2l d p c 码的双向图表示 2 3 编译码过程 l d p c 码的编译码过程如图2 3 所示，通过随机编码产生 一 爿= c 是a ，麒矩阵。g 是吖删矩阵，三副州 对a 进行高斯消元，得到= 【p ；，】 臣 图2 t 3u ) p c 编译码过程框图 北袁奎通人学岫l ：毕业沦上 l d p c 玛译码算法研究 l d p c 码的生成矩阵为：g7 = i p c 2 1 c 传输向量f ：g r 5 其中s 为长度为k 的向量，f 为长度为的向量。 传输中的噪声用，t 表示，j = ，+ ”t 根据爿g r ：o ，推出 彳( f + j j ) = 爿( g 7 5 + ，i ) = 爿”= z 其中z 为接收端的向量集合。根据a 与：， 推测i ，从而推测i ：，+ 再，i 中的前k 个b j 【即为信息向量j 。 2 4 经典的译码算法 信逍编码的泽码算法是决定编码性能和应用前景的个重要因素。 尤其是在长码的条件下译码算法的复杂度决定了编码的前途。但是通 常分组码的译码复杂度与码长成指数关系，码长增大到定程度后，复 自 皮n 勺增加l 是不可控制的，无法实际应用。l d p c 码则不同，i _ | = j 于j 校 验矩阵的稀疏性使它存在商效的泽码算法，其译码复杂皮与码长成线 性关系。克服了分组码在长码长时所面临的巨大译码计算复杂度问题， 使长编码分组的应用成为可能而要获得好的编码性能必须采用长的编 码分组。l d p c 码的出现使人们终于获得了一种可以实际应用的分组码。 而且由于其校验矩阵的稀疏- | 生在长的编码分组时，相距很远的信息比 特参与同一校验这使得连续的突发差错对译码的影响不大，编码本身 就具有抗突发差错的特性，不需要交织器的引入，没有因交织器的存在 而可能带来的时延。令人兴奋的是l d p c 码不仅适用于二进制对称信道， 而且适用于任何最佳输入为对称分布的信道，几乎在任何信道上都是“好 码”。 北袁变通人学顽i 二毕业论上 l d p c 码：董玛算注：坪x 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 最初提出的硬判决译码算法n 该算法最有最低的译码复杂度， 但是其性能也是m e s s a g ep a s s i n g 算法中最差的，适用于对性能要求不高 的应用。反之，如果在译码中采用另一个极端一无穷阶量化，即连续性 的算法时，算法成为b p ( b e l i e fp r o p a g a t i o n ) 算法，这种算法相对低 阶量化的m e s s a g ep a s s i n g 算法来说其译码复杂度最高，同时其性能也 是最好的，适用于对性能有较高要求的场合。b p 算法在编码二分图中没 有环坩哺况下是一种渐进最大似然的算法，如果t a n n e r 圈中不存在环， u 三就是环长是无穷大，则这种算法等效于最大似然算法，具有最优的泽 码盹能，当然在码长圃定的h ! 况下，对于适用的码字来浇无环是不可 能的；但是通过增大嫩小环的环长可以提高码字的性能，环长达到一 定的值就可以接近无环时的性能。 g a l l a g c r 曾给出了两种经典l d p c 码的迭代译码算法：硬判决和软 判决算法。硬判决译码算法具有较低的计算复杂度，但性能桐列较差。 软判决译码算法性能较好，但计算复杂度相对较大。若需要两种算法的 折衷可以从m e s s a g ep a s s i l l g 算法中选择有合适信息符号集大小即合适 量化阶数的算法，获得相对较低的计算复杂度，较好的译码性能。 b p 算法的性能和最大似然译码的性能还有一定的差距。但是最大似 然译码算法的复杂度又太高，不能实际实现。为了进一步提高编码的性 能，人们寻找性能上更接近最大似然译码算法的实用算法。 北束交通人学哦j ：毕业论文l o p c 玛佯码算法 i j 究 2 4 1 硬判决算法 硬判决算法：也称为b f 算法。即译码器计算所有的奇偶校验位， 然后对包含在不满足奇偶校验方程中的位进行反转p l 。使用这些新的值， 奇偶校验位重新计算。当某一位同时不满足多个奇偶校验方程时，表明 这一位以较大的概率出错。如果奇偶校验集很小，这种译码过程是合理 的，因为许多情况下奇偶校验集包含一个传输错误或者没有错误。 规则= 进制( 厶f r ，) l d p c 码，它的传送码字长度为三，校验码字 k 度为吖，信息码字长度为足。奇偶校验矩阵中每列包含f ? ，个l ，每行 包含r f ，个1 。非规则l d p c 码，它的每行巾l 的个数或每列t i tl 的个数 赴变化的这样可以川述比特节点和校验1 ，点的收敛，因而能够进一步 改进性能m i 。假设彳= 以，】足l d p c 的码字x 的奇侧校验矩阵：参与到 校验节点n 1 的比特熊用( ，j f ) s f ：1 。，= 1 ) 表示，相似地，参与到比特节 点1 的校验集用m ( ，) s ：i 。，= l 表示。传送序列x = ( x ，) 经过 高斯信道后，相应的二进制硬判决序列为z = ( z ，z ：，气) 。 首先，根按 式( 2 3 ) ，译码器计算所有的校验子的值： 占二1 s 。= 2 。彳。= z ，爿川 ( 2 3 ) ，= 0 如果s = o ，说明接收向量z 是个码字，如果j o 说明接收向量 z 有错误出现。然后。统计每一位不满足奇偶校验方程的次数，对于超 过一定次数占的位进行反转。反转后。重新根据式( 2 3 ) 计算，对超过 一定次数的位再次反转，直到所有的奇偶校验方程都满足运算或者超过 一定的迭代次数为止。这种译码算法是一种迭代算法，参数占称之为门 限，根据t ，d 。，码字最小距离氐。，信噪比s n r 决定占的值的大小1 9 l 。 北京变通凡学颤f ：毕业论文 l d p c 碍详码葬注研亢 2 4 2 软判决算法 软判决算法：也称置信传播( b e l i e fp r o p a g a i i o n ) 算法或和积 ( s u m p r o d u c t ) 算法。这种算法适用于噪声独立的二进制信道模型如 无汜忆的b s c 信道、二进制输入实数输出的高斯信道。l d p c 码的奇偶 校验矩阵用a 表示，a 的大小为：m ，其中，7 = l m ，= 1 。 x 为接收到的码字序列。参与到校验节点，7 i 的比特集l 用 ( ) ； ，：也，= 1 表示。相似地参与到比特节点l 的校验集 l 用 ( d ；似：以，= l ；表示。如果比特集合不包括l ，则用( j j j ) ，表示。这 种算法有两个交互的郎分，叩吼。，和，它们是与奇偶校验矩阼a 中仆 零元索棚关的值，在迭代运算中不盹斤地进行更新，如图2 4 所示。 比特1 7 点校验1 7 点比特节点校验点 oo ， 叮， oo ( a ) 从比特节点到校验节点( b ) 从校验节点到比特节点 图2 4 置信传播( b p ) 算法 数值q ：，是指x 中的比特1 有值为x 的概率值( x 为。或1 ) ，通过除 了校验节点m 以外的其它与此比特节点相关的校验节点上的信息计算。 1 7 北未z 迂凡学碳i ：毕业j 芑上 l d p c 码悼玛算江讲在 如果y 中的比特l 固定在值工，其它比特通过概率 g 。，三( ) f 有一 个独立分布数值，：为满足此校验节点，7 i 的概率值，如图2 4 所示。如 果由矩阵a 定义的双向图不包含循环，在一定的迭代次数后，b p 算法 将产尘所有比特节点的精确的后验概率当然，完全避免循环是不可能 的，在设计奇偶校验矩阵时，总是尽量避免短环的存在【6 】。 b p 译码过程如下【5 】= ( 1 ) 初始化：设p ? = p ( = o ) ( 比特是。的先验概率) p 卜p ( = 1 ) = l p ? 。如果噪声的变化是可知的( 例如如果信道是 二进制输入实数输出的高j 圻信道) 那么初始化为适当的归一化概率。 对于( f f ) 爿。，= 1 ，变量f ，：，和“被初始化为值p ? 和p j 。 ( 2 ) 水平迭代：在水平迭代算法i 1 ，贯穿所有的梭验节点1 1 1 ，汁 算剥+ 于缚一个，e ( ，7 j ) 的两种概牢。根据爿x = z 。首先圪足当= o 时 所观察到的他= 。的概率，假设其它的比特 ：， 通过( 口：。“ 有一个 独立的分椰，如式( 2 4 ) 定义。 7 0 = 只引西= o ，“：f 。加，2 ) 啪兀鳓( 2 舢 ，e 帅i n ，钍( ，f ) 、， 其次，0 是当- = l 时观察到的值z 。的概率，由式( 2 5 ) 定义： 7 0 = 爿。l 西= 1 ，“：，。三( ，2 ) ) ) n 粥( 2 鼬 “1 钍( j i i ) u ，。d 条件概率的值或者为o ，或者为1 ，取决于是否观察到的值气与假设 的值和( 而j 匹配。 在实际的运算中，可以使用一种简便算法，先计算 阮；巩一z ， ( 2 6 ) 北京至通人学坝l 一毕业：圭上 l d p c 鹳浮玛算注研究 = ( 一1 ) 铂兀瓴 ( 2 _ 7 ) ，e ( 删) 、， 从下面的恒等式( 2 8 ) 和( 2 9 ) 万，；。，曼一0 ， ( 2 8 ) ，0 + ! ，= 1 ( 2 9 ) 得到 噶= ( 1 + 万，j ，) 2 ( 2 1 0 ) ，：，= ( 1 一万，：，) 2 ( 2 1 1 ) ( 3 ) 垂直迭代：利用瑞和呓，的值，更新叮：，和g i ，的值。对于比特 节点中的繇个l ，计算 9 ：，= p ? 兀鼎( 2 1 2 ) 口：，= ，p f 兀，t ， e ( ) 其巾，口。，满足口：，+ 以，= l 。那么，“伪后验概率” g ? = 口腐兀，0 ，l ，( ，) ( 2 1 3 ) q ? 和口抽值为 ( 2 1 4 ) 纠= 爿兀：，( 2 1 1 5 ) ，j j e ，( ，) 这些值用于判定假设的译码主，这些值是否稳定决定着何时译码算 法中止。 ( 4 ) 译码：如果g o 5 ，那么判定暑为1 ，否则为o 。如果满足衙= o ( 模2 ) 或者达到了迭代的最大次数，则停止迭代运算，否则继续迭代。 北京交通人学坝i ：毕业论二(l d p c 玛译玛葬注研究 2 4 3 改进的软判决算法 2 4 3 1 高吞吐量l d p c 译码结构 e n 9 1 i n g y e o 提出了两种译码结构和相应的串行结构l d p c 译码器设 计，可以应用到随机生成的或者在伽罗华域上利用几何元素特性而生成 的码字上【2 0 1 。两种译码设计都具有低的计算量要求。原来的并行译码设 计有一个非常大的存毒嚣要求。它取决于双向图中度的数目。然而，交错 的使_ 玎b p 算法估计的译码设计。具有减少内存需求的特点它仅决定 于此分组t 0 比特数目，因此，这种译码结构具有较高的吞吐能力。交 锵泽码没汁的i 占本恩怨是：每一个比特节点n ，仅与单一的信息q f ( 女) 有关，gh ( 膏) 在第k 次迭代时被广播到激活的校验节点s ( k j 的子集 上去。姆一信息q h ( d ) 被输入的l l r 初始化其中，= ，根 据公式( 2 1 6 ) 更新。 q ，( 七) ：q 。( 尼一1 ) + 尺。，。 2 1 6 m c i s ( ，) n ，( ” j l d p c 码的b p 译码算法由于双向图的结构面临复杂的相互连接和 非常大的内存需求的挑战，而交错的译码设计使内存需求减少到仅一个 码长的大小与双向图中度的数目无关。在限制迭代次数的情况下，交 错的译码算法优于并行译码算法。 2 4 3 2l d p c 码的改进w b f 算法 j u n t a n z h a n g 提出了一种改进w b f ( w e i 业t e db i t - f l i p p i n g ) 算法，通 过校验约束信息和每一比特的内在信息，使得性能得到改善 2 ”。改进的 北京变通人学顾i ：毕业论上l d p c 码译玛算注讲究 w b f 算法在性能，复杂度和速度方面提供了一种好的折衷。 设接收到码字的代数值序列为y = ( y ，托，h ) ，”= ，相应 的二进制硬判决序列为z = ( j ，z ：，知) 。参与到校验节点m 的比特集用 n ( j 7 f ) = h 。= l 表示，相似地，参与到比特节点n 的校验集用 m ( ，1 ) = ：h 。= 1 表示。 在标准w b f 算法中，译码的迭代过程如下【2 2 i ： ( 1 ) ，7 ：】，2 ，吖 计算校验子 ( 2 1 7 ) s m = z l h j ，j = i ( 2 ) j = l ，2 ，计算 b ：( 2 妒1 m ，。 2 18 e ，i ) ( 3 ) 反转比特：其中，l _ a r g n l a x i 如s 厄，即取巨，为最大 值寸的”。 重复步骤( 1 ) 一( 3 ) ，直到所有的奇偶校验方程都满足或者达到尼 大的迭代次数时停止运算。 在改进的w b f 算法中， b ：( 2 川川。嘶l 弘i 2 t 1 9 n ，e ，( ，1 ) 对于给定的l d p c 码字，在给定s n r 下的最优的口可以定义为在此 s n r 下，改进w b f 算法产生最小b e r 的值。在每一s n r 下的口的最 优值可以通过仿真确定。 北京交通凡掌幔i ：毕业论文l d p c 码洋玛算压讲究 2 4 3 3 归一化b p - b a s e d 和补偿b p - b a s e d 算法 b p 算法可以通过b p - b a s e d 算法得到简化，b p - b a s e d 算法在实现上降 低了译码的复杂度，但也降低了译码性能。j i n 曲u c h e n 提出了采用归一 化的近似最佳通用b p b a s o d 译码算法，即n o 玎1 1 a l i z e db p b a s e d 算法和通 过降低可靠性值来改善外信息精度的o 脏e tb p - b a s e d 算法吲。应用密度 演进去获得规一化b p _ b a s e d 算法和补偿b p - b a s e d 算法的门限。结果表明， 对于这两种以b p 为基础的算法，通过选择合适的参数。性能会非常接 近b p 算法。 2 5 小结 水章概要介绍了l d p c 码的定义、两种常见表示方法：h 矩阵表示 和双向图表示，详细闸述了碰判决b f 译码算法、软判决b p 译码算法的 原理。碘判决译码算法具有较低的计算复杂度但译码性能柏剥较差。 软判决译码算法性能较好，但具有较高的计算复杂度。另外介绍了三 种改进的软判决译码算法，它们分别从计算复杂度和译码性能的某一方 面进行改善。如何达到在不改变译码复杂度的前提下，进行误码性能的 改善，是本文的主要研究问题。 北京支通人学填l ：毕业i 2 上 l d p c 婷1 辛玛算注 i 。： 第3 章l d p c 码译码算法分析 为了研究l d p c 码译码算法的性能，对b p 译码算法进行了编程仿 真。仿真中采用的信道是二进制输入的加性高斯白噪声信道，调制方式 是基带的b p s k 调制。要想在仿真中获得较低的误比特率，需要大量的 数据帧即需要花费大量的运行时间，尤其在码长较长时，运行时间更 是难以接受，因此只对一些选定的码长不是太长的情况进行了模拟。而 在仿真中这种码k 选择上的限制使得性能结采较l d p c 码所能够达到的 性能指标有一定的差距。 3 1 l d p c 码的仿真 3 1 1h 矩阵的生成 仿真中所用的校验矩阵考虑到编程上的简单性使用随机构造的方 法生成，每一列的重量大致相同，每一行也大致有相同的重量。由于长 度为4 的环的消除在编程实现上较为困难。而且在码长不够长时没有 长为4 的环的校验矩阵不一定存在，因此构造的校验矩阵并不保证没有 短长度的环。 步骤如下： ( 1 ) 产生最初的奇偶校验矩阵 两种方法： e v e n c 0 1 方法：每列上随机选择地放置固定数目的l ，约束条件是这 北京交通人学碗i ：毕业论上 l d p c 码谭玛算注研究 些l 在不同的行中。 e v e n b o t h 方法：在每列中放置固定数目的l ，但是每行中l 的数目大 致相同。 ( 2 ) 在只有一个l 或者没有1 的行中增加l ，l 的位置随机决定。 因为只有一个l 或者没有1 的行是冗余的，要努力避免冗余的情况。 ( 3 ) 如果最初的奇偶校验矩阵中，每列中1 的数目是偶数，就增加 l 以避免行相加为o 的情况，增加1 的位置随机选择。目的是使h 矩阵 达到满秩。 ( 4 ) 消除两列中的某两行中都存在l 的情况，减少长度为4 的短环 把其中的个1 移到这个列的其它位忍，直到所有| 1 列邮满足为止，或 糟1 0 次尝试来解决短环问题失败时为止。 通过以上4 种操作，最终使得像行和每列中i 的数曰是大致相同。 3 1 2 h 矩阵到g 矩阵的转换 一个码字x 分成 ，比特校验位用c 表示，足比特信息位，用s 表 示，假设码字的信息位在码字的尾部。h 矩阵分成m m 的矩1 5 车a 和 m 足的矩阵b ，矩阵a 位于i i 的前列。根据h x = 0 则彳c + 凰= 0 。 如果a 是非奇异的，则c = 爿。丑s 三种方法计算c ： d e n s e 方法：先计算爿b ，以d e n s e 格式存储然后再与s 相乘，获 得校验比特。此时的g 矩阵为彳。b ，以d e n s e 格式存到一个文件中。 m i x e d 方法：先计算a ，以d e n s e 格式存储，矩阵b 以s p a r s e 格式 存储，编码时