（通信与信息系统专业论文）ldpc码编译码技术研究.pdf

摘要 摘要 信道编码是数字通信系统和计算机系统的重要组成部分。l d p c 信道编码技 术是编码界的重要成果之一，1 2 码率的二元l d p c 码在a w g n 信道下的性能距信 息论中的s h a n n o n 限仅差0 0 0 4 5 d b ，它是目前距s h a n n o n 限最近的纠错码。 g m l a g e r 在1 9 6 2 年提出低密度校验码( l d p c 码) ，1 9 9 6 年经过m a c k a y 、s p i e l m a i l 和w i b e 唱等人的再发现后，l d p c 码以其性能优越、全并行迭代译码结构，译码 复杂度线形增长，便于硬件实现等一系列优点，在无线通信、深空通信和存储工 业等诸多领域得到了广泛应用。 本文首先回顾了信道编码技术的发展历史，介绍了l d p c 码的基本概念和原 理。在几个重点的研究方向：校验矩阵的构造、相关编码方式、简化译码算法以 及性能估计分析等方面作了详细的介绍，并提出了自己的创新解决方案。本文的 重点是新型校验矩阵的构造和译码算法的优化。 校验矩阵的构造是编码的前提，好的构造方案可以大大简化复杂度。本文首 先回顾了几种主要的矩阵构造方法：随机化构造、半随机化构造和结构化构造， 并比较了各自的优缺点。在此基础上提出了一种基于码长连续变化的q c l d p c 码的构造方法，设计出的h 矩阵具有较大g i r t h 值，且码率码长可以灵活变化。 此外，对于非规则码我们采用了码率压缩的方法同样实现了高码率并且连续变 化。 译码算法是l d p c 码的关键，译码复杂度的大小直接影响系统的实现。主要 分硬判决译码、软判决和复合译码，经典的译码算法有比特反转( b f ) 译码算法 和置信度传播( b p ) 译算法。对于硬判决的比特反转算法，作者在基于加权错误 校验比特反转算法基础上做了优化，主要是科学合理的引入了判决门限，使得在 保证系统性能的前提下大大简化了译码的复杂度。仿真表明：保证了系统性能， 并且大大减少了译码所需迭代次数。 对l d p c 码的译码性能，本文用经典的密度进化和高斯近似等理论进行了估 计和分析。此举有助于优化校验矩阵行和列的度分布，并能有效预测l d p c 码字 的译码性能，同时还能够确定信道阀值。 关键词：l d p c 码，矩阵构造，码率，码长，加权校验 ab s t r a c t f,l! 曼m j 穹= 暑曼暑皇暑暑皇昌葛 a b s t r a c t c h a n n e lc o d i n gi sa l li m p o r t a n tc o m p o n e n tf o rd i g i t a lc o m m u n i c a t i o r l ss y s t e m s a n dc o m p u t e rs y s t e m s ，a n dl d p cc h a n n e lc o d i n gt e c h n o l o g yi so n e o ft h ee n c o d i n g r e s u l t s h a l fo ft h eb i n a r yb i t - r a t el d p cc o d e si na w g n c h 锄e lp e r f i o 加1 a n c eo n l y w i t ha t a po f0 0 0 4 5 d bt ot h es h a n n o ni n f o r m a t i o nt h e o r yl i m i t i ti st h el a t e s t e r r o r - c o r r e c t i n gc o d e sf r o mt h es h a n n o nl i m i t g a l l a g e rp r o p o s e dl d p cc o d e si n19 6 2 ， a f t e rm a c k a ya n do t h e r sr e d i s c o v e r e di ti n 19 9 6 ，w i t hb e s tp e r f o r m a n c e ，c o m p l e t e l v d e c o d 啦a l g o r i t h mi np a r a l l e ls c h e m e ，d e c o d i n gc o m p l e x i t yo fl i n e a rg r o w t ha n d e a s i l yr e a l i z e df o rh a r d w a r ed e s i g n ，l d p cc o d e sh a sa l r e a d yb e e nw i d e l vu s e di n m a n yp r a c t i c a l s y s t e m s ，s u c h a sw i r e l e s sc o m m u n i c a t i o n s y s t e m ，d e e p - s p a c e c o m m u n i c a t i o ns y s t e m ，a n ds t o r a g e s y s t e m t h i st h e s i sr e v i e w st h ec h a n n e l c o d i n gt e c h n o l o g yd e v e l o p m e n ta tf i r s t ，a n d i n t r o d u c e st h eb a s i cc o n c e p to fl d p cc o d e sa n d p r i n c i p l e s f o rt h ef o c u so fr e s e a r c h i ns e v e r a l d i r e c t i o n s ：c h e c km a t r i xo f s t r u c t u r e ，r e l a t e d t o e n c o d i n g a n d d e c o d i n g ，s i m p l i f i e da l g o r i t h m ，a n a l y s i sa n de s t i m a t e do ft h ep e r f o r m a n c e a u t h o rp u t t o r w a r do w ni n n o v a t i v es o l u t i o n s t h ef o c u so ft h i sp a p e ri san e w c a l i b r a t i o nm a 踊x o ft h es t r u c t u r ea n dt h eo p t i m i z a t i o n a l g o r i t h m t h ec o n s t r u c t i o no ft h ec h e c km a t r i xi sa p r e c o n d i t i o nf o rc o d i n g ，ag o o dp r o g r a m c o n s t r u c t i o nc a r l g r e a t l ys i m p l i f yt h ec o m p l e x i t y t h i st h e s i sr e v i e w sm a i n c o n s t r u c t i o nt y p e so fl o w - d e n s i t yp a r i t ym a t r i x ：r a n d o m i z e dm e t h o d ，s e m i “m d o m m e t h o da n ds t r u c t u r e dc o n s t r u c t i o n m e t h o d ，a n dc o m p a r et h e i ra d v a n t a g e sa n d d i s a d v a n t a g e s ，t h e np r o p o s eam e t h o do f c o n s t r u c t i o nb a s e do n c o n t i n u o u s l yv a r i a b l e l e n g t h ，w h o s ep a r i t yc h e c km a t r i xh a sl a r g eg i r t h ，a n dt h eb l o c kl e n g t ha n dc o d er a t e c a nb ei n c r e a s e d f u r t h e r m o r e ，w em a k eu s eo ft h ec o m p r e s s i o n 南rc o d er a t e 幻 a c h i e v eah i g hc o d er a t ea n dc h a n g e a g i l e l y t h ed e c o d i n ga l g o r i t h mi st h ek e y t ol d p cc o d ea n dt h ec o m p l e x i t yo fd e c o d i n g d i r e c ti m p a c tr e a l i z a t i o no ft h es y s t e m i th a st h r e ek i n d so fd e c o d i n ga l g o r i t h m s ： h a r d d e c i s i o nm e t h o d ，s o f t d e c i s i o nm e t h o d sa n d h y b r i dd e c o d i n g ，c l a s s i c a la l g o r i t h m i sb fa n db p t oh a r d - d e c i s i o nm e t h o d s ，a u t h o ro p t i m i z e st h ew v b f ，m a i l l i ys e tt i l e s c i e n t i f i ca n dr a t i o n a ld e c i s i o nt h r e s h o l da n de n s u r e st h es y s t e mp e r f o r m a n c ea tt h e s a m et i m eg r e a t l ys i m p l i f i e dt h e c o m p l e x i t yo ft h ed e c o d i n g b ys i m u l a t i o ni th a sb e s t p e r f o r m a n c ea n ds i g n i f i c a n t l yr e d u c e dt h en u m b e ro fi t e r a t i o n sr e q u i r e df o rd e c o d i n g a b s t r a c t w ea n a l y s e sd e c o d i n gp e r f o r m a n c eo fl d p cc o d e s 、析t hd e n s i t ye v o l u t i o na n d g a u s s i a na p p r o x i m a t i o n i th e l p st oo p t i m i z et h ed e g r e ed i s t r i b u t i o nf o rl o w - d e n s i t y p a r i t y ，a c c u r a t e l ye v a l u a t et h ep e r f o r m a n c em a t r i xw i t h o u ts i m u l a t i o n sa n dd e t e r m i n e t h ec h a n n e lv a l u el i m i t k e y w o r d s ：l d p cc o d e s ，m a t r i xc o n s t r u c t i o n ，c o d el e n g t h ，c o d er a t e ， w e i g h t e dd e c o d i n g 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有 关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名 a 严肿只 限采哆 第1 章绪论 第1 章绪论 1 1 数字通信系统的结构 通信的目的是把对方不知道的消息及时可靠地传给对方。随着对高效、高可 靠性数字通信系统需求的迅猛增长，设计人员最关心的是如何在数据源功率和宽 带有限，系统复杂性和设备造价尽可能小的条件下实现尽可能准确的信息传输， 即使信息传输的误码率最小化。信道编码是消除或降低信息错误概率的有效手段 之一。为更好的理解信道编码在数字通信系统中的地位和作用，下面首先介绍通 用数字通信系统的基本组成结构。 卧信源编码器h 信道编码器h 数洲l j 器卜 i 即 i i i i l i i 刚信源译码器h 信道译码器h 数? 解调器尸调制； 编码信道 图! - i 数字通信系统基本组成结构 图中信源是产生需要传输的信息。信息可以是模拟信号，也可以是数字信号。 如果是模拟信号，则在送入数字系统传输之前需要进行采样和数字化处理；如果 是数字信号则可以是字、码字等符号，一般将这些称为码元。 信源编码器的任务是将信源发出的消息，比如语音、图像或者字符等的原始 数据，转化为有利于较小数据量并且便于在传输媒介中进行传输的形式，信源输 出经过信源编码器编码后得到的数字序列成为信息序列。 信道编码是在发送器和接收器之间实现信号可靠传输的必要手段之一。传输 信道存在一定的噪声和衰落，必然会对其上传输的信息引入失真和信号判决错 误，因此需要采用差错控制码来检测和纠正这些比特错误。信道编码器的作用就 是对信源编码器的输出进行编码，通过加入一定的冗余码元，提高纠错能力，使 之能够抵抗信道的噪声和各种衰落等，提高系统的抗干扰能力。以二元有限域上 的信道编码为例，其基本思想就是将每k 个连续的信息比特认为一组，经过适当 的编码后得到，z 个比特的输出，这甩个比特组成的序列称为一个码字。k 个信息 比特与n 个码字比特的比值成为编码速率，简称码率尺，即： 第1 章 绪论 尺：一k( 1 1 ) 玎 从而经过信道编码后的数据率为： r c = 生= 竿( b i t s ) ( 1 - 2 ) l r lt ，【 为信源编码器输出信号的数据率。 数字调制器的作用是使信息变成能够适应信道传输的信号。假设调制器输出 的每个信号的持续时间为r ，则称r 为信号间隔，而称1 r 为符号速率。 信号经过调制器后送入物理信道进行传输。典型的物理信道包括有线信道、 无线信道、光纤信道、卫星信道、磁记录信道以及水下声音信道等，但又有着各 自的特点。比如，无线信道会受到多径的影响产生衰落，而卫星信道会受到信号 功率衰减的影响等，这些在系统设计过程中都应该考虑。 信号到达接收端，在接收机中，数字解调器的作用是通过对接收到的调制信 号序列或传输码字进行最优估计，然后输出数字编码序列到信道译码器。信道译 码器对传输消息进行估计和判决，估计准则是根据编码准则和信道特性而确定 的，目的是使信道噪声所造成的信号判决错误最小化。最后，信源译码器根据信 源编码准则将得到的信道译码器输出的编码信息序列经过相应的信源译码后，得 到对原始信源序列的估计并传递给用户。 伴随着通信技术的飞速发展以及各种传输方式对可靠性要求的不断提高，差 错控制编码技术作为抗干扰技术的- - ；f d e 重要手段，在数字通信领域和数字传输系 统中显示出越来越重要的作用。 1 2 信道编码技术的发展历史 1 9 4 8 年c e s h a n n o n 发表了著名的通信的数学理论。其中s h a n n o n 第二 定理也称信道编码定理i l 】指出：若有一离散、平稳、无记忆信道，其信道容量为 c ，只要待传送的实际信息率r c ，那么一定不存在这样的方案。s h a n n o n 引用了3 个基本条 件用于证明他的定理： 一、采用随机的编译码方法： 二、构造码长的渐进好码或者s h a n n o n 码； 三、译码采用最佳的最大似然译码方法。 2 第1 章绪论 5 0 多年来构造好码的思想基本上是按照s h a n n o n 弓i 用的后两条基本条件为主 线进行研究的。经过研究者的不懈努力，各种差错控制编码方案不断涌现。 2 0 世纪4 0 年代，r h a m m i n g 提出了第一种实用的信道编码方案一( 7 ，4 ) h a m m i n g 码，它能够纠正7 个比特中所发生的单个比特错误。这个编码方法就 是分组码的基本思想，h a m m i n g 提出的编码方案后来被命名为汉明码。但是 h a m m i n g 码存在许多不足，第一是效率不高，码率只有4 7 ，其次是纠错能力较 低，它只能纠正单一的错误。m g o l a y 针对汉明码的缺点提出了两种以他自己名 字命名的高性能码字格雷码( g o l a y 码) 【3 】：一种是二元o o l a y 码，采用1 2 个数据 比特，11 个校验比特为一组，最多能纠j 下3 个错误。另一种是三元g o l a y 码， 运算域是三进制数，6 个数据符号，一组有5 个校验符号，并能纠正2 个错误。 1 9 5 4 年r e e d 在m u l l e r 提出的分组码的基础上得到了一种新的分组码，称 为r e e d - m u l l e r 码，简称r m 码【4 l 。r m 码比h a m m i n g 码和g o l a y 码前进了一大步， 在码字长度和纠错能力方面有较强的适应性。i i 码是一类参数选择范围很广的 分组码，因此它在2 0 世纪六七十年代的火星探测方面得到了极为广泛的应用。 1 9 5 7 年，p r a n g e 提出了循环码5 6 ，循环码是线性分组码的一个子类，它除 了分组码的特点外，还有循环特性，也就是说任何一个码字，循环移位以后，还 是一个码字，它可以用移位寄存器实现编码和伴随时计算译码。循环冗余校验码 ( c r c ) 就是循环码的一种。c r c 一般都是用于纠正一位错误，主要用于检错， 而不是纠错。 1 9 5 9 年，作为循环码的一个重要子类，b c h 码被提出。其码长玎= q ”一l ，饼 是整数，二元( g = 2 ) b c h 码可以纠错的数目为( 2 ”一1 ) 2 。后来r e e d 和s o l o m a n 把b c h 码推广到非二元( g 2 ) 的情况，就是r s 码( r e e d s o l o m a n 码) ，这种 编码的特点是能够同时纠正突发错误和随机错误。 1 9 6 0 年r e e d 和s o l o m n 将g c h 码扩展到非二元( 矿2 ) 的情况，得到了 r s ( r e e d s o l o m o n ) 码。r s 码的最大优点是其非二元特性可以纠正突发错误并且 它也能纠正随机错误。 上面提到的这些分组码，都是将k 个信息比特( 符号) ，经过m 个校验关 系，产生m 个校验比特( 符号) ，产生了n = m + 七个编码后比特( 符号) 。分 组码的本身有一些不足：一是，按帧传输、按帧解码，因此帧长较长时会带来一 定的时延。二是要求准确的帧同步，这样才能保证准确解码。此外，多数分组码 要求解调器的硬判决输出，这样又会带来一些判决时的误差，影响性能。 在1 9 5 5 年，e l i a s 首先提出了卷积码【6 j 。卷积码与前面提到的码字不同，它 不是将数据分割成不同的分组，而是通过移位寄存器将校验比特加入输入数掘流 中。卷积码的编码实现简单，用移位寄存器可以实现，并且可以连续译码，无须 第1 章绪论 准确的帧同步。由于卷积码在编码过程中引入了寄存器，增加了码元之间的相关 性，因此，在相同复杂度的条件下可以获得比分组码更高的编码增益，代价是增 加了分析和设计的复杂性。 随着人们对卷积码研究的深入，在译码算法方面出现了以下几种译码算法： 序列译码算法、门限译码算法和维特比i t e r b i ) 译码算法【7 。其中维特比( v i t e r b i ) 译码算法的出现，使卷积码逐渐成为研究和应用的重点，特别是在通信系统中得 到了极为广泛的应用。约束长度红7 ，码率为1 2 和1 3 的o d e n w a l d e r 卷积码已 经成为商业卫星通信系统中的标准编码方法。在i s 9 5c d m a 系统中，约束长度 k = 9 ，码率为1 2 的卷积码应用于上行链路。在移动通信领域，g s m 采用约束长 度扣5 ，码率为1 2 的卷积码； 卷积码的主要问题是对突发性错误的纠错能力差。用交织和卷积码结合的方 式，可以在码比特送入信道前，先进行分组交织，再进行卷积码编码。对于接收 端，先解交织，再译码。经过这一过程，突发性错误就变成了随机错误，卷积码 性能也因此得到改善。 1 9 6 6 年，f o r n e y 提出将两个短码串联成长码，其基本思想是将编制长码的 过程分级完成，从而通过用短码级联构造长码的方法来提高纠错码的纠错能力。 级联码的目标是构造具有较大等效分组长度的纠错码，并且将最大似然译码分段 进行，其有纠错能力强，并且译码不复杂，展现了构造s h a n n o n 码的美好前景。 1 9 9 3 年，法国的c b e r r o u 等人在卷积码和级联码的基础上提出了t u r b o 码 【8 l ，由于很好的利用了香农定理中的随机性编译码条件，所以在信道编码的理论 和应用中都取得了突破性的进展，是信道编码史上的旱程碑。t u r b o 码的解码原 理是利用软输入软输出的迭代译码算法( 即m a p 算法，s o v a 算法) ，达到了接 近s h a n n o n 极限的优异性能，同时译码复杂度也较低。t u r b o 码采用并行级联递 归的编码器结构，是一种系统形式的卷积码，译码算法主要有m a p 算法、l o g - 一m a p 算法、s o v a 算法等。t u r b o 码凭借其优秀的性能而成为编码界研究的热点，并在 通信中有广阔的应用前景。但是t u r b o 码也有缺点，主要表现是译码复杂度较大 ( 复杂度随码长成指数增长) ，码长较长时，由于交织器具有较大的时延，还表 现出有e r r o r - f l o o r 效应。 1 3l d p c 码的研究现状 在深入研究t u r b o 码原理的过程中，1 9 9 6 年d j m a c k a y 、m n e a l 和 n w i b e r g 几乎同时发现：早在1 9 6 2 年，g a l l a g e r 提出来的信道编码方案 l d p c 码( l o wd e n s i t yf a r i t yc h e c kc o d e s ) 【9 】也是一个好码具有更低的线性译码 4 第1 章绪论 复杂度。g a l l a g e r 提出l d p c 码后一直没有得到编码界的重视，只有1 9 8 1 年 t a n n e r 从图论i lo j 的角度研究过l d p c 码。 自从m a c k a y “再发现”l d p c 码后【l i 】f 1 2 l ，人们的进一步研究表明：给予非 规则双向图的l d p c 长码的性能可以优于t u r b o 码，而且这样的码的性能可以非 常接近s h a n n o n 限。其中一个原因也在于l d p c 码具有良好的距离特性。由于 l d p c 码不仅具有良好的距离特性，小的译码错误概率和较低的译码复杂度，而 且适合码长大于2 0 0 时，不存在错误平台，其码率容易调整。实验结果中几乎均 为可检测错误。所以l d p c 码无论在理论上还是在实际上都具有极其重要的价 值。l d p c 码的重新发现是继t u r b o 码后在纠错码领域又一重大进展。 无论g a l l a g e r 还是m a c k a y 都是用随机的方法构造l d p c 码，用随机法构造 的l d p c 码的码字参数选择灵活，但对于高码率、中短长度的l d p c 码用随机法 进行构造，要避免短循环是困难的，其没有一定的码结构，编码复杂度高。于是 人们考虑用代数法构造l d p c 码。l d p c 码代数构造可采用几何方法、图论方法、 实验设计方法、置换方法来设计。不同的构造方法都是为了实现以下几个目的： 增大图中最小循环长度( g i r t h ) 。优化非规则码的节点分布，减小编码复杂度，构 造的l d p c 码要有好的码性能。 m g l u b y 等指出，非规则h 矩阵构造的码字性能优于相应的规则h 矩阵构 造的码字。在寻找好的码结构方面，m a c k a y 等提出：能快速编码的l d p c 矩阵 通常具有下三角形结构。t j r i c h a r d s o n 探讨了如何构造编码矩阵，使编码时问 与码块长度实际上符合线性关系( 线形时间编码) ，而非通常认为的平方关系。 y k o u 和s l i n 等探讨了基于有限几何学的l d p c 码结构。s l i n 研究团队的 b a m m a r 等提出用均衡不完全区组设计方法( b i b d ) 构造好的l d p c 码。 g a l l a g e r 曾给出两种l d p c 码的迭代译码算法：软判决和硬判决算法，即软 判决概率译码算法和比特反转算法。前则虽有好的性能，但太复杂；消息传递算 法可以认为是二者的折衷。消息传递算法( m p ) 有时也称置信传播( b p ) 算法。 在m p 译码算法中，节点到节点的消息是通过t a n n e r 图传递的。具体的算法我 们将在第二章l d p c 的译码思想中作详细分析。 译码算法的改进和优化离不开译码性能的分析。在译码性能分析的研究方 面，t j r i c h a r d s o n 等开发了一种在码块无限长假设条件下跟踪l d p c 码t a n n e r 图中消息概率的技术，称为“密度进化”算法的数值程序，来近似估计噪声门限 ( 在该门限一下可望成功地采用b p 算法) ，提出了一种通用的方法来确定具有 离散或连续输出字符集的任何二元输入无记忆信道中采用m p 译码的l d p c 码的 性能。特别对于b p 译码算法，该方法可提供任何所需精度的性能估计。 第1 章绪论 s y c h u n g 等将消息离散化，通过计算机迭代搜索寻找最优的节点次数分布， 特别适合于非规则码的分析。在二进制输入a w g n 信道下，设计码率l 2 、码长 1 07 的非规则l d p c 码在错误概率l o 击时，离s h a n n o n 限仅0 0 0 4 5 d b i t 3 】。 近年来，l d p c 码的很多研究成果表明l d p c 码是一种性能优异的好码。 l d p c 码比t u r b o 码在技术上更具有优势，更能适应未来系统高速速率数据传输 和高性能的要求。由于l d p c 码提出较晚，因此与第三代移动通信标准失之交臂， 但基于l d p c 码编码方案极有可能成为第四代移动通信系统的应用方案，目前已 经有很多系统采用l d p c 码。l d p c 码所具有的巨大应用潜力，使其在深空通信、 光纤通信、卫星数字视频和声频广播、磁光全息存储、移动以及固定无线通信 和数字用户线等领域都得到了广泛的应用。目前l d p c 码已经为多个国际标准组 织所重视，欧洲d v b 标准组织制定的最新数字视频卫星广播全球标准d v b s 2 已经使用l d p c 码作为其前向纠错编码方案；美国h u g h e s 公司和一些研究机构 也已经研究出使用l d p c 码的编译码芯片。w i m a x 以及b 3 g 等标准里面也采用 了低密度的编译码方案。相信随着l d p c 码的进一步技术成熟，更多的未来通信 系统会采用这种具有优异性能和应用前景的编码方法。 1 4 本文的结构与重点 第一章介绍了数字通信系统的构成及信道编码技术的发展历史，重点介绍了 l d p c 码的提出与发展现状，分析了每种信道编码的优缺点，并作了简要比较。 第二章主要介绍了l d p c 码的基本概念、原理以及编译码思想。 第三章从编码的角度介绍了l d p c 码目前主要的校验矩阵构造方法，并针 对规则码和非规则码分别提出了校验矩阵的构造方法，使得此类l d p c 码的码率 码长能够灵活变化。 第四章重点介绍了l d p c 码的比特反转类算法，并提出一种基于加权方案的 译码改进算法，达到了相对优异的性能，同时具有较低的复杂度。 第五章用密度进化和高斯近似的方法对l d p c 码的性能进行分析，并就各自 的特点作了比较。 第六章是对本文所讨论内容的总结，并预测t l d p c 码的未来发展趋势。 6 第2 章l d p c 码概述 2 1 信道编码基础 第2 章l d p c 码概述 2 1 1 线性分组码 线性分组码是最基本的信道纠错码，最著名的是h a m m i n g ( 7 ，4 1 码。下面所 介绍的线性分组码均以二进制为例。 线性分组码将待编码的信息序列以k 个为单位划分成组，再由编码器对这七 个信息比特进行线性运算得到m 个校验比特，接着把这k 个信息比特和m 个校验 比特合并，长度为1 = 七+ m 。由于j | 个信息比特总共构成2 个信息序列，因此编 码后的码字也有2 。个，即构成一组线性分组码，用( n ，k ) 表示。门表示码长，| 表 示信息位长度，码率r = k 刀。此外，二元线性分组码必须满足如下两个条件： l 、码字集合中任意两个码字模2 加之后的结果依然是码字集合中的码字。 2 、码字集合中包含有全零码字。 线性分组码的编码可以描述为一个信息矢量x 和一个矩阵g 相乘的过程 u = x g ( 2 一1 ) g 是由霓个力维矢量 g o ，g ”，g k 。) 构成；x 是信息序列分组 ，一，一。 ； 编码得到的u 是门维输出 ，m ，u n 1 ) 。 根据式( 2 1 ) ，码字u 可以表示为 u 2 x o g o + 一g l + + 坼一i g k i 矩阵g 被称为编码生成矩阵，其形式展开为 g = g o g l ： g o ，1 g t i ： ( 2 2 ) ( 2 3 ) 与g 相对应的是校验矩阵h ，线性分组码也可由校验矩阵h 来定义： u h t = 0 ( 2 - 4 ) 一个( ，z ，尼) 线性分组码的校验矩阵h 可以表示为 h = 则式( 2 - 4 ) 可以表示为 o i f l i o ： i i ： 小1 o 吃小i ，i 7 + - 啊，i 吃一，一l ( 2 5 ) 第2 章l d p c 码概述 。 i l ： 魄o 曩， ： 扩， 加。 吃一o 死一川i 吃一川嘏一i = 0 ( 2 6 ) 2 1 2 信道容量和香农极限 信道容量表是一个信道下可靠传输的最大信息传输率。不同的信道，噪声存 在的形式不同，信道带宽以及信号的各种限制不同，因而信道容量也不同。香农 在其文章中定义的信道容量为： c - m a x ，i ( x ；y ) = 日( y ) 一h ( y x ) = 剐咖( 枷。g 矧) q 。7 工i y |p ，ill x 和y 分别代表信道的输入和输出：p ( x ) 是x 的概率密度函数；，( x ；，) 是 彳和y l l i ! i l i , i , i ；圩( x ) 是信源熵；h ( y x ) 为信道条件熵，即因为信道噪声 丽造成的信息损失熵。 特例：对于带宽无限的加性高斯白噪声( a w g n ) 信道，信道容量为 c 扣：( 1 + 2 惫 p 8 ， e 是传输信号的平均功率，0 为高斯白噪声的功率谱密度。 对于带宽为w ，信号平均功率为e 的带限a w g n 信道，信道容量为 c 删( + 南) p 9 ， 式( 2 9 ) 即为著名的香农信道容量公式。 对以低密度码的研究，需要涉及到输入离散、输出连续的a w g n 信道。由 于只有输入符号均匀分布时才能使互信息量达到最大，因此假设输入符号的概率 密度函数为： p ( x ) = 拟h 厄) + 万( x 一厄) ( 2 - 1 0 ) p ( x = 厄) = p ( x = 一厄) = 0 5 对于a w g n 信道可得： 8 ( 2 1 1 ) 第2 章l o p c 码概述 p c 肛辟如 - 华 p c 枷垌= 矗e x p ( _ 华 将式( 2 一1 2 ) 和( 2 1 3 ) 代入式( 2 - 7 ) 奉f ( 2 - 1 2 ) ( 2 - 1 3 ) 一e 志斗毕 l o g x p ( _ 警卅4 ， r 表示码率，毛表示传输每一个信息比特所需的能