（基础数学专业论文）深度的算法及其复杂性分析.pdf

硕士学位论文 m a s t e r s t h e s i s 中文摘要 在2 0 0 0 年，l u oy u a n 等人给出了有限域上字的深度的两个算法，按照深度的 定义还有个深度的算法。本文首先对模p 剩余系上字的深度的这三个算法的复杂 性做了分析，计算了它们在最坏情况下的复杂性和平均复杂性本文进步推广了 l o u 的算法，给出了模矿剩余类环上字的深度的三个算法，也计算了它们在最坏情 况下的复杂性和平均复杂性本文对这六个算法给出了相应的v c 程序运行之后， 我们得到关于素数，字长，深度和运算次数的四组数据最后用m a t h e m a t i c a 对这 些数据进行拟合得到了函数图像和函数关系式，然后把试验结果和前面理论分析的 结果进行了比较 关键词；算法；复杂性；深度 硕士学位论文 m a s q ：x 甜s t h e s i s a b s t t a c t l u oy u a uh a d 舀v e ut w oa l g o r i t h m sa b o u td e p t ho fc o d e so v e rg f , q ) i n2 0 0 0 ， w ec a na l s og e tk u o t h e ra l g o r i t h mf z o mt h ed e 血z i t i o ni nt h i sp a p e r ，w eh a v e a n a l y s e dt h ec o m p l e x i t yo ft h i st h r e ea l g o r i t h m sw ec o m p u t et h ec o m p l e x i t yi n t h ew o r s tc o n d i t i o na n da v e r a g ec o n d i t i o n t h ea l g o r i t h m sw h i c h 舯b yl o uh a 8 b e e ne 虹e n d e dt o2 口2i nt h i sp a p e ra n dt h e nw ec o m p u t et h ec o m p l e ：4 t yi nt h e w o r s tc o n d i t i o na n da v e r a g ec o n d i t i o n t h e nw eh a v ew r o t ev c p r o g r a n lf o rt h i ss i x a l g o r i t h m s w eo b t a i nas e r i e $ 硝d a t aw eh a v ec a r r i e do u tt h ee x p e r i m e n tr e s u l t a n dt h e o r yr e s u l tc o m p a r i n g k e y w o r d s ：a l g o r i t h m ；c o m p l e x i t y ；d e p t h i i 硕士学位论文 m a s t er s t h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：名t l 兰兰日期：护7 年夕月z - 7 1 a 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：锄j 兰兰 喊刀年 月l 7 日 导师签名：鬯睁 日期：d 7 年厂月碣日 本人已经认真阅读。c a l l s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程” 中的规定享受相关权益。回壶途塞逞童卮溢蜃! 旦圭生；旦= 生 旦三生筮查! 作者签名：毒i l 兰兰 日期：0 7 年夕月1 7 日 日 r 罨月t ， 毙严 弘 。 签 ：师期 b 丁日 硕士学位论文 m _ a s t e r s t h e s i s 第一章引言 编码理论与信息论大约同时在4 0 年代后期由h a m m i n g ，s h a n n o n 等人f 1 0 - 1 4 而创立的上世纪5 0 年代至上世纪6 0 年代初，科学家们主要研究各种有效的编译 码方法 1 9 9 7 年t e t i z o n 首先在文献【1 】中将微分用在线性码中给出了线性码深度的 概念和线性码深度分布的概念，并且证明了k 维的线性码恰有k 个不同的深度值， 在文献【2 】中l o uy u a n 还给出了计算有限域上线性码的深度的两个算法到上世纪 9 0 年代，随着有限域上编码理论的发展日益成熟，科学家们将注意力集中到环上线 性码的研究上来1 9 9 4 年a r o g e rh a m m o n s ，p v i j a yk u l n a r ，a r c a l d e r b a n k ， n j a s l o a n e ，p a t r i c ks o l e 合作的文献【1 9 】中是篇研究环上线性码的重要文献 他们得到了互上的码在g r a y 映射下的二元象，引起了许多学者对环上线性码的 兴趣j w o l f m a n n 在文献【2 1 2 2 l 中证明了g r a y 的二元象保持循环移位不变的性 质，同时还得到了个四元循环码的二元g r a y 象是线性的，则其二元象就是二元 线性循环码之后在2 0 0 3 年s a nl i n g 和j a s o nt h r o i i i sb l a c k f o r d 在文献f 1 7 1 中将 刃一z 尹上的g r a y 映射推广到z 孙。一z 矿“ 复杂性的定义和算法复杂性( c o m p l e x i t y ) 的概念最早在2 0 世纪5 0 年代由 v o n n e u m a n n 提出，他认为这是2 0 世纪物理学需要解决的重大问题，后来由 k o l m o g o r o v 在文献用中给出了具体定义2 0 世纪7 0 年代l e m z i v 在信息理论的 研究中对复杂性给出了个定义2 0 世纪8 0 年代末期k a s p e r ，s c h u s t e r 对于l e m z i v 意义下的复杂性进行了研究，提出了随机序列复杂性测度的算法计算复杂性分为 时间复杂性和空间复杂性时间复杂性的减小通常是以空间复杂性的增大为代价的； 空简复杂性的减小也往往导致时间复杂性的增大不同的算法具有不同的时间复杂 性函数 本文首先对有限域上计算字的深度的三个已知算法的复杂性作了分析接着把 这三个算法推广到模p 2 剩余类耻，并且对环上的算法也作了复杂性分析对于上 述的六种算法，我们分别写出了它们的v c 程序每个程序可以按照相应的算法提 供的方法计算字的深度，而且记录计算过程中所用的运算次数具体的过程是：首 先我输入一个素数p 程序会随机产生个整数n 作为字的长度，然后在随机产生 个长为n 的磊或者是z 如上的字接下来计算这个字的深度和记录计算过程中 的运算次数运行这个程序之后可以得到关于素数p ，字长n ，深度d 和运算次数 的数据我们用m a t h e m a t i c a 对这些数据进行拟合得到了图像和函数关系式并且 把理论结果和实验结果进行了对比 1 硕士学位论文 m a s t e r s t h e s i s 本文的结构如下文章的第部分是引言介绍了字的深度计算和复杂性分析 的背景和意义第二部分，是本文的预备知识介绍了字的微分、深度、深度分布等 概念第三部分，本文首先介绍了文献( 2 j 中有限域上三个的计算深度的算法，接 下来计算了每一种算法的在最坏情况下的复杂性和平均复杂性以比较这些算法的好 坏第四部分，我们把有限域上深度的算法推广到的模矿剩余类环上。也得到了 关于环上字的深度的三个算法，我们证明了它的正确性，另外也给出了每一种算法 在最坏情况下的复杂性和平均复杂性第五部分，我们根据上面的算法写出v c 程 序，通过运行这些程序得到具体的关于字长、深度、计算次数等数据，接着又用用 m a t h e m u t i c a 软件对这些数据进行了分析，用函数来拟和并勉出了函数图像，对理 论结果和试验结果进行了比较 本文中的p 均为素数记，【口严l 是长为i n 分量全是a 的向量，本文所讨论的字 的长度均有限为n 2 硕士学位论文 m a s t er s t h e s i $ 第二章预备知识 定义2 1 令乃是模矿剩余类环，则z = ( 。l ，现，) 其中黾勿，i = 1 ，2 ，称为z 上的个字 定义2 2 令z = ( z l ，x 2 ，) 是筘的个字，映射e ：e ( x ) = ( z 2 ，如，) 成为z 的前截运算，映射g ：g ( z ) = ( x l ，x 2 ，) 称为z 的后截运算 定义2 3 令z 扣是模矿剩余类环，对= 0 l ，x 2 ，x 。) 2 定义z 的微分 为d z = ( z 2 一：g l ，一x 2 ，z n 一一1 ) 小r 。 对比z ? 有d x = z a 令仉( ) = 厶i t 一1 厶- l + 1 ，d ( 。) = z 瓯( i ) 因 此d e p t h ( x ) 是使得q 。( z ) = o - 一1 成立的最小非负整数，若这样的i 不存在则 d e p t h ( x 1 = n 约定l = 1 ，2 ，n 一1 q 。( i ) = a i o ： 知 啦0 一1 ) ： 1 啦“一1 ) 1 3 啦“一1 ) 1 硕士学位论文 m a s t e r s t h e s i s 其中 一c 一妒( ；) c m 庐叭，t 引理2 1 假设c 是g f ( q ) 上的线性码，c 的深度谱为d t ，d k 那么它的深度 分布为 现= 们i - - - ： 引理2 2 假设c 是z p 上的长为n 维数也为n 的字，c 的深度谱为0 ，1 ，l 那么它的深度分布为 皿= 兰一，n 4 硕士学位论文 m a s l m r s t h e s i s 第三章三个已知的算法及其分析 算法1 输入：b 上一个长度为嚣的序列。= 如1 ，现，) 输出：码字的深度d 和运算次数t i m s t e p l 先判断z l 是否为罨如果2 1 = 0 则d = 0 ，如果霉l 0 则d = 1 s t e p 2 我们已经知道了x 1 ，司= ( 2 1 ，2 2 ，墨) 的深度d f 我们可以来计算a d o x i + l + 1 戤+ + a & g x i + l 一函如果这个式子等于零则记反+ l = 杰如果这个式子不等于 零则最+ 1 = i + l s t e p 3 重复s t e p 2 当 n 停止 分析：计算每一组组合数所需要花费的时间复杂度为l + 3 + 5 + + 2 i 一1 = 铲 然后再计算o 戤+ 1 + a d 。i x i + + a & d ；x 件1 一d 这也又有个乘法因此又需要花费 画个时间复杂度，两部分合起来是他总的时间复杂度当这个码字在每一步的计算 中a & o z 件1 + l 以+ + a d 。& x 件1 一血均不为零时，这是计算机需要花费的时间最 长，是圣1 ( t 2 + 力= n + 1 ) ( 2 n + 1 ) 6 + n + 1 ) 2 = o ( 竹3 ) 对于这个算法它的计算次致与字的深度无关，而是只于字的长度有关因此对每 个字它所花费的时间是样的，复杂度都是0 ( n 3 ) 算法2 输入：昂上个长度为n 的序列z = ( x l ，2 2 ，z 。) 输出：码字的深度d 和运算次数t i m s t e p l 先判断( z 1 ，茹2 ，) 是否全为零，若全为零d = 0 停止，否则进行s t e p 2 s t e p 2 把巧+ 1 一赋值给巧得到n 一1 元的序列，重复s t e p l 同时d = d + 1 s t e p 3 当序列的长度为l 时即只剩下若z i 0 则d = n ，若2 1 = 0 则d = n 一1 分析：第一步我们首先要判断z 1 ，x 2 ，z 。是否全为零这需要n 步，第二步要判 断勋一z l ，z 。一2 n 一1 是否全为零这需要n 一1 步，以此类推，我们计算个码 字的深度最多需要做到笫n 步，因此加起来共需要做坦譬坦此判断，所以最坏复杂 度为毕= o ( n 2 ) 对于个长为n 的g f ( q ) 上的字，由引理2 1 知它的深度分布为 取：1 0 ip i p l “i = 1 ，n 如果深度为i 那么需要判断z = ( 。1 ，x 2 ，) 判断z 1 = ( 2 2 一z l ，一2 n 1 ) 一直到第共需要疗+ 一1 ) + + ( 咒一i ) = ( i + 1 ) n + 业2 坐所以要算出所 5 硕士学位论文 m a s l 飞r st h e s i s 有码字的平均复杂度 1l 厶n t ：o “+ 1 ) n - - 坐产( 矿一矿一1 ) ) = 詈( e ( i + 1 ) ( 一p i 一1 ) + i 0 + i ) 1 2 ) ( 矿一一1 ) 暑( 0 + 1 ) ( 一矿1 ) ) = 芳( 1 + 譬 + + 1 ) 矿) = 0 ( n 2 ) 算法3 输入：b 上个长度为n 的序列工= ( z l ，勋，) 输出：码字的深度d 和运算次数t i m s t e p l 算出m = i a x r l p 扎，r 为非负整数) 记= ( x l ，z 2 ，) ，= ( z l ，z 2 ，z 矿) ，名= ( z p ，r i + 1 一z 1 ，x n 一一矿) 就唧先判断o = ( z l ，z 2 ，z 。) 是否全为零，若全为零d ( z ) = 0 停止 s t e p 3 若。= 0 l ，勋，) 不全为零，若全相等则d ( o ) = 1 停止 s t e p 4 判断z = ( z 矿+ 1 一z 1 ，z 。一z 。矿) 若全为零那么d ( z ) = d ( y ) 把可赋值 给z 再回到x t e p l s t e p 5 判断。= ( 妒+ 1 一z 1 ，z 。一一妒) 若不全为零那么d ( x ) = d ( z ) + p f r i 把 2 赋值给o 再回到s t e p l 分析：我们假设矿 n 0 + 1 ) p m 其中0 s p 第一部分首先要看z = ( z l ，z 2 ，) 是否为零需要n 步，第二步要判断z 需要t i , 一p m 步，由假设s 矿 n n 停止 分析：计算每一组组合数所需要花费的时间复杂度为1 + 3 + 5 + + 2 i 一1 = 产 然后再计算a & o x i + 1 + o 血1 + + 也z i + l 一吨这也又有个乘法因此又需要花费 函个时间复杂度，两部分合起来是他总的时间复杂度当这个码字在每一步的计算 中咄。戤+ 1 + a d d x i + + a d 。& x i + l 一出均不为零时，这是计算机需要花费的时间最 长，是：i 妒+ i ) = n 0 + 1 ) ( 孰+ 1 ) 6 + n + 1 ) 2 = d ( 护) 对于这个算法它的计算次数与字的深度无关，而是只与字的长度有关因此对每 个字它所花费的时间是一样的，复杂度都是o ( n a ) 有定义可以得到下面的算法 算法2 输入z 上个长度为礼的序列z = ( 茁，x 2 ，z 。) 输出：码字的深度d 和运算次数t i m 8 硕士学位论文 m a s t e r s t h e s i s s t e p l 先判断( z “z 2 ，z 。) 是否全为零，若全为零d = 0 停止，否则进行s t e p 2 s t e p 2 把x j + l 一赋值给巧得到n 一1 元的序列，重复s t e p l 同时d = d + 1 时e 序列的长度为1 时即只剩下若z 1 0 则d = n 。若；t 1 = 0 则d = n 一1 分丰l 膏第一步我们首先要判断z 1 ，现，是否全为零这需要仃步，第二步要判 断z 2 一霉1 ，。一x n - i 是否全为零这需要n i 步，以此类推，我们计算个码 字的深度最多需要做到第n 步，因此加起来共需要做i ! 专业此判断，所以最坏复杂 度为哔= o ( n 2 ) 对于一个长为n 的g f ( q ) 上的字，由引理2 1 它的深度分布为 f 1 i = 0 51 一一1 i ：l ，嚣 如果深度为t 那么需要判断$ = ( z 1 ，z 2 ，z 。) 判断。1 = ( x 2 一x l ，霉。一一1 ) 一直到第共需要几+ 一1 ) + + 一i ) = ( i + 1 ) n + 亘业2 所以要算出所 有码字的平均复杂度 击( 函0 + l m + 学_ p i - 1 ) ) = 暑( 0 + 1 ) 一矿以) + i ( i + i ) 2 ) 一矿1 ) 素( e ( i + 1 ) ( 矿一矿- 1 ) ) = 芳( 1 + 等寻+ ( 竹+ 1 ) 矿) = o ( t z 2 ) 引理4 2 设z = ( z l ，勋，靠) 筘，矿= p l ，现，如，2 n - l - 1 ) ，如果d 卿 ( 矿) 仃，那么d e p t h ( = ) = c 坳危( z ) 证明：有深度的定义，显然d e p t h ( = ) e 讲h ( z ) ，现在需要证明d e 印h ( x ) 螂矗( z ) 令a l e p h ( = ) = k ，由于沙( 矿) = 时，o 】，若口0 那么却 ( 矿) = n + l ， 当o = 0 时d e p t h ( z + ) = d e 癣h ( a ) 所以命题得证 引理4 3 设。= 扛1 ，钇，) 经，矿= ( x l ，貌，拍) ，如果 d 印t 0 ) n ，那么d e p t h ( = 。) = d e ：h ( z ) ，如果却危( 矿) n ，那么d 印地( 矿) = 出砖矗和) 引理4 4 在q 。( p 细) 中 ( 1 ) o j 矿“当j 驴“一10 墨t p 一1 时， ( 穹) 三。埘， 9 硕士学位论文 m a s t e r s t h e s i s ( 2 ) 当j = 劫觚一10 t p 一1 时 ( 7 ) 三御c 耐， 其中删三l ( m o d p ) ，0 p 一1 证明：由组合数学，知 ，( ? ) 妒( = 1 ) ( ? ) 叫m 耐， t ( 善。) = p ( 善l 。) ( l 。) 一( 雾l 。) = 与筹瑞等鲁掣 ( 矿f - 一t ，) ；c 嘶， t ( 。) 三p c m 彬， 因为 在乙中可逆设其逆元为m t ，敌i 在z 中也可逆设其逆元为k ，我们有 仇三后( m o 勿) ，由上式我们知道 ( 雾。) 三州m 耐净肌c m 耐， 这样就得到了结论 1 0 硕士学位论文 m a s t e r st h e s i s 引理4 5 设z = ( z 1 ，x 2 ，x n ) 乃如果 n 则 d 矿”= ( 警o p $ 矿n 一1 + 1 ，+ 霹o p 帆酽一t 押一矿m ) 其中翻兰l ( m o d p ) ，0 碱 p 证明：由定理2 的结论可以直接得到 定理4 6 设z = ( x l ，x 2 ，) 是磊( c = p 0 1 纡矽皿= 1 ，2 ) ，上的个字， 由映射恍：z c z 五我们可以得到r 个字它们分另q 属于域上，那么z 的深度就 等于r 个字中深度最大的个 证明：由中国剩余定理知： 妒：z c z p ：- o 锄o o 孙，戤一( a i l ，) 是一个同构映射 对。求t 嬲我们可以得到职加c 舀c 叫( ：) 一，k c 叫( ：) 酬 那么它的个分量厶( 一1 ) l ：) 磁一t 对应的像是( 二( _ 1 ) ( ：) ，酐( ：) 骗) 的每一个分量都为零 把d t 的每个分量的像都列出来，再经过排列组合就得到r 个长为n 的字，这r 个 字分别是在锄- ，磊扣，z 上的射影，又由于前面的映射妒是个同构映 射，所以这r 个字均为零因此就得到了结论 由引理4 2 ，4 3 ，4 4 ，4 5 可以得到下面的算法 算法3 输入：z 上个长度为n 的序列互= ( z l ，勋，) 输出：码字的深度d 和运算次数t i m s t e p l 算出m = m 凹 r l 矿 吼r 为非负整数 记z = ( x l ，x 2 ，) ，可= ( z l ，z 2 ，和n ) ，z = ( e 警o p m i x i t , 2 ，, 一1 + l ，瑶。跳z 矿n l + f l p 2 f - i ) s t e p 2 先判断z = ( z l ，z 2 ，z 。) 是否全为零，若全为零d ( z ) = 0 停止 s t e p 3 若z = ( z 1 ，现，z 。) 不全为零，若全相等则d ( z ) = 1 停止 s t e p 4 判断z = ( 警讧m z 舻一- + 1 ，名o p 帆z 矿n 一- 押1 2 ，1 ) 若全为零那么d ( x ) = d ( y ) 用y 代替z 再回到s t e p l s t e p 5 判断z = ( 冬护帆帮一- + l ，乏“m $ i p “一- 佃一p “) 若不全为零那么d ( x ) = d ( z ) + p m 把。赋值给z 再回到s t e p l 硕士学位论文 m a s t er s t h e s i s 分析在这个算法中有内外两层循环我们假设s p n 0 + 1 ) p ”其中0 s 矿 由算法计算酊e p l 需要m ( m + 1 ) 步，接下来进行s t e p 2 ，3 判断钆x 2 ，是否全 部需要n 步，进行s t e p 4 ，5 判断z = ( 备腓z t p 一一t + l ，壤。肌印一l + 。一，一) 是否各个分量全为零，我们看到每一个分量的计算需要印一2 步这共需要( 印一 2 ) 铲( + 1 ) 一p ) 步，到这里共需要( 劬一2 ) 扩( m + 1 ) 一p 觚) + n ，因为我们要计算最 坏情况下的复杂性所以接下来的循环是进行s t e p 2 3 5 。有算法可以看到，是用z 代 替茹，那么所得到的结果也是用n p 撕代替几，用n 一劲拥代替礼一p 孙，即为 ( 印一2 ) 一劲细) + n 一矿“。每循环一次2 的长度就会减少个p 2 m 。如此循环一直 到z 的长度减到n p 一1 ) p 加，这是共需要( 3 v - 2 ) 一( p 一1 ) p 2 m ) + f l 一0 , - 2 ) p 加 上面加起来的和为渤一2 ) ( p 2 1 ) 一矿“) + 矿0 n + t ) + ( 3 p 一2 ) 铲( ”1 ) 一2 p 2 ”) + p 2 ( ”件1 ) 一矿”+ + ( 3 p 一2 ) ( 矿( r e + 1 ) 一( p 一1 ) p 2 ”) + 矿( “+ 1 ) 一( p 一2 ) ；p = 矿【仇+ ”( 3 p 一 1 ) p 一1 ) + 垡亏坐( 印+ 2 ) 矿8 ，接下来进行外层的循环即s t e p l ，2 3 ，4 ，这时m 变 成m 一1 ，也就是这循环在上面所得结果的基础上用p 觚代替p 2 ( m + 1 ) 用矿( m - 1 ) 代替矿8 ，得到p 加( 3 p i ) c o 一1 ) + 业( 3 p + 2 ) p 2 ( 1 ) 一直到变成零结果为 矿( 劬一1 ) 一1 ) + 坚i 止( 3 p + 2 ) ，我们把这些加起来得到 矿( ”1 ( 3 p 一1 ) 一1 ) + 垒笋( 劬+ 2 ) p 撕+ p 细( 劬一1 ) 函一1 ) + 生! 笋( 印+ 2 ) 矿( m - 1 ) + + 矿( 3 p 一1 ) ( p 一1 ) + 业；( 3 p + 2 ) = ( ( 3 p 一1 ) ( p 一1 ) f 一( 3 p 一1 ) ( p 一1 ) 2 ) 警 = o ( 矿”+ 4 ) 假设c 是z 上的码字，的深度谱为0 ，1 ，乱，这时利用上述算法来计算中 码字深度所需要的平均复杂度，我们假设正= a r 矿+ n r 一1 矿( r - 1 ) + + n 1 矿+ a o 那么在这个算法中第一部分需要判断n 矿，n 一矿次共要【( 砷+ 1 ) n 一 矿r ! 学】( 劬一2 ) ，第二部分要判断p 2 r 一矿( ，矿一2 p 2 ( 一，p 2 r 一口r 一1 矿( r 1 ) 共要a r l p 打一矿( r - 1 ) 生些掣2 ，以此类推，到第r + l 部分判断p 一1 ，p 一2 ，p a o 共要n o p 2 一型号业，把这些都加起来 ( 口r + 1 ) n 一矿掣+ a r l 矿一矿( r 一1 ) 墅毫掣+ + n o p 2 一塑鱼2 生盟 = ( 口r + 1 ) n + 一1 善尹+ + n o 矿一( 掣矿+ 生_ 工! ；= 王业矿( r - 1 + + 璺垒i ! 盟矿) = ( a r + 1 ) 礼+ 矿反一脚矿( 叶1 ，一旷! = f ! ；盟+ 矿( r 一1 ，生生堑2 2 卫生+ + ) ! f 等唑 ( 砷+ 1 ) n + ( 矿一1 ) 函一d r 矿( r + 1 ) 平均复杂度 专( ：l + l m + 酽一1 x 一嘞矿( r + 1 ) ) 铲o + 1 ) 一矿) = 沁+ 1 ) n n r 州j + ( 击：1 0 1 ) i 酽# h ，一矿) ( a t + 1 ) 礼+ n = d ( 铲+ 2 ) n ) = o ( p 2 n ) 硕士学位论文 m a s t e s t h e s i $ 第五章实验和实验数据分析 程序的运行过程如下：首先我输入个素数p 程序会随机生成个整数n 作为 字的长度，然后再随机生成个长为1 1 1 的码字，接下来计算它的深度以及记录他在 计算过程中所需要的运算次数我们得到了如下表关于素数p 、字长n 、深度d 和 运算次数的数据，用m a t h e m a t i e a 对这些数据作出分析我们可以得到以下的函数图 像及其及其函数关系式，在z p 和z 上算法1 和算法1 和算法2 和算法2 是一 样的。所以共有四组数据 p 7 34 37 12 33 77 31 14 78 31 96 12 98 3 n3 5 1 572 42 43 42 842 62 0 1 03 3 1 8 d3 51 572 42 43 42 842 62 01 03 31 8 运算次数 1 1 7 52 0 0 , t 22 41 1 0 27 5 31 26 4 3 3 7 88 71 0 4 93 0 11 4 7 3 3 1 33355771 l1 11 31 31 31 31 3 1 63 382 8 71 5 3 3 1 1 1 28 7 3 22 11 0 2 2 1 63 382 771 53 31 01 2873 22 11 02 2 2 6 91 5 4 87 21 1 1 06 03 0 91 5 8 11 6 51 9 58 4 6 31 4 7 96 2 71 3 56 8 7 557 7771 11 1 1 1 l l1 11 1 1 31 31 3 1 462 41 32 51 42 02 52 31 21 91 83 21 61 2 1 362 41 3 2 51 42 02 5 2 31 1 1 91 8 3 21 5 1 2 2 5 23 98 2 2 2 8 88 9 42 6 7 5 6 7 8 9 7 7 5 3 1 9 2 5 1 04 5 61 4 7 93 5 1 1 9 8 p 1 91 l2 37 91 72 34 13 79 72 971 31 31 7 n2 92 92 02 41 63 62 543 33 521 41 33 6 d2 92 92 0 2 41 6 3 62 543 33 521 41 33 6 运算次数 4 3 54 3 52 1 0 3 0 0 1 3 6 6 6 6 3 2 51 05 6 16 3 039 17 86 6 6 3571 11 11 91 92 32 32 92 33 172 91 9 2 62 54 34 61 93 64 84 12 71 83 2 3 3 1 13 91 2 2 62 54 34 61 93 64 84 12 71 83 23 31 13 91 2 3 2 5 3 0 0 9 0 31 0 3 51 7 1 6 3 01 1 2 88 2 0 3 5 1 1 5 34 9 6 5 2 85 57 8 0 7 2 硕士学位论文 m a s t e r st h e s i s 1 91 31 31 7 1 7 2 3 2 3 2 9 2 9 3 13 13 73 7 7 3 5 19 03 68 23 17 32 28 44 07 61 86 1 7 35 19 03 68 23 07 32 2 8 4 4 07 61 86 1 2 7 0 11 3 2 64 0 9 56 6 63 4 0 34 9 52 7 0 12 5 33 5 7 08 2 02 9 2 6 1 71 8 9 1 p 1 77 33 7 5 9 7 3 9 7 4 1 4 35 37 13 1 n81 22 73 263 12 8 1 3 1 12 31 4 d81 22 73 263 12 81 31 12 31 4 运算次数 2 3 87 2 67 3 0 61 1 9 6 61 1 01 0 9 1 08 0 4 29 0 8 5 7 04 5 9 81 8 2 33 335557771 11 11 11 11 13 7 1 l2 41 74 62 583 474 31 53 81 462 92 22 6 1 12 41 74 6 2 583 474 31 53 81 4 6 2 92 22 6 1 7 7 94 81 1 41 4 01 7 7 04 0 12 4 43 21 4 92 33 01 1 4 1 4 36 5 0 1 31 3 1 7 1 7 1 9 1 91 92 32 32 92 93 11 333 4 0 2 64 54 73 63 53 14 01 81 72 22 532 41 7 4 02 64 54 73 63 53 14 01 81 72 22 532 41 7 1 2 3 1 9 5 2 2 22 7 6 3 2 52 9 1 2 5 63 2 9 2 0 62 7 2 4 6 26 0 01 87 9 4 8 p 33 35 555 7 771 9 n9 58 93 27 45 69 87 56 14 9 9 42 5 d9 58 93 17 45 69 87 56 14 99 42 5 运算次数 3 5 24 0 64 9 55 9 8 9 3 46 8 2 48 8 2 41 9 9 92 9 4 0 5 2 5 9 2 46 0 0 51 11 31 31 l1 171 71 71 7 2 92 9 1 31 385 35 04 19 03 52 84 43 31 1 1 31 385 35 0 4 1 9 03 52 8 4 4 3 31 1 3 63 1 9 81 3 7 26 5 7 2 2 5 0 2 2 5 3 3 6 2 0 2 1 5 7 41 1 9 07 5 61 8 9 21 0 5 61 1 0 3 11 71 31 11 31 32 32 31 91 91 31 31 1 45 45 63 54 33 12 95 84 02 53 181 3 45 45 63 54 33 12 95 84 02 53 18 1 3 1 22 8 6 23 0 8 01 1 9 01 8 0 69 3 08 1 23 3 0 61 5 6 06 0 0 9 3 01 3 7 23 1 9 8 从上面的表格中可以发现绝大多数字的深度和字的长度是相等的，只有少数出 现不同这是因为，由引理2 1 可知在随机产生一个乙上的字的时候，其深度等 1 4 硕士学位论文 m a s t e r st h e s i s 于字长的概率为p - 。1 由引理2 2 可知在随机产生一个2 上的字的时候，其深度 等于字长的概率为2 茅 对于上表中所得到的数据，我们用m a t h e m a t i c s 用函数去拟合得到了函数关系 式和函数图像如下： 上图中我们用关于变量n 的函数去拟合得到9 ( 神= - 7 7 7 7 0 1 + 3 2 9 1 8 9 n 4 - o 7 7 7 5 0 h 24 - 0 3 3 7 4 4 n 3 我们发现算法以计算1 出来了最坏复杂度的结果d ( n 3 ) 一 致，此图形横坐标为字的长度纵坐标为运算次数 上图中我们用关于变量n 的函数去拟合得到9 ( 礼) = - - 5 8 1 6 1 8x 1 0 一“+ o 5 n + 0 5 n 2 发现结果和算法2 中的最坏复杂度的结果生专华= o ( 礼2 ) 致此图形横坐标 为字的长度纵坐标为运算次数 1 5 硕士学位论文 m a s t er st h e s i s 上图中我们用关于变量p ，n 的函数去拟合得到g ( p ，n ) = o 3 2 5 2 8 8 p n 发现结果 和算法3 中的最坏复杂度p n = 0 ( 册) 一致，此图形x 轴为字的长度y - 轴为z - 轴运算次数 上图中我们用关于交量矿，行的函数去拟舍得到岔p ，萄= 5 9 4 7 9 2 珏矿与算法3 中的复杂度d ( 礼护) 是一致的此图形x - 轴为字的长度y 轴为盔- 轴运算次数 1 6 硕士学位论文 m a s t e r s t h e s i s 参考文献 1 】e t i z o n t ”t h ed e p t hd i s t r i b u t i o n - an e wc h a r a c t e r i z a t i o nf o rl i n e a rc o d e s f j 】i e e e t r a n s i n f o r m t h e o r y , 4 3 ( 4 ) ：1 3 6 1 1 3 6 3 ，1 9 9 7 【2 】l u oy f uf w ，w e ik w ”o nt h ed e p t hd i s t r i b u t i o no f f i n e a rc o d e s 【j 】i e e et r a n s i n f o r m t h e o r y 4 6 2 1 9 7 0 2 2 0 3 ，2 0 0 0 1 3 】杨善林，朱士信，童宏”计算有限历环上码字深度的两种算 5 p 中国科学 技术大学学报，6 5 5 - 6 6 0 ，2 0 0 4 1 4 】m i t h e n c j ”o ni n t e g e r - v a l u e dr a t i o n a lp o l y n o m i a l sa n dd e p t hd i s t r i b u t i o n so f b i n a r yc o d e s ”i j 】i e e et r a n s i n f o r m t h e o r y 4 4 ( 7 ) 3 1 4 6 3 1 5 0 ，1 9 9 8 【5 1 j h v a nl i n t ”i n t r o d u c t i o nt oc o d i n gt h e o r y n e wy o r k s p r i n g e - v e r l a g ，1 9 8 2 【6 j 张振涛，杨义先，胡正名”关于线性码深度分布的研字p 北京邮电大学学报。6 8 - 7 2 ，2 0 0 2 【7 】k o l m o g o r o v a n ”t h r e ea p p r o a c h e st ot h eq u a n t i t a t i v ed e f i n i t i o no fi n f o r m a - t i o n 【j 】i n f o r mn a n 8 1 - 3 ，1 9 6 5 【8 1k a s p e r k ，s c h u s t e r h g ”e a s i l yc a l c u l a b l em e a s l 】r ef o rc o m p l e x i t yo fs p a t i a l e m p o r a lp a t t e r n ”【j j p h y s r e va ，3 6 - 8 4 3 ，1 9 8 7 9 jl e m p e l a ，z i v j o nc o m p l e x i t yo f f i n i t e se q u e n c e s ”阁i e e en i n f o r m t h e - o r y , 2 2 - 7 58 8 ，1 9 7 6 【1 0 】m j e c o l y , ”n o t e so nd i g i t a lc o d e i n g ”，p r o c i e e e v 0 1 3 7 ，6 5 7 , 1 9 4 9 【1 l 】m j e c o i y ，”b i n a r yc o d i n 矿，i e e et m n s i n f o r m t h e o r y , 2 4 - 2 8 ，1 9 5 4 1 1 2 】r ，w h a m m i n g ，”e r r o rd e t e c t i n ga n de r r o rc o r r e c t i n gc o d e s ，b e l ls y s t t e c h j ， v 0 1 2 9 ，1 4 1 6 0 ，1 9 5 0 【1 3 c e s h a n n o n ，”am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n ”，b e l ls y s t t e c h j ，3 9 4 2 3a n d6 2 3 - 6 5 6 ，1 9 4 8 1 7 硕士学位论文 m a s t e r 8t h e s i s 【1 4 c e s h a n n o n ，”c o m m u n i c a t l o nt h e