（应用数学专业论文）线性码的深度分布和二元序列的广义导数的研究.pdf

线性码的深度分布和二元序列的广义导数的研究 摘要 序列的导数是刻画和分析序列的复杂性以及线性码深度分布的重要工具。 本文研究了导数在编码和序列密码领域中的应用，推广了有限域和有限环上的 深度分布理论，创造性地定义了二元域上多序列的广义导数，研究了周期多序 列的广义导数序列的性质和结构。 本文的工作主要表现在以下几个方面： 1 )定义了有限环昂+ u f p 上码字的广度，研究了环昂+ 掰昂上码字广度的 一些性质，并给出了计算环昂+ 诉上码字广度的算法。 2 ) 定义了有限环z 矿上码字的广度，研究了环z l 口上码字广度的一些性质， 给出了环z 扩上码字广度的两个递归算法，推广了有限域和有限环上码字的深 度分布理论，进一步丰富了有限环上的编码理论。 3 )定义了二元域上多序列的周期和广义导数，证明了周期二元多序列的 广义导数仍然是一个周期二元多序列，研究了二元多序列的广义导数的周期与 原二元多序列的周期之间的关系，并给出了两类特殊周期即周期分别为2 和 2 一1 的二元多序列的广义导数与原二元多序列在结构上的关系。 关键词：线性码；深度分布：广义导数；导数；多序列；周期；流密码 r e s e a r c ho nt h ed e p t hd i s t r i b u t i o no fl i n e a rc o d e s a n dt h eg e n e r a l i z e dd e r i v a t i v e so fb i n a r ys e q u e n c e ：s a b s t r a c t t h ed e r i v a t i v eo fs e q u e n c e si sa ni m p o r t a n tt o o lt od e p i c ta n da n a l y z et h e c o m p l e x i t yo fs e q u e n c e sa n dt h ed e p t hd i s t r i b u t i o no fl i n e a rc o d e s t h ea p p l i c a t i o n o fd e r i v a t i v et ot h ef i e l do fe n c o d i n ga n ds t r e a mc i p h e ri ss t u d i e d ，t h et h e o r yo ft h e d e p t hd i s t r i b u t i o ni nf i n i t ef i e l d sa n df i n i t er i n g sa r ee x t e n d e d t h eg e n e r a l i z e d d e r i v a t i v e so fb i n a r ym u l t i s e q u e n c e sa r ec r e a t i v e l yd e f i n e d s o m ep r o p e r t i e sa n d s t r u c t u r e so ft h eg e n e r a l i z e dd e r i v a t i v e so fp e r i o d i cm u l t i s e q u e n c e sa r ed i s c u s s e d t h em a i nr e s e a r c h e so ft h i sd i s s e r t a t i o na r ea sf o l l o w s 1 ) t h ew i d t ho fc o d e w o r d so v e rt h ef i n i t er i n gf p + z 妨i sd e f i n e d ，s o m e p r o p e r t i e so ft h ew i d t ha n dar e c u r s i v ea l g o r i t h m f o rc o m p u t i n gt h ew i d t ho f c o d e w o r d so v e rt h ef i n i t er i n gf p + t l f pa r eg i v e n 2 ) t h ew i d t ho fc o d e w o r d so v e rt h ef i n i t er i n g 乃i sd e f i n e d ，s o m e p r o p e r t i e so ft h ew i d t ha n dt w or e c u r s i v ea l g o r i t h m sf o rc o m p u t i n gt h ew i d t ho f c o d e w o r d so v e rt h ef i n i t er i n g z 萨a r eg i v e n t h i sr e s e a r c hg e n e r a l i z e st h ed e p t h d i s t r i b u t i o nt h e o r i e sa n de n r i c h e st h ee n c o d i n gt h e o r yo v e rf i n i t er i n g s 3 ) t h ep e r i o da n dt h eg e n e r a l i z e dd e r i v a t i v e so fb i n a r ym u l t i s e q u e n c e sa r e d e f i n e d t h eg e n e r a l i z e dd e r i v a t i v e so fp e r i o d i cb i n a r ym u l t i s e q u e n c e sa r ep r o v e d t ob ep e r i o d i cb i n a r ym u l t i s e q u e n c e s t h ec o n n e c t i o nb e t w e e nt h ep e r i o do ft h e g e n e r a l i z e dd e r i v a t i v e so fp e r i o d i cb i n a r ym u l t i s e q u e n c e sa n d t h a to ft h e m s e l v e si s s t u d i e d ，t h e nt h ec o n n e c t i o nb e t w e e nt h es t r u c t u r eo fm u l t i s e q u e n c e sw i t hp e r i o d 2 na n d2 ”一1a n dt h es t r u c t u r eo ft h e m s e l v e si sa l s or e s e a r c h e d k e yw o r d s ：l i n e a rc o d e ；d e p t hd i s t r i b u t i o n ；g e n e r a l i z e dd e r i v a t i v e ；d e r i v a t i v e ； m u i t i s e q u e n c e ；p e r i o d ；s t r e a mc i p h e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金胆王些太堂一或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：狮缔签字日期脚年易月咖 学位论文版权使用授权书 本学位论文作者完全了解 金胆兰些左堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权金垦王些太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：乡次 诿徊 - 一， 签字嗍瑚年6 月( 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名 铂乞 签字日期游6 月沙日 电话： 邮编： 致谢 时光飞逝，三年的研究生生活即将结束。在这段难忘的日子里，作者在学 习和生活上得到了许多老师、同学和亲友的关心和帮助，在此，向他们表示最 衷心的感谢。 衷心感谢我的导师朱士信教授。朱老师不仅在学业上给予了我悉心的指导 而且在生活上给予了我无比真诚的关心，使我得以克服重重困难顺利完成学业。 朱老师严谨的治学态度，渊博的学识，为人师表的风范深深地感染着我，是我 终身学习的楷模。在此，我向尊敬的导师致以最诚挚的谢意和深切的敬意。 感谢三年来与我朝夕相处的各位师兄弟。他们在生活中给予了我很多无私 的帮助和鼓励，在科研上给我提出了很多有益的的建议，并给予我热情的指导， 他们分别是施敏加、开晓山、唐淼、童宏玺、许和乾、陈安顺、宛金龙、姜光 峰、孙琳等。 感谢我的父母和妻儿，他们始终如一的理解和支持是我坚强的后盾。 作者t 张道福 2 0 0 9 年4 月 第一章绪论 1 1 研究的背景和意义 1 1 1 背景 编码理论起源于现代通信技术和电子计算机技术中差错控制研究的实际需 要。美国数学家s h a n n o n 在1 9 4 8 年发表的论文“通信的数学理论n 1 中首次 提出了著名的有扰信道编码定理，奠定了纠错码理论的基石，开创了纠错码理 论这一全新的研究方向。根据s h a n n o n 的思想，h a m m i n g 心1 、b o s e 、c h a u d h u r i 、 h o c q u e n g h e m ( b c h ) 1 、m a s s e y 6 州、m a c w i l l i a m s 、g o p p a 池1 33 等一批杰出 的纠错码理论专家先后给出了一系列设计好码和有效译码的方法。此后，越来 越多的通讯学家和数学家投身到纠错码领域的研究，他们的工作推动了纠错码 在理论和应用上的飞速发展。 纠错码理论的诞生和发展大致经历了以下几个阶段： 2 0 世纪5 0 年代至6 0 年代初期是纠错码从无到有迅速发展的阶段。在这一 时期，人们主要研究各种有效的编码和译码方法，提出了著名的b c h 码，同时 也给出了纠错码的基本码限，奠定了线性分组码的理论基础。 2 0 世纪6 0 年代至7 0 年代初期是纠错码发展过程中最为活跃的时期。人们 不仅提出了许多有效的编码和译码方法，而且注意到了纠错码的实用化，讨论 了与实用有关的各种问题，如码的重量分布、译码错误概率和不可检错概率的 计算、信道的模型化等，这些问题的研究为纠错码的应用打下了坚实的基础。 2 0 世纪7 0 年代至8 0 年代初期是纠错码发展史上具有极其重要意义的时 期。以g o p p a 为首的一批学者在理论上构造了一类g o p p a 码，其中一类子码能 达到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能，这一成 果在纠错码发展史上具有划时代的意义。在此期间，大规模集成电路和微机技 术的迅猛发展，为纠错码的实用化打下了坚实的物质基础，纠错码中与实用相 关的各种技术及有关问题得到了极大的关注，并在实用中取得了巨大的成功。 2 0 世纪8 0 年代初至今，g o p p a 等从几何角度讨论分析码，利用代数曲线 构造了一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达 到的性能。由于代数几何码是一类范围非常广的码，在理论上已经证明它具有 优越的性能，因而受到了编码理论工作者的重视，使代数几何码的研究得到了 迅速的发展，取得了许多成果。 1 9 9 7 年，e t z i o nt 首次把用于刻划和分析序列的线性复杂度的著名的微分 算子应用到编码领域中，定义了二元域上码字的导数，提出了二元域上码字深 度和码的深度分布的概念，研究了码的深度分布和码字深度的一些性质，给出 了一个计算二元域上码字深度的递归算法，并利用深度分布给出了码的一种新 的分类方法，即按深度等价进行分类。此后，众多学者投入到有限域上深度分 布理论的研究。近年来，随着有限域上编码理论的日趋完善，国内外从事编码 理论研究的学者逐渐将研究的热点转移到有限环上的编码理论。朱士信等定义 了有限环上线性码的深度、深度分布和深度谱，研究了这些环上线性码的深度 分布的性质和算法等，建立了有限环上线性码的深度分布理论。 密码按其加密体制来分可分为分组密码和序列密码，后者又称为流密码。 流密码拥有频谱理论、代数等理想的数学工具并具有加解密速度快、硬件实现 容易、安全性能好等特点，因此，流加密是各国军事和外交保密通信中普遍采 用的主要的加密方式。密钥流序列的线性复杂度及其线性复杂度的稳定性是衡 量流密码安全性能的一个重要的度量指标，序列的导数作为刻划序列线性复杂 度的一个有力工具成为密码学工作者研究的一个重要的对象。 1 1 2 意义 纠错码的研究不仅具有理论意义，而且具有重大的现实意义。纠错码技术 己经渗透到很多领域，利用纠错码可以降低数字通信系统以及计算机存贮和运 算系统中的误码率，提高通信的质量，延长计算机无故障运行的时间等，在美 国等西方国家中已被作为一项标准技术而被广泛采用。纠错码中的许多编码和 译码的原理和方法与通信系统中其它有关技术相结合，得到了一些令人惊喜的 结果，例如，纠错码与调制技术相结合所产生的t c m 技术，已作为国际通信标 准技术而被推广使用；纠错码与信源编码相结合，提高信息传输的可靠性和有 效性；纠错码技术应用于超大规模集成电路的设计中，以提高集成电路芯片的 成品率，降低芯片的成本。 纠错码与现代密码技术相结合，构造出了既能加密又具有检错和纠错功能 的密码系统。纠错码的成熟理论和技术成功地解决了密码学中的许多问题，同 时，这些问题的解决又进一步促进了纠错码理论和技术的发展n4 。1 5 3 ，纠错码与 密码的结合是纠错码理论和密码学发展的必然产物。 随着科学技术的进步和实际需要，纠错码理论必将进一步发展，其应用范 围必将更加广泛。 】2 研究的现状 近年来，纠错码理论研究的热点主要集中在有限环上的编码、代数几何码、 量子纠错码、时空码和纠错密码。 密钥序列在流密码中具有重要的意义，根据b m 算法n 们一条抗攻击强度大 的密钥序列必须具有足够高的线性复杂度。但是具有高线性复杂度并不能保证 序列具有强的抗攻击强度，例如：周期序列1 ，1 ，1 ，1 ，1 ，1 ，1 , 0 ，1 ，1 ，1 ，1 ，1 ，l ，l ，0 ，的 线性复杂度等于其周期，其线性复杂度已达到最大，但将其每个周期的第八个 比特改为1 时其线性复杂度就立即降为0 ，可以用低线性复杂度的序列去逼近 高线性复杂度的原序列，用这样的具有高线性复杂度的序列作为密钥序列是极 不安全的。为了解决这个问题，人们提出了差错线性复杂度n l1 8 1 。线性复杂度 和差错线性复杂度是密钥序列安全性的一个重要的度量指标，因此，序列的线 性复杂度和差错线性复杂度是近年来研究的一个热点，而且单序列的相关问题 已研究得比较完备，目前研究的热点是多序列的线性复杂度和差错线性复杂度。 加密和纠错的联合编码、基于纠错码的密码体制作为编码和现代密码的交 叉已成为编码和密码学工作者研究的热点。 1 3论文的主要内容和结构安排 本文在总结前人对有限域和有限环上码字的深度分布理论以及二元域上序 列的导数和广义导数问题研究成果的基础上，研究了有限环上码字广度的性质 和算法以及二元多序列的导数和广义导数的性质和结构问题。 本文的正文部分分为六章： ， 第一章首先介绍了纠错码理论和纠错密码理论产生的背景及其研究的意 义和现状，接着介绍了本文研究的主要内容和结构上的安排。 第二章简要介绍了纠错码理论和序列的基本知识。 第三章首先介绍了深度分布理论研究的背景及其意义，接着简要总结了 有限域上码字深度分布的已有成果，最后将有限域和有限环上码字的深度分布 理论作了进一步推广，分别定义了有限环昂+ 诉和z 矿上码字的广度，给出了 这两类环上码字广度的若干性质和计算码字广度的递归算法。 第四章在前人研究的基础上进一步研究了二元序列的广义导数。首先对 二元序列的广义导数的已有研究成果作了简要的概述，然后给出了序列周期的 新的定义并进一步研究了周期二元序列的广义导数。 第五章定义了二元域上多序列的周期、导数和广义导数，研究了周期二 元多序列的广义导数的周期性，给出了周期分别为2 和2 一1 的周期二元多序 列的广义导数与原多序列在结构上的内在关系。 第六章对全文进行总结并提出有待于进一步研究的问题。 第二章基础知识 2 1 分组码【1 9 2 1 】 在数字通信中，数字信息在传送过程中往往会受到各种干扰，因此，接收到的数 字信息可能就不是原来信息源发送的数字信息。为了使信息源发送的数字信息能正确 地传送到收信者，除了可以采取各种技术上的措施之外，还可以利用纠错码来进行差 错控制，其中分组码就是一类非常重要的纠错码。 2 1 1 分组码的基本概念 分组码是把信源输出的信息序列，按每k 个码元分成一段，通过编码器使这k 个 码元按一定规则产生，个检验位，输出长度为行= k + ，的一个码字，每个码字的校验 位仅与本组的信息元有关。 定义2 1 1 1 分组码是对每段k 位长的信息组，按一定规则增加，= 刀一k 个校验 元，组成长为刀的序列( c o ，q9 e9 c n 彩乞一。) ，称这个序列为码字( 或码组) 。在二进制情 况下，信息组共有2 个，通过编码器编码后得到的码字也有2 个，这2 个码字的集合 称为( 玎，k ) 分组码，其中，1 1 表示码长，k 表示信息位的个数。 押长序列( 简称为n 重) 的可能排列总共有2 ”种，而( n ，k ) 分组码的码字集合只有 2 种。所以，分组码的编码问题就是制定出一套规则，以便从个2 “个，z 重中选出这2 个码字，不同的规则就得到不同的码。我们称被选取的2 个门重为许用码组，其余的 2 ”一2 个n 重为禁用码组。 称r = ，z 为码率，它表示( t i , 七) 分组码中信息位在码字中所占的比重，它是衡量 分组码有效性的一个基本参数。 定义2 1 1 2 对于两个，? 重 x = ( x o ，置，翰一i ) y = ( y o ，y l ，以一。) 来说，用d ( x ，y ) 表示x 和y 的对应位置上不相等的分量的个数，即 d ( x ，y ) = ：1 x i y 我们把d ( x ，y ) 叫做x 和y 之间的汉明距离，简称距离。 定义2 1 1 3 对任意，2 重x = ( x o ，五，而一。) ，定义w c x ) 为x 中非零分量的个数， 即 w ( x ) = 1 n 0 称w ( x ) 为x 的汉明重量，简称重量。 定义2 1 1 4 在( ，z ，七) 分组码中 ( 1 ) 两两不同码字之间距离的最小值d ，即 4 d = r a i n d ( x ，y ) l x ，y ( 刀，j | ) ，x y ) 称为该分组码的最小汉明距离，简称最小距离。 ( 2 ) 非零码字的重量的最小值 m i n w ( x ) l x ( ，z ，k ) ，x o ) 称为该分组码的最小重量。 最小距离是衡量( 以，k ) 分组码的纠错能力和检错能力的一个重要的参数。下面的 定理说明了( 疗，k ) 分组码的最小汉明距离d 与其纠错能力和检错能力的关系。 定理2 1 1 1 任一( ，| j ) 分组码，若要在码字内 ( 1 ) 检测e 个随机错误，则要求d e + l ； ( 2 ) 纠正f 个随机错误，则要求d 2 t + 1 ； ( 3 ) 纠正f 个随机错误，同时检测p ( f ) 个错误，则要求d t + p + 1 ； ( 4 ) 纠正f 个错误和p 个删除，则要求d 2 t + p + l 。 2 1 2 线性分组码 对于一个( 甩，k ) 分组码来说，若每个码元的取值有g 种( 口为素数幂) ，则共有g 个 码字。n 长的g 元数组共有g ”个，这口4 个n 维数组组成一个g f ( q ) 上的栉维线性空间， 记为k 。 定义2 1 2 1 如果一个( 刀，k ) 分组码的g 个码字的集合构成了圪的一个k 维线性 子空间，那么称该分组码为一个分组长为船，信息位为k 的g 元线性分组码，简称g 元 ( 刀，k ) 线性分组码或q 元线性码。 因为该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为群码。 由于线性分组码是特殊的分组码，因此有关分组码的参数，如码率，码字的距离 与码的最小距离，码字的重量等定义，以及说明最小距离与纠错能力之间关系的定理 2 1 1 1 ，对线性分组码均适用。 k 和d 是分组码的两个最重要的参数，因此我们用门，k ，d 1 表示码长为以、码率为 k 、最小距离为d 的线性分组码，而用符号( ，z ，m ，d ) 表示码长为n 最小距离为d 码字个 数为m 的线性分组码。 2 1 3 一致校验矩阵与生成矩阵 【玎，k ，d 】线性分组码的编码问题就是在力维线性空间圪中，如何找出满足一定要求 的由2 个矢量组成的k 维线性子空间k 。，换言之，就是在满足给定条件下，如何从 已知的k 个信息元求得厂= 刀一k 个校验元。这相当于建立一线性方程组，已知k 个系数， 求玎一k 个未知数，使得到的码恰好具有所要求的最小距离d 。 如果一个( 咒一k ) x n 阶矩阵日满足 h c 1 = 0 t ( 2 1 ) 或 c h t = 0( 2 2 ) 其中c 为 玎，尼，d 】线性分组码的任一码字，日的每一个行向量均线性无关，则称日为 ，2 ，k ，d 】线性分组码的一致校验矩阵。 一般情况下，任何一个 即，k ，d 】码的一致检验矩阵日可表示为： h = 扛抄1啊川 红川吃加2 j j l o 吃。 吨。一l 吨。一2 吃一邶 由此，可以很快地建立码的线性方程组： 确， 加， 吃一，l 1 一七一一2 盔，。1 f ，气一 烈： ( 2 3 ) ：0 t( 2 4 ) 矩阵日的每一行代表一个线性方程组的系数，它表示求一个校验元线性方程。若把矩阵日的每 一行看成一个矢量，则这疗一k 个矢量恰张成了刀维线性空间中的一个玎一尼维予空间圪。 因为i ，z ，七，d 1 码的每一个码字必须满足( 2 1 ) 式，所以它的每一个码字必然在由矩 阵日的行向量所张成的线性空间圪枞中的零空间中。显然圪m 的零空间是一个七维 子空间圪而这正是( ，2 ，后，d 】码的码字集合，因而，圪加。与【，2 ，尼，d 】码的每一个码字 均正交，也就是矩阵日的每一行与它的每一个码字的内积均为零。 l ，2 ，七，d 1 分组码的g 个码字组成一个七维子空间，因此这个码字完全可以由七个独 立矢量所组成的基底张成，设基底为 q = i 扩j ，g l 扩2 ，g l ，o ) c 2 。国2 一- l ，岛扩2 ，9 2 o ) ( 2 5 ) 龟= 饿, n - ig 一2 ，g 枷) 若把这组基底写成矩阵形式，则有 g = g l 。n l 9 2 ，一l g k p l 【疗，后，d 】码中的任意码字c 都可由这些基底的线性组合生成，即 c - m g = ( - l ，一2 ， fg l 一- ，一。l - - j , n - i 。 g l ，一2蜀，0 9 2 一一2 9 2 ，0 g k 一l 一一2。0 ( 2 6 ) ( 2 7 ) 其中珑= ( 书书，m n 一。) 是是个信息元组成的信息组。因此，若已知信息组小，通 过( 2 7 ) 可求得相应的码字，称( 2 7 ) 中的矩阵g 为【，2 ，尼，d 】码的生成矩阵。 6 矿 m 冉 山 蜀一 一 因为一个线性空间的基底不是唯一的，因此码的生成矩阵g 也可以不止有一种形 式，但不论哪一种形式，它们都生成相同的线性空间，即生成同一个f 船，k ，d 1 码。g 中 的每一行及其线性组合均为【玎，k ，d 】码的一个码字，所以由( 2 1 ) 式和( 2 2 ) 式可知 g h t = 0 ( 2 8 ) 或 日g t = 0 t( 2 9 ) 这说明由g 与日的行生成的线性空间互为零空间。 因为线性码由其生成矩阵完全确定，所以编码器的存储量可以大大减少，它不必 存储q 个( 指g 元码) 码向量，而只需存储生成矩阵的k 个行。对编码的基本要求是 编码设备越简单越好，线性空间是符合编码需要的良好的数学结构，一般而言，线性 码的编码是容易实现的，适当地选取生成矩阵可以进一步简化编码设备。 2 1 4 一般性质 定理2 1 4 1，z ，k ，d 1 线性分组码的最小距离等于其非零码字的最小重量，即 d = m i n w ( c ) ic i ，z ，k ，d l ，c 0 ) 因此，求线性码的最小距离就转化为求问题最小重量问题，该定理说明了线性码 的优越性。 码长n ，信息位的个数k 和最小距离d 是线性码最重要的三个参数，这三个参数 之间有一定的制约关系。研究码的纠错能力，分析码的n ，k ，d 之间的关系，不仅能从 理论上指出哪些码可以构造出，哪些码不能构造出，而且为工程实验提供了各种码性 能估计的理论依据。 给定玎和k 后，d 必须满足下列上限： 定理2 1 4 2 ( p l o t k i n 限) q 元i n ，k ，d 】码的最小距离d 满足 d 行q 卜1 ( 留- 1 ) ( q 一1 ) 。 定理2 1 4 3 ( s i n g l e t o n 限) 任意i n ，k ，d 】码的最小距离d 满足 d 疗一k + 1 。 以上两个上限定理说明，对于某些参数n ，k 和d 来说，【r , k ，d 】码是不存在的。 下面给出一个下限定理： 定理2 1 4 4 ( g i l b e r t v a r s h a m o v 限) 若下述不等式 ( 以：- 1 ) ( 鸟一，) + ( 厅2 1 ) ( q 一- ) 2 + + ( ：二：) ( g 一) d - 2 9 5 一 成立，则一定存在码长为甩，维数n s 且最小距离d 的g 元码。 定理2 1 4 4 说明好的线性码是存在的。 一 2 1 5 检错能力与纠错能力 定理2 1 5 1设c 是码长为n 的码，如果c 中任意两个码字的距离都，+ 1 ，那 7 么c 是可以检查出f 个差错的检错码。更进一步，如果c 中确有两个码字的距离等于 ，+ 1 ，那么c 不能检查出f + 1 个差错。 如果c 中任意两个码字的距离都2t + 1 ，那么c 是可以纠正f 个差错的纠错码。 更进一步，如果c 中确有两个码字的距离等于2 f + 1 ，那么c 不能纠正t + 1 个差错。 由定理2 1 5 1 可知，码的检错和纠错能力完全取决于其最小距离，再由定理 2 1 4 1 可知印，k ，d 】线性分组码的检错和纠错能力取决于其最小重量，我们有如下定 理。 定理2 1 5 2 设c 是一个g 元阮k ，d 】线性码，h 是它的一个校验矩阵。如果日的 任意t 列都线性无关，而日有t + 1 列线性相关，那么c 的最小重量等于t + l 。这时c 是 厂1 可以检查出，个差错的检错码，也是可以纠正i 1 个差错的纠错码，其中 l2l 阡 量，如果f 是偶数， 丁t - 1 ， 如果f 是奇数 在数字通信中，我们要根据具体的需要，选择码率高，纠错( 或检错) 能力强， 编码和译码都比较简单的码。 2 2线性移位寄存器序列 伪随机序列广泛应用于连续雷达波测距信号、遥控系统的遥控信号、多值通信的 地址信号、数字通信的群同步信号、保密通信的加密密钥等方面。 由于序列密码具有高效安全、实时性好以及加密和解密容易实现等特点，因此序 列密码在军事和外交等敏感领域中有着极其广泛的应用。序列密码的密钥序列主要采 用线性移位寄存器序列以及其变种序列，如前馈序列、非线性生成序列以及钟控序列 等等。 2 2 1 线性移位寄存器的组成及其工作原理 用符号 表示一个寄存器，它可以以q 个状态之一作为其状态，这g 个状态看作g f ( q ) 中的q 个 元素。 用符号生伊 表示一个来乘法器，它是一个开关电路，当输入为a 时，输出为f 口，这里ga g f ( q ) 。 用符号 1 2 h 表示一个加法器，它是一个由n 个输入端和一个输出端构成的开关电路，当玎个输入 端的输入分别是口l ，a2 ，a 。时( a l g f ( q ) ) ，输出端的输出是a i + 口2 + + 。下图 8 口 是一个q 元甩级线性移位寄存器的框图： 图中r 个小方框是，1 个寄存器，从左到右依次叫做第1 级、第2 级、第玎级寄存器。 假设开始时第1 级、第2 级、第以级寄存器的内容依次分别为“圳一：，口。， 我们就说这个移位寄存器的初始状态为( a o ，a l ，一。) 。当加上一个移位脉冲时，移位 寄存器就将每一级的内容移送给下一级，第玎级移出的内容就是输出，同时将各级的 内容送给相应的乘法器，而将加法器的输出 岛= 一( q 一1 + c 2 a , , 一2 + + 岛缅) 反馈到第1 级，这样该移位寄存器的状态就变成( a i ，晓，- l ，) ，而输出是口o 。 2 2 2 线性移位寄存器序列及其周期性 不断地给移位寄存器加移位脉冲，它的输出就是一个g 元序列 a b ，a l ，a2 ， ( 2 1 0 ) 该序列适合线性递归关系式 a k = 一岛砚巾露玎 ( 2 1 1 ) f ；1 该序列就叫做上述q 元胛级线性移位寄存器所产生的g 元n 级线性移位寄存器序列。它 之所以叫做线性的，是因为递归关系式( 2 1 1 ) 对于( 2 1 0 ) 来说是线性的。 显然留元，2 级线性移位寄存器序列( 2 1 0 ) 由其初始状态( a t ，a z ，儡，) 和递归 关系式( 2 1 1 ) 完全确定。 把多项式 厂( x ) = 1 + c i x + e a x 2 + + 岛妒 ( 2 1 2 ) 叫做前述g 元n 级线性移位寄存器的联接多项式。显然，( 2 1 2 ) 1 刍递归关系式( 2 1 1 ) 完 全确定，递归关系式( 2 1 1 ) 也由联接多项式( 2 1 2 ) 完全确定。因此，序列( 2 1 0 ) 也可以 由其初始状态( q ，a 2 ，_ ，q r ) 和联接多项式( 2 1 2 ) 完全确定。我们把适合递归关系式 ( 2 1 1 ) 的q 元砟级线性移位寄存器序列叫做由f ( x ) 产生的g 元甩级线性移位寄存器序 列。用符号g ( 厂) 来表示适合递归关系式( 2 1 1 ) 的q 元n 级线性移位寄存器序列的全体 组成的集合，则有： 定理2 2 2 设f ( x ) = 1 + 芝岛f 研x 】，那么l g ( 厂) i _ q ”，并且g ( f ) 可看作蜀上 的门维向量空间。 定义2 2 2设g = ) 函是有限域g f ( 口) 上的序列。如果存在正整数7 使 9 a t + t = a k ( 2 1 3 ) 对一切非负整数k 成立，那么称g 是周期序列。满足( 2 1 3 ) 的最小的正整数，叫 做g 的周期，记作p ( g ) ，即 p ( a ) = m i n l la m = a k ，对一切非负整数k 。 由q 元刀级移位寄存器产生的周期为g ”一l 的移位寄存器序列叫做g 元，2 级m 序 列。二元m 序列的主峰高度、副峰高度、自相关函数和互相关函数满足一系列 特性( 具体参见文献 1 9 】) ，因此雷达和声纳系统常采用m 序列调制成的信号来 进行测距。 由q 元刀级移位寄存器产生的周期为矿的移位寄存器序列叫做g 元拧级m 序 列，它是周期最大的q 元船级序列。m 序列具有很好的伪随机性【2 2 1 ，因而被广 泛地应用于保密通讯中，利用m 序列可以有效地保护原始信息。因此，研究如 何构造m 序列是一个非常有意义的问题，经典的构造方法主要有生成树法、剪 接法、算子法、并圈法等2 2 粕】。 1 0 第三章线性码的深度及其推广 3 1 研究的背景 微分算子最初是用来刻划和分析序列的线性复杂度的【2 7 ，28 1 ，1 9 9 7 年e t z i o n t 在文献【2 9 】中首次将微分算子应用到编码领域中，定义了二元域上码字的导 数，提出了二元域上码字的深度和深度谱的概念，研究了码的深度分布和码字 深度的一些性质，给出了一个计算二元域上码字深度的递归算法，并利用深度 分布给出了构造新码的方法和码的一种新的等价分类方法，即按深度等价进行 分类，码的深度问题的研究引起了国内外很多学者的广泛关注 2 9 - 3 5 】。m i t c h e l l 在文献 3 0 】中研究了二元线性循环码的深度分布；l u o 在文献【3 1 】中给出了计算 有限域c 上线性码码字深度的算法。文献 3 2 】将纠错码的深度分布与周期分布 建立联系，对于码长为2 的幂次的线性码，给出了利用深度分布求周期分布的 方法，并确定了码长为2 的幂次的扩展汉明码和扩展循环码的周期分布。 上述码的深度分布问题的研究都局限在有限域上。近年来，随着有限域上 编码理论的日趋完善，国内外从事编码理论研究的学者逐渐将研究的热点转移 到环上的编码理论。文献 3 3 】定义了有限环乙上码字的深度和码的深度分布， 研究了z 4 上线性码和线性循环码的性质，并指出了有限域上码的深度分布的某 些理论在有限环是不成立的。朱士信等在文献 3 4 3 6 】中定义了有限环上线性码 的深度、深度分布和深度谱的概念，建立了有限环上线性码的深度分布理论。 文献 3 4 ，3 5 进一步研究了乙环上的线性码与线性循环码的深度谱，文献【3 6 】研 究了有限环z 矿上码字深度的若干性质并给出了两种计算环z ，上码字深度的 递归算法。基于有限域和有限环上线性码的深度分布理论，朱士信等定义了码 字广度、广度分布和广度谱的概念，研究了有限环z 4 上码字广度的性质以及z 4 上码字的广度分布，并给出了计算z 4 上码字广度的两种有效的递归算法。由于 有限域g f ( 2 ) 上运算的特殊性，g f ( 2 ) 上码字的广度就是码字的深度，因此，码 字的广度实际上是码字的深度概念的一种推广。本文研究了有限环昂+ u f p 和有 限环z 矿上码字广度的性质及其算法。 3 2有限域上线性码的深度分布及其应用 3 2 1 基本概念 对于有限域f = g f ( q ) 上的字x = ( x l ，x 2 ，) ，定义算子d 为 j d ( x ) = ( 吻一x l ，x 3 一而，矗一毛一i ) 称d 为x 的导数，不难验证d 是一个线性算子，即对任意x ，y f ”，t t t f 都有 d ( x + j ，) = d ( x ) + d ( y ) ，d ( a x ) = c t d ( x ) 。 定义3 2 1 1 【3 1 1 设x f ”，称使得d 。x = 【0 ”】成立的最小非负整数为向量x 的深度，记为d e p t h ( x ) ，如果没有这样的f 存在，则规定d e p t h ( x ) = 聆。 为了方便表述，把分量全是口的聊维行向量( 口，矾，口) 记为 口”】。由深度的 定义可知，对于长为厅的码字c 来说，d e p t h ( x ) = f 当且仅当存在0 口f 使得 d 1 c ：k 肿1 。，】，显然，2 长码字的深度不超过聆。 定义3 2 1 2 1 3s 】给定一个长为刀的码c ，设口表示深度为f 的码字的个数， 则称集合 d n ，口，见 为码c 的深度分布。 定义3 2 1 3 【3 1 】对于g f ( q ) 上的 玎，明线性码c ，设其深度分布为 或，d 1 ，包) ，则称指标集 i l l f ，z ，d f 0 ) 为码c 的深度谱。 定理3 2 1 1 【2 9 1【1 7 , k 】线性码的非零码字的的深度分布恰包含七个非零值。 定理3 2 1 2 【2 9 l g f ( q ) 上【聆，k 】线性码c 的任意k 个具有不同的非零深度值 的码字可构成c 的生成矩阵。 3 2 2 g f ( q ) 上码字深度的算法 设4 = ( ) 酬。1 ) 是卵( g ) 上的矩阵，其中 嘞。- - i , f = i = ，j + 1 10 ，其它 则对任意x = ( 而，x 2 ，矗) f ”，x 的导数可表示为d x = x 4 ，。设 q ( f ) = 4 4 ，一。一4 叭。 其中1 i 胛一1 ，规定q ( 0 ) = l ( 厶表示单位矩阵) ，q ( 玎) 是n x o 的空矩阵，那 么x 的第i 阶导数可表示为d 7 ) = x q ( f ) ，因而d e p t h ( x ) 就是使x q ( f ) = 【0 ”。】成 立的最小非负整数，如果不存在这样的i 则规定d e p t h ( x ) = 玎。 命题3 2 2 1 【3 1 】对于1 i ，7 1 来说，矩阵q ( f ) 可以表示为 q ( f ) = l ： q 1 ： l 1 1 其中= ( 一1 ) 7r | ( m o d p ) ，_ ，= 0 , 1 ，i ，p 是g f ( q ) 的特征。 ， 命题3 2 2 2 【3 1 1 对；= ( 鼍，屯，磊，x n + 1 ) f 川，若x = ( ，x 2 ，吒) f ”的深度 为m ，则 喇砷m 如融+ l + o t a 否则x , _ 1 + + + l 乩。 l 聆+ 1 ，白姒u 由命题3 2 2 2 可得计算叩( g ) 上码字深度的一个算法： 算法3 2 2 1 3 1 1 对任意z = 瓴，恐，；毛) p ，设玉l ，】= 瓴，毛) ，谚= d e p t 而o , ( 】) ，f = 1 2 ； 1 ，2 ，”o ( 1 ) 若x l = 0 ，贝4d l = 0 ；若x 1 0 ，则碣= 1 。 ( 2 ) 假设z 已经算出，那么 j j ，z ， 如取+ l + l t + + + 4 珥