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

北京邮电大学博士学位论文 论文题目 专业 研究方向 博士生 指导教师 论文类型 低密度码编译码技术的研究 通信与信息系统 无线通信 邓建民 乐光新教授 应用基础 摘要 ( 签名) ( 签名) 高速信道编码是人们不断研究，但又没能彻底解决的一个课题。在单用户 通信时，通信系统的码率有一个极限值，实际通信系统的码率总是无法超越 它，这个值即为信道容量。信道编码领域中许多理论和关键技术都在不断发 展。在直接采用最大似然译码的编码技术中，实际通信系统的码率无法接近这 一极限。例如，卷积编码随著状态数的增大，计算复杂度里指数增加，而要使 得码率接近于信道容量，信道码长必须非常大，实际通信系统无法达到这个要 求。最大似然译码算法是最优的，其具有理论意义和实践意义。采用迭代译码 算法的t u r b o 码和低密度码，其实际系统的码率，可充分接近信道容量，迭代译 码算法是一种次优算法。而与t u r b o 码比较，低密度码具有数学结构较好，易于 并行实现的特点。本论文主要研究了低密度码的编译码算法，密度演化算法， 以及有记忆信道下带信道估计的改进置信扩散算法。包括： 1 推导了低密度码校验矩阵日的l u 分解算法的变换过程，比较了几种 分解算法对分解结果稀疏性的影响。仿真结果表明，对于随机方法产生的稀 疏校验矩阵，m i n p r o d 算法的效果是做好的。本文提出的m i n c o l p r o d 算法具有 与m i n p r o d 算法接近的性能。 2 密度演化算法与非正规低密度码的优化 密度演化算法是通过观察传递消息概率密度的演化过程，调整低密度 码( l d p c ) 度数分布，来优化编码方案的一种数字计算方法。通过算法可以求出 低密度码的信道容量，并且通过分析密度演化的结果，可以寻找性能更好的非 正规低密度码。非正规低密度码是一类可以同t u r b o 码竞争的信道码。 本文此部分的工作是，提出基于线性可行域的密度演化( d e ) 算法，利用可 行域的凸集特点，利用凸集顶点确定可行域。 3 求低密度码信道容量时，利用物理参数降级的特点，提出低密度码信道 t 摘要 容量的变步长两点法，降低了密度演化算法的复杂度，使得准确性提高并且复 杂度降低。 4 运用密度演化算法，求出一组莱斯低密度码信道的信道容量，并对莱斯 衰落信道下l d p c 的性能进行分析，对莱斯衰落信道下的低密度码进行优化。 5 对相关瑞利信道下低密度码的性能进行了分析，提出一种相关信道下考 虑信道状态的低密度码置信扩散译码算法。 关键词：低密度码、置信扩散、双向图、信道估计、密度演化 北京邮电大学博士学位论文 t i t l e ：r e s e a r c ho i lc o d i n ga n d d e c o d i n gt e c h n o l o g yo fl d p c m a j o r ： c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s p e c i a l t y ： w i r e l e s sc o m m u n i c a t i o n n a m e ：d e n g j i m a m i n s u p e r v i s o r ：p r o f y u eg u a n g x i n t y p e ：a p p l i e df o u n d a t i o n s i g n a t u r e s i g n a t u r e a b s t r a c t ( 英文摘要) h i g hs p e e dc h a n n e lc o d i n g i sa p r o b l e mw h i c hh a v eb e e nr e s e a r c h i n g0 n ，b u t i th a sn o tb e e nq u i t es o l v e dy e t i ns i n g l eu s e rc o m m u n i c a t i o n ，t h ec o d er a t ei s al i m i tv a l u e ，w h i l ei nap r a c t i c a lc o m m u n i c a t i o ns y s t e mt h ec o d er a t ei s b yn o m e a n sl a r g e rt h a nt h i sv a l u e ，w h i c hi sc a l l e dc h a n n e lc a p a c i t y , a l s om a n yc h a n n e l c o d i n gt h e o r i e sa n dk e yt e c h n o l o g i e sa r ed e v e l o p i n g i nc o d i n gt e c h n o l o g i e sw h i c h a d o p td i r e c t l ym ld e c o d i n g ，t h ec o d e r a t ec a n n o t s u f f i c i e n t l ya p p r o a c ht h i sv a l u e f o re x a m p l e ，t oc o n v o l u t i o n a lc h a n n e lc o d e s ，w i t ht h es t a t e sn u m b e ri n c r e a s e d ， t h ec o m p u t a t i o n a lc o m p l e x i t yi n c r e a s e se x p o n e n t i a l l y , s ow h e nw el l s ei t sr a t et o a p p r o a c ht h ec h a n n e lc a p a c i t y , t h ec o d el e n g t hm u s t b ev e r yl a r g e ，b u tt h i si so f t e n i m p o s s i b l ei np r a c t i c a l c o m m u n i c a t i o n s y s t e m m ld e c o d i n g i so p t i m a l ，a n di th a s t h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e t u r b oc o d e sa n dl d p ca r es c h e m e sw h i c h c o u l ds u f f i c i e n t l ya p p r o a c ht h ec h a n n e lc a p a c i t yi np r a c t i c a ls y s t e m ，w h i l ei t e r a t i v e d e c o d i n gi s as u b o p t i m a la l g o r i t h m c o m p a r e dw i t ht u r b oc o d e s ，l d p cn o t o n l yh a sag o o dm a t h e m a t i c a ls t r u c t u r eb u ta l s oi se a s yt ob e r e a l i z e di np a r a l l e l t h et h e s i sm a i n l ys t u d i e st h ec o d i n ga n dd e c o d i n go fl d p c ，d e n s i t ye v o l u t i o n a l g o r i t h m ，a n da ni m p r o v e m e n to nt h eb e l i e f - p r o p a g a t i o na l g o r i t h mo fl d p c i n t h em e m o r yc h a n n e lw i t hc h a n n e le v a l u a t i o n h e r e a f t e ri si n c l u d e d ： 1 d e d u c et h et r a n s f o r mp r o c e s so fl ud e c o m p o s i t i o na l g o r i t h mo fc h e c k m a t r l xhf o rl o w - d e n s i t yp a r i t y c h e c kc o d e c o m p a r et h ee f f e c t so fs e v e r a ld e - c o m p o s i t i o na l g o r i t h m so nt h es p a r s e n e s so ft h eg e n e r a t e dm a t r i c e s i tc a nb e s h o w nb ys i m u l a t i o n st h a tf o rt h es p a r s ec h e c km a t r i xg e n e r a t e da tr a n d o m ，t h e m i n p r o da l g o r i t h m i sb e s t a n dm i n c o l p r o da l g o r i t h mh a sa p p r o x i m a t e l yt h e s a m ep e r f o r m a n c ea sm i n p r o d i i i a b s t r a c t ( 英文摘要) 2 d e n s i t ye v o l u t i o na l g o r i t h ma n dt h eo p t i m i z a t i o no fi r r e g u l a rl o w d e n s i t y p a r i t y - c h e e kc o d e s d e n s i t ye v o l u t i o ni s a na l g o r i t h m w h i c ha d j u s t st h ed e g r e ed i s t r i b u t i o no f l o w d e n s i t yp a r i t y - c h e c kc o d e ( l d p c ) ，b yw a t c h i n gt h ee v o l u t i o no fp r o b a b i l i t y d e n s i t yo fm e s s a g e s b yt h i sa l g o r i t h mt h ec h a n n e lc a p a c i t yo fl d p cc a nb ec a l c u l a t e do u t ，a n db ya n a l y z i n gt h er e s u l t so fd e n s i t ye v o l u t i o n ，t h eb e t t e ri r r e g u l a r l d p c m a y b ef o u n do u t l d p ci sac o m p e t i t o ro ft u r b oc o d e s o m ew o r ki nt h i st h e s i si n c l u d e ，p r o p o s i n gt h ea l g o r i t h mb a s e do nl i n e a r f e a s i b l ef i e l df o rt h ed e r u s i t ye v o l u t i o na l g o r i t h m ，w h e r e i nu s et h ec h a r a c t e r i s t i c s t h a tf e a s i b l ef i e l di sac o n v e x ，a n du s et h ev e r t i c e sd e f i n i n gt h er a n d o mf e a a i b l e f l e l d 3 d u r i n gc o m p u t i n gt h ec h a n n e lc a p a c i t yo fl d p c ，u s i n gt h ec h a r a c t e ro f p h y s i c a ld e g r a d a t i o n ，p r o p o s et h ev a r i a b l es t e pt w op o i n t s m e t h o df o rc o m p u t i n g t h ec h a n n e lc a p a c i t yo fl d p c ，w h i c hl o w e rt h ec o m p l e x i t yo fl d p c d e n s i t ye v o h i t i o na l g o r i t h m ，s ot h a tt h ev e r a c i t yi si m p r o v e da n dt h ec o m p l e x i t yi sl o w e r e d 4 a p p l y i n gt h ed e n s i t ye v o l u t i o na l g o r i t h m ，g i v eas e to fc h a n n e lc a p a c i t y o fr i c e a nl d p c c h a n n e l ；a n a l y z et h ep e r f o r m a n c eo fl d p c u n d e rr i c e a nf a d i n g c h a n n e l ；o p t i m i z et h el d p c u n d e rr i c e a nc h a n n e l 5 a n a l y z es h ep e r f o r m a n c e o fl d p cu n d e rc o r r e l a t e d r a y l e i g hc h a n n e l ，p r o p o s ea nl d p cb e l i e f - p r o p a g a t i o nd e c o d i n ga l g o r i t h mc o n s i d e r i n gc h a n n e ls t a t e s f o rl d p cu n d e rc o r r e l a t e dc h a n n e l s k e y w o r d s ：l d p c ，b e l i e f - p r o p a g a t i o n ，b i p a r t i t eg r a p h ，c h a n n e le s t i m a t i o n ，d e n s i t ye v o l u t i o n i v 北京邮电大学博士学位论文 第一章引言 现代社会已步入信息时代，在各种信息技术中信息的传输即通信起着支 撑作用。由于人类社会生活对通信的需求越来越高，世界各国都在致力于现代 通信技术的研究与开发以及现代通信网的建设。移动通信是现代通信系统中不 可缺少的组成部分，移动通信是指通信双方至少有一方在运动状态中进行信息 传输。例如，移动台( 车辆、船舶、飞机或者行人) 与固定点之间，或者移动 台之问的通信都属于移动通信的范畴。另外，还有一种可移动的概念，即通信 用户的位置是可变的，但在通信过程中用户可能并不处于运行状态。这类通信 也可称为移动通信，但与严格意义的移动通信相比，两者的无线信道特性有较 大的差别。现代移动通信是一门复杂的高新技术，不但集中了无线通信和有线 通信的最新技术成就，而且集中了网络技术和计算机技术的许多成果。目前， 移动通信已从模拟通信发展到了数字移动通信阶段，并且正朝着个人通信这一 更高级阶段发展。未来移动通信的目标是，能在任何时间、任何地点、向任何 人提供快速可靠的通信服务。移动通信可以说从无线电通信发明之目就产生 了。1 8 9 7 年，m g 马可尼所完成的无线通信实验就是在固定站与一艘拖船之间 进行的，当时的距离为1 8 海里。现代移动通信技术的发展始于2 0 世纪2 0 年代， 但是一直n 2 0 世纪7 0 年代中期，才迢来了移动通信的蓬勃发展时期。1 9 7 8 年 底，美国贝尔实验室研制成功先进移动电话系统( a m p s ) ，建成了蜂窝状模 拟移动通信网，大大提高了系统容量。与此同时，其它发达国家也相继开发出 蜂窝式公用移动通信网。这一阶段的特点是蜂窝移动通信网成为实用系统，并 在世界各地迅速发展。移动通信得到迅猛发展的原因，除了用户要求迅速增加 这一主要推动力之外，还有几方面技术进展所提供的条件。首先，微电子技术 在这时期得到迅速发展，使得通信设备能够实现小型化、微型化。其次，提 出并且形成了移动通信新体制，即贝尔实验室在7 0 年代提出的蜂窝网的概念。 蜂窝网，即所谓的小区制，由于实现了频率再用，大大提高了系统容量。第三 方面进展是随着大规模集成电路的发展而出现的微处理器技术日趋成熟以及计 算机技术的迅猛发展，从而为大型通信网的管理与控制提供了技术手段。这一 阶段所诞生的移动通信系统一般被当做是第一代移动通信系统。从2 0 世纪8 0 年 代中期开始，数字移动通信系统进入发展和成熟时期。蜂窝模拟网的容量已 不能满足日益增长的移动用户的需求。8 0 年代中期，欧洲首先推出了数字移 动通信系统( g s m ) 。随后美国和日本也相继指定了各自的数字移动通信体 第一覃引言 制。2 0 世纪9 0 年代初，美国q u a l c o m m 公司推出了窄带码分多址( c d m a ) 蜂窝 移动通信系统，这是移动通信系统中具有重要意义的事件。从此，码分多址这 种新的无线接入技术在移动通信领域占有了越来越重要的地位。这些目前正在 广泛使用的数字移动通信系统是第二代移动通信系统。第二代移动通信系统主 要是为支持话音和低速率的数据业务而设计的。但随着人们对通信业务范围和 业务速率要求的不断提高，已有的第二代移动通信网将很难满足新的业务需 求。为了适应新的市场需求，人们正在等待第三代( 3 g ) 移动通信系统的实际应 用。但是由于3 g 系统的核心网还没有完全脱离第二代移动通信系统的核心网 结构，所以普遍认为第三代系统仅仅是一个从窄代向未来移动通信系统过渡的 阶段。目前，人们已经把目光越来越多地投向三代以后( b e y o n d3 g ) 的移动 通信系统中，使其可以容纳市场庞大的用户数、改善现有通信品质不良，以及 达到高速数据传输的要求。若以技术层面来看，第三代移动通信系统主要是 以c d m a 为核心技术，三代以后的移动通信系统则非常可能是以正交频分复用 ( 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 ) 为核心的多载波传输 技术。 在通信的基本要求：信息传输的有效性和可靠性方面，编码调制处于核心 的位置。从第三代及以后移动通信系统的发展方面来看，这些系统的共同特 征是信息的传输越来越高效，由此带来对于信道编码及载波调制的要求也就 更高，信道调制方面第三代移动通信系统己被建议使用s t b c ( 空时分组码) ， 信道编码是保证信息传输可靠性的重要措施，在现代技术条件下，传统上 认为实现复杂性较高的迭代译码算法的实现屏障已被打破，以并行级联卷积 码( t u r b o 码) ，串行级联卷积码以及低密度码( l d p c ) 等为代表的采用迭代译码算 法的码被证明几乎是满足现代通信系统要求的唯一有效的方案。这类码有一个 共同的特征，可以用双向图来表示其结构，所以也称为图码( g r a p hc o d e ) 。这些 码还使用可实施以并行结构的迭代译码算法。 接收机采用信道编码技术来检测或纠正在无线信道中传输引入的一部分或 全部的误码。解码是在接收机进行解调之后执行的，所以编码被看作是一种后 检测技术。由仙农信息论的基本原理，由于编码后会使信道传输速率提高，这 样就扩展了信道的传输带宽。信道编码通常分为两类，分组编码和卷积编码。 仙农信息论一直是信道编码技术的理论基础和指导，信息论在信道编码方面的 论点为，对于一定信道，无论是物理信道，还是广义信道( 编码信道) ，存 在着一个信息传输的界，称之为信道容量c ，当信道设计传输速率小于信道容 量c 时，总可以用一定的方法( 编码) 使得信道传输的误码率充分小，这个理 2 北京邮电大学博士学位论文 论一直在指导着信道编码技术的发展。通信专家们致力于寻求设计方案以达到 这一个信息界。对于寻找能够比较好地接近信道容量的一些码，好多种类的码 都做到了这点【9 ，2 2 ，8 2 l ，但是对于每类码，是否具有现实可行的编码方案或者 译码方案，这些码大都是不能同时满足这两个条件，所以同仙农信道编码定 理【8 51 - - 样，这些只有理论上的意义。卷积码当它们的限制长度增加时，可以接 近信道容量，但是它们的复杂性随着限制长度呈指数增加。很长段时间，一 般认为如果使用卷积码，从实现的角度看，信道的容量是一个小于信道容量的 速率”凰”，很多人认为这个猜想适用于所有的码，而在丑。之上的码率是无法实现 的。f o r n e y 证明了存在现实可行的”级联”码【5 1 1 ，但是这个证明同s h a n n o n 的证 明一样，也是非构造的f8 2 】。第一个切实可行而性能又对信道容量充分接近的码 是m b o 码，1 9 9 3 年出现的p c c c 码( 并行级联卷积码+ ，也称n t r b o 码) 1 1 5 1 ，首先 解决了这个信息编码的问题，工、i r b o 码使用一种称之为迭代译码算法的解码算 法，使得在并行设计的情况下，复杂度不是太高。不过这并不是唯一的方案，近 年来对于六十年代g a r r a g e 提出的低密度码阢8 0 】重新进行了研究和认识俐，证 明同t u r b o 码一样，它也是一种可实现的非常好的码。同样低密度码一般使用迭 代解码的密度置信算法，在并行设计的情况下，有着非常低的复杂性，解码设 备的功率消耗也比较低【4 5 】。不过很长一段时间内，由于低密度码本身的计算复 杂性，未能够引起编码学界太多的重视，这个情况持续至l j t u r b o 码出现之后， 先后有学者重新发现了低密度码的理论意义和它的重要应用价值。低密度码除 了码率能够充分接近信道容量外，在短分组的c d m a 应用中也是非常有竞争力 的8 9 - 9 1 】。目前，多进制低密度码的实验性能【6 1 6 2 】已经超 过t u r b o 码。在未来 的无线通信领域，低密度码会成为一种很有竞争力的编码方案。 1 1 无线通信对信道编码的要求 要求具有更高数据速率和更好频谱效率是三代f 3 g ) 无线通信系统的主要推 动力量。所谓的国际移动电信2 0 0 0 ( i m t - 2 0 0 0 ) 标准的三代移动通信系统，具有 下列特征 全球通用 适合所有的移动应用 支持分组和电路交换传输 p a r a l l e lc o n c a t e n a t e dc o n v o l u t i o nc o d e s i n t e r n a t i o n a lm o b i l et e t e c o m m u n i c a t i o n s2 0 0 0 3 第一辛引言 根据移动台的移动以及速度，可以提供达2 m b p s 的高速数据传输 频谱利用率高 3 g 系统在发展过程中，并没有定义一个唯一的空中接口标准，它是建立在 现有2 g 系统的基础上的，2 g 系统包括不同的技术和空中接口标准，既有码分多 址( c d m a l ，也有时分多址( t d m a ) 部分。在1 9 9 8 年有1 7 个不同的i m t 2 0 0 0 标 准向国际电联( i t u ) 提出。这些建议都面向文本，图片，语音，图像，音频以及 计算机数据的传输。确定这些建议系统的性能，要考虑许多因素。这些因素取 决于无线链路的特征，比如信号衰落，多径畸变以及带宽限制。另外，这些建 议必须能灵活地支持各种具有不同数据速率及业务质量( q o s ) 的业务，以满 足i m t 2 0 0 0 的要求。 无线系统的一个尤其重要的方面是设计高效的调制以及编码方案，调制 编码方案决定了提供可靠通信的发送和接收结构。1 9 4 8 年，仙农提出了信道容 量g 的概念，( b i t s s e c ) 。在一个加性白高斯噪声( a w g n ) 中，带宽为b ，信噪比 为s n r ，那么信道容量为 c b l 0 9 2 ( 1 + s n r ) g 表示在传输信道中，如果传输速率r c ，则无论怎样改进编码调制方案， 都不可能使误码率充分小，而是使得误码率有一个非零下界。随着t u r b 码【1 5 】的 出现，以及学者对低密度码的重新认识【6 目和研究，证实了”好码”+ 是存在的， 这些对于仙农信息论来说是一个重大的发展，丰富了它的内容。t u r b o 码是 并行级联卷积码，是非线性码，而低密度码是线性分组码，它们都能很好地 接近仙农信道容量，是”好”码。t u r b o 码使用了并非最优的迭代译码算法， 这是因为t u r b o 码的格状图是时变的，随着卷积的长度增加，状态数也呈指 数增加。同样，( 凡，k ) 线性分组码最大状态数目的上界为m i n k ，n k ，其 中k 是线性分组码的校验方程的数目，而n 是码字长。l d p c 码是一种线性分 组码，如果l d p c 译码算法中使用最大似然的v i t e r b i 译码算法，其译码复杂度 为2 m i n k t 礼- k 。所以在低密度码的实际应用中，不可能采用最大似然( m l ) 译 i 面聂石i 面话出的码是理想的，称为”非常好的码。所谓好”码指的是这样一族码，这族码能够对 于小于某个最大码翠的一个码率值，使得这族码中的一个码以任意小的错误概率达到这个码率值，而这个 冯率值是小于信道容量c 的，所谓坏”码是指，达到任意小错误概率时只能把码率降为0 的一族码。而对 于坏码 乜不一定是无用的。所谓”可行”的码是指，在时间和空间上能够以分组长度的多项式量级来实现编 码和译码的一族码。 4 北京邮电大学博士学位论文 码。低密度码( l d p c ) 可以用置信网络的分形图表示，而低密度码( l d p c i 的 校验矩阵可以为置信网络分形图的邻接矩阵，迭代译码算法中常用的s u m p r o d u c t 算法是基于译码图的次最优的译码算法。在s u m - p r o d u c t 算法中，算法 复杂度与低密度码校验矩阵中l 的数目仅仅为线性关系。这也是一个综合的算 法，通过置信迭代，解出满足定义码的所有校验方程的向量，这个向量就是 码空间中的码字。尽管由于在分形图中一定存在多个环，算法的软输出虽不 是真正的后验概率，但理论与仿真f 1o o 】都表明概率译码算法的输出是非常理想 的。在t u r b o 码领域中，交织性能增益是一个重要的参数。具有递归系统卷积 ( r s c ) 码的。l h r b o 码可以产生交织性能增益。具有r s c 成分码的2 h r b o 码的性 能受交织器大小的影响。这称为交织性能增益。通过设计一个随机交织器把 输出解相关到两个译码器中，这样在两个译码成分之间可以应用基于信息交换 的迭代译码算法。低密度码( l d p c ) 由随机稀疏校验矩阵或它的双向图定义。低 密度码( l d p c ) 译码时，对比特节点进行译码的后验概率是通过随机图进行计 算。 根据仙农公式( 1 1 ) ，有c b = l 0 9 2 ( 1 + s n r ) ，即( s r ) = 2 c b 1 ，所 以在一个单入单出的a w g n 信道中，增加1 b i t s e c h z 的信道容量，需要增 加1 0 l 0 9 1 n ( 2 ) = 3 d b 的信噪比。 1 2 信道模型 一个通信系统的信道模型示予图1 1 ，在图11 ，输入信息序列为矿，通过编 码器编码，变为信道符号序列x ，x 经过在信道中的传输，到达信道的输出 端，得到信道符号序列y ，在通信研究过程中，通常都要假定x 与y 的符号个数 相等。由x 至】，的过程，可以用条件概率转移函数来描述，f i x ( 可 z ) 。因此， 可以看到在，至x 的变换中，包括通常的信道编码和调制，而在y 至矿的过程中 包括解调和译码。这是一般的模型，再来建立更为具体的模型。 定义1 1 ：信道称为无记己的，如果信道的输出只与信道的即时输入f 即s 信 道输出对应的信息符号) 有关部如果信道输入为x = o l x 2 t 3 x n 并且信道 输出为y = y _ l y 2 y 3 t y n ，则剪b ，l x ( y x ) = p v f x ( y lj 。1 ) 最， x ( 现! 。2 ) 最，i x ( 掣a l z 3 ) ， 一砖7 x ( y n l 。) 这样使得信道可以完全由输入符号x 和输出符g - y 以及户v x ( 1 z ) 决 定。 定义1 2 ：信道容量，倍道的信道容量为信遭可无差错f 差错概率任意小) 传输 5 第一章引言 屯三k 画 图1 1 ：通信系统模型 的最大信息率，令p z x ) 为倍道输入嘱符号的先验概率它为司变的，p y x 表 示后验概率用i t x j y 、表示x 秘z 间的e 信息，当先验概率p x i j x 、变化 时，x 和v z 间互信息的最大值为信道的容量c ，即c = m a x p x ( x 、i i 您y j l 。 锐1 1 ：桶性白高斯信道a w e n ) ，是通信系统串常用韵信道模型一般表示通 信条件最差的情况，即最保守的情况，输入符号集x ，和输出符号集y 皆为实数 集r ，输入和输出之闻满足关系y = x + ，其中为均值为0 ，方差为矿2 的高 斯白嗓声那么p r i x b 为均值为z ，方差为一韵高氟概率密度函数。 戳1 ，2 ：b s c ( 二元对称信道) ，b s c 信道为一类简单信遭，只由一个参数p 决 定，又因为具有对称的性质，所以能简化一些复杂的分析，特别是在编码 应甩研究中b s c 信道为基本的信遭模型之一。在b s c 信道中，输入符号 为x = ( o ，l ，输出符号为y = o ，l ，并且b ，i x ( o i l ) = p y i x ( 1 1 0 ) = p 。如 图2 图1 - 2 ：b s c 信道模型 例1 3 ：z - i 言n ，信道符号同在定义，君中的x 和y ，发送端发送符号o b 寸，接收 端一定会收到o ，p y i x ( ol o ) = 1 发送端发送1 时，接设端以概率p 收至蜘，以概 6 北京邮电大学博士学位论文 图1 3 ：z 信道模型 率1 一p 收到，脚i x ( 1 l o ) = 0 ，p y l x ( 0 1 1 ) = p ，p y i x ( 1 i l ) = 1 一p 。如图j 跚 示。 对于二元信道，假设需要计算已知信道输出结果的情况下，原输入信道符号 的可能性，就需要计算后验概率马( i y ( x o l y = y ) 和p x l r ( x = l l y = ) ，后 验概率为条件概率，所以满足关系式& - l y ( x = o l y y ) + 取i y ( x = lj y = y ) = 1 ，因此这两个后验概率是不独立的，自然可以用一个量来表示，一般 这个新的量取它们的比值，f 父1 y ( x = o l v = g ) f k y ( x = l i y = y ) ，称为似 然比( l i k d y r a t i o ) ，有对取对数，称为对数似然比( 1 0 9 - l i k e l y r a t i o ) 。信源发出 的信源符号，通过信源编码与信道编码的变换，在输入二元信道前，变为二 进制的比特流，二元制比特流中，一般假定为均匀( u n i f o r m l 的，即x = 1 ， 和x = 0 的先验概率相同，都为 ，所以由b a y e s 公式和全概率公式有： p x f y ( x = o l y = y ) l p x i r ( x = 1 i f = g ) p x i v ( x = o l y = y ) p ( y = y 、 玖t v ( x = 1 1 y = y ) p ( y = y ) p y i x ( y = y i z = o ) p ( x = 0 ) f 专( y = y i x = l ) p ( x = 1 ) p v x ( y = y f x = 0 ) ，、。、 p y i x ( y = i x = 1 ) ”7 7 第一章引言 定义1 3 ：似然比，对于二元输入售道，比值甓景妻；g 器称为似然比，似然比 取自然尉数i 。g 是蓦燕暑高称为对数似然比( l 兄) 。 在任意二元输入信道的似然比中，似然比及对数似然比的形式依赖于对信 道噪声n = y x 的分布所作的估计。 定义1 4 ：二元输入对称信道佃巧a ，是一个信道输入符号为x = o ，1 ，输 出符号为实数集尺的无记忆信遁，并且满2 ：p v l x ( y = y l x = 0 ) = p v i x ( y = 一y i x = 1 ) 。所以b 俗e 信道可以完全由p y i x ( y = y l x = o ) 来决定。 例1 4 ：二元删除信道( b e 回，信道的输入符号集x = ( 一1 ，1 ，信道的输出符 号集为y = f 一1 ，0 1 ，输出符号0 表示删除，即码符号丢失，二元输出符号与 二元输入符号相等的概率为f h x ( y = 1 i x = 1 ) = p y i x ( y = l l x 1 ) 一 l p ，输出等于零的概率为& = o l x = 1 ) = r i x ( y o l xi ) = p 。 剿除信道为一个非平r 的简单信道在研究低密度码时，经常以这种信道作 为研究对象。这类信道上的低密度码称为低密度纠删码( l o w d e n s i t ye r a z u r e c o d e ) ，又称为复损码( l o s s r e s i l e n tc o d e ) a 图1 4 ：b e c 信道模型 飘1 5 ：二进输入加性白高斯信道( b i a g n ) ，是常用的通信系统的信道模型， 输入基带符号集x = 卜1 ，1 ) ，输出符号集y 为实数集豫，输人符号和输出符 号之间满足关系y = x + n ，其中为均值为口，方差为盯2 的高斯自噪声，那 _ 幺p z l x l 讲z 、为均值为茁，方差为萨的服从商巅分布的随机变量的密度函数。 8 北京邮电大学博士学位论文 由于b i a w g n 信道的条件概率密度函数满足对称条件，所以信道容量为 在p ( z = 1 ) = p 江= - 1 ) = 时的输入输出之间的互信息，所以b i a g n n 道的信道容量为 c = ，一赤五万( 斋) 唧譬扼s ， 例1 6 ：二进输入拉普拉斯信道伊儿，输入符号为x = 一l ，1 ) ， 集y 为实数集r ，输入和输出z 阃满足关系y = x + l l 限扶分布 p b i l ( z ) ：万1e 一掣 b i l 信道的信道容量为 = - i t + 玎4a r c t a n ( e - 1 1 ) 也( 掣) 1 3 码和码族 输出符号 ( 14 1 信道编码总是在信息比特中加入冗余，产生适合信道传输的码字，通过在 信息和冗余之间建立一定的数学关系，在信道接收端就能够利用这些关系，纠 正接收码字中的误码( 纠错) ，或者把接收码字中错误的码字检验出来，从而 使得接收端作出放弃接收码字，通知发送端对传错码字进行重传或者进行其 它处理的决定。在图1 1 的通信系统模型中，限制x 的取值为某个码e 中的码字 ( 编码) ，通过构造e 使得e 中的码字具有一定的性质，比如，使得笆中的码字 之间的最小距离较大，这样码c 中的两个不同码字q 和之间，不容易受信道 差错的影响，而产生误码。 定义1 5 ：群，设g 是一个非空集合。如栗在g 上定义了一个代数运雾g ：a b c a g 。b g 。c g ，称为乘法( 般意义上的乘法s 环中的乘法相区渤) ， 记做o + b ，而且运算适合以下条件j 对于g 申任意元素。油，c 有 a ( b c ) = ( a b ) cr 结合封； 在g 中有一个元素，它对g 孛任意元素。有 9 第一章引言 对于g 中任惹元素口郝存在g 孛一个元素b 使 b a = e 在群的定义中，没有要求群的运算适合交换律，。6 = 妇。如果群g 的运算 适合交换律，那么群称为交换群或阿贝尔( a b e t ) 群。群g 中元素的个数称为 群g 的阶，i a 为i c 。如果i g f 为有限数，g 称为有限群。如果l g f 为无限，g 就称 为无5 艮群。代数编码理论中常用的g m o v o i s 域，包含的加法群和乘法群都为有限 群。 定义1 6 ：环，设l 是一非空集合，在l 上定义了两个代数运算，一个叫加法， 记为a 十6 ，一个日“乘法，记为曲。如果具有性质j l 对于加法成为一个交换群； 乘法的结合律：对所有舭，6 ，c l ， a ( b c ) = ( a b ) c ； 乘法对加法的分配率：对所：有d c j a ，b c l a ( b + c ) = a b + d c ， ( b + c ) d = b a + c a ； 那么l 称为一个环。 定义1 7 ：设三为一个环。如果三中有一个元素e 具有性质： e o = a e = 口v a l 那么e 称为环l 的单位元素，可以证明，环中的单位元是唯一的。具有单位元素 的环穆为幺环。 定义1 8 ：如果环l 的乘法适合交换律，即 a b = b a ，v a ，b l 那么l 称为交换环。 定义1 9 ：域如果环f 是交换幺环，至少含有两个元素，且全体非零( 环中加 法群的单位元) 元素对乘法或一群。那么环f 称为域。 】0 北京邮电大学博士学位论文 定义l 。i o ：有履域，元素个数有煨的域，又称为伽罗瓦域，是亩伽罗瓦首先发 现的。 域同构，如果在域f 和f 7 之间有一个一一对应，口，并且对f 中任意两个元 素n ，6 ，有 a ( a b ) = 矿( d ) 旷( 6 ) 盯( o + 6 ) = 盯( n ) + 盯( 6 ) 则f 和f 称为同构，同构的域看作是同一个域。 定理1 1 ：对每个素9 勋和任一芷整数n ，存在一个唯一序助“个元素的有腹域，除 此之铃无其它矿个元素的有限域。 最简单的域是g a l o i s 域g f ( 2 】，只有两个元素，一个零元，一个幺元，0 ，1 ， 加法为通常的模加，乘法为通常的乘法。同样当q 是素数时，g f ( q ) = 0 ，1 ， g 1 ) a 域g f ( p ) 至l j 域g f ( p ”) ，g f ( p ) 称为a f ( p ) 的扩张域。 定义1 1 1 ：羁袭a 中的码长为n 的分组码定义为a “的子集，印表示a 的笛卡儿乘 积。这个舻的子集的元素称为码字。 实际上，在通信应用中，总是希望找到的码具有比较好的数学结构，典型 的结构有代数结构，当分组码的所有元素构成一个域时，称为线性分组码。 定义1 1 2 ：域f 上的一个( n ，七) 线性码是p 的维线性子空闭。叫做该码的维 数，r n k 是它的线性冗余。并且r = k n 是码率。二迸分组玛是二 元g a l o i s 域g f 俐上的线性分组码。 线性码具有比较好的性质，例如线性码的所有元素构成一个线性空间，所 以对于码c 中码字元素c ，有e c = e 。此外，对于线性码，它可以由它作为一 个线性予空间的基所唯一确定，不妨以一个行向量表示e 中的码字，则线性码的 基向量组成的矩阵称为线性码的生成矩阵g ，基向量可唯一确定已知线性码。 定义1 1 3 ：( n ，) 线控码e 的生成矩阵g 是亩线性码的个基f 句量组成的矩阵，v u f 。为信息比特亭列f 以行向量表示) 刚u g 为对信息比特荸多她进行编码形成 的码字。所以，可以把码的生成矩阵用于编码算法。 线性码的另一个重要的参数为校验矩阵h 。 对于( n ，k ) 线性码c ，为一个线性空间，仍记为c ，其核空间为勇，并且勇的 维数为礼一七，由核空间的定义，v a c ，v b 勇，n 与6 的内积为0 ，即o b = 1t 第一章引言 0 。昴的孔一个基向量( 以行向量表示) 组成( n 一妫他矩阵，记为日7 ，有v a ，o 日= 0 ，h 称为线性码c 的校验矩阵。 定义l - 1 4 ：h a m m i n g 距离，分组码c 中两个码孚a