（信号与信息处理专业论文）编码与密码中的若干问题研究.pdf

北京邮电人学博1 学位论文 摘要 摘要 密码学是一门研究通信安全和保护信息资源的既古老而又年青的科学和技 术。它包括两方面：密码编码学和密码分析学。密码编码学是对信息编码以隐蔽 信息的一门学问：而密码分析学是研究分析破译密码的学问。这二者既相互对立 又相互促进，共同推动密码学的发展。 纠错编码是提高通信质量或可靠性的一门年青的学科。自1 9 4 8 年s h a n n o n 提出信道编码定理至今，这门学科已取得了丰硕的成果。利用纠错编码的差错控 制技术，已成为通信系统设计中一种重要、在某些场合甚至是必不可少的技术手 段，纠错编译码器已成为现代通信系统中的重要组成部分。 纠错编码和密码学可以说是信息科学领域中的一对孪生兄弟。纠错编码的任 务是通过增加消息多余度的办法排除在噪声信道下传输消息时所带来的干扰，从 而使接收端能够纠正错误，正确译码。与此相反，密码学的任务则是人为地在要 传输的消息中加入“噪声”，使其变成窃听者难以解读的消息，而合法的接收端 可通过“密钥”将消息正确解密。 本文对纠错编码与密码技术应用进行了深入研究，主要成果及创新体现在以 下几个方面： 1 提出了p ”的一种分圆法，并利用此分圆法构造了所有码长为p 的二元 d u a d i c 码，同时也给出了这种码的计数。d u a d i c 码是一类性能优良的二 元循环码，它真包含二次剩余码( q r 码) ，与q r 码有非常相似的性质， 一些d u a d i e 码甚至具有比q r 码更好的性质。例如，d u a d i c 码 ( 1 1 3 ，5 7 ，1 8 ) ，( 1 5 1 ，7 6 ，2 3 ) ，( 2 3 3 ，1 1 7 ，3 2 ) 都比相同码长的q r 码达到更大的 最小重量。 2 给出了码长为任意长度的二元d u a d i c 码的构造方法与计数，并且给出了 不等价的d u a d i c 码的计数。d u a d i c 码的构造方法和计数，以及不等价的 d u a d i c 码的计数一直是d u a d i c 码研究中的公开问题。本文提出了一种新 的码构造方法，首次解决了这三个问题。 北京邮l 匕大学博l ：学位论文摘簋 3 对一类m d s 阵列码的纠错译码算法进行了改进。阵列码在通讯和存储 系统中都有非常重要的应用，近年来得到了广泛的研究。阵列码是线性 码，与常见的线性码不同，它并不是把信息位和校验位放在一维的向量 中，而是放在二维的阵列中。改进的译码算法能在一定条件下直接定位 到发生误码的位置，然后只需将该位置的比特值取反，就实现了纠错译 码。与原算法中先对校验子进行对偶码的编码，再进行码字重建等复杂 运算相比，改进的算法效率大大提高。 4 如何撤消证书一直是公开密钥基础设施( p u b l i ck e yi n f r a s t r u c t u r e ，p k i ) 研究和应用中的一个难点问题。本文对目前研究和应用中的证书撤消机 制进行深入全面的研究，详细描述了各种机制的工作原理，并对各种机 制的优缺点进行了详细剖析。在此基础上，对在线证书状态协议( o n l i n e c e r t i f i c a t es t a t u sp r o t o c o l ，o c s p ) 进行了改进以提高效率，并对基于该 协议的证书应用提出了新的实现模型。 5 在对p k i 信任模式进行分析比较的基础上，提出了各p k i 信任域如何实 现信任域扩展的方案和技术实现。p k i 的基本任务就是要在开放的网络 中建立并维护一种令人可以信任的环境和机制，但是，不同的p k i 域产 生不同的彼此信任的用户群体，形成了各自不同的封闭型的信任环境。 如何安全地、经济地、可靠地实现p k i 信任域间的交叉认证，对p k i 的 进一步发展和应用将起到非常重要的作用。 北京邮l u 人学博f ：学位论文a b s t r a c t a b s t r a c t c r y p t o l o g y i sa n a g e o l d a n df r e s hs c i e n c ea n d t e c h n o l o g y o n s t u d y i n g c o m m u n i c a t i o n s e c u r i t y a n di n f o r m a t i o n p r o t e c t i o n i te n c o m p a s s e s b o t h c r y p t o g r a p h y a n dc r y p t a n a l y s i s c r y p t o g r a p h yi st h ea no f s e c r e t i n gi n f o r m a t i o n a n d c r y p t a n a l y s i s i st h ea r to fb r e a k i n g c r y p t o s y s t e m s t h e y a r et w o o p p o s i t eb u t i n t e r a c t i o n a ls c i e n c e s ，a n da c c e l e r a t et h ed e v e l o p m e n t o f c r y p t o l o g yt o g e t h e r e r r o r - c o r r e c t i n gc o d i n gi saf r e s hs t u d yo np r o m o t i n gc o m m u n i c a t i o n a lq u a l i t y a n dr e l i a b i l i t y i th a sa c q u i r e dan u m b e ro fa c h i e v e m e n t ss i n c es h a n n o np r e s e n t e d c h a n n e lc o d i n gt h e o r e mi n1 9 4 8 t h ea p p l i c a t i o no fe r r o r - c o r r e c t i n gc o d e sh a s b e c o m ea ni m p o r t a n ta n dn e c e s s a r yt e c h n o l o g yi nd e s i g n sf o rc o m m u n i c a t i o ns y s t e m s a n dt h e e r r o r - c o r r e c t i n gc o d i n gd e v i c e i s a l w a y sam a i nc o m p o n e n to fm o d e m c o m m u n i c a i i o n s y s t e m s i nf a c t ，e r r o r - c o r r e c t i n gc o d i n ga n dc r y p t o l o g ym a yb es e e nt w i nb r o t h e r s t h e f u n c t i o no fe r r o r - c o r r e c t i n gc o d i n gi sd e c r e a s i n gn o i s ei nn o i s ec h a n n e l sb ya d d i n g i n f o r m a t i o nr e d u n d a n c y h o w e v e r , t h et a s ko fc r y p t o l o g yi s a d d i n g n o i s e t o m e s s a g et r a n s f e r r e d ，s oa st op r e v e n t i n gl i s t e n e r - i nf r o ma c q u i r i n g t r u ei n f o r m a t i o n t h i sd i s s e r t a t i o nm a k e sr e s e a r c h e so ns o m ep r o b l e m so f e r r o r - c o r r e c t i n gc o d i n g a n d c r y p t o l o g y m a i na c h i e v e m e n t s i nt h i sp a p e ra r es u m m a r i z e da sf o l l o w s ： 1 a c y c l o t o m i ca p p r o a c h t o t h e c o n s t r u c t i o no f a l l b i n a r y d u a d i cc o d e so f p “ l e n g t h si sp r e s e n t e d ，b yw h i c ha l lb i n a r yd u a d i cc o d e so fp ”l e n g t h sa r e e n u m e r a t e d d u a d i cc o d e sa r eac l a s so f g o o de r r o r - c o r r e c t i n gc o d e sw h i c h i n c l u d eq u a d r a t i cr e s i d u e ( q r ) c o d e sa n dh a v e p r o p e r t i e sa n a l o g o u st ot h a t o fq r c o d e s s o m ed u a d i cc o d e sh a v eb e t t e rp r o p e r t i e st h a nq r c o d e s f o re x a m p l e ，( 1 1 3 ，5 7 ，1 8 ) ，( 1 5 1 ，7 6 ，2 3 ) a n d ( 2 3 3 ，1 1 7 ，3 2 ) d u a d i cc o d e sh a v e h i g h e rm i n i m u mw e i g h t s t h a nt h eq r c o d e so f t h es a m e l e n g t h s 2 a a p p r o a c ht o c o n s t r u c t i o na n de n u m e r a t i o no fa l lb i n a r yd u a d i cc o d e so f a r b i t r a r yl e n g t h si sp r e s e n t e d ，a n dt h en u m b e ro fi n e q u i v a l e n td u a d i cc o d e s i i i 北京m u u 人学博i 。学位论文 a b s t r a c t 3 4 5 i sd e r i v e d t h ep r o b l e mo f c o n s t r u c t i n ga n de n u m e r a t i n gt h ed u a d i cc o d e s w i t ha r b i t r a r yl e n g t h sr e m a i n so p e nu pt on o w i nt h i sp a p e r , w es o l v et h i s p r o b l e m a i m p r o v e de r r o r - c o r r e c t i n gd e c o d i n ga l g o r i t h mf o rac l a s so fm d sa r r a y c o d e si sp r e s e n t e d a r r a yc o d e sh a v ei m p o r ta p p l i c a t i o n si nc o m m u n i c a t i o n a n ds t o r a g es y s t e m s ，a n dh a v eb e e ns t u d i e de x t e n s i v e l ya r r a yc o d e sa r ea c l a s so fl i n e a rc o d e s ，w h e r ei n f o r m a t i o na n dp a r i t yb i t sa r ep l a c e di na t w o d i m e n s i o n a l ( o rm u l t i d i m e n s i o n a l ) a r r a yr a t h e rt h a nao n e d i m e n s i o n a l v e c t o r w i t ht h ei m p r o v e d a l g o r i t h m ，t h ee r r o r b i tc a r lb ef o u n d a c c u r a t e l yi n s o m ec o n d i t i o n s t h e n e r r o r - c o r r e c t i n gd e c o d i n gp r o c e s sw a sc o m p l e t e d a f t e r o n l yr e v e r s i n gt h ee r r o r b i t b u tt h eo r i g i n a la l g o r i t h mn e e d st op e r f o r m m o r ec o m p l i c a t e d o p e r a t i o n s ，i n c l u d e dd u a lb - c o d ee n c o d i n ga n dc o d e r e c o v e r i n g t h ei m p r o v e da l g o r i t h m i sm o r ee f f i c i e n t c e r t i f i c a t er e v o c a t i o ni sa l w a y sah a r dp r o b l e mo fr e s e a r c ha n da p p l i c a t i o n o fp u b l i ck e yi n f r a s t r u c t u r e ( p k i ) i nt h i s p a p e rw ep r e s e n tar e v i e wo f c e r t i f i c a t er e v o c a t i o ns c h e m e s t h ew o r k i n gp r i n c i p l e so fa l ls c h e m e sa r e d e s c r i b e d ，a n d t h e a d v a n t a g e s a n d d i s a d v a n t a g e s o fe a c hs c h e m e sa r e a n a l y z e di ns o m ed e t a i l i na d d i t i o n ，o n l i n ec e r t i f i c a t es t a t u sp r o t o c o l o c s pi si m p r o v e dt op r o m o t ee f f i c i e n c y a n dan e w i m p l e m e n t a t i o nm o d e l o f a p p l i c a t i o no no c s p i sa l s op r e s e n t e d b a s e do nt h ea n a l y s i so ft h et r u s tm o d e l so fp u b l i ck e yi n f r a s t r u c t u r e ，t h e c r o s s c e r t i f i c a t i o ns c h e m e sa n dt e c h n o l o g i c i m p l e m e n t t oe x t e n dt r u s t a m o n g p k i sa r eg i v e n f u n d a m e n t a l l y , p k ii sf a c i l i t yf o rr e p r e s e n t i n ga n d m a n a g i n g ab e l i e v a b l ee n v i r o n m e n ta n dm e c h a n i s mi n o p e n n e t w o r k h o w e v e r , e a c hp k ic r e a t e sad i f f e r e n tt r u s tr e g i o nf r o mo t h e rp k i s i tw i l l p r o m o t e t h ef u r t h e rd e v e l o p m e n ta n d a p p l i c a t i o no f p k i i f c r o s s c e r t i f i c a t i o n a m o n g p k i sc a nb e i m p l e m e n t e ds e c u r e l y ，e c o n o m i c a l l ya n dr e l i a b l y 1 v ：l 匕京u 人学博i j 学位论文第一章绪论 第一章绪论 1 9 4 8 年s h a n n o n 在通信的数学理论( am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ) 1 一文中提出了著名的信道编码定理，开创了纠错编码的研究 方向，此文标志着编码理论的开端。1 9 4 9 年，s h a n n o n 在他的论文保密系统的 通信理论( c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m ) 2 中，从信息论的角度阐 述了密码学的基本问题，从而奠定了现代密码学的研究基础。自此以来，几十年 间，纠错编码与密码学一直在不同的领域中互不相干地向前发展。7 0 年代中期， d i f f i e 和h e l l m a n 在他们的论文密码学的新方向( n e wd i r e c t i o n si n c r y p t o g r a p h y ) 【3 中，提出加密和解密密钥不同的公钥密码体制的思想，并基于 离散对数问题，提出了第一个公钥密码系统，随后，许多学者构造了很多不同的 基于数学难解问题的公钥密码系统，如r s a 、背包体制、e 1 g a m a l 方案 4 6 等。 1 9 7 8 年b e r l e k a m p 等证明了一般线性分组码的译码问题是一个n p c 问题 7 ，从 而为纠错编码在密码中的应用打开了大门，同年，m a c e l i e c e 利用g o p p a 码构造 了第一个基于线性分组码的公钥密码体制【8 。从此以后，国内外很多学者利用 纠错编码的特点和理论构造了各种各样的公钥密码体制、数字签名方案、秘密共 享方案、认证码等【9 ，纠错编码与密码相结合的研究得到了迅速的发展。 1 1 通信系统模型 所有通信或信息传输系统都可归结成如图1 1 所示的数字通信系统模型。 回“亘亟，压因“巫巫，压叵h 酬 图1 1 数字通信系统模型 北京邮i u 人学博f j 学位论史笫一苛绪论 信息传输或通信的目的，是要把收方不知道的信息及时、可靠、完整、安全 而又经济地传送给指定的收方。图1 1 中描述的整个系统的各个部分，就是为了 完成上述目的。当然，由于具体要求与应用场合的不同，图中的某些组成部分可 能没有，也有可能还要增加其它部分。 图中信源编码器是把信源( 人、计算机或其它信息处理设备) 发出的消息如 语音、图像、文字等转换成二进制形式的信息序列，也就是0 、1 符号串，并且 为了使传输更为经济有效，还要去年一些与被传信息无关的多余度。 在信息传输或处理过程中，除了指定的接收者外，还有非指定的或非授权的 用户，他们通过各种技术手段企图窃取机密信息。因此，为了保证被传送信息的 安全和e 一私，必须在信源编码器输出信息通过加密器时，用编码方法对信息进行 隐藏。 由于传输信息的媒介如电波、电线等总是存在有各种人为或天然的噪声和干 扰，因此，为了提高整个系统传输信息的可靠性，就需要对加密器输出的信息进 行一次纠错编码，人为地增加一些多余信息，使其具有自动检错或纠错功能。这 种功能由图中的纠错编码器完成。 为了使信息能与传输媒介的特性相匹配，使传输更为有效和可靠，从纠错编 码器输出的二进制( 或多进制) 数据送入调制器进行调制。从调制器输出的信号 经传输媒介后到达收端。由于传输媒介中的各种干扰的影响，到达收端的信号序 列中可能已有错误。收端的解调器对收到的信号解调，变成二进制( 或多进制) 序列串，送入纠错译码器纠错后，进入解密器，解密器把输入的序列恢复成原本 的信息，再通过信源译码器恢复成原始的消息送给信宿( 人或计算机等) 。 信道是传输信息的通道，又是传送物理信号的具体媒介。它可以是一对导线、 一条同轴电缆、光导纤维或传输电磁波的空间等。一般信道都属于开放信道，无 j 是指定的接收者或窃听者都可同样方便地收到在开放信道中传输的消息。因此 当信号通过这些媒介时，是很不安全的。不仅存在着各种天然和人为干扰使被传 送信号产生错误以外，而且还存在着非指定或非授权用户通过各种方法( 如搭线、 电磁波接收、声音接收等) 对所传输的信号进行侦听( 称被动攻击) 。更有甚者， 有些非法入侵者主动向系统攻击，采用删除、更改、增添、重放、伪造等手段， 向系统注入信号或破坏被传的信号，以达到欺骗别人，有利于自己的目的，这种 北京| | f l j l u 人学博f ：学位论文第一章绪论 攻击称为主动攻击。因此如何保护系统中所传消息的真实性、完整性、可靠性 即如何实现保密通信，这是任何一个通信系统都面临和必须解决的问题。 1 。2 保密通信、纠错编码与密码学之间的关系 保密通信是发送端对欲传输的消息采取加密措施后才在信道中传送，而接收 端对所收到的加密消息进行解密使它恢复出原消息的一种通信方式。加密的目的 是隐蔽消息内容，使窃听者和无关人员在收到加密消息后无法获得原消息，而指 定的接收方则可用“密钥”方便地把收到的加密消息正确地变换成原消息。而为 了保证消息传输可靠性，加密消息在进入信道开始传输之前，要进行一次纠错编 码，以增强消息的抗干扰能力。 在通信系统中采取消息加密和纠错编码等措施，可以使得在开放信道中传输 的消息具有抗信道干扰和防止消息被非法接收者或无关人员窃听和能力，从而能 够安全、可靠地把消息传送给指定的接收者。由此可见，纠错编码和密码技术实 现保密通信的两个不同侧面的技术手段，。这也是s h a n n o n 在4 0 年代同时研究编 码理论和密码学的原因。 密码学是一门研究通信安全和保护信息资源的既古老而又年青的科学和技 术。它包括两方面：密码编码学和密码分析学。密码编码学是对信息编码以隐蔽 信息的一门学问：而密码分析学是研究分析破译密码的学问。这二者既相互对立 又相互促进，共同推动密码学的发展。 纠错编码是提高通信质量或可靠性的一门年青的学科。自1 9 4 8 年s h a n n o n 提出信息编码至今，这门学科已取得了丰硕的成果。利用纠错编码的差错控制技 术，已成为通信系统设计中一种重要、在某些场合甚至是必不可少的技术手段， 纠错编译码器已成为现代通信系统中的重要组成部分。 纠错编码和密码学可以说是信息科学领域中的一对孪生兄弟。虽然加密和纠 错编码同属于增加信道中传输消息多余度的范畴，但是前者是要把消息的结构规 律打乱，使之有可能在消息空间的任何位置出现，并且要求它们的出现概率越均 匀越好。我们可以把这种加密的作用称为增加消息在信道中的疑义度。而纠错编 码的作用仍然是要增加消息在信道中的多余度，只是这种多余度不同于疑义度， 因为它在信道中传输时只须考虑抗干扰而没有被窃听的顾虑。 北京邮也人学博l 学位论文 筇一章绪论 1 3 纠错编码概述 s h a n n o n 信道编码定理为实现通过有噪信道的可靠通信奠定了理论基础近。 近5 0 余年以来，作为信息论的一个分支，纠错编码已从理论研究走上了工程应 用。随着大规模集成电路和计算机技术的发展，纠错编码技术( 也称差错控制技 术) 在通信、计算机网络、工业自动监控等领域得到了广泛的应用。 s h a n n o n 信道编码定理指出，在编码效率小于信道容量的条件下，通过编码 可以使译码错误概率任意小，从而达到可靠通信。定理的证明采用了随机编码技 术，给出的结果只说明存在一种编码方式，其误码率随着码长n 的增长趋于任意 小。但证明是非构造性的，它没有告诉我们如何构造实际上可实现的、具有上述 性能的这类码的方法。纠错编码就是为解决这一问题而产生的学科。它的目的是 寻找在实际上易于实现且能达到有效而可靠通信的编译码方法。 通俗地讲，所谓纠错编码，就是按一定规则给信息序列m 增加一些多余的 码元，使不具有规律性的信息序列m 变换为具有某种规律性的数字序列c ，又 称为码序列。也就是说，码序列中的信息序列m 的诸码无与多余码元之间是相 关的。在接收端，纠错译码器利用这种预知的编码来译码。根据相关性来检测和 纠正传输过程中产生的差错就是纠错编码的基本思想。 纠错编码的主要功能就是能自动地纠正或检测出数据传输过程中由于各种 噪声干扰而造成的误差。目前能达到这种目的的纠错编码有许许多多。按照不同 的方式可以将众多的纠错编码进行不同的分类。例如： 1 ) 按照编码规则的局限性可分为分组码和卷积码。 若编码规则仅局限在本码字之内，即本码字的监督元仅和本码字的信息元相 关，则称这类码为分组码。若本码字的监督元不仅和本码字的信息元相关，而且 还和与本码字相邻的前若干个码字的信息元相关，则这类码称为卷积码。 2 ) 根据信息元和监督元之间的关系可分为线性码和非线性码。 线性码的所有码字在并元和运算之下是封闭的，而非线性码则不封闭。或者 换句话说，线性码实际就是n 维线性空间中的一个k 维( 七 2 ，方法类似。 由于口4 = r p + l ，r 为整数，所以 口p 抽) = c ，p + ，9 = + ( ： ，p + i p 2 j r 2 p 2 + + ( ； r 9 p 9 = 1 + a p 2 ，a 为整数。 因此c s p , ( a ) ip f i p ( 口) ， 又由引理2 1 ， 6 p ( 口) i 艿一( 口) ， 因而 占，：( 口) 占p ( 口) ，p f i p ( 口) 。口 例如，岛( 2 ) = 3 ，岛。( 2 ) = 2 1 ；4 。：( 2 ) = 4 i ( 2 ) = 5 。 定理2 1 2 设p ；+ l ( m o d 8 ) 为素数，则对任意整数m 1 ，都有 ( p ”) 屯- ( 2 ) 为偶数。 证明： 由定理2 6 ，有( p 一1 ) = 2 e i 万。( 2 ) ，两边同乘以p ，得 o ( p ”) = p m - i ( p 一1 ) = 2 e l p ”一1 占。( 2 ) 又由定理2 1 1 ，可得矿( p ”) = 2 e 。一( 2 ) ，1 1 1 1 妒( p ) a 矿( 2 ) 为偶数。口 定理2 1 3 设p - - - + l ( m o d 8 ) 为素数， 妒( p ”) = 2 e ，。占矿( 2 ) ，则 c o ：p 一1 a 1 ) 正好就是阶为2 e 。的p 的分圆类集合，其中c 。表示包含a 北京邮电人学博i ：学位论史 第二章一元d u a d i c 码的构造j 计数 j 宄 的2 分倒陪集。 证明： 设g 为p ，p 2 ，p ”的公共原根，则存在1 t ( p ) 使 g ；2 ( m o d p ”) 。假设2 模p ”的阶为万。( 2 ) = 6 0 ，p ) t n a g 磊；l ( m o d p ) 。 故 f 磊；o ( m o d # ( p ”) ) ；0 ( m o d 2 e , , , 8 0 ) 从而有信0 ( m o d 2 e 。) 。由于d o 为9 2 e 生成的循环群，所以2 d o ，于是 c 1 = 1 ，2 ，2 2 ，2 a o - t 量d o 又i c 。l = l d o i ，所以c i = d o 。注意到e = 口c l ，于是 c 。：p “一1 口1 就是阶 为2 9 。的分圆类集合。口 定理2 1 4 所有码长为p ”的d u a d i c 码都为分圆d u a d i c 码。 证明： 由d u a d i c 码和分圆d u a d i c 码的定义及定理2 1 3 容易得到。口 2 4 3 码长为p “的d u a d i c 码的计数和构造 在这一小节利用前面的产生分圆类集合的方法和前一节2 3 中的一些结果， 来构造码长为p ”的d u a d i c 码。用这种构造法只需考虑p ”的分圆类集合，其中 每个分圆类为2 分圆陪集。 由文【7 中的定理2 7 的证明，可以得到下面的引理。 引理2 2设整数e = 2 s e 7 ，e 为奇数，令h = 忙，2 e ，2 2 e ，2 5 e ， z 2 。= 0 , 1 ，2 e 1 ) 。i r i oc z 2 。，且满足： 1 ) l i o i = e ； 2 ) 至少存在一个非零元d z 2 。，使得下式成立 ，o + d = i i ，l + d = i o ( 2 3 ) 其中i l = z 2 。i o 。 令，( d ) 表示式( 2 3 ) 的解集( 厶，i 。) ，- 7 ：是l i ( d ) i 就是由d 确定的分割数，则有 4 北京i | l f l 乜人学博i ：学位论文第二章_ - ) f i d u a d i c 码的丰l j 造j 计数研究 下列结论成立： a ) 对于任一d h ，| ，( d ) l = 2 。 b ) 如果d l ，d 2 h ，d l d 2 ，那么i ( d 1 ) n i ( d 2 ) = c ) 当d 取遍h 中的元素时，u z ( d ) 给出了式( 2 3 ) 的全部解集。若将 d e h ( i o ，) 和( ，l ，厶) 看作不同的解，则全部解的总数为i z ( d ) f 。 d e h 事实上，若d h ，则d 满足式( 2 3 ) 。那么当口是奇数时，显然有 o + e d = i i ，i i + 倒= i o 因此任一谢a h 也满足式( 2 - 3 ) 。于是u ，( 耐) 也给出了式( 2 3 ) 的解集， d e 日 由引理2 2 ，i ( d ) l 为式( 2 3 ) 的全部解的个数，则 l ，( 积) i i i ( d ) i dldeh 另一方面，显然，( d ) ，( o d ) ，即f ，( d ) f f ，( o d ) f ，从而有 i z ( d ) i i ，( 谢) i d e hd e h 因此，i ，( d ) i l ，( 谢) 1 ，且，( d ) = ，( 耐) ，也就是说，a d 和d 确定了式( 2 3 ) 的相同解集。于是有下面的结论： 定理2 1 5设整数e = 2 5 e 7 ，e 为奇数，h = 盈，2 e7 ，2 2 e ，2 s e ) z 2 。= o ，l ，2 e 一1 ) ，i oc z 2 。，| i o i = e ，i = z 2 。i o 。令z = a c l ，其中d h 口为任一奇数，则z 满足 ，o + z = i l ，i l + z = i o y f - 且l ( z ) = ，( 砝) = ，( d ) ，即有1 ，( 谢) i = i ，( d ) i = 2 。，( z ) 如引理2 2 中的定义。 定、理2 1 6 设p = + l ( m o d 8 ) 是一个素数 p 只= 如：( p 一1 ) 万p ( 2 ) = 2 e l ，e 1 = 2 s e 0 ，e 0 为奇数，r n 为一正整数 则p 的分割数n ( p ) 为： n ( p ”) = 2 = o 北京邮l u 人学博i ? 学位论文第一二章二元d u a d i c 鹳的构造0 计数研究 其中e = q ，吼= 矽( p ) 2 8 。t ( 2 ) 。于是，码长为p “的d u a d i c 码的数量为 4 n ( p ”) 。 一i 证明：p 的分因类集合s = u s 为 s o = d o ，d l ，一，d 2 川) ， s l = p d o ，p d l ，p d 2 。一1 ， s j = p 7 d o ，p j d l ，一，p 。d 2 川 ， s m l = p ”1 d o ，p r o - 1 d l 一，p ”1 d 2 其中d o = ( 9 2 ) ，d i = g d o ，g 为p ，p 2 ，p 4 的公共原根。s 为所有小于p “ 的p 。的倍数但不是p “1 的倍数的数组成的2 - 分圆陪集的集合。特别地，对于 s h ，它由p ”1 的倍数且小于p “的数组成的2 - 分圆陪集的集合。显然，s 可 以写为如下等价形式： s 剃= p r o - 1 d o ”，d 1 川，d 2 e _ l ( p ) 其中d ，9 ( f = 0 , 1 ，2 e l 一1 ) 为p 的阶为2 e l 的分圆类。 对于p 的每一分割e o 和e l ，显然q 旺e i ，i = 0 , 1 ：j = 0 , 1 ，一1 。于 是s j 分属于民和e l ，即对于p ”的每一分割岛和e l ，s j 也存在着分割。和 e 1 7 分别属于和巨。 由定理2 1 1 ，可知s m - 1 是s a j = 0 , i ，小一1 ) 中包含不相等的陪集最少的集 合，所以我们先计算s 。的分割数。 考虑下式 ，o ( 一1 ) + d = ，l ( ”一，l ( 卅一1 ) + d = i o ( 小一1 ) ( 2 4 ) i ! 皇! ! ! ! ! ! ! 盔兰竺! ：堂些堡苎 笙三主三垄! ! 型! 塑塑塑生旦! ! 堕 令，( 一1 ( d ) 表示式( 2 4 ) 的解集( ，0 ( m - i ) ，i ( m - i ) ) ，于是 ，”1 ( d ) l 就是由d 确定 的s _ l 的分割数。由引理2 2 知道，当d 取遍h 刊= ，2 e 。，2 2 e 。，2 5 e 。 中 的元素时， u i 一1 ( d ) 给出了式( 2 4 ) 的全部解集；并且对于任一d 川， 1 ，”、1 ( d ) b2 4 。 若s ，( = 0 , 1 ，一2 ) 与s 。一l 有相同的陪集数，即e 。= e l = 2 5 e o ， 于是由引理2 2 可知，当d 取遍日( ，) = h 一1 = ，2 e o ，2 2 e 0 ，2 5 e o 中的元 素时， u j 7 1 ( d ) 给出了下式 ，o n + d = 吖力，0 7 + d = i o d ( 2 5 ) 的全部解集；并且对于任一d 日d ，l ，( d ) | = 2 4 。 若s ，与s ，一i 有不同的陪集数，则显然& 与s 州有不同的陪集数，由定理 2 1 1 ， s o i _ p x l s 卅_ l i ，即e m = p x q = 2 。p 。e 0 ，z 1 ，2 ，肌一1 ) 。于是 由引理2 2 知，当d 取遍日( o ) = p 日( 一1 = 仞。e 0 ，2 p e 0 ，2 2 p 。，2 s p 。 中的元素时， u 1 o ( d ) 给出了式( 2 5 ) 的全部解集( 此时_ ，= 0 ) ：并且对于 任一d h ，p ( d ) 卜2 4 。 由定理 2 1 5前的讨论，我们知道当d 取遍 日【o ) = p x 日( 埘一1 = 扣1 ，2 p l e 0 ，2 2 p e o ，2 5 p 。) 中的元素时， u ( m - i ) ( d ) 也给出了式( 2 4 ) 的全部解集；又由定理2 1 5 可得，对于任一 d h ，p 。( 矗) i 22 吐，其中d 2p 。d l 2 詈d 即 。p l i ( i - 1 ) ( d ) l = p ( d ) r 。 同理，易证当d 取遍日( o ) = p x h m 一1 = 妇。，2 p l e o ，2 2 p 。e 0 ，2 s p 。 中的元索时( 这里p 。= e n _ _ l ) ，u j 飞d ) 也给出了式( 2 5 ) 的全部解集 e l d e o o 北京邮l 乜人学博j ：学位论文第_ 二章二元d u a d i c 码的构造1 打 数研究 ( = 0 , 1 ，m 一2 ) ；并且对于任一d h 0 ，| ，1 d ) l = 2 “，其中 d 2 。e m d 。一一，b 口j ，( d ) l = | ，。( d ) i 。一7 气。 综上所述，当d 取遍中的元素时， u ，q d ) 给出了式( 2 5 ) 的全部 d e 甘f o ) 解集( - ，= 0 , 1 ，m 一1 ) ，从而能构造出s = us 女的全部分割。 而对于任一d h ( 们，s 的由d 确定的分割数为 眦) = m 兀- ! p ( d ) i = 爿p ( d ) r 7 ，= 0，= 0 = 垆( d ) r 1 。嵋v = ( 2 d ) q + 岛”+ 7 注意到( e o ，e ，) 和( e 。，e o ) 表示p ”的同一分割，因此p ”的由d 确定的不同 分割数为2 - i ( d ) l 。 所以p “的所有分割数为 5 n ( p “) = 2 - 1 l i ( d ) | = 2 - ( 2 2 q 7 6 岛) 5 + 气+ 一7 d e l l o j = o ：2 1 ( 2 2 7 岛) q + q ”e - ) 7 q j = o 口 由上述定理，我们可以很容易地得出以下两个推论 推论 2 1 设pz + _ l ( m o d 8 ) 是一个素数 p 只= 扣：( p 1 ) 6 p ( 2 ) = 2 q ) ，e l = 2 s e 0 ，e 0 为奇数，聊为一正整数 且万( 2 ) = p k - l f i p ( 2 ) ，七= l ，2 ，m ，则p “的分割数( p “) 为 j n ( p ) = 2 2 ”1 推论 2 2 设ps + l ( m o d 8 1是 一个素数 北京邮电人学博i ：学位论文第二章二元d u a d i c 码的构造与汁数研究 p p e , = p ：( p 一1 ) 6 。( 2 ) = 2 e l ， e l 为奇数， m 为正整数，且 占。( 2 ) = p k - 1 8 p ( 2 ) ，k = 1 ，2 ，m ，贝, l j p “的分割数n ( p ”) 为： u ( p 、= 2 5 ”1 定理2 1 6 的证明过程也给出了d u a d i c 码的构造方法，通过举例说明。我们 来构造码长p 2 为的d u a d i c 码，设p = 3 1 。 例2 3 构造码长3 1 2 为的d u o x t i e 码 解： 因为p b ，由前一节中码长属于b 的d u a d i e 码的构造方法，可计 算得p = 3 1 的分割数有4 种，分别为： ( l ”，d ) = ( 0 ，1 ，2 ，3 ) ，( o ，1 ，5 ，3 ) ，( 0 ，4 ，5 ，3 ) ，( o ，2 ，4 ) ，1 ) 因为e 2 = e l ，所以 ( 厶，d ) = ( 0 ，1 ，2 ，3 ) ，( o ，1 ，5 ，3 ) ，( 0 ，4 ，57 ，3 ) ，( 0 ，2 ，4 ，1 ) 其中i 泛示s o 中分圆类的