（通信与信息系统专业论文）ldpc译码算法的研究及其在ofdm系统中的应用.pdf

重庆邮电人学硕+ 论文 摘要 摘要 正交频分复用( 0 f d m ) 调制技术由于具有良好的抗多径干扰能力和高效的频 谱利用率，在许多数字传输系统如a d s l 、d v b 、d a b 、8 0 2 1l a 、h i p e f l a n 2 中被 广泛应用，成为当今无线通信研究的热点。1 9 9 6 年m a c k a y 等人重新研究了最早 f l q g a l l a g e r 于1 9 6 3 年提出的低密度校验码( l d p c 码) ，并发现l d p c 码是一种能 够接近s h a n n o n 界限的好码，从此l d p c 码受到业界的广泛关注。由于l d p c 码在很 多方面具有比t u r b o 码、卷积码等更优的性能，将l d p c 码与o f d m 技术结合应用成 为了论文研究工作的核心，这将会有十分重要的理论和实践意义。论文对二进制 l d p c 译码算法进行了研究，主要提出了改进的l d p c 译码算法并最终将其运用到 基于o f d mi e e e 8 0 2 1 l a 标准的无线局域网系统中。仿真验证了算法的可行性以及 l d p c 码与o f d m 系统结合比卷积码与o f d m 结合的有效性更高。论文最后对多进 sf j l d p c 码进行了一定研究，并提出了一种更简化的译码算法。 传统的二进制概率域l d p c 译码算法( b p 算法) 存在大量的连乘、除法及指 数运算而且当译码循环时，其运算量会以指数形式增加，这不仅增加了复杂度， 而且会使算法的数值稳定性变差，限制其实际应用。针对b p 算法运算量大的缺点， 文章从对数域上来改进b p 算法，将连乘和指数运算等浮点运算转换为复杂度更 低、稳定性更好的加法运算。从而大大降低了运算复杂度，且更利于硬件的实现。 目前，大部分文献提到的l d p c 迭代译码算法均基于b p s k 调制，在未来的 3 g + 高速无线通信中，o f d m 技术必然需要采用频谱利用率较高的多电平调制。而 将l d p c 码用于多电平调制的o f d m 系统时，一方面，l d p c 译码算法不能直接 在多电平调制解调下运用；另一方面，在0 f d m 系统中，译码前信号经过f f t 运 算后，一些由信道提供的后验概率参数的分布会发生明显的变化。要想实现l d p c 与o f d m 的有效结合，需要考虑在l d p c 译码算法上作进一步改进，使之能成功 跨度到基于多电平调制的o f d m 系统中，这也是本文工作的一个重点。 近来，多迸制l d p c 码的研究及应用己初见端倪。文章最后受前文工作的启发， 同样从对数域上提出了一种更简化的多进制l d p c 译码算法。该算法比多进制 l d p c 傅立叶变换算法运算量更低，更易硬件实现。 关键词：低密度奇偶校验码，正交频分复用，对数似然比和积译码，最小和对 数似然比和积译码，多电平调制 重庆邮电人学硕十论文 摘要 a b s t r a c t o f d mm o d u l a t i o nt e c h n i q u eh a sg o o dp e r f o r m a n c e si nw i t h s t a n d i n gm u l t i - p a t h d i s t u r b i n ga n dh i g hu s i n go ff r e q u e n c yb a n d w i d t h s o ，i th a sb e e na p p l i e dd i f f u s e l y ， s u c ha sa d s l ，d v b ，d a b ，8 0 2 1l a , a n ds oo n n o w a d a y s ，i tb e c o m e st h ed i s q u i s i t i v e h o t s p o ti nw i r e l e s sc o m m u n i c a t i o n s l d p ch a sa t t r a c t e dl o t so fa t t e n t i o n so fr e l a t i o n a l f i e l d sb e c a u s eo fm a c k a yw h or e s e a r c h e dn e w l yl d p cw h i c hw a sp r e s e n t e df i r s t l yb y g a l l a g e ri n1 9 6 3a n dr e d i s c o v e r e dt h a tl d p cw a sag o o dc o d ew h i c hc o u l da p p r o a c h t h es h a n n o nl i m i tb ym a c k a yi n1 9 9 6 l d p ch a sm o r ee x c e l l e n tp e r f o r m a n c et h a n t u r b oc o d e s 、c o n v o l v ec o d e so ro t h e r si nm a n ya s p e c t s ，s ol d p cc o d e sc o m b i n i n g 、v i m o f d mw o u l dh a v ea c a d e m i ca n dp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rp a y si t sa r e n t i o n s o nd e c o d i n ga l g o r i t h m so fl d p c c o d e ，t a k i n go u tan e wl d p cd e c o d i n ga l g o r i t h ma n d a p p l y i n gi ti n t ow l a ns y s t e mb a s i n go no f d m i e e e 8 0 2 1l as t a n d a r d s i m u l a t i o n v a l i d a t e dt h a tt h en e wd e c o d i n ga l g o r i t h mi sf e a s i b l ea n dc o m p a r e dt oc o n v o l u t i o n a l c o d e ，l d p c - o f d ms y s t e mh a sa s c e n d a n tp e r f o r m a n c e t h ec o n v e n t i o n a lp r o b a b i l i t yf i e l dl d p cb pd e c o d i n ga l g o r i t h mi st o oc o m p l e x ，i t h a sm u c hf l o a t i n g - p o i n tc a l c u l a t i o ns u c ha sm u l t i p l i c a t i o na n de x p o n e n t i a l s o ，t h e v a l u eo ft h i sa l g o r i t h mi sm u c hu n s t a b l e c o n s i d e r i n gt h e s ep r o b l e m s ，t h i sp a p e rb r i n g s f o r w a r dan e wd e c o d i n ga l g o r i t h mb a s i n go nl o g a r i t h mf i e l d ，l o g l i k e l i h o o dd e c o d i n g a l g o r i t h m t h e r ei sr e a ln u m b e ra d d i t i v ec a l c u l a t i o nn e a r l yi nt h i sn e wa l g o r i t h mw h i c h h a sg o o ds t a b i l i t ya n dt h ec o m p l e x i t yf a l ld o w ng r e a t l y i ti sp r o p i t i o u st oo p e r a t ei n h a r d w a r e p r e s e n t l y ，l a r g ep r e f e r e n c e sr e f e r r i n gt ol d p ca r eb a s i n go nb i n a r ym o d u l a t i o n , s u c ha sb p s k b u ti nf u t u r e3 g + m o b i l ec o m m u n i c a t i o n s t h ee x t e n s i v e l ya d o p t e d o f d mt e c h n i q u er e q u i r e sc o m b i n i n gw i mm u l t i l e v e lm o d u l a t i o n s o h o wt oc o m b i n e t h ec h a n n e lc o d i n gl d p cw i t ht h em u l t i m o d u l a t i o no f d mi so u rp r i m a r yw o r k b u t ， i no n e s i d e ，l d p cd e c o d i n ga l g o r i t h m s c a n n o tb eu s e d s t r a i g h t a f t e r m u l t i d e m o d u l a t i o n , a n di nt h eo t h e rs i d e ，s o m ep a r a m e t e r sw o u l db ea l t e r e dw h e ni t h a sp a s s e dt h r o u g hf f to p e r a t i o ni no f d ms y s t e m u n d e rt h e s es i t u a t i o n s ，a b o v et h e n e wd e c o d i n g a l g o r i t h mm u s tb ea m e l i o r a t e da g a i n t h i sp a p e ri m p r o v e s a b o v e l o g l i k e l i h o o dd e c o d i n ga l g o r i t h mw h i c hb a s e so nb p s km o d u l a t i o n , c a l l e dl o g b p a l g o r i t h m i tr e a l i z e ds p a n n i n gf r o ml d p c b p s km o d u l a t i o nt ol d p c - m u l t i l e v e l i l 重庆邮电大学硕七论文 摘要 m o d u l a t i o ni no f d m s y s t e m r e c e n t l y t h er e s e a r c ha n da p p l i c a t i o no fq - a r yl d p ch a v ec o m ef o r t h g e t t i n g i l l u m i n a t i o nf r o mt h ef o r e g o i n gp a p e r s ，a tt h el a s to fa l lw o r k ，t h i sp a p e rp u tf o r w a r da n e wd e c o d i n ga l g o r i t h m b a s i n g o i l q - a r y l d p c t h en e wa l g o r i t h mh a sl o w e r c o m p l e x i t yt h a nq - a r yl d p cf f td e c o d i n ga l g o r i t h m ，a n di ti sp r o p i t i o u st oh a r d w a r e s r e a l i z a t i o ng r e a t l y k e yw o r d s ：l d p c ，o f d m ，l o gb p ，m i n s u mb p ，m u l t i - l e v e lm o d u l a t i o n u i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重庞鲣鱼盍堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 汤兰 签字日期：酣歹年，月f 同 学位论文版权使用授权书 本学位论文作者完全了解重庆鲣曳太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和僭阅。本人授权重鏖整曳盔堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：侈兰 导师签名： 撇、趴 签字醐碑的r 多日 h 重庆邮电人学硕士论文第一章绪论 1 1 研究背景 第一章绪论 长期以来，纠错编码技术一直被认为是克服由噪声、自然干扰、人为干扰、衰 落以及其它信道损耗所造成的不良影响的一种有效方法，在数字通信的各个领域 中获得了极为广泛的应用，纠错编码主要有分组码、卷积码、t u r b o 码和l d p c 码 等。 在移动无线系统中，分组码和卷积码已得到广泛的应用。如g s m 和i s 5 4 第二 代数字蜂窝标准都采用了卷积码，而其它系统则大都采用了分组码。尽管分组码 的硬判决译码器比较容易实现，但卷积码也具有相对简单的软判决译码算法( 如 v i t e r b i 算法) ，且性能优于分组码，因此，卷积码比分组码更受到青睐。出于实时 性的考虑，移动通信系统中对译码时延的要求比较高，需要高速译码器的支持。 可是，v i t e r b i 译码算法的复杂度与约束长度成指数增长的关系，限制了卷积码的大 规模应用。t u r b o 码是卷积码的并行或串行级联，在数据包较长时可获得比传统级 联码更大的编码增益，被认为是大编码存贮卷积码或传统级联码的替代方案。然 而，t u r b o 码虽已成为3 g 的信道编码标准，但其译码复杂度高，时延长，又由于 宽带无线通信系统对实时通信要求较高，要求数据包长较短且采用复杂度要尽可 能低，因此很难采用复杂度较高且适用于长数据包传输的t u r b o 码。t u r b o 码难以 适应最高数据速率远比3 g 要高的后3 g ( 即b 3g ，或4 g ) 未来无线通信系统的需求。 l d p c 码于二十世纪六十年代由麻省理工学院的r g g a l l a g e r 提出【2 】，由于 受当时硬件处理速度等限制，该码提出之后的数十年的时间里都没有引起人们的 注意。随着计算处理能力的日渐提高，最近d a v i d j c m a c k a y 等重新“发现”并认 识到该码的重要价值 3 1 1 4 1 ：该编码的译码性能可与t u r b o 码媲美甚至更优，具有较 大灵活性和较低的差错平底特性( e r r o rf l o o r s ) ，二迸f l ；j j l d p c 码译码复杂度比 t u r b o 码低：l d p c 码是一种能够接近s h a n n o n 界限的好码1 5 l 。由于l d p c 码是基 于线性分组码的校验矩阵构造的，译码时校验方程组的各个校验方程在进行后验 概率运算时可以完全并行操作，再者其吞吐量大，具有潜在的快速译码优势，硬 件复杂度低，因而适合硬件实现，完全能够满足实时通信系统的要求。 目前，对l d p c 码的应用研究已受到业界的广泛关注，已有学者对l d p c 码在 b p s k 调制下的应用作了初步探讨1 6 】，朱琦等将非规贝i j l d p c 码应用于i e e e 8 0 2 1 6 a ， 重庆邮电火学硕士论文第一章绪论 并在s u i 一3 和s u i 3 多径衰落信道环境下取得良好性能【刀李祥明等【8 】研究了 a w g n 信道条件下基于有限域g f ( q ) 的非规则低密度奇偶校验编码与q 进制结合 实现带宽有效传输和编码优化方法；另外，第二代卫星数字广播标准d v b s 2 已将 l d p c 码作为它们的信道编码方案之一。 在移动无线信道中，信号从发射天线经过一个时变多径信道到达接收天线，会 产生时间选择性衰落和频率选择性衰落。信道的时变特性引起的信号频谱的展宽， 导致d o p p l e r 效应，造成信号随时间呈现选择性衰落；信号的多径传播引起信号在 时间上的扩展并带来频率选择性衰落。根据多径信道在频域中表现出的频率选择 性衰落特性，人们想到了正交频分复用( 0 f d m ) 调制技术。o f d m 将频域划分为 多个子信道，各相邻子信道互相重叠，但不同子信道互相正交，是频谱效率很高 的一种调制技术。应用o f d m 技术，一方面能够克服频率选择性衰落；另一方面， 取小于相干时间的一段时间间隔作为一个o f d m 符号的持续时间，还可以将信道的 时间选择性衰落对传输系统的影响大大降低。0 f d m 由于具有良好的抗多径干扰能 力和高效的频谱利用率，在许多数字传输系统如a d s l 、d v b ( d i 面诅lv i d e o b r o a d c a s t i n g ) 、d a b ( d i g i t a la u d i ob r o a d c a s t i n g ) 、8 0 2 1l a 、h i p e r l a n 2 中均被 广泛应用。1 9 9 8 年7 月，被i e e e s 0 2 1 1 标准组选用作为5 g h z 频段标准基础的物理层 调制技术，这是第一个把o f d m 用于分组业务的通信标准。 然而，在无线环境下，一些子载波由于深衰落可能导致完全丢失，这些深衰落 的子载波将对整个系统的b e r 产生决定性的影响。因此，o f d m 系统必须与纠错 编码结合，提高整个系统的b e r 性能，已有许多将纠错码，如卷积码、r s 码、 t u r b o 码应用于o f d m 的实例。由于l d p c 码具有前述较好的特性，加之其性能较 t u r b o 码更优，于是考虑将l d p c 码与o f d m 结合成为可能，并预期能在无线局域网 系统中取得更好的传输性能。 本文将l d p c 码与多电平调制结合并应用于基于o f d m 的宽带无线局域网系 统( i e e e 8 0 2 1 1 a ) ，迸一步探索多进制l d p c 编译码原理及其应用。 1 2 本文工作 本文的主要工作有： ( 1 ) 针对传统概率域上的l d p c 译码算法( b p 算法) 存在大量的连乘、除法及指 数运算，而且当译码循环时，运算量就会以指数形式增加等问题，本文从对数域 的角度以及采用最小和近似特性将译码算法进行了改进，将大部分连乘的运算转 换为了复杂度更低，稳定性更好的加法运算，从而大大降低了运算复杂度，更利 于硬件的实现。 2 重庆邮电大学硕十论文 第一章绪论 ( 2 ) 目前，大部分文献提到的l d p c 迭代译码算法均基于b p s k 调制，相对于 m q a m m p s k 调制，b p s k 调制频谱利用率太低，在未来的3 g + 高速无线通信中， o f d m 必然采用频谱利用率较高的多电平调制。而将l d p c 码与o f d m 结合时会 出现两个问题：一方面，l d p c 译码算法不能直接在多电平调制解调下运用；另一 方面，在译码前，信号经过o f d m 解调进行f f t 运算后，一些由信道提供的后验 概率参数的分布会发生明显的变化，这样就限制了l d p c 码在o f d m 系统中的实 际应用。要想实现l d p c 与o f d m 的有效结合，研究如何把l d p c 译码算法应用 于多电平调制下的无线通信系统是一个关键。本文在已改进后的基于b p s k 调制 的最小和对数似然比b p 算法的基础上作改进，提出了一种基于距离特性的译码概 率初始化算法，同时解决了上述两方面的问题，通过仿真实现验证了l d p c 码能 在多电平调制的o f d m 系统中有效的应用。 ( 3 ) 基于l d p c 码在o f d m 系统中的应用，在i e e e 8 0 2 1 l a - - o f d m 系统中， 本文将l d p c 码与i e e e 8 0 2 1 1 a 标准中用到的卷积纠错编码在系统误码率性能上进 行了仿真比较，得出的结论是：在与o f d m 结合应用时，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 傅立叶变化译码算 法中还存在着大量乘法等浮点运算的不足之处，提出了一种更为简化的对数域傅 立时变化译码算法，该算法从整体上去掉乘法运算，而转变成较为简单的加法运 算、比较运算和一次查表运算，复杂度大大降低，更有利于硬件上的实现。 1 3 论文结构 本论文的结构安排为：第一章总体介绍本文的研究背景及主要工作；第二章给 出l d p c 码的基本概念，并讨论l d p c 编码构造方法、译码算法和影响l d p c 码性能 的因素等；第三章以i e e e 8 0 2 1 l a 标准中的w l a n o f d m 为参考，介绍无线局域 网系统的参考模型，主要包括系统模型、编码方法和调制方式等；第四章提出新 改进的l d p c 译码算法，并通过m a t l a b 程序仿真，对两种l d p c 译码算法方案进行 比较；第五章将l d p c 译码方案在多电平调制下作进一步改进，给出了基于 i e e e 8 0 2 1 1 a 标准的仿真链路模型，并利用仿真说明多电平调制下l d p c 码与o f d m 结合应用的可行性；第六章迸一步分析多进制l d p c 编码原理及译码算法，提出了 一种更简化的译码算法思路，并指出多进制l d p c 应用研究的迫切性；第七章总结 本文工作并探讨下一步研究方向。 重庆邮电大学硕十论文第二章l d p c 码概述 第二章l d p c 码概述 2 1l d p c 码的发展历史 1 9 4 8 年，贝尔实验室的c l a u d e e s h a n n o n 发表了题为“a m a t h e m a t i c a l t h e o r y o f c o m m u n i c a t i o n ( 通信的数学理论) 的论文，奠定了信道编码理论的基础；1 9 6 2 年 后g a l l a g e r 首先提出l d p c 码1 2 j ，并给出l d p c 码的简单构造( g a u a g e r 构造) 和硬判决概率及用迭代译码的方法来进行译码的译码思路。 1 9 8 1 年t a n n e r 建立了编码的图模型概念【9 】，证明了和积算法在无环图中译码的 最佳性，并提出了构造适合和积译码的图模型的代数方法。 1 9 9 6 年前后m a c k a y 和n e a l 【4 】【埘，s p i s e r 、w i b e r g t “l 和s p i e l m a n t l2 】重新发现 l d p c 码的优越性能。在二进制加性白高斯信道( b i a w g n ) 下，码率为l 2 的 最好的不规j j l d p c 码的门限值距香农限只有0 0 0 4 5 d b 1 3 - 1 5 1 。 1 9 9 8 年d a v e y 和m a c k a y 提出了基于g f ( q ) 的l d p c 码 i “，并得出多进制 l d p c 码的性能在某些情况下要好于二进制l d p c 码；同年，l u b y 等人提出了基 于非规则图的l d p c 码1 1 7 1 。 2 0 0 1 年r i c h a r d s o n t j 等人提出了一种简化的编码方式【l8 】，充分利用l d p c 码校验矩阵的稀疏性，降低了l d p c 码的编码复杂度，可以实现接近线性复杂度 的编码。 2 0 0 1 年和2 0 0 2 年，t o n gz t l 粥和s r i d h a ra 1 1 a 1 2 0 1 1 2 1 1 等从译码优先的角度出发，设 计了一系列低复杂度的l d p c 码，其中，使用单位阵的循环移位阵和全零矩阵作 为子矩阵构造二元域规则l d p c 码的方法设计的译码器在2 0 0 2 年被b l a n k s b ya 等 用硬件实现1 2 ”。 2 0 0 3 年，h o n g x i ns o n g 等几位学者对多进铜j l d p c 码的研究表明【2 3 l ，多进制 l d p c 码在磁盘存储系统中的纠错性能好于作为磁盘存储系统工业标准之一的r s 码的性能。 2 0 0 4 年经过广泛的仿真测试后，从7 种先进的纠错码方案挑选出l d p c 码作为第 二代卫星数字广播d v b s 2 标准内层编码方案，取代此前卫星数字广播标准内层 编码的卷积码，( 外层用b c h 码取代r s 码) 。 可见，随着a s i c 技术的进步，l d p c 码的真正实用化已初见端倪。 4 重庆邮电大学硕十论文 第二章l d p c 码概述 2 2l d p c 码的基本概念 2 2 1l d p c 码的定义及描述 l d p c 码是一种线性分组码，因此具有线性分组码的所有特性。分组码【2 1 1 是 信息序列以后个码元分组，通过编码器将每组的t 元信息按一定的规律产生r 个冗余 码元( 称为校验元) ，输出码字长为n = k + r 。任何一个( n ，露) 分组码，如果其信息 元与校验元之间的关系是线性的，即能用一个方程组来描述的，则称为线性分组 码。( ，七) 线性分组码的每个码字有n 七个校验元，要从个信息元中求出n - k 个校 验元，必须有n 七个独立的线性方程，根据求校验元的不同线性方程，就得到不同 的( 斗，_ | ) 线性分组码。 ( 行，) 线性分组码的编码问题是如何根据已知的j i 个信息元求得n _ i 个校验元。 由于是线性码，它们是由h 岳个线性方程构成的方程组。( 靠，蠡) 线性分组码的2 2 个码字组成n 维向量空间的一个碰匪子空间，而线性空间可由其基底张成，因此( 押， 后) 线性分组码的2 个码字完全可由七个独立的向量所组成的基底张成。设女个向量 为： g t2l 蜀1 蜀2 “蜀女”g l 。j 9 2 。( 9 2 1 9 笠“9 2 “9 2 。) g k = ( l g k 2 g 肚罐k ) ( 2 1 ) 将它们写成矩阵形式： g = 9 1 1 9 1 2 9 1 k & n 9 2 1 9 b 一- 9 2 k ”- 岛。 g k l g k z g 慷“毽h ( 厅，七) 码中的任何码字，均可由这组基底的线性组合生成。即 蜀i g l ：g j i 蜀。 c ：m g ：( 铂。观一。) 9 2 i & 扩” g k l g k 2 ”g u g 缸 ( 2 2 ) ( 2 3 ) 一般而言，( ，t ) 线性码有r = 疗后个校验元，故必须有，个独立的线性方程，所 重庆邮电大学硕士论文 第二章l d p c 码概述 以( 即，i ) 线性码的校验矩阵由r 行和n 列组成，每一行代表一个线性方程的系数。 可表示成： h = h i1 啊2 啊。 吃，：吃。 绋，以：k 由h 矩阵可以建立码的，个线性方程 ( 2 4 ) ( 2 5 ) 简写成；日c 。= 0 或c h 1 = 0 。 由于g 中的每一行及其线性组合均为码的一个码字，所以由式( 2 3 ) 可知生成矩 阵和校验矩阵满足g h 7 = o 或g 7 = 0 7 ，说明由g 与日的行生成的空间互为零 空间。 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即校验 矩阵中只有数量很少的元素为“l ”，大部分都是0 ， g a l l a g e r 最早给出了规则 l d p c 码的定义，采用三个参数聍，p ，鼋来定义规贝j l d p c 码( 疗，p ，q ) ，其中p 是校验矩 阵日中每列所包含的“1 ”的个数，辞是日中每行所包含盼1 的个数，之所以叫规 则码，就是只日中每行所包含的“l ”的个数以及每列所包含的“1 ”的个数分别相同， 这里的q ，p 也称为矩阵目的行重和列重。由于p 和辞都很小，校验矩阵日具有 很低的“密度”，因此由校验矩阵日所确定的码称为低密码校验码( l o w - d e n s i t y p a r i t y c h e c k ) 。图2 1 给出了个由g a l l a g e r ( 1 2 ，3 ，4 ) 规贝j l d p c 码的校验矩阵 图2 1 ( 1 2 ，3 ，4 1 的l d p c 码的校验矩阵 当校验矩阵h 各行或各列中“l 的个数不相同时，就得到非规贝e j l d p c 码m 1 。 6 = 1；j ；q 气 。l 坳 纯坳。助 觑玩 所 。l o o l o o o l o o o l l o 0 o o l o o l o 0 l o 0 l l 0 0 o l 0 0 l o l 0 0 o 0 l o o l o o l 0 o o 1 0 o l o o o l 1 o o 0 o 1 o o l l o o l o o o l o o o 1 o i o 1 0 o o o l o l o o 1 o ，0 0 重庆邮电大学硕士论文 第二章l d p c 码概述 2 2 2l d p c 码的t a n n e r 图表示 因子图( 也称二分图或t a n n e r 图) 模型是当前较为常用的表示l d p c 码的图模 型，它归纳了目前所有的图模型定义，提供了一个关于迭代译码的一般性框架。 因子图模型实质上是表达一个全局函数到一组局部函数乘积的有效分解。 定义：因子图是结构形如图2 2 的二部图，其表达式的因式分解表达为： g ( x ，x 。) = 1 - 1 ，厂， ，) ( 2 6 ) ，e j 。 d 是离散下标集， 一是 葺) 的一个子集，厂( 一) 是以子集置中元素为变 量的函数因子图中，有对应于工，的变量节点和对应于z 的因子节点( 也称检 验节点) ，当且仅当x 是乃的自变量时，变量节点一和因子节点之间有边相 连。 f ；ee 图2 2 二分图( t a n n e r ) 实例 l d p c 码可以用t a n n e r 图来表示。设一个( ，p ，目) 规贝j j l d p c 码具有校验矩阵 h = ( 囊，) 。，则其相应的t a n n e r 图模型可以表示为一个二分图。其中码字向量 x = 瓴，毛- ，) 表示为一组变量节点缸，= l ，2 开) ，分别对应于校验矩阵的各列， 而校验约束则表示为一组校验节点亿，i = l ，2 矾 对应于二分图中的 ，i = 1 ，2 m ) ，表示为校验矩阵中的各行，仅当麓，= 1 时，变量节点x ，与校验节 点z f 之间有一条边相连，节点x ，与z ，之间互称邻接节点，其间的连接边称为两 个节点的邻接边。对于( 玎，p ，口) 规则l d p c 码，每个变量节点与p 个校验节点相连， 称该变量节点的度为p ；每个校验节点与口个变量节点相连，称该校验节点的度为 q ，度表示与节点相连的边的数目。图2 - 3 给出了对应于图2 1 所示的校验矩阵对应 的t a n n e r 图结构。根据c h = o 这一约束关系，与同一校验接点相连的变量值之 和必为o 。 x ix 2x 3 x 4 x 5 x 6 x 7 x 8x 9x l ox l lx 1 2 图2 3 ( 1 2 。3 ，4 ) l d p c 码的t a n n e r 图 变量点 重庆邮电大学硕士论文 第二章l d p c 码概述 对于非规, t j l d p c 码，相应的t a n n e r 图中各变量节点或校验节点的度并不相 同，通常用序列 p l 所。) 和 q ，q 以 来表示其中边的度分布，其中p ，表示与 度为，的变量节点相连的边占总边数的比率，吼表示与度为i 的校验节点相连的边占 总边数的比率，z 和d ，分别表示变量节点和校验节点的最大度数。显然应有 y 4 p ：i 及f 4 吼= 1 ，即部分之和等于全部。这里之所以用边的度分布，而不 一l ，一l 用节点的度分布来描述l d p c 码是因为l d p c 码的译码采用的是基于置信传播 ( b e l i e fp r o p a g a t i o n ) 的软输出迭代译码算法( s o f to u t p u t i t e r a t i v ed e c o d i n g a l g o r i t h m s ) ，也称软b p 算法，如和积译码算法( s u m - p r o d u c ta l g o r i t h m ) ，在译码过 程中，信息的传递是在边上进行的，采用边的分布来描述l d p c 码有助于分析其 在给定译码算法下的实际性能和理论性能的上下界。 2 3l d p c 码的构造及实现 l d p c 编码的问题主要有两类，第一类是校验矩阵日的构建( 日矩阵是与g 矩 阵对偶的一个矩阵，代表了校验特征，抒矩阵经过高斯消去很容易得到生成矩阵 g ，然后就很容易编码) ；第二类是编码的实现，也即由检验矩阵生成码字序 列。校验矩阵日的构建是编码器复杂度及可实现性的核心步骤，日矩阵的好坏直 接影响编码解码的性能。而构建矩阵的核心则是围绕避免短环和增加码问距离 展开，而这两者也有一定关系。因而，l d p c 码构造的实质就是校验矩阵彦的构造， 的随机化构造方法比较常用，因而对其重点介绍；同时相对于随机构造的方法， 本文主要介绍一种确定性的构造方法。本文的仿真实现采用的是随机构造的方法。 在构造矩阵的方法中，又分为规贝u l d p c 码校验矩阵和非规则日矩阵的构造， 下面以规则的u ) p c 码构造为例进行介绍。 如前所述，设规则的l d p c 码为( 拧，p ，g ) ，其中p 是校验矩阵h 中每列所包含的 “1 ”的个数，口是日中每行所包含的“1 ”的个数，注意日中所有行包含的“l ”数量之 和应和所有列包含的“l ”数量之和相等，例如日是所n 的矩阵，则有t n q = h p 。 如果校验矩阵h 是满秩的，则编码码率定义r = m m ) n = 卜4 ，p 。 如何构造日? ，如果已知编码长度n 和码率且，同时给定每行包含“1 ，的数量g ， 则p = m q n ，通过这些参数可构造满秩矩阵日，为了得到好的译码性能，构造 时有个限定条件就是应尽量使矩阵中的最小“闭环”长度g i n l l 最大，或者使长度小 的闭环数量尽量少，校验矩阵中闭环必须是偶数i g i r t h 4 ，也就是说矩阵中任意 两行中“l ”的交迭数不能超过1 。按照上面的限制条件，即每行或列所包含的“l ”的 数量以及最小“闭环”长度g i r t l l 最大化，来构造校验矩阵h ( 类似于填字游戏) 。如 重庆邮电大学硕+ 论文 第二章l d p c 码概述 图2 4 ，该图就是按照每列3 个l 、尽量使最小g i r t h 大于4 的两个要求构造出的校 验矩阵，其中的斜线表示填入的为l ，空白表示填入的为0 ，g i r t h 为6 ( 闭环相连 结的边数之和) ，注意此图闭环的中间没有交接点。 陟 - ， ，7 图24 校验矩阵中舀m l 为6 的“闭环”的实例 上述构造的过程中，前提条件之一是最小“闭环”长度g i r t h 最大化，需要这个 限定的理出是因为在译码循环中节点接受的信息并不应该包括自身发出的信息， 但是如果在矩阵中( 或者图中) 存在周期，也就是“闭环”，则经过周期次循环后， 从该节点发出的信息又被作为另一个节点的信息传递回来，从而造成了自身信息 的叠加，影响译码的准确性，所以，我们在构造矩阵时要尽量避免短圈的存在， 通过增大最小圈的长度，也就是g i r t h 的长度，就可以提高码字的性能，当g i r t h 达 到一定值时就可以接近无圈时的性能。关于矩阵中周期( 闭环长度) 的问题详细 请见参考文献【2 】。 上述的填充构造校验矩阵的方法只是一种基本的构造思想，考虑到要求构造的 l d p c 码长很长时，该填充方式复杂度会很大，下恧给出两种l d p c 规则码的构造 方法。 2 3 1 l d p c 码的g a l l a g e r 构造方法 采用后文介绍的和积算法( s p a ：s u n - p r o d u c ta l g o r i t h m ) 进行译码取得最大后验 概率的译码性能的条件是双向图中没有小的循环，称之为四线循环( 4 - - c y c l e s ) ， 没有四线循环的条件反映到双向图中就是任意两行中l 的交迭数目不超过2 个。无 四线循环的二元高比特率l d p c 码可以通过随机生成行构成，般来说，这种方法 不能生成固定行重量的矩阵。对于这种方法，g a l l a g e r 提出了一种替代的方法：设 m 行列的矩阵日可以通j 丑y 个大小为( m d ) x n 的子矩阵构成，子矩阵本身也 是l d p c 矩阵，列重量为1 ，行重量为k ，m 必须是，的整数倍p j ，后卜1 个子矩是 第一个子矩阵的独立列置换的结果。图2 5 是由g a i l a g e r 构造的一个( 2 0 ，3 ，4 ) 的 9 重庆邮电大学硕士论文 第二章l d p c 码概述 校验矩阵。 图2 5 ( 2 0 ，3 ，4 ) 的l d p c 码的校验矩阵 虽然l d p c 码的校验矩阵是稀疏的，但相应的生成矩阵不一定是稀疏的，因此 编码器有可能比较复杂。文献 2 5 】中提出了一种类似于上述结构的并行级联的校验 矩阵的编码结构。这种码的一个最大的优点是生成矩阵和校验矩阵都是稀疏的， 这有利于用有效的v l s i 结构实现编、译码结构。 图2 ，6 显示了这种码的系统校验矩阵日的结构和相应的生成矩阵g ，码率是8 9 ， 信息比特长k = 5 1 2 ，, = 5 7 6 ，1 6 x 5 1 2 的子矩阵e 是矩阵g 和好的基矩阵，e 的每 一行包括3 2 个连续的1 ，剩下的是0 。如图2 6 所示，每一列连续的1 对下一列连续的 1 的偏移量是3 2 。 。产：i f 1 舢1 。卜 g= p 1 i 蜀( p i ) 1 6 4 c 6 4 _ ；, 1 - 一2 两j ：乃( p 1 ) p l 石l ( p 1 ) 万2 ( p 1 ) 疗3 ( p 1 ) i ，1 2x ，1 2 ( b ) 生成矩眸 图2 6g a l l a g e r 构造法中系统校验矩阵h 的结构 6 4 x 5 7 6 的矩阵日是有6 4 x 6 4 的单位矩阵和6 4 x 5 1 2 的置换矩阵级联而成，如图 2 6 ( a ) 部分所示，它由置换矩阵e 和e 的三个随机置换矩阵p 2 = 巧( p 1 ) ，巴= # d e 0 ， 只= 以( e ) 构成，这里的蜀函数是独立的列置换。因为h 是系统形式，所以5 7 6 x 5 1 2 的生成矩阵g 可以通过只，p ，p 1 ，e 和5 1 2 x 5 1 2 的单位矩阵很容易地的获得。这 个结构关键的地方在于g 和h 都是稀疏的，这种码的v l s i 结果设计可获得高的吞 吐量和可以接受的译码复杂度【2 5 】。 1 0 重庆邮电大学硕+ 论文第二章l d p c 码概述 2 3 2l d p c 码的确定性结构构造方法 相对于随机结构的矩阵，确定性结构的矩阵是很容易获得的，这种矩阵可以通 过更少的参数来定义l d p c 码。确定性结构的l d p c 码的构造方法基于“阵列码” ( a r r a yc o d e ) 。阵列码是用来检测和纠正突发差错的二维码。阵列码的几何结构 和r s 码类似，是通过环而不是有限域来定义的。当阵列码被看作二元码时。可以 利用它的校验矩阵的