（通信与信息系统专业论文）ldpc码和积译码的动态调度算法.pdf

中文摘要 低密度奇偶校验( l d p c ) 码是一类可以逼近香农容量限的线性分组码。l d p c 和积译码中信息更新的次序称为调度，它直接影响译码的收敛速度、误码性能和 译码复杂度。在常见的泛洪调度( f l o o d i n g ) 中，所有变量节点和校验节点在一次 迭代中更新，并将更新的信息传递给相邻节点。泛洪实现相对简单，但收敛速度 一般。而在动态调度中，译码器根据边的残余值进行有选择的更新，这样不仅加 快收敛，还能改善错误平台。动态调度的主要问题是贪婪性和较大的复杂度。 首先，针对贪婪性，提出了基于相对残余的动态调度( r e l a t i v e r e s i d u a l b a s e d d y n a m i cs c h e d u l e ，r r d s ) 算法，在拥有相同残余值的节点中，优先更新低可靠度 的节点，即相对残余值大的节点，从而使选择更有针对性，降低贪婪程度。仿真 表明，与目i j 性能优异的v c r b p ( v a r i a b l et oc h e c kr e s i d u a lb e l i e fp r o p a g a t i o n ) 相 比，r r d s 调度算法具有更快的收敛速度和更低的错误平台，并且适用于多种l d p c 码。 其次，提出了基于节点的c n r r d s ( c h e c k n o d e w i s er r d s ，c n r r d s ) 和 v n r r d s ( v a r i a b l e n o d e w i s er r d s ) 算法，以降低r r d s 算法的复杂度。r r d s 算法中，搜索空间是节点间的边，从中找出具有最大相对残余值的边，然后更新 相连的节点，与此不同，基于节点的r r d s 的搜索空间是节点。由于t a n n e r 图中 节点数远小于边数，基于节点进行搜索会大幅度缩短搜索时间。仿真结果表明， 该算法的性能接近r r d s 且保留了对l d c p 码的普适性特点。 最后，提出了m i n s u mv n r r d s ( m v n r r d s ) 和m i n s u mc n r r d s ( m c n r r d s ) 调度算法。采用m i n s u m 算法计算相对残余值，进一步降低运算复 杂度。仿真结果表明，这两种算法的收敛速度均好于v c r b p ，错误平台更低，且 适于多种类型的l d p c 码。由于变量节点包含更多的校验信息，基于变量节点的 算法均好于基于校验节点的算法。 关键词：调度、和积译码、误码平台、残余值 分类号：t n 9 1 1 2 2 m a b s t r a c t l d w d e n s i t yp a r i t y c h e c k ( u p c ) c o d e sh a v e t h e p o t e n t i a l o fa p p m a c h i n g s h a n n o nl i m i tw i t hs u m - p r o d u c ta l g o r i t h m t h em e s s a g ep a s s i n gs c h e d u l eo v e rt h e t a n n e r 伊a p hd i r e c t l ya f 诧c t sc o n v e r g c n c em t e ，c o m p l e x i t y 粕de r r o rp e b 册锄c e i i l g e n e r a ln 0 0 d i n gs c h e d u l e ，a l l t h ev a r i a b l en o d e s ，锄ds u b s e q u e n t l ya l lt h ec h e c kn o d e s ， p a s sn c wm e s s a g e st ot h e i rn e i g l l b o 璐1 r h ec o m p l e x i t yo ft h ea l g o r i t h mi sn o 姗a ia n d t h ec o n v e r g e n c es p e e di sl o w a st os o m ed y n a m i cs c h e d u l e sb a s e do ni c s i d u a l ，t h e c o n v e r g e n c eo fd e c o d i n gc a nb ea c c e l e r a t e d ，t h u si m p r 0 v et h ee r r o rf 1 0 0 re f f e c t t h e m a i np r o b l e m so fd y n a m i cs c h e d u l e se x i s ti nt h e 伊e e d i n e s sa n dd e c o d i n gc 0 m p l e x i t y f i r s t l y r e l a t i v e r c s i d u a l - b a s e dd y n 锄i cs c h e d u l e ( r r d s ) i sp r o p o s e dt oa b a t et h e 擎e e d i n e s s a m o n gt h o s en o d e st h a th a v et h es a m er e s i d u a l ，t h en o d ew i t ht h e1 e a s t 他l i a b i l i t y i e ，t h eg r e a t e s tr e l a t i v er e s i d u a l ，h a st h ep r i o r i t yo fu p d a t e o b v i o u s l y t h e s c h e d u l ei sm o r ep u l l p o s e f u la n dt h u sw e a k e n st h e 笋e e d i n e s s s i m u l a t i o nr e s u l t ss h o w t h a tr r d sc 锄a c c e l e m t et h ec o n v e r g e n c es t a b l y 觚do b t a i nl o w e re 玎o rn o o rt h 锄t h e f a m o u sv a r i a b l et 0c h e c kr e s i d u a lb e l i e fp r o p a g a t i o n ( v c r b p ) f o rd i f 艳r c n tt y p e so f l d p cc o d e s s e c o n d l y ；c h e c k n o d e - w i s er r d s ( c n - r r d s ) a n dv a d a b l e - n o d e - w i s er r d s ( v n r r d s ) a r ep r o p o s e dt or e d u c et h ec o m p l e x i t yo fr r d s i l lr r d s ，t h ee d g ew i t h t h e 黟e a t e s tr e l a t i v er e s i d u a li sf o u n db e f o r ei t sn e i g l l b o r i n gn o d e sa r cu p d a t e d h e r e i n t h es e a r c hs p a c ec o n s i s t so fa l lt h ee d g e si nt h e1 锄e rg r a p h w h i l ei nt h en o d e - w i s e r r d s s ，t h es e a i hs p a c ei sc o m p o s e d0 fn o d e si n s t e a do fe d g e s b e c a u s et h en u m b e r o fn o d e si sm u c hi e s st h a nt h en u m b e ro fe d g e si nt h et a n n e r ，t h es e a r c h i n gt i m eo f n o d e - w i s es c h e d u l ei ss h o n e n e dg r e a t l y s i m u l a t i o nr c s u l t s ，t h ep e 湘咖a n c eo ft h et 、0 n o d e - w i s er r d s si sv e r yd o s et ot h er r d sf o rav a r i e t yo fl d p cc o d e s f i n a l l y m i n - s u mv n r r d s ( m v n - r r d s ) 觚dm i n s u mc n r r d s ( m c n r r d s ) a r cp r o p o s e d m i n - s u mi s u s e dt og e tr c l a t i v e - r e s i d u a l ，w h i c hf u n h e r l o w e 璐t h ec o m p u t a t i o nc o m p l e x i t y s i m u l a t i o nr e s u l t ss h o wt h a tt h et w om i n s u m v e r s i o n so fn o d e - w i s er r d s sh a v ef a s t e rc o n v e r g e n c er a t e 柚dl o w e re r r o rn 0 0 rt h a n v c - r b pf o rv a r i o u sl d p cc o d e s s i n c ev a r i a b l e - n o d e sh a v em o r cc h e c ki n f 0 咖a t i o n ， v a r i a b l e - n o d e - w i s es c h e d u l e sa r eg e n e r a l l yb e t t e rt h a nc h e c k - n o d e - w i s es c h e d u l e s k e y w o r d s ： s c h e d u l c ，s u m - p r o d u c t ，e r r o rf l o o r ，r e s i d u a l c l a s s n o ：t n 9 11 2 2 致谢 本论文的工作是在我的导师张立军副教授的悉心指导下完成的，张老师严谨 的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢二年来张 老师对我的关心和指导、感谢他对我的科研工作和论文提出了许多的宝贵意见、 感谢他孜孜不倦为我修改论文。 研究期间，v c 弱a d o 和j h m 的论文给了我创新的源泉，在此表示衷心的 感谢。 另外，非常感谢林舒教授有形无形的教诲和指导给了我受之无穷的源泉，我 将牢记林老师的淳淳教诲，走好今后的学习、生活和工作中的每一步。 作为有线实验室的一分子，感谢陈常嘉老师、胡师舜老师、郭宇春老师和实 验室的其它所有的老师，他们给了我无私的帮助和宽松的学习环境，让我在一个 充满温暖和关爱的环境罩愉快而顺【利地完成了学业。特别要感谢的是胡师舜老 师，她的认真负责、勤勤恳恳的工作作风和对学生的真挚关爱是我们工作得以 顺利完成的重要支持力量。 感谢共同参加本课题研究的刘明华、宋紫溪同学，与他们的共同讨论和交流 给了我许多有益的启示和灵感。特别要感谢宋紫溪同学给我提供的码字，丰富了 我的论文数据，帮助我顺利完成了本论文。 感谢我的家人和所有给我关心和帮助的朋友们，是他们支持我完成了这一切。 1 引言 数字通信系统通过信道将信息从信源传递到信宿。信道噪声会导致传输的信 号在接收端出现错误。香农在1 9 4 8 年发表了一篇题为“am a t h e m a t i c a ln e o r yo f c o m m u n i c a t i o n ”的经典论文【，文章中指出，只要信息的传输速率低于信道的容量， 那么通过对信息进行编码，就可以在不牺牲信息的传输或存储速率的情况下，将 有噪信道或存储媒介中引入的错误减到任意少的程度。如图1 - 1 所示，这些错误将 在数字通信系统中通过信道编码纠正。信道编码的编码器将每一个可能的信源信 息比映射成不同的有效码字x ，对于二进制码，x 对应的是一串比特序列。译码器 根据接收信号y 获取最大可能的传输信息1 2 。因此，如何设计有效的编码方法来实 现纠错就成为了设计数字通信系统的核心问题之一。 图1 1 数字通信系统 f i g u r e1 1d i g i t a lc o m m u n i c a t i o ns y s t e m 信道编码的研究已经历经数十年。1 9 5 0 年代，人们在信道编码发展早期发现 了汉明码【扒、格雷码1 3 1 、r e e d m u l l e r l 4 ，5 l 等几类重要的线性分组码和卷积码【们。1 9 6 0 年代出现了b c h1 7 ，8 】和r s1 9 】等多种好的分组码和构造级联码【1 0 j 。低密度奇偶校验 码( 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 ) 于1 9 6 2 年由g a l l a g c r 提出【1 1 j ，之后很长 时间没有引起人们的重视。只有t a n n e r 于1 9 8 1 年从图论的角度研究过l d p c 码【1 2 】。 一直到1 9 9 3 年b e r r o u 等提出了t u r b o 码1 1 3 j ，人们同时发现t u r b o 码从某种角度上 说也是一种l d p c 码，从而重新认识到l d p c 码所具有的优越性能和巨大的实用 价值。1 9 9 6 年m a c k a y 和n e a l 的研究表明，l d p c 长码可以达到t u r l ) o 码的性能 【1 4 l 。最近的研究表明，被优化的非规则u ) p c 长码采用置信传播( b e l i e fp r o p a g a t i o n ， b p ) 译码算法时，能得到比t u r b o 码更好的性能，已经被证实能够获得只距香农限 0 0 0 4 5d b 的误码性能1 1 5 j 。目前，l d p c 码被认为是迄今为止性能最好的码，是当 今信道编码领域的研究热点，近几年国际上对l d p c 码的理论研究以及工程应用 都已取得重要进展。其中，改善l d p c 的译码算法是一个重要的研究领域，它直 接影响着当前的通信系统。在这篇论文中，我们提出了快收敛，低复杂度且易于 实施的l d p c 和积译码的动态调度算法。 1 1l d p c 码的调度 1 1 1l d p c 码的定义 本质上，l d p c 码是线性分组码，定义为稀疏校验矩阵日的零空间。g a l l a g e r 要求二元u ) p c 码的校验矩阵日具有下列结构属性【1 6 ，1 7 】： ( 1 ) 每一行有d ，个1 ； ( 2 ) 每一列有d ，个1 ； ( 3 ) 任意两列之间位置相同的1 的个数不大于1 ； ( 4 ) 与码长和日的行数相比，d c 和d ，都是很小的。 假设码长为，z ，信息位为七，校验位为m 一万一七，则校验矩阵日为m 咒矩 阵。由于列重d 。和行重d ，都远小于码长刀和日中行数川，从而h 中大部分元素 都是零，元素1 的密度很小，因此日为低密度奇偶校验矩阵。上述定义并未要求日 矩阵满秩，其中码率为 r ：竺竺旦。l 一竺：1 一生( 1 1 ) ，l彪刀 d 。 h | 11 1 1011ooo oo1 1 1 11 10o 0101o1o1 1 1 101o1001 1 1 11oo1o1o11 图1 2 规则l d p c 码，l = 1 0 ，d 。= 6 ，d ，一3 f i g u r e1 2r e g u l a r l d p c c o d e 疗一1 0 ，d 。一6 ，d ，= 3 图1 3 非规则l d p c 码刀一9 ，列重恒定，行重变化 f i g u 尬1 3l r r e g u l a ru ) p cc o d e 厅一9 ，c o n s t a n tc o l u 砌w e i g l l t ，v a r i a b l er o ww e i g l i t 注意，z d ，- 朋d 。若满足上面四个条件的奇偶校验矩阵h 的行重和列重都是 恒定的，那么由日确定的l d p c 码( d ，d c ) 为规则码，如图1 2 所示。若奇偶校验 2 川训训副 o 0 1 o 1 o 0 1 1 0 o 1 o 0 1 o 1 1 o o 1 0 0 o 1 1 o o 1 0 1 o 1 o o 1 1 o o o i h 矩阵日的各行或者各列具有不同的重量，则l d p c 码称为非规则码，如图1 3 所 示。 t a n n e r 在线性分组码中引入图形表示法，描述了码字比特与约束它们的校验 方程和之间的关系，奠定了研究l d p c 码的理论基础。l d p c 码的t a n n e r 图由两 个节点集合组成，分别是对应于码字比特的咒个变量节点集合 o ，y l ，一，k ) 和对 应于各个奇偶校验方程和的m 个校验节点集合( c o ，c 1 ，c 历) 。当且仅当第f 个码 字比特参与了第，个奇偶校验方程和时，变量节点”和校验节点c ，之间才有一条 ( k ，c ，) 相连接。定义节点度数为与此节点相连的边数量，因此，变量节点的度数 等于包含该变量节点的奇偶校验方程和的个数或对应日矩阵中列的重量；校验节 点的度数等于被该奇偶校验方程和控制的变量节点的个数或对应h 矩阵中行的重 量【1 2 】。 校验节点 变量节点 图1 4 规则l d p c 码t 姐n e r 图 f i g l i 陀1 4t a n n e r 伊a p ho fr e g u l a rl i ) p cc o d e 校验节点 变量节点 图1 5 非规则u ) p c 码t a n n e r 图 f = i g u 陀1 51 a n n e rg r a p ho fi 1 1 r e g u l a rl d p cc o d e 规则l d p c 码t a n n e r 图中变量节点和校验节点度数都是不变的，如图1 4 所 示，粗线表示变量节点度为3 ，校验节点度为6 。 非规则l d p c 码t a n n c r 图，每个变量节点可能有不同的度，校验节点也是如 3 此。令a ) 为变量节点的度分布，表示如下： a ( x ) 昌“鼍“a ，x 扣1 ( 1 2 ) f _ 1 。 其中a ，代表与度为f 的变量节点相连接的边占总边数的比例，d ，m “代表变量 节点的度的最大值；令p ) 为校验节点的度分布，表示如下： p ( x ) 昌“警。p ，x - 1 ( 1 3 ) f _ 1 。 其中肛代表与度为f 的校验节点相连接的边占总边数的比例，d 。m 。代表校验节点 的度的最大值。如图1 5 所示，其中变量节点度不变，粗线表示校验节点的变化。 在t a n n e r 图中，从某个节点出发又回到此节点为一循环，该过程所经历的边 的数目称为环长，最小环长定义为t a n n e r 图的围长( g i n h ) ，h 矩阵的行列限制表明 对应u ) p c 码t a n n e r 图的西n h 至少为6 【1 6 l 。另外，可从t a n n e r 图的角度解释非 规则u ) p c 码的性能优于规则u ) p c 码，在非规则u ) p c 码的t a n n e r 图中，度数 较大的信息比特节点可以很快得到正确译码结果，这样它就可以给校验节点提供 更准确的信息，得到准确信息的校验节点又可以传递更准确的信息给其他度数较 小的信息比特节点，从而产生波浪效应，加速收敛，获得优异性能【1 7 l 。 1 1 2调度的概念 在l d p c 和积译码算法中，基于图1 4 和1 5 的t a n n e r 图迭代过程，变量节 点和校验节点交替更新各自节点的信息并传递给相邻的节点【1 6 1 8 l 。这一迭代译码 过程并没有涉及节点更新次序的问题，若合理安排节点更新次序就是调度。调度 直接影响着和积译码的性能、收敛度和复杂度。 例如，在译码迭代过程中，我们发现有一些难收敛的变量节点需要足够的软 信息量才可能译j 下确，相对地，易受敛的变量节点只要少量的软信息量便足以译 码成功。如果调度合理，难收敛的变量节点优先更新接收足够量的软信息而易受 敛的变量节点只需给予合理的软信息，会使译码过程更易于整体收敛1 1 9 j 。当然， 这只是一种更新基准之一，对于调度的研究是希望能给出一种基准，能够合理安 排节点更新次序让译码更易于收敛、提高性能同时保持一定复杂度。 1 2 调度算法分类 调度目前大致分为泛洪调度、串行调度、动态调度三类【1 9 】，下面将对调度算 法的发展过程做一个简要介绍。 4 泛洪调度( f l o o d i n g ) 是最原始的调度【删，在1 9 9 8 年由b j f r e y 提出，整个 流程分为变量节点同步更新和校验节点同步更新两个过程，对所有节点不加以区 分对待，统一更新。它与和积译码算法非常相近，性能几乎一致，区别在于f l o o d i n g 在迭代译码中先计算全部信息，然后再对每个节点计算全部外信息，以此来降低 运算时间。 在动态调度出现前，串行调度一直是和积译码调度研究的重点。它是针对泛 洪调度做的改进、整个流程采用串行更新，在一个过程内完成对所有变量节点和 校验节点的同步更新处理，两类节点互相利用对方产生的最新信息1 2 1 】。根据节点 的不同分为变量节点串行调度【2 1 粕】和校验节点串行调度【2 5 - 2 7 1 。基于t a n n e r 图的环， 串行调度又可以分为概率性调度和确定性调度【勰，2 9 1 。另外还有一些串行调度的改 进版本1 3 u 椰j 。 变量节点串行调度算法有( s h u 御e db e l i e fp r o p a g a t i o n ，s b p ) 【矧，在一次迭代 过程中，逐次更新变量节点的过程中，便及时利用变量节点产生的最新软信息更 新关联的校验节点。s b p 遍历一边变量节点后便进行判决，由于在一个阶段内完 成f 1 0 0 d i n g 两个阶段的工作，因此收敛速度对比f l o o d i n g 提升了两倍且保持和 f 1 0 0 d i n g 一致的译码复杂度，换句话说，s b p 无代价提升收敛速度两倍。校验节点 串行调度算法有( l a y e rb e l i e fp r o p a g a t i o n ，l b p ) 【矧，原理和s b p 相似，只是基准 换成了校验节点。l b p 同样在一个阶段内完成f 1 0 0 d i n g 两个阶段的工作，也实现 了无代价提升收敛速度两倍。 无论是变量节点串行调度还是校验节点串行调度，原理上都是及时利用对方 产生的最新软信息更新自身，从而实现收敛加速。从n e r 图分析，这两种串行 调度是加快节点彼此之间的信息交互，但并没有考虑到t a n n e r 图的环。其实在和 积译码信息传递的过程中，有一个隐含的假设条件，就是信息在整个译码过程中 统计独立，这个独立性假设成立的前提是t a n n e r 图中不存在环。当t a n n e r 图中没 有环的时候，该算法可以准确地计算出对数似然比。但是在长度为，的环的途中， 独立性假设只在，2 次迭代内有效，然后信息便会在环内进行循环传递f 1 6 1 。 基于t a n n e r 环的因素，串行调度目前分为概率性调度和确定性调度。两种调 度都是基于每个节点所计算出来的环路系数【2 8 ，冽来规定每个节点的迭代次数，使 其不违背独立性假设，由此让每个节点的信息更新都得到最优化的处理，从而可 以忽略t a n n e r 图的环所带来的影响，即便t a n n e r 的环为4 【弱j 。概率性和确定性区 别在于，前者根据计算出来的迭代次数按比例分配，后者则是直接按计算结果次 数固定分配。性能方面来说，两者都没有误码平台的出现，概率性调度要优于确 定性调度。 从这之后，串行调度的改进也有不同的发展比如l 孙3 3 1 ，总的来说较之前的改进 5 体现在利用最新信息并及时判决上。之前两个方向的串行调度还需要遍历完一个 流程才进行判决，联合行列译码1 3 3 l 则更新完一个节点所关联的边就进行判决，使 一些容易收敛的变量节点不需要等待其余难收敛的变量节点提前被译出从而提高 收敛速度。仿真表明联合行列译码不仅收敛速度较f l o o d i n g 快了2 5 倍，而且拥 有良好的误码平台特性【3 3 j 。串行调度的这种改进也为动态调度的提出做了很好的 铺垫。 串行调度都只是顺序的串行遍历节点所关联的边，并没有对更新的边有区分 对待。联合行列译码改变了普通串行调度的判决过程加快了收敛，但并没有给出 量化标准判断节点是否收敛。 上述局限性使得串行调度对l d p c 码不具备普适性，发展很有限。因此，调 度需要一种判断收敛的量化计算标准来区分更新的边。 动态调度给出了这样的收敛量化计算标准，于2 0 0 7 年由vc a s a d o 在他的博 士论文【3 4 j 中提出，首次提出利用残余值这一节点更新前后值的绝对差来选择 n e r 图中的边进行相应的更新，给调度的研究带来了革新式的发展。 1 3研究现状 最早的动态调度版本就是vc a s a d o 提出的( r e s i d u a lb e i i e fp m p a g a t i o n ， r b p ) 【3 5 ，3 6 l ，通过计算校验节点到变量节点( c ，k ) 的边信息更新前后的绝对 差优先选出其中最大残余值所关联的边更新变量节点到校验节点( k c ，) 的边 信息并将该残余值置为零，然后再更新c ，一k 并计算新的残余值后进行判决，若 不满足校验方程和或达到最大迭代次数则重复以上步骤。 r b p 每更新完一条边所关联的信息便进行判决，这的确最大程度的提升了收 敛速度，但也导致了一个动态调度普遍存在的“贪婪性 问趔3 5 3 7 j 。“贪婪性 是 由过快的收敛导致，使得原来已经纠正错误的变量节点在迭代次数继续增加的时 候又会回到错误状态【3 6 1 。当最大迭代次数在1 0 次以下的时候，r b p 的“贪婪性 问题不会出现，这个阶段r b p 表现了极快的收敛速度，对比早期的串行调度快了 将近5 倍。然而当最大迭代次数继续增加的时候，“贪婪性”会直接导致r b p 的性 能将不再改进从而出现误码平台1 3 引。 针对r b p 的“贪婪性 问题，v c a s a d o 又提出了( n o d e w i s er e s i d u a lb e l i e f p r o p a g a t i o n ，n w r b p ) 【3 5 】确保动态调度随着最大迭代次数的增加能够稳定地加 快收敛。在迭代过程中，n w r b p 区别于r b p 的是根据最大残余值选出边进行相 应的更新后不立即判决，而是用同一运算流程再更新完边所在校验节点的相邻边 后进行判决。这一解决方案通过缓和易于收敛变量节点的收敛速度来缓解“贪婪 6 性 。仿真结果表明，在最大迭代次数设为1 0 次以下的时候，n w r b p 对比早期 的串行调度收敛快了两倍，收敛速度不如r b p ，然而在1 0 次以上的时候n w r b p 将继续改进性能实现稳定地加快收敛，而且对比f l o o d i n g 改善了误码平台。 “贪婪性 问题在动态调度中是一个n p 问题【3 5 3 7 1 ，虽然n w r b p 对比 f l o o d i n g 改善了误码平台，但随着信噪比继续增大时仍旧有可能存在误码平台。然 而n w r b p 误码平台特性对比当前的u ) p c 译码算法来说，还是具备了很好的竞 争力和前景。另外，值得一提的是，n w r b p 改善误码平台的同时也实现了稳定加 快收敛，这一成就很大程度上激励了后人继续研究动态调度。进一步研究动态调 度的重点将集中在如何缓和“贪婪性 同时保持较低的调度复杂度。 关于动态调度的最新研究成果，目前来说，j h m 于2 0 0 9 年提出的 ( v a r i a b l e t o c h e c kr e s i d u a lb e l i e fp r o p a g a t i o n ，v c r b p ) 1 3 8 j 是最显著的。他在 v c a s a d o 的基础上，依据c ，一e 的边信息仅仅包含了一条校验和的信息量而 u c ，的边信息包含了所有校验和的信息量1 3 引，于是将残余值的基准选为 k c ，的边信息，从另一角度改进了“贪婪性 问题。v c r b p 除将c ，一k 的 边信息残余值计算改为k c ，的边信息更新前后绝对差的计算，其运算流程和 n w r b p 基本一致。这一改进使得v c r b p 的收敛速度对比n 、肌r b p 又提升了一 倍且随着最大迭代次数的增加同样保证稳定加快收敛。另外，v c r b p 对“贪婪性” 的缓和，对比n w r b p 又进一步改善了误码平台。 1 4内容与创新 v c r b p 利用包含更多校验和信息量的边信息来计算残余值从而改善“贪婪 性 。结合v c b r p 这一优点，本文利用信息本身可靠度提出了相对残余值来进 一步改进“贪婪性”。同时对相对残余值带来的计算复杂度从寻找和计算最大相 对残余值的两个角度分别加以改进。 本文一共提出了三种新的动态调度算法： 1 ) 基于相对残余的动态调度( r e l a t i v e r e s i d u a l b a s e dd v n a m i cs c h e d u l e ，r r d s ) 在v c r b p 的基础上考虑了边的自身更新信息，根据k _ c ，边信息的残余值 和自身更新信息的大小即信息可靠度来计算最大相对残余值，这一改进使得对于 拥有相同残余值的边优先选择可靠度低的边来进行相应的更新，从而提升收敛速 度。基于以上物理意义，本文给出了相对残余值计算公式来量化选择边。仿真表 明融合v c r b p 和n w r b p 优点的r r d s 实现了稳定提升收敛速度且拥有良好的 误码平台特性。另外，值得一提的是，r r d s 对结构性规则和非规则l d p c 码同样 能够稳定加快收敛和改善误码平台，这也验证了r r d s 调度算法对l d p c 码字的 7 普适性。 2 ) 基于节点的r r d s r r d s 虽然带来了优越的性能，但是在计算相对残余值的时候却引入了除法运 算。根据t a n n e r 图中点的数量远小于边的数量，提出利用点取代边寻找最大相对 残余值来降低复杂度。同样根据物理意义，我们给出了相应的计算公式。这一算 法根据节点的不同，分为( v a r i a b l en o d e r r d s ，v n r r d s ) 和( c h e c kn o d e r r d s ， c n r r d s ) 。v n r r d s 和c n r r d s 的区别在于前者寻找节点是变量节点而后者 是校验节点，另外v n r r d s 也具备了v c r b p 包含全部校验和信息的优点。仿 真结果表明对于不同类型的u ) p c 码，v n r r d s 和c n r r d s 性能接近于r r d s 。 另外，由于拥有全部校验和的信息，v n r r d s 性能略优于c n r r d s 。 3 ) 基于节点的m i n s u mr r d s v n r r d s 和c n r r d s 以点比较取代边比较减少寻找最大相对残余值的对比 次数，然而无论v n r r d s 还是c n r r d s 在相对残余值的运算部分仍旧存在一定 的复杂度。在v n r r d s 和c n r r d s 的基础上，提出了基于节点的m i n s u m r r d s ，利用f o s s o r i e r 提出的u ) p c 码和积译码的简化计算m i n s u m 【4 1 4 3 1 算法改 进相对残余值的运算部分。同样根据原理，给出了对应的计算公式，且同样根据 节点的不同分为( m i n s u mv a r i a b l en o d e r r d s ，m v n r r d s ) 和( m i n s u mc h e c k n o d e r r d s ，m c n r r d s ) 。另外，值得一提的是，m v n r r d s 和m c n r r d s 只是在计算相对残余值的时候引用m i n s u m 算法，其余运算流程与v n r r d s 和 c n r r d s 一致。仿真结果表明对于不同类型的l d p c 码，m v n r r d s 和 m c n r r d s 性能介于v c r b p 和c n r r d s 之间，更接近于c n r r d s 。同样由 于拥有更多校验和信息，m v n r r d s 性能略优于m c n r r d s 。 1 5 章节安排 本文主要内容是l d p c 和积译码的动态调度算法研究。第一章介绍了l d p c 码的调度算法的发展和研究现状，并给出本文的主要工作内容和创新。第二章介 绍了l d p c 和积译码并对现存的经典调度算法按时间顺序做一概括性介绍，同时 从原理上解释动态调度如何克服陷阱集改善误码平台。基于相对残余的动态调度 改进算法r r d s 在第三章提出。r r d s 相对残余值的寻找复杂度和计算复杂度分 别在第四，五章给出相应的v ( c ) n r r d s 和m v ( c ) n r r d s 算法加以改进。最后 在第六章给出本文结论与展望。 8 2 和积译码的调度算法比较 本章介绍了l d p c 和积译码算法，同时对现存经典的调度算法根据非动态和 动态作一个概括式介绍并给出算法描述、流程和仿真分析。最后，利用t a n n e r 图 详细分析了动态调度从原理上如何克服陷阱集( t r a p p i n gs e t ) 从而改善误码平台。 2 1 和积译码 假设对应于一种消息的码字v 一( ，h ，一。) 通过有噪信道进行传输。译码器 根据相应的接收序列r = ( ，o ，厶一，) 、编码规则以及信道噪声特性对码字作出判 决。这种作判决的过程称为译码。根据输入译码器信息的形式不同，形成了两种 译码方式，分别是硬判决译码和软判决译码【1 6 】。 如果解调器的输出被量化为两个电平，即0 和1 ，就叫做解调器对信息作出硬 判决，并输出硬判决接收序列。然后译码器基于某种译码算法来处理这个硬判决 接收序列，这种译码方式被称为硬判决译码。如果解调器的输出被量化为两个以 上的电平，或者根本未经过量化，就叫做解调器对信息作出软判决，并输出软判 决接收序列。通过处理软判决接收序列进行的译码被称为软判决译码。软判决译 码能够提供比硬判决译码更好的性能。但是，软判决译码的实现比硬判决译码要 复杂。 u ) p c 码可采用多种方式译码，包括大数逻辑译码( m a j o r i t y - l o 酉c ，m l g ) 【4 4 ，4 5 1 ， 比特翻转译码( b i t - n i p p i n g ，b f ) 矧，加权比特翻转译码( w e i g l l t e db fd e c 0 d i n g ， w b f ) 【4 刀，后验概率译码( ap o s t e r i o rp r o b a b i l i t y a p p ) 【删，以及和积译码算法 ( s u m - p r o d u c ta 1 9 0 r i t h m ，s p a ) 1 4 。在这5 种译码算法之中，和积译码算法的误 码性能最好。 和积译码算法是一种基于b p 逐符号的软判决迭代译码算法1 3 引。在译码过程 中，和积译码算法分为概率域和对数域。前者利用每个传输比特的后验概率来进 行译码，而后者在概率译码的基础上利用其对数似然比来进行译码，以加法运算 代替乘法运算，减少了概率相乘的次数，从而降低了译码的复杂度，并使得数值 的稳定性更好。下面详细介绍基于对数域的和积译码算法1 1 6 5 。 假设在a w g n ( 加性高斯白噪声) 信道下，一个l d p c 码的码字 v 一( hh 屹q ) 在发送前经b p s k 调制被映射为一个双极性序列 x 一( j 五吒- 1 ) ，其中而- 2 屹一1 且os ，s 万一1 。令y 一( y oy l y 1 ) 为软判决接收序列，且y ，五+ 忍，其中甩，是均值为0 ，方差为仃2 的高斯噪声。 9 在给定软判决接收序列y 以后，和积译码算法是基于t a n n e r 图来传递信息， 最终计算出码字比特1 ，的对数似然比p ( u ) - l n 【尸( 屹一oiy 。) 尸( u - 1iy ，) 】，其中 盹- 1 i y ) 为其后验概率。在t a 仰e r 图的迭代过程中，变量节点和校验节点交替更 新各自节点的信息。变量节点先处理自己的输入信息，然后将计算结果传递到相 邻的校验节点。然后，每个校验节点处理自己的输入信息，并把结果传递到相邻 的变量节点。在每次迭代结束时，计算出码字比特的对数似然比，并据此对码字 比特”做出硬判决，从而检测是否满足校验方程。同时，将计算出的对数似然比作 为下一次迭代的输入继续进行译码。于是，迭代过程持续进行，直到校验方程全 部满足或达到最大迭代次数时停止译码。 基于对数域的和积译码算法具体步骤如下： 1 ) 初始化变量节点的信息：利用下式将每个变量节点的信息初始化为信道信息。 酬- l n 【瑞】粤加1 眨1 ， 2 ) 更新校验节点的信息：利用下式更新从校验节点c ，向变量节点”传送的信息 尺( c j k ) 。 尺( c 屹) 昌兀 a 何) 斜 驴 ) ) 】 ( 2 2 ) 屹( c ，) 屹匕i ! v ( c ，) 图2 1 函数妒 ) 的曲线图 f i g u 他2 1c u eo ff u n c t i 彻畋功 1 0 ( e c ) 图2 2 更新校验节点的过程 f i g u 佗2 2t l i ep r o s so fu p d a t i n gc h e c kn o d c 其中驴 ) 一l o g 【0 工+ 1 ) 0 工一1 ) 】，当x 0 ，驴。1 ) 一驴o ) 。图2 1 展示氟力 延x ，y 正半轴央角4 5 度线严格对称，这使得在实现的时候利用砸) 的对称性进行 查表来避免多余运算。另外q ( v c ，) a 口何) ) ，口( i f ) 代表q ( y ，c ，) 的符号， 即口( 玎) 一s f g 冗【q ( v r c ) 】；卢( 玎) 代表q ( v 。c ，) 的大小，即卢( 玎) = l q ( k c f ) l 。 ( c ，) 嵋代表除了变量节点u 以外，所有与校验节点c ，相邻的变量节点的集合。 图2 2 展示了信息r ( c ，u ) 从校验节点c ，向变量节点”的传递过程，箭头表示信息 传递的方向。传递到变量节点”的信息是校验节点从除了”以外的其它相邻变量节 点可以获得的全部外信息。 尺( 图2 3 更新变量节点的过程 f i g u 他2 3t h ep m c e s so fu p d a t i n gv a r i a b l en o d e 3 ) 更新变量节点的信息：利用下式更新从变量节点y ，向校验节点c ，传送的信息 q ( y f c ，) 。 q ( v t c - ) 昌比) + 蠢) c ，尺( c 6 v r ) ( 2 3 ) 其中p 以) 代表各变量节点信息的初始值，( _ ) c ，代表除了校验节点c ，以外， 所有与变量节点u 相邻的校验节点的集合。图2 3 展示了信息q ( y ，cf ) 从变量节 点v ，向校验节点c ，的传递过程。传递到校验节点c ，的信息是变量节点从信道以及 除了c ，以外的其它相邻校验节点可以获得的全部外信息。 4 ) 对变量节点的信息做出硬判决：利用下式计算出全部变量节点的信息q ( h ) ， 并根据q ( u ) 做出硬判决，从而得到估计接收序列v 一o o ，y l 一，y 。- ) 。 ! ：( ，r ) = = c 6 ；琴( y ，) 尺c 6 v ，+ ，( y r )( 2 4 ) 对于f 一0 ，1 ，刀一1 ，令 叱宣盅粼竺 旺5 ，v 皇上(