（信号与信息处理专业论文）低密度奇偶校验码及其在正交频分复用系统中的性能研究.pdf

赢客邮电大学硕 ? 研究生学位论文 摘要 摘要 低密度奇偶校验( l d p c ) 码是用非常稀疏的校验矩阵来表示的线性分组码，其性能 在一定条件下比t u r b o 码优越，现已得到广泛的应用。为了充分利用l d p c 码良好性能， 其译码算法的研究具有重要的意义。通过对l d p c 码译码影响因素进行的分析，可很好地 利用译码算法在复杂度和性能之间折衷，达到实际通信系统的要求。正交频分复用( o f d m ) 是一种离效并行传输技术，其频谱利用率高、成本低，能够有效地对抗i s i 。将l d p c 编 码技术应用到o f d m 系统中将构成ll d p c c o f d m 系统结构，具有好的抗多径衰落性 能。 本论文在l d p c 两种基本译码算法位翻转( b f ) 和相位翻转( b p ) 算法基础上，给 出了一种改进的算法，即混合译码算法，它是两种基本译码算法在复杂性和性能间折衷。 数值计算结果表锈，混合译码算法得到复杂发比b p 算法低，译码性能要比b f 算法高。同 时以b p 算法为基础，对影响译码性能因素进行分析，主要包括码长、码率、列重、短环、 噪声失配等，与同等条件下的t u r b o 码性能做了比较。最后，对l d p c c o f d m 系统在交 织器、扩频、码长、外交织等方面进行抗衰落特性研究，仿真结果表明该系统具有比 t u r b o c o f d m 更好的性能，较好的抗衰落性。 关键字：l d p c 码，b f 算法，b p 算法，正交频分复翔，多径衰落信道 南京邮电大学硕上研究生论文 a b s t r a c t a bs t r a c t l o w - d e n s i t yp a r i t y c h e c kc o d e si sac l a s so fl i n e a rb l o c ke r r o r - c o r r e c t i n gc o d e st h a tc a nb e d e f i n e db yv e r ys p a r s ep a r i t y c h e c km a t r i x 。s i n c ei t sp e r f o r m a n c ei sm o r es u p e r i o rt ot u r b o s u n d e rc e r t a i nc o n d i t i o n ，l d p ch a se x t e n s i v ea p p l i c a t i o n si nm a n yf i e l d 。i no r d e rt oa b u n d a n t l y u t i l i z ei t sg o o dp e r f o r m a n c e ，i ti si m p o r t a n tt os t u d yi t sd e c o d i n ga l g o r i t h m s i na d d i t i o n ，b y a n a l y z i n gt h o s ed e c o d i n gf a c t o r sw h i c ha f f e c tt h ep e r f o r m a n c e ，i ti sp o s s i b l et of i n dt h es u i t a b l e d e c o d i n ga l g o r i t h mi np r a c t i c a lc o m m u n i c a t i o n ss y s t e mb yt r a d i n go f fb e t w e e nc o m p l e x i t ya n d p e r f o r m a n c e o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ( o f d m ) i sav e r ya t t r a c t i v e t e c h n i q u ef 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 ge n v i r o n m e n tt h a tc a u s e s i n t e r - s y m b o li n t e r f e r e n c e ( i s i ) 。l d p cc o d e do f d ms y s t e mw h i c hi sc o m p o s i 捃db yl d p c c o d e da n do f d m t e c h n i q u e s ，h a sg o o dp e r f o r m a n c ei nt h em u l t i p a t hf a d i n ge n v i r o n m e n t i nt h i st h e s i s ，w ef i r s ti n t r o d u c e dt h eb a s i cc o n c e p t i o no fl d p ca n do f d m t e c h n i q u e s b a s e do nt h ec o n v e n t i o n a l d e c o d i n ga l g o r i t h m ，b fa n db pm e t h o d s ，w ep r o p o s e d a n i m p r o v e m e n td e c o d i n ga l g o r i t h m ，n a m e dh y b r i dd e c o d i n ga l g o r i t h m ，a n dd i s c u s s e di t s p e r f o r m a n c eb yn u m e r i c a le x p e r i m e n t s i ti ss h o w nt h a tt h ei m p r o v e m e n ta l g o r i t h mh a sb e r e r p e r f o r m a n c et h a nt h a to fb f , a n dh a sl o w e rc o m p u t a t i o nc o m p l e x i t yt h a nt h a to fb pa l g o r i t h m ， t h e n ，w ea n a l y z e dt h o s ed e c o d i n gf a c t o r sw h i c he f f e c t e dt h es y s t e m sp e r f o r m a n c e ，s u c ha sc o d e l e n g t h s ，c o d er a t e s ，c o l u m nw e i g h t ，s h o r tc y c l e ，a n dn o i s em i s m a t c h a n dc o m p a r e dt h e mw i t h t u r b oc o d e s p e r f o r m a n c e l a s t ，w ec o m b i n e dl d p ct e c h n i q u ew i t ho f d mt e c h n i q u et h a t c o n s t r u c t e d 】l d p c c o f d m s y s t e m w ef i n dt h a tt h ep e r f o r m a n c eo ft h el d p c c o f d m s y s t e mi sb e t t e rt h a nt h a to ft h et u r b o c o f d m i nt h es o m ec o n d i t i o n s k e y w o r d 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 ，b i tf l i t t i n ga l g o r i t h m ，b e l i e fp r o p a g a t i o n a l g o r i t h m ，o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ，m u l t i p a t hf a d i n gc h a n n e l l l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：童避因期：掣 南京邮电大学学位论文使用授权声踢 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理o 签名啤名：避魄幽舌 南京邮电大学硕士研究生论文第一章绪论 第一章绪论 l 。l 本文背景 在现代通信系统中，为了抵消信道中各种噪声的干扰，以保证数据信息能够得到可靠、 有效的传输，往往需要采用纠错编码技术。丽随着无线数字通信的发展及各种高速率、突 发性强的业务的出现，研究并利用好纠错编码技术就显得越来越重要。 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文通信的数学理论中提出了著名的有扰 信道编码定理【m 1 11 ： 每个信道具有确定的信道容量g 对于任何r 码是一种具有稀疏校验矩阵的线 性分组码；其性畿优予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 码性能的优越性通常要在码长较 长时才能够体现出来，当码长为巾短长度时，由于编码中短长度环的存在，编码的性能会 有所损失。 l d p c 码的研究与进展大体包括以下几个方面： ( 1 ) 因为l d p c 码是一种线性分组码，它的编码实现主要是校验矩阵的确定过程， 所以所谓码结构设计也就是校验矩阵的构造。l d p c 鹳的校验矩阵构造方法露前主要有几 何方法、图论方法、实验设计方法、置换方法等。l d p c 码可以分为：正则码和非正则码， 即校验矩阵每行或这列非零元素个数是固定对应的码就是正则码否则就是非正则码。般 的在相同情况下，m g l u b y 等【6 】指出，非正则l d p c 码的性能优于相应的正则l d p c 码。 另一种分类方法是将它分为二元域和多元域上的l d p c 码。而m c d a v e y1 7 等的研究表明 多元域上的l d p c 码的性能较二元域上g a l l a g e r 码的性能有较大提高，且域的阶数越高， 编码的性能越好，但是复杂度增加。在寻找好的码结构( 所谓好的码结构就是既有好的牲 2 南京邮电大学硕- 上研究生论文 第一章绪论 能又有较低的编码复杂度的码结构) 方面，l u b y 等【9 】采用基于线性规划的方法来设计线性 时间可编码的非正则码。d j c m a c k a y 等f 8 】提出对非正则码采用先选择轮廓再选择结构的 两步选择方法，并指出能快速编码的l d p c 矩阵通常具有下三角形结构。j c a m p e l l o 等【1 0 】 提出采用扩展的比特填充算法来设计具有高码率、高g i r t h 和b e r 性能的良好的l d p c 码。 s j j o h n s o n 和s r w e l l e r 1 1 1 提出一种基于k i r k m a nt r i p l e 系统的组合设计方法，适合于构建 短码长、高码率和在其二分图中不出现长度为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 l l 2 】【1 3 】探讨了基于有限几何学的l d p c 码结构，基于欧氏几何和投影几何 中的线和点，构造出了4 类l d p c 码。总之，好码结构不断出现，编码的性能在不断提高。 ( 2 ) l d p c 码的译码和性能分析 在译码算法的研究方面，硬判算法和软判算法。硬判算法简单易行，但是性能较差： 后者虽有好的性能，但实现复杂度太高。于是作为二者的折衷，文献 1 4 中提出了消息传 递算法( m e s s a g ep a s s i n ga l g o r i t h m ) 。e r k s c h i s c h a n g 等1 1 5 】对消息传递算法作了推广，将它 扩展为一种更加通用的算法：和积算法( s u m - p r o d u c ta l g o r i t h m ) ，并指出和积算法实际上包 含了大量的实际译码算法( 如前向后向算法、b p 算法、维特比算法等) ，它可应用于任何 f a c t o r 图，众多的实际译码算法均可有和积算法框架导出。m p c f o s s o r i e r 1 6 】【1 7 1 研究了降低 复杂度的l d p c 码的迭代译码，提出了a p p b a s e d 和b p b a s e d 算法。在此基础上，j i n g h u c h e n 和m p c f o s s o r i e r i l 8 儿1 9 1 提出了两种改进的b p b a s e d 算法的密度演进算法及其离散形 式。 在性能分析及译码相关的一些方面，d j c m a c k a y 和c e h e s k e t h 2 0 1 研究了l d p c 码 采用b p 算法译码时译码性能随实际噪声变化的敏感程度，得出了噪声估计失配与译码性 能的函数关系。m g l u b y 等在中给出了一种新的基于m a r t i n g a l e s 的c o n c e n t r a t i o nb o u n d s 方法来分析l d p c 码。t j r i c h a r d s o n 和r l u r b a n k e 将中的方法从b s c 和二元 m a s s a g e p a s s i n g 译码算法的约束条件推广到各类信道模型，提出了一种通用的方法来确定 具有离散或连续输出字符集的任何- 5 ；输入无记忆信道中采用m a s s a g e p a s s i n g 译码的 l d p c 码的性能。s y c h u n ge ta l ( 2j i 利用消息分布的高斯近似对密度寻优算法进行简化，证 明采用高斯近似可在不降低精度前提下快速找到门限和快速、容易地优化次数分布。y o n g y i m a o 和a h b a n s h e m i 2 2 】【2 3 1 从迭代策略角度对译码算法进行了研究，提出了一种基于t a n n a r 图的g i r t h 分布的概率方案译码方法。在不增加复杂度的情况下，概率方案的性能较传统的 瀑布方案有明显改善。 ( 3 ) l d p c 码与o f d m 技术结合的研究 移动通信是现代通信系统中不可缺少的组成部分。移动通信不但集中了无线通信和有 3 南京邮l 乜大学硕：l 二研究生论文 第章绪论 线通信的最新技术成就。为了适应新的市场需求，人们正在发展第三代( 3 g ) 移动通信系统。 但是由于3 g 系统的核心网还没有完全脱离第二代移动通信系统的核心网结构，所以普遍 认为3 g 系统仅仅是一个放窄带向未来移动透信系统过度的阶段。目前，入们已经把露光 越来越多地投向蜃3 g ( b e y o n d3 g ) 的移动通信系统，该系统可以容纳庞大的用户数、改善 现有通信质量，达到高速数据传输的要求。从技术层面来看，3 g 主要是以c d m a 为核心 技术，而在3 g 以后的移动通信系统中正交频分复用( o f d m ) 最受瞩圈，o f d m 技术在无 线通信领域的应用成为目前研究的热点。l d p c 码也是4 g 移动通信首选编码方式。对于 高速数据业务来说，单载波时分多址( t d m a ) 系统和窄带c d m a 系统都存在很大的缺陷。 由于无线信道存在时延扩展，高速数据流的符号宽度又相对较窄，所以符号之间会存在较 严重的符号闻干扰( i s i ) ，这对单载波t d m a 系统中使用的均衡器提如了非常高的要求， 即抽头数量要足够大，训练符号要足够多，训练时问要足够长，从而均衡算法的复杂性也 会大大增加。此外，c d m a 系统一个非常重要的特点是采用闭环的功率控制，这在电路交 换系统中比较容易实现，但对于分组业务来说，对信道进行预测，然后再返回功率控制命 令会导致较大的时延，因此对于高速的无线分组业务来说，这种闭环的功率控制问题也存 在缺陷。因此，人们开始关注o f d m 系统，希望通过这种方法来解决高速数据流在无线信 道中的传输阏题，从_ 悉可以满足带宽要求更高的多种多媒体业务。 2 0 世纪6 0 年代o f d m 技术已经被提出，使子载波信道频谱相互覆盖的并行传输和 o f d m ，其中每个子信道承载的信号传输速率和要求各个子信道在频域距离在上相等，从 而避免使用高速均衡，并且可以对抗窄带脉冲噪声和多径衰落以及充分利用频谱资源。但 这种多载波传输技术在双向无线数据方面的应用却是近十年来的新趋势。近年来，o f d m 由于其频谱利用率高、成本低、具有较强的抗多径衰落能力等原因越来越受到入 f 糟毫关注。 随着人们对通信数据化、宽带化、个人化和移动化的需求，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 技术 在移动通信领域的应用，预计3 g 以后移动通信的主流技术将是o f d m 技术。 在0 f d m 系统中，纠错编码是必不可少的，包括卷积码、r s 码、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 子载波之 闽实现联合编码，可以有效对抗多径移动信道中深度衰落对载波信道某些特定频率的影 响，极大地提高系统性能。 4 南京邮电大学硕上研究生论文第一章绪论 1 3 本文的内容和框架 ， 本文重点研究了l d p c 码的译码算法影响因素进行数值仿真及：l d p c c o f d m 系 统结构模型的抗衰落性研究。本文从第二章起的内容和框架如下： 第二章介绍l d p c 码及正交频分调制( o f d m ) 原理的研究。 第三章分析短圈对译码性能的影响，给出维长( g i r t h ) 的概念，分析维长( g i r t h ) 对译码性能和迭代次数的影响。 第四章l d p c 码的译码理论的研究，重点对b f 、b p 译码算法进行分析，给出了混合 译码算法。仿真和分析影响译码性能的因素。 第五章l d p c 码和0 f d m 系统结合，给出。l d p c - c o f d m ，系统结构模型；在衰落信 道下性能仿真，得到该系统具有较强的抗衰落特性。 第六章全文总结和展望。 南京邮电犬学硕一? 研究生论文 第二奄l d p c 码及o f d m 韧f 究 第二章l d p c 码及o f d m 研究 2 1l d p c 码原理与介绍 2 。1 。1l d p c 码介绍 l d p c 码是一种线性分组码。由线性分组码的性质，域( 本章讨论的是二元域) 上长 嚣，k 维的编码c 可用( 群妨x 彰维的校验矩阵露描述： c ( n ) x 毯f ”：h x t = 0 ( 2 。l 。1 ) l d p c 码也可以用校验矩阵描述。只要校验矩阵定了，就可以很容易确定编码器，相 应地确定l d p c 码。这个矩阵与其它分组码的校验矩阵的区别在于：它的矩阵中含有大量 的o ，仅含有少量的l ，是一个稀疏矩阵，这是l d p c 码性能优越的原因所在。一个二进制 向量x = ( x ，x 2 ，x 。) r ，当且仅当墩= 0 时，才是个码字。一个用矩阵表示的l d p c 码， 这个矩阵的每一列都含有，个l ，被定义位列重，每一行都含有k 个1 ，k 被定义为行重， 且稀疏矩阵行数m 和列数满足k = n j i m ，这就是g a l l a g a r 提出的( 3 ，4 ) 正则码。记煳= m 一曲为的行数，n = h j f 】，芦l ，n ，产l ，m 。t 的行对应二分图中的校验节点，抒的列对 应二分图中的变量节点，如果h f i = l ，则表示变量节点和校验节点c j 之闻有边褶连，反 之则表示两节点之闻没有边蛊接相连。根据节点之闻相连表示存在一条边，我们可以根据 劈构造如对应的二分图。之所以称构造出的图为二分图是因为图中的节点分为两类，一类 是变量节点，一类是校验节点，且变量节点之间和校验节点之间均没有边直接相连。二分 图也可称为两种颜色可着色的图，所谓两种颜色可着色的图指的是可用两种颜色对图中所 有的边着色，使得图中任何一个环( 即闭回路，且回路所包含的任何两条边均不同) 上的 相邻边的颜色相异。由着色( d y ec o l o u r ) 定理碡渊可知该图中只包含偶数长度的环。 对本文中用到的符号说明如下： 矗，以。：分别表示变量节点辑和c j 的次数( 即某节点伸出的边的个数) ；对于正则码 来凝，各变量节点和各校验节点的次数分别是同一个僮，记为磊和磊； 斌砖) ：表示与变量节点致有边相连的校验节点的下标； ( o ) ：表示与校验节点白有边相连的变量节点的下标： ( 1 ，) 仃：表示( 曲与的差集； 式 南京邮电大学硕士研究生论文 第二章l d p c 码及o f d m 研究 ( 叻f ：表示( o 与i 的差集。其中f 表示第f 个信息节点，j 表示，个校验节点。 因为校验矩阵的图结构对码的最小距离和译码性能有直接的重要影响，所以问题的关 键在于如何构造没有短长度环或环的平均长度尽可能大的校验矩阵。 2 1 2l d p c 码的图结构 在l d p c 码的研究过程中，t a n n e r 提出“二分图( b i p a r t i t eg r a p h ) 模型对l d p c 码 进行分析。用二分图表示l d p c 码的优点是便于译码和进行性能分析。二分图由比特节点 ( b i tn o d e s ) 、校验节点( c h e c kn o d e s ) 以及连接它们的边( e d g e ) 组成，图2 1 是二分 图结构图。环数的定义为从任意一个变量节点经过校验节点最终又回到陔变量节点围成图 形经过的路径的边数，其中校验节点和变量节点之间不能相连接。 信息 比特 校验 约束 五而恐 图2 1 具有长为4 的短长度环的二分图片断 在定义二分图中引入了节点度的概念，即节点伸出去的边为：矾和以。上述例子图2 1 是一个二元域上的l d p c 码，其编码的校验矩阵中，每- - y d 有d ，( 一3 ) 个非零元，每一行有 d c ( - - 4 ) 个非零元。即编码码字x 中的每个比特参加d ，个校验约束，两每个校验约束包括d 。 个比特。在二分图中，d ，、吐分别表示与比特节点和校验节点相连的边数，称为浚节点的 次数( d e g r e e ) 。当为常数时( 如上面的例子) ，即辱蓐有比特节点的次数都样、所有校验节 点的次数也都样，这样的l d p c 码称为正贝l j ( r e g u l a r ) l d p c 码，简称正则码。 如果构造校验矩阵时使得任两列之间重叠的l 最多只有一个，那么就可以消除长度为 4 的环。但是在二分图2 2 中环的最小长度为6 时，编码的最小距离有可能为4 。如图2 2 所示的编码的二分图片断，如果在某个码字中这4 个变量节点的取值为b , b , b k b ，那么在其 它变量节点保持不变的情况下，这4 个变量节点全部取反变为b ，b , b k b l ，所有的校验约束仍 然得到满足，因此也是一个码字，这两个码字的距离为4 。较小的最小码距将会使编码的 7 南京邮电大学硕士礤究爱沦文第二二牵l d p c 鹞及o f d m 研究 性能恶化。因为最小码距不大于4 的码的纠错能力小于2 ，即该码无法纠正所有差错个数 大于等于2 的差错事件。这是非常坏的情况，应当尽量避免。 鼍裼鼍故 髅患 比特 校验 约康 心。2。3 咚氏 图2 。2 厂二小重量码字麴环长为6 的二分图片断 从对上面两种简革躅结构麴分柝可以看到，编码图结构中的环，特剃是短长度的环对 编码有重要的影晌，二分图中出现长度大于2 的环时会辱l 起译码算法性熊的下降，特别是 环长为4 时会导致译码失败。因此在构造编褥时，如衡消除短长度环，提高环的平均长度 是需要着重考虑的闯题。 如何增n - - 分图中酌g i r t h ( 即圈中的最小环长) ，如 碍构造恰当的校验矩阵使得幽校 验矩薄得到编码生成矩阵的计算篱单，如何提离校验矩阵的秩，如何减小矩阵的相关性， 都是l d p c 码的编码研究领域的重点。 2 1 3 g a l l a g e r 的构造方法 g a l l a g e r 给出了慨，勘正则码的构造方法：对于码长炎嚣的( 蕊，国硪则码，纯将校验矩 阵按行水平的分割为蔫个相同大小的子矩阵，每个予矩阵麴任捌都只包含个l 。第一 个子矩阵以预定的方式构造，如可以用递减的形式包含所有的l ，矩阵的第i 行掰有的l 都分布在第( i - 1 ) d c + 1 到越列。其它下面的如1 个子矩阵都是第一个予矩阵的隧橇排列。 这种构造方法哥如下表示： h o 黑 l l l l 、， 呔 lll l 、v “ lil l - - - v - - - 其中，编为第一个子矩阵，校验矩阵辩如下构造： 3 ( 2 ，l 。2 ) 南京邴电大学硕士研究篷论文 第二誊l d p c 褐及o f d m 研究 h = 日。 窍2 ( 耧8 ) ( 厝o ) ( 2 1 。3 ) 这里硇矩阵h o 的列置换。上面夥矩阵的第一个子矩阵为h o ，也可以阁凰的任置换代 替，得到如下更加对称靛构造方法： 2 i 4 非正别码的构造 h = 确( 辩o ) 霈2 ( 尉o ) 甄 也是无法区分的， 所以短圈存在降低了校验约束正常的检错和纠错能力。圈2 1 说明了五、x ：通过长度为4 的圈相互联系，图2 2 说明了硝、x 2 、x ，通过长度为6 的圈相互联系，而l d p c 码的信息 传递( m e s s a g ep a s s i n g ) 译码算法是假定变量节点是相互独立，短圈的存在必然破坏了独 立性的假设，使得译码性能明显下降，事实上最短圈长度越长，信息传递算法越接近最 优纂法。 1 6 南京邮电大学硕士研究生论文第三章赢维长l d p c 码的校验矩阵构造算法 一 j h 燃 x f l l x 1 1 图3 1 含有四环的矩阵胃 x i x j x k l至 ll l羔 c p c 叮 c p q c r 图3 2 含有6 环的矩阵h 下面通过校验矩阵来分孝厅短圈：图3 。l 给出了圈长为4 的短圈在l d p c 码校验矩阵中 出现的一般形式，由带箭头的实线清楚可以看到变量节点t 、x j 和校验节点c p 、c 。构成了 长度为4 的短圈。蚕3 2 给出了圈长为6 的短圈在l d p c 码校验矩阵中嬲现的一般形式， 由“1 ”的位置清楚可以看到变量节点麓、x 、 c 6 的短圈，对于第二章的图2 1 和图3 1 而言，如果x ，= 硝，x = x 2 ， = ， p 嚣q ，c g = 龟和，= 秽4 ，二分图与蜜2 。l 中的短圈就可以和校验矩阵i 孛的短圈x k 一一x 对3 应c 起来。圈样 的方法我们可以得n - - 分图2 2 和图3 2 矩阵对应。 下面将对校验矩阵中的短圈傲进一步的解释：在校验矩阵中，菲零元素代表了行号对 应的校验节点和列号对应变量节点的相连接的一条边。而在校验矩阵图中连接两个非零元 素的边只代表了一种连接，并且这种连接只熊水平方向的和或者垂直方向，其中水平方向 的边表示两个变量节点通过一个校验节点连接起来，如图3 2 ，变量节点x ，和x ，通过校验 节点c 。连接起来。分析可知，如果存在两个变量节点之间的距离为2 ，这两个变量节点在 校验矩阵图中就会形成一条水平方向的边。同理，垂直方向的边表示两个校验节点通过一 个变量节点连接起来，可知如果存在两个校验节点的距离为2 ，那么在校验矩阵图中相应 位鼍就存在一条垂壹方向的边。校验矩阵图中巢些边按照一条水平边连一条垂直边，再连 1 7 南京邮电大学硕士研究生论文第三章商维长l d p c 码的校验矩阵构造算法 一条水平边，再连一条垂直边，如此下去若能够构成一个闭合路径，并且所有的水平边不 同行，所有垂直边不同列，则在校验矩阵中就可形成一个短圈，并且所构成的短圈的长度 则由该圈包含的非零元素个数确定，因为我们知道非零元素对应二分图中真实的边，根据 校验矩阵图的特点发现，非零元素的个数正好又与短圈中边的个数相等，所以短圈长度恰 好又等于矩阵图种短圈包含的边的总数。图3 1 中圈有四个菲零元素，所以该圈的长度为 4 ，并有4 条边；图3 2 中圈有六个非零元素，该圈的长度为6 ，并包含6 条边。根据以上 描述，我们就可完全将二分图中的圈和校验矩阵的圈一对应起来了，这样就可通过判断 校验矩阵中出现圈情况来确定二分图中出现圈情况。 对于图3 1 ，由于变量节点麓，x ，对应校验矩阵中的的两列之间重叠的l ( o v e r l a p ) 至 少为2 。校验矩阵中两歹l 的o v e r l a p 为0 意味着，那么这两列是相互正交的，相关性最小。 如果o v e r l a p 越大，则两列的相关性就越大。所以，如果校验矩阵两列之间o v e r l a p 为2 的 情况出现比较频繁，必然增强了校验矩阵的列的楣关性，这样会减少校验矩阵的秩，从丽 使得该校验矩阵确定的分组码的自由距离减少。对于图3 2 ，长度为6 的短图增强了三列 之闻的相关性，综上所述，校验矩阵中的短罂的存在，与无短圈情况比较，会导致校验矩 阵的列的相关性增强，从而减小校验矩阵的秩，减小码的自由距离，降低码性能。事实上 高g i r t h 码的校验矩阵更可能是满秩的，其中高g i r t h 码是指对应二分图最短圈圈长比较大 的l d p c 码。 通过从二分图、译码算法和校验矩阵三个焦度的分析，我们论证了l d p c 码二分圈中 的短圈存在将恶化l d p c 码的码性能，所以无论对于正则码，还是对于非正则码，找到消 除短匿的算法变的非常重要。 3 。l 。2 码参数选择与二分图中短圈的关系 码长( c o d el e n 西h ) 比较短的时候，校验矩阵中“l 出现频率比较大，更加容易构成 短圈；而码长较长，非常稀疏，消除短圈比较容易，可以提高性能，所以从消除短圈的角 度，码长越长越好；但是码长越长，译码延时越大，因为l d p c 是分组码，所以要折衷考 虑。l d p c 奇偶校验矩阵的列权重( c o l u m nw e i g h t ，某列中l 的个数) 是另一个很重要的 参数，某列权值越大，该列对应的码字比特经过少量的迭代就可以获得很多的信息，所以 这个比特的对数似然比可以很快的收敛；但是，列权值越大，校验矩阵就越不稀疏，短圈 更容易出现，会导致性能下降，所以列重量的选取也需要折衷考虑。码率( c o d er a t e ) 反映 了信息比特在码字中占的比例，码率越低则越容易构造高g i r t h 的码，越离则越难构造l l 弼， 1 8 南京郎电人学硕l ：硬究生论文第三章赢维长l d p c 妈的校验戋臣阵构造算法 其巾高g i r t h 意味着对应二分图最短圈圈长比较大。所以，码率越高越容易消除短圈的影响， 可以提高性能，但传输效率下降，故也要折衷考虑。 3 2g i r t h 相关的概念及其应用于好码的选择 3 2 1 二分图的g i r t h 、节点的g i r t h 和边的g i r t h 的定义 为了定量研究二分图中的短圈，在图论中，三分图的g i r t h 是指一个图中最短圈的圈长， 例如：某个二分图有长度为6 、8 、1 0 、1 2 和长度更长的圈，则该二分圈的g i r t h 先6 。二 分图中，某个节点“的g i r t h ( t h eg i r t ha tn o d eu ) 是指经过节点材的最短圈的圈长，例如：经 过节点u 有长度为8 、l o 、1 2 和长度更长的圈，则该节点u 的g i r t h 为8 。定义二分图中变 量节点的最短圈圈长分布( g i r t hd i s t r i b u t i o n ) g ( t ) ，= 4 , 6 ，删为具有g i r t h 为，的变量节 点占整个变量节点的比例，丽这罩z 一是这个二分图中所有变量节点的g i r t h 中最大的那个。 ，m x 1 2 二分图的g i r t h 的平均值( g i r t h a v e r a g e ) 定义为g ( 2 k ) 2 k 。同理，在二分图中，包含某 七尊2 条边e 的圈有许多，边e 的g i r t h 是指包含边e 的最短圈的圈长，例如：包含边e 有长度为 l o 、1 2 和长度更长的圈，则该边e 的g i r t h 为l o 。如果不做特别说明，论文后面所指的g i r t h 分椎就是指二分图中变量节点的g i r t h 公布。事实上，我们还可以确定二分图中每条边的 g i r t h ，即包含该边的最短圈的圈长，边的g i r t h 可以比变量节点的g i r t t h 更加详细= 分图中 的短圈情况。需要指出的是，这里二分图的短圈变量节点的g i r t h 定义，边的g i r t h 定义只 是为本文分析问题方便而提出的，不能作为正式的术语。 3 2 2g i r t h 好码的选择 耄上面我们g i r t h 对译码性能是有影响的。一个变量节点的g i r t h 是指最短路径的长度， 它等同于从这个节点出来的信息传递回该节点本身的最小迭代次数。在实际迭代次数达到 这个最小迭代次数之前，与这个节点联系的信息可以最优地传递给二分图的剩余部分。如 果某个变量节点的g i r t h 越大，那么该变量节点发出的信息被传递给自身的f 反馈信息将越 小，则译码性能也越好。所以，使变量蒂点的g i r t h 尽量大对码性笼的提离是有利的，换句 话说，二分图具有更多大g i r t h 的变量节点是有益的。所以，我们可以把一个l d p c 码二分 图的g i r t h 作为磐码判断依据，或者可以把变量节点的g i r t h 平均值作为判断的依据。 1 9 南京邮电大学硕一二研究生论文 第三章离维长l d p c 码的校验趟阵构造算浚 对于随机构造的二分图，由于随机数产生的差异，同一条件码集将包括大量的码，丽 它们的性能也不是完全一样，从g i r t h 的角度，圈长分布的好坏可以作为一个选择依据。步 骤如下：首先，被选择的码崧须最短圈的长度( g i r t h ) 是尽量大；其次，对于具有同样大 小g i r t h 的码，选择g i r t h 平均值( g i r t ha v e r a g e ) 最大的码。而这样做的依据就来自于上面 的理论分析。 3 3g i r t h 对l d p c 码性能的影响性能仿真 图3 3 不同维长g i r t h 码性能曲线 取一个舻8 1 6 ，m = 4 0 8 ，产3 ，k = 6 的规则码，对上述结论进行了m a t l a b 仿真论证，首 先在高斯信道下仿真不同g i r t h 码的误比特性能，其中译码算法采用信息b p 算法，目的是 验 正一下g i r t h 大的码是不是具有更好的性能。图3 3 给出了高簸信道下仿真的结果，可以 看到：在比特能量信噪比e b n 。比较低的情况下，g i r t h 对误比特的性能影响不是很明显： 但是当e b n 。比较的大时候，g i r t h 的影响就比较明显了。分析原因，不难发现，在信嗓眈 较离的情况下，假设迭代次数不变( 事实上变化不是很大，一般雀某个平均值附近变化) ， 那么对于g i r t h 大的码，它们的变量节点将自身信息传递回自己的次数就比较少，于是它们 性能上更接近最优解码，性能必然要好。 2 0 j翻融hu1一，；一 - | 8 6 4一： 高!l懈f一 p n n一 一 _ g g g 南京邮电大学硕士研究生论文第四紫l d p c 码的译码算法殿性能仿真 第四章l d p c 码的译码算法及性能仿真 好的信道编码使得编码后的码字序列具有较强的纠错能力，为有效地抗信道噪声提供 可能。译码则是将这种可能转化为现实的过程，译码算法的优劣决定了能否最大程度的发 挥码本身具备的这种纠错潜力。好的译码算法可以减少算法复杂度，尤其是在长码的条件 下，译码算法的复杂度决定了工程实现的可行性。l d p c 码得以迅速发展的原因不仅在于 其优异的性能，还在于其译码复杂度低( 因为其校验矩阵是稀疏的) ，且可实现完全的并 行操作，适合硬件实现，具有高速译码的潜力。校验矩阵的稀疏特性的另一个好处是，在 码长较长时，相距很远的信息比特可能参与同一校验，使得连续的突发差错对译码的影响 不大，因此码本身就具有抗突发差错的特性，从而无需在编码端引入交织器，没有因交织 器的存在而带来的编码时延。本章介绍了l d p c 码各种译码算法的原理与实现步骤及其数 值仿真。 4 1m e s s a g ep a s s i n g 算法 m e s s a g ep a s s i n g 算法是一种工作在图论基础上的译码算法，由于在算法的运行过程中， 可靠性信息在二分图的变量节点和校验节点之间来回的传送，因此称为m e s s a g ep a s s i n g 算 法。该算法的前提假设是码对应的二分图中没有环，如果图中有环的存在，算法的性能会 有一定程度的损失。 不失一般性，假设信道的输出符号集即译码器的输入符号集为0 ，译码过程中发送消息 的符号集为m ，通常有o c m 。m e s s a g ep a s s i n g 算法的操作过程如下：在零时亥l ，所有的信 息节点v m 门 ，以为码长) 都接收到一个相关的信道输出消息n ，即一取值范围在o 内的 随机变量。在译码过程中，可靠度消息沿着图中豹边在节点之间相互传递。首先，每个变 量节点都给所有与之相邻的校验节点发送一个取值范围在符号集m 内的消息。典型的情形 是零时刻，变量节点将悲作为它的第一个消息发送( 这要求o c m ) 。每一个校验节点c j 处理它接收到的消息，并回送取值范围在m 内的相关消息给所有与之相邻的变量节点协。 然薏每一个变量节点毪对刚接收到来的消患和信道输出消息珞进行处理，计算出新的可靠 度消息，然后将之发送给相关的校验节点。对算法的每一次迭代过程，( 1 e 肋，都包括一 个消息处理的循环：校验节点处理和发送消息，接着是信患节点处理和发送消息。下面是 m e s s a g ep a s s i n g 算法的详细译码步骤： 第一步：每个变量节点琢都向所有与之楣邻熬校验节点c j 发送一取值范匿在符号集m 2 l 南京邮电大学硕上研究生论文第四章j l d p c 码的译码算法殿性能仿真 内的可靠度消息，消息由映射甲z ：ox m 略一_ mp o ) 确定。该映射不以来自节点g 的 消患为变量。 第二步：每一个校验节点白处理它接收到的消息，并回送取值范围在m 内的相关可靠 度消息给所有与之相邻的变量节点歌。消息由映射￥岔：m 屯一书m ( z 确定。该映射不 以来自节点1 ，。的消息为变量，重复第一步。 算法孛的矗，是指带点x 的次数，z 为迭代次数，在= 0 时，映射￥：8 ：oxm 如哼m 的质d 砖一1 个变量成为哑变量，退化为甲? ：o 专m ，该映射通常采用恒等映射，即 甲? ( ) = 。注意算法中的映射可以依赖于迭代次数，和图中的节点，也就是说同一个节 点对某个发送消息的计算函数可以随迭代次数的变化焉变化，藤同一次迭代中，