（信号与信息处理专业论文）ldpccofdm系统性能分析.pdf

南京邮电学院学位论文独创性声明 本人声明所星交的学位论文是我个人在导师指导下进行的研究 工作及取褥的研究成果。尽我所知，除了文中特别加以标注和致谢的 遗方夕 ，论文中不包含其德入已经发表或撰写过的研究成果，也不毡 含为获得南京邮电学院或其它教育机构的学位或证书而使嗣过的材 牵季。与我一嗣工 擘的溺恚辩本蚕秀究辑散静饪何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名；叁墨友日期l 垫! 兰竺2 ) 南京邮电学院学位论文使震授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人掰送交学霞论文的复鞠件帮电予文档，可良慕瘸影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期蠹的保密论文乡 ，允许论文被查阕察整淹，霹戳公毒 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 枣京鼹电学院磷究生部办壤。 磷究擞签名：鳖圣免 导搿熬名： 摘要 低密度奇偶校验( l d p c ：l o w d e n s it yp a r it y c h e c k ) 码是一类可以川非常稀疏的奇偶 校验( p a r i t yc h e c k ) 矩阵或二分幽( b i p a r t i t eg r a p h ) 定义的线性分组纠错码，最初是 由g a l l a g e r 在1 9 6 2 年提出的，也称g a l l a g e r 码。m a c k a y 和n e a l 重新发现了它，并且证 明它在基于b f ( b e l i e f p r o p a g a t i o n ) 的迭代译码的条件卜具有逼近香农限的性能。 f 交频分复用( o f d m ) 作为一种高效并行传输技术，由于其频谱利用率高、 能够有效对抗i s i 、成本低等原因越来越受到人们的关注。随着人们对通信数据 化、宽带化、个人化和移动化的需求，o f d m 技术在综合无线接入领域将得到越 来越广泛的应用。b 3 6 移动通信的主流调制技术将是o f d m 技术，而将l d p c 编码 应用于o f d m 系统中构成的l d p c c o d e do f d m 系统有着广阔的应用前景， 本文对采用l d p c - c o f d m 系统在多径衰落信道下的性能进行了以下的研究： 1 ) 研究了l d p c 码对o f d m 固有特性的影响，主要指o f d m 固有的峰值功率 与平均功率比( p a p r ) 过大的问题，发现码型的选择确实对p a p r 有一定的影响， 在校验矩阵h 、o f d m 子载波数和调制方式一定的情况下，p a p r 值仅在一个很小 的范围内随着信源的变化浮动，也就是说它的方差很小，因此在可以事先筛选出 优秀的码型以降低系统的p a p r 值，这也可以作为l d p c 码优化工作的一部分来考 虑。 2 ) 对l d p c c o f d m 系统中是否采用交织器进行了讨论，认为在码长较短时， 交织器的作用非常显著，但随着码长的增加，有交织和无交织的系统b e r 性能差 别逐渐减小，出于减小系统延迟考虑，码长较长时交织器可以省略。 3 ) 选取了i m t 一2 0 0 0 给出的标准车载a 信道，对在该信道条件下，采用q p s k 和1 6 a m 两种不同调制方式的情况下，正则、非正则l d p c 码与o f d m 实现联合编 码的性能进行了仿真，码率分别取1 2 和1 3 ，并且与t u r b o 编码的o f d m 系统 的性能进行了对比，发现在码长较长时，l d p c 编码的系统误码性能要优于t u r b o 码系统，另外l d p c c o f d m 系统在多径信道下，可以以较高的数据速率实现信息 传输，因而l d p c - o f d m 系统在后3 g 时代是一个极有竞争力的选择。 南京邮i u 学院坝1 研究生学位论文 关键词：l d p c 码，正则码，非正则码，二分图，m e s s a g e p a s s i n g 算法 b e li e f p r o p a g a t i o n 算法，多径衰落信道，正交频分复用 2 露袁龆 筢攀兢骥 。磷宠笺举链论文 a b s t r a c t l d p cc o d ei sac l a s so fl i n e a rb l o c kc o d e sw h i c hc a r lb ed e f i n e db yt h es p a r s e c h e c km a t r i xo rb i p a r t i t eg r a p h ，t tw a sf i r s td i s c o v e r e db yg a l l a g c ri n1 9 6 2 ，s oi ti s a l s oc a l l e dg a u a g e rc o d e m a c k e ya n dn e a lr e d i s c o v e r e di ta n dp r o v e di t sa b i l i t yo f a p p r o a c h i n gs h a n n o n l i m i t b a s e do n b e l i e f - p r o p a g a t i o nd e c o d i n ga l g o r i t h m 。 t h e r a p i dg r o , t ho f w o r l d - w i d ec e l l u l a rs u b s c r i b e r sa n di n t e r n e tu s e r sn e e d s h i g h e rd a t at r a n s m i s s i o nr a t e s o r t h o g o n a lf r e q u e n c y d i v i s i o nm u l t i p l e x i n g ( o f d m ) i sa v e r ya t t r a c t i v et e c h n i q u e f o rh i g h - b i t * r a t ed a t at r a n s m i s s i o ni nam u l t i p a t hf a d i n g e n v i r o n m e n tt h a tc a u s e si n t e r s y m b o li n t e r f e r e n c e ( t s t ) 。，l d p cc o d e do f d m s y s t e mi s a p r o m i s i n gt e c h n o l o g yi na p p l i c a t i o n ， t h i st h e s i ss t u d i e st h el d p cc o d e do f d ms y s t e mi nt h em u l t i p a t hf a d i n g e n v i r o n m e n t t b em a i nc o n t e n t sa r e 箍f o t l o w s 1 ) w es t u d i e dt h ep e a k - t o a v e r a g ep o w e rr a t i o ( p a p r ) o f t h eo f d m s y s t e m u n d e rt h ei n f l u e n c eo fl d p cc o d e s t 酶v a l u eo fp a p ri sd i f i e r e n tw i t hd i f f e r e n t k i n d o f c o r r e c t i n g c o d e w ec a nc h o o s e g o o dl d p c c o d e st or e d u c et h ep a p r 。 2 ) w e d i s c u s st h ee f f e c to f i n t e r l e a v i n gi nt h es y s t e m w h e n t h ec o d el e n g t hi s r a t h e rs m a l l ，t h a ti sn o t a b l e ，w i t ht h ei n c r e a s i n go ft h ec o d el e n g t h ，t h ee f f e c to f i n t e r l e a v i n g d e c l i n e s ow ec a no m i ti ta t 氆a tt i m e + 3 ) w e c h o o s eas t a n d a r dc h a n n e li n3 g , a d o p t i n gq p s ka n d16 q a mr o o d u l a t e m e t h o d t h ec o d er a t eo fl d p cc o d e sa r el 2a n dl 聪a l t e r n a t i v e l y w ef i n d 曦戤t h e p e r f o r m a n c eo f t h e l d p c c o f d m s y s t e mi sb e t t e rt h a n t h a to f t h e 弧i 幽。一c o f d m + k e y w o r d s ：l d p cc o d e s ，r e g u l a rc o d e s ，i r r e g u l a rc o d e s ，b i p a r t i t eg r a p h ，m e s s a g e p a s s i n ga l g o r i t h m ，b e l i e f - p r o p a g a t i o na l g o r i t h m ，m u l t i p a t h f a d i n gc h a n n e l ， o r t h o g o n a lf r e q u e n c y d i v i s i o nm u l t i p l e x i n g 3 南京帮f u 举虢颤 ：研究生擘位论文 第一章绪论 在现代数字通信系统中，为保证各种数据能够可靠、有效地传输，往往要利 用纠错编码技术。：i 垃年来，随着无线数字通信的发展及各种高速率、突发性强的 薪、监务懿蹬王冕，臻炎：沣列蠲好纠戆缡筠技术魏越寒越显缛毖燹。 纠镛编码的起源可以追溯到1 9 4 8 年仙农信息论的问世。从那时起，菸理论 不断发展、成熟，成为一门重要的学科。纠错碣主要有分组码和卷积码两大类。 无论楚分缝码、卷较疆，还是缀联疆、黍瑗玛，握怼予未编璐粒绩况，缡褥瑟豢 来的性能上的改善存在一个理论上限，即香农限( s h a n n o nl i m i t ) 。香农信息论 指出了设计纠错码的方向，具有黧大意义。 香农筵二定理( 龟舔信遭绩鹳定瑾) 搔老实褒可靠暹信辨兔诲款传羧速率数 上限为倍道容量。在信道带宽受限和功率受限的条件下，带限a w g n 倍道的信 道容量c 表示为： c 一引| h 轰陋 弘t ， 其中为带宽，只。为信道输入带限信号的平均功率。如果传输速率为r ，= c ， 剐 一c w = l o g 2 旧1 惫 m z ， 一e b ：笙( 1 - 3 ) 一 n 。c w f 拿1 ：j 秘型：l n 2 一解0 - 4 ) k e j 。秽“c w 表明带限信道中，传输速率达到信道容量时，可靠通信所需的最小比特能噪比为 一1 6 d b ，称之为香农限。香农限成为设计信邋编码时试图滠近的信噪比下限。 褡表理论饺纠镶编码理论不黼发震成熟，成为- - f 重甏豹科学。最稠鹃研究 主要集中在以代数理论为基础的线性分组码，出现了汉明码、循环码等一系列好 码。五十年代弓l 进的卷积码在编碣过程中弓l 入了寄存器，增加了码元之间的相关 经，扶两在相同的笈杂度下获褥沈分组码更高的编码增益，溺时也璜热了分摄和 5 赢富鼯吨学靛磺 + 研究生够位论文 设计的复杂度。随螯器种卷积码译码算法的出现，尤其v i t e r b i 算法，假进了卷 强玛豹深入磷究积藏矮。嚣嚣寒壅凌懿t c m ( 梅糖壤璃谖) 技术，葵定了卷较 码在通信领域中的主导地位。 八十年代和九十年代初，经过几十年的研究和实践，纠锚编码理论和技术取 褥了袋大熬发震。法霆豹c ，b e 徉o u 等太在卷板弼移缀联毽懿鏊爨上，予1 9 9 3 年 提出了一种全新的编码方案附b o 码，在信j 室妻编码的理论和应用中取得了突破 性的进展。这种编码能够随着码长的增加而逼j 艟香农的理论极限，同时译码复杂 痊毫哥渡接受。t u r b o 玛采爱菸纷缀联递| 扫弱缡玛器缝稳，蹩耪系统茨漆积羁。 其译码辣法主要有m a p 算法、l o g - m a p 算法、m a x l o g - m a p 算法、s o v a 算法 等。t u r b o 码具有独特的编码结构和译码思想：在子编码器中采用了反馈型的系 统卷裁鹈，显在予编鹞器淘；l 入交绠器，藏少了子壤臻器耀翁惑静鞠关性，模仿 了随机编码的形式 闹时在译码中采用了软输入、软输出的译码信息和信息反馈 的译码器形式，并引入了迭代译码的思想。 在t u r b o 妈瓣稿发f ，男一癸疑存糖 菝褥糕帮性毯戆缡褊重薪送入了入翻蕊 视野。逮就是l d p c ( l o wd e n s i t yp a r i t yc h e c k - - 低密度奇偶校验) 码。它最初 是出o a l l a g e r 1 于1 9 6 2 年提出的。这种编码出于校验矩阵的稀疏性，使得译码 复杂漤与鹂长袋线彀关系。之螽，d + j 。c m a c k a y 、m n e a l 秘n w i b e r g 等久对其 重新谶行了研究，发现它也具有邋近香农限的性能。现在它已成为通信技术中的 新的研究热点，其技术也同趋成熟。 l d p c ( l o w d e n s i t yp a r i t yc h e c k - - 象爨痰鸯缓铰验) 疆是一秘其鸯褥藏较 验矩阵的线性分组粥；其性能优于t u r b o 码，具有能够逼近番农限的性能特性； 具有较大灵活性和较低的差错平底特性( e r r o rf l o o r s ) ：幽于其校验矩阵的稀疏 牲，它豹译玛复杂痰低子t u r b o 诵，冒颤在线缝复杂凄痰实瑗译羁，莠胃强实现 完全的并行操作，硬件实现复杂魔低，可以实现大吞吐量高速译码。 l d p c 码的缺点主要在于，篡编码的复杂度较高，虽然摄新的研究焱明它可 疆在线缝霹闻瘫绫鹣，毽是其复絷度裰霹予卷积鹚等可敬瓣簿编疆豹蕊皋说镄然 过大。同时在码长很长的情况下，由于必须在接收到所有的信息比特后爿能够进 行编码，这就会给编码带来一定的时延，在对实时性要求较高的场合，其应用会 受蜀黻潮。暑努，l d p c 鹃洼缝豹往越淫逶鬻霰在鹂长鞍妖簿方戆够俸瑷密来， 6 南京邮i u 学院坝l + 研究生学位论立 当码长为中短长度时，由于编码中短长度环的存在，编码的性能会有所损失。 l d p c 码具有巨大的应用潜力，目前基于l d p c 在各通信领域应用的研究正方 兴未艾，如在移动和固定无线通信、深空通信、光纤通信、卫星数字视频和声频 广播、磁光全息存储、电缆调n 解调器和数字户线( d s l , ) 等领域的应用。本文 的工作f 是着眼于l d p c 码在移动通信领域的应用。 移动通信是现代通信系统中不可缺少的组成部分。顾名思义，移动通信就 是指通信双方至少有一方在运动状态中进行信息传输。例如移动台与固定点之问 或移动台之问的通信都属于移动通信的范畴。另外，还有一种可移动的概念，即 通信用户的位置是可变的，但在通信过程中用户不处于运动状态。这类通信也可 称为移动通信，但与严格意义的移动通信相比，两者的无线信道特性有较大的差 别。 移动通信不但集中了无线通信和有线通信的最新技术成就，而且集中了网 络接收和计算机技术的许多成果。目前，移动通信正朝着个人通信这一更高阶段 发展。未来移动通信的目标是：能在任何时间地点，向任何人提供快速可靠的通 信服务。可以浇移动通信从无线电通信发明之只就产生了。1 8 9 7 年，m g 马可 尼所完成的无线通信实验就是在固定点与一艘拖船之白j 进行的。现代移动通信技 术的发展始于2 0 世纪2 0 年代，但是一直到2 0 世纪7 0 年代中期，才迎来了移动 通信的蓬勃发展。 从2 0 世纪8 0 年代中期开始，数字移动通信进入发展和成熟时期。模拟蜂 窝网的容量已不能满足同益增长的移动用户的需求。欧洲首先推出了全球移动通 信系统( g s m ) ，随后美同也相继指定了各自的数字移动通信体制。9 0 年代初，美 国o u a l c o m m 公司推出了窄带码分多址( c d m a ) 蜂窝移动通信系统，这是移动通信 系统发展中的里程碑。从此，码分多址这种新的无线接入技术在移动通信领域占 据了越来越重要的地位。这些目前正在广泛使用的数字移动通信系统就是第二代 移动通信系统。 第二代移动通信系统主要是为支持话音和低速率的数据业务而设计的。但 随着人们对通信业务范围和业务速率要求的不断提高，已有的第二代移动通信网 络很难满足新的业务需求。为了适应新的市场需求，人们正在发展第三代( 3 g ) 7 南京i l l l l i 乜学院砸i 研究生学位论史 移动通信系统。但是由于3 g 系统的核心网还没有完全脱离第二代移动通信系统 的核心网结构，所以普遍认为3 g 系统仅仅是一个从窄带向未来移动通信系统过 度的阶段。目前，人们已经把目光越来越多地投向后3 g ( b e y o n d3 g ) 的移动通信 系统，该系统可以容纳庞大的用户数、改善现有通信质量，达到高速数据传输的 要求。从技术层面来看，3 g 主要是以c d m a 为核心技术，而在3 g 以后的移动通 信系统中f 交频分复用( o f d m ) 最受瞩目，o f d m 技术在无线通信领域的应用成为 目前研究的热点。 对于高速数据业务来说，单载波时分多址( t d m a ) 系统和窄带c d m a 系统都存 在很大的缺陷。由于无线信道存在时延扩展，高速数据流的符号宽度又相对较窄， 所以符号之间会存在较严重的符号间干扰( i s i ) ，这对单载波t d m a 系统中使用的 均衡器提出了非常高的要求，即抽头数量要足够大，训练符号要足够多，训练时 阳j 要足够长，从而均衡算法的复杂性也会大大增加。对于窄带c d m a 来说，其主 要问题在于扩频增益与高速数据流之间的矛盾。在保证相同带宽的前提下，高速 数据流所使用的扩频增益就不能太高，这样就大大限制了c d m a 系统抵抗噪声的 优点，从而使得系统的软容量受到一定的影响，如果保持原来的扩频增益，则必 须要相应地提高带宽。此外，c d m a 系统一个非常重要的特点是采用闭环的功率 控制，这在电路交换系统中比较容易实现，但对于分组业务来说，对信道进行预 测，然后再返回功率控制命令会导致较大的时延，因此对于高速的无线分组业务 来说，这种闭环的功率控制问题也存在缺陷。 因此，人们丌始关注o f d m 系统，希望通过这种方法来解决高速数据流在无 线信道中的传输问题，从而可以满足带宽要求更高的多种多媒体业务。 o f d m 的提出已经有近4 0 年的历史了，第一个实际应用是军用的无线高 频通信链路。但这种多载波传输技术在双向无线数据方面的应用却是近1 0 年来 的新趋势。近年来，o f d m 由于其频谱利用率高、成本低、具有较强的抗多径衰 落能力等原因越来越受到人们的关注。随着人们对通信数据化、宽带化、个人化 和移动化的需求，o f d m 技术在综合无线接入领域将得到越来越广泛的应用。随 着d s p 芯片技术的发展，傅立叶变换反变换、6 4 1 2 6 2 5 6 q a m 的高速m o d e m 技 术、格状编码技术、软判决技术、信道自适应技术、插入保护时段、减少均衡计 算量等成熟技术的逐步引入，人们开始集中精力丌发o f d m 技术在移动通信领域 8 南衷郯 u 学院硕| + 研究生学位论文 的应用，预计3 g 以厢移动通信的主流技术将怒o f d m 技术。 凌o f d m 系统孛，绸锗编码戆必不哥多垂孽，包耩卷拣璐、黔鹞、t u r b o 码在 内的多种纠错编码都鞠被应用在o f d m 系统当中。目前，l d p c 码的优良性能决定 了l d p c 编码与o f d m 技术的结合题当前移动通信发展的必然趋势。利用l d p c 码 在o f d m 予载渡之溷实襞联台缡鹳，可爨畜效辩辘多径移动传道中深度袭藩对载 波信道菜些特定频率的影响，极大地提高系统性能。 零文共五章：第一章介绍了l d p c 码的产生，当前的研究状况以及o f d m 技 术静产生秘发震 簿二章详囊说明了l d p c 编戳豹基本赣念謦瑟泽鹞算法；第三章 阐述了o f d m 的研究状况和基本原理；第四章讨论了l d p c c o f d m 现有的研究进展、 系统架钩与优化：第五章描述了移动信道的特点和瑞利衰落信道的衰落模型；第 六耄绘滋了l d p c - o f d m 系统缍梅、茨卖结票良及对结栗静分凝。 9 南京鼯电学院颤i j 辫究熏学位淦文 第二章l d p c 码基础 g a l l a g e r 1 子1 9 6 2 年提出的l d p c 码，熙一种具有稀疏的校验矩辫的分组 码。所谓鲍“低密度”正是来源予斑阵的稀疏性。 ； ( a )( b ) 图2 - 1l d p c 码倒( 正则码) 由线性分组鸦鲍性质，在域f 上，码长为摊，k 维的编鼹c 可用印k ) x n 的 校验矩阵描述：c ( h ) ：= x f ”：h x 7 = 0 ) ，褐率为k n 。 2 1l d p c 码的圈结构 在l d p c 码的研究过程中，t a n n e r 5 提出“二分犀( b i p a r t i t eg r a p h ) ”模 鍪对l o k 鹞逶 亍分析。二势圈出院特节点( b i tn o d e s ) 、扳骏节点( c h e e kn o d e s ) 以及连接它们的边( e d g e ) 组成。图l 是一个校验矩阵和对威二分图的例子，每 个比特节点对应于校验矩阵的一刿，也就是码字中的一个比特；每个校骏节点对 应予辩缒阵豹一行，裘示一个校骏等式。琵将节点密较验节点之润麓边表示该比 特节点参与到该校验节点所代表的等式中。 上述例子是一个二元域上的l d p c 码，其编码的校验矩陈中，每一列露d 。( = 2 ) 个非零元，每一行脊d ，( = 3 ) 个非零元。即，编码码字x 中的每个比特参加d 。个 校验约柬，而每个校验约束包括d 。个比特。在二分图中，d ，d 。分别表示与比 特节点和棱验节点相连匏透数，称为该节点酌次数( d e g r e e ) 。当为常数澍( 如上 面的例子) ，即所有比特节点的次数都一样、所有校验节点的次数也都一样，这 样的l d p c 码称为正则( r e g u l a r ) l d p c 玛，简称正则码。 _ f 掰警二分圈孛辩比特节点鹣次数各不穗阐( 莜验节熹的次数氆奢稻疲酶交 1 0 l l 0 o i o 1 0 ，。l 1 1 h 毫赢郏 巍学院鹾卜硪究生举链论支 动) 时，这样的l d p c 码称为非正则( i r r e g u l a r ) l d p c 码，简称非f 则码。非正 翻玛逶零麓次数分奄对( d e g r e ed i s t r i b u t i o np a i r ) 薅，p ) 滚爨述： d。1 五( x ) = 五，工“1 、_ p ( x ) = p 。x 1 分别为比特节点和校验节点的次数分却 t = 2i = 2 多璜式；五( 反 表示与次数为i 麴比特( 较羧) 节点褶逢瀚逮数在慧逸数中掰 占的比例；d 了“( d ? “) 表示比特( 校验) 节点中的最大次数。图2 - 2 ( b ) 为一一 测量：= 0 。4 ，量：= 0 6 ，岛= 0 6 ，p 4 = 0 4 懿聂裂妈。 幽予非正则码中节点次数分抑的不均匀，次数高的比特节点因为受到较多 的校验约束的监督，将较快地被正确译码。反过来，它们又将给其它次数较低的 苇点撬供更可靠的译玛信惑。这簸是嚣谖静“滚浪效应( w a v ee f f e c t ) ”。 从比特节点的角度看，其次数越高越好，因为对它进行监督的校验节点越 多，提供的译码信息越准确，使德它能更快更凇确地被译碣：但是从校验节点角 凄看，翊是次数越低麓好，这嚣它提供给与之鞠邻豹跑薅节患的校验信慧簸更准 确。针对这一矛盾，非f 则码显然比f 则码能够更好地实现骶者的平衡。这f 是 我们研究、优化非正则码的目的所在。 对( 五，力菲正稍玛，著给定鹚长狞，码率冀，翻校验节煮的个数掰= ( r ) t 辨a 设二分图中的总边数为e ，则： 。莩孚。磕蝴一2 蠢2 嘉 q 嘲 e 矗，表示与次数为i 的比特节点相连的边数；一上则表示次数为i 的比特 节点的个数：同理，e 旦表示次数为i 的校骏节点的个数。 i 出线牲分组鹞熬定义，在校验缒阵嚣豹行蠢量线幢燹关懿条件下，碣率： r ：翼竺：1 一竺 咒玎 ( 2 - 2 ) 对( 靠。，d 。) 正则褐两言，由于二分图中的憨边数= 摊d ，= 掰- ，所以正则 捣的碣率又可以写成： 南京邮l 乜学院坝i ) 1 _ 究生学位论文 r 。a r 小芋 ( 2 3 ) ( ，p ) 非f 则码的码率： 咖小等 c n - 4 ， 由于在优化设计l d p c 码的时候，我们将注意力集中在次数分布对的寻找上， 而对二分图中的环和校验矩阵行向量的相关性等具体的设计问题忽略，所以我们 后面所说的码率通常指的是“设计码率( d e s i g nr a t e ) ”，即认为校验矩阵的行 向量线性无关。实际的码率通常可能大于设计码率。 2 2l d p c 码的编码 如何增加二：分图中的g i r t h ( 即图中的最小环长) ，如何构造恰当的校验矩 阵使得由校验矩阵得到编码生成矩阵的计算简单，如何提高校验矩阵的秩，如何 减小矩阵的病态，都是l d p c 码的编码研究领域的重点。 2 2 i g a l l a g e r 的构造方法 g a l l a g e r 1 给出了( d ，d ) 正则码的构造方法：对于码长为月的( d ，。：) 正 则码，他将校验矩阵按行水平的分割为d 个相同大小的子矩阵，每个子矩阵的任 - - n 都只包含一个l 。第一个子矩阵以预定的方式构造，如可以用递减的形式包 含所有的1 ，矩阵的第j 行所有的1 都分布在第( 卜1 ) 旁l 到d , y u 。其它下面的 d 1 个子矩阵都是第一个子矩阵的随机排列。这种构造方法可如下表示： j l ! ，n 1 1 1 l 止 届为第一个子矩阵，校验矩阵如下构造 ( 2 5 ) 1 2 禹京郛l u 学院磺 研究生举位论丘= h = 日o 7 2 ( 群。) l d 。( h o ) ( 2 6 ) 这阜力b 矩阵撼的列鬻换。上藤矩阵的第一个子矩阵为瞄，也可以用聪的任一 嚣换健耱，褥妥魏下燹麓对豫豹构造方法： 2 2 ，2m a c k a y 豹鞠滚方法 h = 7 i ( h o ) 7 2 ( o ) 口d ( h o ) ( 2 7 ) m a c k a y 在校验矩阵中引入一贱重量为2 的列，降低整个校验矩阵的熏量以 城少二分蚕中环毂数爨，由戴躐少译褥算法受爨豹舔豹影峨，毽是弓l 入鬟爨为2 的列会蜉致低重量码字的出现，需噩采取措施减少其的出现概率。m a c k e y 给出 了如下指导性的构造方法 3 。 稳造法l a ：这是最慧本豹构造方法，该方法掇造楚缒簿每列豹重量都为一嚣定 值( 例如t = 3 ) ，随机的构造矩阵使每行的熏量尽可能的相等，而每两列之 间獯叠的l 的个数不大于1 。 穆逢法2 a ：该掏造滋稳造教棱验瓣簿 l 萋罢列豹霆量蘩为2 ( 掰为矩簿行数) 。这 z 些煎为2 的列幽两个詈詈的单位矩阵构成，一个在上，一个在下。 zz 构造法l b ，2 b ：出铸造l a 或构逡2 a 褐造校验矩阵，并款该矩阵中删除一些仔 细选择的列，镁得结果矩阵对应的二分图中没有小于浆个给定长度l ( 例如 扛6 ) 的环。 m a c k a y 还攫广了g a l l a g e r 熬陡桩构造法，裂雳羲 残缒黪魏叠秘襁逡蕉则码 和菲诋则码的校验斑阵。 1 3 囊豪邮电学婉蛾七褥究生学位论文 2 1 4 超辍( u r l t r a - l i g h t ) 构造法 m a c k 8 y 8 1 裁瘸了最多为罢舅靛繁整为2 熬刭叛减少踅箨熬豢量。对二遴 z 制编码来说更多的重量为2 的列是不可接受的，因为这会增加译码的误码率，并 导致不可检测的译码错误。而非二进制的编码可以包含更多的重量为2 的列而不 箍著降 鑫误疆率。这静梅逡方法壹m a c k a y 静构造法2 a 交纯孬寒，该构造方法中 堆积了一系列觅小的单位矩阵。 超轻构造法a ：构造了要个重量为2 的列之后，进一步在一个要罢的单位阵黪 二二z 放置两个垡罢的单位阵。重复该激程直到最多有廊个重量为2 的列被构造 44 出来，每次都将新的小单位阵放在上次构造的菜一单位阵旁，这样矩阵行的 重量为3 ，4 或更高，这镶毂予上述过程重复了几次。最蘑壤充裁余数列， 使每行的重量尽可能的相等。 2 + 1 5j 燕则码豹搀造 非f 则码即校验矩阵的行或列的重量分布不均匀的码。下面是l u b y ， m i t z e n m a c h e r ，s h o k r o l l a h i 和s p i e l m a n 8 的构遗非正则矩阵的方法。 稳造法i r ：令于为楚终巾簿零元的蕊数。f 由下式绘爨： r = 以玩z 聊， ( 2 8 ) i 这景丹怒磅长，刃怒姣验豹个数，i 是重为j 瓣刭掰占毙捌，。是重为， 的行所占比例。 考虑一个具有，个友节点 上1 ，三， 和，个右节点( 蜀，r ，) 的二分图。对 每一个灌璧为j 戆剜，我们绘歹个二分蚕懿庄繁点标号，弩鹤为该到酶列 号。相似的，对每一个重量为，的行，我们给j 个右节点标上该行的行号。 垮节点厶与节点冀确连。 最后，随机的排列右节点的标母。这样就给漱了非正则校验矩阵。当封 弼 右节点的时候，应避免重复边的出现：对矩阵所有的行，检查有相同标号 j 豹裹警燕是否与鞠圈挥号匏左繁点糖连。若鸯煎重毅撵列，壹至掰有褪嬲 1 4 毒京辩泡学院硕 ：研究生举使论文 标号的右节点都与不同标号的左节点相连。 接建法i r u l a ，i r u l b ：妇莱戆瘁戆歹l 孛鸯繁鲎夷2 戆列，霹鬟一耱爨l r 变 化而柬的方法构造。在这些变化后的方法i r u l a 和i r u l b 中，我们选择 二分图右节点行标号的一种摊列使得重量为2 的列具有u l a 和u l b 构造法 戆槐造影式。焚它熬梅造方浚与l r 洼穗闲。 j c a m p e l l o 等 2 0 提出采用扩展的b i t f i l l i n g 算法柬设计具有离褐率、 高g i r t h 和b e r 性熊良好的l d p c 码；s j 7 0 h n s o n 和s r w e l l e r 2 1 提出一种 基予k i r k m a nt r i p l e 系统豹缀台竣诗方法，遥会予秘建矮褊长、裹玛攀耨在萁 t a n n e r 图( 即二分图) 中不出现环长为4 、g i r t h 至少为6 的厩则l d p c 码 y k o u ， s l i n 和m f o s s o r i e r 2 2 2 3 探讨了基于有限几何学的l d p c 码的结构，将编码 筵讫至煺疆强鹳编鹞电路帮爵实疆；j 。r o s e n t h a l 蠢p ，v o n t o b e l 2 4 】还磷究了基 于r a m a n u j a n 图和按照m a r g u l i s 的概念构建的币则l d p c 鹞，其性能忧于随机构 码方法。 2 3l d p c 码的译码 2 。3 1m p ( m e s s a g ep a s s i n g ) 算法 g a l l a g e r 1 在提出l d p c 码时给出了两种迭代译码算法：硬判决和概率译 强。籍簧显毒磐弱瞧艉，毽太复祭。 m a c k a y 等 2 3 在t a n n e r 5 等前人的然础上，继承了t u r b o 码的软信息 译码思想，归纳了“和一积”算法( s p a ：s u m p r o d u c ta l g o r i t h m ) 。 算法孛缓设：n ( m ) = 私：抒。= l ；表豕参与梭验方穰扰镌篦黪豹綮台， n ( m ) _ 表示集台n ( m ) 中去除元素h 后构成的集台，m ( n ) = m ：h 。= l j 嵌示比 特站参与的校验方疆静集台，掰( 国、掰表示集套掰( 砖中去滁嚣素搬基捣成粒集台： q ：。为比特”从集合 f ( 竹) 珑得到校验信息后被译作x 的条件概率；为比特胛固定 为x ，其它e e 特嶷奄不同盼分稚冀概率为番。，：( 搬) 聍 时，校验方程m 成立的 1 5 南京邮i b 学院f 互| i ：t i j f 究生学位论义 条件概率；码字x 的似然度( 1 i k e l i h 。o d ) 定义为兀臂，其中x 。表示码字z 中的第 n 位比特的取值，爿= 再i 面j 1 面了孬，片= l 一爿，_ y t 为时刻的信道输出。 s p a 算法步骤如下： ( 1 ) 初始化：g ，o 。= 片，g k = 爿： ( 2 )迭代： ( 2 a ) 水平迭代步骤 令国。= q 。o 。一g ：。，对每个m 、 的取值，求出 瓯。= 兀国。， n e f m i n 再计算哦：去( 1 + 吼) ，t 。：去( 1 一瓯。) ； ( 2 b ) 垂直迭代步骤 对每个、n 的t r r * n x = o ，l ，更新g ：= a 。，0 丌。， 。e m f n l 、” 其中口。为一个保证g ：。+ q ：。= i 的可调变量； ( 3 )计算“伪后验概率 ( p s e u d o p o s t e r i o f p r o b a b i l i t i e s ) ”： q ：= a 丌，o = o ，1 ) ； ( 2 5 ) m e 研) ( 4 )基于“伪后验概率”的判决： 若g ： o 5 ，则x 。= 0 ，反之，贝4 x 。= 1 ； 若根据“伪后验概率”判决得到的码字量满足礅= 0 时，则译 码结束，否则，从水平步骤( 2 a ) 开始新的迭代译码； 若经过最大迭代次数后仍然未找到满足礅= 0 的码字，则宣布 译码失败。 图2 2 示出了在二分图上的译码过程中译码信息的传递。 之后，r i c h a r d s o n 等人 1 3 在m a c k a y 的基础上总结归纳出一类基于二分图 结构的消息传递( m p 一- m e s s a g ep a s s i n g ) 算法。它是一个算法类，译码眭能随对 1 6 南京邮电学院硕士研究生学位论文 译码消息( m e s s a g e ) 的量化阶数的增加而提高，同时计算复杂度也会增加。对 译码消息采用两阶量化时，算法即成为g a l l a g e r 提出的硬判决译码，其译码复 杂度最低，性能也是最差的。反之，若对译码消息进行无穷阶量化，即消息是连 续变量时，算法就成为信度传播( b p b e l i e fp r o p a g a t i o n ) 算法。其译码复杂度 在m p 算法类中最高，性能也最好。b p 算法的译码消息也是定义在l l r ( l o g l i k e l i h o o dr a t i 0 一对数似然比) 域上的，译码思想与s p a 一致，在二分图中没 有环的情况下( 即，g i r t h = ) 将精确成为最大似然( m a x i m u ml i k e l i h o o d ) 译 码，具有最优的译码性能。 0 o o 口 o o o o o 图2 2l d p c 码的译码信息传递示意图 m p 算法是一种工作在图论基础上的译码算法。由于在算法运行过程中，译 码信息在二分图中的比特节点和校验节点之间来回传递，故而得名。 设编码后发送到信道上的符号集为m ，译码器的输入符号集为0 ，通常有 0 c m 。m p 译码算法的思想如下：在零时刻，所有比特节点v 。( f = 1 ，盯) 都收到 一信道输出的初始译码消息r ( 取值在0 内的随机变量) ；译码开始后，译码消 息沿着二分图中的边在节点之间相互交换，以第一个译码迭代为例，比特节点f 先 将初始译码消息t 发送到与其相连的校验节点，每个校验节点c ，处理它收到的消 息后，将结果发回给与之相连的比特节点，比特节点再处理、发送如此迭 代下去。比特节点按照消息映射、壬，：f ) o x m 小1 一m ( t 1 ) ，t r y ，( ：0 斗m ( i = o ) 1 7 南京邮电学院硕。研究生学位论文 对其收到的消息进行处理，校验节点按照消息映射叫”：m 以。_ m ( i 0 ) 对其收 到的消息进行处理，其中，为迭代次数。m p 算法中的消息映射可以依赖于迭代次 数，和二分图中的节点，也就是说同一个节点的消息映射可以随迭代次数的变化 而变化，而同一次迭代中，不同节点的消息映射也可以是不同的。 m p 算法中重要的一点是“消息独立性( m e s s a g ei n d e p e n d e n c e ) ”条件：沿 某条边发送的译码消息的映射函数中的自变量不包含来自该边的信息，也就是 蜕，某节点“沿某边e 发送的信息应该与上次节点“沿边e 接收的信息无关。这 一点，在s p a 算法的迭代中也有体现。该条件保证了在同一次迭代中，节点发送 的译码消息与接收的消息相互独立，仅仅发送接收到的外信息( e x t r i n s i c i n f o r m a t i o n ) 。这是一个优秀的m p 算法所必须具有的重要特性，它使得对l d p c 码的译码性能的分析成为可能。 2 3 2 对数域的b p 算法 一个二进制随机变量c o ，1 ) 的统计特性可以由参数p = p r c = 1 来指定，事 实上，它的概率分布可以由对数似然比唯一确定：五- 1 0 9 詈苦品。根据五的符 号可以确定c 的最有可能取值。当1 比0 更有可能的时候，五是正的；当0 比1 更有可能的时候，五是负的。此外，a 绝对值的大小反应了这种判断的可靠程度。 对于一个给定的随机比特ce o ，l ，让r 是指一个概率密度依赖于c 的观察 值，而概率密度函数为f ( r ic ) 。当c 固定，f ( r ic ) 可以看成r 的函数，它被称 为条件概率密度函数。另一方面，当r 固定，f ( r ic ) 是c 的函数，被称为似然 函数。 在进行观察之前，c 的先验概率是p r c = 1 和p r c = 0 。经过一次观察以后， 这些概率变成后验概率p r c = lir 和p r c = 0 ir 。根据概率论中的贝叶斯公式 ( b a y e sr u l e s ) ，后验概率和似然函数是成正比的，即p r c = l ir = f ( r i c = 1 ) p r c = 1 f ( r ) 所以，后验概率的对数似然比可以表达为： 南京邮i u 学院硕i j 研究生学位论史 川。g 器船乩s 等高礼g 黼e ， 右边的第一项被称为对数似然比( l l r ) ，而第二项被称为先验的对数似然 比( p r i o rl l r ) ，左边被称为后验的对数似然比( p o s t e r i o rl l r ) 。如果c 出现 为0 或者1 是等概的，则先验的对数似然比为0 ，并且后验的对数似然比等于对 数似然比。 让我们考虑对一个奇偶校验矩阵为h 的码字进行解码，其中我们已知了 信道的加性高斯噪声，此时接收观察值r = _ ，。 与发送的码字具有以下的关 系： r = 2 c l + n ，( 2 - 7 ) 这里噪声向量n 的分量是方差为盯2 独立的零均的高斯随机变量( 这个式子 意味着存在一个双极性的比特到符号的映射，o 到一1 和1 到+ l ，也就是b p s k 调制) 。 对于这n 个比特，具有最小差错率的检测器将计算后验的对数似然比： 。= ，。g 端= - 。e ；：；渊c z s ， 此时，如果五。 o ，则可以判定c 。= 1 ，否则c 。= 0 。应用贝叶斯准则，上面 表达式的分子： r r c 。= ，1 ， l ；。) = ! ：5 1 1 1 1 j i ；：俨( z 。) 上面的推导从第二个式子到第三个式子是假设了c 。，_ 独立于( 1 ；。 。这 样，2 - - 9 式可以简