（信号与信息处理专业论文）数字多媒体广播系统中ldpc码研究与实现.pdf

摘要 摘要 数字多媒体广播系统中l d p c 码研究与实现 硕士研究生：张赞导师：吴乐南教授 东南大学信息科学与工程学院 数字技术的成熟使得多媒体广播获得了生机，如何让用户能够在任何地点任 何状态下( 移动或静止) 享受到多媒体的信息服务一直是通信相关领域专家与技 术人员关心的课题。近年来出现了许多数字移动多媒体广播系统的标准，包括 d 觥- d m b 、d v b - t 、d v b - h 、m 觚a h d 、d r m 、i s d b t 、s t i m i 等，其中欧 洲开发的d a b ，r - d m b 已经在我国开播。 以上数字广播系统的传输都无一例外地采用了先进灼o f d m 技术，主要是发挥 o f d m 系统频谱利用率高、抗干扰能力强和能够获得分集增益的特点。信道编码是 数字通信系统中另一个十分重要的环节，d a b 厂r - d m b 系统采用了纠随机错误的卷 积码和纠突发错误的r s 码的级联，获得了比较好的性能。 由g a l l a g 茁在1 9 6 2 年首先提出的低密度奇偶校验( l d p c ) 码，在沉寂了多 年之后受到t u r b o 码的启发，m a 衄和w i b c r g 等人对g a l l a g 盯鸦重新进行了研究 发现其优异性能，使l d p c 码再次成为通信技术研究的热点。u ) p c 码是一种具有 稀疏校验矩阵的线性分组码，研究结果表明，采用迭代的概率译码算法，【，d 】p c 码 可以达到接近香农极限的性能。 本论文较为系统地介绍了l d p c 码的码字构造、编码和译码算法，重点是u ) p c 译码算法的改进及其在数字多媒体广播系统中的应用。通过仿真，表明l d p c 码的 性能能够超过船与卷积的级联码，这意味着在广播系统中采用u ) p c 码不仅能够降 低译码的复杂度，还能获到更高的编码增益。最后，本文在公司的t m s 3 2 0 6 4 1 6 数字信号处理器上对l d p c 码的译码算法进行了优化。 关键词：l d p c 码，o i d m ，数字移动多媒体广播 目录 a b s t r a c t r e s e a r c ha n d i m p l e m e n t a t i o no fl d p c f o r d i g i t a lm u l t i m e d i a b r o a d c a s t i n gs y s t e m i n f o r m a t i o ns c i e n c e & e n g i n e e r i n gs o h o o ls o u t h e a s tu n i v e r s i t y m u l t i m e d i ab r o a d c a s t i n gf i e l dh a sg a i l ii t sv i t a lf o r c ew i t ht h ef r u i t f u l n e s so f d i g i u at e o h n o l e d g e s i t i st h er e s e a r c hf e c e so ft p e r t sa n de n g i n e e r si n c o m m u n i c a t i o nr e l a t e df i e l df o rs u b s c r i b e r st oa c s sm u l t i m e d i as e r v i c ea ta n y t i m e i ne n y p l a o e r e a c o n ty e a r sm a n ys t a n d a r d sf o rd i g i t a lm o b i l em u l t i m e d i a b r o a d e a s t i n g s y s t e m s cf o r t h , s u c ha sd a b t - d m b ，d v b t ，d v b - h , m e d i a f l o , d r m , i s d b - ta n ds t i v f i ，a m o n gw h i c ht h ed a b t - d m bh a sa h r , a d y b e e nu s e di nc h i n a a l lo ft h ea b o v e d i g i t a lh _ i o 取l 。j 晤斑i gs y s t e m sa d o p tt h ea d v a n c e do f d m t e o h n o l e d g ei no r d e rt o a c h i e v e h i s hs p e c t r u md t i o i e o y , r o b u s t n e s sa g a i n s t i n t e r f e r e n c ea n dd i v e r s i t yg a i n s c h a n n e lc o d i n gi sa n o t h e ri m p o r t a n tp a r tf o rd i g i u a c o m m u n i c a t i o n t h ed a b t - d m bs y s t e m1 1 8 0 8c o n v o l u t i o n a lc o d ea si n n e rc o d e a g a i n s tr a n d o mc r r 懈a n dr so o d ea 8o l 衄o o d ea 母e t l m l tb u r s te l t o r s t h i sk i n do f t r e l l i sc o d ei sa b l et oa c h i e v eh i 曲c o d i s 汹 l o w - d e n s i t yp a r i t y - c h e c kc o d e s ，i sd e f i n e di nt e r m so fv e r ys p a r s oi n a t l i c e s ， a n dc 锄b ed e c o d e db yi t e r a f i v ea l g o r i t h m s i tv mf i r s t i n v e s t i g a t e di n 1 9 6 2b y g a l l a g c r , b a th a db e e nn e a r l yf o r g o t t e nu n t i lm a c k c ya n dw m c r gr e d i s c o v e r e dt h e i r e x c e l l e n tp r o p e r t y o f a c h i e v i n gi n f o r m a t i o nr a t e su p t ot h es h a n n o nl i m i t t h i sd i s s e r t a t i o np r e s e n t sas y s t e m a t i ci n v e s t i g a t i o no fl d p cc o d e si n c l u d i n g c o d eo o n a t r u o f i o n , e n c o d i n ga n dd e c o d i n gm e t h o d s s i m u l a t i o nm s u l t ss h o wt h a tt h e p e r f o r m a n c eo fl d p cc o d e sc o u l de x o e c dt h et r e l l i sc o d e sc o m p o s e do fr sa n d c o n v ，w h i c hm e a l ：l sa p p l i c a t i o no f l d p cc o d e si nd i g i t a lb r o a d c a s t i n gs y s t e m st a i l n o to n l yr e d u o ed e c o d i n gc o m p l e x i t yb u ta l s oa c h i e v eh i g h e rc o d i n gg a 油f i l a i l y l d p c d e c o d i n ga l g o r i t h mi so p t i m i z e d0 1 1t m s 3 2 0 c 6 4 1 6d i g i t a ls i g n a lp r o c e s s o r k e 了w o r d s ：l d p cc o d e ，o 叫d i 萄t a lm o b i l em u l t i m e d i ab r o a d c a s t i n g i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：导师签日期：乏丝z ! ：厂 东南大学硕士学位论文 第一章绪论 本章首先介绍信道编码理论和l d p c ( l o w - d e n s i t yp a r i t yc o d e ) 码的研究现状，然后概 述基于o f d m 系统数字广播的发展，最后给出这次论文的主要内容和结构。 1 1 选题背景与意义 在当今世界四大传播媒体中，报刊、广播、电视、互联网各自凭借自身的优势，拼夺传 媒市场，争占信息领域。报刊作为历史最长的媒体，依然用着传统的方式，坚守着固有的阵 地，并保持着旺盛的生命力；电视凭借数字技术仍然焕发着青春；互联网这个新生儿，正借 助计算机、电子通信和网络技术乳汁的哺育而茁壮成长。广播这个有着近百年历史的媒体， 似乎到了未老先衰、残阳西下的境地。然而数字化的时代正改变着这个世上唯一只用耳朵不 用眼睛的媒体步入光明，新一代数字广播正步入我们的生活。 d a b 是数字音频广播( d i g i t a la u d i ob r o a d o a s t i n g ) 的英文简称f l l ，刨始于欧洲。当时欧洲 人开发d a b 的初衷是改变传统的广播技术，提高声音播出质量和提供高速移动接收性能。因 为传统的调幅( a l 讧) 广播和调频( f m ) 广播，已逐渐不能满足人们的欣赏需求。从1 9 7 0 年 代以来，数字技术就不断地发展和广泛应用，在声音的拾取、记录、复放各方面音响质量都 得到了极大的改善，尤其是1 9 8 0 年代后期c d 唱片的应用和普及，c d 机进入了广大听众的家 庭，提高了听众对音频质量的要求。二是由于广播事业的迅速发展，频段内分配的广播频率 越来越多，各频率间所需的保护间隔越来越难以保证，引起了经常性的邻频或同频干扰。三 是由于交通工具的日趋普及，人们生活节奏变快，途中的移动群体越来越庞大，对移动接收 自然提出了更高的要求。由于以上这些因素，欧洲人开发了d a b 。 d m b 是数字多媒体广播( d i g i t a lm u l t i m e d i ab r o a d c a s t i n g ) 的简称。虽然早期研究的d a b 解决了音质和高速移动接收上的一系列问题，但随着人们物质生活水平的不断提高，信息消 费日趋多元化，仅靠收听高质量的声音广播，已不能满足人们对信息的索取。所以为了充分 发挥d a b 技术的优势，突破传统单一音频广播模式，开发了d a b 数字多功能应用，即在声 音传输的基础上，同时传递相应的图像、文字、数据、图片等信息。例如电台在广播节耳播 出的同时，可同步传送与节目相关的主持人或者现场的图片甚至是视频流，为听众提供声音 以外的视觉效果。这样就把数字广播从原来只有单纯的声音广播功能，扩展到结合数据、活 动图像等多媒体业务播出的数字多媒体广播。新一代数字广播在技术上有以下特点： 节约无线频谱资源 众所周知，每个国家的无线电频率资源都很宝贵，就广播电视系统而言，一个电视台占 用了某频段，附近的电视台就不能再使用这个频率段，否则就会相互干扰。d a b 适合单频网 实现，各个发射台在同一时刻使用同一频率发射同一套节目，其发射功率都很低，电磁污染 比较小，而且可以不断扩大覆盖区域，这样就提高了频谱利用率。 抗干扰能力强，接收效果好 d a b 采用了o f d m 调制技术，通过时域交织和频域交织以及纠错能力强的卷积码，能够 提供c d 质量音质纯净的声音，并通过纠突发错误r s 码的级联，使得传输视频节目成为现实。 实现了便携移动接收 现在使用的调频和模拟电视，如果在移动中接收信号，所收到的信号会受到很大的损耗 但是使用d v b d a b 等数字化传输方式，即使是在时速几百公里的高速列车上，也能够收看 东南大学硬士学位论文 到清晰稳定的电视图像，聆听到c d 立体声音质的震憾音响。同时d a b 系统采用差分技术， 接收机复杂度很低，适合手持终端的使用。 1 2o f d m 系统简介 电磁波信号在无线信道传播过程中经过自然界( 如山峦、树木) 或者人造障碍物( 房屋 建筑等) 后会产生反射、折射和散射，因此，接收机天线会收到来自不同方向具有不同延迟、 不同强度、不同相位的多径信号。这些多径信号的叠加导致接收到的复合信号的相位和幅度 发生变化，体现在频域上就使得传输信号发生频率选择性衰落。单载波系统中一般都使用均 衡器来抵抗信道的频率选择性衰落，但是对于高速系统来说符号问干扰会非常严重，所需要 的均衡器阶数会很高，均衡过程十分复杂，因此提出了多载波技术，其基本思想是把整个传 输带宽分为很多小块，在每个小块内信道是平坦衰落的。 o f d m 作为一种多载波调制( m u l t i - c a r r i e r m o d u l a t i o n ) 技术1 2 1 1 3 1 ，可以在多个载波上分剐 调制数据，并行发送。为了节省带宽，各个载波之间是正交的，o f d m 中的“正交”表示的是载 波频率问精确的数学关系。o f d m 既能充分利用信道带宽，也可以避免使用高速均衡和抗突发 误码。设各个载波上的码元周期是t ，那么相邻载波的频率间隔为l 厂r ，因此各路信号的频谱 实际上是重叠的，接收端利用这些子载波之间的正交性，可以把每一路信号分离出来，从而 实现解调。对调制在子载波上的n 个数据作n 点f f t 运算，得到的结果作为o f d m 符号i l j n + 时 域样点，样点之间的间隔为t n 。o f d m 系统的典型框图如图l - l 所示。 麓 图1 - 1o f d m f 降输系统框图 在发送端，首先对原始数据进行编码、交织；然后串并交换，把一路信号分成并行的n 路，通过n 点i f f t 把数据调制到多个相互正交的子载波上并行发送，i f f t 后得到的n 个样 点称为一个o f d m 符号；把符号的最后l 个样点复制到最前面作为保护间隔，用于抵抗符号 问干扰，再通过发射机发送出去。 接收端执行与发送端相反的过程，对射频( r f ，r a d i of r e q u e n o y ) 信号下变频后进行抽 样，得到离散的样点；然后进行定时估计找到o f d m 符号的起始位置，除去c p 部分：对c p 后面的n 个样点作n 点f f t 后进行判决解调，如果采用相干解调，那么还需要估计信道参数 来辅助解调：把解调后的数据进行解交织、解码，得到原始数据 o f d m 技术有很多优点是单载波技术无法比拟的1 4 1 ： 1 ) 非常高的频谱利用率。o f d m 系统各子信道不但没有保护频带，而且相邻信道间信号 频谱的主瓣还相互重叠，但各子信道信号频谱在频域上相互正交，各子载波在时域上正交， 2 东南大学硕士学位论文 o f d m 系统的各子信道信号的分离( 解调) 是靠这种正交性来完成的o f d m 的频谱利用宰是单 载波系统的2 倍。 2 ) 实现比较简单。当子信道上采用q m 或m p s k 调制方式时，调制过程可以用i f f t 完成， 解调过程可以用班呵完成，既不用多组振荡源，又不用带通滤波器组分离信号。硬件实现时直 接使用相应的d s p 芯片或专用集成电路即可。 3 ) 抗多径干扰、抗衰落能力强。由于一般的o f d m 系统均采用循环前缀方式，使得它在 一定条件下可以完全消除信号多径传播造成的码间干扰，完全消除多径传输对载波间正交性 的破坏，因而具有很好的抗多径干扰能力。o f d m 的子载波把整个信道划分成许多窄信道，尽 管整个信道有可能是极不平坦的衰落信道，但在各子信道上的衰落却是近似平坦的，这使得 o f d m 系统子信道的均衡特别简单，往往只需要一个抽头的均衡器即可。窄带干扰只会影响到 系统的个别子载波，对整体信息传输影响不大 4 ) 多载波系统可以根据每个子载波的信噪比来动态分配其功率等资源，使系统在整体意 义下达到最优。 5 ) 广播应用中，利用多载波系统可以实现单频网络。单频网络中，用户能够接收到来自 不同发射机的相同信号，由于传输时延的不同，接收信号是多个强径的叠加。o f d m 系统保护 阃隔的存在使得传输过程中没有符号间干扰，多个强径其实可以看成是一种时间分集，因此 系统还能获得额外的分集增益。 尽管o f d m 技术具有诸多优势，但也有一些明显的缺点，主要有下面3 个： 1 ) o l d m 系统作为多载波系统，因为各子载波之间要求严格正交，因此对同步的要求特 别高。o f d m 系统中主要要求以下3 种同步：载波频率同步、抽样频率同步和帧同步目前各 个同步问题都要分为两步：粗同步( 又称为捕获) 和精同步( 2 z 称为跟踪) 。 2 ) o f d m - - 个主要问题就是峰值和均值功率比p a p r ( p e a k - t o - a v e r a g o p o w e r r a t i o ) 比较高， 由此引发发射端严重的功率问题。采用电池供电的便携式设备对功耗要求相当严格，如果峰 值功率过高，超过功放的线性范围，引起非线性失真，最后将导致o f d m 整体性能下降。 3 ) 在无线信道中，通常有差分解调和相干解调两种方式，差分解调不需要信道估计，信 道信息己经包含在相邻符号差中了，但它使噪声有3 d b 的增强，并且无法利用频带利用率高 的多电平调制技术；而相干解调允许使用任何信号星座，所以，在无线环境中，连续调制因 为效率高而受到关注，但此时就需要信道估计。因此信道估计的性能会严重影响整个系统的 性能，除去估计算法本身的因素，定时同步的精度和移动环境的突变都会影响估计的准确性。 此外设计信道估计器还有以下两个问题，一是要确定采用何种形状的导频信息，二是要保证 估计器的低复杂度和良好的跟踪性能 1 3 信道编码简介 由于通信信道固有的噪声和衰落特性，信号在经过信道传输到达接收端的过程中不可避 免地会受到干扰而产生失真。通常要采取信道编码来检测和纠正由信道失真引起的信息传输 错误。纠错编码通过特定的编码方式在码字中引入校验位，建立信息位与校验位间的相关性， 而正是这种相关性，使得识别和纠正信息位的传输错误成为可能。 1 9 4 8 年，美国贝尔实验室的c e s h a n n o n ( 香农) 在贝尔技术杂志上发表了莫基性文献a m a l h e m a t i c a lt h e o r yo f e , o m m u n i o a t i o n ”，标志着信息与编码理论这一学科的创立。s h a n n o n 在文 中提出了著名的有噪信道编码定理，即对任何信道都存在确定的信道容量c ，且只要实际传输 速率r 小于c ，就存在一种编码方法，当码长充分长且采用最大似然译码时，可使译码错误概 率任意小。反之如果r 大于c ，则不可能有一种编码能使差错概率趋于0 。 信道编码定理中信道容量c 表示从信道输出中获取的关于信道输入的最大信息量，也就是 3 东南大学硕士学位论文 信道输入与信道输出间的最大平均互信息，是信道的极限传输能力。有噪信道编码定理从理 论上给出了纠错码的极限，同时也指明了纠错码研究的方向和目标。编码定理虽然没有给出 码字的具体设计方法，却指出了设计逼近信道容量的码字的方向：编译码采用随机方式，加 大码字的长度，采用最大似然译码。然而最大似然译码算法的复杂度随着码长的增加以指数 形式递增，这在物理上是不可实现的。因此构造物理可实现的编码方案和寻找基于晟大似然 准则的简单有效的译码算法，直是纠错码研究的核心内容。按照监督码元是否仅与本码组 内的信息码元有关，可以得到两种形式的信道编码，即分组码和卷积码。分组码中每个码组 内的监督码元仅与该码组内的信息码元有关：而卷积码每个码组内的监督码元不仅与本码组 的信息码元有关，还与前面若干码组内的信息码元有关。分组码分析比较简单，迅速发展成 系统的代数编码理论，成为纠错码中理论体系最完整、最成熟的一类码字“。 循环码是目前广泛使用的一类线性分组码，除了具有线性分组码的封闭性井，还对循环 移位具有封闭性。循环移位特性大大简化了编译码结构。循环码中一个重要成员就是由b o s e 、 r a y - c h a u d h u r i 和h o c q u e n g h e m 于1 9 5 9 1 9 6 0 年提出的可纠正多个随机错误的循环码，命名为 b 叫吗。在此基础上r c c d 和s o l o m o n 于1 9 6 0 年将其扩展到多进制情形，得到了r e e d - s o l o m o n 码。 r s 码的突出优点是非常适合纠突发错误，在c d 播放器、d v d 播放器及d 、，b 和数字用户线( d s l ) 标准中有广泛的应用。卷积码利用了多个码组中信息位的相关性，因此即便每个码组的信息 位比较少，仍能获得较高的编码增益。卷积码译码最常用的是维特比( v i t d o i ) 算法，非常适 合纠正随机错误，但是译码器如果不能正确译码，就会导致突发性错误，因此常采用卷积码 作为内码和r s 码作为外码的级联纠错码，充分利用了卷积码和r s 码的纠错性能的互补特性， 从而提高编码增益，这种级联码在d a b 、d v b 等多种通信系统中得到使用。 1 9 9 3 年，法国的c l o u d - b a n - o u 等提出了并行级联卷积码即t u r b o 码，巧妙地将卷积码和随 机交织器结合在一起，实现了随机编码的思想，为s h a n n o n 随机码理论的应用研究奠定了基础。 通过多个软输出译码器之间的迭代，系统渐近性能逼近最大似然译码。采用这种编码，在 a w g n t 言道和b p s k 调制下，编码效率为l 2 、比特信噪比为0 7 d b 时，可以获得低于1 0 1 的误 比特率，使信道编码理论和实践进入了一个崭新的阶段 1 4 l d p c 码概述 u ) p c 码最早是由g a n a g 一7 l 于1 9 6 0 年代初期在其博士论文中提出，故又称为g a l l a g e f 码。 但在其后的长时间里被忽视了，其中一个重要原因是就当时的技术条件而言，l d p c 编译码器 的实现过于复杂，再就是1 9 6 0 年r s 码的发现，r s 码与卷积码构成的级联码被认为是很完美的 直到1 9 9 6 年，m a z k a y 等发现u 城码同样具有逼近信道容量的译码性能且成本远低于t u r b o 码工 阱 c 码才又引起了人们的研究兴趣。 t 于1 9 8 1 年提出利用图论中的二分圈来描述_ l d p c 码，即t m m e r 图，t a a n e r 还证明了 置信传播译码算法在没有闭合环路的t r a i n e r 图上具有最佳的译码性能“。1 9 9 6 年，m a e k a y 的 研究表明，正则u ) p c 码与t u r b o 码相比还有一定的差距。1 9 9 8 年，l l 出礴人提出了利用非正 i j t a n n e r 图来改善l d p c 码性能，这就是非正则l d p c 码。2 0 0 1 年t j r i o h a r d s o n 与s y ，o r e s 等提出了著名的密度演化算法来优化非正 j t a n n o r 图的参数，所设计的l 2 码率非正则l d p c 码 在a w 洲信道中，其性能距香农限不超过0 0 0 4 5 d b 9 j ，这一结果超过了所知最好的t u r b o 码， 也是目前所知最好的纠错码，由此掀起了l d p c 码的研究热潮。 l d p c 码的校验矩阵十分庞大，因此其参数优化工作十分复杂，密度演化是获取最优参数 值的精确方法，但是计算非常复杂，搜索时间很长。2 0 0 1 年s y c h u a g 根据中心极限定理。假 定t a n n e r 图上传递的外部信息服从高斯分布，提出一种单参数的设计方法，即高斯逼近( a 魄： g a m e i a aa p p r o x i m a t i o n ) ，其精度比密度演化算法差，但复杂度大大降低“w 4 东南大学硕士学位论文 l d p c 编码要比n 蝴复杂，而j l t a n n c r 图中的闭合环路，特别是最小环长对迭代译码性 能影响很大，因此构造编码简单性能优越的l d p c 码是现在的研究热点之一。校验矩阵的具体 构造也有很多方法，主要分为随机构造和代数构造两类。不同结构的码字有着不同的编码和 译码结构。l d p c 译码算法主要有位翻转( b f ：b i t - f l i p p i n g ) 算法和置信传播( b p ：b d i o f p r o p a g a t i o n ) 算法两大类：b f 算法是一种计算复杂度很低的硬判决算法，但译码性能很差，虽 然还有很多研究提出了w b f 和l p - w b f 算法，但是相比b p 算法，性能差距很明显：而b p 算法 是一种软输入软输f l ( s l s o ) 的迭代译码算法。l d p c 译码研究主要集中在寻找与b p 译码相比性 能损失不大，但复杂度更低的译码算法，如m i n - s t m l ，归一化( n m 舷d ) m i n s m ，o 】匦c t m i n - s m 等。各种译码算法的性能比较，可以通过密度演化方法来分析。 u ) p c 码与t u r b o 码都是性能逼近香农限的好码，两者各有特点。码长较短雕j l d p c 码特别 是正则u ) p c 码性能比t u r b o 码差，而且l d p c 编码也比t u r b o 码复杂。但是l d f c 码与t u r b o 码 相比有以下优势： 译码迭代可以根据信道自适应地终止，有利于降低功耗： l d p c 码具有接近s h a n n o n 限的优异性能，错误平台更低，高码率u 聊码依旧有很好的 性能： b e 译码可以全并行，比t u r b o 码的串行译码具有更快的速度和更低的复杂度，这使得 u ”c 非常适合广播系统，有利于降低接收机的复杂度； ( 1 ) l d p c 码具有随机码特性，在与信源或者信道级联时无需额外加交织器，系统的复杂度 和延时都比t t h b 0 码低： l d p c 码已成为下一代通信系统强有力的竞争者，目前已有很多系统采用或研纯_ d p c 码。 休斯网络系统( h n s ) 公司提出了基于l d p c 码和b c h 码级联方案的d v b - s 2 系统1 1 2 1 ，说明l d p c 码正在由理论转向实际应用。目前还有很多关于l d p c 码在广播系统和无线局域网中的研究， 主要集中在码字构造和译码器的硬件实现方面。码字构造主要研究如何构造出g j 曲尽可能大 的码字从而获得较大的最小距离；译码器的实现主要是针对不同结构的码字，寻找其特殊的 实现结构以达到最大的数据传输速率。 1 5 论文的主要内容和结构 本论文选择l d p c 码作为研究方向，介绍l d p c 码字的几种典型结构，同时给出对应的编 码方法，重点对译码算法进行深入分析与仿真，寻找一种低复杂度且逼近b p 的译码算法。为 测j , 式l d p c 码在数字广播中的性能，我们将l d p c 编码放到t - d m b 系统中，分别在高斯信道和 多径信道下仿真系统的性能，并与r s 码与卷积码的级联进行对比。 论文共分五章。本章为绪论，简单介绍了信道编码基本原理，l d p c 码的发展、优缺点和 研究现状，以及o i d m 技术的基本原理和数字音频，多媒体广播的发展现状。第二章阐述关于 u ) p c 码的部分理论基础，包括l d f c 码的二分图结构和l d p c 码的闭合环路等，重点介绍l d p c 经典的码字构造和编码方法。第三章中重点研究l d p c 码的译码算法，主要针对m i n s m 算法 进行改进，并推广到非规则码字。第四章将l d p c 与o f d m 系统结合，检测其在高斯和衰落信 道下的性能。第五章给出u ) p c 玛在t i 数字信号处理器上的实现与优化。最后是全文的总结和 有待进一步研究的工作。 东南大学额士学位论文 第二章l d p c 码的码字构造和编码 u ) p c 码是一种线性分组码，由于校验矩阵的稀疏性，它具有t n ”图这样的数学模型， 因此理论分析相对简单。1 9 9 0 年代，人们利用t a h 图来对u ) p c 码的译码性能进行分析，目 前已经有了一些较为完善的理论；人们还发现基于稀疏图的l d p c 码具有非常接近s l l a m 限 的性能。本章首先介绍线性分组码的原理，然后简介l d p c 码图论的基础知识，最后给出u ) p c 码的分类。 2 1l d p c 码的图结构 线性分组码在纠错码中有很重要的地位它的数学模型简单，较易进行性能分析。而l d 壬，c 码本质上就是一种线性分组码，它通过一个生成矩阵g 将信息序列映射成码字序列每一个生 成矩阵g ，都存在一个奇偶校验矩阵h ，所有的码字序列c 构成了h 的零空间。 图论中一个图由顶点和边组成的，其中树( h ) 和二分图( b i p 枷t eg r 印i i ) 都可用来描 述和分析u ) p c 码。二分图中所有的顶点分为两个子集，任何一个子集内部各顶点之间没有边 相连，任意一个顶点都和一个不在同一个子集里的项点相连。 2 1 1 树 g a a g e r 用校验树来表示日矩阵，用以说明消息在置信传播译码中传播的过程。此后，表 示l d p c 矩阵的树图有了改进，如图1 1 所示：一条斜线和与其上端相连的一条横线代表一个 校验方程，线上的节点即为构成此校验方程的节点；黑点代表校验节点，白点代表变量节点。 图中有两层结构，由上至下，第1 层表示为校验方程c ，第2 层表示参与c 的信息节点1 ，第3 层表示v 参与的其余校验方程，第4 层代表参与上一层校验方程的其它信息节点。如果继续衍 生下去，将会出现相同的节点 校验节点 信息节点 校验节点 信息节点 图2 - l 变量节点v 的校验树 6 东南大学硕士学位论文 2 1 2t a n n e r 图 1 9 8 1 年t a c f l “1 建立了编码的图模型概念，并证明了和积算法在无环图中译码的最佳性， 后来人们将应用于编码领域的二分图称为t a n n e r 图。l d p c 码可以用一个t a n n e r 图来表征，该 图和校验矩阵一一对应。图中包含3 种元素：变量节点( v a r i a b l e n o d e ) 、校验节点( c h e o k n o d e ) 和连接它们的边，其中变量节点内部和校验节点内部没有任何边连接，只有在变量节点与校 验节点之间才有边相连接，任意一对变量节点和校验节点最多只有一条边相连t a n n e r 图中的 每一条连线对应于校验矩阵中的l 而且对于一个码长为，码率r = 足的线性码的校验数目是m = 一足。任意一个 线性码都可以用一个t c r 图来表示，而l d p c 的t a m | e r 图是稀疏的，每个变量节点只和少数 几个校验节点相连，每个校验节点也只和少数几个变量节点相连。使得图中边的数目几乎正 比于码长，而不是的二次方。图2 - 2 是一个( 6 ，3 ) 线性分组码的二分图。 图2 - 2 ( 6 ，3 ) 线形分组码的校验方程和对应的二分图 圈2 - 2 的第1 行节点表示发送的位( 称为变量节点) ，第2 行是它们满足的校验( 称为校验 节点) 图中变量节点集合y 一( m ，屹，) 和校验节点集c = ( q ，岛，e i ，) 内部不存在 相连的边，但两类节点之闻存在连线，意味着该变量位参加了此校验式，也就是校验矩阵某 一行中1 的位置。每个节点上的连线数目称为该节点的度( d e 汀) ，图2 - l 中，变量节点 的度都是也= 2 ，校验节点的度都是以= 3 。 l d p c 码是线性分组码的一种，它的最小距离d 二决定了性能优劣，然而一般情况下， l d p c 码的码长较长，无法直接求出一个码的最小距离。而t a n n e r 图中的环在一定程度上反映 了译码性能。t a r m e r 图中由变量节点、校验节点和边首尾相连组成的闭合环路称为环。环的长 度就是其中边的数目。从u ) p c 码的t a n n e r 图中可以看出，每个节点都会存在许多这样的闭合 环路，且每个环的周长一定是2 的整数倍。在图2 - 2 中变量节点v i ，如，k 就参与了一个长度为6 的环，如图中粗线所示，由v 1 起，经过q - - 3 q k _ c 3 ，最后返回v l 。环在l d p c 码的迭代解码过程中会造成不良影响，形成无效信息的正反馈，使迭代解码无法达到最佳性 能，环是如何影响译码性能将在译码章节中详细说明。理论和实践均已证明，t m m e r 图中的环， 特别是短环对迭代解码的性能影响很大。 t a m 日图中最短环的周长称为最小圈长鲫t ，例如图2 - 2 中g i | 廿f 6 。西r n l 越大，最小距离磊 的下界越大，码的纠错能力也越强。t a c 瓒f 出了最小距离的下界与g i f i h 的关系： 7 东南大学顼士学位论文 。d ( d - 两0 ( r - 旷0 e ( - ) i - i + 知一1 ) ( 川) r 叼加为奇数 嗡喾 i d l ( ，一l l l g 2 为偶数 ( 2 - 2 ) 其中，d 为u 聪码的最小码距，g 为u ) p c 码的g i r t h ，为变量节点的次数，d 为二分图中 子码( s u b c o d c ) 的最小码距。后面章节的仿真结果将表明，如果二分图g l , t h = 4 ，将会影u 向l d p c 码的误码率性能，所以在构造u 聪码的校验矩阵时，要尽量避免二分图中出现g i 础为4 的情况。 2 2 分类 l d p c 码有多种分类方法，例如按行重、列重是否为定值划分，可以分为规则码和非规则 码；按所在的域划分，分为二元域和多元域的码。下面将分别介绍这两种分类。 2 2 1 规则码和非规则码 ( 1 ) 规则( r e g u l a r ) l d p c 码 如果l d p c 码的校验矩阵行列重量固定为( p ，) ，即每个校验方程有p 位参与校验，每 个变量参与，个校验方程，我们称之为规则l ，d 】p c 码。这也是g a l l a g e a 最初提出的g a l l a g e r 码的 特点。我们用g a l l a g e r 列 l d p c 码的表示方法：将码长为、行重和列重分别为p 和，的l d p c 码记为0 v , 以p ) l d l 码。从t a m a e r 图的角度看，这种l d p c 码的变量节点次数全部为y ，而 校验节点次数都为p 。可以适当放宽上述规贝咀嗍码的条件，行或列的重量可以不是固定的 整数，但行列重量尽量服从均匀分布。另外为了保i 正_ l d p c 码的t m m c r 图上不存在长度为4 的环， 通常要求行与行及列与列之间的交叠部分重量不超过i 。当校验矩阵日满秩时，规则码的码率 r = ( 一m ) i n f f i k m = l r p ；当校验矩阵盯不满秩时，r = ( 一r a n k ( h ) n = k m m a c i ：a v 在文献1 1 以中证明了在任意信道中，1 ) 规则l d p c 码满足了好码( g o o d ( 奴i c 基) 定 理的要求，即在固定列重纠：p 3 ) 、码长n 足够长的情况下，存在一个0 到信道传输容量之问 的值r ，在此速率下可以实现无差错传输：2 ) 规i j l d p c 码满足了更好码( v e r yg o o dc 0 8 ) 定理的要求，即如果不同定列重p ，当p 膨很小时，l d p c 码可以很接近信道容量。 ( 2 ) 非规则( i n e g e l a f ) l d p c 码 在t m m 图中，信息节点希望能参与尽可能多的校验方程，以便更准确地判断自己；而校 验节点希望向尽可能少的信息节点传递消息，以确保更准确低判断信息节点。非规则l d p c 在 此要求下受到人们的重视。i 嘶8 1 分析了非规则l d l ，c 码的性能和构造非规则好码的方法。 非规则码的行列重以不再是固定值，即每个变量节点参与的校验式数目或每个校验式中 含有的变量节点数不再保持均匀，而是有意设置部分突出的变量节点和校验节点。在译码过 程中，那些参与较多校验式的变量节点迅速得到正确译码信息，然后它们给相邻校验节点更 8 东南大学硕士学位论文 加有效的概率信息，而这些校验节点又可以给与它们相邻的次数少的变量节点更多的信息。 整个译码过程呈现出一种波浪效应，次数越高的变量节点首先获得正确信息，然后是次数较 低的节点，然后依次往下，直到次数最低的变量节点。正是这种波浪效应，使得非规则码获 得比规则更好的译码性能 2 2 2 二元域和多元域的码 m a t t h e w c d a v e y 和m a o k a y l “将上述二元域的l d i c 码推广到了多元域g f ( q ) 上。假设在 g f ( 2 ) 和域o f ( q ) q = 2 p ) 上构造的u ) p c 码所对应的校验矩阵分别是日2 和日。h 2 中的 元素是0 或l ，而日。由元素o ，l ，q - i 构成，日。中每个元素都是日，中q 个元素的组合 从矩阵看将相应g h 2 ) 域中相应的i x q 向量代入g f ( q ) 域的日，得到日。的二进制形 式，调节校验矩阵日。可以增加与之对应的二进制校验矩阵z 中列的平均重量，从日。的 t a n n e r 图看，结构并没有