（通信与信息系统专业论文）dmbt系统中多码率ldpc码译码器研究及实现.pdf

d m b t 系统中多码率l d p c 码译码器研究及实现 摘要 在现代通信系统中，纠错码被用来提高信道传输的可靠性和功率 利用率。1 9 6 2 年，g a l l a g e r 首次提出了l d p c 码的古典模型，即规则 ( r e g u l a r ) 的l d p c 码。但由于当时计算机水平发展有限，硬件实现困 难，l d p c 被长期的遗忘了，直到1 9 9 5 年才成为学界的焦点。l d p c 码是目前最逼近香农限的一类纠错码，它具备比t u r b o 码更接近香农 限的误码率性能和完全并行的迭代译码算法，因此也比t u r b o 码具有 更广泛的应用前景。当前众多新兴领域中都采用了l d p c 码，如无线 局域网i e e e 8 0 2 1 1 、地面广播传输系统d v b s 2 和中国移动多媒体广 播c m m b 等等，未来的无线移动通信中l d p c 码也将成为一个选择。 现今中国出台的数字电视地面传输标准中的多载波系统d m b t 的信 道编码方案中也采用了l d p c 码作为其内码。 本文重点对d m b t 系统中采用的l d p c 码的译码算法和性能进 行研究和分析，并采用f p g a 自主设计和实现了该系统的l d p c 译码 器。为了使读者有一个清晰的思路，更好地理解d m b - t 系统中的 l d p c 码，本文前半部分主要从理论上详细介绍了l d p c 码，为后半 部分做好铺垫。第二章循序渐进地阐述了l 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 码( q c l d p c ) ，详细阐述 了这种码的特点，并由此切入到d m b t 系统中采用的q c l d p c 码。 针对d m b - t 系统，本文给出了其所采用的三种码率的q c l d p c 码 的具体参数。从第四章开始，本文进入l d p c 码的实现部分，总结了 利于硬件实现的q c l d p c 码的译码算法，并采用m a t l a b 软件对 d m b t 系统的l d p c 码进行了性能仿真，验证了其优越的误码性能。 本文最后一章是对研究生阶段所做课题的归纳和总结，给出了 d m b t 系统中能够支持o 4 、0 6 、0 8 码率以及q p s k 、1 6 q a m 和 6 4 洲三种调制方式的l d p c 译码器的设计思路和实际的f p g a 设 计结构，并由时序仿真结果验证所设计的译码器的有效性。 关键词：低密度奇偶校验码奇偶校验矩阵t a n n e r 图准循环码 和积算法最小和算法 t h er e s e a r c ha n df p g ar e a i 。i z 佃o n o fl d p ci nd m b ts y s t e m a b s t r a c t a si sk n o w nt oa l l ，e r r o rc o r r e c t i n gc o d ew a su s e di nc o m m u n i c a t i o n s y s t e mt oi m p r o v et h er e l i a b i l i t y a n dp o w e ru t i l i z a t i o no fc h a n n e l t r a n s m i s s i o n l o wd e n s i t yp a r i t y - c h e c kc o d e s ( l d p cc o d e ) ，ak i n do f e r r o rc o r r e c t i n gc o d e ，w a si n v e n t e db yr o b e r tg a l l a g e ri n1 9 6 2 g i v e n t h e d e v e l o p m e n tc o n d i t i o n o fc o m p u t e rt e c h n o l o g ya tt h a tt i m e ，t h e c o m p l e x i t yo fl d p ch a r d w a r er e a l i z a t i o nw a so u to ft h eq u e s t i o n s ot h e c l a s s i c a lm o d e lo fl d p ci no t h e rw o r d sr e g u l a rl d p c ，w a sl a r g e l y f o r g o t t e n u n t i l1 9 9 5 ，i tf i n a l l yc a m eb a c kt ot h ef i e l do fr e s e a r c ha n d b e c a m et h ef o c u s i th a sb e e ns h o w nt h a tl d p cc a np e r f o r mv e r yc l o s et o t h es h a n n o nc a p a c i t yl i m i t l d p ch a sas i g n i f i c a n t l yl o w e rc o m p l e x i t y t h a nt u r b oc o d e sa tt h ec o d el e n g t h s ，p e r f o r m a n c ea n ds n b e s i d e s ， l d p cd e c o d e ri ss u i t a b l ef o rf u l l yp a r a l l e li m p l e m e n t a t i o n t h i sh a s s i g n i f i c a n ta d v a n t a g e sw h e nc o n s i d e r i n gl o n gc o d e s i ti ss a f et os a yt h a t l d p cs u r e l yh a sam o r ep r o m i s i n gf u t u r e t h et r u t hi sl d p ch a sb e e n a d o p t e da ts om a n yr e s e a r c ha c h i e v e m e n t sc u r r e n t l y ：s u c ha sw i r e l e s s l a ni e e e8 0 2 11 ，t e r r e s t r i a l b r o a d c a s t i n gt r a n s m i t t i n gs y s t e m d s 2a n dc h i n am o b i l em u l t i m e d i ab r o a d c a s t ( c m m 鳓i nc h i n a t e r r e s t r i a ld t vs t a n d a r d ( g b 2 0 6 0 0 2 0 0 6 ) w h i c hw a sr e l e a s e dr e c e n t l y , t h ec h a n n e lc o d i n gs c h e m eo fi t sm u l t i c a r d e rs y s t e m ( d m b na l s ou s e l d p c t h i sp a p e rm a i n l yf o c u s e so nt h er e s e a r c ha n da n a l y s i so ft h e c o d e c a l g o r i t h ma n dt h ep e r f o r m a n c eo fl d p c u s e di nd m b ts y s t e m i na d d i t i o n 。ad e c o d e ro ft h ed m b ts y s t e mi sr e a l i z e dw i t hf p g 八 i n0 r d e rt om a k ei te a s yt ou n d e r s t a n d ，t h ef i r s tc h a p t e ro ft h i sp a p e r g i v e st h ei n t r o d u c t i o no fl d p cc o d e t h es e c o n dc h a p t e rw i l lt a l ka b o u t t h ep r i n c i p l eo fl d p cc o d e ，i n c l u d i n gt h ed e v e l o p i n gh i s t o r y , d e f i n i t i o n ， a n a l y s i so ft a n n e rg r a p h ，c l a s s i c a ld e c o d es c h e m ea n dc o n t e m p o r a r y d e c o d es c h e m e b a s e do nw h a tw ei n t r o d u c e da b o v e 。t h et h i r dc h a p t e r w i l lt a l ka b o u tt h ec h a r a c t ：e r i s t i co fav e r ys p e c i a lk i n do fl d p cc o d e 。 n a m e dq c l d p cc o d e ( q u a s i c y c l i cl d p cc o d e ) f u r t h e r , t h i sp a p e r g i v e st h ep a r a m e t e r so ft h eo c l d p cu s e di nd m b ts y s t e m f r o mt h e f o u r t hc h a p t e ro n w em o v ei n t ot h er e a l i z a t i o no ft h el d p cd e c o d e t h e c o d e ca l g o r i t h mo fq cl d p cw h i c hi ss u i t a b l ef o rh a r d w a r e r e a l i z a t i o ni sc o n c l u d e d a d d i t i o n a l l y , m a t l a bi su s e dt oc o n d u c tt h e p e r f o r m a n c es i m u l a t i o no ft h el d p cc o d eu s e di nd m b - ts y s t e m a n d t h es i m u l a t i o nr e s u l tp r o v e st h a tt h ec o d e sp e r f o r m a n c ei sp r e t t yg o o d i n t h el a s t c h a p t e r ，1w i l l t a l ka b o u tt h ed e s i g ni d e aa n df p g ad e s i g n s t r u c t u r eo ft h el d p cd e c o d e rf o rd m b ts y s t e mw h i c hc a l ls u p p o r t 0 4 ，0 6 ，0 8c o d er a t ea n dq p s k 16 q a ma n d6 4 q a mm o d u l a t i o nm o d e s t h ev a l i d i t yo ft h i sd e c o d e rw i l lb ed e m o n s t r a t e db yt h et i m i n g s i m u l a t i o nr e s u l t k e y w o r d s ：l d p c ，p a r i t yc h e c km a t r i x ，t a n n e rg r a p h ，e c - l d p c ， s p a ( s u m - p r o d u c ta l g o r i t h m ) ，m i n s u ma l g o r i t h m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：名喳p l 本人承担一切相关责任。 日期：立蹲1 一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名：气。么p l fz 譬。吖 日期：型! i ：圣： 日期：乞堕琴l l l 北京邮电大学硕士学位论文 1 1d m b t 系统简介 第一章绪论 在经历了机械电视时代、黑白电子电视和彩色电视时代以后，电视向着数字 化和高清晰度向前迈进，模拟电视在全世界范围内正在逐步引退。经过多年坚持 不懈的研究和发展，数字电视地面广播( d t m ：d i g i t a lt e l e v i s i o n t e r r e s t r i a l b r o a d c a s t i n g ) 取得了很多的成果，世界上已经提出了三个地面数字电视 标准：欧洲的d v b t ，美国的a t s c 和同本的i s d b t ，且都达到实用阶段。我国也 在2 0 0 5 年3 月提出了具有自己知识产权的地面数字电视标准一中国数字电视地 面广播融合方案( 建议稿) ，并计划在2 0 0 8 年用数字电视转播奥运会，2 0 1 0 年全面 实现数字广播电视，2 0 1 5 年停止模拟广播电视的播出。数字电视相对模拟电视在 节目制作、节目存储、信号处理、传输以及播出都发生了革命性变化。其采用数 字技术将活动图像和声音等信号加以处理、压缩、编码、经存储或实时广播后， 供用户接收。与传统的模拟电视相比，数字电视在图像和声音质量两方面都有重 大改进。其根据清晰度可分为：标准清晰度数字电视( s d t v ：s t a n d a r dd e f i n i t i o n t e l e v i s i o n ) 和高清晰度数字电视( h d t v ：h i g h d e f m i t i o nt e l e v i s i o n ) ，码率分别约为 4 4 m b p s 和2 0 m b p s 左右。数字电视的优势和特点主要表现在5 个方面： 1 ) 清晰度高、音频效果好。由于数字电视全过程采用数字信号，不受节目编辑、 传输、转播和接收的影响。s d t v 数字电视节目可以达到d v d 质量，在观看h d t v 节目时清晰度是目前电视的4 倍以上，如3 5 1 u n 电影般清晰。 2 ) 频带利用率高。原p a i 颜道可播放4 到8 套标清数字电视。 3 ) 抗干扰性能好。解决了模拟电视中的闪烁、重影、亮色互串等问题；可以实 现城市楼群的高质量接收，移动载体中也可接收到清晰的数字电视节目。 4 ) 便于开展各种综合业务和交互业务( 包括因特网业务) ，有利于构建“三网合 一”的信息基础设施。 5 ) 节目的加密处理等应用。 d m b t 是我国自主知识产权的数字电视地面传输国家标准，它的制定和提 出对我国高新技术产业的发展和相关民族产业的振兴有着深远的影响。该标准定 义了在5 2 m h z 8 6 6 m h z 频段中，每8 m h z 数字电视频带内，地面数字电视广播 无线传输信号的规范。该系统不但具有传统电视广播服务的基本功能，还具有适 应新一代多媒体广播服务的可扩展功能，可支持固定( 含室内、外) 接收和移动( 含 便携手式) 接收两种模式。在固定接收模式下，可以提供标准数字电视业务、高 北京邮电大学硕士学位论文 清晰度电视业务、数字声音广播业务、多媒体广播和数据服务业务；在移动接收 模式下，可以提供标准数字电视业务、数字声音广播业务、多媒体广播和数据服 务业务。 系统发送端完成从m p e g t s 传送码流到地面电视传输信道的基带信号的转 换。输入数据码流经过扰码器( 随机化) 、前向纠错编码( b c h + l d p c ) ，然后进行 比特流到符号流的星座映射，再进行交织后形成基本数据块。基本数据块与系统 信息组合( 复用) 再经过帧体数据处理形成帧体。帧体与相应的帧头( p n 序列) 复接 为信号帧( 组帧) ，最后经过基带后处理形成输出信号( 8 m 带宽内) 。该信号经变频 形成射频信号( 5 2 m h z 8 6 6 m h z 频段范围内) 【1 】。下图所示为d m b t 系统原理框 图及参数图。 数 l 帧头i c 帧 基正 体 组 带 交 复数 帧 后上 用据 处变 处 理频 理 图1 - 1d m b - t 系统发送端原理框图 x t s + x 1 4 + l q p s k1 6 q a ml 系统ll 扩频 _-。_。_-_。_。_-_。_。_一。_一 复位：信号帧i 3 2 q a m ( 星座不同) ll 信息il 编码 t s 流 蓑h 咎h 蛊 姜嘉h 萎曩h _ ji _ j l 皇 时域卷积交织( 5 2 2 4 0 ) ( 5 2 7 2 0 ) 频域交织( 多载波时选 用) 多载波：n = 3 7 8 0i d f t 变换 单载波：n - - i 插入双导频( 可选) 图1 - 2d - t 系统发送端系统参数框图 频 出 图1 - 3d m b - t 系统接收端系统参数框图 2 习 北京邮电大学硕士学位论文 1 2 差错控制技术 差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传 输特性不理想及噪声的影响，接收端所收到的数字信号不可避免地会发生错误。 为了在已知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信 号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降低。但实 际上，在许多通信系统中的比特误码率并不能满足实际的需求。此时则必须采用 信道编码( 即差错控制编码) 才能将比特误码率进一步降低，以满足系统指标要 求。 差错控制随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编 码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种存储器中也 得到日益广泛的应用。差错控制编码的基本实现方法是在发送端将被传输的信息 附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联 ( 约束) 。在接收端，一旦收到的数据发生差错，信息码元与监督码元之间既定的 关系就会遭到破坏，接收端就可以发现错误乃至纠正错误。因此，研究各种编码 和译码方法是差错控制编码所要解决的问题。编码涉及到的内容也比较广泛，线 性分组码、交织码，卷积码、t u r b o 码等都是差错控制编码的研究范畴。 1 2 1 信道编码理论及其发展 根据香农( s h a n n o n ) 信息论 2 1 1 3 1 提出的信道编码定理，任意离散输入无记忆 平稳信道存在信道容c ，它标志着信道传输能力的上限，只要信息传输速率r 小于c ，就存在一种编码方式，当平均码长足够大时，译码错误概率可以做到任 意小；反之，则无论采用何种编码方式也不可能保证错误概率任意小。该定理虽 然没有明确指出如何对数据信息进行纠错编码，也没有给出这种具有纠错能力通 信系统的具体实现方法，但它莫定了信道编码的理论基础，从理论上指出了信道 编码的努力方向。 随着纠错编码理论的不断完善和超大规模集成电路( v l s l ) 的迅速发展，信道 编码已成功应用于各种通信系统中，而且在计算机、磁记录和数据存储等方面也 得到了日益广泛的应用。 信道编码的基本思想是：通过对发送端信息序列作某种变换，使原来彼此独 立，相关性极小的信息码元产生某种相关性，在接收端利用这种相关性来检查并 纠正信息码元在信道传输中所发生的差错。 在差错控制系统中使用的信道编码可以有多种。按照纠错编码的不同功能， 可以将其分为检错码、纠错码和纠删码；按照信息码元和附加监督码元之间的关 3 北京邮电大学硕：l 学位论文 系可分为线性码和非线性码；按照信息码元在编码后是否保持原来的形式不变， 可划分为系统码和非系统码；按照纠正错误类型的不同，可分为纠正随机错误的 编码和纠正突发错误的编码；按照信息码元和监督码元之间的约束方式不同可划 分为分组石l - a j ( b l o c kc o d e ) 和卷积碉j ( c o n v o l u t i o n a lc o d e ) 。 1 2 2u ) p c 码的发展 l d p c 码是一种基于稀疏矩阵的奇偶校验码。g a l l a g e r 于1 9 6 2 年首先发明 了这种码，故又称g a l l a g e r 码f 4 1 。由于当时的计算机处理能力与相关理论的薄 弱，这种优良的码型没有在科学界引起足够的重视。随着八十年代末，应用迭代 译码思想的t u r b o 码展现出优良的性能，科学家开始重新审视l d p c 码。1 9 9 5 年m a c k a y 和n e a lf 5 1 发现l d p c 码的性能足可以和t u r b o 码【6 1 相比，并且它描 述和实现简单，对严格的理论分析具有可验证性，译码复杂度低于t u r b o 码，可 并行计算，适合于硬件实现，具有高速译码潜力，于是他们重新介绍了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 码，性能好于规则l d p c 码。 目前，l d p c 在国际上已经形成了较为完备的理论体系。t a n n e r 图【7 】与和积 算法【8 1 为l d p c 提供了图论模型，成为l d p c 的现代解释工具。通过图形优化 l d p c 成为一个新的研究角度。译码算法引用人工智能领域中的b p 算法【9 】，成 为l d p c 码的一个亮点。科技人员已经开始全力研究如何更有效的应用u ) p c 码。目前，l d p c 码已被应用在多个领域内，如无线局域网i e e e 8 0 2 1 1 、地面广 播传输系统d v b $ 2 1 1 0 和d m b t 【1 】等等。可以预见，在未来的几年里，l d p c 码将成为纠错领域中的一个里程碑。 1 3f p g a 设计方法介绍 自从1 9 8 4 年美国x i l i n x 公司率先发明v p 6 a ( 现场可编程门阵列1 器件以来， f p g a 技术随着c m o s 工艺的提高而日渐成熟。f p g a 的结构类似于掩膜可编 程门阵歹i j ( m p g a ) ，由逻辑功能块排列成阵列组成，并由可编程的内部连线连接 这些逻辑功能块来实现不同的设计。f p g a 器件集成度不断增大，器件价格不断 下降的趋势，以及其现场设计、现场修改、现场验证、现场实现的可达数百万门 级的数字系统单片化的应用优势，逐渐受到各国电子系统应用领域的设计工程师 广泛的关注和欢迎。时至今日，f p g a 技术已不再是a s i c ( 专用集成电路) 技术领 域的一个点缀和补充。f p g a 技术不仅可以避免通常a s i c 单片系统设计周期长， 前期投资风险大的弱点，而且克服了过去板级通用数字电路应用设计的落后、繁 4 北京邮电大学硕士学位论文 琐和不可靠性，而跃之为电子应用( 包括通信技术、计算机应用、自动控制、仪 器仪表、a s i c 设计) 领域广受欢迎的技术，成为数字系统的科研实验、样机测 试、小批量产品的即时实现的最佳途径。正式在这样的技术应用背景下，f p g a 及其应用技术在全世界范围内，成为了电子系统设计领域的热门技术。 本论文在f p g a 设计中采用了a l t c r a 公司s t r a t i xi i 系列中的e p 2 s 9 0 f 1 0 2 0 c 5 芯片，图1 4 给出了本论文在f p g a 设计实现过程中的流程以及在设计的各个阶 段所用到的e d a 工具。 图1 4 f p g a 设计流程 1 ) 对应用数字系统的设计思想进行描述( 本设计采用v e f i l o g h d l 语言) ，具 体的就是描述要实现的功能和技术要求。 2 ) 进行逻辑功能仿真，验证已描述的系统功能的可实现性。若功能不能实 现，需重新修改描述文件。 3 ) 对数字系统的逻辑功能描述进行综合，产生门级的逻辑电路图，并对其 进行逻辑化简和优化。 5 北京邮电大学硕士学位论文 4 ) 制定约束文件，对具体f p g a 器件进行布局布线，得到包含延时信息 的s d o 文件。 5 ) 使用布局布线后的器件给出的模块和连线的延时信息s d o 文件作时序仿 真，在最坏的情况下对电路的功能作出更准确的估计。如果功能不能实 现，需重新修改描述文件。 6 ) 生成码流文件，进行硬件调试。 从图1 2 中可看出，f p g a 模块设计流程主要由两大主要功能部分组成： 1 ) 设计开发：即从编写设计文件一综合_ 布局布线_ 下载生成这一系列步 骤。 2 ) 设计验证：也就是进行各种仿真的一系列步骤，包括编写设计文件后的 功能仿真以及布局布线后的时序仿真，如果在仿真过程中发现问题应返 回设计输入进行修改。 1 4 设计目标和论文组织 本论文主要研究了d m b t 系统中的l d p c 码的译码算法，并研究使用f p g a 来对以上算法进行硬件实现，利用a l t e r a 公司的s t r a t i xi i 系列器件 e p 2 s 9 0 f 1 0 2 0 c 5 芯片完成硬件测试。 本文的第二章讲述了l d p c 码的基本原理，这样可以便于以后几章的理解。 第三章阐述了d m b t 系统中l d p c 码的特点，并分析了其构造方法。 第四章对d m b t 系统中l d p c 码的译码算法进行了详细的研究，并对算法 采用m a t l a b 和v c 软件进行性能仿真和分析。 第五章设计了一种支持多码率多种调制方式的l d p c 译码器的f p g a 硬件 结构。 第六章是对全文的总结。 6 北京邮电大学硕士学位论文 第二章l d p c 码基本原理 l d r , c ( l o wd e n s i t yp a r i t yc h e c k 低密度奇偶校验1 码最初由g a l l a g e r 在1 9 6 2 年提出【4 】，它是基于稀疏校验矩阵的线性分组码。由于当时技术条件的限制， 人们的兴趣大都集中在有实现可能的编码方式上，如卷积码、级联码等，以致 l d p c 码在很长一段时间内几乎被人们遗忘。直到1 9 9 6 年，m a c k a y 和n e a l 5 】 随机构造出的l d p c 码当码长很长时在性能上超过了b e r r o u 6 等人提出的t u r b o 码，而且在实现上更有优势，从而激起了编码界对l d p c 码的研究热情。目前， 国内外对l d p c 码的理论研究和工程应用都有了重大进展。 本章主要从以下几个方面介绍l d p c 码：首先介绍u ) p c 码的定义和t a n n e r 图表示；接着介绍了l d p c 码的构造方法，最后介绍了l d p c 码的译码方法和 消息传递策略。 2 1l d p c 码的定义 u ) p c 码是一种线性分组码，可以用生成矩阵g 和校验矩阵h 来表示。u ) p c 码又是一类特殊的线性分组码，特殊性就在于它的奇偶校验矩阵h 中非零元素 的个数远远小于零元素的个数。 g a l l a g h c r 定义的l d p c 码，其校验矩阵中每一列包含屯个非零元素，每一 行包含以个非零元素，若码长为，则可记为( ，d d 。) 。在校验矩阵h 中， 每一行和每一列中1 的数目是固定的。任意两行( 或两列) 之间1 的重叠数目小于 等于1 ，这称为行列约束( r o w c o l u m nc o n s t r a i n t ，r c 约束1 。图2 1 是由g a l l a g h e r 构造的一个( 2 0 ，3 ，4 ) l o i c 码的校验矩阵，它的d 。；。= 6 ，设计码率为1 4 ，实际码 率为7 2 0 。 琦鸷鱼再一，- 000o1 00001 0 0001 0 0 o o 1 111 ；0000i 0000 0000 000o ；111 1 ；0000i 0 000 000o ；00001 0000 j1 111 00 0 0 0000i ooo0i 0000i 0000i11 1 1 1000 ；1000 ；1000 ；1000 ；00 0 0 0100 ；0100 ；0100 00 00 ；10 0 0 0010i 0010i 000 0j 0100i 010o 0 oo1 ：0000 ：001o ：0 010 ：0 010 0000 ；00 01i 0001i 00 01i 0001 r 矿而i 矿t 百可w 而1 可几旷矿百阿1 可石 0100 ：0 010 ：0010 ：0 0 0 1 ：0 000 0010 ；0001 ；0000 ；10 00 ；0010 0001i 000 0i1000 0100 ；10 0 0 00001000j 0100 i 0010 0001 图2 1n = 2 0 、c i v 暑3 、d c = 4 规则l d p c 码校验矩阵 7 北京邮电大学硕士学位论文 这种校验矩阵每行和每列中1 的数目( 汉明重量) 相同的l d p c 码称为规则 l d p c 码( r e g u l a rl d p cc o d e ) 。 2 2l d p c 码t a n n e r 图表示 l d p c 发展到9 0 年代，出现了新的表示方式：因子图表示，即t a n n e r 图。 设l d p c 码的校验矩阵h 为一个m x n 阶的矩阵，该矩阵可以由t a n n e r 图表示。 图的下边有n 个节点，每个节点表示校验矩阵的列，称为变量节点( v a r i a b l e n o d e ) ：上边有m 个节点，每个节点表示一个校验集，称为校验节点( c h e c kn o d e ) ： 与校验矩阵中1 元素相对应的上下两个节点之间存在连接边，我们将这条边称 为两端节点的相邻边，相邻边两端的节点称为相邻点。每个节点相邻边数称为该 节点的度数。 对于规则的l d p c 码来说，校验矩阵中每一行和每- n 中1 的个数各自相 同，对应的t a n n e r 图中上边节点度数和下边节点度数分别对应着一个固定值。 图2 2 为( 2 0 ，3 ，4 ) 的t a n n e r 图表示。下边的比特节点的度数为3 ，上边校验节点的 度数为4 。 z ：z 2z ：h 乙z x lx 2 - - x n 图2 - 2 ( 2 0 ，3 ，4 ) 规则l d p c 码的t a n n e r 图表示 上图的下方每一个节点x n 代表的是变量节点，上方每一个节点z m 代表 的是校验节点。在校验矩阵h 中，某列x n 中有若干个非零元素，例如对于x 2 列，这列中三个1 分别对应于z l 、砀和z 1 2 行，这样就在t a n n e r 图中把x 2 和 z l 、乙和z 1 2 连接起来。从行的角度考虑，把某一行z m 中非零点处的) ( n 相 连，得到同一个t a n n e r 图。在规则l d p c 码中，与每个变量节点相连边的数目 是相同的，校验节点也具有相同的特点。在译码端，把与某一个校验节点z m 相 连的x n 求和，结果若为0 ，则无错误发生。 与规则l d p c 码相对应的是非规则l d p c 码( i r r e g u l a rl d p cc o d e ) 1 1 ， 8 北京邮电大学硕上学位论文 其校验矩阵h 中每行中1 的个数不同，每列中1 的个数也不一样。其编码方法 与规则l d p c 码基本相同，非规则l d p c 码的t a n n e r 图中变量节点之间、校验 节点之间的度有可能不同，是一个变化的值。非规则码的性能要好于规则码，最 近几年的研究表明，对于在6 f ( 8 ) 构造的非规则码，它的性能要比t u r b o 码还好， 能够显著提高码字性能，其性能非常接近于s h a n n o n 限。 2 3l d p c 码的译码算法 最大似然概率译码无疑是二进制信道的最佳译码方案，译码错误率也是使用 最大似然概率译码来分析的，然而在实际应用中，尤其是当码长较大时，这种方 案需要的硬件复杂度，存储器个数和时延是难以承受的。为解决这类问题，u ) p c 的发现者g a l l a g e r 于1 9 6 3 年提出了两种古典的译码方案1 1 3 1 ，前者基于硬判决， 后者基于软判决。g a l l a g e r 文中给出的迭代译码算法，经过后来的学者不断的改 进和演化，形成了今天的和积( s u m p r o d u c t ) 算法【8 1 。 2 3 1 古典译码方案 1 硬判决方案 译码器输入为硬判决获得的初始值1 1 或0 ，译码器计算所有的校验矩阵， 如果某个b i t 参与的校验方程出现了错误，并且数目超过一个预定值，就改变这 个比特的值。计算完整个分组的所有比特后，再用改变后的值进行下一轮计算， 直到所有的校验方程都满足为止。 如果校验方程的监督比特较少，那么这个方案很可行，因为大多数校验方程 就只会含有一个传输错误，或无错。因此，当一个比特参与的大多方程都出错， 那么这个比特错误的可能性非常大。 2 软判决方案 软判决方案中，译码器计算值是某一个比特为0 或者为1 的概率。码字集 合为s ，发送序列为 x ，接收序列为 y ，则第d 个比特为1 的概率为 p r i x d - - - l l y ，s 】，为o 的概率为p r x d = o l y ，s 】= 1 一p r 【x d = 1 l y ) ，s 】。 阐述其算法时，先引入一个g a l l a g e r 定理： 定理l ：只代表经过信道传输后第d 个比特为1 的初始概率( 跟信道本身性 能相关) 。对于( n ，j ，k ) 的规则l d p c ，昂代表在第f 个校验方程中第，个校验比特 为1 的概率，那么有： 9 北京邮电人学硕上学位论文 糕p r x d 糊一半i j l 器k - i 端 1l 船1 ， - 1 i y ，s 】只i i1 一兀一2 晶) i p 叫 通过定理1 ，我们可以得到每个比特为1 或为一0 的概率的相对值，如果比值 大于1 ，在本次迭代中判定为一0 ：如果比值小于1 ，则判定为1 1 。经此一次迭代， 分组中每个比特的概率值都会得到刷新，得到缸) 。用这个序列与h 相乘，如果 为0 ，则译码成功。否则用缸) 进入下一轮迭代，系统设定最大迭代次数，如果 超过这个次数还不成功，则放弃继续译码。 2 3 2 现代译码方案 l d p c 发展到9 0 年代出现了新的表示方式t a n n e r 图表示，并且通过把 智能网络中的b p ( 置信度传播算法) 算法引用到l d p c 中来，成为l d p c 的现 代译码方案，即和积算法【8 】。 2 3 2 1b p 算法概述 和积算法与t a n n e r 图紧密结合在一起，如图2 3 ，各边上传递的消息叫做 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 方法。 1 p i x n p ； 图2 - 3 信度传播译码的t a n n e r 图表示 1 m e s s a g e 的含义 如图3 1 所示，假设：比特0 映射为+ 1 ，则x = + 1 ；比特1 映射为1 ，则x - - 1 。 c h e c kt ov a r i a b l e ：尺二( a = + 1 或a = 1 ) 是校验节点z 。向变量节点x 传递 的校验信息，表示z 。根据除外其他相邻变量节点 以：k n ，k n ( m ) ) 1 0 北京邮电大学硕上学位论文 当前状态向宣称的“毛一a 使z 。满足”的可信度； v a r i a b l et oc h e c k ：既( a = + 1 或a = - 1 ) 是变量节点x n 向校验节点z ，传递 的变量信息，表示工。根据除z 。外其他相邻校验节点 乙：l 细，1 m ( n ) 和初始概率消息耳向z 宣称“z 。- a ”的可信度。 2 和积算法迭代过程 初始化：计算初始消息 砰】i 和初始化 q 二i ； 迭代消息传递和更新： 阶段1 ：各个工节点向其所有相邻校验节点z 传递已更新的消息q 二i ， 而各个z ，节点根据接收消息更新尺j ：- l ( 校验节点更新) ： 阶段2 ：各个只和z 节点向其所有相邻变量节点分别传递消息写和 吒，而各个节点根据接收消息更新q 二( 变量节点更新) 。 迭代终止：x 。节点根据所有接收消息计算最终消息q ：。 3 l d p c 码译码一般采取的迭代终止策略 每轮迭代结束时，计算最终消息并根据不同消息量度判决工，计算伴随 式r 日r ； 如果伴随式为零向量，则宣告成功，终止迭代；否则取前一次计算得出 的值，转到第二个步骤继续迭代。若迭代次数达到预先设定的最大次数 ，一仍未成功，则根据最终消息判决得x ，终止迭代，译码不成功。 2 3 2 2 概率测度下的b p 算法 根据上述和积算法中对消息传递和更新过程的分析，在概率测度下，变量消 息定义为q 二靠- - 2p 瓴m ai ) ， z ，：z m o ) 朋) ) ，校验消息定义为 1 吃- p ( z _ l 工- a ) ，设码字先验等概，则初始概率消息耳- p ( x - ai y 。) 。设 码长为1 1 的l d p c 码工一o l ，x 2 ，h ) b p s k 调制后并通过a w g n 信道，在接收 北京邮电大学硕士学位论文 端得到序列y o ，y ：，) ，) ，其中y - 1 2 x 。+ y ，服从均值为0 ，方差为 o 2 的随机变量，下面给出各种公式的推导。 既眠i 庸拒川、肌沪惹警慧掣 盟t a i ! 。) p ( z ，：z m o ) m ) i y 。，戈一口) i 以亿：l e m ( n ) 研 i y ) 眠口n ，尸( z ，i - a ) ，詹( j ；n 恼 尸( t 乙：，e m 加) 胁 ) - 口一砰职： 式 既i p ( z 詹l - 口) 一p ( z 麻，z i ；口) 一p ( z _ l 吒- 口，x ) p ( x l x 一4 ) i ，三尸l 工) 即j 叫- p ( z i z 诹盹) i ，三尸i z 诹、，璐 式( 2 - 3 ) 例如：假设第m 个校验方程为x 2x x 3 屯- + 1 。计算毛= + 1 时满足这个校验 方程的概率： 月j ：1 2 一mp x 2 z 3 x s = + z l x 2 = + 1 ，x 3 = + 1 ，x 5 = + 1 ，q 二；q 二： + p x 2x 工3xx 5 = + l l x 2 = + 1 ，x 3 = + 1 ，x 5 = 1 ) q 二：q ： + p x 2 z 3 x 5 = + 1 l 工2 = + 1 ，x 3 = - 1 ，x s = + 1 q 二；q 二： + p x 2 x x 3xx 5 = + 1 i x 2 = + 1 ，屯= - 1 ，x 5 = - 1 q ：；q