(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf_第1页
(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf_第2页
(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf_第3页
(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf_第4页
(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf_第5页
已阅读5页,还剩60页未读, 继续免费阅读

(信号与信息处理专业论文)无线网络中基于信息理论安全的物理层协议研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

南京邮电大学 硕士学位论文摘要 l i i it i ii i ifi ii fi i iiiil y 17 5 4 7 7 2 南京邮电大学硕士研究生论文摘要 摘要 随着无线网络和英特网的发展,接入节点变得错综复杂,使得网络通信的安全性很难 得到保障。信息安全和保密通信成为了通信领域研究的热点。现代密码学的加密算法大多 数是基于计算复杂度的应用层加密算法,随着计算机性能提高尤其是量子计算技术的挑 战,需要构建更科学更完善的密码体制。根据香农的完全保密的概念,把信息论和密码技 术相结合的保密通信技术成为一个新的研究方向,即根据信道型的物理特性,研究对应的 保密方法。 本文围绕无线网络中基于信息理论安全的物理层协议进行了研究,介绍了目前国内外 发展现状,以及开展该课题的研究意义。根据目前信息理论及编码技术的发展现状,把物 理层安全的研究定位于基于信息理论的密钥共享算法的研究。介绍了有噪信道的密钥共享 模型,建立了一个完整的密钥共享算法框架。在此基础上,重点研究了协商纠错过程,并 利用分布式信源压缩编码的概念,论证了协商纠错编码和有边信息的的信源压缩编码之间 的等价关系。介绍了当初始化信息为连续随机变量时的协商纠错算法,讨论了连续型随机 变量的协商纠错和编码调制技术之间的内在联系,并提出了一种多级编码信道模型。连续 型随机变量协商纠错算法分为两部分:第一部分是量化以及区间划分,本文讨论和总结了 协商纠错的理想迭代算法,并提出了的一种新的量化方法,得到了一个很高的理想协商效 率。第二部分是根据第一部分的量化思想,得出不同信噪比下的分量码的最佳码率。以最 佳码率作为设计协商纠错编码的标准,对分量进行了设计。本文设计的协商纠错算法和s e c 算法性能进行对比,协商效率得到了提高。 关键词:无线网络安全完全保密密钥共享低密度奇偶检验码纠错编码 南京邮电大学硕士研究生论文 a b s t r a c t a b s t r a c t a sw i r e l e s sn e t w o r k sa n di n t e r n e tc o n t i n u et of l o u r i s hw o r l d w i d e , t h ea c c e s sn o d e sh a v e b e c o m ec o m p l i c a t e da n dt h es e c u r i t yo fn e t w o kc o m m u n i c a t i o ni sd i f f i c u l tt ob e g u a r a n t e e d m o d e mc r y p t o g r a p h ye n c r y p t i o na l g o r i t h m sa r eb a s e d o nt h e c o m p u t a t i o n a l c o m p l e x i t yo ft h ea p p l i c a t i o nl a y e re n c r y p t i o na l g o r i t h m s w i t h t h ei n c r e a s e d c o m p u t e r p e r f o r m a n c e ,e s p e c i a l l yt h ec h a l l e n g eo fq u a n t u mc o m p u t i n gt e c h n o l o g i e s ,n e e dt oc o n s t r u c tm o r e s c i e n t i f i ca n db e t t e rc r y p t o s y s t e m a c c o r d i n gt os h a n n o n sc o n c e p to fc o m o l e t ec o n f i d e n t i a l i t y , t h ec o m b i n a t i o no fi n f o r m a t i o nt h e o r ya n dc r y p t o g r a p h ys e c u l c o m m u n i c a t i o nt e c h n o l o g yi s b e c o m i n gan e wr e s e a r c hd i r e c t i o n n a m e l ya c c r o d i n gt ot h ep h y s i c a lc h a r a c t e r i s t i c so ft h e c h a n n e lm o d e l ,t or e s e a r c ht h em e t h o dt oc o n f i d e n t i a l i t y t h i sp a p e ri sb a s e do nt h ep h y s i c a ll a y e rs e c u r i t yp r o t o c o l si n f o r m a t i o nt h c o r y t h e d e v e l o l n n e n to ft h es t a t u sa th o m ea n da b r o a da n dt h er e s e a r c hs i g n i f i c a n c eo ft h e 酬i 岫a f r o d e s c r i b e d b a s e do nc u r r e n td e v e l o p m e n ts t a t u so fi n f o r m a t i o nt h e o r ya n dc o d i n gt e c h n o l o g y , t h i s p a p e ri sl o c a t e di nk e yd i s m b u t i o no fi n f o r m a t i o nt h e o r y as e c r e ts h a r i n gm o d e lo fd i s t u r b i n g d m m e ti s 白a t r o d u c e d , a n aac o m p l e t ef r a m e w o r kf o rk e yd i s t n b u t i o na l g o r i t h mi se s t a b l i s h e d a l o to fw o r ko ft h i sp a p e ri sf o c u so nr e c o n c i l i a t i o n b a s e do nt h ec o n c e p t so fd i s t r i b u t e ds o t l t c o d i n g , t h i sp a p e rh a sp r o v e dt h ee q u i v a l e n c eb e t w e e nr e c o n c i l i a t i o na n ds o u r c ec o m p r e s s i o n c o d i n gw i t hs i d ei n f o r m a t i o n ar e c o n c i l i a t i o na l g o r i t h mi sp r o p o s e dw h e n t h ei n i t i a li n f o r m a t i o n i sc o n t i n u o u sr a n d o mv a r i a b l e t h ei n h e r e n tc o n t a c t i o nb e t w e e nt h ec o d e dm o d u l a t i o nt e c h n i q u e a n dc o n t i n u o u sr a n d o mv a r i a b l er e c o n c i l i a t i o ni sd i s c u s s e d a n dam u l t i - l e v e lc o d i n gc h a n n e l m o d e lf o rc o n t i n u o u sr a n d o mv a r i a b l er e c o n c i l i a t i o ni sp r o p o s e d c o n t i n u o u sr a n d o mv a r i a b l e r e c o n c i l i a t i o na l g o r i t h mi sd i v i d e di n t ot w op a r t s t h ef i r s tp a r ti sq u a n t i t a t i o na n di n t e r v a l d i v i s i o n t h i sp a p e rh a sd i s c u s s e dt h ei d e a li t e r a t i v ea l g o r i t h ma n dp r o p o s e dan e wq u a n t i t a t i o n m e t h o dw h i c hr e a c h e dav e r yh i 曲i d e a le f f i c i e n c y t h es e c o n d p a r t i st h ed e s i g no f r e c o n c i l i a t i o nc o d i n g c o m p a r e dw i t ht h ep e r f o r m a n c eo fs e ca l g o r i t h m ,t h er e c o n c i l i a t i o n e f f i c i e n c yh a sg r e a t l yi n c r e a s e d k e y w o r d s :w i r e l e s sn e t w o r ks e c u r i t y , c o m p l e t ec o n f i d e n t i a l i t y , k e yd i s t r i b u t i o n , l o w - d e n s i t yp a r i t yc h e c kc o d e s ,e r r o r - c o r r e c t i n gc o d e s u 南京邮电大学硕士研究生论文 目录 目录。 摘要i a b s t r a c t i i 目勇乏i i i 第一章绪论1 1 1 弓i 言1 1 2 研究意义1 1 3 研究概况3 1 4 论文章节安排6 第二章信息理论基础8 2 1 香农熵以及互信息8 2 2c o l l i s i o n 概率和c o l l i s i o n 熵 2 3h a s h 函数。 8 2 4i d p c 码。 2 4 1l d p c 的概念 9 9 9 2 4 2 规则l d p c 码和非规则l d p c 码。ll 2 4 3l d p c 迭代译码算法。1 2 2 5 基于e x i t 图的l d p c 码的性能估计和分析1 4 2 5 1e x i t 图的原理和译码器模型1 4 2 5 2e x i t 图在l d p c 码的应用一1 6 2 6 小结19 第三章有噪信道密钥共享模型2 0 3 1 保密容量的概念2 0 3 2 密钥分发速率2 2 3 3 有噪信道的密钥共享模型。2 4 3 3 1 信息初始化阶段2 4 3 3 2 优先提取一2 5 3 3 3 协商纠错2 6 3 3 4 保密增强2 6 i i i 南京邮电大学硕士研究生论文 目录 3 4 协商纠错与分布式信源编码2 7 : 3 4 1 分布式信源编码理论基础2 7 3 4 2 离散随机变量的协商纠错2 9 3 5 小结3l 第四章连续随机变量的协商纠错3 2 4 1 高斯信道密钥共享模型3 2 4 1 1 密钥共享框图3 2 4 1 2 离散和连续随机变量协商纠错之间的联系3 3 4 1 3 连续协商纠错与有边信息的信道编码之间的联系3 5 4 1 4m l c m s d 协商纠错编码原理3 7 4 2 量化以及区间划分算法设计3 8 4 2 1 理想迭代算法3 9 4 2 2 改进迭代算法4 2 4 3 协商纠错编码设计4 5 4 3 1 最佳码率4 6 4 3 2 设计接近最佳码率的l d p c 码4 8 4 3 3 实验结果及分析5 l 4 4d 、刍占5 3 第五章总结与展望一5 4 5 1 总结5 4 5 2 展望5 5 参考文献5 6 致 谢5 9 攻读硕士学位期间发表的论文目录6 0 南京邮电大学硕士研究生论文第一章绪论 1 1 引言 第j 章绪论 随着英特网的迅速发展,以及无线网络兴起,接入网络的节点变得错综复杂,从而使 得网络通信的安全性很难得到保障。比如由于无线网络具有广播特性,在无线网络中传送 数据就特别容易遭到窃听。因此保密和安全通信的研究具有越来越重要的意义。传统密码 学的安全研究的大多数是独立于应用层的,目前应用的比较广泛的加密技术,比如l i s a 和 a e s ,都属于应用层加密技术,前提是假设物理层能提供无差错链路。理论和实践表明, 与传统的加密方法不一样的是,也可能通过物理层安全得研究来加强现有数字通信的安全 性。信息理论安全就是属于物理层安全的一种,它被广泛认为是最严谨的安全概念,通常 需要密码技术和信道编码技术相结合。它的基本原理是利用信道传输的随机性,保证无线 网络中恶意窃听的第三方,不能对信息进行正确译码。 1 2 研究意义 和有线网络相比,无线网络除了存在有线网络所面临的安全问题之外,还存在着一些 其他的安全问题。第一个问题是网络拥塞问题。网络中的攻击者通过大量的在物理信道上 发送垃圾消息,从而导致整个网络瘫痪,使得网络中的合法用户无法正常通信。网络安全 的设计人员也很难应对这种类型的网络攻击。第二种是,由于网络中的身份认证机制的欠 缺,导致攻击者绕过安全障碍,例如防火墙进行非法接入。第三种是由于无线网络的广播 特性,攻击者很容易对网络中传送的数据进行窃听。本文研究的正是第三种安全威胁的应 对策略,我们假定网络模型已经具有身份认证机制,任何对消息的篡改,以及冒充合法用 户都会被发现。窃听者只能被动的窃听信道上的消息,而不对消息进行更改。 网络分层的概念的提出,主要是为了使得通信协议简单化。人们延续了网络分层的概 念,对于上述的安全问题提出了不同的解决方案。例如,物理层的扩频调制技术,缓和了 信道拥塞问题。应用于数据链路层身份认证技术,可以预防攻击者的非法接入。应用层的 数据加密技术,使得窃听者很难窃听到有用的信息。对物理信道的窃听,属于物理层的攻 击,人们也可以从物理层的角度加强网络的安全性。 现代密码学的加密算法分为对称加密和公开密钥加密,对称加密算法是应用较早的加 南京邮电大学硕士研究生论文第一章绪论 密算法,技术成熟。在对称加密算法中,数据发信方将明文( 原始数据) 和加密密钥一起经 过特殊加密算法处理后,使其变成复杂的加密密文发送出去。收信方收到密文后,若想解 读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复 成可读明文。不足之处是,交易双方都使用同样钥匙,安全性得不到保证。此外,每对用 户每次使用对称加密算法时,都需要使用其他人不知道的惟一钥匙,密钥管理成为用户的 负担。对称加密算法在分布式网络系统上使用较为困难,主要是因为密钥管理困难,使用 成本较高。公开密钥加密算法使用两把完全不同但又是完全匹配的一对钥匙一公钥和私 钥。加密明文时采用公钥加密,解密密文时使用私钥才能完成,而且发信方( 加密者) 知道 收信方的公钥,只有收信方( 解密者) 才是唯一知道自己私钥的人。由于不对称算法拥有两 个密钥,因而特别适用于分布式系统中的数据加密。广泛应用的不对称加密算法有r s a 算 法和美国国家标准局提出d s a 。不足之处是加密速度比较慢。 传统的加密算法都是基于计算复杂度的。虽然基于计算复杂度的密码学在信息安全方 面发挥重要作用,在维护信息安全方面取得了很大的成功,但也存在一些问题。首先,计 算密码不能提供具有无条件安全性的密码方案。现代密码学认为,任何加密体系的加密解 密算法都是可以公开的,其安全性在于密钥的保密性。实际上,由于存在被动窃听的可能 性,如果通信双方完全通过在经典信道上传输信息,则在双方之间建立保密的密钥是不可 能的。其次,随着技术的不断发展,计算机的计算速度呈级数增长,量子计算机的即将出 现更是威胁着计算密码的安全性。研究表明,用量子计算机破译r s a 算法只要几分钟量级 的时间;说明现有的计算密码在计算机技术的发展面前已经力不从心,要维护信息安全需求 构建更科学更完善的密码体制。 根据香农的完全保密的概念,把信息论和密码技术相结合的保密通信技术成为一个新 的研究方向。所谓的完全保密系统,就是假设有如图1 1 所示的信道模型。发送方a l i c e 要在一个不安全的信道上传送一个消息m 给接收方b o b ,窃听者e v e 没办法根据密文恢复 消息m 。也就是e v e 收到密文c 的条件下,不能得到任何关于m 的信息,即x ( m ,o = 0 。 即h ( m ) = h ( m i c ) ,即明文数据和密文数据统计独立,人们又把满足上述等式的安全称为无 条件安全。在抗击惟密文攻击中,完善保密与无条件安全是等价的。无条件安全又称为信 息理论安全,因为它从信息论的角度来考虑的。在完善保密的密码系统中,不管e v e 使用 多长的时间以及有多大的运算能力,他采用任何破译方法都不会比在未知密文的情况下对 明文进行随机猜测强。本文正是从信息论安全的角度,对无线通信物理层的安全协议进行 了研究,从而可以对现代加密系统起到一个补充和加强的作用。 2 南京邮电大学硕士研究生论文 第一章绪论 1 = :1 i 图l - l 密码系统基本框图 基于信息理论的安全研究和基于计算复杂度的安全研究都是密码学非常重要的研究 方法。信息理论的安全作为密码学研究的一个分支,相对于基于计算复杂度的安全研究有 更严格的概念性。由于它是建立在信息理论基础上,假定窃听者e v e 拥有无限的时间、设 备和资金,对e v e 的计算能力不做任何限制。即使窃听者e v e 能在很短的时间内将所有的 密钥都遍历一遍的话,无条件安全密码系统也不会被攻破。随着科技的迅猛发展,具有无 限计算能力的量子计算机和d n a 计算机的实现也不是梦想,故无条件安全模型的建立有 着非常现实的意义。 1 3 研究概况 最早的无条件安全密码学的研究者香农,提出了完全保密的概念,而且证明了完全保 密密钥的存在性。即在任何一个完全保密系统中,要求加密密钥的长度至少和明文的长度 一样长。典型的例子就是一次一密体制,它要求密钥必须以完全随机的方式产生,并通过 安全的途径送给通信对方,每次用过后的密钥都立即销毁。因此,在很长一段时间内,人 们认为无条件安全是很难实现的。但值得一提的是,s h a n n o n 在证明他的完全保密定理中, 假设窃听者除了不知道密钥外,所获得的信息与合法用户是一样的。 由于香农的完全保密很难实现,且他所限定的条件在现实生活中很难实现,人们又对 香农的完全保密模型进行了适当的修改。修改后的模型更接近实际,而且也是可证明的无 条件安全模型。第一个修改就是放松s h a n n o n 对明文和密文毫不相关的限制,使明文和密 文有任意小的相关性;第二个修改是去除窃听者能够接受与合法用户一样的信息这一假 设。基于上述两个修改条件的典型例子就是量子信道和有噪信道。 量子密码主要是由w i e s n e r 提出,在8 0 年代由b e n n e t t 和b r a s s a r d 发展起来的【6 j 。它 主要是通过光子( 更精确地说是低密度的光子束) 在光纤上的传输来实现的。在量子世界中, 依据h e i s e n s e b r g e 的测不准原理,有一些物理性质是不相容的。测量其中的一个性质,会 使另一个性质的测量值变得随机。例如,测量某单个光子的线偏振会使圆偏振的测试结果 随机。从传统密码学和信息理论角度来看,窃听者在通信双方没有意识到的情况下进行窃 堕室塑! 皇奎堂堡主堕壅竺堡奎蔓二童堕笙 听是不足为奇的。但是在量子信道中,数字信息编码为光子的偏振态,窃听者如果对所传 输的信息进行窃听时,会不可避免地引起量子信道上的随机干扰。现在的量子密钥共享协 议己经可以在2 0 - 3 0 公理内实现。 有噪信道,是相对于香农的完全保密系统的无噪信道提出的。从香农对无条件安全模 型的限制条件可以看出,他考虑的是无噪信道,故他总是假设窃听者可以收到与合法收方 同样的信息。但是实际中的信道都是有噪声的,且都是通过纠错码来消除信道中的噪声的。 所以,如果在密码学中直接使用这样的有噪信道,就可以不考虑香农这一假设的限制了。 在香农理论的基础上,w y n c r 提出了搭线窃听信道模型,后来c i s a r 和k o m c r 又对搭 线窃听信道模型进行了重复的定义。c i s a r 和k o m e r 的窃听信道模型又称为有加密消息的 广播信道模型。 w y n e r 提出的窃听信道模型【8 】如图1 2 所示,a l i c e 通过一个有干扰的信道给b o b 发送 消息,a l i c e 和b o b 之间的信道有称为主信道。而e v e 则通过另一个有干扰的信道,这里 称为次信道,窃听主信道的输出。由于e v e 窃听到得信息经过的是主信道和次信道级联的 信道,所以e v e 获得的消息z 是y 的州尽化版本。 在这个模型中,x , y , z 形成了一个马尔科夫链,局盯= 艺l r 这意味着i ( x ;z l y ) = = 0 ,w 油贯 的分析结果表明:在这种情况下,发方可以在与收方不共享密钥的条件下无条件安全地向 收方发送秘密信息 z 图1 2 搭线窃听信道模型 c i s a r 和k o m a 的窃听信道模型又称为有加密消息的广播信道模型忉,如图1 3 所示。 主信道和次信道是两个独立的离散无记忆信道。信道转移概率为叭并定义了保密容量的 概念g ( 饬。x ) 。保密容量的含义是a l i c e 使得e v e 得到的关于发送消息任意小的情况下, 向b o b 发送消息的最大速率。c i s a r 和k o m o r 证明在主信道的信道特性比次信道好的情况 下,可以得到g ( 吃x ) 大于零的值。从理论上说明,有可能存在一种信道编码方法,使得 a l i c e 向b o b 安全发送消息的速率大于。然而,至今也没找到一种合适的编码方法。由于 4 南京邮电大学硕士研究生论文第一章绪论 很难找到实际的编码方法,在很长一段时间内,信息理论安全的研究,一直停滞不前。 z 图1 - 3 有保密信息的广播信道模型 随后,m a u r e r 又对上述模型进行了推广。他提出了一个利用相关随机信息进行协商的 密钥共享模型。a l i c e 和b o b 得到了彼此相关的特殊信息,利用一个无噪不安全的公共信 道进行密钥协商,对于知道一些边信息的e v e 却几乎得到不到关于最终密钥的信息。一种 特殊情况就是假设一个卫星信源以低信噪比不断地向地面发送随机比特串 u = ( q ,呸) 舢i c e ,b o b 和e v e 分别用不同的接收天线同时接收卫星信源的信号分别得到 三个随机变量x = ( 五,五) ,y = ( k ,k 一) 和z = ( z l ,z 2 ) 近年来,m a u r e r 在他的一篇重要文章中证明,即使主信道的信道特性比次信道差,也 可能在一个不安全的认证信道上实现通信双方的密钥共享。事实上,m a u r e r 提出了一个实 现发送方和接受方密钥共享的方案,通过在公共反馈信道传送消息却不向窃听者泄漏任何 关于密钥的信息。在这个方案中,次信道和主信道都是彼此独立的具有随机噪声的二进制 对称信道。由于由接受端产生并与发送端共享的密钥可以用来加密信息,所以即使次信道 特性很好也可以实现机密的传送。 同时由于无线信道的应用越来越广泛,无线信道的广播特性使得网络特别容易遭到窃 听,人们重新对信息理论安全研究有了空前的热情。h e r o 介绍了用于无线通信保密的空时 信号处理技术,g o e la n dn e 昏求出了m i m o 通信系统中的信息最高可达的安全速率。p a r a d a a n db l a h u 研究了各种衰落信道下的安全容量。b a r r o sa n dr o d r i g u e s 详细的研究了慢衰落信 道上的安全容量,结果表明慢衰落信道上,即使窃听者拥有更高的s n r 仍然可以实现保密 通信而无需通过反馈或者引入人为干扰噪声。虽然已经有了以上的诸多的研究,但是有关 无线通信中物理层编码工作还是很值得注意的问题。这种基于物理特性的信息论安全理 论,不受到计算复杂度的约束,而且理论上只要用于密钥共享的算法足够好,用于这种算 法的编码选择的码长合适可以实现完美保密通信,也就是它的通信速率可以达到安全容 量。 无条件安全作为密码系统的一个重要分支,得到了越来越多人的关注,而且也有了相 s 堕窒堂皇奎兰堡主堕壅竺堡苎墨二雯笙堡 当多的理论成果。随着信道编码技术的发展,在将来在实际的通信系统中实现无条件安全 通信也极有可能。然而,现阶段的编码技术却很难设计出一种可行的编码方法,能直接应 用于高斯信道和瑞利信道。本文考虑到无条件安全的研究现状,及现有编码技术的限制, 主要侧重于利用无条件安全实现密钥共享的协议研究。本文的理论基础也是基于m a u r e r 的理论基础。 1 4 论文章节安排 本文围绕无线网络中基于信息理论的物理层安全协议进行了研究,介绍了目前国内外 发展现状,以及开展该课题的研究意义。根据目前信息理论及编码技术的发展现状,把物 理层安全的研究定位于基于信息理论的密钥共享算法的研究。介绍了密钥共享算法的结 构,以及各个阶段的对整个算法的意义。重点研究了连续型随机变量协商纠错算法,提出 了用于该算法的一种量化方法,这种量化方法,使得最佳协商效率非常高。 第一章是论文的绪论部分。介绍了本课题的研究现状和研究意义。 第二章介绍了信息论的一些重要概念,也是本论文研究的重要依据。如互信息的概念, 在后面的章节中有着至关重要的作用,还有c o l l i s i o n 概率和c o l l i s i o n 熵的概念,是保密增 强技术的理论基础。介绍了l d p c 码,l d p c 码即低密度奇偶校验码,是一种特殊的线性 分组码,因而具有线性分组码的共同特性。l d p c 码与一般线性分组码的主要区别是,其 校验矩阵为稀疏矩阵。这一特点使l d p c 码具有自己独特的异于一般线性分组码的编码和 译码方法。 第三章介绍了保密容量的概念,总结和推导了m a u n e r 密钥共享模型的密钥分发速率 的上界和下界。总结了有噪信道密钥共享算法的总体框架,整个算法总共分为四个阶段, 即信息初始化阶段、优先提取阶段、协商纠错阶段以及保密增强阶段。本文的研究重点是 放在这四个阶段的协商纠错阶段。所以第四节着重介绍了离散随机变量的协商纠错过程, 并且介绍了协商纠错和有边信息的信源压缩编码之间的内在联系,论证了协商纠错和有边 信息的信源压缩编码之间的等价关系,下一章将会论证有边信息的信源压缩编码和有边信 息的信道编码之间的等价关系。 第四章提出了高斯信道的密钥共享模型,介绍了当初始化信息为连续随机变量时的协 商纠错算法,讨论了连续型随机变量的协商纠错和编码调制技术之间的内在联系。然后把 连续型随机变量协商纠错算法分为两部分的工作进行研究。第一部分是量化以及区间划 分,本文提出的量化方法,得到了一个很高的理想协商效率。第二部分是根据第一部分的 6 南京邮电大学硕士研究生论文第一苹绪论 量化思想,计算出最佳码率,然后用性能非常好的l d p c 长码去接近这个理想码率。发现 通过m o n t e c a r l o 仿真得到的码率和理想码率还是有比较大的出入,本文提出了用e x i t 图性能估计的方法,实现多级编码的分量码之间码率的合理选择,从而达到一个比较理想 的协商效率。最后是本论文的实验结果,并和比较成熟的s e c 算法的性能进行了比较,并 且利用已有的保密增强技术,对他们的密钥速率进行了估计和比较。 第五章总结了本论文所做的工作,对进一步的工作进行了展望。 7 南京邮咆大学硕士研究生论文 第二章信息理论基础 2 1 香农熵以及互信息 第二章信息理论基础 首先,我们介绍熵的概念,它是随机变量不确定度的度量。设x 是离散型随机变量, 取值空间为z ,概率密度函数p ( x ) = p r x - - x ,x z 。那么随机变量x 的香农熵定义为【2 2 】: 日( x ) = 一p ( x ) l o g ( x ) ( 2 - 1 ) x e z 设y 是取值空间为y 的随机变量,则在已知y 对于x 的条件熵定义为: h ( x l r ) = 一烈y 矽( z i 】r = 力( 2 - 2 ) y e , 互信息描述了两个集合之间,一个集合中事件出现后所给出的关于另一个集合中的事 件出现的信息量的平均值。关系式定义如下: j ;n = 胃( 幻一h ( x 1 1 0 = h ( d 一日( 】,f 柳 ( 2 - 3 ) 互信息的链式法则: ,五一t ;y ) = j ( 五;y lb ,五:,也) t = l ,阢,五,五;y ) = 日,五,五) 一日,五,鼍iy ) 矗 = h ( x t ix , 巾五中) 一y h i r i p 。l d p c 码的校验矩阵可用一个t a n n e r 图表示,对于( n ,k ) l d p c 码,t a n n e r 图将它的( n k ) x 以校验矩阵h 的每列看成一个变量节点,每一行看成一个校验节点,则 t a n n e r 图中总共有n 个变量节点和n k 一个校验节点。如果= 1 ,则表示校验节点q 与变 量节点y ,之间有一条边相连。例如( 1 0 ,5 ) l d p c 码也可表示为( 1 0 ,2 ,4 ) l d p c 码。 h = ( 2 - 9 ) 相应的t a n n e r 图如图2 1 所示。一般情况下,校验矩阵是随机构成的,因而是非系统化的。 在编码时对校验矩阵进行高斯消去,可得: 日= 【,p 】 ( 2 - 1 0 ) 生成矩阵为: l o o o 0 1 l 0 0 1 0 l 0 0 1 l 0 0 l 0 0 l 0 1 o 1 o o 1 l 0 0 l o 0 o l l o 0 1 o 1 0 l 0 0 1 1 o 0 0 南京邮电大学硕士研究生论文第二章信息理论基础 g = 【_ ,j c l c 2 c 3 c 4 c 5 v 1 1 ,2 v 3v 4v 51 6 v 7v 81 9 图2 - 1 ( 1 0 ,2 ,4 ) l d p c 分组码对应的t a n n e r 图 2 4 2 规则l d p c 码和非规则l d p c 码 、 、 疡 ( 2 - 1 1 ) 若l d p c 码的校验矩阵h ,每行( 或每列) “1 的个数相同,即t a n n e r 图的每个校验节 点c j ( 信息节点巧) 有相同个信息节点( 校验节点c j ) 和它相连,则校验矩阵h 所对应的 l d p c 码称为规则l d p c 码,否则为非规则l d p c 码。如上节所描述的( 1 0 ,2 ,4 ) l d p c 码 为规则l d p c 码,此时称校验节点的度为4 ,信息节点的度为2 。对于非规则l d p c 码, 则不能用这种形式表示,因为每个节点的度可能不相同,只能用普通的线性非组码的表达 方式表示。等式( 2 1 2 ) 校验矩阵蜀所对应的的l d p c 码可表示为( 1 0 ,5 ) l d p c 码,“5 一表 示信息长度,“l o 表示码字长度。对应的t a n n e r 如图2 2 所示: ? 6 7 1 ,l 马= 110oololol 011o 01o olo ooll0 01l01 0 0 0lll0 olo l00o1o1010 图2 - 2 ( 1 0 ,5 ) t l e 规则l d p c 分组码对应的t a n n e r 图 l l j 。j 巧口 ( 2 1 2 ) 塑室些皇奎堂堡主堡壅竺丝苎蔓三皇堕星堡丝茎型 对于非规则l d p c 码,相应的t a n n e r 图上的各个节点的度各不相同,通常用度分布序 列饥,y 2 ,乃,j 和惦,岛,魂j 表示,其中乃表示与度为j 的信息节点相连的边占总边的比 例,岛表示与度为i 的校验节点相连的边占总边的比例。西和4 分别表示信息节点和校验 d d - , 节点的最大度数,应有i 乃= 1 及肛= l 。边度分布序列可以用多项式来表示,即 7 ( 力:圭乃( 2 - 1 3 ) ,= l 以) :圭岛一 满足厂( 1 ) :圭厂,:1 及p ( 1 ) :圭岛:l 。 ,= l i - i ( 2 - 1 4 ) 图2 - 2 所示的l d p c 码可表示为7 ( 功= 0 8 x + o 2 x 2 和从曲= 0 6 x 3 + 0 4 x 4 。规则l d p c 码可以看成非规则l d p c 码得特例。设一个l d p c 码所对应的t a n n e r 图的总边数为e ,根 据边的度分布多项式,可以得到度为j 的信息节点的个数为屹= e y j j ,度为i 的校验节点 个数为吩= e p , i ,则信息节点和校验节点的总数为: - - d d l4lt 刀= 屹= j = e 7 ,j t l , 4 ,d , m - 芝u 1 _ 翰f = 哇p , i l 霉lj 罩ii = l 当校验矩满秩时,通过度分布多项式y ( 砷和p ( 力构造的非规则l d p c 码的码率为: 驯:竿小靼 n 艺y j f j 对于校验矩阵非满秩的情况,实际码率要比r ( p ,) 略高。 2 4 3l d p c 迭代译码算法 ( 2 - 1 5 ) ( 2 - 1 6 ) ( 2 1 7 ) 对于线性分组码,译码的复杂度随码长呈指数增长,传统的最大似然译码,对于l d p c 这样的长码来说,是很困难的或者说是不现实的。l d p c 码的各种译码算法都是由一种基 1 2 壹室坚! ! 奎兰堡主堑窒竺笙塞 墨三垩堕星堡笙墨型 于图的消息传播算法( m a s s a g ep a s s i n ga l g o r i t h m ) 演化而来,这种算法以二分图为基础。由 于在算法的运行过程中,有消息在二分图的两种节点之间来回传送,因此称其为m e s s a g e p a s s i n g 算法。该算法是工作在二分图中没有环的假设之上,否则的话,传递的消息不再相 互独立,此时算法的性能会有一定程度的损失。如果l d p c 码的译码算法中传递的消息是 消息节点的“可信度 ,则此时l d p c 码译码算法又称之为置信传播( b e l i e f p r o p a g a t i o n ,简 称b p ) 算法,在此主要简单介绍l d p c 码最基本的译码算法( 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 ) b p 算法。这是一种迭代概率译码方法,是l d p c 码特征之一,也是其性能优于的原因 之一。 b p 算法是以二分图为基础的一种迭代译码算法。在二分图不含有环时,b p 算法是一 种最优译码算法。但是,在码长有限时环是无法避免的,因此在有限码长情况下,b p 算法 是一种次最优算法。b p 算法的译码复杂度与码长是成线性关系的,并且在随着码长的增加, 其性能会逼近最大后验概率译码。 在实际运算中,为了减少计算中的乘法运算,在译码过程中引入对数似然比的概念, 关于对数似然比的概念在第二章中已有叙述。引入对数似然比后,b p 算法的计算步骤如下, 在此,k 为迭代次数。 第一步:计算m :,当k - o 时,表示由信道输出计算相应码元的对数似然比,然后将 对应码元v 的消息节点消息值赋予砖。k o 时,将第k - 1 次迭代过程中除了校验节点c 之 外所有与v 相连的校验节点传递的消息值与初始值相加赋予m :,计算公式为: 肌坩k = 肌一o k - 1 ( 2 - 1 8 ) c e - ,k 第二步:计算,砖。将除了v 之外所有与c 相连的消息节点的值经过计算后传给消息 节点v ,计算公式为: f ,1 + 兀t a n h 幻:! :。2 ) 砖乩l 希翻 l p 擘彤扣 ( 2 - 1 9 ) 第三步:判决。朋乏大于0 则判v 为0 ,小于。则判为l ,进而得到估计出码字,将 码字于与校验矩阵相乘,结果为全零序列时停止译码,否则,循环进行上述操作,直到得 到e 确的估计码字或者达到预先设定的迭代次数时停止。 上述算法中,l 小k 川卯k ) 代表第k 次迭代时消息( 校验) 节点传递给校验( 消息) 节点的消息 南京邮电大学硕士研究生论文第二章信息理论基础 值,c m c 表示除了校验节点c 之外与消息节点v 相连的其它校验节点,矿c 、,表示 : 。 除了消息节点v 之外与校验节点c 相连的消息节点。 2 5 基于e x i t 图的l d p c 码的性能估计和分析 译码收敛性是指收到的码字是否能够找到迭代方法接近正确码字,如果能够接近则说 明收敛,e x i t 曲线( e x t r i n s i ci n f o r m a t i o nt r a n s f e rc h a r t ) 是从互信息角度分析译码器的收敛 性【1 7 】。互信息可以充分反映译码器输入输出的相关性,它的特性:( 1 ) 互信息是最准确的统 计变量;( 2 ) 互信息也几乎是鲁棒性最好的统计变量,也就是说互信息不会随着信道、调制 解调器的变化而有很大的影响。因此采用互信息来观察密度进化过程,比采用其他参数跟 踪密度进化过程要简单而且准确。通过后面的分析可以看出e x i t 曲线图分析得到的译码 器阈值比高斯估计方法的性能更好。 2 5 1e x i t 图的原理和译码器模型 典型的信道编码模型如图2 3 所示,该信道为广义信道,其中信息序列m 经过编码器 输出为x ,再通过信道传输,输出为y ;通过译码器,判决输出为三。则它们有如下关系: y = x + 刀,其中n 为噪声,这里只考虑加性噪声模型

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论