《分组等重码软件实验平台及其应用研究》由会员分享，可在线阅读，更多相关《分组等重码软件实验平台及其应用研究（85页珍藏版）》请在金锄头文库上搜索。
1、中国科学院成都计算机应用研究所 硕士学位论文 分组等重码软件实验平台及其应用研究 姓名：孙宣东 申请学位级别：硕士 专业：计算机应用 指导教师：王晓京 20030601 摘要 分组等重码软件实验平台及其应用研究 孙宣东( 计算机应用)导师：王晓京研究员 摘要 差错控制编码，也称纠错编码，是提高信息传输和存贮可靠性的一种最基本 最重要的手段，是计算机和信息安全领域的核心基础技术之一。近来，差错控制 编码与密码技术相结合，在信息安全领域也起到了举足轻重的作用“3 。此外，差 错控制编码的思想和技术在I T 技术的其它许多领域也都有广泛而重要的应用。 【3 】 分组等重码是纠错码中最基本的码类之一，
2、在理论上有重要的意义，引人注 目，5 0 年来国际上对此进行了不懈的研究，但与其它码类相比目前尚缺乏有效 的定性理论和构造性方法。因此至今进展甚微，举步维艰“。 在中科院成都计算所知识创新工程信息安全研究组的策划和指导下，迥于 目前广泛流行的理论演绎方法，我们特别提出了一种基于计算途径的分组等重码 研究方法，并且研制了基于这种算法途径的分组码距离性质软件实验平台。软件 实验平台的基本功能是： 验证理论上关于等重码的预期结果和性质，特别是 关于不同等重码的种种理论下界和上界。 利用软件平台可以产生的远比理论 推导更为丰富的多样性结果，通过归纳研究和演绎研究相结合的途径，从新的角 度推动关于等重码
3、结构理论进而非等重码结构理论的深入研究。我们的实验平台 产生了大量丰富而有趣的数据，大大拓展了过去的直观想象范围，其中许多计算 结果接近或达到目前国际上通过其它理论途径推导的已知结果，有的计算结果则 是首次发现m “附囊”嗍”。我们在软件实验平台产生的大量数据的研究基 础上，还提出了一种有效的构造性方法，并通过该方法实际产生出一组目前国际 上还没有人实现的( 2 1 ，2 ”1 ，2 ) 等重码和( 2 。，2 “) 无重量限制码，给出了 迄今为止已知的最好结果”驯”“。 为了更好地扩展基于P C 机计算途径的分组等重码研究，我们研究并提出了 分组等重码软件实验平台及其应用研究 并行化算法，并
4、准备在大型并行机器上作更大规模的扩展实验，期待尽快得到更 好的结果。此外，我们研究并提出了未来更加可行的网格计算实验平台的实现方 法，并打算率先在局域网上实现，取得经验和验证我们的算法后建立个人网站， 发挥网格计算的巨大优势来获得更多有意义的成果。为了更好地扩展基于计算途 径的分组等重码研究，我们研究并提出了P c 机算法的并行化并准备在大型并行 机器上作更大规模的实验。此外，我们研究并提出了未来更加可行的网格计算实 验平台的实现方法，并打算先在局域网上实现，取得经验和验证我们的算法后建 立个人网站，发挥网格计算的巨大优势来获得更多有意义的成果。 我们的实验平台构造的( 2 ，2 ) 无重量限
5、制码具有很强的纠错能力，本 文简要描述了使用( 1 2 8 ，6 4 ) 无重量限制码对A S C I I 码纠错编码和译码方法。相对 于传统纠错方法，我们的方法的方法产生的码字集纠错能力更强、编译码结构简 明，具有较高的应用价值，在各个方面诸如硬盘信息灾难恢复、数字通信、重要 数据的备份等各个领域都能得到广泛应用。另外我们在“基于数字子母章的新型 证件防伪与验证系统”中也应用了我们的等重分组码进行纠错编码；并且实现了 一个简单的将等重码隐藏在图象中的算法，这个图象隐藏算法还具有一定的通用 性，在我们建设个人网站时也得到了应用。 本文在研究前人方法的基础上，首先从分组等重码入手，提出了崭新的基
6、 于计算途径的编码结构研究方法，建立了和正在建立基于计算途径的软件实验平 台P c 版、并行计算版和网格计算版等系列的实验平台。通过我们的方法途径， 已经获得了一些迄今为止最好的结果和丰富的有价值的崭新实验数据。 诚然，由于时间等条件局限，我们的软件实验平台功能还不尽完善，我们 宁可将它看作仅仅是一项新的工作的开端。我们相信通过实验平台的进一步工 作，将继续得到更多的有关等重码构造的极有意义的性质并刷新国际范围得到最 好结果。其应用前景也引入入胜。 关键字：纠错码分组码等重码并行计算网格计算 A b s t r a c t3 T h e A p p l i c a t i o n a n dR
7、 e s e a r c ho f E x p e r i m e n t a lL o n g D i s t a n c e E l i c i t o rf o rG r o u p - d i v i d e d C o n s t a n t - w e i g h t C o d e s B y ：S u nx u a n d o n g ( C o m p u t e rA p p l i c a t i o n ) D i r e c t e db y ：P r o f W a n gX i a o j i n g A b s t r a c t T h e e r r o r
8、 - c o n t r o l l i n gc o d e ，w h i c h i sa l s oc a l l e d e r r o r - c o r r e c t i n gc o d e ，i s a n e s s e n t i a lm e a n st oi n c r e a s et h e r e l i a b i l i t yo f i n f o r m a t i o ns t o r a g ea n dt r a n s m i s s i o n , a n d i ti sa l s oo n eo f t h ec o r et e c h
9、 n o l o g yi nt h ef i e l d so f c o m p u t e r a n di n f o r m a t i o n s e c u r i t y C o m b i n e dw i t ht h ec i p h e rt e c h n o l o g y , i th a sr e c e n t l yb e e np l a y i n ga v e r yi m p o r t a n t r o l ei ni n f o r m a t i o ns e c u r i t y “1M o r e o v e r , t h ei d
10、e aa n dt e c h n o l o g yo fe r r o rc o n t r o l l i n g c a r tb e w i d e l y a n de f f e c t i v e l yu s e di nI Tt e c h n o l o g ya sw e l la sm a n yo t h e rf i e l d s “ A ss u c hab a s i co n e a m o n ga l l t h e e r r o r - c o r r e c t i n gc o d e s , t h eg r o u p d i v i d
11、e d c o n s t a n t - w e i i g h tc o d ei se s p e c i a l l yt h e o r e t i c a l l ys i g n i f i c a n ta n di sg e t t i n gg r e a tp u b l i c a t t e n t i o n I nt h ep a s t5 0y e a r s ，i n t e m a t i o n a lr e s e a r c hh a sb e e nm a d e u n r e m i t t i n g l yt o d e v e l o pi
12、 t H o w e v e r , c o m p a r e dw i t ha n y o t h e rc o d e s ，i ts t i l ll a c k so fe f f e c t i v e q u a l i t a t i v et h e o r i e sa n dc o n s t r u c t i o n a lm e t h o d s C o n s e q u e n t l y , b yf a rl i t t l ep r o g r e s s h a sb e e nm a d ea b o u ti ta n dw ea r ea l
13、w a y si nd i f f i c u l t i e s H e r ew es p e c i a l l yp u tf o r w a r dac a l c u l a t i o nb a s e dg r o u p - d i v i d e dc o n s t a n t - w e i g h t c o d ep r o d u c i n gm e t h o d ，w h i c hi sq u i t ed i f f e r e n tf r o mt h ew i d e l y p o p u l a r i z e d t h e o r e t
14、i c d e d u c t i v em e t h o da tp r e s e n t A n dw eh a v ea l s od e v e l o p e da ne x p e r i m e n t a lL o n g D i s t a n c eE l i c i t o rf o rC o n s t a n t w e i g h tc o d ep l a t f o r m ，w h i c hi sb a s e do nt h i sk i n do f a l g o r i t h m i cp a t h O u re x p e r i m e
15、n t a lp l a t f o r mh a sp r o d u c e dah u g en u m b e ro fv e r y i n t e r e s t i n gd a t a ，m o s to f w h i c ha r ev e r yc l o s et ot h eb e s to n e sk n o w nb yt h ew o r l d w h i l eD a r to f w h i c ha r ee v e nt h es a m e 弱t h eb e s to n e s n 9 9 。叫1 帕“9 9 拍小町 p 9 。“1 。1 p
16、“ “伽 B a s e do nt h es t u d yo n s u c hr e s e r v o i r so fd a t aw e a c q u i r e d ，a n e f f e c t i v e c o n s t r u c t i o n a lm e t h o dh a sb e e nr a i s e db yU S B ym e a n so ft h i s ，w eh a v ep r o d u c e da g r o u po f ( 2 ，2 ，2 1 - 1 ) c o n s t a n t w e i g h tc o d ea n d ( 2 ，2 。) w e i g h t u n l i m i t e dc o d e a S w e l la st h eb e s tr e s u l t sw eh a v ee v e rg o t ，w h i c ha n yo t h e r si nt h ew o r l
