（信息与通信工程专业论文）高速数传中ldpc码关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 低密度奇偶校验码( l d p c 码) 是近年来信道编码领域一个里程碑式的进展， 优异的纠错性能和自然并行的译码算法使得它在多个国际性通信标准中得到应 用。本文对l d p c 码在高速数据传输中的应用进行分析和研究，主要工作有以下 几方面： 1 研究了l d p c 码的构造方法。采用行列约束作为构造准则，提出了两类结 构化的二进制l d p c 码构造方法：一类是基于循环群的构造方法，另一类是基于 有限域的构造方法，这两类方法都能构造出t a n n e r 图的围长不小于6 的结构化 l d p c 码。仿真结果表明，构造出来的l d p c 码在加性高斯白噪( a w g n ) 信道 下采用b p 译码可获得良好的误码率性能。 2 提出了一种有效的准循环l d p c 码高并行度译码器设计方法。在准循环 l d p c 码的高并行度译码器设计中，难点在于如何有序处理大量存储器读写以避免 减轻存储器访问冲突。采用“码变换 的方法可以解决这一问题。通过码变换可 以将准循环l d p c 码转化为( 近似) 块准循环l d p c 码。( 近似) 块准循环l d p c 码，无论是对设计高速l b p 译码器，还是高速s b p 译码器，都有助益。对于( 近 似) 块准循环l d p c 码，设计了两种高并行度的译码器：高并行度l b p 译码器和 高并行度s b p 译码器，讨论了它们的具体结构，并且与现有方法做了详细比较。 3 研究了块准循环l d p c 码的编码问题。提出了一种由块准循环奇偶校验矩 阵计算块准循环生成矩阵的方法。基于块准循环生成矩阵，设计了两种采用移位 寄存器的编码电路，一种编码电路的复杂度与码的校验码元数成线性关系，另一 种编码电路则可用于实现高速并行编码。这两种编码电路结合码变换技术还可以 应用于一些准循环l d p c 码的编码。 4 提出了一种基于准循环l d p c 分组码的准循环l d p c 卷积码构造方法。与 准循环l d p c 分组码类似，准循环l d p c 卷积码能够简化译码器设计并且降低存 储需求。仿真结果显示，构造出来的l d p c 卷积码在a w g n 信道下采用流水线 b p 算法译码具有良好的误码率性能。提出了一种能够对l d p c 卷积码进行译码的 流水线l b p 算法，并且针对准循环l d p c 卷积码设计了一种流水线l b p 译码器， 比现有的流水线s b p 译码器在实现复杂度和译码吞吐量上都具有优势。 5 完成了信息速率为8 0 0 m b p s 的( 8 1 7 6 ，7 1 5 4 ) 有限几何l d p c 码的编译码器设 计，以及在大规模f p g a 上的实现。 关键词：高速数据传输；低密度奇偶校验码：分组码；卷积码；t a n n e r 图 第i 页 国防科学技术大学研究生院博士学位论文 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 ，w h i c hw a sr e d i s c o v e r e di nr e c e n ty e a r s ， i sam i l e s t o n ei nc h a n n e lc o d i n gd o m a i n i t so u t s t a n d i n ge r r o r c o r r e c t i o np e r f o r m a n c e a n dn a t u r a lp a r a l l e ld e c o d i n ga l g o r i t h mr e s u l ti ni t sa p p l i c a t i o ni ns e v e r a li n t e r n a t i o n a l c o m m u n i c a t i o ns t a n d a r d s t m sd i s s e r t a t i o nd i s c u s s e st h el d p cc o d e sa p p l i c a t i o ni n 1 1 i 曲d a t ar a t et r a n s m i s s i o n , a n ds t r e s s e ss e v e r a lt a s k sb e l o w 1 t w on o v e lm e t h o d sf o rc o n s t r u c t i n gs t r u c t u r e db i n a r yl d p cc o d e ss a t i s f y i n gt h e r o w - c o l u m nc o n s t r a i n ta r ep r o p o s e d o n ei sb a s e do nc y c l i cg r o u p s ，a n dt h eo t h e ri s b a s e do nf i n i t ef i e l d s 1 1 1 es t r u c t u r e dl d p cc o d e sc o n s t r u c t e db yb o t ho ft h e s em e t h o d s h a v eg i r t h sa tl e a s t6 e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ec o n s t r u c t e dl d p cc o d e s d e c o d e d 、肮n lb pa l g o r i t h mo v e rt h ea w g nc h a n n e lc a na c h i e v eg o o db i te r r o rr a t e ( b e r ) p e r f o r m a n c e 2 a ne f f i c i e n tm e t h o df o rd e s i g n i n gh i g h l y p a r a l l e ld e c o d e ra r c h i t e c t u r eo f q u a s i - c y c l i c ( q c ) l d p cc o d e si sp r e s e n t e d mk e yp o 缸f o rh i g h l y - p a r a l l e ld e c o d e r a r c h i t e c t u r eo faq c l d p cc o d ei sh o wt od e a lw i t hal a r g ea m o u n to fm e m o r yr e a d i n g a n dw r i t i n gi na no r d e r l ym a n n e rs oa st oa v o i d r e d u c et h em e m o r ya c c e s sc o l l i s i o n c o d et r a n s f o r m a t i o ni saw a yt os o l v et h ei s s u e q c l d p cc o d e sc a nb et r a n s f o r m e d i n t o ( a p p r o x i m a t e ) b l o c kq u a s i c y c l i c ( b q c ) l d p cc o d e s ( a p p r o x i m a t e ) b q c l d p c c o d e sh a v eh i g hs p e e dd e c o d i n ga d v a n t a g eo v e ro t h e rt y p e so fl d p cc o d e sf o rs b po r l b pa l g o r i t h m b o t hah i g h l y - p a r a l l e ll b pd e c o d e ra n dah i g h l y p a r a l l e ls b pd e c o d e r f o r ( a p p r o x i m a t e ) b q c l d p cc o d e sa r ep r o p o s e d m o r e o v e r , t h e i ra r c h i t e c t u r e sa r e d i s c u s s e di nd e t a i l ，a n dc o m p a r e d 谢也t h ee x i s t i n gd e c o d e r s 3 n l ei s s u eo ne f f i c i e n te n c o d i n go fb q c - l d p cc o d e si sa d d r e s s e d am e t h o di s p r e s e n t e dt of e n dt h eb l o c kq u a s i c y c l i cg e n e r a t o rm a t r i c e so fb q c - - l d p cc o d e sf r o m t h e i rp a r i t y c h e c km a t r i c e s ，g i v e ni nb l o c kq u a s i c y c l i cf o r m b a s e do nt h eb l o c k q u a s i c y c l i cg e n e r a t o rm a t r i xo fab q c l d p cc o d e ，t w ot y p e so fe n c o d i n gc i r c u i t s u s i n gs i m p l es h i f tr e g i s t e r sa r ed e s i g n e d o n ei sd e s i g n e df o re f f i c i e n te n c o d i n go fa b q c - l d p cc o d e ，i t se n c o d i n gc o m p l e x i t yi sl i n e a r l yp r o p o r t i o n a lt ot h en u m b e ro f p a r i t yb i t so ft h ec o d e 。n l eo t h e ri sd e s i g n e df o rh i g h s p e e dp a r a l l e le n c o d i n g t h e s e e n c o d i n gc i r c u i t sc o m b i n e dw i t hc o d et r a n s f o r m a t i o nc a na l s ob ea p p l i e dt oe n c o d i n go f s o m eq c l d p cc o d e s 4 an e wc o n s t r u c t i o nm e t h o df o rq c - l d p cc o n v o l u t i o n a lc o d e si sp r o p o s e d b a s e do nq c l d p cb l o c kc o d e s s i m i l a rt oq c l d p cb l o c kc o d e s ，t h e s el d p c c o n v o l u t i o n a lc o d e sn o to n l ys i m p l i f yd e c o d e rd e s i g nb u ta l s or e q u i r el e s sm e m o r y s t o r a g e s i m u l a t i o nr e s u l t ss h o wt h a tt h e c o n s t r u c t e dl d p cc o n v o l u t i o n a lc o d e s d e c o d e dw i t i lp i p e l i n e db pa l g o r i t h mo v e rt h ea w g nc h a n n e lc a na c h i e v eg o o db e r p e r f o r m a n c e ap i p e l i n e dl b pa l g o r i t h mf o rd e c o d i n gl d p cc o n v o l u t i o n a lc o d e si s 第i i i 页 国防科学技术大学研究生院博士学位论文 p r o p o s e d ，a n dat y p eo fd e c o d e ra r c h i t e c t u r ef o rq c l d p cc o n v o l u t i o n a lc o d e si s d e s i g n e d b a s e do i lt h e p i p e l i n e d l b pa l g o r i t h m n l e p i p e l i n e d l b pd e c o d e r a l e l l i t e c t u r eh a ss o m ea d v a n t a g e si ns p e e da n dc o m p l e x i t yo v e rt h ep i p e l i n e ds b p d e c o d e ra r c h i t e c t u r e 5 b o t ha ne n c o d e ra n dad e c o d e rw i t ht h r o u g h p mo f8 0 0m b p sa l ei m p l e m e m e di n f i e l dp r o g r a m m a b l eg a t ea r r a y ( f p g a ) f o r ( 817 6 ，715 4 ) f i n i t e - g e o m e t r yq c l d p c c o d e k e yw o r d s ：h i g hd a t ar a t et r a n s m i s s i o n ，l d p cc o d e s ，b l o c kc o d e s ， c o n v o l u t i o n a lc o d e s ，t a n n e rg r a p h 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1l d p c 码的s b p 算法译码流程2 2 表2 2l d p c 码的l b p 算法译码流程2 3 表5 1 编码器的编码速度与复杂度比较7 3 表7 1 ( 8 1 7 6 ，7 1 5 4 ) l d p c 码编码器资源利用表9 7 表7 2 ( 8 1 7 6 ，7 1 5 4 ) l d p c 码译码器资源利用表1 0 4 表7 3 信息速率为8 0 0 m b p s 的l d p c 8 p s k 高速系统的误码率1 0 8 表a 1c c s d s 推荐的l d p c 码校验矩阵中各循环矩阵参数说明1 2 3 表a 2c c s d s 推荐的l d p c 码生成矩阵中各循环矩阵参数说明1 2 4 第页 国防科学技术大学研究生院博士学位论文 图目录 图2 1 ( 1 6 ，8 ) 低密度奇偶校验码的奇偶校验矩阵1 3 图2 2 ( 1 6 ，8 ) 低密度奇偶校验码的t a n n e r 图。1 4 图2 3t a n n e r 图中的4 圈和6 圈1 5 图2 4 近似下三角奇偶校验矩阵l7 图2 5 函数t a n h 。1 伍) 的曲线2 4 图2 6 采用l b p 算法与s b p 算法译码的l d p c 码误码率性能对比2 6 图3 1 码长为6 9 6 的循环群l d p c 码误码率性能3 4 图3 2 码长为1 4 1 6 的循环群l d p c 码误码率性能3 5 图3 3 奇偶校验矩阵中的4 圈结构图3 7 图3 4 码率为5 6 的有限域l d p c 码误码率性能3 9 图3 5 码率为7 8 的有限域l d p c 码误码率性能3 9 图4 1 准循环l d p c 码的全串行l b p 译码器4 3 图4 2 准循环l d p c 码的部分并行s b p 译码器4 5 图4 3 块准循环l d p c 码的高并行度l b p 译码器5 3 图4 47 比特循环右移桶状移位器5 4 图4 5 准循环l d p c 码的串行水平运算高速l b p 译码器5 5 图4 6 块准循环l d p c 码的高并行度s b p 译码器5 7 图4 7 不同消息传递方案的时序图。6 1 图5 1 二次扩展方法构造的块准循环l d p c 码误码率性能6 3 图5 2 块准循环l d p c 码的基于p s r a a 的串行编码电路6 9 图5 3 块准循环l d p c 码的基于s r a a 的串行编码电路7 1 图6 1 码率为1 3 的时不变l d p c 卷积码的t a n n e r 图7 8 图6 2l d p c 卷积码的直接编码器【l l o 】7 9 图6 3 时变l d p c 卷积码的构造步骤示意图8 1 图6 4 码率为5 6 的有限域l d p c 卷积码的误码率性能8 4 图6 5 码率为7 8 的有限域l d p c 卷积码的误码率性能一8 4 图6 6l d p c 卷积码的流水线l b p 译码过程示意图8 7 图6 7 码率为7 8 的l d p c 卷积码采用不同译码算法性能对比8 8 图6 8 码率为6 7 的l d p c 卷积码采用不同译码算法性能对比8 8 图6 9 码率为2 3 的l d p c 卷积码采用不同译码算法性能对比8 9 图6 1 0l d p c 卷积码级联，个处理器的译码器结构9 0 图6 11 准循环l d p c 卷积码流水线l b p 译码器中的存储单元结构图9 2 第v 页 国防科学技术大学研究生院博士学位论文 图7 1 信息速率为8 0 0 m b p s 的l d p c 码编码器实现框图9 6 图7 2l d p c 8 p s k 系统的数据结构9 6 图7 3 伪随机扰码序列生成器9 7 图7 4 高速l d p c 码编码器的f p g a 片内结构9 7 图7 5 ( 8 1 7 6 ，7 1 5 4 ) 有限几何l d p c 码的量化译码性能9 9 图7 6 树状c f u 实现结构的基本模块1 0 0 图7 74 输入v f u 的实现结构1 0 1 图7 8 信息速率为8 0 0 m b p s 的l d p c 译码器实现框图1 0 2 图7 9 高速l d p c 码译码器的片内结构1 0 5 图7 1 0 信息速率为8 0 0 m b p s 的l d p c 8 p s k 高速系统1 0 6 图7 1 1 系统误码率性能测试框图1 0 7 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表和撰写过的研究成果。也不包含为获得国防科学技术大学或其它教 育机构的学位或证书而使用过的材科与我一同工作的同志对本研究所做的任何 贡献均巳在论文中作了明确的说明并表示谢意 学位论文题目：直鎏兹笾圭坠垒匹璺差煞拉苤盈窀 学位论文作者签名：拯玉生蜴 日期：2 0 0 9 年9 月2 1 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借闲：可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名：主塞章蛆 日期：2 0 0 9 年9 月2 1 日 作者指导教师签名：至篷垒显 日期：2 0 0 9 年9 月2 1 日 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 课题背景 跟踪与数据中继卫星系统( t d r s s ) 是2 0 世纪航天测控通信技术的重大突破， 它从根本上解决了测控、通信的覆盖率问题，同时还解决了高速数据传输和多目 标测控通信等技术难题，并且具有很高的经济效益【l 】。1 9 6 4 年，美国航天测控专 家m m a l c o l m 提出利用地球同步卫星转发功能进行测控的新概念。1 9 8 3 年4 月4 日，美国发射了世界上第一颗跟踪与数据中继卫星，开创了天基测控新时代。截 至目前，美国发射的民用和军用中继卫星达到2 0 多颗，并且组网运行，它们已经 成为美国航天测控和空间大容量高速数据传输的主要手段。俄罗斯的中继卫星系 统也已组网运行，现正在发展后续系统。欧空局和日本也已经成功应用了各自的 中继卫星系统。2 0 0 8 年4 月2 5 日，我国成功发射了首颗数据中继卫星天链一 号0 1 星，标志着我国成为继美国、俄罗斯、日本、欧洲之后拥有中继卫星的国家。 各国之所以如此坚持不懈地发展中继卫星系统，重要原因在于它有很多应用 需求。长期以来，地面与航天器之间的联系是通过地基测控系统实现的。由于电 磁波直线传播特性和地球曲率的限制，一个地面站只能遥测遥控飞行至地球一定 弧度轨道的航天器，一旦航天器飞出这一范围，地面站就会与之失去联系。理论 上，只要建立足够多的地面站，就能够实现对航天器1 0 0 的覆盖率。实际上，以 对于轨道高度高于3 0 0 千米的卫星为例，必须在地球上建立1 0 0 多个地面站才能 达到1 0 0 的覆盖率，考虑到经费、地理环境和政治因素等原因，这是根本不可能 实现的。与地基测控相比，天基测控的最大优势在于它的覆盖率高，单颗中继卫 星对低轨航天器的覆盖率不低于5 0 ，两颗中继卫星就能基本覆盖整个中低轨道， 如用3 颗中继卫星，则可以实现对2 0 01 2 0 0 0 千米高度范围内所有航天器的连续 跟踪和数据通信【2 ，引。 中继卫星的高覆盖率保证了其能够将中低轨道的各类航天器观测地球产生的 数据和图像实时传送至地面。但是，随着各类航天器大量增加，它们会产生极高 数据率的探测信息，这对于载人航天器和对地观测任务来说尤为突出：随着遥感 技术等数据采集技术的飞速发展，大量图像数据的传输也迫切需要高速率的传输 系统。就我们目前了解，数据中继卫星的各种观测卫星用户的海量数据传输速率 需求很高，如航天遥感数据经过压缩后仍有3 4 0 m b p s 的信息速率，有些相关用户 甚至提出了超过1 g b p s 的需求，中继卫星的数据传输率要求越来越高【4 】。 目前，西方各国在高速数据传输业务方面，3 0 0 m b p s 的卫星高速数传系统已实 用化，1 g b p s 甚至更高速率的高速数据传输系统正在研究或实验。美国航宇局 第1 页 国防科学技术大学研究生院博士学位论文 ( n a s a ) 第一代t d r s s 的最高返向数据传输速率为3 0 0 m b p s ，而第二代t d r s 卫星具备勋波段通信能力，其最高返向数据传输速率可达8 0 0 m b p s 。欧洲遥感卫 星l 号e r s 1 的数据传输速率为1 0 5 m b p s ，欧洲数据中继卫星系统最高返向数据 传输速率为5 0 0 m b p s ，欧空局( e s a ) 资助的m h o m s 项目【5 j 正在研制一种新的 高速率、可在轨重构的卫星数字调制解调器，最高信息速率达到1 g b p s 。日本 n a s d a 的d r t s s 系统最高返向数据率为3 0 0 m b p s ，1 2 g b p s 传输速率的卫星高 速数据传输系统也已研制成功【6 】。 随着传输容量需求的快速增长，高速数传中面临着功率频谱受限的严重压力， 因此寻求功率频谱同时有效利用的传输手段已成为高速数传系统设计研究的主要 目标。为了满足传输带宽的限制与高数据率的要求，可以采用高阶调制技术来提 高传输效率，诸如8 p s k 、1 6 q a m 、1 6 a p s k 甚至更高阶的调制技术都是提高频谱 效率的候选方案。然而，这些高阶调制技术在相同带宽条件下提高数据传输率是 以降低功率利用率为代价的。通过在高阶调制系统中应用具有强大纠错能力的信 道编码则是提高功率利用率的有效手段。就信道编码方面而言，作为目前性能最 好的码之一，低密度奇偶校验( l o wd e n s i t yp a r i 够c h e c k ，l d p c ) 码无疑是一种 很好的选择。 高速数据传输技术在卫星测控、卫星侦察、宽带军事卫星通信、d r s s 以及相 应的工业民用通信系统中都有广泛的应用前景。本课题确立研究l d p c 码在天基 综合信息网高速数据传输中的应用，不仅能够解决我国天基综合信息网中实时、 大容量数据传输的瓶颈，促进天基综合信息网的发展，而且在其它高速数传系统 中( 尤其是功率频谱同时受限的系统中) 也有着广阔的应用前景。 1 2l d p c 码的研究现状 l d p c 码最早是由麻省理工学院的g a l l a g e r 于1 9 6 3 年在其博士论文中提出来 的一种具有稀疏奇偶校验矩阵的分组码，并且证实具有极为优越的性能，然而限 于当时的科技水平却无法实现。此后三十多年基本上被人们所遗忘，其间最大进 展是由t a n n e r 在1 9 8 1 年推广了l d p c 码并给出了其图表示，即后来所谓的 t a n n e r 图【7 】。直到t 1 l 曲码【8 】的出现，伴随着t 1 】码带来的巨大冲击，l d p c 码 终于在1 9 9 5 年由m a c k a y 与n e m 重新发现并加以研究【9 ，1 0 1 。2 0 0 1 年，l u b y 指出 不规则l d p c 码可以达到与t u r b o 码一样的性能n u 。同年，c h u n g 构造了距离香农 ( s h a n n o n ) 限仅0 0 0 4 5 d b 的l d p c 码口钉，迅速引起强烈反响和极大关注。 目前，有关l d p c 码的研究方向主要包括码的性能分析、码的构造、有效编 码、译码算法、硬件实现以及针对实际通信系统的应用等。 第2 页 国防科学技术大学研究生院博士学位论文 1 2 1l d p o 码的性能分析 对l d p c 码的重新研究首先是从其性能分析开始的，l d p c 码的译码性能分析 方法主要可以分为三类：密度进化、高斯近似和e x i t 图。 l d p c 码的迭代译码存在阈值( t h r e s h o l d ) 现象( 或者称为译码门限) ，即当 信噪比大于这个译码门限时，随着码长趋于无穷大迭代译码可使误码率( b i te r r o r r a t e ，b e r ) 趋于零，反之，则总存在一定的错误概率。g a l l a g e r 最早发现了二元 对称信道( b i n a r ys y m m e t r i cc h a n n e l ，b s c ) 的阈值现象。l u b y 等人【l l 】随后发现 在二元删除信道( b i n a r ye r a s u r ec h a n n e l ，b e c ) 中同样存在这种阈值现象，并且 发现不规则l d p c 码可以改进阈值。r i c h a r d s o n 等人在g a l l a g e r 和l u b y 的工作基 础上将对l d p c 码译码特性的分析方法扩展到更一般的信道模型，系统建立了无 圈图上的密度进化( d e n s i t ye v o l u t i o n ，d e ) 理论【1 3 ，1 4 1 ，并且证明了随机有圈图的 译码门限可以逼近无圈图的译码门限，因此，无圈图上的密度进化理论可以用于 近似估算有圈图上l d p c 码的性能。采用密度进化方法，可以分析l d p c 码的码 集平均渐近性能，并能计算出任意码集在相应信道条件下的门限值，根据这个门 限值，可以初步预测此码集性能的好坏。密度进化还可以用于分析l d p c 码在不 同信道、不同消息传递机制的收敛特性，优化度序列设计以改善不规则l d p c 码 的译码门限，量化译码方案的分析选择，以及扩展到多进制l d p c 码的分析。h o u 等人【l5 j 将密度进化算法扩展到衰落信道，并用来设计衰落信道下的l d p c 码编码 调制系统。密度进化的运算量较大，在实际计算中通常采用离散化的密度进化算 法【1 2 】。 由于密度进化算法是对无限维消息密度的进化过程进行跟踪，计算复杂度高。 鉴于密度进化算法的高复杂度，c h u n g 等人提出利用高斯分布来近似译码过程中从 变量节点和校验节点输出的置信度消息，从而对消息密度进化过程的跟踪变为对 一维均值参数的跟踪，此即高斯近似算法【16 1 。a r d a k a n i 等人提出了更接近l d p c 码译码真实特性的半高斯近似方法【1 7 】。 外信息转移图( e x t r i n s i ci n f o r m a f i o nt r a n s f e rc h a r t ，e x i t 图) 由b r i n k 最先 提出【1 8 】，并应用在了l d p c 码的设计中【1 9 】。文献 2 0 】中分析了各种e x i t 曲线的计 算方法。与密度进化方法类似，e x i t 图也可以用于分析l d p c 码集合的译码门限， 将l d p c 码的译码过程看作是变量节点译码器和校验节点译码器之间外部信息的 迭代，而不规则l d p c 码的e x i t 图是各成员节点e x i t 图的线性组合【2 l 】，因此 可将不规则l d p c 码的度序列设计问题转化为种线性规划问题，用图来形象描 述时，就是一个曲线拟合问题。与密度进化跟踪整个分布的进化不同，e x i t 图只 跟踪互信息量的进化，因此计算量要小得多。e x i t 图提供了一种预测和分析迭代 算法收敛行为的方法，不仅可以用来分析和设计l d p c 码、重复累积码( r e p e a t 第3 页 国防科学技术大学研究生院博士学位论文 a c c u m u l a t ec o d e ，r a 码) 、t u r b o 码等，还可以应用于迭代解调和译码系统、多 输入多输出( m m o ) 系统、以及衰落信道下的l d p c 码编码调制系统。 1 2 2l d p c 码的构造现状 l d p c 码的性能好坏与否直接取决于其奇偶校验矩阵结构，l d p c 码的构造就 是确定其奇偶校验矩阵。有关l d p c 码的构造方法种类繁多，主要可以分为两大 类：随机构造法和结构化构造法。 随机构造法的思路是把奇偶校验矩阵中的非零元素l 随机散布在一个大小 已经确定的矩阵中，然后再根据一些约束条件对1 的位置进行调整。这些约束 条件主要包括满足规则码的行、列重量要求，满足不规则码行、列重量分布比例 的要求，满足矩阵所对应的t a n n e r 图的围长要求等。典型的随机l d p c 码构造方 法主要有：g a l l a g e r 的方法、m a y k a y 的方法瞄】、( e x t e n d e d ) b i t - f i l l i n g 算法 2 3 , 2 4 】、 p e g 算法【2 5 1 、基于外信息度( e x t r i n s i cm e s s a g ed e g r e e ，e m d ) 的构造法【2 6 j 等。 前两种方法都是根据行重和列重随机产生h 矩阵，主要是针对规则l d p c 码的构 造。后三种算法可以用于构造不规则l d p c 码。对于不规则l d p c 码而言，度数 分布对是影响其性能的一个关键因素，在构造不规则l d p c 码之前需要知道码的 变量节点和校验节点的度数分布对，它们通常是由密度进化或者e x i t 图等方法得 到的。p e g 算法是目前最常用的随机l d p c 码构造方法之一，利用p e g 算法可以 容易地构造出围长大、短圈数量少的l d p c 码，从而具有优异的性能。基于e m d 的构造法通过有选择的去除短圈，增加码的停止集( s t o p p i n gs e t ) 规模，提高最小 距离的下限，从而能够有效降低码的错误平层( e r r o rf l o o r ) 。 结构化构造法的最终目标就是要达到硬件成本的最小化，编译码器实现复杂度 的降低，以及获得尽可能大的编码增益。典型的结构化l d p c 码有：1 ) 有限几何 l d p c 码【2 7 】；2 ) 组合l d p c 码；3 ) a r r a yl d p c 码【2 8 】；4 ) 基于r s 码的l d p c 码【2 9 1 ； 5 ) 基于循环置换矩阵的准循环l d p c 码、6 ) r a 码及其改进形式等。前五种方法都 能构造出准循环l d p c 码。准循环l d p c 码是指可以将奇偶校验矩阵分成数个小 的方阵，而每个方阵则是循环矩阵或全o 矩阵的l d p c 码。准循环l d p c 码在硬 件实现上，由于非常便于存储器的寻址而能够大大降低译码器的复杂度，由于可 以采用反馈移位寄存器而能够实现线性复杂度的编码。基于有限几何构造的有限 几何l d p c 码是出现最早的一类准循环l d p c 码。在文献 3 0 ，3 1 ，3 2 3 里s t e i n e r 三连系、循环差族和循环差集等组合设计方法也被引入l d p c 码的构造中，这些 组合方法中的大多数也能得到准循环l d p c 码。基于有限几何、组合设计等代数 方法能够构造消除短圈、性能优良、有较好的最小距离、错误平层低的l d p c 码， 但是码率和码长等参数的选择不够灵活。f o s s o r i e r 在文献【3 3 】中针对基于循环置换 第4 页 国防科学技术大学研究生院博士学位论文 = = 3 3 - - - = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ：= = = = = = = = = = = = = 矩阵的l d p c 码给出了若干围长判定条件，基于此可以采用计算机搜索的方式来 构造准循环l d p c 码，文献 3 4 】将p e g 算法扩展从而应用于构造准循环l d p c 码， 这些方法构造出来的l d p c 码在码长和码率等参数的选取上更加灵活。第六种方 法构造出来的码也具有编码复杂度低的优点。r a 码是d i v s a l a r 等人 3 5 】为了解决 l d p c 码编码复杂度高这一问题而提出的。随后，j i n 等人【3 6 】将r a 码推广为不规 则重复累积码( i r r e g u l a rr e p e a ta c c u m u l a t ec o d e ，i r a 码) ，并且证实了i r a 码 可以取得与不规则l d p c 码同样优越的性能。i r a 码的编码可以像t u r b o 码一样 采用两个分量码串行级联的方式来实现，而译码则可采用基于t a n n e r 图的b p 算 法来实现，因此，同时具备编码复杂度低和能够自然并行译码的优点。与准循环 l d p c 码的结合，还可以进一步简化其编译码器的实现复杂度，目前许多标准中的 l d p c 码都兼具准循环l d p c 码与i r a 码的结构特点。 1 2 3l d p o 码的编码现状 t 1 l 曲码的编码仅仅需要进行一些卷积运算与交织处理，相对来说比较简单。 而l d p c 码的编码比较复杂，寻找低复杂度的编码方法是l d p c 码应用要面临的 一个重要问题。 m a c k a y 首先提出将普通线性分组码的编码方法应用于l d p c 码的编码方案 瞄】。该方法首先通过高斯消元将稀疏奇偶校验矩阵转换为系统形式从而得到生成 矩阵，然后利用生成矩阵和信息码元序列相乘得到校验码元序列。这种方法导致 编码复杂度随码长成平方增长，对于码长上千的l d p c 码来说，其计算量是难以 接受的。 其后，p l i 等人【明提出了一类面向编码器实现的半随机l d p c 码，这类l d p c 码要求校验矩阵右边矩阵为固定的双对角方阵，而左边矩阵为随机矩阵，这样就 可以采用类似t u r b o 码的串行级联编码，编码器结构简单、复杂度也低，但是该 编码器的设计针对性太强，很难应用于一般类型的l d p c 码。 2 0 0 1 年，r i c h a r d s o n 等人【38 】提出了基于校验矩阵的近似下三角形式的编码方 法。该方法首先通过预处理将校验矩阵转换为下三角或者近似下三角的形式，由 于只对校验矩阵进行列交换而保持了矩阵的稀疏性，然后采用近似下三角形式的 稀疏校验矩阵可以实现接近线性复杂度的编码，文中还给出了几种转换校验矩阵 的贪心算法。基于近似下三角矩阵的有效编码算法对所有的l d p c 码均适用，初 步解决了l d p c 码编码难的问题。 2 0 0 1 年以后，准循环l d p c 码凭借其校验矩阵结构上的优点和优越的性能逐 渐成为了l d p c 码领域的研究热点。针对准循环l d p c 码的线性复杂度编码方法 也随之被提出。文献 3 9 1 对此作了初步的研究，但是没有给出对任何准循环l d p c 第5 页 国防科学技术大学研究生院博士学位论文 码均可行的编码方法。针对任意准循环l d p c 码的通用编码方法于2 0 0 6 年在文献 【4 0 】中给出，文献讨论了如何由任意的准循环校验矩阵求解出准循环生成矩阵的方 法，并在此基础上设计出了三种线性复杂度的编码电路。从此，l d p c 码编码复杂 度过高的问题得到了较好的解决。 通过在校验矩阵的构造过程中引入特定约束来进一步降低编码复杂度也是目 前常见的一种方法。例如i e e e8 0 2 1i n 、i e e e8 0 2 1 6 e 等标准中采用的l d p c 码都 是在准循环l d p c 码的基础上附加约束，从而能够有效利用校验矩阵的稀疏特性 来实现有效编码。这些方法的优点是编码复杂度能够进一步降低，不足之处是通 用性不够。 1 2 4l d p c 码的译码算法 线性分组码通常采用代数译码，复杂度与其码长成指数增长关系，因此对于 l d p c 长码而言，传统的代数译码方法很难适用。l d p c 码的众多译码方法大都是 基于t a n n e r 图的消息传递算法。这些算法充分利用了奇偶校验矩阵的稀疏性，使 得译码复杂度与码长成线性增长关系，从而克服了长码在应用中所面临的计算复 杂度问题。将这种基于稀疏奇偶校验矩阵的低复杂度消息传递算法推广到卷积码 的情形，出现了所谓的l d p c 卷积码，关于l d p c 卷积码的相关内容及研究现状 在第六章中介绍。 根据消息量化级数的不同，可以将l d p c 码的译码方法分为硬判决译码和软 判决译码。 l d p c 码的硬判决译码算法主要有一步大数逻辑译码算法 2 7 1 、g a l l a g e r 提出的 比特翻转算法( b i t f l i p p i n ga l g o r i t h m ，b f a ) 、加权比特翻转算法( w b f a ) 【4 1 郴】 等。一步大数逻辑译码算法只适用于某些结构比较特殊的码，如有限几何l d p c 码。比特翻转算法的优点是计算复杂度非常低，缺点是其译码性能不理想，并且 译码器输出没有可靠性信息，只适用于低端应用中，因为在低端应用中对性能要 求相对不是很高，而且很可能不需要迭代均衡信道估计等技术，没有可靠性信息 也显得无关紧要。加权比特翻转算法采用信道的软信息对比特翻转的判据进行加 权，可以在复杂度增加不多的情况下提高