（信号与信息处理专业论文）ldpc码理论分析和译码仿真平台的实现.pdf

北京交通大学硕士学位论文 中文摘要 摘要：l d p c 码的优异性能及其在信息可靠传输中的良好应用前景( 例如光通、 卫星通信、深空通信、第4 代移动通信系统等) ，已引起世界各国学术界和i t 业界 的高度重视，成为当今信道编码领域最瞩目的研究热点。近几年国际上对l d p c 码 的理论研究己取得重要进展，在应用基础乃至工程应用和v l s i ( 超大规模集成电 路) 实现方面的研究亦在全方位开展。 本文的研究重点是l d p c 环数的检验，好码的搜索和l d p c 仿真平台的实现， 主要是环数校验算法和b p 算法的理论研究和编码实现，为以后d s p 的实现打下 良好的基础。主要包括以下几方面的工作： 一、对影响l d p c 码的重要因素之一的环进行了相关介绍。在环分布的基础 上，提出了基于图论的环数校验算法，并在对l d p c 码校验矩阵中的短环( 四环， 六环) 的形状分析的基础上，提出了种基于图论的环数校验算法巧妙的实现方 法，并用c 语言实现。环数检验算法除了可以对已知校验矩阵中的环数进行检验 外，还可以用于设计性能优异的大酮数准循环( q u a s i c y c l i c ，q c ) 码。 二、主要介绍了基于b p 译码算法的l d p c 码仿真平台的设计，给出了仿真 平台下校验矩阵的输入格式和配置文件的格式及意义，对其中的各个模块有详细 的设计实现过程，并用c 语言进行仿真实现。 关键词：低密度奇偶校验码；校验矩阵； 环；环数检验算法；b p 算法；l d p c 仿真平台；编解码：准循环码 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t ：t h e o u t s t a n d i n gp e d o r m a n o f l d p c c o d e sa n d g o o dp m s p e c t so f r e l i a b l et r a n s m i s s i o no fi n f o r m a t i o ni nt h ea p p l i c a t i o n ( f o re x a m p l e ，o p t i c a l c o m m u n i c a t i o n , s a t e l l i t ec o m m u n i c a t i o n , d e e ps p a c ec o m m u n i c a t i o n s ，f o u r t h - g e n e r a t i o n m o b i l ec o m m u n i c a t i o ns y s t e m s ，e t c ) ，h a sa t t r a c t e dt h ew o r l da c a d e m i aa n dt h ei t i n d u s t r ya t t e n t i o n sa n db 踟n e st h em o s tn o t a b l ea “瑚o fr e s e a r c hh o ts p o t si nt o d a y s c h a n n e lc o d i n 吕i nr e c e n ty e a r st h ei n t e r n a t i o n a lc o m m u n i t yo nt h et h r e t i c a ls t u d y l d p cc o d e sh a v em a d ei m p o r t a n tp r o g r e s si nt h ea p p l i c a t i o no f b a s i ca n de n g i n e e r i n g a p p l i c a t i o n sa n dv l s i ( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t s ) i m p l e m e n t a t i o no fr e s e a r c h c a r r i e do u ti na l ld i r e c t i o n s t h i ss t u d yf o c u s e so nt h el d p cg i 础c a l i b r a t i o n , g o o dl d p cc o d es e a r c h i n ga n dt h e a c h i e v a m e n to fl d p cb pa l g o r i t h ms i m u l a t i o np l a t f o r m , w em a i n l yd o 画m 1c a l i b r a t i o n a l g o r i t h ma n db pa l g o r i t h mo ft h e o r e t i c a ls t u d ya n dc o d i n g , l a yag o o df o u n d a t i o nf o r f o rt h ef u t u r eo f t h ed s pr e a l i z a t i o n i n c l u d i n gw o r ki nt h ef o l l o w i n ga r e a s ： f i r s t ，i n t r o d u c et h em o s ti m p o r t a n tf a c t o ro fl d p cp e r f e r m a n c e o nt h eb a s i so ft h e g i r t hd i s t r i b u t i o n , t h i sp a p e rp r e s e n taw a yo fa l g o r i t h mb a s e do ng r a p ht h e o r yf o r c o u n t i n gt h en u m b e ro f 鲫l ，a n da n a l y z et h es h a l 把o fs h o r tg i r 也i nt h el d p cc h e c k m a t r i x ( 4 - g i r t h , 6 - g i a h ) ，t h e ni n e s e n t sai l c wi m p l e m e n t a t i o nw a yo ft h eg i n h c a l i b r a t i o nb a s e do ng r a p ht h o o r y , a n di m p l e m e n t e db yc u s i n gt h i sa l g o r i t h m w ec a n c a l c u l a t et h en m n b e ro fs h o r tc y c l e si nt h ec h e c km a t r i x w ec a na l s ou s et h ea l g o r i t h m f o rf i n d i n gt h eg o o dq u a s i - c y c l i c ( q c ) c o d ew i t hl a r g e 垂n h 。 s e c o n d , d e s i g nb pa l g o r i t h ms i m u l a t i o np l a t f o r mo fl d p cc o d e i n t r o d u c et h ei n p u t m a t r i xf o r m a ti ns i m u l a t i o np l a t f o r ma n dt h ec o n f i g u r a t i o nf i l ef o r m a t d e s i g nt h e v a r i o u sm o d u l e si nd e t a i l sa n di m p l e m e n tt h es i m u l a t i o np l a t f o r mb ycl a n g u a g e , t h e n g i v et h es i m u l a t i o n r e s u l t 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 ；c h e c km a t r i x ；g i r t h ；b pa l g o r i t h m ； l d p cs i m u l a t i o np l a t f o r m ；c o d e c ；q u a s i - c y c l i cc o d e 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名巾叶 签字日期：岬年l 月1 日 导师签名育7 务 导师签名：削7 签字日期：7 刀年f 枷2f 北京交通大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：年月日 致谢 首先要感谢我的导师肖扬教授在我攻读硕士研究生期间给予我的悉心指导 肖老师严谨的治学态度，渊博的学识以及谦逊的为人都深深地影响着我。从研一 阶段的基础知识学习到研二阶段的科研能力培养，从硕士论文的选题、撰写到最 终的定稿都凝聚着肖老师的心血。特别是在进行课题研究中，肖老师给予我的谆 谆教导才使得我的论文得以顺利地完成。 这里，我还要感谢信息科学研究所的其他各位老师给予我的帮助，特别是在 研一阶段的基础知识学习中得到的帮助。同时，我还要感谢我的父母和所有帮助 过我的同学、好友，大家在平时的学习中积极讨论，增长了我的理论深度和广度 最后向所有关心支持和帮助过我的人们表示衷心的感谢。 北京交通大学硕士学位论文 序 本论文的研究工作是在国家自然科学基金项目( 6 0 5 7 2 0 9 3 ) 的资助下完成， 在肖扬老师的大力帮助下，本文作者对l d p c 码编译原理进行了深入研究。l d p c 码以其优异的性能在今后新一代移动通信系统中具有潜在的应用前景，因此本论 文研究内容具有理论和实用意义。 本文在分析影响l d p c 码因素的基础上，用c 实现了快速环数检验算法，最 后还实现了l d p c 码b p 算法的仿真平台。本文设计的b p 算法仿真平台可以对不 同配置参数下的译码性能进行研究( 如不同信噪比) ，为以后d s p 的实现打下了很 好的基础。 北京交通大学硕士学位论文 1 引言 本章简要介绍了l d p c 码的应用背景及意义；接着阐述了纠错码的一些基本原 理；最后总结了作者在攻读硕士期间所做的主要工作并给出了本文内容安排。 1 。1课题应用背景及意义 当今世界已进入了飞速发展的信息时代，信息产业已成为国民经济的主导产 业，通信则成为信息产业中发展最为迅速，进步最快的行业。随着科学的进步和 生活水平的提高，人们对于通信的需求量以及通信质量也r 益增长。出于对于通 信质量的高要求，人们希望找到些提高通信质量的方法，而纠错码作为信道编 码是提高通信质量特别是无线通信质量的好方法之一。 伴随着信息时代的到来以及微电子技术的飞速发展，今天纠错码已不再单纯 是理论上探讨的话题了，它已经成为一门标准技术而被广泛采用。在通信领域中， c r c 校验己成为c c t 对各类线路传输建议中不可缺少的一部分；在移动通信中， 纠错码被广泛用于模拟体制的信令传输及数字体制的整个传输，以提高传输的可 靠性和节省珍贵的频谱资源：在卫星通信中，纠错码技术己成为用来降低对高功 放的要求和减少地球站天线孔径的尺寸的经济可靠的方法，v s a t 和u s a t 的兴 起，都是和纠错码技术的应用有关的；在电话网上的数据传输中，纠错码，差错 控制技术已是使高速数据传输( 9 6 k b i t s 以上的数据率) 成为现实的关键技术。纠 错码技术还广泛应用于计算机存储和运算系统中，此外，纠锚码技术还应用于超 大规模集成电路( v l s i ，u l s i ) 设计中，以提高集成电路芯片的成品率，降低芯 片的成本。 随着移动通信的发展，对纠错码不断地提m 新的要求。t u r b o 码虽己成为3 g 的信道编码标准，但其译码复杂度高，时延长，难以适应最高数据速率远比3 g 要 高的后3 g ( 即b 3 g 或4 g ) 未来移动通信系统的需求。l d p c 码是一类可以用非 常稀疏的校验矩阵( p a r i t y - c 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 发现，故亦称o a l l a g e r 码一1 。经过数十年的沉寂，随着计 算机能力的增强和相关理论的发展，l d p c 码重新被重视，并证明它在采用基于霓 信传播( b e l i e f - p r o p a g a t i o n ，b p ) 的迭代译码算法的条件下具有逼近s h a n n o n 限的 良好性能，叮以这么说，l d p c 码的重新发现是继t u r b o 码后在纠错编码领域的又 一重大进展”“。 l d p c 码在新一代移动通信超3 g 中有着很大的用武之地，因为l d p c 码本身 北京交通大学硕士学位论文 即有抗突发差错的特性；不需要引入交织器，避免了可能带来的时延；可以实行 完全并行的操作，便于硬件实现；吞吐量大，极具高速译码的潜力：它不仅具有 接近s h a n n o n 限的优异性能，同时由于在码的构造、译码方法上的相关成果的获 得使得l d p c 码在信道条件较差的无线通信中展现出了巨大的应用前景，非常适 合于在未来的移动通信系统中的实现。 1 2 理论背景 首先浏览一下纠错码的基础知识”1 ，作为研究l d p c 码的开始。首先，我们 回顾一下s h a n n o n 的信道编码定理。 定理1 1 每个信道具有确定的信道容量c ，对于任何小于c 的码率胄，存在 有速率为r 码长为以的分组码及”o ，k o ，胁j 卷积码，若用最大似然译码，则随着码 长的增加其译码错误率p 可任意小，即 p s 4 p “似 ( 1 - 1 ) 和 p c 2 。由信息论的基础知识可知，在高斯白噪声信道时，信道容量 c = w l 0 9 2 【1 + w n o 】j ) 一( 1 3 ) 式( 1 3 ) 中，矿是信道所能提供的带宽，只2 e r 是信号功率，巨是信号 能量，r 是分组码信号的持续时问即信号宽度，c 矽是单位频带的信号功率，0 是单位频带的噪声功率，只( 删o ) 是信噪比。 2 引言 图1 1e ( 固与r 的关系 由式( 1 - 2 ) 和图1 1 可看出。信道容量c 、码长拧和错误概率p 之问的转换 关系。为了满足一定误码率，的要求，可以用以下两类方法实现。 一是增加信道容量c 。从而使e ( r ) 增加。由c 的表示式式( 1 3 ) 可知，增加c 的方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、 调相等宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低 噪声器件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的 方法，是通信设计工作者经常采用的传统方法。 另一种方法是在r 一定下，增加分组码长n ( 也就是增加分组信号持续时间 r ) ，可使p 随n 的增加而呈指数下降。但由于码长n 的增加，当r 保持一定时， 可能发送的码字数2 i 指数增加，从而增加了译码设备的复杂性。这种方法就是信 道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的 途径。 纠错编码的意义就在于：保持一定的信息传输效率条件下，通过编译码来降 低误码率以实现可靠通信，并且要求译码器尽可能简单。 利用纠错码进行差错控制的数字通信系统如图1 - 2 所示，由此可如下定义分组 码。 定义1 1 分组码是对每段，位长的信息组，以一定规则增加r = n k 个校验元， 组成长为开的序列：c _ 一，c _ 一。一，c 0 j ，称这个序列为码字。在二进制情况下，信 息组总共有2 个，因此通过编码器后，相应的码字也有2 个，称这2 个码字集合 为l ”，r j 分组码。 北京交通大学硕士学位论文 图l - 2 分组码的数字通信模型 线性分组码是分组码中最重要的一类码，它是讨论各类码的基础。虽然这类 码的概念比较简单，但却非常重要，特别是有关码的生成矩阵g 和校验矩阵日的 表示法，以及它们之间的关系，而日与纠错能力之问的关系则更为重要。 一个【”，纠线性分组码，是把信息划成女个码元为一段( 称为信息组) ，通过编 码器变成长为，j 个码元的一组，作为t 牟，线性分组码的一个码字。在二迸制情况 下，有2 “个数组，2 个码亨集合构成了一个j | 维线性予空问，则称它是。个【”， 线性分组码。 定义1 2i n ，七】线性分组码是g f ( g ) ( 在二元域情况下为g f ( 2 ) ) 上的以维线 性空间圪中的一个史维子空问。 定义1 3 两个二元向量气和q ( 其中埘，玎 l ，材) ) 的距离定义为它们之 白j 对应位取值不同的个数，称为它们之白j 的汉明距离，记为d ( c _ ，巳) 。 定义1 4 在个，| ) 线性分组码中，任两个码字之间距离的最小值，称为 该分组码的最小汉明距离，记为d 面。 4 定义1 5 二元向量q 中1 的个数，称为它的汉明重量，简称重量，记为以c 一。 定理1 , 2 任一( 矗，七) 线性分组码，若要在码字内： 检测p 个随机错误，则要求码的最小距离d 2 p + l ； 纠正1 个随机错误，则要求d 2 + l ； 纠正f 个随机错误，同时检测g 仨f ) 个错误，则要求d f + p + l 。 纠正f 个错误和p 个删除，则要求d 2 f + ，+ 1 引言 该定理确定了码的纠错能力与它的距离之问的关系，是纠错码理论中最基本 的定理之一。 定理1 3 若巧是维空间矿的子空阃，则和巧中每一个h 维矢量均正交的所 有矢量，构成矿的另一个子空间，称为k 的零空州或解空问。 定理l 一4 若维空间矿的子空问k 的维数为七，则k 的零空间的维数为 n - - 七。 仇t d ) 线性分组码的编码问题就是在n 维线性空间圪中，如何找到满足一定 要求的，有2 个矢量组成的t 维线性子空间圪。或者说，在满足给定条件( 码的 最小距离d 和码率月) 下，如何从已知的七个信息元求得，= h 一七个校验元。这相 当于建立一组线性方程组，己知七个系数，要求以一t 个未知数，使得到的码恰好 有所要求的最小距离d 。 一般情况下，任何一个伽，i ，d ) 码的日矩阵可以表示为 - 4 ) 5 ) 6 ) 5 北京交通大学硕士学位论文 简写为 或 日c 7 ：0 7 ( 1 7 ) c 日。= ( 1 - 8 ) 由于【疗，膏，d j 码的每一码字必须满足式( 1 - 7 ) 或式( 1 8 ) ，即它的每一个码字 必然在由h 矩p c 的行所张成的一一空间中的零空间中。由定理1 4 可知，7 一一一的 零空日j 必然是一个七维子空日jv j ，而这正是( n ，| i ，d ) 码的码字集合全体。所以， 一一t 与( ”，七，d ) 码的每一个码字均正交，也就是日矩阵的每一行与它的码的每一码 字的内积均为0 。 ”，席，鲫分组码的2 个码字组成了一个j 维子空间，因此这2 个码字完全可由 k 个独立矢量所组成的基底而张成。设基底为 6 ( 1 9 ) 若把这组基底写成矩阵形式，则有 9 1 j - jg i , e - 2 g i 0 g2 - 1 9 1 i - 2 g2 , 0 9 1 - jg i - 2 g t o ( n ，| ，d ) 码中的任何码字，都可由这组基底的线性组合生成，即 c = m g ；【所m 1 2 m 。j 譬2 7 1 轧：一：。8 7 。 lg r - - ig - - - 2 g - o l g 一i g j 一2 g i o ( 1 - 1 0 ) j 砷 枷 鼠般 培 五 之 扩 跏 自居 培 ” 一 0 和 月 一 溉：慨 = i i = q g q 引言 式中，m = ( ，一：。) 是k 个信息元组成的信息组。因此，若已知 信息组r z ，通过式( 1 - 1 1 ) 可求得相应的码字，称式( i - 1 0 ) 的g 为( 以，k ，d ) 码的 生成矩阵。 l d p c 码是一种线性分组码，它的校验矩阵h = ) 沪蛔是稀疏矩阵，即非零 元素( 在g f ( 2 ) 域上即为1 ) 的个数占总元素个数的比例非常小。前面介绍了线性 分组码可以由它的生成矩阵g = ( 。决定，l d p c 码同样可以由其生成矩阵来决 定，给定生成矩阵g ，l d p c 码的码字集合可以表示为 c = 伽f 了i x = n j g j ，t ) ( 1 - 1 2 ) 其中为生成矩阵g 的第i 行。等价地，l d p c 码也可以由校验矩阵日来决定。 给定校验矩阵，码字集合可以表示为 c = 工g k 工，啊) = o ，f = 1 ，2 ，行一t ) 其中，h ，为校验矩阵日的第i 行。因此选定了校验矩阵，那么这个l d p c 码也 就确定了。 1 3本文的研究重点和所做的工作 本文基于l d p c 码的实际编码应用，首先对影响l d p c 码性能的环进行了研 究，在定义了环分布的基础上，提出了一种好的图论启发式方法，并用c 语言进 行了实现；接着对l d p c 码的b p 译码算法进行了重点研究，并用c 语言实现了 b p 算法：接着在前者的基础上我们在v c 下搭建了l d p c 码的仿真品台，对影响 b p 算法性能的参数进行了研究，最后对l d p c 码的硬件实现中的关键问题进行了 考虑。特别是对信息节点和校验节点的实现给出了较详细的说明。并针对目前已 有的方案提出了改进和修j 下。 第一章是引言，概述了本论文内容的理论背景知识与现实意义，并简述了本 文的主要工作。 第二章对当前l d p c 码的校验矩阵的主要的几种构造方法进行了介绍，接着 对l d p c 码的编译码方法进行了总结性的阐述。 第三章对影响l d p c 码的重要因素之一的环进行了相关介绍。在定义了环分 布的基础上，提出了基于图论的环数校验算法，对l d p c 码校验矩阵中的短环( 四 环，六环) 的形状分析的基础上，提出了一种基于图论的环数校验算法巧妙的实 现方法，并用c 语言实现。 第四章主要介绍了l d p c 码仿真平台的设计，对其中的各个模块有详细的设 7 北京交通大学硕士学位论文 计实现过程。 第五章对本文的工作进行总结和展望。 北京交通大学硕士学位论文 2l d p c 码的编译码原理 本章首先介绍了l d p c 码的定义及t a n n e r 图表示，在此基础上，介绍了l d p c 码的编译码原理，主要介绍了b p 算法和l o g 域b p 算法。 2 1l d p c 码的提出及t a n n e r 图表示 一个码长为、信息位个数为k 的线性分组码可以由一个生成矩阵g 来定义， 信息序列s 通过g 编码映射成发送序列，也就是码字c = s g 。线性分组码也可以 由一卜一致校验矩阵日来等效描述，所有码字均满足c h 7 = 0 。校验矩阵的每一 行表示一个校验约束，其中所有非零元素对应的码元变量构成一个校验集，用一 个校验方程表示；校验矩阵的每一列表示一个码元变量参与的校验约束，当列元 素不为零时，表示该码元变量参与了该行的校验约束。在下文中具体阐述。 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性【4 0 】，即校 验矩阵中只有数量很少的1 ，大部分都是o ”。g a l l a g e r 最早给出了正则( ，五，力 u ) p c 码的定义，正i o l d p c 码的校验矩阵日满足下面三个条件： ( 1 ) 日的每行有p 个“1 ”。 ( 2 ) 的每列有2 个“】”，五3 。 ( 3 ) 与码长和日矩阵的行数相比，p 和a 都很小。 其设计码率为r = l 一五p 。，由于满足这个结构条件的校验矩阵不唯一，所以 具有参数( ，五，p ) 的l d p c 码构成了一个码集合。 例如对于规则( ，w ，) l d p c 码，这种表示表明奇偶校验矩阵日的每一列含 有心个1 ，每行含有个“l ”。若每一行和每一列的“1 ”的个数不为一恒定的常数， 那么我们称这类码为非规则奇偶校验码。 设一个( 五，纠码c 具有校验矩阵h 。= ( 。，其因子图模型可以表示为 一个二分图( b i p a r t i t e ) i 1 2 0 3 码字向量，= ( 而，x 2 ，工) 表示为一组变量结点 k ，j = 1 , 2 ，n ，对应于校验矩阵的各列，而校验约束则表示为组校验结点 z 。i = 1 , 2 ，肼 ，对应于校验矩阵的各行。当且仅当h 。= l 时，变量结点茸，与校 验结点z 之间有一条边相连，结点x ，与z ，之间互称相邻结点，其问的连接边称为 两个结点的相邻边。对规则l d p c 码，校验矩阵各行中“l ”的数目均为妒，各列中 “l ”的数目均为a ，因此，因子图上每个变量结点具有五条入射边，即度数为a ； 每个校验结点具有p 条入射边，即度数为p 。总计，因子图上共有e = n g = m p 条 边。令集合m ( j ) = p ：h 口= l 表示变量z f 的受约束范围：令t ，：h f = 1 | ( i ) = 表示约 束关系z ，的约束范围如图2 1 所示，一个简单的校验矩阵的t a n n e r 图表示。 北京交通大学硕士学位论文 f i = 10o o 0o o ol 01o o o 0 o 0 o 图2 1 校验矩阵的t a n n e r 图表示 2 2l d p c 码的编码原理 l d p c 码是线性分组码，它是由校验矩阵定义的。由于校验矩阵h 对应唯一 的生成矩阵g ，所以校验矩阵的构造是编码的关键之所在。由于校验矩阵是非系 统形式，所以l d p c 码是非系统的。 2 2 1规则( 准规则) l d p c 码的构造 1 g a l l a g e r 结构的l d p c 码 g a l l a g c r 码是线形分组码，它是由校验矩阵定义的。由于校验矩阵式非系统码 形式，所以g a l l a g e r 码是非系统码。最初的l d p c 码的编码方法是g a l l a g e r 在其 论文中提到( n ，j ， ) 规则l d p c 码设计方法，其中h 表示码长，表示校验矩阵 中每列所含1 的个数，而k 则表示校验矩阵中每行所含1 的个数。它的校验矩阵日 构造方法如下。 ( 1 ) 将校验矩阵日分成，个子矩阵且，吼，日，每个子矩阵的每列有且只有一 个1 ； ( 2 ) 子矩阵q 中的1 呈下降的阶梯状排列，即第f 行的七个1 从第( f 1 ) k + 1 位 1 0 j - l l) 一 l d p c 码的编译码原理 排到第砖位； ( 3 ) 其余的子矩阵通过对凰进行随机列置换得到，所有置换是等概率出现的。 冒= 日 日2 ( 2 1 ) 上述设计方法设计的校验矩阵日是规则的，行重为k ，列重为，。按上述方法 很容易构造一个稀疏矩阵，矩阵中包含大量的0 。且每行每列含有固定数量的l 。 这样，一旦确定了g a l l a g e r 码的k 、，则相应的也确定了g a l l a g e r 码的码率，。 r = ( 一m ) n = 竺二尝竺坐= t j k 。此外，在构造其余j l 部分时，为编码 川 引入了一定的随机性，符合s h a n n o n 证明信道编码定理引用的三大必要条件之一： 采用随机编码。( 其余的两个条件是编码长度上寸0 0 和译码采用最佳的最大似然译 码方法) 。 该校验矩阵虽然不能保证一定没有四环，但是可以通过计算机设计来避免出现 四环。g a l l a g e r 的这种设计方法在，3 ，k 的时候有很好的距离特性。 g a l l a g e r 的编码方法于1 9 8 1 年被t a n n e r 推广，并且被应用于c d m a 通信。 g a l l a g e r 码的设计方法随后被m a c k a y 等人进一步推广 2 m a c k a y 构造方法 m a c k a y 发现了通过稀疏矩阵日编码的优势，并且首先显示了这类码的优异 性能。为了不在图中出现长度为四的环，m a c k a y 采取的办法就是构造时要保证任 意列间的重叠不大于1 。m a c k a y 在其网站”6 1 上公布了大量他设计的l d p c 码，这 些码大部分是规则的，可以应用于数据通信与储存。m a c k a y 提出了4 种l d p c 码 的构造方法可以避免所构造的校验矩阵中存在四环l t l 。他提出的有指导性的构造 校验矩阵方案如下【1 】： 构造方法c 1 a ：这是基本的方法。该方法固定每一列的列重为五( 例如五为 3 ) ，随机构造矩阵使每一行的重量尽可能地相等，并且每两列之间重叠“1 ”的个数不 大于l 。这样构造的矩阵由于每两列之问重叠“1 ”的个数不大于1 ，所以因子图上不 存在4 环。如图2 - 2 所示。表示了按照此方法构造的一个u ) p c 码( 3 ，6 ) 码。 北京交通大学硕士学位论文 ：o 5 时， 判定f 比特= 0 0 ) ，得到当前译码。在所有比特被译出之后，得到译码矢量工= ( 而， 而，) 。 ( 3 ) 尝试判决算法 i f h x 卸，t h e n 停止译码，输出工= ( 玉，毛，) 作为有效的输出值； e l s ei f 达到预定的迭代次数，t h e n 停止迭代，计错误帧数； e l s e 开始下一轮迭代； e n d ； e n d 2 3 4对数域上的b p 译码算法 一个二进制随机变量c 0 ，1 ) 的统计特性可以由一个参数p - - - p r c = 来指定， 这是因为p r c - - 0 l = l - p ：事实上，它的概率分布可以由对数似然比唯一确定： 1 8 u ) p c 码的编译码原理 l ：虹旦山 。p ，【c = q 根据 的符号可以确定c 的最有可能取值当1 比0 更有可能的时候_ 是正 的：当0 比l 更有可能的时候， 是负的此外，4 绝对值的大小反应了这种判断的 可靠程度。对于一个给定的随机比特c 0 ，1 ) ，f 是指一个概率密度依赖于c 的观 察值，而概率密度函数为f 【r l c ) 。当c 固定，酬c ) 可以看成r 的函数，它被称为条 件概率密度函数，另一方面，当r 固定，划c ) 是c 的函数，被称为似然函数。 在进行观察前，c 的先验概率是州萨1 】和州网】。经过一次观察以后，这些 概率变成后验概率p f 【c = l 时和研酬阳。根据概率论中的贝叶斯公式( b a y e s r u l e s ) ， 后验概率和似然函数是成正比的， 即 p r 【c = l i r = f ( r t o = 1 ) p r c = 1 f ( r ) ( 2 - 9 ) 所以，后验概率的对数似然比可以表达为： 川。s 嬲礼s 揣+ l o g 蒜嚣 f 2 - l o ) 右边的第一项被称为对数似然比( 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 = l q r 矗j 与发送的码字具有以下的关系： r = 2 c - l + n ( 2 11 ) 这里噪声向量n 是方差为a 2 独立的零均的高斯随机变量( 这个式子意味着存在 一个双极性的比特到符号的映射，0 到1 和l 到+ l ，也就是b p s k 调制) 。 对于这n 个比特，具有最小差错率的检测器将计算后验的对数似然比： = 崦揣刮。g 岽渊 ( 2 - 1 2 ) 此时，若2 - 0 ，则可以判定；= 1 ，否则；。= 0 。 具体算法如下： 初始化：对于所有的m e ，肼 和一e m ) ，令2 1 0 ；对于所有的一e ，椰， 杏掣2 寺 1 9 北京交通大学硕士学位论文 迭代：f o r 迭代次数i = 1 ，2 ，, i m a x 校验节点升级 f o r 研，加并且疗( 神 础= 之t 鼬。c 见。劬弹 ) 变量节点升级 f o r h l ， ( 2 1 3 ) 掣k 手+ 。丢缪 ( 2 - 1 4 ) 这个算法可以迸一步为二分图中信息传递过程来解释。在第0 次迭代的时候， 三， 从每个变量节点到它所涉及到的校验节点的信息是一2 “；第m 个校验节点收集它的 输入信息，产生反映它奇偶校验结果的奇偶校验对数似然比，并把这个对数似然 比作为输出信息进行传递。上述过程中要捧除某个变量节点传递信息到某个校验 接点，而该校验节点将信息又传递回来的情况。每个变量节点接收j0 由该变量节 生， 点的度决定) 个信息。并且第n 个变量节点通过将a 2 。和所有的输入信息相加产生 一个新的预测值，如( 2 - 1 4 ) 式所指示的。这个过程可以重复，即变量节点传递它们 新的预测值给校验节点，而校验节点再将信息传递给变量节点，同样要排除信息 正反馈给自身的情况。 根据算法的特点，我们很容易意识到该算法基于二分图的并行实现是可行的， m 个校验节点可以是m 个独立的处理机，对于n 个变量节点，每个节点是一个求 和节点。并行实现使得在极高速率的条件下使用l d p c 码和迭代解码成为可能。 当然，对于该算法软件实现一般来说都是串行的。b p 算法在对数域上进行，和概 率域上进行相比可减少乘法运算次数。 b p 算法每次迭代大约需要m ( d r + t ) 次浮点乘运算，每译出l b i t 大约需 峨( 以+ t ) r ( t 为平均迭代次数) 次浮点乘运算，与码长无关，总的乘法次数约为 t n d r