（信号与信息处理专业论文）低密度校验码编译码原理及应用.pdf

她京女g 屯大学硕士论文低密度筏验辩藕谭褐瑟理及斑掰 低密度校验碑编译码原理及应用 攮要 低寮菠技验( l 踯c ) 妈愚羊孛遘遮蛰农羧翡鲟鹞，密于冀受好黥经 能、近线形时间复杂度的编码算法、可并行实现的译码算法以及广阔的 旋用翦景，l i ) p c 码已经成为壤遴编鹑鞭域翡礤究热点之一。本文在凌 商理论的基础上，对联磺e 玛灼基本爨瀵窝瘦弱邂嚣耢巍，联褥了一是 静成绩，为以看的深入研究打下萋础。苜先，在线性分组码的基础上介 缬了低密度校验磁的基本原理，总结了鳗前l ，e 码常用的几种编码方 法，并根据8 0 2 1 l n 标准中校验矩阵的特殊性，分绍了基于遮罩孛特殊梭 验短阵的两种篱擎笏行豹编码方法。然瑶，详缁介绍了l d p c 码的硬翔 决译鹈翼涪和软剿决译碣算法，徽点分耩了甚翦竣为常趱的和积译码帮 懋信传攒( b e l i e f p r o p a g a t i o n ) 算法。并介绍了l d p c 码在a w g 烈下仿粪 懿系统捱凝铸寞步骤黧缡译玛模浚静樊嚣实瑗。接着，辑究了一蒂孛特辣 的l ，c 鹨一之鬃鹞，分析之澎弼的编译鹈算法及萁复杂度。最麓，错“ 究了l d p c 码的广泛应用，分析了其在w l a n 中和未来移动通行中的虚 弱，绘出l 褥在8 0 2 1 l 珏中瀚仿粪缭祭，并与卷弦鹳仿真结巢进行 眈较，结巢表明，在l | n 系统翁各种工作模式嗣数据速率下，l d p c 磷 的性能都比卷积码好。 关键诱；迭代译碣憾餐度搜验弱秘襁译璃舅法之彤鹃 无线届域网 北京邮屯大学硕+ 论文低密度校验确编译码原理及应州 c o d i n ga n da p p l i c a t i o n0 fl o wd e n s i t y p a r l t yc h e c kc o d e s a b s t r a c t p m v e dt ob en e a rs h a n n o nl i m i t ，l o w d e n s i t yp a n t y c h e c kc o d e sh a v eb r i g h t p m s p e c t si na l l k i n d so ff m u r ec o m ml l l l i c a t i o ns y s t e m sb e c a u s eo ft h e i ro u t s t a n d i n g p e r f o m a n c e ，g o o dc o d i n ga l g o r i t l l mt l l a th a sa l m o s t l i n e a rt i m ec o m p l e x i t ya n dd e c o d i n g a l g o r i m mt h a tc o u l db ec a r r i e do u tp a r a l l e l ，t h e yh a v eb e c o m eo n eo f t h eh o t t e s tt o p i c si n c o d i n gt h e o r yt o d a y t h i sp a p e rd o e ss o m er e s e a r c ho nt h eb a s i cp r i n c i p l e sa n d 印p l i c a t i o n so fl d p c ，a i l d e s t a b l i s h e sf o u n d a t i o nf o rf u t u r er e s e a r c hf i r s to fa l l ，t h ep a p e ri n t r o d u c e ss o m eb a s i c p r i n c i p l e so ri 。d p co nt h eb a s eo f1 i n e a rb l o c kc o d ea n ds u m su ps o m ef a m i l i a rc o d i n g a l g o r i t h m s ，a n dt h e ng i v e st w os i m p l ec o d m gs c h e m e sa c c o r d i n g t os p e c i 矗cc o n 6 9 u r a t i o n o ft h eb a s ep a r i t yc h e c km a t r i xg i v e ni nt h ep r o t o c o lo f8 0 21 1 na n dt h e n ，t h ep a p e r i n t m d u c e sh a r d a d j u d g e dd e c o d i n ga l g o r i t h ma n ds o n - a d u d g e dd e c o d i n ga l g o r i t l l mo f i 。o w - d e n s i t yp a r i t y - c h e c kc o d e si nd e t a i l ，e s p e c i a l l ya n a l y z e st h em o s tp o p m a ru s e d d e c o d i n ga 1 9 0 r i t h mw h i c hj sc a l l e ds u mp r o d u c ta l g o r i t h m a f t e rt h a t ，t h ep 印e rp r e s e n t s t h es i m u la t j o ns y s t e mf o rl d p ca n dr e a l i z a t i o no ft h ec o d i n ga 1 1 dd e c o d i n gm o d u l ea r e r t h a t ，t h i sp 即e rd o e ss o m er e s e a r c ho nap a n i c u l a rl o w d e n s l t yp a r i t y c h e c kc o d e z i g z a g c o d ea 1 1 dg i v e si t sc o d i n ga 1 1 dd e c o d i n ga l g o r j t h mf i n a l iy ，s u m m a r i z e st l l eb r o a d 印p i i c a “o no fl o w d e n s i t yp a n t y c h e c kc o d e sa 1 1 da n a l y s e sl t sa p p l i c a t i o n si nw l a n a n df u t u r em o b i l ec o m m u n i c a t i o n sw es i m u l a t ei t sp e r f o r n l a n c ei n8 0 21 1 ns y s t e ma n d c o m p a r ei t w i t hc o n v o l u t i o nc o d et h es i m u l a t i o nr e s u l t si n d i c a t et h a tl o w d e n s i t y p a r i t y c h e c kc o d e sa r em u c hb e t t e rt h a nc o n v o l u t i o nc o d ei na l lt h ew o r k i n gm o d eo f 8 0 2 1 l n k e yw o r d s ：i t e r a t i v ea l g o r l t h m l o w d e n s n yp a r i t y c h e c kc o d e s ( l d p c ) s u mp m d u c td e c o d i n g z i g z a gc o d e s w l a n 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处 本人签名： 立j 盏 本人承担一切相关责任。 日期：3 艘6 ：。! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：垒磕 导师签名 h 删： 2 0 q ：2 h 期：3 脚6 3 。l 北京邮电大学硕士论文低密度校验码编译码原理及应用 第一章绪论 提高信息传输的可靠性和有效性，始终是通信工作追求的目标。信道编码是为 了保证通信系统的传输可靠性，克服信道中的噪声和干扰，而专门设计的一类抗干 扰技术和方法。它根据一定的( 监督) 规律在待发送的信息码元中人为的加入以下 必要的( 监督) 码元，在接收端利用这些监督码元与信息码元的( 监督) 规律，发 现和纠正差错，以提高信息码元传输的可靠性。称待发送的码元信息为信息码元， 人为加入的多余码元为监督( 或校验) 码元。信道编码的目的是试图以最少的监督 码元为代价，以换取最大程度的可靠性的提高。 1 1 信道编码的发展 1 9 4 8 年，s b a l l n o n 在他开创性的权威论文通信的数学理论中，首次阐明 了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，即： 对于一个给定的有扰信道，存在一个确定的参数，即信道容量c ，当信道中的传送 信息率r ，如果r c ，则不可能实现无差错通信。 信道容量是信息传输速率的最大值，信道编码定理告诉我们达到这个最大值的可 能性和超过这个最大值时存在的传输问题。丽关于采用什么具体韵倍道编译码方法 才能使得信道的信息传输速率r 逼近信道容量c ，s h 釉o n 并没有给出一个完整的 答案，因此自s h a i l i l o n 提出了著名的有扰信道编码定理以来，人们一直致力于构造 纠错能力接近理论极限，编译码复杂度可接受的信道编码。大致的发展过程可以分 为以下几个阶段h w ： 5 0 年代至6 0 年代，主要研究各种有效的编、译码方法，如纠单个错误的h a m m i n g 码、g 0 1 a y 码、r e e d - m u l l e r 码以及著名的b c h 码编译码方法，奠定了线性分组码 的理论基础。 6 0 年代至7 0 年代初是信道编码发展过程中最为活跃的时期。不仅提出了许多有 效的编译码方法，如门限译码、迭代译码、软判决译码、卷积码的v i t e r b i 译码等。 而且还研究了信道编码的实用化问题，如码的重量分布、译码错误概率和信道模型 北京邮电大学硕士论文低密度校验码编译码原理及应用 佬等，为信遂编弼的实用纯订下了整实麓基锻。期润，f o m e y 籀出了较麓实用的攀 行级联码，它在译码复杂艘没有明显增加的情况下，性能得到较大改善。 7 0 年代褪至8 0 年找怒绷话码麓餍变中懿有极其蘸要意义豹时期。在理论主甄 g o p p a 为首的一批学者，构造了一类线性循环码一一o o p p a 码，其中一娄子码能达 舞酯a 薅遥缀羁定理中所指密韵往莪。掰鱼，在遮期闻，大舰模集成电路帮镦 机的迅速发展，为纠错码的实用打下了坚实的基础。 鑫8 0 年蓰秘酸寒，国p 弘戈稿等人姨蔻帮观点讨论努斩羁，秘用我数魏线构造 了一类代数几何码。代数几何码是一拱范围非常广的码，在理论上已经证明它具有 谯越静键憝。 进入9 0 年代，t u r b o 硒的出现掀起人们对伪随机编码和软输入软输出遮代译粥 箨法翦磷究裹潮，窭现了一系裂剥用遮健泽秘鹣稳编秘方式，魏疆弹c 羁、黍积璐 蒋，这些码都可达到接近s h a n l l o n 极限的优异性能。 进入2 l 世笺螽，信遴编羁理论缝遘逡辩年抟笈髓，瑾论葬警遮诀为轴a m 所提出的点对点a w o n 信道中的信邋编码问题已经获得较为圆满的解决。现在理论 爨救主要研究重点放在对鼗予编码系统、分布试数攥隧终的编疆阀题、多无线无线 通信系统的编码方案以及多用户干扰抵消技术的研究上。 。2 迭代译码 迭鼗译鹨基于逶过霸主一巾适当弱遥符号( 蟾) 匏可纛缝信惑，穆正出信遵接受 的值。这种译码方案可用于由级联得刹的长码的译码，译码步骤被分成几个复杂度 鞍低浆死令步骤势艇逐巷萼霹靠牲信患在译玛步骥之蠲传递。遮耱运符号豹歉输入7 软输出的译码算法也允许同样序列的煎复即迭代译码。 t w b o 的出现g 起了a 翻对迭戴译褥蘸热悸关注，穗蹙各斡琨代豹翱德鹎理论 相继出现，丰富了s h a i l n o n 倍道编码理论，目前出现的性能良好的使用迭代译码的 编码方式 耋要有以下几静： 1 u r b o 码 h r 孙码，又称并行缀联卷积鹞( p e e c ) ，是由c b e r r o u 等在i c c 粥会议上 搬出的，它巧妙地将卷积码和随机交织器结台在一起，如图l l 所示，实现了随机编 玛抟惑瑟。电予确南。玛蹩幽两个或多个分量褐经过不剃交织后对嗣蓓惑序剜送 + 2 ， 北京邮电大学硕士论文低密度校验码编译硝原理及应用 行编码，为了更好的稳麓译码箍之翔的信息，译码算法所用驰是较判决信息得弼酶 也是软信息，一个译码单元的软输出信息作为下一个译码单元的输入。为了获得更 好豹译码性能，将琵过程选代多次，遮藏燕软输入软输出熬遮代译码算法，采用这 种译码方法，可以使译码复杂度在可接受的范围内能达到接近s h a i l n o n 限性能。 模拟结栗表明，如栗采用大小为6 5 5 3 5 的随机交织器，并鼠进行1 8 次迭代，剐 在最，地0 7 d 8 时，码率为l ，2 的r b o 码在a w g n 馆遘上的误比特率( b e r ) 蔓l o ， 达到了近s h n o n 限的性能( 1 2 码率的s h a | ：i n o n 限是0 d b ) 。 爿- 艺 霉l lh 抟。秘编码器 t u r b o 码的优越性能震动了学术器，被认为是编码技术发展的一个重要里程礴。 人们磺究发现，黼码之所以有搬就优越的性能，主蘩是它的编译码方法基本实现 s h a n n o n 证明信邋编码定理的三个熬本条件：1 ) 采用随机编码方式；2 ) 编译码长腋 _ + 。；3 ) 译褐采角最大 娃爨译稻算法。 目前1 、玎b o 弼己广泛地应用于第三代移动通信系统中。 低密度校验码 交予弧痨。弱臻莛驰性戆，缳捩或为謦际嫠患论窝绽玛鬓谂赛骚究兹热点，燕 是对t u r b o 码的深入研究，人们才。发现它与1 9 6 2 年o a l l a g e r 提出的低密度校验( l 0 w d e n s i t y 糯r 姆 赫l ，e ) 玛1 有许多稳舷之韪，它稍在编羁蠛都采用醚撬编码爨方 式，在译码端都采用迭代译码方式。g a l l a g e r 当时之所以没有发现l d p c 码的这一特 性，主舞骚困在于当时谤冀搬毂傍囊轻力有簸，无法对码长较长麴l d p c 璃进毒亍傍 真实现，而且芷魑由于硬件水平的限制，使得学术界当时也错谡的认为l d p c 码译 码算法过于复杂，无法在实际系统中应用露一痘忽视。直到1 9 9 6 年，艇a c k a v 秘 n e a l 2 j 酋先揭示并证明采用b p 迭代译码算法，l d p c 鹤县有逼近s h a f l n o n 限的性能， 从此l d p c 码的研究跨入了个毅灼阶段。 北京邮电大学硕士论文 低密度校验码编译码原理及应用 与糯r & 码鞠跣，l d p c 码其有一套较为系统的优化设诗方法，更强大的绷错麓 力和更低的地板效应，同时由于l d p c 码迭代译码算法为并行算法，延时远远小于 曩t 鳓筠赫串行造代泽弱舅法。这些都为l d p c 玛的应搿提供了广阔静裁景。 尽管t u r b o 码在3 g 通信标准中获得了主导地位，但现在许多正在拟定的通信标 准帮更多戆关注了l d p c 鹤。翻翔，l d p c 璐作为d v b * s 2 ( 斑e2 埔g e n e 拖t i 。n 击g i t 鑫l v i d e ob f o a d c 勰t i n gs a t e l l i t e ) 通信标准和n a s aj p l 实验索推出的深空通信e c s d s 标 准中懿傣道编玛镞逸方案；砸在掇定静w 耋a n 标凑8 。2 1 1 e 和w 淞n 标准8 0 2 1 l n 都采用了i 。d p c 码作为信道编码的改进方案。 r a 弼 1 9 9 8 年，d i v s a l a r 等提出了r a ( r e p e a t i a c c u m 啦a t e ) 妈t 即重复累积鹦。它具有 t u f b 0 码_ 芊曙l d p c 娲的优点，即编码和译码都舆有线性时间复杂度。 ( q j v ，) r a 码的编码方法是对个输入信息比特或。，d 。，每个比特麓复g 次， 并对这g ，个比特进行交织得到序列，z ：，。“。输出序列x ，x 。经过模二累加得 戮：并l = 丑，置= 茸一i + = ，对予江l 。 生矩堕卜巨乎兰岖乎叠” t p c 码 图卜2 ( 2 柏r a 码缟码嚣 1 9 辩年，垮赫i 旗提出瓣 ，c 强f 孙p d u 麟c o 如臻! 一静赢效豹二维薅魏编码技 术，它在离码率的情况下比t u r b o 码更加接近s h a n n o n 情道编码定理的理论极限， 器量梅遗方法菲常麓錾，可强鑫嚣个或多个筑分篷玛缀联稳残长弼。我们域两分量 玛为例，令一、c 2 装示两个系统线性分组码，( 一，鼻，一) 表示分组码c 。的参数，扛1 ，2 ， 箕中一表示编码鹃长，毛表示信息瓦特长度，表示最小汉硝距。则乘积码表示为 p = c 嚣，其中8 表示k n e e k 穰，黎积玛懿搀或鄂鳊妫梃踅搬强1 3 和1 4 辩示。 毙哀瓣电大学碛士论文 糕密度校验羁编译碍摄理瑟澎耀 + 一堤+ 吲l 每一 i 。舢缸 时i e c b l | f ! 圈l 一3t p c 的结构躅 l 编码器l 交缎嚣l 编码嚣l 端卜4 隶积码鳊码榧蕊 黎积码的码长n = h ，坞，信息比特长度= 毛如，援应的最，i 、汉明矩为 d = d 如，因此整个编码码率露= 塌心= 量堡。莱积码块包括信息块、行校验 lo 块、列校验块以及校验的校验块。这样，组合最小汉明距较小的短码，可以构造出 最，j 、汉明题 # 鬻大的长鹈，麸蔼获摄优勇麴纠姥挂熊。 t p c 译码采用修正的c i a s e 簿法的送代译码技术，这种次优译码算法的计算耋 较小，面且译码过程中不需要修燕信遒噪声方羞豹储值。在8 0 2 ，l & 中评c 码作为 推荐的信遭编码方式。 z i g z a g 码 2 0 0 1 年，攀坪等人擒出了一种新型的纠错码一之型码f 5 “，它可形成非常简捷的 软输入软输出舰则，之型码可以羲作一种特殊的l d p c 码。仿真结果表明，其性能 在误比特率为1 0 4 处距番农理论极限仅1 9 d b 。在中簿或高硝率的情况下，这种码字 的性耱更好。嚣且，多维缓联之型妈其寿敞标准强f b 。羁更低的误差她板。 除此之外，还有低密度生成粥( l o wd e n s i t yg e n e r a t o rc o d e l ，m n 码，并行缀联 g a i a g 码等都是性能优异豹信道编码。 北京邮电大学硕士论文 低密度校验码编译码原理及应月j 3l d p c 码的研究豌状 陵着遥蔷技术翁发震，国p e 褐已经戒为淫售领域静研究热点。强翦，溪蠹筇瓣 l d p c 码的研究工作主要包括以下几个方面： ( ) 己b p e 褥静构遣及傀耗 校验矩阵的构造主要是设计适台不同通倍系统的非规则l d p c 码。采用的方法 是营先剥用线槛瓣划l i n e a rp g f a m m i n g 拇0 1 ) 、密瘦遴纯，e x l t 等工箕饶纯设计 l d p c 码的度分布，然后按照该分布生成相应的校验矩阵。最初，l u b y 等人采用线 性援列秘密度进纯方法撬纯度分奄褥造基棼非怒爨毛d p e 筠在a w g 辩荣遒番 r a y l e i g h 衰落信道下，与规则l d p c 码相比，性能得到极为显著的提高。最新的研 究表孵，菲褒裂己，c 璐在嘉蓊经遭下，洒鹞长鸯1 0 7 对燕篱弧a 盘n o n 疆只霄 0 0 0 4 5 d b ，远远超过了t u r b o 码的性能；d a v e y 和m a c k a y 从减少1 h n e f 图上的小 薜路有利于改善译码褥经豹概念窭发，提出了蕊于磷国) 趣 萄翡多进镯l d p 羁， 它能进一步提高了l d p c 码的译码性能。近来，人们对l d p c 码在r r c e 信邋、m i m o 信道、o f d 麓、醚l 鹾。一o f d m 系绞中己d p c 鹦躺设诗避行了磅变。在短弼长条停下， 度分布的分析和优化仍然是当前的研究热点。 棂搂绘定熬鹅长、强率鞠度分_ 蠢，棱骚颦阵的具髂生或方法燕要分蠢健鼗稳遗 和随机构造两丈类。代数构造方法，如组合设计、有限儿何等方法，其优点是能够 绘出辑嚣棱验矩孵绻襁并毒效懿避免短霉路熟存在，懋楚垂手代数翡遥方法受疆予 特定代数结构韵特性，无法构造出任意码率的校验矩阵。而随机构造方法中最主要 的薅静橡造方式为m a c k a y 等人提出躲构造方法帮 u 提出蛉p e g 梅造方法。 ( 2 ) l d p c 弼的译码研究 在l d p e 码译码算法的研究方嚣，g a l l a g e r 最早提出了二元盏教信道下概率泽璃 算法”。m a c k a y 基于连续信道和软判决译码提出的和积( s u mp r o d u c t ) 译码算法， 梅文献f l3 】中被称之为置信传攫( b e l i 联p p a 9 3 l o n ) 算法，该算法实质上是g a l l a g e f 概率译码算法的对数域实现。为了达到译码复杂度和译码性能的最佳折中，先后提 出了各种简化算法。随着l d p c 码的逐步适用亿，译鹦冀法的量化及援应的性能分 析人们也件了大量的研究。 l d p c 码迭代蹲码的性能分析一蠢是l d p c 编码技术的研究热点。当妈长无穷 l 豪豁窀大学磺士论文羝密瘦校验玛编译羁辕理及痘爰 长，不存在短环路的条件下，针对不同的信道和不同的译码算法，采用高斯：i 鲢似、 密度进彳七藕嚣x 仃等分析方法，精确的分析出l d p c 璃鲍璐论极限。当码长为有限 长时，目前二进制删除信道和a w g n 信道下的性能进行了分析。另外，人们采用统 诗力学( s t a “辩i c a lm e c h “i c 曲静分析方法龟褥出l d p e 鹞羲德惩性能。 ( 3 ) l d p c 码的成用研究 l o p c 褊静度蠲研究主要蘩中在对备释遂信环境下静应用弱牲熊分析。班) p c 碣 由于其优异的性能和相对较低的编译码复杂度在各种通信系统中都有广泛的应用。 ( 4 ) l 葑p e 释静嫒件实现 随着l d p c 码的豳益实用化，它的备种硬件实现也涌现出来。目前已有的硬件 芯片与产品衣； 1 ) f l a r i o n 公司推出的可编程l d p c 译码器，采用5 比特近似的b e l i e f p 辨g a 蛀冀法。毛瑚i c 码熬编璐器采躅躺p 芯劈实理，蒜骞羁率秘鹳长 可变等特点。 2 ) l u c 尊墩技术公霹已经疆转实现? 一款援予毙逶落粼络麴l d p e 码编译羁 器，释吐量为1 0 g b p s ，码率为0 9 3 ，误粥率为l 矿”。 3 )在攀母咎技术霉骣会议“l s s c e2 ) 0 5 ”上，螽湾赫兹交道大学穷缓了魏艇拜发 的宽带无线u w b 用基带l s i 中封装l d p c 码。l d p c 码长廉为6 0 0 位，编 码率燕3 珥。棱盎行判豹类型为“半趣则”型，也就是说嚣方囱静翔投( 擅为“l ” 的要素之和) 可在1 l 1 4 之间变化，列方向的加权则固定为3 。编解鹑器 出1 5 0 个信息带点单元鞠5 0 个捻燕节点单元构或。 4 )在半导体技术国际会议“i s s c c2 0 0 5 ”，意法半导体也报告了他们开发的支持 d v b - s 2 规格的调制与解码l s l 。纠错码采羽l d p c 码。采用9 0 n m 工艺c m o s 技术制造。调制方式为q p s k 时，离纠错码的瑗论极限一香农极限 ( s h 煳nl i m i t ) 仅差0 - 3 0 5 d b 。这是反复进行5 0 次躬码处理后获得的结 粟。 幽于l d p c 码的优越性能，业界评价缀高。我们可以乐观的估计，作为t u r b o 码强有力的竞争者，在下一代无线通信、光通信、广播电视以及存储设备领域的应 用正在急剧增加。 北京邮电大学硕士论文低密度校验码编译码原理及应用 1 4 论文研究内容 本文主要讨论了目前信道编码领域的热点课题l d p c 码。分析了主要的编译码 算法，并分析了l d p c 码的应用，其中重点讨论了其在w l a n 新标准8 0 2 1 l n 中的 应用及性能。 第二章，在线性分组码的基础上简述了低密度校验码的基本原理，然后介绍了 目前l d p c 码常用的几种编码方法，并根据8 0 2 1 1 n 标准中校验矩阵的特殊性，介绍 了基于这种特殊校验矩阵的编码方法。 第三章，讨论了l d p c 码的译码方法，并仿真了l d p c 码在a w g n 信道下的性 能。 第四章，介绍了一种特殊的l d p c 码一之型码，分析了之型码与l d p c 码的编 译码复杂度，并仿真给出了之型码在a w g n 信道下的性能。 第五章，分析了l d p c 码在未来通信领域中的应用，重点介绍了l d p c 码在 w l a n 下的应用，并给出仿真结果和性能分析。 第七章，总结全文，谈论下一步的工作和需要解决的问题。 北京邮电大学硕士论文 低密度校验码编译码原理及应用 第二章l d p c 基本原理及编码算法 2 1l d p c 码的溉念 1 9 6 2 年，g a l l a g e r 首次提出低密度奇偶校验码【l j ，即l d p c ( l o wd e n s i t yp a r i t y c h e c k ) 码，它是基于稀疏校验矩阵的线性分组码，并证明了该码具有接近香农限的 性能，还提出了性能和复杂度适中的译码算法。出于当时技术条件的限制，人们的 兴趣大都集中在有实现可能的编码方式上，以致l d p c 码在很长一段时间内几乎被 人们遗忘。 直到1 9 9 6 年，m a c k a y 和n e a l 2 】随机构造的l d p c 码当码长很长时在性能上超 过了b e m u 等人提出t b o 码，而且在实现上更有优势，从而激起了编码界对l d p c 码的研究热情，这是继n b o 码之后纠错码领域掀起的又一研究热潮。 2 1 1 线性分组码 我们通常在有限域上讨论码构造，具有q 个元素的有限域也称为g a l o i s 域，用 g ，臼) 或者c 表示，擐简单的域是二元域g f ( 2 ) 。一个t ) 的线性分组码将t 位的 信息序列u = ( ，) 映射成n 长的码字c = 瓴，) ，r 位校验元( r = h t ) 与k 关的n 维向量岛乳，作为基底的线性组合。 g = | l ， 北京邮电大学硕士论文低密度校验码编译码原理及应用 枷一翰的矩阵h ，g 的符和h 的行正交，印g h l 司，h 1 是h 的转置矩阵，0 怒 一令女妇一女) 的全零矩阵，称h 为校验矩阵。缀容易谖圈鹦字秘校验矩薄满足鞋下 关系： c | = 0 绒者 妒= o 。 如累生成矩阵g 经过有限的行运算和列置换后，转化成g 2 f 那】的形式，其中p 是枷一) 维矩醉ti 为l 的单位矩阵。这时，生成的码字前k 位与消息位对应， 蓉下的如一女) 位魄特是夔警阮特，与之对疰戆校验矩阵为壬差= 瑟女。i 。】。 一个码字中非零元素的个数称为码重，任意两个码字之间对应位置上不同的元 素戆个数髂为投骥鞭褰。 2 1 2帅p c 码的嫩义 l d p c 码是一类特殊的线性分组码，特殊之处就在于它的奇偶校验矩陴h 中非 零元素秘个数菲霉少，远远小于零元索麴个数，掰鞋l d p c 玛霹由蕊控验矩降亲定义。 按照校验矩阵每行和每列中非零元素的个数是否相等，l d p c 码可以分为舰则l d p c 筠彝非援女l p e 璐。撬l l 转p c 璐瓣寝验踅黪巾每一列稼含疵个嚣零元素，每一稽 包含吐个非零元素，若码长为，则可记为( ，d 。，d 。) 。 二元l d p c 鹞的稀疏矩阵是一个0 ，1 矩阵，一个码字悬合法的，当且税当它与校 骏矩阵的熊积在模2 加法和乘法运算下是一个全零向量。蒋将l d p c 码推广剩一般有 隘域g f 妇 圭，g f ( 孽) 上l d p c 褐的稀疏矩阵的元豢是飙g f 国) 上取值。一个粥字是合 法的，当且仅当其姆校验矩阵的乘积在g f ( g ) 的加法和乘法运算下怒全零向爨。图2 - 1 怒二元f 2 0 ，3 ，4 ) 规莉l d p c 码豹校验矩黪。 北京邮电大学硕士论文 低密度校验码编译码原理及应用 墨2 一l 搀2 乱蕊一4 、磊= 3 规则l 黼碣棱验撇阵 若奇髑校骏矩阵珏窍m 行 列，且h 矩阵为满秩的，则该码的鹳率曼为： 置。1 一丝：l 一生 nd 1 2 1 3 l d p c 码的二分豳袭示 ( 2 2 ) 设l d p c 褐韵校验斑阵h 为一个膨除豹矩阵，该矩阵可以由= 分图( 也 称t a n m r 图) 表示。图的左边有个节点，每个节点表示校验矩阵的列，称为比特 节点f 瞧胃称为燮薰节煮) ；右边有材个爷煮，每个节点表示个整验纂，称为校骏 节点；与校验矩阵中“l ”茹索相对皮的左右两个节点之间存在连接边。我们将这条边 称受嚣漆节点耥稠邻透，翱邻逑掰端熬节煮称鸯籀邻焘。每个节点耦邻韵透数称为 该节点的度数。 对子蔑舞豹l 鹨来说，棱验矩簿串每一行帮每一舞孛“l ”静个数备宣穗稳， 对应的二分图中左边节点度数和右边节点度数分别对应着一个固定值。图2 2 为 o ，3 ，妨豹二分爨衰示。庭边錾 萼孝帮患的瘦数为3 ，表透校验警熹豹瘦数为6 ， i b 京邮电大学硕士论文 低密度梭验粥编译硝原理及应用 c 瓣2 2 f l e ，3 ，6 揽萋l 弹璃娉弧n n e f 鞭表隶 对于非规则l d p c 码梭验矩阵，行成列的非零元素不搿固定，对应的瓿m e t 圈 中信息节点和校验节点韵度不褥相嗣，它们分别服从各自的度分布。 定义l p d c 福t b 特节点的分布函数丑o ) 和校验节点的分布p ( ”分别为 ( x ) 豁乏：焉qo 一3 ) 矿砖篇芝痧矿2 氇嘲 式中齿靼盛癸燃表示技验矩阵中毙跨翦点秘校验繁悫戆最大度数i 焉和砖分别表示 殛n n e f 翻上艘为f 躺诧特节煮和校验节点相连韵边占所有边的比例。国( 2 3 ) 式和( 2 - 4 ) 式霹褥强n n e r 图孛密为| 静院特节点数为 ，i牛赤 弘5 ， ，i 垒：磊膳 一 度为，的校虢节点数为 强n n e r 鹫中的憨遗数为 埘，喇苏“：2 r 女 一1 2 ， f 2 塔) u 轧 仉 h 北京邮电大学硕士论文 低密度梭验码编译鹤原理及成用 肚喹7 蒿州高 或 塞，嚣埘志 所对应的非规则l d p c 码的码率为 ( 2 * 7 ) 2 8 ) 砥 舻等小等 。， 娥粼穰l c 娲燕菲鬟粼l ，e 稻耱特铡，宅也霹驳蠡发势蠢来袭示，拓圈2 - 2 豹 ( 1 0 ，3 ，6 ) 规则l d p c 码，系数 = l ，矶= 1 ，即坝x ) = x 2 ，“x ) ；x 5 ，则根据 2 鲫式 可得褐率最= l ，2 。 校验矩阵的环也可反映在t a n n e f 中，图2 ，3 所示的为长为4 舶环在校黢矩阵和 两枣f 中静表录。 圈2 34 _ 琢在校狳矩阵和h n n e r 中的巍示 虫子d | 强译羁算浚采惩选投译玛，冀舞法麴撵罨是基予程莰在帮纛簿簧遴翡 信息缆计独立，当有环存在时，某一节点发出的信息经过一个环长的传递会被传网 奉赛，胰蔼造成蠹赛售惑熟叠搬，破辐了猿纛的啜设，影响译硝熊准确性。先了凝 究环的存在对译码性能的影响，人们提出了豳长( g i n h ) 的概念。所谓的围长，是 撰一令l d p c 码袋对应的弧n n e r 图孛簸小环长，该篷至少为4 曼必为鳃数。 从直观上肴非规则l d p c 码性能优于规则l d p c 码。因为在变量节点和校验节点 的总度数一定时，度数丈螅变量繁点从校验麓点褥到晦信息较多，隧孬貔够更好缝 被正确译码，这些正确的译码信息经校验节点提供给度较小的变量节点。使度较小 的变量节点也糍更好她被蕊确译码。理论分析和仿真结果证明了这一点。对g f f # ) 上的l d c p 码已有的结果证明其性能较二进制码优。 薅 北京邮电大学硕士论文 低密度校验码编译码原理及应用 2 1 4l d p c 码的构造 l d p c 码是一种随机码，没有特定的生成多项式和校验多项式。描述该码的参数 为码长和稀疏校验矩阵中比特节点和校验节点的度分布。构造方法是根据通信系统 中要求的码长和码率来确定校验矩阵的维数，然后通过线性编程工具等获得性能优 异的度分布表达式。最后根据优异的度分布填充非零元素的位置。目前已有多项技 术来具体构造校验矩阵，主要分为代数构造和随机构造两类。最常用的随机构造方 法为： 1 )根据给定的列和度分布，采用( 2 - 9 ) 式计算出校验矩阵的行； 2 )定义一个射x 全零矩阵，并根据矩阵的度分布采用( 2 - 5 ) 和( 2 - 6 ) 式计算列和 m 中的重量分布： 3 )对矩阵中的第t 列( 1 ) ，从个列中不放回的随机抽出一个做为该列的重 量，设为厶：随后，从该列的m 行中随机选取l 行，并将对应位置的非零元 素簧为1 。如果这一置换使矩阵产生周期为4 的短环路，则删除这一列所有非 零元素并重新选取丘行进行非零元素置换，直到该列不产生周期为4 的短环路 为止： 4 )列方向上的非零元素生成完成以后，需在肘行方向所对应的非零元素进行调 整，使得非零元素在行方向上也达到烈功所规定的分布。调整方法为在保持列 位置不变韵条件下将非零元素从数量过多的行调整到数量过少的行，在这一过 程中同样要避免产生周期为4 的短环路； 通过以上步骤所生成的校验矩阵通常具有很好的随机性，保证了l d p c 码迭代 译码中两个子码之间的独立性，从而使得迭代译码具有优越的纠错性能。 另一种常用的随机构造方法是h u 采用“步步最优”的策略，构造出具有较大围 长的l d p c 码的有效方法渐进边增长( p m g r e s s i v ee d g e - g r o 研h ；p e g ) 算法。他通 过在已有t a n n e r 图上依次添加边，使得每次添加边时都尽可能减少对已有1 锄n e r 图 的围长的影响，来构造最终的1 m e r 图。该算法不但适用于正则l d p c 码的构造， 也适用于非正则l d p c 码的构造。 北京邮电大学硪士论文低密度校验码编译码原理及应用 2 。2l d p e 璐逶霜编鹳方法 粼码的难点在于它瓣编褥方法，本节主要 重论鹱槛梅选燃秘豹死秘逶粥 的编码方法。 2 2 。l 蟪性分缎码通用编码 设麒瓣粳验矩菸毂勰联毒移帮是线瞧无关熬。掇攫癸照鹨定义，慰于耱入 信源， ，“，编码藤褥到鹳譬c ，c f ”，满足方程： l k 7 = 0 ( 2 - 1 0 ) 为了在接牧端易手诞分信意经翱较验证，通常采潮系统谒。挺是，对于任意 个陡枫榴造的校骏矩阵戡它其精释系统鹂的形式，绷此首先黼要对缭定翻钉棱虢矩 阵珏遴抒捌变换，分瓣裁【a | 弼魏形式，其中a 为村维浆矩阵，狂为村掰缭 豹满秩怒阵，鹤字c 一似 棚满足 【a b 岈。 则 a 群+ l 酗嚣嚣q - 1 2 ) 嚣魏，撰辫筱验证 p = b 一a ( 2 一1 3 ) 其中“一”号表示商量b 。a # 的逆嚣，在二避瓤编码孛逆元巍它率巍。 该方法的计冀复杂发表现在计冀b _ 1 a ，大终为联膨3 ) 。擐楚，若在实际的遴馈 系统中采蠲相阏校验矩阵，刘b 。a 通进预计算并存储，其计算复杂度为埘哟。 2 。盖2 b u 分解 利用嚣矩陲的稀疏特性，对校验健尹= 嚣“a 口的求鳃采用娃下方法：蒋先对b 矩阵进行i j u 分解，即b = l u ，其中l 为下三角矩阵，u 为上三角矩阵。则校验谯 潢足l l 一一a h 方程，然羼透过戳下步骤计簿较验位p ： * 】5 北京邮电大学硕士论文 低密度校验码编译码原理及应用 l z 一度# ，出予a 是稀蔬篷薄，掰驻计算对揭燕眈予 羲 2 ，令l = y ，趔t 尹= ，透过嚣肉递麴运舞褥劐良爨芦鳃徨 3 ) 通过后向递! 翻运算，解方程l = ，得到梭验信息一。 薯2 3 蔫觜耩去法 采用高麟消去法把校验矩阵化衡为如鲻2 - 4 所示鳃等价下三角矩阵： _ 一肛m - * 一m 一 一- 瓣2 5 下五瘴彩式酶奇偶援验矩捧 构造系统码。= “，p ) ，采用( 2 1 4 ) 式的回带法计算校验位比特： n “ 秘2 葛q ，疗+ 蒿蝎一一巧 弘1 4 ) ，= i，宣l 2 0 0l 挣p c 码静有效编码方法 上凡节酌编鹊方法中采用豹l i j 分勰和离辩游去法避避一系列鹣运算，嚣霄可戆 破坏了棱验炬阵的稀疏性。为了充分利用校验矩阵的稀疏特性，文献【1 4 】搬出了近似 线性复杂度婚编码方法。它的编码步骤如下： 步骤l 预处理 1 ) 三角化 为了不改变h 矩阵的稀疏特性，仅仅对i i 矩阵的行和列重排，得到如图2 s 所 豕的近似下兰免稀疏降蠢： 1 6 。_、i!籽；。t 北京邮电天学碗士论文低密度校验码编详码原理及应用 噜斛甜呻_ g 竹涮曙p 酗毫 ； 霹2 避憧下曼霜瓣校验挺辫 辨豪霹为摇下形式： 巍= 忙耋：) ， 獒孛a 静雏数舞掰一拶秘阳嗨，器药嚣，蕈为( 魄bf 为g ( 够，玲为苫挚e 为g ( 强葑，基t 是对角线元素全必l 豹下三角簌黪。在三角 缘过程孛，使矩簿瓣熬髫罨霹藏夺。 ( 2 ) 秩验算 瓣蠡左乘瘫簿 f l 静、 l e 譬川l j 往一t 妨 锼其藏先拳下籀鸯静弱艇肄 ( 一e t 文+ f 一驸气+ 移习 ， 鹱舅母= 一嚣蕈。b 矜是褥菲奇辫，著奇辩，列与前褥强重簿，直至谈斑砗为非 奄舅。 步骤2 编码 竣霾艨对瘦豹系统羁岛。稿，热，艘) ，其。p # 为系统e 特，尹l 帮p2 海校骏拢 特。校擂方程承；= o 可得： a h + 科+ 勖；= o 0 嚣t “a + f k 7 + ( - l 鬻”b + d ? 一。 犯一1 8 ) ( 2 一l 辫 ；，im； 北京邮电大学硕士论文低密度校骢硒编译码原理及应用 辗攥拉- 1 乃式，得 鼽= m ( 一i f r 一1 a + f ) 具体的计算过程和复杂度如表2 * l 所示： 表2 。l 热= 馨。一班。a + d ，瓣计算过稳 ( 2 1 2 0 ) 矩阵运搏计算嶷杂度备注 a ”7 d ( ) 稀疏缒阵相乘 t 一a 辩j 9 ( ， 耩琉缒薄递归运算 一e t 。【a 矿】 d ( 0 稀疏矩阵相乘 f h 7硝) 稀疏矩阵相乘 一e t 洚拜l + f 牡1 联) 趣法 一中+ 1 ( 一e t 1 a 脚十f 7 )p ( 孽2 ) g 。g 阶矩阵相乘 由( 2 m 1 8 ) 式计算n ，2 = 一t 一( a + 田睁j )( 2 也1 ) 其俸麓| 卡算过程舞表2 0 掰承： 表2 - 2 肌；一t 。( a + l | p j ) 的计算过程 矩阵运算计算复杂度备注 a 矿状奶 耩瘫矩薅挺黍 脚j 0 ( ) 稀疏矩陴相乘 a w 7 + 却j 0 ( ) 加法 l 下。江棚婿 9 ( ) 臻筑矩簿递l l = 运算 一1 8 一 北京邮电大学硕士论文低密度校验码编译码原理及应用 2 3 基于特殊校验矩阵的编码方法 l d p c 码校验矩阵的构造是基于稀疏的随机图，所以该类码字编码和译码的硬 件实现比较复杂，联合考虑l d p c 码的编译码f ”1 ，以单位阵的循环移位阵