（通信与信息系统专业论文）联合ldpc码和网络编码的合作通信技术研究.pdf

重庆邮电大学硕士论文 摘要 摘要 下一代移动通信对数据传输速率和各种业务的需求不断增加，客观上要求具 有能够满足更高的数据速率，支持各种业务的通信技术方案。协作通信技术有望 成为解决高速数据传输的候选技术之一。协作通信技术利用合作用户的空闲天线， 形成虚拟多天线，从而获得空间分集增益。l d p c 码是一种接近香农限的优秀纠错 编码技术，网络编码改变了过去存储转发的数据发送方式，提高了频率利用率。 协作通信技术可以将信道编码与网络编码结合起来，进一步提高系统的性能和容 量。本文将l d p c 码和网络编码应用于协作分集，所做的主要研究工作如下： 1 、研究了结合l d p c 码的三种协作通信系统的性能。针对两用户的协作通信 系统模型，对放大转发，译码转发，编码协作等三种传统协作分集方式进行了详 细分析；以图形的形式给出了两用户协作通信的仿真模型，介绍了具体的协作过 程；研究了选择性协作条件下，结合l d p c 码与协作通信的三种协作分集系统的 性能。仿真结果表明：选择性协作能够减小基站和协同用户的处理复杂度，使得 系统的整体性能得到提高。 2 、对两用户情况下联合l d p c 码和网络编码的协作通信系统进行了研究。通 过构造能够消除四环的结合了l d p c 码和网络编码的整体码字的h 矩阵，将l d p c 码应用于结合网络编码的协作通信系统。通过仿真，比较了不协作、译码转发、 联合l d p c 码和网络编码的协作等三种情况下的系统性能。仿真结果表明：在瑞 利衰落信道条件下，联合l d p c 码和网络编码的协作比译码转发至少有3 d b 的改 善。 3 、研究了结合l d p c 码和网络编码的联合迭代译码技术。首先在具体场景下， 推导了几种联合迭代译码算法；其次通过仿真，比较了硬判决硬判决的独立网络 和信道译码、硬判决软判决的串行网络和信道译码、没有消除四环的联合网络和 信道译码和消除四环的扩展联合网络和信道译码四种联合译码方式的性能。仿真 结果表明：在a w g n 信道条件下，采用不同编码形式情况下，消除四环的扩展联 合网络和信道编码方案改善尤为明显。 关键词：l d p c 码，网络编码，协作通信，联合迭代译码，整体码字h 矩阵 重庆邮电大学硕士论文 a b s t r a c t a b s 仃a c t t h en e x tg e n e r a t i o no fm o b i l ec o m m u n i c a t i o n si si n c r e a s i n gd e m a n df o rd a t a t r a n s m i s s i o nr a t e sa n dv a r i o u ss e r v i c e s ，t h eo b j e c tr e q u i r ec o m m u n i c a t i o n st e c h n o l o g y s o l u t i o n sf o rm e e t i n gt h eh i g h e rd a t ar a t e sa n ds u p p o r t i n gav a r i e t yo fb u s i n e s s c o o p e r a t i v ec o m m u n i c a t i o nt e c h n o l o g yw h i c hi ss o l v i n gh i 曲一s p e e dd a t at r a n s m i s s i o n i s e x p e c t e d t ob e c o m eac a n d i d a t ef o ro n eo ft h e t e c h n o l o g i e s c o o p e r a t i v e c o m m u n i c a t i o n st e c h n o l o g ym a k e su s eo faf r e ea n t e n n at of o r mav i r t u a lm u l t i a n t e n n a , g e tt h es p a c ed i v e r s i t yg a i n l d p cc o d ei sag o o de r r o rc o r r e c t i n gc o d i n gt e c h n i q u e s n e a rt h es h a n n o nl i m i t ，t h en e t w o r kc o d i n gc h a n g ed a t ad e l i v e r ym e t h o d sw h i c hi ss t o r e a n d f o r w a r d , i m p r o v i n g t h e f i e q u c n c yu t i l i z a t i o n c o o p e r a t i v ec o m m u n i c a t i o n t e c h n o l o g yc a nb ec o m b i n e dw i t hc h a n n e lc o d i n ga n dn e t w o r kc o d i n g ，f u r t h e ri m p r o v e t h ep e r f o r m a n c eo ft h es y s t e ma n dc a p a c i t y t h i sa r t i c l ew i l la p p l yl d p cc o d ea n d n e t w o r kc o d i n gi nc o o p e r a t i v ed i v e r s i t y , t h em a i nr e s e a r c hw o r ki sa sf o l l o w s ： 1 、s t u d yi nt h et h r e ec o o p e r a t i v ec o m m u n i c a t i o ns y s t e mp e r f o r m a n c ew h i c h c o m b i n e 晰廿ll d p cc o d e s f o rt h et w o t i g e rc o o p e r a t i v ec o m m u n i c a t i o n s y s t e mm o d e l ， d e t a i l l ya n a l y s i so nt h r e ek i n d so f o ft r a d i t i o n a lc o o p e r a t i v ed i v e r s i t ya p p r o a c hw h i c h i n c l u d et h ea m p l i f i c a t i o na n df o r w a r d ，d e c o d ea n df o r w a r da n dc o d e dc o o p e r a t i o n ；g i v e t w os i m u l a t i o nm o d e lo fc o o p e r a t i v ec o m m u n i c a t i o ni nt h ef o r mo fg r a p h s ，d e s c r i b e s t h es p e c i f i cc o o p e r a t i v ep r o c e s s ；u n d e rs e l e c t i v ec o o p e r a t i o nc o n d i t i o n s ，t h ec o m b i n a t i o n o fl d p cc o d e sw i t ht h ec o o p e r a t i o no ft h r e ec o o p e r a t i v ed i v e r s i t yc o m m u n i c a t i o n s y s t e mp e r f o r m a n c e s i m u l a t i o nr e s u l t ss h o wt h a t ：s e l e c t i v ec o o p e r a t i o nc a nr e d u c et h e b a s es t a t i o na n dc o o p e r a t i v eu s e r st h e p r o c e s s i n gc o m p l e x i t y , t h eo v e r a l ls y s t e m p e r f o r m a n c ei si m p r o v e d 2 、i nt h ec a s eo ft w o1 x s o i s ，s t u d yi nj o i n tl d p cc o d e sa n dn e t w o r kc o d i n g c o o p e r a t i v ec o m m u n i c a t i o ns y s t e m t h r o u g hs t r u c t u r et h eo v e r a l lc o d ew o r dh - m a t r i x w h i c he l i m i n a t ef o u rc i r c l e st oc o m b i n et h el d p cc o d ew i t hn e t w o r k c o d i n g l el d p c c o d e si su s e di nc o o p e r a t i v ew i t hn e t w o r kc o d i n gc o m m u n i c a t i o ns y s t e m t h r o u g h s i m u l a t i o n ，c o m p a r ew i t hn o n c o o p e r a t i o n , c o d e dc o o p e r a t i o n ，j o i n tl d p cc o d e sa n d n e t w o r kc o d i n gc o o p e r a t i v es y s t e mp e r f o r m a n c e s i m u l a t i o nr e s u l t ss h o wt h a t ：i nt h e r a y l e i g hf a d i n gc h a n n e lc o n d i t i o n s ，t h ej o i n tl d p cc o d e sa n dn e t w o r kc o d i n g c o o p e r a t i o ni si m p r o v e da tl e a s t3 d bt h a nc o d i n gc o o p e r a t i o n 3 、s t u d yi nj o i n ti t e r a t i v ed e c o d i n gt e c h n i q u e sw h i c hc o m b i n et h el d p cc o d ew i t h 重庆邮电大学硕士论文 n e t w o r kc o d i n g f i r s t ，i ns p e c i f i cs c e n a r i o s ，d e r i v es e v e r a lj o i n ti t e r a t i v ed e c o d i n g a l g o r i t h m ；f o l l o w e db ys i m u l a t i o n ，c o m p a r i n gw i t h h a r dd e c i s i o n - h a r dd e c i s i o ns e p a r a t e t h en e t w o r ka n dc h a n n e ld e c o d i n g ，h a r dd e c i s i o n s o f t - d e c i s i o nt h es e r i a ln e t w o r ka n d d e c o d i n ga n dj o i n tn e t w o r ka n dc h a n n e ld e c o d i n gw i mf o u rc i r c l e sa n de x t e n dj o i n t n e t w o r ka n dc h a n n e ld e c o d i n gw i t hn of o u rc i r c l e s s i m u l a t i o nr e s u l t ss h o wt h a t ：i nt h e a w g nc h a n n e lc o n d i t i o n s ，u s i n gd i f f e r e n te n c o d i n gc o n d i t i o n s ，t h ee l i m i n a t i o no ft h e f o u rc i r c l e so ft h ej o i n tn e t w o r ka n dc h a n n e lc o d i n gs c h e m ei sp a r t i c u l a r l ye v i d e n t l y i m p r o v e d k e yw o r d s ：l d p cc o d e s ，n e t w o r kc o d i n g ，c o o p e r a t i v ec o m m u n i c a t i o n s ，j o i n ti t e r a t i v e d e c o d i n g , t h eo v e r a l lc o d ew o r dhm a t r i x i i i 重庆邮电大学硕士论文 第一章绪论 1 1 引言 第一章绪论 随着科技的发展和人们业务需求的专业化，精细化，移动通信技术得到了飞 速的发展，特别到2 1 世纪，移动通信技术更是达到了前所未有的成就。第一代移 动通信系统以模拟技术为主，典型的如美国所使用的高级移动电话系统a m p s 。源 予欧洲的第二代移动通信技术g s m ，采用了数字化技术，主要业务是传送语音和 低速率的数据。与第一代移动通信系统相比具有很明显的优点，如频谱利用率高， 保密性好，系统容量大等。随着移动通信的发展，人们越来越追求高速率的数据 业务，3 g 技术支持数据，图像，多媒体业务，具有较高的数据速率，满足了业务 发展的需求。在此基础上，3 g p p 弓 领制定了第三代移动通信系统标准：欧洲的 w c d m a 技术、北美的c d m a 2 0 0 0 技术，以及我国具有自主知识产权的t d s c d m a 技术。 2 1 世纪初，无线业务需求继续增长，人们对移动通信的服务质量和数据传输 速率的要求不断提高。在国际电信联盟无线电通信部关于下一代移动通信系统的 纲领性文件m 1 6 4 5 中，明确要求，低速用户的传输速率要达到1 0 0 m b s ，高速用 户要达到1 g b s 。 在无线通信环境中，两个严峻的挑战存在于高传输速率通信中。首先，高传 输速率传输必然带来严重的信道衰落。例如，空间选择性衰落，时间和频率选择 性衰落。摆在我们面前的一个重要问题是如何克服衰落的影响，提高信号的传输 质量。其次，无线频谱稀缺的现实，要求必须提高有限频谱资源的使用效率。使 用传统的办法解决这些问题似乎非常困难，因此亟需寻找新的途径来提高移动通 信系统的可靠性和有效性。为此人们进行了大量的研究，其中包括采用调制技术， 信道编码技术和分集技术，而近年来，学者提出的协作通信技术有望成为解决高 速数据传输和大范围网络覆盖的关键技术之一。 协作分集是无线通信领域提出的一个新概念，它的基本思想是通信系统中的 移动终端都有一个或多个协作用户，移动终端不仅传输自己的信息，还帮助协同 用户传输其信息，通过这样的方式，在信息传输的过程中，终端通过利用了协作 伙伴的空间信道，从而获取了一定的空间分集增益n 1 。由于目前的多天线主要设置 在基站，移动终端上很难安装多天线，而协作分集通过用户间共享天线，构成了 虚拟的m i m o 系统，因此上说，协作分集为m m o 技术实用化提供了一种新的方式。 使得单天线的移动用户在多用户协作的环境下，获得分集增益和m i m o 的容量优 重庆邮电大学硕士论文 第一章绪论 势，而且实现起来更加的容易。 具备协作通信能力无疑是未来移动通信网络终端、中继站甚至基站的基本技 术特征之一。 1 2 研究背景和意义 作为一类重要的协作通信技术，信道编码和网络编码的应用，将会极大地拓 展协作通信的内涵和意义，它能够充分的利用信道编码的冗余优势和网络编码的 协同优势，而且有助于进一步提升和改进通信性能和协作效能，极大地提高通信 的容量和传输效率。 总而言之，联合信道编码和网络编码机制是信道编码，网络编码思想和协作 通信思想有机融合的产物。 目前，对联合信道编码和网络编码的研究才刚刚起步，大部分的研究主要有 三方面：( 1 ) 信道编码在协作通信中应用( 2 ) 网络编码在协作通信中的应用( 3 ) 联合卷积码，t u r b o 码的网络协作通信系统。 由于协同分集的冗余特性，怎样更加有效的利用信道编码将是一个亟需解决 的问题。从信道编码的角度看，h u n t e r 和n o s r a t i l l i a 首先将信道编码引入协同分集， 提出了编码协作的概念，当用户间信道条件较好时，在不同的信道，发送用户的 不同码字，从而获得空间分集增益；当用户间信道条件差时，自动的转到非协作 模式，使得误码率明显的降低【2 】【3 】【4 】【5 1 。s t e f a n o v 和e r k i p 在文献中研究了基于卷积编 码的协同编码通信系统，码字的两部分由源节点和中继节点分别传输，从而获得 编码增益【2 1 。在文献【6 】z h a ob i n 研究了适用于半双工通信模式的分布式t u r b o 编译 码方案。z h a n gz h e n g 提出了改进的合作t u r b o 编译码方案，它分别适用于时分半双 工通信和全双工通信模式，能够逼近中继通信系统容量，与前述的分布式t u r b o 编 译码方案所不同的是，为了提升合作编码性能，改进的合作t u r b o 编译码方案，源 节点采用完整的t u r b o 编码器， 中继节点则采用t u r b o 译码器【7 】i s 】。k h o j a s t e p o l l r 在 文献 9 3 5 b 提出了全双工中继技术的l d p c 码编码方案，虽然从信息论的角度来看， 方案可能不是最优。但是它的性能优良，并且结合了实用中继l d p c 编码设计的大 部分关键因素，即有限字符集的容量分析，协议设计，功率分配，因子图构建和 解码算法 9 】。c h a k r a b a r t i 等人将l d p c 码引入编码协作协议，证明了在随机编码的 情况下，能够接近香农限 1 0 】。同时文献【1 l 】在编码协作中的信道编码采用了l d p c 码。文献 1 2 1 中对编码协作进行了扩展，将空时编码与编码协作方法结合，通过空 时码进行发送，证明在快衰落信道条件下可以获得完全分集增益，且频谱的利用 2 重庆邮电大学硕士论文 第一章绪论 率也高。上述对于信道编码在协同中的研究表明，编码设计和码型的选择对协同 分集的性能改善具有重要的作用。 第一次将网络和编码进行结合，提出网络编码概念的是香港中文大学的 r w - y e u n g 和n c a i 等人。其主要思想是：在网络中，参与传输的节点不仅是单一 地执行存储转发功能，而是可以通过对来自多条链路的数据进行一定的线性或非 线性处理，且对源节点所发送的信息，保证接收节点可正确恢复出来，从而达到 网络的最大容量，最大限度的利用网络现有资源。 网络编码思想的提出从本质上打破了通信网络中传统的存储转发信息处理方 式，在优化功率受限网络的功率消耗，提高网络的带宽资源利用率、平衡链路负 载方面具有很大优越性。另外，无线传播信道的广播特性为网络编码的应用提供 了更为有利的条件，俨然成为通信网络研究领域中的新研究热点。网络编码和协 作分集都能有效地提高通信系统的传输性能，那么如何把这两种方法自然融合， 充分挖掘网络编码在协作分集技术研究中的潜能，成为众多学者研究的一个热点。 在网络编码协同分集中，c h e l a 首次提出了网络编码协作分集的概念，并在分 布式天线和多用户协作网络中考虑了网络编码的应用 1 3 】。李严梅研究了基于网络 编码的两种协作分集方式：基于信号叠加协作分集和码字叠加的协作分集，证明 了网络编码可以进一步提高通信系统的性能 1 4 】。c o n gp e n g 较为系统的研究了网 络编码协作通信的中断概率和分集复用折中性能，证明了网络编码协同通信的性 能要优于单纯的进行协作通信【1 5 】。在实际的环境拓扑考虑下，s t e f a n o v 较早的研究 了两用户之间信道不理想时协作系统的性能增益 1 6 1 。 在联合信道编码和网络编码合作通信中，郝建军将卷积编码和网络编码应用 于两用户合作通信中，通过对性能的分析和仿真，证明了在快衰落和慢衰落环境 中性能的有效改善 1 7 1 ；另外一些学者将t u r b o 码和网络编码应用于协作分集中， 通过性能的分析和仿真，证明了联合编码设计方案能够有效降低错误概率和提高 信道容量 1 8 。c h r i s t o p h 从因子图的构造方面考虑了网络编码和l d p c 码的应用， 构造了整体码字的因子图，通过与其他系统对比和分析，证明了信道编码和网络 编码结合时性能的有效提升 1 9 】。l i 在多源一中继一目的节点拓扑下，分析了因子 图中软信息的传递和迭代译码算法 2 0 】。 1 3 选题意义 u ) p c 码性能优越，译码算法是一种并行算法，更加有利于硬件的实现。与 t u r b o 相比，译码复杂度低，当码长足够长时，l d p c 码具有比t l l r b o 码更为优良的 重庆邮电大学硕士论文第一章绪论 性能。并且具有较大的灵活性和较低的错误平层。目前，已经在众多领域得到应 用，成为了下一代移动通信系统信道编码方案的有力竞争者。 网络编码通过在中间节点进行编码或线性组合而不是存储转发的形式，使得 信息的传输速率能够达到最大流，打破了传统的路由方式，充分的挖掘了网络的 潜在能力。近年来的研究表明，除了能够提高系统的容量之外，网络编码也能够 在减小网络的传播时延，负载均衡，提高网络的能量利用效率，增加网络安全方 面提供帮助。 目前，大部分的研究都集中在信道编码或网络编码在合作通信中的应用，对 联合信道编码和网络编码在合作通信中的研究还相对较少，受网络编码或信道编 码在合作通信中应用的启发，研究联合具有很高纠错能力的l d p c 码和网络编码的 合作通信技术具有很大的意义。 1 4 主要研究内容和结构 本文研究了l d p c 码和网络编码联合的问题，在具体的协作拓扑结构下，构 造了整体码字矩阵，分析了联合译码性能并进行了仿真。最后，从译码的角度对 几种译码方案进行了仿真分析，论文的具体内容如下： 第二章，给出了l d p c 码的定义，重点介绍了l d p c 码的编译码算法和h 矩 阵的构造；之后详细说明了网络编码的基本原理，基本方法。 第三章，首先给出了两用户协作的系统模型，详细介绍了三种传统协作分集 和仿真模型，最后采用选择性协作的方式，对三种协作分集进行仿真分析，给出 三种协作分集方式的分析结果。 第四章，在两用户拓扑结构下，将l d p c 码和网络编码应用于具体协作过程， 研究分析了编码和译码方式，构造了整体码字的h 矩阵，并应用p e g 算法构造了 整体码字矩阵，对h 矩阵进行消除四环的操作，最后通过仿真分析，证明联合l d p c 码和网络编码方案性能的改善。 第五章，首先给出了蝶形网络结构，详细介绍了网络编码和信道编码结合的 三种联合译码方式，最后在进行相同编码和不同编码的情况下，对四种联合迭代 译码方式进行了仿真，并对仿真结果进行了分析。 4 重庆邮电大学硕士论文 第二章l d p c 码和网络编码的基本原理 第二章l d p c 码和网络编码的基本原理 2 1l d p c 码 1 9 6 2 年g a l l a g e r 在自己的博士论文中提出了一种线性分组码低密度奇偶校验 码( l d p c ) 【2 l j 。他证明了l d p c 码具有优良的性能：( 1 ) 码字的最小距离随码 长的增加而线性增加。( 2 ) b s c 信道下译码的错误概率随码长而指数减少。( 3 ) 提出了两种迭代译码算法，但由于计算机技术的发展滞后导致计算能力的不足， 使得l d p c 码很少被人提及，直至1 j 1 9 9 3 年b e r r o u 等发现了t u r b o 码，才知道t u r b o 码 从某种角度上说也是一种l d p c 码，l d p c 码所具有的巨大实用价值和优越性能近 几年才被人们重新认识到。 2 1 1l d p c 码的表示方法 l d p c 码是稀疏的奇偶校验矩阵，它的每一行( 列) 所含的非零元素的个数都要 远远小于这一行( 列) 元素的总个数。奇偶校验矩阵中每一行非零元素的个数成为行 重量用d c 表示，每一列含有的非零元素的个数成为列重量，用d 。表示。图2 1 给出 了规则l d p c 码的稀疏奇偶校验矩阵。 l0 0111o o ol00o 0 010 0 001 0o o1 10 0 1o 00 0lo oll000l 0l1o10o 0 0 0l0l0 l0 0 0oo1 图2 1 规则l d p c 码 如果奇偶校验矩阵h 中每一行和每一列的行重和列重都分别相同，对应的矩阵 称为规贝i j l d p c 码，其码率为1 一d ，d 。从图中可看出，行重为d c = 4 ，列重为吐，= 3 。 非规贝i j l d p c 码的校验矩阵中各行的行重和列重是不完全相同的，因此不能像 规贝j j l d p c 码那样通过常数来表示，而是通过度分布多项式以，p ) 乜3 1 来表示，其中元 和称为度分布函数，并定义为： 五g ) = 以x “( 2 - 1 ) o l o o 0 1 0 1 o 0 0 l 0 1 0 o 1 0 0 o 1 1 o o o o 1 0 1 0 l 0 0 0 o 1 o l o 0 1 0 1 o 0 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 ( 2 - 2 ) 式中五表示与列重为f 的变量节点相连的边占所有边的百分比，岛表示与行重 为f 的校验节点相连的边占所有边的百分比，d ，表示最大列重，d 。表示最大行重。 规则u ) p c 码是非规贝i j l d p c 码的一种特殊情况，对于规则的l d p c 码，用度分 布多项式可以表示为： 。旯g ) = _ ( 2 3 ) p ( x ) = 工厶q( 2 - 4 ) 如果用p 和p 分别表示f 兄g 和f p g ，那么在l d p c 码的校验矩阵是 满秩的前提下，l d p c 码的码率可完全由度分布多项式计算得到： r c 以，户) = l 一【p p ) ( 2 5 ) l d p c 码还可以用因子图【2 4 】来进行表示，因子图由变量节点，校验节点以及 相连接的边组成，图2 2 给出上图中h 矩阵相对应的因子图表示。图中的圆圈表示 变量节点，表示经过编码之后的信息比特位，它对应于奇偶校验矩阵中相应的列； 右侧的方框表示校验节点，代表一个由所有非零元素组成的校验方程，对应于奇 偶校验矩阵的相应的行，而相关的边表示了信息比特参与了方框所表示的校验节 点的校验方程。 变量节点 2 1 2l d p c 码的编译码 图2 2 因子图 校验节点 l d p c 码是一种线性分组码【2 5 】，可以通过向量空间e 的一个特定的七维子空 间c 来表示。从而可以找到k 维子空间c 的一组基召= g 。，g lp ，g 。q ， 2 2 】。因此， 对任何c c ，存在着系数函， ，能够使得c 可以表示为： 6 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 c = u o g o + 甜l g l + + u k - i g t l ( 2 - 6 ) 也可以将式( 2 1 ) 写为c = u g ，其中”= 【u ou l u 】，而g 便是一个k x n 的生成矩阵，它的每一行对应了一个向量霸。而奇偶校验矩阵h 是一个0 一七) 刀 的矩阵，它对应空间c 上，每一行对应于一个向量忽。所以对于任何c c ，有c 忍- = 0 ( 0 i 万一k 1 ) 。 l d p c 码的编码可以通过信息比特与码字生成矩阵相乘来实现。对随机构成的 l d p c 码来说，首先把奇偶校验矩阵化为l i i p ti 的形式，然后就可以通过转化得到系 统形式的生成矩阵h i i 。而且某些l d p c 码的校验比特可以直接通过信息序列和校 验矩阵来求得。另外，一些特殊构造的l d p c 还可以采用其它一些非常高效的编码 方法。 在b p 译码算法中，节点之间传递的是概率信息，它是经过信道之后的码字中 每个比特为0 ( 或者为1 ) 的概率，称为置信。图2 3 与图2 4 用因子图分别说明了外 信息如何在变量节点和校验节点之间进行转移的，它们都基于最大后验概率准则 进行传递。 d | 1 0 c n i c n 2 图2 3 变量节点的信息转移图列 7 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 8 b 帆b 沌 图2 4 校验节点的信息转移图列 图2 3 中变量节点的信息转移图例说明，变量节点b n 0 传递给校验节点c n 2 的 外消息就等于c n 0 、c n l 传递过来的外信息和经过信道之后b n 0 获得的初始外信 息，c n 2 传递给b n 0 的外信息并不包括在内。这也正是遵循外消息传递原则所致。 图2 4 与上面的说法相同，校验节点c n 2 传递给变量节点b n 2 的外信息，依据的 是和c n 2 相连的b n l 、b n 2 传递过来的外信息，但b n 0 传递给c n 2 的信息并不包括 在内。 由于l d p c 码的码长不可能无限的长，所以环的存在将是不可避免的事实，环 是指沿着边从某个节点出发又回到原始节点所经历的路径，这时的外信息就不是 纯正的外信息，这是因为环的存在，使得传递出去的外信息在经过一定的迭代次 数之后包含在有其他节点传递给自己的外信息之内。如果这个节点的初始信息有 错误的话，错误将会被放大，从而反复的影响自己的后验概率的计算，影响译码 的性能。因此在进行b p 译码的时候，应该尽量避免在构造的h 矩阵中存在着四环 等短环，使得译码性能受到影响。 下面我们对b p 译码算法【2 i 】的具体译码过程进行详细的推导和分析，对于码字 矢量c 中的某个比特c i ，计算b p 算法所对应的最大后验概率： ，( 1 7 i = 1 ) = p ( ( c i = 1 y ，墨) j ( 2 7 ) 其中c 表示经过信道后在接收端观测到的码字矢量，y 表示发送端的码字矢 量，墨表示一个事件，换而言之，就是比特c i 参与的所有奇偶校验方程都被满足。 引理2 1 一个长为m 的二进制序列a = ( q ，4 。) ，a l 之间相互独立，用足表示 a 。为1 的概率，那么序列口中包含偶数个1 的概率为： 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 p 蝴= 序列a 中包含偶数个1 的概率为： p 刎2 l + 兀o - 2 p 。) l l 1 一兀( 1 - 2 p 。) 2 ( 2 - 8 ) ( 2 - 9 ) 在这里，定义g 玎( 1 ) 和( 1 ) 为： 劬0 ) ：在除去c n j 以外，其他所有与删，相连的c n 的外信息以及来自信道的 观测结果y ，的外信息已知的情况下，e l 为1 的概率。 乃( 1 ) ：在c i 为1 以及所有与c ，相连的b n 具有独立分布且为l 的概率已知的情 况下，q 被满足的概率。 于是很容易能够得到如下公式： o ( o ) = 告+ i 1i - i ( 1 2 q 移( 1 ) ) ( 2 - 1 0 ) 厶f 毫r i f l r j i o ) = 吉一告兀( 1 2 q 移( 1 ) ) ( 2 - 1 1 ) 厶 厶i e r j i 劬( o ) = 0 - p i ) 兀“o ) ( 2 - 1 2 ) j e c t l i q 扩( 1 ) = p ，兀r j ，( 1 ) ( 2 1 3 ) j j e c t f j 其中r 朋表示除去啡以外所有与q 相连的b n 组成的集合，q ，表示除去 c n l 以外所有与叭相连的c n 组成的集合，e 表示y f 已知的情况下c ，为1 的概率。 根据y ，计算出如( 1 ) 和口矿( o ) 的初始值，利用上面几个式子反复计算g 茚( 1 ) 、 g i f ( o ) 、勺( 1 ) 和( o ) ，就可以得到b p 译码算法的具体过程了。 下面给出了完整的基于概率域的b p 算法： 1 初始化：( 假设比特0 映射为+ 1 ，比特1 映射为1 ) 劬( 0 ) - - 1 - 霉= p ( c f = 眠) = 1 ( 2 - 1 4 ) g 扩( 1 ) = 霉= p = 1 l ) 2 i ：芸刀7 ( 2 - 1 5 ) 2 校验节点计算： ( 0 ) = 圭+ 勺( 1 ) = 圭一 9 2 9 吩( 1 ) ) 一2 9 。( 1 ) ) ( 2 - 1 6 ) ( 2 - 1 7 )o，o 兀兀 l 一2 1 2 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 3 比特节点计算： q o ( 0 ) = k 驴( 1 一只) 兀( 0 ) ( 2 1 8 ) j e c t j 劬( 1 ) = 巧p 兀，：，f ( 1 ) ( 2 1 9 ) j 9 黜i lj 其中常数项k v 是用来保证勤( 1 ) + ( 0 ) = 1 。 4 后验概率计算： q ( 0 ) = k ，0 - p , ) i - i r j , ( o ) ( 2 2 0 ) ，e q q ( 1 ) = k ，只兀o ( 1 ) ( 2 2 1 ) ，e 白 其中常数墨用来保证q f ( 1 ) + q ( o ) = l 。 根据( 2 1 5 ) 和( 2 1 6 ) 式，对码字c 中的比特c ，进行硬判决：如果q ( o ) 0 5 ，则 判c ，= 0 ，否则就判为1 。然后计算c h t 是否为零向量，如果是，则本次译码结束； 若不是，则返回2 继续进行循环计算直至c h t 为零向量或到达预先设定的最大循环 次数。 基于概率域的b p 译码算法中包含有大量的乘法计算，计算复杂度较高，如果 果进行硬件实现的话，将非常不利。 下面我们将b p 译码算法从概率域转换到对数域，对数域的b p 算法采用加法运 算，非常有利于硬件的实现，因此在实际中都是使用对数域的b p 译码算法。 下面我们定义： 厶蜘。g 瑞 酬乩g 铡 三( r o ) = l o g 瑞 ( 2 - 2 2 ) ( 2 - 2 3 ) ( 2 - 2 4 ) 根据上面的式子，对概率域的b p 译码算法进行改造，可得到下面对数域b p 译 码算法的具体推导： 1 初始化： 2 校验节点计算： 其中 三也) = 三心) = 1 。g i o = 2 y f 仃2 ( 2 - 2 5 ) 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 蚓= b r l tm e r f t 叫l l _ el = j 初乜) ) 喇叫吲础( 护。g 筹 岛- - i l g ，】 ( 2 - 2 6 ) ( 2 - 2 7 ) ( 2 - 2 8 ) ( 2 - 2 9 ) 3 比特节点计算： 三g 驴) = 三 ) + 三b ) ( 2 3 0 ) i 戢t | l 4 后验概率计算： 三 ) = l ) + 以) ( 2 3 1 ) 5 硬判决结果计算： v f ， a ：0 i fl ( q i ) 0 ( 2 3 2 ) c ，2 i 1e k , l r 。s l e j ( 2 3 2 ) 然后计算c h t 是否为零向量，如果是，则本次译码结束；若不是返回继续进行循 环计算直至c h t 为零向量或达到最大循环次数。 2 1 3h 矩阵的构造方法 l d p c 码h 矩阵的构造 2 6 】主要包括两种：随机构造法和代数构造法。随机构 造法由g a l l a g e r 构造法，m a y k a y 随机构造法，p e g 构造法，比特翻转和扩展的比特 翻转算法组成。而代数构造方法有：准循环构造法，有限几何构造法，均衡不完 全设计构造法。下面我们重点介绍下p e g 构造法。 在构造l d p c 码时，p e g ( p r o g r e s s i v ee d g e g r o w t h ) 算法【2 7 】【2 8 1 是一种高效的方 法。它在不影响二分图环长的情况下，通过在变量节点和校验节点之间按照 e d g e b y - e d g e 方式建立连接。 首先定义l d p c 码变量节点的度序列： 岛= ( d b o ，奶，识一) ( 2 3 3 ) 其中，d b , 是第i 个变量节点包的度数，满足递增顺序纸奶，蛾一。同样 定义校验节点的度序列： d c = ( 砜，如，呶一1 ) ( 2 3 4 ) 其中，奶是第j 个校验节点勺的度数，满足递增顺序蛾如，蛾一。从 与变量节点集合巧相连的角度看，有边的集合为e = 瓦u & u u- i ，瓦是与 变量节点岛相连的边的集合，0 i 万一l 。进一步，定义与变量节点2 j i 相连的第k 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 条边为磋，o 七奶一1 。 对给定的变量节点魏，根据t a n n c r 图，沿着扛展开成深度为，的子图( 或树图) ， 此时包含的所有校验节点的集合，称为变量节点岛的深度为，的邻居，用心表示， 其补集为税= 圪以。图4 1 为对变量节点觑的z 层子图，从岛开始，走过所有的 边，将与其相连的边记为 ，c ，。) ， ，c ，：) ， ，c j d 岛) ，然后走过与校验节点 锄，勺2 ，c j d b t 相连的边，其中不包括 ，c ，。) ，( 岛，c j 2 ) ， ，c j d 岛) 。一直进行下去， 直到达到要求的深度，此时子图中可能有些节点和边会出现多次。由图4 1 可看出， 在第，层首次出现的任何变量节点与初始节点6 ： 的距离为2 j ，而在第，层首次出现 的任何校验节点与魏的距离为2 ，+ 1 。因此，集合职可以定义为一个集合，集合中 的校验节点与变量节点反的距离小于或等于2 l + 1 。同理校验节点c ，的深度为，的邻 居膨，定义为一个集合，集合中的变量节点与校验节点c ，的距离小于或等于2 ，。 图2 5t a n n e r 图的变量节点展开的深度为l 的子图 对给定的t a n n e r 图参数，包括变量节点数、校验节点数、变量节点度序列， 可以按照e d g e - b y - e d g e 的方法在变量节点和校验节点之间设置新边，而引入的新 边对图的围长的影响尽可能的小，可以使变量节点的本地围长达到最大。关键是 要找到与此变量节点距离最远的校验节点，并在它们之间设置一条新边。 2 2 网络编码 2 2 1 网络编码理论 1 9 9 8 年，香港中文大学的r 0 b e nl i ( 李硕彦) 和r a y m o n dy e u n g ( 杨伟豪) 首 次提出了网络编码的思想【2 9 1 ，网络编码是在路由器中增加智能化功能，将传统路 1 2 重庆邮电大学硕士论文第二章l d p c 码和网络编码的基本原理 由器中对数据包的存储转发方式变为对数据进行线性或非线性操作，然后再转发 出去，由于这一系列的操作是在网络层出现的，因此也称为网络编码。网络编码 的提出，打破了传统的信息处理方式，使得网络能够达到最大的容量，更加充分 的利用网络的资源。并且在平衡链路负载，降低能量消耗，节约网络有限的带宽 资源方面也有巨大的优势。目前，学者对网络编码的研究已经达到了白炽化阶段， 成为当今最引人瞩目的前沿领域。 图论中的最大流最小割定理表明，一个通信网络可以传输的最大流量等于其 最小割。通信网络可以通过有向图来进行表示，由于传统的网络采用存储转发的 模式，并不能实现网络的最大流，所以并不能达到最佳的效果。假如我们使用网 络编码的话，即在网络的中间节点对接收到的信息进行编码处理后在发送出去， 在接收端可以根据网络的要求译码出所需的信息，这样将会极大地提高网络的传 输速率，充分利用网络资源，实现最大流最小割定理信息的传输上限。其实从严 格的定义上来说，传统的存储转发模式的路由方式可以看过是网络编码的一种特 殊表示【3 0 】。 图2 6 蝶形网络图 在图2 6 中，我们假设每条链路容量为“1 ”，源节点s 向目的节点j ，和z 同时发 送两个比特信息6 l 和6 2 。图2 6 ( a ) 中源节点j 分别向中间节点r 和“发送6 1 和6 ：，中 间节点，和节点“再分别