（通信与信息系统专业论文）衰落信道下ldpc码的设计和优化分析.pdf

摘要 低密度奇偶校验码是一种优秀的线性分组奇偶校验码，可以以距离香农限 非常近的速率传输。 本文研究在衰落信道下l d p c 码的设计与优化分析方法。以b i a w g n 信道为 基础，先研究l d p c 码在该基带信道下的性能特点，得出规则l d p c 码在较短帧 就具有优秀性能，不规则l d p c 码要在l 矿才具有优异性能的结论。并得知规则 l d p c 码的性能优化主要在于h 矩阵的设计，而不规则l d p c 码的优化则在于度 的分布对的设计与优化。针对h 矩阵的设计，作者提出了两种新的设计方法： e v e n b o t h 和e v e n c o l ，并发现e v e n b o t h 方式的性能更加突出，该结论在非相关 瑞利衰落信道下依旧有效。针对度的分布对的设计，作者采用了密度进化的方 法，通过大量仿真，找出了一系列好的分布对，并研究了密度进化方法在非相 关瑞利衰落信道下具有可行性，该度的分布对在非相关瑞利衰落信道下仍具有 优秀的性能。本文对规则l d p c 码和不规则l d p c 码，卷积码，t u r b o 码进行了 性能比较，并给出了结论。 本文第一章阐述了规则和不规则l d p c 码的基本原理，包括其发展历史， 奇偶校验矩阵h ，常规编码方案和特殊矩阵的快速编码方案。第二章论述了古 典译码方式和现代的利用消息传递的信度传播译码算法，以及和积算法在后者 中的运用。第三章从以门限值来判定码字性能的角度出发，引入了一种新的 l d p c 码的优化方法一密度进化方法，进而分析了不规则i d p c 码的度的分 布对的优化原理。第四章论证密度进化方法在非相关的瑞利衰落信道下的可行 性，以及密度进化算法在该信道下的应用。第五章为仿真数据分析部分，给出 了仿真系统的流程图和模块详解，以及相关数据曲线和表格。文章末尾指出了 l d p c 码广泛的应用前景和下一步工作方向。 关键词：l d p c 码，香农限，信度传播译码，和积算法，门限值，密度进化 a b s t r a c t 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 si sag o o dl i n e rb l o c kc o d e s ，w h i c h p e r f o r ma tar a t ee x t r e m e l yc l o s et ot h es h a n n o nc a p a c i t y i t se r r o r - c o r r e c t i n ga b i l i t y h a st i g h tc o n n e c t i o nw i t ht h eb l o c kl e n g t ha n dc o n s t r u c t i o nw a y t h i st h e s i si sf o c u so nt h ed e s i g na n do p t i m i z a t i o no fl d p cc o d e si nn o n - r e l a t e dr a y l e i g hf a d i n gc h a n n e l b a s e do nb i a w g n c h a n n d ，i tw a sf o u n dt h e r e g u l a rl d p cc o d e sh a sg o o dp e r f o r m a n c ei ns h o r t e rb l o c kl e n g t ha n dt h ei r r e g u l a ri n l o n g e rb l o c kl e n g t h hm a t r i xi se s s e n t i a lt or e g u l a rl d p cc o d e s ，a n dd i s t r i b u t i o no f d e g r e ei se s s e n t i a lt oi r r e g u l a ro n e s t h i st h e s i sa n a l y s e st h eb a s i ct h e o r yo fl d p cc o d e sf i r s t l y , i n c l u d i n gi t sh i s t o r y , t h ep a r i t yc h e e km a t r i xh ，b i p a r t i t eg r a p h ，o r d i n a r ye n c o d ea n df a s t e re n c o d i n gs k i l l s f o rs o m e s p e c i a lh s e c o n d l y ，c l a s s i cd e c o d ea n dm o d e m b e l i e fp r o p a g a t i o n a l g o r i t h mu s i n gm e s s a g e - p a s s i n gm e t h o d i sd i s c u s s e d i nt h et h i r dp a r t ，f r o mt h ep o i n t o ft h r e s h o l d ，d e n s i t ye v o l u t i o nm e t h o da n dt h eo p t i m i z a t i o no fd e g r e ed i s t r i b u t i o na r e d i s c u s s e d i nt h ef o u r t hp a r t ，t h ef e a s i b i l i t yo fd e n s i t ye v o l u t i o nm e t h o di nt h el l o n r e l a t e dr a y l e i g hf a d i n gc h a n n e li se x p a t i a t e d i nt h ef i f t hp a r t , s i m u l a t i o nr e s u l t sa r e a n a l y s e d i nt h ee n do ft h i sp a p e r ，s o m ea p p l i c a t i o no b s t a c l e st h a tm u s tb eo v e r c o m e i no u rf u t u r ew o r ka l ep r e s e n t e d k e yw o r d s ：l d p cc o d e s ，s h a n n o nc a p a c i t y ，b e l i e fp r o p a g a t i o nd e c o d i n g , s u m p r o d u c ta l g o r i t h m ，t h r e s h o l d ，d e n s i t ye v o l u t i o n 重庆邮电学院硕士论文 1 1 引入 第一章绪论 1 9 4 8 年，美国贝尔实验室的c l a u d ee s h a n n o n 在贝尔技术杂志上发表了题 为通信的数学理论的论文。s h a n n o n 在该文中指出，任意的通信信道都有 一个参数c ，称之为信道容量，如果通信系统所要求的传输速率r 小于c ，则 存在一种编码方法，当码长n 充分长译码采用最大似然译码时，系统的差错概 率可以达到任意小，这就是著名的信道编码定理。该理论的提出，标志着现代 信息论与编码理论这一学科的诞生。 虽然s h a n n o n 给出的仅仅是一个编码的存在性定理，但却开创了信道编码 理论这一富有活力的研究领域。同时我们看到，s h a n n o n 确实给出实现信息可 靠传输的方向，但此定理仅仅是一个存在性定理，s h a n n o n 并没有给出如何构 造这种码型的具体方法，即定理仅是一非构造性定理。自从1 9 4 8 年以来编码理 论家一直在找s h a n n o n 所说的“好码，但由于计算能力等诸多的因素使得进展 甚微，直到1 9 9 3 年的t u r b o 码的出现才在一定程度上回答了s h a n n o n4 0 多年 前提出的问题。 迄今，纠错码已发展了5 0 多年，科学家们致力于研究各种具有不同优点的 纠错码，并研究其相应的编、译码方法。例如，1 9 5 0 年h a m m i n g 发明了h a m m i n g 码，h a m m i n g 码是一种能纠正一个错误的完备线性分组码：此后又出现了b c h 码的编译码方法，b c h 码是循环码的一个子类，具有较好的码距特性；同时，还 出现了卷积码及序列译码方法，卷积码不同于上面提到的分组码，它是一类非 分组码；并且，通过理论分析给出了纠错码的基本码限等。在译码算法方面出 现了门限译码、迭代译码、软判决译码、卷积码的维特比译码。特别是维特比 译码的出现为纠错码的实用化前进了一大步。 1 9 6 2 年g a l l a g e r 提出了一种新的线性分组码低密度奇偶校验码 ( l o wd e n s i t yp a r i t yc h e c kc o d e s ，在后文中均简称l d p c 码) 【l 】，在当时就提 出了用硬判决的迭代译码的方法来进行译码，但是由于当时计算机仿真水平的 限制，这种码字的性能没有得到完全的体现。当时他主要从理论的角度来分析 l d p c 码的性能，如码的重量分布、译码错误概率和不可检测概率的计算、还 有信道的模型化等。 随着九十年代初，应用迭代译码的t u r b o 码表现出优秀的性能，科学 家开始重薪审视l d p c 码，发现它可以比t u r b o 码更接近香农限。1 9 9 6 年 d m a c k a y 从现代编码理论观点出发，证明利用迭代译码的l d p c 码具有逼近 垩鏖坚皇兰堕堡主堡茎 香农限的性能【2 1 。不规则l d p c 码甚至可以距离香农限只有0 0 0 4 5 d b u j 。这为 无数从事现代高效纠错编码研究的科研人员指明了前进的方向，掀起了一轮新 的研究l d p c 码的热潮。1 9 9 8 年由m a c k a y 和s p i e l m a n 提出了l d p c 码的不 规则编码方式【4 j ，这更是l d p c 码的发展进程中所跨出的非常重要的一大进步。 针对于不规则l d p c 码的复杂性，r i c h a r d s o n 和u r b a n k e 开创了利用软判决 的迭代译码算法一b p ( b e l i e f p r o p a g a t i o n ) 算法，该算法从人工智能学科中 发展而来，与和积算法完美结合，使得高效准确的l d p c 码译码成为现实。而 理论研究方面，密度进化算法则是绝对的亮点。密度进化是现代编码理论中分 析纠错码渐进性能的新方法，计算精确的门限值，从而寻找优秀的度的分布对。 这为l d p c 码的优化设计指明了新的方向。 1 2 什么是l d p c 码 1 2 1l d p c 码的历史 1 1 9 6 3 年，g a l l a g e r 发现的l d p c 码被称作古典码型：规则 l d p c 。 2 1 9 9 8 年，m a c k a ya n ds p i e l m a n 发明了不规则的l d p c 。 3 r i c h a r d s o na n du r b a n k e 开创了用译码分析设计码型的方法。 针对l d p c 码的概述，本文对l d p c 的原理、编码、译码阐述路线都是先讲规 则的l d p c 码，然后是不规则的情况。 1 2 2 校验矩阵h 通常，一种线性分组码是由其生成矩阵表示。不同于其它码型，l p d c 码 是由其校验矩阵表示的。作为一种典型的奇偶校验码，它的h 矩阵具有非常稀 疏的形式：绝大多数的矩阵元素都是0 ，只有很少数量的l 。规则的l d p c 码可 以用( n ，j ，k ) 描述，1 1 表示分组长度，j 表示h 中每一列中l 的个数，k 表示h 中每一行中l 的个数。 根据线性分组码的性质，知道了h 矩阵，可以推知其生成矩阵g 。可以看 出，l d p c 码的生成矩阵g 没有简洁、规律明显的表达形式。观察h 的意义， 矩阵的每一行是一个校验方程：c h e c k ；矩阵的每一列表示一个变量b “受到哪 些c h e c k 的约束。图1 1 的例子中，第一行即为：为o x 6 e ) x 7o x s = 0 ，0 表示 模2 加。所以k 的意义是一个c h e c k 约束k 个变量v a r i a b l e 。第一列表示v a r i a b l e x , 重庆邮电学院硕士论文 受到c h e c k 2 、c h e c k 5 、c h e c k 7 的约束，所以j 的意义是每个变量b i t 受到j 个c h e c k 的约束。 0 堙上q 旦j ! - 上q 殳业 - l l00l0 00 00 01 o o ol0 0 00l l l0 1010 001 100100 h 2 j16l0000l00l0 0 扫o1 10 0010 0l lo0l l0l0 00 0 0 0 o o00l0l0oll 0i1000 00i 100 c h e c k l l 玉所受约束关系 图i 1 ( 1 2 ，3 ，4 ) l d p c 的校验矩阵 1 2 3 二部图b i p a r t t i eg r a p h s 为了清晰地反映变量点与函数点的关系，九十年代中期，科学家们开始用 因子图来表示l d p c 码。根据代数学中的分布法则，任何一个多变量函数 g ( 而，x 2 ，而) 都可转化为因子函数的乘积，即因式分解： g ( 而，而，而) ；无( ) 厶( ) ( ) ( 1 1 ) 其中每个因式的变量是集合“，x 2 ，) 的一个子集。用图来表示，圆圈代表 变量点r a t a b l en o d e s ，方框代表因子函数，则 删表示饰) 表不，i 引 规则的l d p c 码的每个变量b “都受j 个c h e c k 的约束，因此每个变量点应 该连接j 个校验点。每个校验方程有k 个变量，因此每个校验点应与k 个变量 点相连。正如图1 2 所示，由于l d p c 码是一种线性码，使得它的因子图一边 为变量点，一边为校验点，故l d p c 码的因子图表示有专用的定义：二部图 b i p a r t t i eg r a p h s 。每个点发出的边的个数称为这个点的度。 重庆邮电学院硕士论文 c h e c k n o d e s ：m v a r i a b l e n o d e s ：r l 图1 2( 1 2 ，3 ，4 ) l d p c 的二部图 已知分组长度1 1 ，如何确定需要多少个校验方程呢? 从二部图看，所有变 量点发出的边的条数等于所有校验点接受的边的条数，即t ，= m k 。因此校验 方程的个数，也是h 的行数目m - - m - 犁。 。 疗 1 2 4 不规则l d p c 码的基本表示 顾名思义，不规则码的每个变量点所受约束的个数不一样，每个校验方程 约束的变量点的个数也是不一样的。这就使得二部图中的点所连的线的数量不 是完全一样的。 为什么这种不规则的码型在码长很大时，性能要比规则l d p c 好，甚至比 t u r b o 码还要好很多昵? 这种现象称作“波浪效应 ( w a v ee f f e c t ) 【5 1 。一部分点 的约束度高，使得译码相对快速得多，因此可以为其它低约束度点提供更准确 的信息，最终使得所有点的译码速度加快。这跟我国的一项基本国策居然是一 样的原理：少部分人先富起来，带动大多数人后富起来，最终实现共同富裕! 对于不规则的情况，h 矩阵中每行每列l 的个数都不再固定，因此( n j j ( ) 的表示方法失去了意义；为了准确的表达一个非规则的码型，我们引入了新的 表达式： d - v a ( x ) = 。 f 1 2 正 p ( x ) = 乃x 。 ( 1 2 ) 户2 其中，允( x ) 表示变量点的度的分布，p ( x ) 表示校验点的度的分布。很明显， a ( 1 ) = l ，p ( 1 ) = l 。五( n ) 表示从度为i + 1 ( j + 1 ) 的变量点( 校验点) 发出 的边占所有边的比例。 例如，对于规则的( n ，3 ，6 ) l d p c ，a ( x ) = x 2 ，p ( x ) = x 5 已知一个 重庆邮电学院硕士论文 度的分布对( 旯，p ) 后，可以确定一系列码字集合c ”( 名，户) ，并且 僚 聃小等小橼。 1 3l d p c 码的编码原理 1 3 1 编码 ( 1 3 ) ( 1 4 ) 1 常规编码 得到校验矩阵h 后，就得到了相应的生成矩阵g 。 信息源为s ，则编码生成的码字u = s g 。 这种编码方式是由最基本的原理推得的。当分组长度为n 时，编码复杂度 为d f 刀2l ，在移动通信中这种传播时延对于语音通信是不能忍受的。计算复杂 、， 度也会使得存储器的数量过多，影响通信成本。为了简化计算，数学家们设计 了很多简便算法。但是这些算法要求校验矩阵h 具有相应的特殊形式。因此在 仿真中，必须先决定选用那种方式进行编码，再根据相应的方式来构造h 。 2 、具有系统形式的h 矩阵的快速编码 已知一个码字u ，奇偶校验矩阵h 位为m 。编码前的信息源为s 。假设 编码后s 位于u 的后部，校验位c 位于u 的开头。即u = c ls 】分解校验矩阵 h ，使之具有形式：m = 4 1 曰】，其中a 是一个村m 的矩阵，b 是一个肘( n - m ) 的矩阵。因此 u t t r = 0 专a c + b s = 0 ( 1 5 ) 由此可以推出c = a q b s 因此只要a 为可逆矩阵，就可以由此得到校验位： 重庆邮电学院硕士论文 这种方式要求h 矩阵具有系统形式。然而l d p c 码的稀疏属性使得这种系 统形式很难达到。因为系统形式要求有一个m m 的单位矩阵，这样使得h 的 其余部分就必须承担剩下的所有的l ，那部分就会显得很密集，而不能达到h 所要求得稀疏的特点。下面我们介绍一种可以快速编码的h ，这种h 矩阵容易 实现，并且编码时间与分组长度呈线性，所达到的性能与常规编码达到的性能 无异，是具有实际操作意义的一种l d p c 码的编码方案。 3 、 具有类似一f 。三角形式的h 的快速编码 图1 3 解释了可以快速编码的奇偶校验矩阵的常见形式，具有类似于下三 角的分布，并介绍了编码的步骤，图中r i 厶表示信息源b i t ，t k 坩如州，是由校 验方程计算出来的校验b i t ，第m 个校验方程计算第k + 脚个b i t 。知砒+ 1 知等 于c 一。b t m o d 2 ，其中r = ( 如一m 。) 2 ，c 。1 是c 的模二代数逆矩阵。这个过程需 要( 一m 。) f ，次计算，f ，即矩阵的行重。c 一可以由m 。2 b i t 的存储器存储。乘 积厨需要丝次计算，再乘以c 。1 需要丝2 次计算。 当奇偶校验矩阵具有类似于下三角形式的分布，虽然要计算所有的收个校 验b i t ，但是由于个数少，所以只需要非常稀疏的计算。当丝小到与万相等 时，l d p c 码便可以线性时间编码。 h= 图1 3 可快速编码的奇偶校验矩阵 重庆邮电学院硕士论文 图1 4 快速编码与常规编码的性能比较 图1 4 表明，快速编码与常规编码的性能是一样的。图中横轴为信噪比， 纵轴为误码率。左图为常规编码的情况，右图为快速编码的情况。 1 4规则l d p c 码的古典设计方法 l d p c 码在1 9 6 3 年就被提出来了，其研究主要是理论上，通过界定其最大 码字距离来检验它的纠错性能。而码字的设计，也主要是针对其校验矩阵h 进 行的。 1 4 1 设计l d p c 码的校验矩阵h 由于l d p c 码是由校验矩阵h 为特征的，不同的h 对应了不同的码字集合。 因此，l p d c 码的编码必须要先设计h 。在根据h 得到相应的生成矩阵g 。 1 、h 的设计要求 规则l d p c 码的设计要求先确定参数j 、k 。目前所知的性能最好的规则 l d p c 是( 3 ，6 ) 码。确定j , k 的值后，根据分组长度n 确定校验方程的个数m 。 系统首先生成一个m 的全o 矩阵，再随机的将每行的k 个o 换成l ，每列的 j 个0 换成l 。在随机置1 的过程中，必须避免两种情况的出现【6 】： ( 1 ) 长为4 的环 当h 矩阵中出现长为4 的环时，对应的二部图如图1 5 所示。这种结构会 导致消息在两组点间反复传递，难以更新，是必须清除的一种结构。理论分析 上来说，最小环长度为6 的情况下码的最小距离为4 。而随机构造的码的最小 距离是可以随着分组长度的增加而线性增长的。 重庆邮电学院硕士论文 01 町f t1d 乒拭【0 c h e c k s b i t s 图1 5h 矩阵中长为4 的环及对应的二部图 ( 2 ) 变量点连接的校验方程过于集中 当变量点连接的校验方程过于集中时，常常导致l d p c 码的错误地板发生。 例如，图1 6 为变量点的重量为3 ，即二部图的下部分。其中三个带阴影的变量 点一共只连接了5 个校验方程。除了最右边的校验方程，其它4 个校验方程中， 每个都连接了两个阴影点。因此，当这三个阴影b i t 出错时，左边4 个校验方程 都不能检测到错误的存在。当分组长度增大时，出现这种拓扑结构的可能性就 会减少。 c h e c k s b i t s 图1 6 一一 o oooo o 导致错误地板的拓扑结构 2 、不规则l d p c 码的h 设计 对于规则的l d p c 码，只要保证每行每列的度样就行了，但是，不规则 l d p c 码是由( 旯。p ) 决定的。最开始发现的不规则l d p c 码，变量点和校验 点的度都不是均匀的，但是实验结构表明，双边不均匀并非最佳方案。我们总 是选择让变量点度的变化很大，而校验点的度一般都比较均匀，而且度比较小。 约束度大的变量点称作优先点。在译码过程中，优先点被正确译码的概率是最 8 重庆邮电学院硕士论文 大的。如何分配这些优先点，让哪些校验点连接更多的优先点，是科学家们正 在努力研究的课题。目前已有的置l 方式有三种：泊松方式、次泊松方式、超 泊松方式。 p o i s s o n 完全随机控制l 的位置。 s u p e r o p o i s s o n ：每行的较重的列的分布比p o i s s o n 分布变化更大。 s u b p o i s s o n 每行的较重的列的分布比p o i s s o n 分布变化更小。 实验结果表示，通常s u b - p o i s s o n 方式不如p o i s s o n 方式，s u p c r - p o i s s o n 方 式要比p o i s s o n 方式好很多。 重庆邮电学院硕士论文 第二章l d p o 码的译码原理 2 119 6 3 年，古典译码方案 最大似然概率译码无疑是二进制信道的最佳译码方案，译码错误率也是使 用最大似然概率译码来分析的。然而在实际应用中，尤其是当码长较大时，这 种方案需要的硬件复杂度，存储器个数和时延是难以承受的。如果稍微较低对 误码率的要求，实际应用的可操作性却可大大增强的方案是非常可取的。 作为l d p c 码的首创者，g a u a g c r 与1 9 6 3 年提出了两种古典的译码方案， 前者基于硬判决，后者基于软判决。 2 1 1 硬判决方案 译码器输入为硬判决获得的初始值l 或0 ，译码器计算所有的校验矩阵，如 果某个b i t 参与的校验方程出现了错误，并且数目超过一个预定值，就改变这个 b i t 的值。计算完整个分组的所有b i t 后，再用改变后的值进行下一轮计算，直 到所有的校验方程都满足为止。 如果校验方程的监督b i t 较少，那么这个方案很可行，因为大多数校验方程 就只会含有一个或没有传输错误。因此，当一个b i t 参与的大多方程都出错，那 么这个b i t 错误的可能性非常大。 2 1 2 软判决方案 软判决方案中，译码器计算值是某一个b i t 为0 或者为1 的概率。码字集 合为s ，发送端序列为 工 ，接受到的序列为 少 ，我们希望找到第d 个b i t 为 1 的概率p r 【吻= 11 y ，s l ，为。的概率为e r x , = 1 1 y ，s 】= 1 - - p r x d = li j ， ，硼。 阐述其算法时，先引入一个g a l l a g e r 的定理： 定理1 代表经过信道传输后，第d 个b i t 为1 的初始概率( 跟信道本身性能 相关) 。对于( n ，j ，k ) 的规则l d p c ，岛代表在第，个校验方程中第，个校验b i t 为l 的概率，那么 装p r x d 黼1 s = 警科焉k - i 高 1 亿l ， = i j ， ，】尼甘il 一丌一2 名) l 为了证明这个定理，需要如下的引理： 重庆邮电学院硕士论文 引理1 一个独立的m 个b i t 的序列，第| 个b i t 为1 的概率为0 ，则整个序列 中出现偶数个1 的概率：旦华，出现奇数个l 的概率：三毕。 这个引理是已为编码理论的基础，所以直接引用，不予证明。 p r x d = li y ，s 】= p r x a = 1 】 砀= 1 时满足j 个校验方程的概率 = 只兀 勤= l 时满足第i 个校验方程的概率 = 局- n 第i 个校验方程的其它k l 变量还有奇数个1 的概率 嘶斟皿字1 汜2 ， 同理：p r 【砀= 。l y ，s 】_ = ( 1 一易，密l 旦学l c 2 3 ) i l i i ( 2 2 ) ( 2 3 ) 两式相除，定理得证。 通过定理i ，我们可以得到每个b i t 的为1 或为0 的相对值，如果比值大于 l ，在本次迭代中判定为o ；如果比值小于l ，则判定为l 。经此一次迭代，分 组中每个b i t 的概率值都会得到刷新，得到 x 。用这个序列与h 相乘，如果 为0 ，则译码成功。系统设定最大迭代次数，如果超过这个次数还不成功，则 放弃继续译码。 g a l l a g e r 为了表示这种迭代译码思想，采用了如图2 1 所示的树形图。图 中d 点表示译码起始点。为了计算d 点的条件概率，需要计算j 个校验方程。 图中的实线表示的正是校验方程。第一层的每条横线有k 一1 个点，代表这个校 验方程的其它变量。 是一lo t h e r d t 癣a 知：丘鹰c ， 秘洒鼬。区曩吐 d 图2 1 迭代译码的树形图 矗 重庆邮电学院硕士论文 2 2 现代译码方案 2 2 1 规则l d p c 的b p 算法 l d p c 码发展到9 0 年代，出现了新的表示方式：因子图表示，即二部图。 并且通过引用人工智能中的b p 算法到l d p c 码中来，成为l d p c 码的现代译 码方案。 b p ：b e l i e f - p r o p a g a t i o n ，信度传播算法，是与二部图紧密结合的。边上 传递的消息叫做m e s s a g e ，分c h e c kt ov a r i a b l e 和v a r i a b l et oc h e c k 两种，因此 l d p c 码的译码也常常称作m e s s a g e - p a s s i n g 方法。 从左到右的边传递的m e s s a g e 是：通过除 了第m 个的其它j - 1 个校验方程得到的第1 1 个变量点为l ( 或o ) 的概率：q k ( q o ) 从右到左的边传递的m e s s a g e 是：第n 个 变量点为l ( 或o ) 时满足第m 个校验方 程的概率：( 最) 图2 2b p 算法与二部图紧密结合 b p 算法延续了古典算法的迭代思想，它的改进在于：在计算变量点满足校 验方程的概率时，不再采用奇数或偶数个l 的方式，而是运用了全概率公式。 这样的改进在于：当分组很大，通常为1 0 7 时，不可排除的总会有某个b i t 出错， 而它所有的校验方程都产生了偶数个错误，使得译码无效。全概率公式是不会 出现这种问题的。 b p 算法的译码步骤： 重庆邮电学院硕士论文 ( 1 ) 初始化 将矗的似然值赋给q k 和q ：。 例如，在加性白色高斯噪声信道a w g n 下，似然值分别为： 小彳t + 唧( 制小卜小 ( 2 ) 从校验点到变量点：c h e c kt ov a f f a b l e 假设第m 个校验方程为x 2 ( gx 3x s = 0 。计算而= 0 时满足这个校验方程的 概率如： 如= p r x 2 ( g x 3o 黾= 0 1 x 2 = o ，墨= o ，x 5 - o g ：3 q 0 5 + p r 恐o x 3 0 黾= o l x 2 = o ，而= o ，毛= l 酲3 靠5 + p r x z ( g x 3o x 5 = o lx 2 = o ，x 3 = l ，x s - - o 3 靠s + p r x 2 ( g x 3 ( g x 5 = o lx 2 = o ，x 3 = l ，x s = 1 ) 以3 q ts ( 2 4 ) 这是典型的全概率计算方法。 其中的条件概率p r ，如果满足校验方程则为l ，不满足为0 同理，我们也可以计算如。 因此，我们可以得到更一般化的表达式： 患= ，p r 满足校验mi 矗= o ，i x , ：( 脚) ，n 如 一e ( 一灿 一毫( 卅卜 = 。p r 满足校验m i = l ， 勺：( 掰) 万 ，兀彩 ( 2 5 ) h e ( 州 ( “卜 ( 3 ) 从变量点到校验点：v a r i a b l e t oc h e e k 这一步跟古典方式是相同的，都是计算某一b i t 取l 或0 时满足所有校 验方程的概率。 dq 册 册 似 膨 m 州 w 幺厶兀兀 z z = = 如 靠 重庆邮电学院硕士论文 ：归一化参数，使口彻0 下i = 1 。 最后得到后验概率： 戮= z 兀以：m e m ( n ) q ：= 一1 - i ：m m ( 玎) ( 4 ) 判决 z 玩，则判定矗= o 。 直到x 日r = 0 ，否则转到第二个步骤。 2 2 2 和积算法 ( 2 7 ) 和积算法与因子图是紧密结合的口1 。当一个函数因式分解并用边缘函数表 示后，求解过程可以相应的变为各个变量的和积。这本身是一个相当复杂的领 域，它可以应用到几乎所有的分组码中。而l d p c 与和积算法却有一种天然的 对应，译码的每次迭代都是一次和积算法的实现。观察译码步骤的第二、三步， 可以清晰地看到这一点。 因子图是一种用于描述多变量函数的“二部 图( b i p a r i t i t eg r a p h ) 。在 因子图中有两类节点，其中一种是变量节点，与之对应的是函数节点。变量节 点所代表的变量是函数节点的自变量。并且同一类节点间无边的直接连接。 图2 3 表示的是一个有五个自变量的函数g 的因子图。根据数学的知识我 们知道任意一个函数都可以进行因式分解。现在假定函数g 可以分解成几个“局 部函数 之积的形式，即： 罟弛，而，x 3 ，五，毛) ：以( 而) 呃如) 呃( 而，而，毛沈如，墨) 卮如，毛) ( 2 8 ) 重鏖塑皇堂堕堡主堡壅 一 _l _ 一 图2 3 自变量函数g 的因子图表示 由( 2 8 ) 式我们做出相应的因子图，如图2 3 所式，局部函数节点与它相关 联的自变量节点用边连接。该因子图清晰的表达了全局函数g 是局部函数无到 厶的乘积。 恼 l 已k 图2 4 函数g 的因子图表示 在图2 3 中反映的是全局函数g ( ) 。而我们感兴趣的往往是通过这个全 局函数计算出的各边缘函数季( 五) 。举个例子，对于而的任何可能取值，我们仅 关心这个喜函数的估计值，设为： 季( 而) 净 g ( 而，而，而，x 4 ，毛) 而内, x 4 岛 ( 2 9 ) 由此可见，宫( 而) 是函数g ( ，x 2 ，黾，h ，黾) 当变量为屯黾时的和函数。 现在将( 2 9 ) 式代入上式运算就可以将其化为和的形式，有 童厌邮电字院坎士论又 季( 而) = l ( x , ) f b ( x ：) 尼( 而，j c 2 ，x 3 ) f o ( x 3 ，x ) f e ( x 3 ，黾) 纛越赢) 讹而x 3 ) 肫川讹瑚 1 0 葫( 而) 厶( 而) 五( 五，而，厶( 而，甄) 五( 屯，砖) 一。 很明显，( 2 1 0 ) 式计算会异常复杂，所以我们将通过一些数学知识将其化 简。 为了简化计算，首先作一些必要的数学定义， 石( 而) ：= l ( x ，毛) ( 2 1 1 ) 矗( 而) ：- - f o ( x ，_ ) ( 2 1 2 ) 则，由： 知i ( 毛) ：2 五( 而) 。f i i ( x 3 ) 我们可以得到 矗( 毛，x z ) ：2e , z c ( x , ，屯，而) 五i i ( 南) ( 2 1 3 ) f v ( x i ) ：= f b ( x 2 埔( 五，而) ( 2 1 4 ) 最终，我们可以由 ( 而) 和万( 毛) 来计算季( 而) ， 雷( 葺) = ( j c l ) ( j c i ) ( 2 1 5 ) 比较( 2 1 0 ) 式与( 2 1 5 ) 式，我们可以很清楚的看到计算窖( 而) 得到了很 大程度的化简。这种化简的思想是基于将一个复杂任务分解成多个小任务的方 法，每个小任务对应到因子图上就是一个函数节点。这使得其计算不需要来自 因子图其他部分的信息，且传送其计算结果仅由这些局部函数的自变量来承担， 从而简化了计算，其具体算法可由后面介绍的和积算法实现。 从上面的一个简单实例可以看到，因子图具有非常良好的可视化效果。并 且可以通过一定的方法把较为复杂的问题转化为一系列只与本地函数有关的局 部问题加以求解，降低了各函数的互相关性。在因子图中，函数节点对每一个 相邻变量节点，由其他相邻变量节点求和计算边缘函数后传递至该变量节点： 变量节点对每一个相邻函数节点，将其它相邻函数节点传递的边缘函数求积后 传递到该函数节点，从而实现了迭代计算。因子图的应用非常广泛，从编码理 论到人工智能、m a r k o v 模型、b a y e s i a n 网络、神经网络等等众多的领域。作为 一种通用的消息传递算法，和积算法实际上包含了大量的实际算法( 前向后向 算法，v i t e r b i 算法，p e a r l s 传播算法等) 。事实上，在因子图的这些应用中， 我们常常需要确定因子图的结构，这是因为因子图结构所包含的信息是由全局 重庆邮电学院硕士论文 函数的因子分解式给出的，且因子图结构对和积算法有着非常重要的影响。即 是说，要通过和积算法求得一个确切的解我们通常要求对应的因子图结构中没 有环，当然已有关于有环图的研究结果。 当了解b p 算法的原理以后，理解和积算法是相对容易的。更多的，我们 直接用b p 算法来表示l d p c 码的译码算法，而跳过和积算法的说法。 2 2 3 不规则l d p c 码的b p 算法 不规则情况下，b p 算法的步骤是一样的。但是不规则的l d p c 码，各个点 的度数不是一样的，因此在计算每个点的概率时，须加以度的控制。并且，在 当前对l d p c 码的算法中，我们通常采用对数似然率l l r ( l o g - l i k e l i h o o dr a t e ) ， 使得原有的乘法计算可以转换为对数的加法计算，提高计算机的计算效率。 用v 代表在第1 次迭代中从变量点到校验点的l l r 消息，叫弋表在第z 次迭 代中从校验点到变量点的l l r 消息。消息的迭代更新过程如下【5 1 ： f ， 1 = 0 k 芝班， o ( 2 1 6 ) 鼬t a n h t u ( o = 拜t a n n 寺v i - i ( 2 1 7 ) 其中，以和疋是最大的变量点的度和最大的校验点的度。( 度表示该点连接 的其它点的个数) 。 重庆邮电学院硕士论文 第三章l d p c 码的优化设计方法一一密度进化方法 3 1l d p c 码的性能与门限值关系 传统的编码理论采用硬判决译码，可以通过分析码字间的距离特性，来判 定其纠错能力；而l d p c 码的译码方式是迭代的，软判决的b p 算法。这意味 着，l d p c 码的纠错能力跟其译码算法的迭代次数，和码字的分组长度是密切 相关的，也就是说，l d p c 码的纠错性能是渐进的。我们将引入一个特殊的参 数：门限值盯，来表示l d p c 码字的纠错性能。 对于二进制对称信道，如果在接收端采用硬判决，由于噪声的存在，发送 比特x 和接收比特y 存在的一定的交错率( c r o s s o v e rp r o b a b i l i t y ) 。如图3 1 所示。用信道质量参数口，表示该信道的信噪比s n r ( 数字通信系统中对应 磊o ) ，也对应地表示了。例如，在b i a w g n 信道上，信道质量参数盯可 以表示该信道的色o 和，也对应地表示了叠加在接收比特上的噪声，是满 足高斯分布n0 , e r 2 ) 的，仃22 芴f 巧1 而， = 日( y ) = 击e x p 很明显，仃越小，e 。n o 越大，越小，信道质量越好。 o x i o 图3 1 二进制对称信道的符号交错率。 ( 3 1 ) 、一 三， 厂 一七 一 一：掣 重厌邮电学院硕士论文 对于任一不规则l d p c 码的分布对( 2 ，力，存在一个最大信道参数盯，使得 对于任意的信道，只要仃 仃时，随着码长和译码迭代次数的增加，随机构造 的码c ( a ，p ) 总是可以达到任意小的误比特率。该值盯即是分布对为( 五p ) 的l d p c 码的门限值。门限值表示了想要l d p c 码成功译码，所需要的信道质量的最低要 求。当信道质量比该门限值更差的时候，无论分组长度多大，迭代多少次，也 不可能达到无误码传输( 即误比特率等于0 ) 。 门限值充分体现了l d p c 码码字纠错性能的渐进性。信道质量参数 盯( 矿 。 。川 其中仇是由信道质量得出的初始概率密度，和。在此表示卷积运算。由于 ，lsj o 时，z = 风( o 丘) 再看虎的密度进化，相对更复杂： 首先定义运算符y ：，( x ，力= 2 t a n h 一( t 觚h 主t a n h y ， 式( 3 4 ) 则演变为甜：厂“，“，厂心圳魄：) ) ) 0 5 ) 设z = ，瓴y ) ， 则p z ( z ) =办办o ) ，简记为n = 尺( 办，办) 。 由于坼，1 f 以是独立同分布的，“的概率密度可计算如下： 以- ：烈z ，r ( ，尺( z ，) ) ) ( 3 6 ) 引入运算符y 的意义在于：由于随机变量“是由方程式 5 材( ) - = d 珥- i t a n h 寺p l - i 重庆邮电学院硕士论文 得来的，没有办法直接观察它的概率密度函数z 的进化规律，只有通过建立输 入输出表，通过查询该表来计算新一轮迭代中z 的值。 dd 对于不规则l d p c 码，度的分布对( 毛p ) ：a o ) = 艺五一一，p o ) = 艺一一。： ，。2 ，2 前面已经提过，a ( 力表示变量点的度的分布，础) 表示校验点的度的分 布，a ( 1 ) = l 。以1 ) = l 。且a ( 一) 分别表示从度为f 的变量点( 校验点) 发出的边占总 的边数的比例。根据前面的推导，可以定义如下两个函数： 以 f ( p ) = 丑_ p f - 2 正 p ( p ) ；艺乃尺卜， t 2 这两个函数分别表示了度为i 的变量点在密度进化过程中，其卷机操作次数 为f 一1 ，度为j 的校验点其查表操作次数为j - 1 。 结合度的分布对，不规则l d p c 码消息的密度进化过程可以总结为 z = 7 0o r ( ，( 风i - ) ) ( 3 7 ) 笛 背 1 = 零l ( 矗) 。 ? 、 f 、 、 l | 一 1 0 石051 01 5 1 w j 图3 3 不规则l d p c 码的消息的概率密度分布 图3 3 复制了m a t l a b 仿真时昂和昂的波形，体现了不规则l d p c 码在译码 过程中，消息概率密度分布的变化趋势。b i a w g n ( b i n a r yi n p u t a d d i t i v ew h i t e 重庆邮电学院硕士论文 g a m s i a nn o i s e ) 信道，t - 3 0 ，码率0 5 ，信道质量参数盯- - 0 9 5 6 2 。图( 口) 是消 息的初始分布，v 为高斯分布，“为冲击响应：图( b ) 是，= 3 0 时，消息密度概率 分布和z 。，v 仍保持了高斯分布的波形，而“呈尖脉冲状态。经过有限次迭 代，曲线明显