（基础数学专业论文）基于golay码的信息协调协议.pdf

基于g o l a y 码的信息协调协议基础数学专业硕士研究生瞿云云指导教师包小敏教授摘要实现无条件安全的关键在于安全密钥协商协议的设计。密钥协商协议包括初始化，信息协调，保密增强三个阶段现在通常的做法是通信双方在初始化阶段通过使用有扰信道或量子信道得到初始错误率为加的串a 与b ，然后在公开认证信道上公开地交换信息进行信息协调与保密增强两个阶段，通信双方最后得到一个高度保密的密钥串，窃听方对此密钥串的信息几乎一无所知。通信双方把协商之后的安全的密钥作为双方共享的密钥使用一次一密体制进行保密通信。本文主要讨论信息理论安全密钥协商中信息协调阶段所用的纠错技术，基于( 2 4 ，1 2 )扩展g o l a y 码结合奇偶校验和提出了一种新的信息协调协议：( 2 4 ，1 2 ) 扩展g o l a y 码信息协调协议。对上述提出的协议做了相应的可行性分析与协议泄漏的信息量分析，详细地给出了一些数学表达式。理论与实验分析表明此协议具有一定的可行性，且在通信过程中所泄漏的信息鼍是比较小的。关键词：信息安全，有扰信道，量子信道，密钥协商，信息协调，g o l a y 码a b s t r a c ti n f o r m a t i o n t h e o r e t i c a l l ys e c u r es e c r e t k e ya g r e e m e n ti st h ek e yt om a k ep e r f e c ts e c l u j t y as e c r e t -k e ya g r e e m e n to v e rap u b l i cc h a n n e lu s u a l l yc o n s i s t so ft h r e ep h a s e s ，i n i t i a l i z a t i o n ，i n f o r m a t i o nr e c o n -c i l i a t i o na n dp r i v a c ya m p l i f i c a t i o n 。t h em o d e l so fu n c o n d i t i o n a ls e c u r i t yf r o mq u a n t u mc h a n n e l sa n dn o i s yc h a n n e l sa r et w ot y p i c a lm e t h o d st og e tt w os t r i n g sc a l l e daa n dbw h i c hh a v ee r r o rr a t ep oi nt h ei n i t i a l i z a t i o np h a s e ，t h e nt w op a r t i e sc a r r yo ni n f o r m a t i o nr e c o n c i l i a t i o na n dp r i v a c ya m p l i f i c a t i o nb ye x c h a n g i n gm e s s a g eo v e rap u b l i cc h a n n e l ，t w op a r t i e so b t a i nas e c r e tk e ya b o u tw h i c hw i r e t a p p e rk n o wn o t h i n gf i n a l l y o n c et h es e c r e t k e yh a sb e e na g r e e do v e rap u b l i cc h a n n e l ，o n ec a nu s et h ek e yt oe n c r y p tm e s s a g e sb yu s i n go n et i m ep a d e r r o rc o r r e c t i o nt e c h n i q u ew h i c hi su s e di ni n f o r m a t i o n -t h e o r e t i c a l l ys e c u r es e c r e t k e ya g r e e m e n ti sd i s c u s s e di nt h i st h e s i s t h em a i nw o r ki nt h i st h e s i si sa sf o l l o w s ：a ni n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o l ，c a l l e d ( 2 4 ，1 2 ) e x t e n dg o l a yc o d ei n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o l ，w h i c hi sb a s e do n ( 2 4 ，1 2 ) e x t e n dg o l a yc o d ea n dt h ee x c h a n g eo fp a r i t yi sp r e s e n t e d t h ec o r r e c t i o na b i l i t ya n di n f o r m a t i o nl e a k a g eo fg o l a yc o d ei n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o l sa r ea n a l y z e da n ds o m ee x p r e s s i o n sa t eg i v e ni nd e t a i l t h et h e o r ya n de x p e r i m e n tr e s u l t si n d i c a t et h a tt h e ( 2 4 ，1 2 ) e x t e n dg o l a yc o d ei n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o lh a sg o o df e a s i b i l i t ya n ds m a l l i n f o r m a t i o nl e a k a g e k e yw o r d s ：i n f o r m a t i o ns e c u r i t y , n o i s yc h a n n e l ，q u a n t u mc h a n n e l ，s e c r e t k e ya g r e e m e n t ,i n f o r m a t i o nr e c o n c i l i a t i o n ，g o l a yc o d e独创性声明学位论文题目：基于g o l a y 码的信息协调协议本人提交的学位论文是在导师指导下进行的研究工作及取得的研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁在文中做了明确说明并表示衷心感谢。学位论文作者：身皇幺讼签字日期：学位论文版权使用授权书年r 月叫日f本学位论文作者完全了解西南大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书，本论文：口不保密，口保密期限至年月止) 。学位论文作者签名：胃宴云云导师签名：，色小纹签字日萁i j ：砂1 年f 月叫日签字魄叩年p 胁日第1 章引言本章首先阐述密码学的发展历史以及密码学的分类，而后我们讨论与无条件安全即信息理论安全有关的概念：计算上安全与信息理论安全，然后介绍完善保密理论及模型，最后给出信息理论安全密钥协商的一般过程。1 1 密码学概述密码学是一门古老的学问，在古代就被广泛地用于军事上，而且在密码编码和密码分析上的优势有时候是取得战争胜利的关键因素。在新技术高速发展的当今社会，信息安全已经与人们的日常生活紧密的联系在一起。在信息的传输与处理的过程中，有关如何保护信息使之不被非法窃取或篡改，亦即信息的认证与保密问题，自然成为人们关注的问题。密码学的应用己经渗透到了社会的各个领域，如对计算机用户的认证、数据加密、网络安全、安全选举、不可追踪的电子现金等。1 9 4 9年，s h a n n o n 发表了一篇划时代的论文保密系统的通信理论i l l ，密码学才真正成为一门科学。在这篇文章中，s h a n n o n 首次用概率统计的观点对信息源、密钥源、接收和截获的密文进行数学描述和定量分析，提出了如图1 1 所示的通用的保密通信系统模型。通信双方a l i c e 和b o b 共享一个秘密钥。若发送方a l i c e 想秘密地给接收方b o b 一个明文信息，她利用秘密钥通过一定的加密规则将明文加密为密文后传给b o b ，b o b 利用所掌握的密钥信息恢复出明文。自然，窃听者e v e 也可能会获得该密文信息，但由于她不知a l i c e 和b o b 间的共享密钥，因而e v e 无法重构明文。在本论文中，我们总是假定通信的发方是a l i c e ，收方是b o b ，e v e 为窃听方( 可能是主动的窃听也可能是被动的窃听) 。1 9 7 6 年，w d i f f i e 与m e ，h e l l m a n 发表的开创性的论文密码学的新方向1 2 j以及1 9 7 7 年美国公布实施的数据加密标准( d e s ) 又把密码学的发展推向了一个崭新的阶段。在论文中他们首次提出了公钥密码体制( p u b l i ck e yc r y p t o s y s t e m ) 的西南大学硕士学位论文图1 1 ：s h a n n o n 的保密通信系统模型概念，虽然他们并没有构造出一个具体的公钥体制，但是他们基于有限域上的离散对数困难问题构造了一个非对称的密钥交换协议。在公钥密码体制的概念提出后不久，基于大整数分解问题的r s a 公钥体制【3 】和基于子集和问题的m e r k l e h e l l m a n背包公钥体制1 4 相继被提出。公钥密码体制在现在已经有很大发展，种类有所增加。比如基于有限域上离散对数困难问题的e 1 g a m a l 公钥密码体制1 5 1 ，基于椭圆曲线上的离散对数困难问题的椭圆曲线密码体制【6 1 ，基于有限域的乘法群子群的迹表示的x t r 密码体制m ( 其安全性也是基于有限域上离散对数困难问题) ，基于格( 1 a t t i c e ) 中困难问题的密码体制a i t a i d w o r k i 8 1 ，g g h l 9 i 和n t r u l 0 1 ，以及基于辫群( b r a i dg r o u p ) 的公钥体制i i l 】，基于纠错码的m c e l i e c e 公钥体制1 1 2 等。公钥密码学在文献i l ，l 有详尽而生动的讲解。密码学的其他分支也有很大的发展，如高级加密标准a e s 的设立等。可以在参考文献1 1 4 1 中找到流密码和分组密码的最新进展。流密码与分组密码加解密使用的密钥相同或者解密密钥很容易从加密密钥导出，因此流密码与分组密码统称为单钥密码、对称密码或者私钥密码；与之相对应，公钥密码体制也称为双钥密码或者非对称密码。各种密码体制的设计构成了密码编码学的内容，各种密码体制的分析则属于密码分析学研究的内容。密码编码总是想设计出更为安全的密码体制来，而密码分析学总是试图证明密码体制是不安全的甚至破解密码体制，密码编码学和密码分析学的发展是一个此消彼涨的过程。比如，第一个背包体制 4 l 刚设计出来不久，就被s h a m i r t 任】使用整数规划的方法破解掉了，随后各种各样的能够抵抗s h a m i r 攻击的背包体制相继被提出，然而更为有力的攻击工具一l 3 格基规约算法1 1 6 也被找到了，而l 3 格基规约算法对乘性背包无能为力【1 7 1 s l ，密码学其他方面比如数字签名、零知识证明等的发展历史可以参阅文献【1 9 2 0 1 。量子密码是密码学与量子力学相结合的产物，不同于以数学为基础的经典密码21 引言体制，其安全性由量子力学基本原理保证，与攻击者的计算能力无关。根据量子力学性质，窃听者对量子密码系统中的量子载体的窃听必然会对量子态引入干扰，于是被合法通信者所发现。合法通信者能够发现潜在的窃听，这是量子密码安全性的本质。因此，量子密码具有得天独厚的优势并逐渐成为密码新技术中的一个重要研究分支。研究和实验表明，量子密码很可能发展为下一代密码技术的重要力量。量子密码研究的内容有量子密钥分发( q k d ) 协议，如b b 8 4 协议【2 l 】，e 9 1 协议【2 1 等，量子密钥分发中的身份认证问题，取得了一系列成果忙3 4 , 2 5 。此后人们还研究了量子密码中的消息认证 2 6 1 和信道认证 2 7 1 的问题。自1 9 8 4 年第一个q k d 协议提出以来，量子密码已经逐渐成为各国学者们研究的热点问题。目前此领域在理论和实验方面都进展迅速。相信在不久的将来，量子保密通信系统定会走入我们的日常生活，这种“量子卫士”也将为我们的信息安全事业提供有力保障1 2 计算上安全与信息理论安全密码体制的设计是实现认证和保密通信的核心部分，因此，所使用的密码体制本身的安全性也势必对整个系统的安全产生重大影响。我们在讨论一个密码体制的安全性时总是要考虑到一定的时效性以及敌人的计算能力和计算资源，如果设计的和使用的密码体制可以确保在规定的时间( 加密数据应当保密的时间) 内不被破解，我们就可以认为该密码体制是安全的。因此，考虑密码体制的安全性是与破解该密码体制所需要的时间紧密相关的。有如下两个定义：定义1 如果一个密码体制即使在敌人拥有无限的计算资源和计算能力的情况下仍然不能被破解，就称该密码体制是无条件安全的。定义2 计算上的安全性考虑的是用当前已知的最好的方法来攻击一个密码系统所需要的计算量，它依赖于攻击者的计算能力，如果敌手破译算法所需的时间超过了加密数据应当保密的时间，就称该密码系统在计算上是安全的。根据密码体制的安全机制可以把密码体制分为计算上安全的和无条件安全的。计算安全模型和无条件安全模型 2 0 1 是目前密码学领域所使用的两个安全模型。计算安全模型所使用的数学工具是复杂性理论，而无条件安全模型所使用的数学工具是概率论和信息论，因此，无条件安全也称信息理论安全。信息理论安全优于计算上安全的一点就是信息理论安全是可以证明安全的。而所有基于计算上安全的密码西南大学硕上学位论文体制都没有被证明是安全的。几乎所有的密码体制包括概率加密的公钥密码体制如e i g a m a l t 5 】和n t r u t 蛐1 都是计算上安全的。目前所知道的能够实现无条件安全的密码体制只有一次一密密码体制t t l 。从理论上讲，如果允许对整个密钥空间穷举搜索的话，那么所有的计算上安全的密码体制都会被攻破。根据现在的计算资源和计算能力，虽然破解这些基于计算上安全的密码体制可能需要几个月乃至几百年的时间。但是，在科技快速发展的信息时代，具有超强计算能力的量子计算机或d n a计算机在不远的将来就可能实用化，到那时，建立在计算安全模型上的密码系统就没有了安全性可言。因此，计算上安全的密码体制就永远面临着被攻破的危险，这也必然刺激我们去寻找能够实现无条件安全的而且实用的密码体制。1 3s h a n n o n 熵、条件熵、互信息s h a n n o n 熵是对随机变量的不确定性的度量，也是随机变量取各个可能值后所显示的信息的平均度量。其定义如下：定义3 设x 为取值于集合x 的一个随机变量，概率分布为段，则x 的s h a n n o n熵定义为日( x ) = 一p x ( x ) l o g p x ( x )设y 为取值于集合v 的一个随机变量，则在y 的条件下x 的s h a n n o n 熵定义为日( x i y ) = p y ( y ) h ( x i y = 秽)y c y其中h ( x i y = y ) = 一xp ( x y ) l o g p ( x l y ) 。定义4 设x 为取值于集合x 的一个随机变量，概率分布为取，y 为取值于集合v 的一个随机变量，概率分布为p y 两者的联合概率分布为p x y ，则x 和y 问的互信息定义为，( x ；y ) = z 可取y ( x y ) 1 0 9 错互信息描述了两个集合之间，一个集合中事件出现后所给出的关于另一个集合中的事件出现的信息量的平均值。有关系式，( x ；y ) = h ( x ) 一h ( x i y ) = h ( y ) 一h ( y i x ) 1 4 完善保密理论及模型介绍信息论的奠基人s h a n n o n 给出了完善保密的定义：单钥体制称为完善保密的，41 引言如果h ( m ) = h ( m i c ) 即明文m 和密文c 是统计独立的，密文不能给出明文的任何信息。在抗击惟密文攻击中，完善保密与无条件安全是等价的。因此无条件安全又称为信息理论安全。在完善保密的密码系统中，不管敌手使用多长的时间以及有多大的运算能力，他采用任何破译方法都不比未知密文的情况下对明文进行随机猜测强。s h a n n o n 在提出完善保密理论的同时证明了完善保密体制是存在的，在任何一个完善保密系统中密钥长度应至少与所加密的明文长度一样长f | l 。典型的一个例子就是一次一密密码体制，它要求密钥必须以完全随机的方式产生，并通过安全的途径送给通信对方，每次用过后的密钥都立即销毁。近几年来，无条件安全理论有了很大进步，提出了许多无条件安全模型。即使敌手能够得到的信息比合法用户多，合法用户也能通过密钥协商实现共享秘密钥。目前所提出的最典型的两个实现方法就是利用有扰信道和利用量子信道的方法。1 4 1 有扰信道模型m a u r e r 提出的一个比较实际的模型一卫星广播信道模型( 如图1 2 所示) ：卫星以低的信噪比不断地向地面发送信号，a l i c e ，b o b 和敌手e v e 分别用不同的接收天线接收卫星发送的信号，由于天线是不完善的，故一定会有噪声，三者分别以错误率m ，船，阳得到三个随机变量x ，z ，五kz 服从联合概率分布e x y z 。此外，a l i c e和b o b 间还存在一个不安全但具有认证功能的公共信道。双方可以在该公共信道进行协调，最后得到双方共知的秘密钥。图1 2 ：m a u r e r 的卫星广播信道模型西南大学硕上学位论文1 4 2 量子信道模型与量子密码量子密码主要是由w i e s n e r 提出，在8 0 年代由b e n n e a 和b r a s s a r d 发展起来的f 2 s , 2 9 1 。它主要是通过光子( 更精确地说是低密度的光子束) 在光纤上的传输来实现的。在量子世界中，依据h e i s e n b e r g 的测不准原理，有一些物理性质是不相容的。测量其中一个性质，会使另一个性质的测量值变得随机。例如，测量某个光子的线偏振会使圆偏振的测量结果随机。从传统密码学和信息理论角度来看，窃听者在通信双方没有意识到的情况下进行窃听是不足为奇的。但是在量子信道中，数字信息编码为光子的偏振态，窃听者如果对所传输的信息进行窃听时，会不可避免地引起量子信道上的随机干扰。b b 8 4 量子密钥分配协议【2 l ，3 0 , 3 - 1 的基本思想如下：量子传输中仅有四种不同的方式来传输对应的o 度，4 5 度，9 0 度，1 3 5 度四种偏振方向的光子，这四种偏振态可分别表示为i 一) ，i ) ，j 下) ，l ) 时，对应的两种测量基矢：r e c t i l i n e a r( 1 一) ，i t ) ) 和d i a g o n a li ) ，i ) 分别表示为e 和o 。如果a l i c e 想通过量子信道向b o b 发送b 0 ，1 1 ，她对b 进行如下的编码：( 1 ) b = 0 随机编码为i 一) ，i )( 2 ) b = l 随机编码为m ，i ) 在接收端，b o b 选择是用：r e c t i l i n e a r 测量基( 亩) 或者d i a g o n a l 测量基( o ) 对收到的极化光子测量。如果光子6 是a l i c e 对信息比特b 用r e c t i l i n e a r 测量基的编码且接收者b o b 用r e c t i l i n e a r 测量基对光子6 测量，则他可以得到6 ；如果用d i a g o n a l 测量基测量光子6 ，则他接收到的是0 或l 。现在的量子密钥分配协议已经可以在水下2 0 3 0 公里内实现m 】，在自由空间也可以在5 8 公里内实现 s 1 。1 4 3 信息理论安全密钥协商的一般过程在公开意义下的无条件安全秘密钥协商是b e n n e t t ，b r a s s a r d 和r o b e r t 在文献f 3 4 , 3 5 1 中提出的，由a h l s w e d e 和c s i s z a r 及m a u r e r 推广【蚓，而m a u r e r 对此引入了一个广义的信息理论模型，现描述如下：a l i c e 和b o b 间由公开信道相连接，第三方e v e 可以窃听该信道中所传递的信息，但不能对信息进行篡改，且在公开信道上可以进行身份认证。信息理论安全密钥协商的一般过程如下：6( 1 ) 初始化阶段：m i c e ，b o b 及窃听方e v e 分别通过有扰信道或量子信道接收到三个随机变量x ，y 及z 作为初始信息，x ，y 及z 服从联合概率分布艮y z 。( 2 ) 通信阶段：( a ) 优先提取( a d v a n t a g ed i s t i l l a t i o n ) ”1 ：当a l i c e 和b o b 都不优先于e v e ，即：如果，( x ；y ) 、，( x ；z ) 和，( x ；y ) j ( y ；z ) 均不成立，优先提取才有必要m i c e 和b o b 通过交换信息( 记作随机变量c ) ，a l i c e 从x 和c 中得到一个新的随机变量a ，同样，b o b 根据y 和c 可以获得一个新的随机变量b ，而且b o b 对a 的不确定性小于e v e 对a 的不确定性，即：h ( a i x c ) = 0 且h ( a i y c l ，( x ；z ) 或( x ；y ) ，( y ；z ) ，则无须优先提取，直接令a = x ，b = y ( b ) 信息协调( i n f o r m a t i o nr e c o n c i l i a t i o n ) 1 2 8 , m 3 8 1 信息协调就是通信双方a l i c e和b o b 通过公开信道交换冗余信息从而消除他们的随机变量中不一致的比特的过程。把冗余信息记作y ，y 的长度为厶，m i c e 和b o b 分别根据y 以及在优先提取阶段所获取的随机变量a 和b 协商出一个共同的比特串s ，在信息协调阶段还必须使e v e 对比特串s 仍然有一定程度的不确定性，即使得h ( s i y c v ) o , h ( s i z c v ) h ( s i z c ) 一三 0 。( c ) 保密增强( p r i v a c ya m p l i f i c a t i o n ) ：在保密增强阶段，m i c e 和b o b 从一个部分保密的比特串s 产生一个高度保密的比特串k ，而且使e v e 对比特串k几乎一无所知。可以通过选取合适的杂凑函数( ( h a s hf u n c t i o n ) 来实现保密增强，m i c e 选定一个h a s h 函数g 并通过公开信道把它发送给b o b 。通信双方计算k = g ( s ) 并把k 作为协商出来的共享密钥，此时e v e 对比特串k 几乎一无所知。( 3 ) 决策阶段：如果m i c e 和b o b 觉得k 可以作为共享的密钥，则他们就接受密钥协商协议执行的结果，否则，他们就丢弃k 并且重新进行密钥协商注1 如果通信双方使用量子信道进行密钥协商的话，则优先提取不是必需的。假设a l i c e 和b o b 都接收卫星发射的低功率信号( 发射低功率信号的目的是使接收者所接收的信号总存在错误比特) ，在优先提取阶段之后，通信双方得到初始7西南大学硕上学位论文错误率为p o 的串a 与b ，或采用量子密钥分配协议得到初始错误率为m 的串a与b 。利用公开信道通过公开讨论来纠正b 中相对于a 中错误比特的全过程称为信息协调( r e c o n c i l i a t i o n ) 。目前已经有一些信息协调协议，例如利用奇偶校验和的c a s c a d e 协议 3 8 1 与b i n a r y 协议 3 9 1 ，利用汉明码的w i n n o w 协议1 4 0 l 等等本文主要讨论信息理论安全密钥协商中信息协调所用的纠错技术，基于( 2 4 ，1 2 ) 扩展g o l a y码结合奇偶校验和提出了一种新的信息协调协议：( 2 4 ，1 2 ) 扩展g o l a y 码信息协调协议。对上述提出的协议做了相应的可行性与协议泄漏的信息量分析，详细地给出了一些数学表达式。理论与实验分析表明此协议具有一定的可行性，且在通信过程中所泄漏的信息量是比较小的。1 5 本文内容及安排第二章介绍了现有的信息协调协议，包含二分法，比特对校验协议，汉明码信息协调协议。第三章介绍了线性码的相关知识，介绍了( 2 3 ，1 2 ) g o l a y 码与( 2 4 ，1 2 ) 扩展g o l a y码，最后给出了g o l a y 码与组合数学中的设计，代数中的群的关系。第四章基于( 2 4 ，1 2 ) 扩展g o l a y 码结合奇偶校验和提出了一种新的信息协调协议，对协议的可行性与泄漏的信息量做了分析。第2 章现有的信息协调协议介绍目前已经有一些信息协调协议，有利用奇偶校验和的二分法与c a s c a d e 协议。利用汉明码的w i n n o w 协议等，下面介绍三种协议。2 1 二分法二分法1 2 8 1 纠错原理如下：设发送方a l i c e 与接收方b o b 留下的数据串的长度为n ，预计的误码率为g 按以下步骤进行信息协调。( 1 ) a l i c e 与b o b 按同一随机序列将它们的数据的位置重新编排。这样做的目的是使错误均匀地随机分布。( 2 ) 将数据分组，每组长度为k ，每组含有的错误个数平均应小于或等于1 ( 3 ) a l i c e 与b o b 各自检测每组数据的奇偶性并通过公开信道进行比较。若对应的数组彼此奇偶性不同，表示该组有错误。错误的个数是奇数。将这样的数组一分为二，再进行奇偶检测及比较。如是地继续进行至最后一个数位，这数位就是错误数位。为了确保不让e v e ( 窃听者) 获得新信息，每公开披露一次数组的奇偶性，就将该数组最后的数位舍弃，被发现的错误数位当然也被舍弃。( 4 ) 经过上一轮的纠错后，各数组的奇偶性虽然相同但仍有可能存在偶数个错误，需重复步骤( 1 ) ，( 2 ) ，( 3 ) 进行新一轮的纠错。进行了数轮如上的纠错后，如果认为留下的错误概率已较低，例如接近1 ，可进行下一步骤。( 5 ) 这一步的目的是确认不存在错误。从余下的数据中随机地取出一个子集，对所取的子集进行奇偶性比较。如果a l i c e 与b o b 的数据完全相同( 没有错误) ，则彼此的子集的奇偶性必定相同。奇偶性相同仍有可能存在错误，有错误检验不出来的概率小于0 5 因为选取的子集含有奇数个或偶数个( 包括0 ) 错误的概率均为0 5 若出现奇偶性不同，即进行步骤( 3 ) 的纠错。如果奇偶性都相同，认西南大学硕上学化论文为a l i c e 与b o b 的数据完全相同( 没有错误) 2 2c a s c a d e 级联纠错c a s c a d e 协议1 3 5 1 描述如下，其中a 表示发送方a l i c e ，b 表示方接收方b o b ：( 1 ) 设待纠错的数据长度为仡，预测误码率为g 。将全部数据随机重新排列，目的是使错误尽可能均匀地分布。记下每个数据的编号，例如，a f 代表a 拥有的顺序为2 的数据，岛代表b 拥有的顺序为z 的数据，f 1 ，n ) 然后将数据分组，每组数据长度为k l ，共分为罟组，k 1 的大小决定于误码率g ，务求每组含有的错误即a l b t 不多于1 个，如可取去 k 1 二1 分作第一组的记为研，第v 组记作秘。上标表示第一轮分组，下标表示该轮中数组的序号。在数组之内，每个数据的标记仍采用未分组前的序号。例如，在数组k 内数据顺序为 1 ，2 ，k t ，在碹中数据顺序为【七l + 1 ，h + 2 ，2 忌1 ) ，在磁中数据位置j 顿序为 z l ( v 一1 ) k l f v k l ， 1 ，晋)( 2 ) a 计算各数组的奇偶性并通过公开信道告知b b 将a 的结果与自己的比较。当出现彼此奇偶性不一致时利用二分法进行纠错。与二分法不同的是不舍弃任何数据。经过这一轮分组纠错后，所有的k 1 ( u l ，卺 - ) 只存在偶数个错误。( 3 ) 进行第二轮分组纠错。在第二轮分组，每数组的长度取为也，如k 2 = 2 k 1 ，利用随机函数厶： 1 扎】_ 【1 n k 2 l ，将佗个数据分为石 t l ，以霹表示第二轮分组后顺序为j 的数组。在数组i q 内数据的位置是 z l a ( 1 ) = 歹) 这里f 是第一轮步骤( 1 ) 已确定的编号。凡满足a ( z ) = j 的编入第二轮第j 组，z 在组内由小到大顺序排序。分组后，对各组进行奇偶性检验及比较，遇到a 与b 彼此奇偶性不一致的，即进行二分法改错。若在k ；内发现错误，它的编号为f ，立即可以断定，在第一轮的分组中含有数据编号z 的数组刚内一定还存在另外的奇数个错误。对于这些数组可以再使用二分法纠错，如是者，被发现及纠正的错误个数倍增，直至不能再发现新错误，第二轮纠错结束。这时第一轮及第二轮的所有数组，即任一霹( u 1 ，昔) ) 及瑶( u l ，薏) ) ，仍然可能含有偶数个错误，需进行第三轮或更多轮纠错。( 4 ) 重复进行步骤( 3 ) 的分组纠错，在第i 轮中( t 1 ) 分组纠错中，采用随机函数1 02 现有的信息协调协议介绍五：【1 叫_ 【1 礼】将扎个数据分为芒个数组，每组长度为觑在数组蟛内数据的位置是 l l f , ( 1 ) = 歹) 。a 与b 进行奇偶性比较发现奇偶性不一致立即进行二分法纠错。与二分法不同的，不舍弃任何数据。凡在翮中发现序号为z 的错误，经纠错后必定可在含有数据序号2 的数组蟛( 1 u 2 ，若错误只有一个，该组数据就成功地纠正了错误，使奶= n 口。若存在3 个或更多的错误则不能确定错误是减少还是增加。改错后a l i c e 及b o b 都应舍弃2 个数据，以维持数据的保密性。被舍弃的数据的位置是 2 ) 0 0 ，1 ，2 ，f 一1 ) 这些位置对应于奇偶校验矩阵的2 j 列，这些列均只含有一个不为0 的矩阵元，它们的耦合作用最小。( 5 ) 进行下一轮改错，重复上述的步骤( 1 ) ，( 2 ) ，( 3 ) ，( 4 ) ，直至不能发现任何错误为止。上述的汉明码信息协调协议称作w i n n o wp r o t o c 0 1 第3 章g o l a y 码的相关知识3 1 线性码的伴随式译码3 1 1 线性码的生成和一致校验矩阵定义5 b 上的一个( n ，k ) 线性码，是n 维矢量空间k ( 岛) = 1 ( z l ，x n ) lz t 日，i = 1 ，扎)的一个k 维子空间，n 称为码的长度，k 称为维数。码的速率是比值鲁，其中是包含q 个元素的有限域一。i定义6 令c 是b 上的一个( 礼，k ) 线性码。一个行空间等于c 的七x 礼阶矩阵g 称为c 的生成矩阵。相反，如果g 是元素取自最的一个矩阵，则它的行空间称为由g 生成的码。如果c 是日上的一个( n ，k ) 线性码，则c 的一致校验是一个具有下面形式的等式：a l x l + a 2 x 2 + + a n x ，l = 0( 3 1 )它对所有的x = ( x l ，x 2 ，x n ) c 都成立。对于任意z c ，使式3 1 成立的所有矢量a = ( a l ，a n ) 的集合，本身也是k ( f q ) 的一个子集。将它记做c 上( c 的正交) ，并称之为c 的对偶码。根据线性代数中的有关结论，c 上的维数是n d i m ( c ) ，即c 上是上的一个( 扎，礼一k ) 线性码。定义c 的一个一致校验矩阵为c 上的一个生成矩阵。更直接地：定义7 令c 是局上的一个( 礼，k ) 线性码。如果当且仅当x c 时，矩阵h 具有性质h x r = 0 。则称矩阵日为码c 的一致校验矩阵。西南大学硕士学位论文印11100 )耻1 。1 )1 43 g o l a y 码的相关知识对于这个信道，很容易区分互相竞争的错误图案，因为如果z k ( 日) ，则p z = z ) = 【1 一( g 一1 ) e n - w g ( 。) 叫日( 。( 3 2 )其中w n ( z ) 为z 的汉明重量，被定义为z 中非零分量的个数，或者说，w 日z )是z 中出现错误的个数。如果；1 ，( 3 2 ) 就是w h ( z ) 的减函数，因此最有可能的z 就是具有最小重量的名伴随式译码算法的步骤如下：( 1 ) 计算伴随式8 = h y r( 2 ) 在对应的s 的陪集中找出最小重量矢量，称它为z o( 3 ) 输出码字c = y z o这个算法的步骤2 工作量巨大，如果k 和礼一k 的值都相对较小，就可以通过查表的方法实现步骤2 ，下面就介绍这种方法。再一次考虑码c 。，前面给出它的一致校验矩阵为：耻10 00 )在这个例子中有四个可能的伴随式：o o ，0 1 ，1 0 ，1 1 将3 2 个矢量z = ( z 1 ，z 2 ，z 3 ，z 4 ，z 5 )依照它们的伴随式进行分类，将它们排列在一个4x8 阶矩阵中，矩阵的元素都属于k ( 易) ，这样的排列称为标准阵列。标准阵列的行是c 1 的陪集；例如，第一行就是码本身在每个陪集中具有最小重量的一个矢量被列在最前面，称为陪集首一般说来，除码本身以外，陪集中的每个元素等于它的陪集首加上写在它上面的那个码字。c 1 的标准阵列：伴随式陪集首0 00 0 0 0 00 0 0 1 l0 0 1 0 10 0 l l o1 l o o l1 1 0 1 01 1 1 0 01 1 1 1 10 10 0 1 0 0o o l l l0 0 0 0 10 0 0 1 01 1 1 0 1儿1 1 0 1 1 0 0 01 1 0 1 11 00 1 0 0 00 1 0 1 10 1 1 0 1 0 1 1 1 01 0 0 0 l1 0 0 1 01 0 1 0 01 0 1 1 l“1 0 0 0 01 0 0 1 11 0 1 0 11 0 1 1 00 1 0 0 l 0 1 0 1 00 1 1 0 00 1 1 1 l给出标准阵列后，就很容易实现伴随式译码器中的三步算法中的第二步：在传输前先建立一个表，它包含所有的( 8 ，z ( s ) ) 对，其中s 是矿山个可能伴随式中的一个，而z ( s ) 是伴随式8 的陪集首。这样步骤2 就简化为：2 令z 0 = z ( 8 )1 5西南大学硕士学位论文如果这种方法是可行的( 即对应于q n 一矗个伴随式中的每一个伴随式，如果能够预先计算和存储它的陪集首) ，那么相应的译码算法就是已知最快的一种译码算法。如果定义两个矢量z 与y 之间的汉明距离如下：d h ( x ，y ) = w 日 z ) = 分量翰y i 的个数，矢量空间k ( 目) 就可以变为度量空间。定义码c 的最小距离为：d m i n ( c ) = m i n d 日( z ；z ) ：z ，x c ，z z 7 】定理1 码c = z 1 ，z 2 ，z m ) 能够纠正所有重量e 的错误图案，当且仅当d m i n ( c ) 2 e + 1 定理1 的证明参见文献 4 2 1 中第1 1 2 页现在将这些结论，应用于线性码这种情况，首先观察到，因为d h ( x ，z ) = w h ( z z ，) ，又因为如果c 是线性码( 且z z ) ，则z z 7 一定是c 的一个非零码字，所以线性码的最小距离与它的最小重量w m i n ( c )相等，其中 t g m i 。( c ) = d n 伽h ( z ) ：z c ，z o 因此，要计算( 礼，k ) 线性码的d m i n ，只需计算矿一1 个重量w 日( z ) ( z 0 ) 就足够了。3 2 循环码的相关知识定义8 对于域f 上的一个( 礼，k ) 线性码，如果每个码字c = ( c o ，c 1 ，g 一1 ) 的右循环移位，即c r = ( g 一1 ，g ，g 一2 ) ，也是一个码字，那么就称这个码为循环码。如果c = ( 岛，g ，g 一1 ) 是一个码字，那么它的生成函数定义为多项式：c ( x ) = g + a z + + g l 护一1其中z 是一个未知数。生成函数的作用在于，通过利用它，可以给出码字右循环移位的一个简单代数描述。为了给出这一描述，需要定义整数和多项式运算的一个重要的r o o d 算符。定义9 如果p 和m 是整数且m 0 ，则pr o o dm 表示p 除以m 得到的余数，因此pr o o dm 等于一个能使p r 被m 整除且0 r ( m 一1 ) 的整数r ，类似地，如果p ( z ) 和m ( x ) 是多项式，则p ( x ) r o o dm ( x ) 表示p ( z ) 除以m ( x ) 的余式；因此1 63 g o l a y 码的相关知识p ( z ) r o o dm ( x ) 等于惟一能使p ( x ) - n ( x ) 被m ( x ) 整除，且d e g 冗( z ) d e gm ( x )的多项式r ( z ) 定理2 如果c = ( c o ，a ，g 一1 ) 是一个码字，其生成函数为c ( z ) = c o + g z + + g 一1 z n 一1则右循环移位c n 的生成函数c 兄( z ) 可以由下面的公式给出：c r ( z ) = x c ( z ) r o o d ( 护一1 )证明因为c ( z ) = c o + q + + g l x n ，所以有x c ( z ) = c o x + + c k 一2 x n 一1 + ( _ 一1 x nc r ( z ) = c k 一1 - 4 - c o x - f + c k 一2 z n 一1因此z c ( z ) 一c r ( z ) = c k 一1 ( z 仃一1 ) 因为d e gc r ( z ) d e g ( x n 一1 ) ，且z c ( z ) 一c r ( z )是矿一1 的倍数，所以根据m o d 运算的定义可以得出结论。口一个( n ，k ) 线性码看成是一个次数不超过n 一1 的多项式的集合，码中多项式的任意线性组合还在码中。从这个观点来看根据定理2 ，循环码是一类线性码，如果c ( z ) 是一个码字，那么x c ( x ) r o o d ( x n 一1 ) 也是个码字。可以把这个结果推广为，对于任意多项式p ) ，p ) e ) r o o d ( x n 一1 ) 也是c 中的一个码字。定义l o 如果c 是一个循环码，那么c 中的一个最低次非零多项式被称为它的一个生成多项式。通常用符号夕( z ) 表示生成多项式。定理3 关于循环码，有以下结论?如果c 是f 上的一个( 佗，k ) 循环码，则它的生成多项式g ( x ) 是x “一1 的一个因式。而矢量c = ( c o ，g ，g 一1 ) 属于该码，当且仅当它所对应的生成函数c ( z ) = c o + c , x + + g 一1 z n 一1 能够被夕 ) 整除。如果用k 表示c 的维数，则k = n d e g g ( = ) 反之，如果夕( z ) 是z n 一1 的一个因式，则存在一个以9 ) 为生成多项式，且k = n d e g g ( x ) 的( 礼，k ) 循环码，该码中所有矢量( g ，g ，g 1 ) 的生成函数都能够被夕( z ) 整除。1 7) = 藉拈3 3g o l a y 码介绍3 3 1 二进制( 2 3 ，1 2 ) g o l a y 码在g f ( 2 ) 上的2 3 维矢量空间3 中，一个半径为3 的汉明球体内含有1 + 谚3 + c 磊+ = 2 0 4 8 = 2 0 4 8 = 2 1 1个矢量，能用4 0 9 6 = 2 1 2 个半径为3 的球体完全填满3 ，且相互之间没有重叠，球体的中心能组成个二进制( 2 3 ，1 2 ) 码，它包含2 1 2 个码长为2 3 的码字，能够纠正任1 83 g o l a y 码的相关知识意重量3 的错误图案具有上述性质的码属于一类非常特殊的码，即完备码。因为2 1 1 一l = 2 0 4 7 = 2 3 8 9 ，所以g f ( 2 1 1 ) 一定含有一个2 3 阶本原单位根，我们称之为p p 在g f ( 2 ) 上的最小多项式为g ( x ) = 兀1 b ( z 一，y ) ，其中b = p 2 。：i = 0 ，1 ，2 ，)是p 的共轭类的集合。通过简单的计算可以证明b 仅含1 1 个元素；实际上，夕( 尘) = i i ( z 一7 ) f e b其中，b = ( 矽：j = 1 ，2 ，4 ，8 ，1 6 ，9 ，1 8 ，1 3 ，3 ，6 ，1 2 同理，p 一1 = p 2 2 的最小多项式为：夕7 ( z ) = ( z 一，y ) f e b 7其中，b = 伊：j = 2 2 ，2 1 ，1 9 ，1 5 ，7 ，1 4 ，5 ，1 0 ，2 0 ，1 7 ，1 1 因为除了1 以外，每个2 3 阶单位根都是9 ( z ) 或9 7 ) 的一个零点，所以在g f ( 2 1 上将。2 3 1 分解为不可约因式：x 2 3 1 = ( z 一1 ) g ( x ) g ( z )( 3 3 )实际上，可以证明【4