（信号与信息处理专业论文）基于dmbth的ldpc码编译码器的研究与设计.pdf

摘要 摘要 自从1 9 4 8 年香农开创了“信息论与编码理论以来，信道编码技术已经成为 通信领域中一个重要的部分。香农理论指出了可靠通信的一个理论上限，几十年 来业界的大部分努力都是在寻找复杂度上适合硬件实现，性能上逼近理论极限的 信道编解码技术。低密度奇偶校验码( l o w d e l l s i t yp 撕妒c h e c kc o d e s ) 以其优异的 性能和广阔的应用前景，成为信道编码技术研究的热点。中国的数字电视地面广 播标准( d m b t h ) 和移动多媒体系统( c m m b ) 以及新一代数字卫星广播标准 v b s 2 ) 都采用l d p c 码作为纠错码。中国数字电视地面传输标准中采用b c h 和 l d p c 码作为前向纠错码，其中l d p c 码为内码，b c h 码为外码。 本文在研究国标中的纠错码基础上，主要针对l d p c 码的编译码器设计和硬 件实现进行了较深入的研究，具体包含下面几个方面的工作。 首先简单阐述了差错控制技术和数字电视技术的相关概念，以及l d p c 码的 基本原理和常用的译码算法。在研究国标中l d p c 码性质的基础上，设计实现了 支持国标中三种码率的基于移位寄存器累加和算法的l d p c 编码器。本文设计的 多码率编码器采用编码电路复用技术，减少了编码器消耗的资源，与传统的编码 器相比，耗费资源较少，并且支持三种码率，有较好的性价比。通过仿真验证， 本文设计的编码器满足国标的要求。 接着仿真了国标中u ) p c 码基于各种译码算法的译码性能，结果表明，b p 算 法性能最好，最小和算法性能比b p 算法低o 7 1 1 d b 左右，本文采用归一化最小 和算法作为译码算法，在归一化系数为o 6 2 5 ，迭代2 0 次时，性能距b p 算法仅 o 0 5 d b 0 1 d b 左右。根据校验矩阵的准循环特性，本文设计的译码器采用部分并 行的译码结构，在资源和速度方面有较好的折中。在设计了译码器的整体结构的 基础上，重点设计实现了译码器的关键模块，包括变量节点处理单元、校验节点 处理单元和存储器设计，并对校验节点处理单元做一定的优化，相比优化前节约 了一半的资源。 关键字：低密度奇偶校验码编码器译码器归一化最小和算法 a b s t r a c t a bs t r a c t e v e rs i n c e19 4 8t h ef o u n d a t i o no f ”i n f o r n l a t i o na 1 1 dc o d i n gt h e o r y ”b ys h a n n o n ， m ec h a l l i l e lc o d i n gt ec _ l l i l o l o g yh a sb e c o m ea i li m p o r t a i l tp a no fc o m m u n i c a t i o n s a s s h a n n o n st h e o r yo n l yp o i n t so u tt h et h e o r e t i c a l l i m i to fr e l i a b l ec o m m u n i c a t i o n s ，f o r s e v e r a ld e c a d e st h er e s e a r c h e r sh a v eb e e nm a i n l y f o c u s i n g o n f i n d i n g c a p a c i t y - a p p r o a c h i n gc o d e sa n dd e c o d e r sw h i c ha r ef i tf o rh 莉w a r ei m p l e m e n t a t i o n n o w a d a y s ，l o w - d e n s i t yp 耐妒c h e c kc o d e si sb e c o m i n g a l li m p o r t a n t t o p i c i n e 啪r - c o n e c t i n gc o d e s ，b e c a u s eo fi t so u t s t a i l d i i l gp e r f o m a l l c e 强d 伊e a ta p p l i c a t i o n p o t e n t i a l l d p cc o d ei su s e da se n o r - c o n e c t i n gc o d e si n c h i n a st e r r e s t r i a ld i g i t a l m u l t i m e d i a ”胁a n d l eb r o a d c a s t i n g ( d m b t h )a l l dc l l i n am o b i l em u l t i m e d i a b r o a d c a s t i n g ( c m m b ) ，a sw e l la sm en e x tg e n e r a t i o no fd i 百t a ls a t e l l i t eb r o a d c a s t i n g s t a n d a r d ( d v b s 2 ) t h ed m b t hs t a l l d a r du s e sl d p c - b c hc o n c a t e n a t e dc o d e sa si t s t o 刑a r de n o rc o n e c t i o nc o d e s i nt h i sp 印a r e rr e s e a r c l l i n gm ee r r c i rc o n e c t i o nc o d e s ，w ep r e s e i l tm ee n c o d i n g a n dd e c o d i n ga l g o r i t h m sa n dt h eh a r d w a r ei n l p l 锄e n tf o rl d p cb a s e do nd m b - 1 h f i r s to fa l l ，as i m p l ei n t r o d u c t i o nt oe r r o rc o r r e c t i o nt e d m 0 1 0 9 y ，d i 西t a lt v ，m e b a s i cp r i n c i p l e so fl d p cc o d ea i l dd e c o d i n ga l g o r i t l ni sp r o p o s e d t h e nam u l t i r a t e m e m o r y - e 伍c i e n te i l c o d e r f o rl d p cc o d e si s p r o p o s e d i nt 1 1 i sp a p e rb a s e do n s h i r r e 百s t 小a d d 昏a c c u m u l a t o r ( s 融蚣) 1 1 1 es 黜认a l g o 珊l i i ls i m p l 语e st l l ee n c o d c r c o m p u t a t i o nm o d u l ea 1 1 d r e d u c e s l ec o m p l e x i t yo fm eo p e r a t i o n t h em u l t i r a t e e l l c o d e rr c u s e sm es r a ac i r c l j i t st oc u td o w nt h en u m b e ro fr e s o u r c ec o n s 啪p t i o n s i m u l a t i o n sd 咖o n s 仃a t et h a tt h ep r o p o s e dm u l t i r a t e 饥c o d e rc a ns a t i s 矽m ed m b t h w i t h1 0 w e rc o m p l e x i t y t h e nw ed os o m es i m u l a t i o n so nd e c o d i n gp e 而m a l l c eo fl d p cc o d e su s i n ga v 撕e t yo fd e c o d i n ga l g o r i t h m s ，a i l ds i m u l a t i o n ss h o wt h a tt l l ep e r f o m a n c e o fm e m i n s u ma l g o r i t h mi sw o r s e0 7 1 1 d bt h a nb pa 1 9 0 r i t h l n a sar e “t ，w eu s em e m o d i f i e dm i n - s u ma l g o r i t h mm a ti sc a l l e dt h en o m a l i z e dm i n s u ma l g o r i t h i na st h e d e c o d i n ga l g o r i t l u l l w i mn o m a l i z e dc o e 衔c i e n to 6 2 5 ，2 0i t e r a t i o n s ，t h ep e 墒r n l a n c e i so m vw o r s ea b o u to 0 5 d b o 1d bt h a i lb pa l g o r i t h m b e c a u s en l ec h e c km a t r i xi s i i a b s t r a c t q u a s i c y c l i c a l ，t h ep a n i a lp a r a l l e ld e c o d e rs t m c t u r ei sp r o p o s e dt h a tm a k e sab e t t e r c o m p r o m i s ei n r e s o u r c e sa n ds p e e d a r e rt h ed e s i 印o ft h eo v e r a us t m c t u r eo ft h e d e c o d e r ，w ef o c u so nt h ed e s i g na n di m p l e m 朗to ft h ek e ym o d u l e so ft h ed e c o d e r ， i n c l u d i n gt h ev a r i a b l en o d ep r o c e s s i n gu n i t ，c h e c kn o d ep r o c e s s i n gu n i ta i l dm e m o r y d e s i 盟t h ei m p r o v e dc h e c kn o d ep r o c e s s i n gu n i ti nt h i sp a p e ro n l yc o n s u m e sa b o u t h a l f o f t h er e s o u r c e so f t h en o n n a lo n e k e y w o r d s ：l d p c ，e n c o d e r ，d e c o d e r ，n o m a l i z e dm i n s u ma l g o r i t h m i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 么趣窆日期：z 7 年弓月侈目 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：纭鹦导师签 日期： 第一章绪论 第一章绪论 本章为绪论，首先简单介绍通信系统中的差错控制技术，包括信道编解码技 术和l d p c 码的现状与发展，然后概述数字电视技术的发展，最后给出本文的主 要内容和结构安排。 1 1 差错控制技术 差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传 输特性不理想及噪声的影响，接收端所收到的数字信号不可避免地会发生错误。 为了在己知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信 号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降低。但实 际上，在许多通信系统中的比特误码率并不能满足实际的需求，此时则必须采用 信道编码( 即差错控制编码) 才能将比特误码率进一步降低，以满足系统指标要求。 1 1 1 信道编码简介 1 9 4 8 年，美国贝尔实验室的香农( c l a u d ee s h a n n o n ) 发表了题为通信的数学 理论，标志着信息论与编码理论这一学科的诞生【l 】。香农在该文中指出，任意的 通信信道都存在一个参数c ，称之为信道容量，如果通信系统的传输速率r 小于c ， 则存在一种编码方法，当码长n 充分长，译码采用最大似然译码时，系统的差错 概率可以达到任意小，这就是著名的信道编码定理。该定理的数学证明解决了好 码的存在性问题，为后人用构造性方法去寻找好的纠错码指明了方向。信道编码 的基本思想是：通过对发送端信息序列作某种变换，使原来彼此独立，相关性极 小的信息码元产生某种相关性，在接收端利用这种相关性来检查并纠正信息码元 在信道传输中所发生的差错。按照信道编码的不同功能，可以将纠错码分为检错 码、纠错码和纠删码；按照信息码元和附加监督码元之间的关系可分为线性码和 非线性码；按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和 非系统码；按照纠正错误类型的不同，可分为纠正随机错误的编码和纠正突发错 误的编码；按照信息码元和监督码元之间的约束方式不同可划分为分组码( b l o c k c o d e ) 和卷积码( c o n v o l u t i o n a lc o d e ) 。 1 电子科技大学硕士学位论文 1 1 2l d p c 码简介 1 9 9 6 年m a c k a y 、s p i e l m a n 和w i b e r g 几乎同时发现：g a l l a g e r 早在1 9 6 2 年提 出的低密度校验码( l o wd e n s i t yp a r i t yc h e c kc o d e ，l d p c 码) 【2 】是一个好码，具有更 低的线性译码复杂度【3 】。人们的进一步研究表明：基于非规则双向图的l d p c 长码 的性能可以优于t u r b o 码，而且这样的码的性能非常接近s h a n n o n 限。其中的一 个原因在于l d p c 码具有较好的距离特性。由于l d p c 码不仅具有良好的距离特 性、小的译码错误概率和较低的译码复杂度，而且适当的码长时，不存在错误平 台，其码率容易调整。实验结果中的错误几乎均为可检测错误。所以l d p c 码无 论在理论上还是实际上都有极其重要的价值，l d p c 码的重新发现是继t u r b o 码之 后在纠错编码领域又一重大突破。s y c h u n g 等研究发现，对于非规则码，在二进 制输入a w g n 信道下，设计的码率1 2 、码长1 0 7 的非规则l d p c 码在错误概率l o 。6 时离s h a n n o n 限仅0 0 0 4 5 d b 4 1 ，这是迄今为止报道出的性能最接近s h a n n o n 限的 信道编码。 近年来，l d p c 码的很多研究成果表明l d p c 码是一种性能优异的好码，比 t u r b o 码在技术上更具有优势，更能适应未来系统的高速数据传输和高性能的要 求。t a n n e r 图【5 】与和积算法【6 】为l d p c 提供了图论模型，成为l d p c 的现代解释工 具。通过图形优化l d p c 成为一个新的研究角度。在译码算法中引入人工智能领 域中的b p 算法，成为l d p c 码的一个亮点。目前，l d p c 码已经应用在多个领域 内，如无线局域网i e e e 8 0 2 1 1 、卫星广播传输系统d v b s 2 和数字电视地面广播 系统d m b - t h 7 1 等等，基于l d p c 编码的方案极有可能成为第四代移动通信系统 的应用方案。可以预见，在未来的一段时间，l d p c 将成为纠错编码领域中的一个 里程碑。 1 2 数字电视技术 1 2 1 数字电视行业的发展 随着电子信息技术的不断发展，电视行业在经历了黑白电子电视和彩色电视 时代以后，目前正在面向数字化和高清晰度方向迅速发展，模拟电视在全世界范 围内正在逐步消退。数字电视技术将带来一场深刻的革命，这不仅仅局限在技术 革命，还将带来广播电视运营体制、管理方式以及用户收听收看电视节目方式的 根本性变革，甚至对整个信息产业的发展产生深远影响。 2 第一章绪论 相对模拟电视而言，数字电视的优势和特点主要表现在清晰度高、音频效果 好、频带利用率高、接收频道多、抗干扰性能好、可用于移动终端接收、节目的 加密处理性能好、便于开展各种综合业务和交互业务，有利于构建“三网合一 的信息基础设施等方面。数字电视的传输存在三种传输的通道：地面、卫星和有 线传输。 地面数字电视广播组织已经提出了三个地面数字电视标准，也是目前世界范 围内采用较多、也较为成熟的三大地面数字电视广播标准【8 】：采用格形编码、八电 平残留边带8 - v s b 调制的a t s c 标准；采用正交频分复用c o f d m 编码调制的地 面数字视频广播d v b t 标准；采用频带分段传输b s t 、正交频分复用o f d m 的 地面综合业务数字广播i s d b t 标准。 1 2 2d m b t h 标准简介 中国数字电视地面传输标准数字电视地面广播传输系统帧结构、信道编码 和调制r 刀，即d m b t h 标准，于2 0 0 6 年8 月1 8 日公布，该标准支持高清晰度 电视、标准清晰度电视和多媒体数据广播等多种业务，突破性地融合了单、多载 波调制技术，满足大范围固定覆盖和移动接收的需要，实现了关键技术创新，形 成了多项有自主知识产权的专利技术。国标中规定了数字电视地面传输系统中最 核心的信号帧结构、信道编码和调制技术，涉及的关键技术有：t d s o f d m 技术、 信号帧的头和帧体保护技术、低密度校验码( l d p c 码) 等。 d m b t h 规定了在5 2 m h z 8 6 6 m h z 频段中，每8 m h z 数字电视带宽内，数字 电视地面广播无线传输信号的规范。d m b t h 系统不但具有传统电视广播服务的 基本功能，而且增加了新一代多媒体广播服务的可扩展功能，支持固定接收和移 动接收两种模式。在固定接收模式下，可以提供标准数字电视业务、高清晰度电 视业务、数字声音广播业务、多媒体广播和数据服务业务；在移动接收模式下， 可以提供标准数字电视业务、数字声音广播业务、多媒体广播和数据服务业务。 相对于其他的数字电视标准，d m b t h 的抗干扰能力较强，主要是采用了l d p c 码与b c h 码的级联作为信道编码技术，具有很强的纠错能力，是国标中的一大亮 点。随着国标的强制执行，目前已经有一些芯片提供商设计了基于国标的信道编 解码器芯片，但由于信道编解码耗费的资源几乎是接收机系统的三分之一，因此， 研究高效率、低复杂度的信道编解码器仍然是一个热点问题，具有重要的实际意 义。 3 电子科技大学硕士学位论文 1 3 论文主要内容与结构安排 l d p c 码具有良好的纠错能力和广泛的应用前景，并作为关键技术应用在 d m b t h 系统中，通过研究d m b t h 系统中的l d p c 码的编解码算法，可以深入 理解l d p c 码的原理和特性，并且对l d p c 在其他信道编码中的应用有一定的指 导意义。 本论文的主要内容是：在研究数字电视地面传输标准中的l d p c 码的性质和 特点的基础上，设计出合适的编解码算法，完成适合国标的l d p c 码编解码器的 研究和设计，主要包含l d p c 编码器和l d p c 译码器两部分内容。 论文的结构和章节安排如下： 第一章为绪论，主要介绍课题相关的差错控制技术和数字电视技术在国内外 的发展现状、本论文的主要内容和结构安排。 第二章概括性地介绍了l d p c 码的基本原理和各种常用的译码算法，分析对 比了各种算法的译码性能。 第三章详细分析了d m b t h 标准中的l d p c 码的性质，重点研究了l d p c 生 成矩阵和校验矩阵的特点，为设计合理的编码器和译码器打下基础。 第四章是本文的重点，在对比常用的各种l d p c 编码方法的基础上，设计出 在效率和资源上适合国标的编码器，在x i l i n x 平台下进行设计和仿真，通过与 m a t l a b 平台下设计的编码器进行编码后的对比，验证了设计的正确性。 第五章是论文的另一个重点，首先设计了基于m a t l a b 平台的l d p c 码的编译 码仿真系统，然后结合d m b t h 仿真了目前流行的各种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 码的基本原理，最后详 细介绍了目前常用的各种l d p c 码的译码算法。 2 1 信道编码基础 信道编码的目的是纠错，常用于数据通信，尤其在无线数据通信中广泛使用， 当自然信道的误码率较高时，使用信道编码技术后可明显降低误码率。在现代通 信系统中，信道编码已经成为必不可少的一部分，无论哪种信道编码方法，都需 要遵循一些基本的定义和定理。 2 1 1 线性分组码的基本原理 线性分组码在纠错码中占有很重要的地位，它的数学模型简单，较易对其进 行性能分析。仳k ) 线性分组码是把信息流的每k 个码元分成一组，通过线性变换， 映射成n 个码元组成的码字。n 是码长，k 是信息位的长度，n - k 是冗余位的长度。 从空间的角度，每个码字可以看成n 维线性空间的一个矢量，n 个码元正是n 个矢 量元素。码元的值取自字符集x = ，五，艺一。 ，当q = 2 时是二进制码，q 2 时是 q 进制( q 元) 码。k 位二进制信息组有2 中组合，构成g f ( 2 ) 上的k 维k 重矢量空间； 而n 位二进制数共有2 “种组合，构成g f ( 2 ) 上的n 维n 重矢量空间，通常2 “ 2 。 纠错编码的任务是在n 重n 维矢量空间的2 “种可能组合中选择2 个构成一个子空 间，称为许用码码集c ，然后设法将k 比特信息组一一对应地映射到许用码码集c 。 不同的编码算法对应不同的码集c 以及不同的映射算法，把这样得到的码称为 k ) 线性分组码，不编码时，一个二迸制码元可携带1 比特信息( 传信率为1 比特符号) ； 编码后n 个二进制码元携带k 比特信息，传信率为( 1 渤) 比特符号。定义k n = r 为 二元分组码的码率p 】。 5 电子科技大学硕士学位论文 2 1 2 生成矩阵和校验矩阵 对于一个( n ，k ) 二进制线性分组码c 而言，它的生成矩阵g 大小为k x 咒，g 的每一行都是一个c 中的有效的码字，由于码c 是n 维向量空间g f ( 2 “) 上的一个 k 维子空间，g 的所有行向量构成了这个k 维子空间的一组基，所以c 中的每一 个码字c 都能用g 的行向量的线性组合来表示。令m ，m 。，m o 是一组二进制信 息码元，它可以看成是在k 维k 重空间中的一个矢量m - ( m kl 一，m 。， n o ) ，也可以 看成一个l x k 的矩阵m 爿m ，m 。，m 。o 编码后，输出的码字长度增加到n ，是k 维n 重码空间c 中的矢量。通常将码字写成通式c ：( q ，c l ，c o ) 。对于线性分组 码，码集c 中任一码字c 的第j 个码元c ，都是信息元m n ，玛，m o 的线性组合， 编码运算可以用n 个方程构成的线性方程组来表示，即 勺= m k l 反t i ) ，+ + ，g i ，g + 岛， ，= 万一1 ，1 ，0 ( 2 - i ) 式中，系数岛 o ，1 ) ，i = k l ，1 ，o 表示第i 个信息元镌对第j 个码元的影响。 线性方程组( 2 1 ) 用矩阵表示为： c = ( 巳- i ，c l ，岛) = m g = m k - i ， ，m o 叶g g i g 。】r ( 2 2 ) 式中，g 称为该码的生成矩阵，是k x n ( k 行n 列) 矩阵： g - - g h g 。g 。】r = & i 1 ) o g i o g o o ( 2 3 ) 其中，g i = m 1 ) g i i 蜀o 】，待k - 1 ，l ，0 ，是g 的第i 行的行矢量。 由( 2 2 ) 可得： c 2 m k i g k i + + g l + m o g o ( 2 - 4 1 可见，任何码字都是生成矩阵g 的k 个行向量的线性组合。 和每个线性分组码相联系的还有一个有用的矩阵，对于任意有k 个线性独立 行的k x n 矩阵g ，存在一个具有n - k 行线性独立的( ，l 一七) 阶矩阵，它使得g 的行空间中的任意向量都和h 的行正交，且与h 的行正交的任意向量都在g 的行 空间中【1 0 1 。因此，我们可以用另一种方法来描述由g 生成的( n ，k ) 线性码：一个n 维向量c 是g 生成的码字中的码字，其充要条件为 6 卜； 死h 。 酝； 蜀岛 开 d 叶 耋： 卜 舻 加踟 第二章l d p c 码概述 c x h r = o r ( 2 5 ) 此时，h 称为校验矩阵，一般情况下，一个他k ) 码的h 矩阵可表示为 h = j l l ，： 吃，： 吃吨。一2 ( 2 6 ) 因生成矩阵g 中的每一行及其线性组合均为( n ，k ) 码的一个码字，所以由上述 式( 2 - 5 ) 可知 g x h r = o ( 2 7 ) 因此，验证h 的方法是看它的行向量是否与g 的行向量正交，若g x h r = o ， 则证明h 确是校验矩阵。 2 2l d p c 码的原理 2 2 1l d p c 码的定义 l d p c 码是一类线性分组码，可以用生成矩阵和校验矩阵来表征，它的奇偶校 验矩阵中“1 的数目远小于“0 的数目，称为稀疏性，它的“低密度 特性也 来源于此。二元l d p c 码的稀疏矩阵是一个0 - 1 矩阵，一个码字是合法的，当且仅 当它与校验矩阵的乘积在模2 加法运算下是一个全零向量。l d p c 码性能可以非常 接近s h a n n o n 限，并且具有小的译码错误概率和较低的译码复杂度。l d p c 码适合 使用长码，码率容易调整。 设码长为1 1 ，信息位为k ，校验位为m - - n - k ，则码率为r = k n ，它的校验矩阵 h 是一个i 1 1 x n 的矩阵。 g a l l a g e ：r 在1 9 6 2 年给出l d p c 码的校验矩阵h 具有以下结构属性： ( 1 ) h 矩阵的每一行有p 个“1 ； ( 2 ) h 矩阵的每- y u 有y 个“l ； ( 3 ) h 矩阵的任意两行( 或两列) 间共同为“1 ”的个数不超过1 ； ( 4 ) 与码长和h 矩阵中的行数相比较，p 和y 都很小，也就是说矩阵中很少 部分元素非零，其他大部分元素都是零，因此，可得l d p c 码的校验矩阵是稀 疏矩阵【1 0 j 。 7 p 丹 k舢咖； 产 ，： 抽 氟岛 ” 电子科技大学硕士学位论文 那么，满足以上四个条件的h 校验矩阵对应的l d p c 码一般表述为( n ，y ，p ) ， 校验矩阵h 有固定的列重y 和固定的行重p 。因为校验矩阵h 有m 行n 列，因此， m 表示码字的校验方程个数，码率r = k n = 1 一g p 。 2 2 2l d p c 码的双向图表示 设l d p c 码的校验矩阵h 为一个m n 阶的矩阵，该矩阵可以由双向图( 也称 t a n n e r 图) 表示。图的下边有n 个节点，每个节点表示码字的信息位，称为信息节 点缸m ，= 1 ，2 ，甩) ，也可称为变量节点，对应于校验矩阵各列；上边有m 个节点， 每个节点表示一个校验集，称为校验节点 z ；，i = l ，2 ，聊) ，代表校验方程，对应 于校验矩阵各行。校验矩阵中“1 元素相对应的上下两个节点之间存在连接边， 我们将这条边称为两个节点的相邻边，相邻边两端的节点称为相邻点。每个节点 相邻的边数称为该节点的度数。每个信息节点与7 个校验节点相连，称该信息节点 的度数为厂；每个校验节点与p 个信息节点相连，称该校验节点的度数为p 。例如： 假设( 1 0 ，2 ，4 ) l d p c 码的校验矩阵为h ，如式2 8 所示，信息节点的度数是2 ， 校验节点的度数是4 ，该校验矩阵对应的双向图如图2 1 所示。 1l11o 1ooo1 日= l0loo1 0 o1 0o 0 o o1o oo oo 0 1loo0 o011o l0101 o1o1l 校验节点 z lz 2z 3z 4z 5 x 1) 2x 3x 4 x 5x 6x 7x 8x 9x 1 0 信息节点 图2 - i ( 1 0 ，2 ，4 ) l d p c 码的双向图 ( 2 8 ) 由上述双向图可以看出，信息节点有1 0 个，对应于如，j = l ，2 ，1 0 ，每个信 息节点有两条边相连，表明信息节点的度数是2 ；校验节点有5 个，对应于 乜，i = 1 ，2 ，5 ) ，每个校验节点有4 条边相连，表明校验节点度数是4 。 8 第二章l d p c 码概述 2 2 3l d p c 码的分类 l d p c 码有多种分类方法，例如按行重、列重是否是定值划分，可以分为规则 码和非规则码；按所在的域划分，分为二元域和多元域的码。下面将分别介绍这 两种分类。 规则l d p c 码和非规则l d p c 码： 若l d p c 码校验矩阵的行重和列重都是某个定值，则称l d p c 码是规则l d p c 码；否则此l d p c 码是非规则l d p c 码。如图2 1 所示的l d p c 码是规则l d p c 码。不规则l d p c 码一般可以表述为( n ，k ) ，如图2 2 所示的( 6 ，3 ) l d p c 码是不 规则的l d p c 码，其校验矩阵为式2 - 9 。 r l 01 1 日= l000 i 010 l 信息节点 图2 2 ( 6 ，3 ) 不规则l d p c 码的双向图 ( 2 - 9 ) 对于非规则l d p c 码，对应的双向图中的各节点的度不相同，通常用度的分 布序列 以，圪， 和 n ，仍，氏 来表示，其中乃表示与度为j 的信息节点相 连的边数占总边数的比率，肛表示与度为i 的校验节点相连第边数占琶整数的比 率，4 和z 分别表示信息节点和校验节点的最大度数，应有乃= 1 和肛= 1 。 边度分布序列可以用多项式来表示，即 产1 扣1 巩 r ( x ) = e y q ( 2 - 1 0 ) 9 ( 2 1 1 ) 1lij q 叫u 馘验 o 1 0 校 0 1 o 卜 万 辟 喜乙耐 l i 、l， x ，i 、 p 电子科技大学硕士学位论文 满足7 ( 1 ) = 乃= 1 和p ( 1 ) = - - l 肛= 1 。规则l d p c 码可以看作是非规则l d p c 码 j = l i = 1 的特例。适当构造的不规则码的性能优于规则码的性能，这一点可以用双向图解 释：对于一个信息节点来说，希望它的度数大一些，因为它从相关联的校验节点 得到的信息越多，便越能准确判断它的正确值，对每一个校验节点来说，刚好相 反，希望校验节点的度数小一些，因为校验节点的度数越小，它反馈给相邻信息 节点的信息越有价值。不规则图比规则图能更好更灵活的平衡这两种相反的要求 【1 1 】。c h u n g 等基于不规则双向图，构造的码率为1 2 、码长为1 0 7b i t 的不规则l d p c 码，经仿真，在误码率为1 0 。0 时，该码的译码性能距香农限仅为0 0 0 4 5 d b ，这是 目前已知的距离香农限最近的码字。 二元l d p c 码和q 元l d p c 码 按照每个码元的取值来分，可分为二元l d p c 码和q 元l d p c 码，研究表明q 元l d p c 码优于二元l d p c 码【1 2 1 。伽罗华域g f ( 2 ) 上的规则l d p c 码推广到 g f ( q ) ( q = 2 ，p 是整数) 上，不同的只是g f ( q ) 上的l d p c 码的校验矩阵h 的非零 元素有q 1 个值可供选择，而不只为“l 。对于二进制l d p c 码来说，如果它的 校验矩阵h 的列重量增大，那么它的性能也增加，但是如果增加列重量会使得 t a n n e r 图中各节点之间的短环数目急剧增加，从而使b p 算法的性能下降。而在 g f ( q ) 域上构造的l d p c 正好可以解决这个矛盾，但不会造成节点之间的循环路径 数目的增加，从而使译码性能得到显著的提高。 2 3l d p c 码常用的译码算法 信道编码的译码算法是决定其性能和应用前景的一个重要因素。线性分组码 的译码复杂度与码长成指数关系，当码长增大到一定程度后，复杂度的增加将是 不可控制的。但由于l d p c 码校验矩阵的稀疏性，使得译码算法的复杂度和码长 成线性关系，克服了分组码在码长较长时所面临的计算复杂度问题。1 9 9 6 年， m a c k a y 和n e a l 提出了b p ( b d i e f p r o p a g a t i o n ) 算法【1 4 j ，也称为s u m - p r o d u c t 算法， 其译码性能比硬判决算法好的多，而相应的运算复杂度也不大。f o s s o r i e r 对低复 杂度的b p 算法作了进一步研究，提出了b p b a s e d 算法【1 5 】，简化了b p 算法。为 了改善b p b a s e d 算法因为校验节点上的简化处理而造成的性能损失，j c h e n 提出 了两种改进算法【1 6 】【1 7 】：采用归一化的b p b a s e d 算法r 亦称为n o r m a l i z e db p b a s e d 1 0 第二章l d p c 码概述 算法) 和通过降低可靠性值来改善外部信息精度的o f f s e tb p - b a s e d 算法。本节将主 要研究b p 算法、b p b a s e d 算法和改进的b p b a s e d 算法。 2 3 1 概率域b p 算法 信度传播( 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 算法。概率域b p 算法时使用的是码字比特的概率值， 一个校验矩阵可以使用一个双向图来表示，沿着因子图中连线传递的似然值不仅 提供了关于比特n 的硬判信息，同时也提供了关于这个硬判值的可信度。 假设b p s k 调制后，每一个码字c = ( q ，c 2 ，一，巳) 映射成传输序列 x = ( 五，恐，毛) ，然后x 通过信道，接受到的序列为y = ( y l ，儿，以) 。根据y ， 译码后得到译码序列6 。 下面将给出一些在迭代译码算法中所使用到的符号的定义【1 8 】： ，f p ) ( b = o 1 ) 表示校验节点j 传给变量节点i 的外部概率信息，即在给定信 息位及其他信息位具有独立概率分布的条件下，校验方程j 满足的概率； q v ( 6 ) 表示变量节点i 传给校验节点j 的外部概率信息，即在得到除j 以外的其 他所有校验节点和信道的外信息后，判断变量节点c = 6 的概率； c ( f ) 表示与变量节点i 相连的校验节点的集合，c ：= 歹：j j l 甜= 1 ) ； r ( ) 表示与校验节点j 相连的变量节点的集合，尺，= 口：j j l 珂= 1 ； c o ) ，表示除j 外与变量节点i 相连的校验节点的集合； 尺( ) f 表示除i 外与校验节点j 相连的变量节点的集合； c h ：包含q 的第j 个校验方程中的第k 个比特； ：对应于的接收值； 只( 1 ) = p r ( q = 1 1 只) ：接收到咒后判断发送比特( 或变量节点) 为c f = 1 的后验 概率； 名= p r ( 勺= 1 i ) ：接收到后判断包含c f 的第j 个校验方程中的第k 个比 特为= l 的后验概率； 墨：中的比特满足包含q 的t 个校验方程。 概率域b p 译码算法的步骤如下( 将消息符号中的上标表示迭代次数) ： 1 初始化 电子科技大学硕士学位论文 计算信道传递给变量节点的初始概率只( 1 ) ，p ( o ) = 1 一只( 1 ) ，江1 ，2 ，z 。然 后对每个变量节点i 和与其相连的校验节点j c ( i ) ，设定变量节点传向校验节点 的初始信息 g 严( o ) = 只( o ) g 严( 1 ) = 只( 1 ) ( 2 - 1 2 ) ( 2 - 1 3 ) 2 迭代运算 步骤( 1 ) ：校验节点信息处理 对所有的校验节点j 和与其相连的变量节点i r ( i ) ，第1 次迭代时，计算变量 节点传向校验节点的信息 f哆( o ) = 吾+ 导兀( i - 2 蚶) 厶q k 吩 ( 2 1 4 ) 伽) = 1 一哆( o ) - 了i 一号n ( i - 2 9 万) l 。 。f e 巧。 步骤( 2 ) ：变量节点信息处理 对所有的变量节点i 和与其相邻的校验节点j c ( i ) ，第1 此迭代时，计算校 验节点传向变量节点的信息 其中，是校正因子，使彰( o ) + q 箩( 1 ) = 1 。 步骤( 3 ) ：译码判决。 对所有变量节点计算硬判决信息 矽( o ) = k 置( o ) 兀，= ：；f ( o ) 竺。 ( 2 1 6 ) 旧( 1 ) = k 只( 1 ) 兀哆( 1 ) “ l 批g 其中k 是校正因子，使得酢，) ( o ) + g ；，) ( 1 ) = 1 。若彰) ( 1 ) 研d ( o ) ，则毒= l ，否 则毒= 0 。 3 停止 若a h r = o 或者达到最大的迭代次数，则运算结束；否则从步骤( 1 ) 继续迭代。 1 2 n 螂n 吼 、，、， ，d 、 ，l， 即 承 v p 国 翰 巧 ) ) 第二章l d p c 码概述 2 3 2 对数域b p 算法 如果概率信思用似然比表示，则得到l l r - b p 算法，即对数域b p 算法。应用 对数，可以使大量的乘法运算可以变为加法运算，从而减少运算时间。为此，需 要定义对数似然比( l l r ) 信息如下： 信道初始信息螂) ：1 0 9 器_ l o g 揣 校验节点传向变量节点的信息) = 1 0 9 嚣 变量节点传向校验节点的信息地护l 。g 等 杰量节点雌。的所有信息地) l 。g 器 通过对b p 算法的化简，可以得到l l r b p 算法的运算步骤： 1 初始化 计算信道传递给变量节点的初始概率似然比信息( 只) ，i = 1 ，2 ，拧。然后对 每个变量节点i 和与其相连的校验节点歹c ( 力，设定变量节点传向校验节点的初 始信息： 影o ( 吩) = ( 层)( 2 1 7 ) 2 迭代处理 步骤( 1 ) ：校验节点信息处理 对所有的校验节点j 和与其相连的变量节点f r ( i ) ，第1 次迭代时，计算变量 节点传向校验节点的信息 鼬( c ，) = p 飘e r ，蛐( ，) 8 ， 二；f二 或者乜) _ 2 劬。1 【，i - t a n h