（计算机应用技术专业论文）基于组合学的数据编码方法研究.pdf

。一。 c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f d e n g r e s e r c ho nd a t a c o d i n g m e t h o db a s e d j _ -1 0 nl o m b i n a t o r i c s c a n d i d a t e ：l uj u n s u p e r v i s o r ：p r o f l i ud a x i n a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： d o c t o ro fe n g i n e e r i n g c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a r c h ，2 0 1 0 j u n ，2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i t y 。 一 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。7 作者( 签字) ：伤半 日期： 耖1 0 年月1 0 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文、( 口在授予学位后即可口在授予学位1 2 个月后 口解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者c ：书平 日期：纱f 年厂月扣日 导师c 签专h 鼠七吻 力i 口年加p 日 - ， 基于组合学的数据编码方法研究 摘要 在信息技术迅猛发展的今天，数据编码技术广泛应用在计算机、多媒体 和通信等多门学科领域，成为基本工具和基础研究问题之_ ，在各类研究和 应用的发展中扮演重要角色。本文提出一种基于组合学的数据编码新方法， 简称组合编码，它根据自身性质和优势，可以在数据压缩、数据保密等多个 领域发挥作用，对于信息的处理和存储传输具有重要意义。 组合编码方法是根据组合学原理，利用字符序列空间与其序数空间的关 系进行编码。该方法需要编码与解码双方预先约定一个基准序列，编码时可 以根据该基准序列计算出序列对应的序数，解码时则可以根据该基准序列由 序数回推出原序列。序数计算是组合编码的技术关键。本文对序数性质进行 了研究：序数取值取决于基准序列；序数大小取决于字符频率分布。 由于组合编码方法涉及的运算量很大，因此本文研究了相应的旨在提高 运算效率的优化算法。分析了不同数迸制对序数计算速度的影响，发现数进 制长度与运算速度基本成正比。本文还采用比例运算以替换计算量庞大的排 列组合运算，推导出相应迭代公式，优化了序数计算过程，减少了运算量， 从而提高了序数计算速度。此外，还对某些特殊情况进行了研究。总之，优 化算法提高了组合编码方法的运算效率。 为了进一步提高组合编码运算效率，提出了并行技术。有两种并行编码 方法：段内并行编码和段间并行编码。段内并行主要采用多线程技术实现， 其关键技术是对序列进行拆分；段间并行算法主要是针对多处理机进行了初 步探讨。 组合编码技术可用于多个领域的研究与应用。本文利用组合编码中有关 序数空间小于序列空间这一性质对数据进行压缩，即当原序列长度与序数长 度之间所节省字节足以抵消字符频率表及其它辅助信息空间时，便可以进行 组合压缩。组合压缩技术充分体现有重复即有冗余这一事实。为了便于实验， 需要选取一个合适的分段长度。为此对内容无规律的随机文件中分段字符频 率分布规律进行了研究，该研究对于频率表的压缩优化乃至整个组合压缩技 术的实现起到关键作用。 本文还研究了组合压缩与算术压缩、字典压缩之间的关系。组合压缩是 一种结合算术压缩技术的字典压缩方法，是一种不依赖概率统计特性的通用 压缩技术。它适用于压缩无记忆信源，特别适合压缩字符频率相近的无记忆 信源。理论分析表明当序列长度足够大时，组合压缩比字典压缩更加逼近压 哈尔滨工稃大学博十学位论文 缩极限。该压缩技术配合其它压缩方法可以使最终压缩效果更逼近信息熵， 在一定空间下能够尽可能多的存储数据，节省资源。 有关组合编码方法的研究，今后的工作还有很多，特别是优化技术和并 行算法设计，在加密解密等其它应用方面也有很大扩展空间。 关键词：数据编码：组合编码；数据压缩；无损压缩：组合压缩： a b s t r a c t d e v e l o p i n ga l o n gw i t h t h ei n f o r m a t i o nt e c h n o l o g y , d a t ac o d i n gt e c h n o l o g y ， a c t i v ei nv a r i o u sf i e l d s s u c h a s c o m p u t e r s c i e n c e ， m u l t i m e d i aa n d c o m m u n i c a t i o n s 。h a sb e c o m eab a s i ct o o la n do n eo ft h eb a s a lp r o b l e m st os t u d y i tn o wd l a y sa ni m p o r t a n tr o l ei na l lk i n d so fs t u d i e sa n da p p l i c a t i o n s b a s e do n t h et h e o r yo fc o m b i n a t o r i c s ，an e wc o d i n gm e t h o d - c o m b i n a t o r i c sc o d i n gl sp l l t f o n ) l ，a r di nt l l i sd i s s e r t a t i o n d u et oi t su n i q u ep r o p e r t i e sa n da d v a n t a g e s ，i t i s a p p l i c a b l ei nv a r i o u sf i e l d ss u c ha sd a t ac o m p r e s s i o n ，d a t as e c r e c y , a n ds oo n - i t l s o fg r e a ts i g n i f i c a n c et oi n f o r m a t i o nd i s p o s i n g ，d a t as t o r a g e ，a n dd a t at r a n s m a s s l o n c o i n b i n a t o r i c sc o d i n gr e f e r s t ot h ec o d i n gm e t h o dt h a ti sb a s e do nt h e c o n l b i n a t o r i c st h e o r ya n dm a k e su s eo ft h er e l a t i o nb e t w e e nt h es p a c eo f t h e o r d i n a ln u i l l b e ra n dt h es p a c eo ft h es e q u e n c e t h i sm e t h o dr e q u i r e sa b e n c h m a r k s e q u e n c et h a ti sa g r e e do nb yt h ec o d e ra n dt h ed e c o d e r b a s e do nt h es a m e b e n c h m a r ks e q u e n c e ，a l lo r d i n a ln u m b e rc o r r e s p o n d i n gt ot h ec h a r a c t e rs e q u e n c e i sc o m p u t e di nt h ec o d i n gp r o c e s sa n dt h ep r i m a r yc h a r a c t e rs e q u e n c ei sd e d u c e d 舶mt 1 1 eo r d i n a ln u m b e ri nt h ed e c o d i n gp r o c e s s o r d i n a ln u m b e rc o m p u t i n gi s t h ec o r ei nt h ec o m b i n a t o r i c sc o d i n gt e c h n o l o g y t h e r e f o r e ，t h ep r o p e r t yo ft h e o r d i n a ln u m b e ri ss t u d i e di nt h i sd i s s e r t a t i o n i ta r g u e st h a tt h ev a l u eo f t h eo r d i n a l n u n l b e rl i e si nt h eb e n c h m a r ks e q u e n c ea n dt h es i z eo ft h eo r d i n a ln u m b e r l i e si n t h ed i s t r i b u t i o no ft h ec h a r a c t e rf r e q u e n c y b e c a u s eo ft h eh u g ec o m p u t i n gq u a n t i t yi nt h ec o m b i n a t o r i c sc o d i n gm e t h o d ， t h et e c h n o l o g yo ft i m eo p t i m i z a t i o ni sp u tf o r w a r dt oi m p r o v et h ec o m p u t m g e f f i c i e n c y a tf i r s t ，n u m b e rs y s t e mi n f e c t i o n t oo r d i n a ln u m b e rc o m p u t i n gi s s t l l d i e di nt h i sd i s s e r t a t i o n i tf i n d so u tt h a tc o m p u t i n gw o r dl e n g t hr e l a t e dt o n u m b e rs y s t e md i r e c t sr a t i ot oc o m p u t i n gs p e e d i no r d i n a ln u m b e rc o m p u t i n g m o r e o v e r , t h ep r o p o r t i o nc o m p u t i n gm e t h o d i sa d o p t e dt or e p l a c et h ep e r m u t a t m n a n dc o m b i n a t i o nc o m p u t i n gm e t h o dw h o s ec o m p u t i n gq u a n t i t yl sh u g e s o m e p r o p o r t i o nf o r m u l a sa r ea l s oe d u c e d a sa r e s u l t ，t h ep r o c e d u r eo fo r d i n a ln u m b e r 哈尔滨丁程大学博十学何论文 i l l c o m p u t l n gi so p t i m i z e db yt h ep r o p o r t i o nc o m p u t i n gm e t h o da n dt h ec o m p u t i n g q u a n t i t y i s r e d u c e d ，t h u sa d v a n c i n gt h eo r d i n a l n u m b e rc o m p u t i n g s p e e d t u r t h e r m o r e ，s o m es p e c i a lc a s e sb e ec l o s e l ye x a m i n e d i naw o r d t h e s eo p t i m i z e d a i g o r i t h m si m p r o v et h ec o m p u t i n ge f f i c i e n c y o ft h ee o m b i r r a t o r i e s c o d i n gm e t h o d t of u r t h e ri m p r o v ec o m p u t i n ge f f i c i e n c y , t h i sd i s s e r t a t i o n p u t sf o r w a r dt h e p a r a l l e lt e c h n o l o g y t h e r ea r et w ok i n d so fp a r a l l e l m e t h o d s ：p a r a l l e lc o d i n g w i t h i nt h es e c t i o na n dp a r a l l e l c o d i n ga m o n gs e c t i o n s f o rt 1 1 ef i r s tm e t h o d m u l t i - t h r e a dt e c h n o l o g yi s a d o p t e da n dt h ek e yt e c h n o l o g yi sh o wt o s p l i tt h e s e q u e n c e f o rt h es e c o n dm e t h o d ，t h ep r i m a r ys t u d yi sm a d ei nt h ec a s eo ft 1 1 e m u l t i c o m p u t e r t h es t u d ya n da p p l i c a t i o no ft h ec o m b i n a t o r i c sc o d i n gt e c h n o l o g yc a nb e u s e di nm a n yf i e l d s t h ec h a r a c t e ri nt h ec o m b i n a t o r i c s c o d i n gt e c h n o l o g yt h a tt h e o r d i n a ln u m b e rs p a c ei ss m a l l e rt h a nt h es e q u e n c es p a c et oc o m p r e s sd a t a i sm a d e u s eo fi nt h i sd i s s e r t a t i o n t h a ti st os a y , w h e nt h es a v e dc h a r a c t e rs p a c ef r o m t h e s e q u e n c el e n g t ha n dt h eo r d i n a ln u m b e rl e n g t hc o u n t e r a c t st h es p a c eo c c u p i e db v t h e f r e q u e n c y t a b l ea n do t h e r a f f i x a t i o n i n f o r m a t i o n ，m ec o m b i n a t o c s c o m p r e s s l o nc a nb ea p p l i e d t h ec o m b i n a t o r i c sc o m p r e s s i o nt e c h n o l o g yf u l l v d e m o n s t r a t e st h ef a c tt h a ti fo n l yr e p e t i t i o ne x i s t s ，r e d u n d a n c yi si n e v i t a b l e t 0 b e t t e rf a c i l i t a t et h ee x p e r i m e n t ，as u i t a b l es u b s e c t i o nl e n g t hi s r e q u i r e d t h e r e f o r e t h er e s e a r c hb e g i n sw i t ht h es t u d yo nt h ed i s t r i b u t i n gr u l eo f t h es u b s e c t i o nb y t e f r e q u e n c yi ns t o c h a s t i cf i l e t h i s s t u d yi st h ek e yt ot h ef f e q u e n vt 2 l b l e c o m p r e s s l o no p t i m i z a t i o na n de v e nt ot h er e a l i z a t i o no ft h e c o m b i n a t o r i c s c o m p r e s s i o nt e c h n o l o g y t h er e l a t i o n a m o n gt h ec o m b i n a t o r i c s c o m p r e s s i o n t h ea l g o r i t h r n c o m p r e s s l o n ，a n dt h ed i c t i o n a r yc o m p r e s s i o ni sa l s os t u d i e di nt h i sd i s s e r t a t i o n t h ec o m b i n a t o r i c sc o m p r e s s i o ni sak i n do f d i c t i o n a r yc o m p r e s s i o nt h a tb e 卸滔t h e c h a r a c t e r i s t i co ft h e a l g o r i t h mc o m p r e s s i o r i i ti sau n i v e r s a i c o m p r e s s i o n t e c h n o l o g yi n d e p e n d e n to ft h ep r o b a b i l i t yc h a r a c t e r i s t i c s i tc a nb ea d o p t e dt o c o m p r e s sm e m o r y l e s s s o u r c e ，e s p e c i a l l ym e m o r y l e s ss o u r c ew i t hs i m i l a r c h a r a c t e rf r e q u e n c i e s t h e o r ya n a l y s i si n d i c a t e st h a tw h e nt h es e q u e n c el e n g t hi s 基j 组合学的数据编码万法研冗 b i ge n o u g h ，t h e c o m b i n a t o r i c s c o m p r e s s i o n c o m e sm u c hn e a r e rt ot h e c o m p r e s s i o nl i m i t t h a nt h ed i r e c t o r y c o m p r e s s i o n c o o p e r a t i n g w i t ho t h e r c o m p r e s s i o nm e t h o d s ，t h i sc o m p r e s s i o nm e t h o d c a nm a k et h ec o m p r e s s i o n e f f i c i e n c ya p p r o a c hi n f o r m a t i o ne n t r o p ya n ds t o r ea sm a n yd a t aa sp o s s i b l ei nt h e g i v e ns p a c e c o n s e q u e n t l yi tc a ns a v em a n y r e s o u r c e s d e s p i t et h em e t h o dp u tf o r w a r di nt h i sd i s s e r t a t i o n ，m u c hr o o mi s l e f t f o r f u t u r es t u d yi nt h ec o m b i n a t o r i c sc o m p r e s s i o n ，e s p e c i a l l yi nt h eo p t i m i z a t i o n t e c h n o l o g ya n dt h ep a r a l l e lt e c h n o l o g y t h e r ei s a l s om u c hs p a c ef o rf u t u r e e x p l o r a t i o ni no t h e ra p p l i c a t i o n ss u c ha se n c r y p t i o na n dd e c r y p t i o n k e yw o r d s ：d a t ac o d i n g ：c o m b i n a t o r i c sc o d i n g ：d a t ac o m p r e s s i o n ：l o s s l e s s c o m p r e s s i o n ：c o m b i n a t o r i c sc o m p r e s s i o n l 基于组合学的数据编码方法研究 目录 第1 章绪论1 1 1 引言一1 1 2 编码技术概述3 1 2 1 编码技术3 1 2 2 数据压缩编码5 1 3 海量历史数据压缩的需求8 1 4 本文的研究内容和组织结构9 第2 章信息熵理论和主要压缩编码方法1 2 2 1 信息熵理论1 2 2 2 统计编码- 1 4 2 2 1 哈夫曼编码1 5 2 2 2g o l o m b 编码16 2 2 3 游程编码17 2 2 4 算术编码17 2 2 5 基于字典的编码1 9 2 3 预测编码2 4 2 3 1d p c m 基本原理2 4 2 3 2 语音信号的预测编码2 4 2 3 3 图像的预测编码2 5 2 4 变换编码”2 6 2 5 分析综合编码“2 7 2 6 本章小结一2 8 第3 章基于组合学的数据编码方法2 9 3 1 基于组合学的数据编码方法基本思想2 9 哈尔滨t 稃大学博十学位论文 3 1 1 组合编码方法基本概念2 9 3 1 2 组合编码方法基本思路3 2 3 2 序数计算公式的推导3 3 3 3 最大序数计算公式的推导3 5 3 4 实例分析3 7 3 4 1 按样品频率降序计算序数3 9 ， 3 4 2 样品频率降序情况下的序列回推4 l 3 4 3 样品排列顺序对序数的影响4 4 3 5 组合编码全局最大序数研究4 6 3 6 本章小结5 5 第4 章组合编码方法的优化技术5 6 4 1 不同数进制对运算速度的影响”5 6 4 2 合并简化计算一5 8 4 2 1 求解当前字符前面各字符排列组合值之和5 8 4 2 2 第一个假设字符的排列组合值5 9 4 2 3 特殊情况的处理6 1 4 2 4 实例的合并简化6 2 4 2 5 优化算法比较分析6 5 4 2 6 比例计算的实现7 0 4 3 本章小结“7 3 第5 章组合编码并行技术研究7 4 5 1 并行计算与并行压缩编码 5 2 组合编码方法的段内并行编码技术 5 2 1 分组串行 5 2 2 分组并行 5 2 3 并行计算的相关与冲突及其进一步优化 5 3 组合编码方法的段间并行编码技术 ， 基于组合学的数据编码方法研究 5 4 本章小结8 5 第6 章组合编码应用技术研究8 6 6 1 问题提出8 6 6 2 组合压缩方法研究”8 8 6 3 组合压缩与字典压缩比较分析”9 4 6 4 组合编码在保密编码中的潜在应用1 0 3 6 4 1 分组密码设计准则”1 0 4 6 4 2 组合加密”1 0 5 6 5 组合编码在信道编码中的潜在应用1 0 8 6 6 本章小结1 11 结论= 一11 2 参考文献1 1 4 攻读博士学位期间发表的论文和取得的科研成果1 2 4 致谢”1 2 6 个人简历1 2 7 、 第1 章绪论 第1 章绪论 1 1 引言 随着信息技术的迅猛发展，人类社会进入高度信息化的时代，计算机技 术、微电子技术、多媒体技术等多种技术相互结合、相互促进，信息的处理、 传输和存储都达到全新的水平，通信技术也随之得到空前发展。在通信技术 研究过程中，人们为了便于找出信息传输和处理的共同规律，将各种通信系 统中具有共同特性的部分抽取出来，概括成统一的通信理论模型。 一般来说，通信系统模型可以分成五部分：信源、编码器、信道、译码 器和信宿。信源是产生消息的源，是事物各种运动状态或存在状态的集合， 信源状态可能是随机的、不确定的，但又有一定的规律性。信道是用来传输 载有消息的信号的媒介，如电缆、光纤、无线电波传播空间等，而由信道输 出的信号通常已经叠加了干扰信号。编码器把消息变换成适合信道传输的信 号，通常分为两种：信源编码器和信道编码器。前者主要是为了提高信息传 输效率，后者则是为了提高信息传输的可靠性。译码器对信道传出的编码信 号进行反变换，译码器也可以分成信源译码器和信道译码器。信宿是消息传 送的对象，也就是负责接收消息，信宿与信源可以处于不同地点和不同时刻。 由于随着以计算机为核心的大规模信息网络的迅速发展，信息安全问题 日益成为信息社会关注的焦点，人们对信息传输的质量要求也越来越高，不 仅要求即快速有效又能可靠地传递信息，还要求信息传递过程中保证信息的 安全保密，不被伪造和篡改。这样有时就需要在编码器这一端加入加密编码， 而在译码器那一端加入解密译码。 一个好的信息传输系统，应该尽可能保证信息传输的可靠性、有效性、 保密性和认证性。可靠性使得信源发出的消息经过信道传输后，接收端能够 准确地、不失真地获取该消息；有效性是指在尽可能短的时间，用尽可能少 的设备来传送信息，即使得各方面耗费达到最低；保密性是指尽可能隐蔽和 保护通信系统中传送的消息而不会发生泄密，使得信息只能被授权接收者获 得，而不能被未授权者接收和理解；认证性则是指接收者能正确判断所接收 哈尔滨工程大学博十学何论文 消息的正确性，验证消息的完整性，而不被其他人伪造和篡改。 通过上述通信系统模型的描述可以看出，在通信过程中，数据编码技术 扮演重要的角色，此外，编码技术在数字化遥测遥控系统、计算技术、数据 与图像处理、自动控制、人工智能和模式识别等方面也都有广泛的应用。概 括起来，编码理论可以包括三个分支：信源编码、信道编码和保密编码。 编码技术在数据压缩方面的应用更是无处不在，对数据的存储和传输有 重要意义。数据压缩编码属于编码理论中的信源编码。随着现代社会信息化 的发展，全球数据量不断增加，这些数据包含各种业务操作数据、报表统计 数据、办公文档、电子邮件、表格、图片、音频、视频等各种数据信息。应 用范围遍及军事、科技、商业甚至日常生活的各个角落：计算机、互联网、 照相、录像总之，数据正在以指数级速度增长，仅从商业角度来说，公 司收集、存储和分析的有关客户、财务、产品和运营的数据，其增长率就达 1 2 5 之多，数据仓库和数据挖掘应用鼓励企业存储越来越长的时间段内越 来越多的数据。此外，大型科学实验如生物、大气、高能物理等也会产生巨 量数据。这些情况导致的结果就是数据大量增加。 数据的爆炸性增长问题正逐步引发人们的注意。根据美国国际数据公司 ( i d c ) 的统计，截至2 0 0 6 年，全球已经生产了1 6 1 千兆兆字节的数据，这 些数字信息大约是现有书籍所含信息的3 0 0 万倍，而世界上有足够存储1 8 5 千兆兆字节的存储设备。若干年后，世界上所具备的存储数据的设备将无法 满足全球数据量的激增，许多潜在的有用数据将不得不被删除。 当今数据中大约将有7 0 以上的数据量都将是由个人制造的。而对企业 来说，数据更多的是来自那些监控摄像头以及日常经营。主要数据量分布在 图片图像以及音视频( 来源于数码相机、医疗扫描仪、监控摄像头等) 、电子 邮件、即时消息 历史数据的归档 理业务交易的， 务系统只存放短 或者被转移到其 们从档案环境中 业对数据的重要 第1 章绪论 ：i i i：i：zi iil - - - - - - = ：=i i i - z lii t ：t i- - i i i _ 历史数据的访问将变得重要、频繁和直接。 此外，通信技术也要求数据在进行传输时所占带宽越少越好，传输速度 越快越好，力求用最少的数码传递最大的信息量。但是目前，般民众尚不 能负担1 g b s 的传输率，即便是几百兆的数据在因特网上传输也非常困难。 因此，数据压缩技术是解决这些问题的关键，现代计算的许多层面都依赖于 数据压缩技术。所谓数据压缩，简单地说就是用尽可能少的数码表示信源所 发出的信号，其主要优势如下： ( 1 ) 实现时间域的压缩：能够较快地传输各种信源，降低信道占有费用。 ( 2 ) 实现频率域的压缩：在现有通信干线上开通更多的并行业务，如电 视、传真、电话、可视图文等。 ( 3 ) 实现能量域的压缩：降低发射功率，这对于依靠电池供电的移动通 信终端如手机、个人数字助理( p d a ) 等尤为重要。 ( 4 ) 实现空间域的压缩：紧缩数据存储容量，降低存储费用，如减少了 硬盘、光盘等存储介质的空间。 总之，数据压缩已经成为现代计算最重要的研究领域和工具之一。本文 提出的组合编码方法便可以用于压缩数据，下面先简单介绍编码技术特别是 数据压缩编码发展状况，第2 章将根据本文研究内容的应用详细阐述主要的 压缩方法。 1 2 编码技术概述 1 2 1 编码技术 编码理论用于研究信息存储与传输过程中信号的编码规律，与信息论、 数理统计、概率论、组合分析等学科关系密切，所谓编码是指为了达到某种 目的而对信号进行的一种变换，其逆变换称为译码或解码。 编码技术可以追述到美国著名画家s f b 莫尔斯所设计的莫尔斯码，莫 尔斯码广泛应用于电报通信中，但是直到2 0 世纪3 0 - 4 0 年代才开始形成编 码理论。后来由美国电信工程师h 奈奎斯特提出著名的采样定理，使得连续 信号可以离散化。1 9 4 8 年美国应用数学家c e 香农提出信息熵的概念，为信 源编码奠定了理论基础，而1 9 4 9 年香农又提出了信道容量的概念和信道编码 定理。随着计算技术和数字通信的发展，纠错编码和密码学也得到迅速发展。 编码理论在通信系统、计算技术、数据和图像处理、自动控制等方面都 哈尔滨t 稃大学博十学位论文 有广泛的应用。根据编码目的不同，编码理论有三个分支： ( 1 ) 信源编码：信源编码对信源输出的信号进行变换，包括数模转换与 数据压缩。信源编码以提高通信有效性为目的，通常通过压缩信源冗余度来 实现。 ( 2 ) 信道编码：对信源编码器输出的信号进行再变换，包括区分通路、 适应信道条件和提高通信可靠性而进行的编码，例如纠错码。信道编码由于 是以提高信息传输可靠性为目的，因此通常通过增加信源的冗余度来实现， 与信源编码正好相反。 ( 3 ) 保密编码：为了使信息在传输中不被人窃取，对信道编码器输出的 信号进行再变换。通常通过对数据的加密和解密来实现，加密可以视为“增 熵”过程，解密则可以视为“减熵”过程。 信源编码包括模数转换和数据压缩两方面，而主要任务是压缩数据。信 源编码有四种基本方法：匹配编码、变换编码、矢量编码和识别编码。所谓 匹配编码是指编码长度与概率分布相匹配，即根据编码对象的概率分布，分 别给予不同长短的编码，出现概率越大，所给编码长度越短。此外，匹配编 码还常采用去相关性的方法进一步压缩数据。变换编码则是先对信号进行变 换，从一种信号空间变换成另一种信号空间，然后针对变换后的信号进行编 码。变换编码在话音和图像编码中有广泛的应用。矢量编码是将可能传输的 消息分类按地址存储在接收端的电子计算机数据库中，发送端只发送数据库 的地址，即可查出消息的内容，从而压缩所发送数据。识别编码主要用于有 标准形状的文字、符号和数据。识别编码的作用不仅限于压缩数据，它在模 式识别中也有广泛的应用。常用的识别方法有关联识别和逻辑识别等方法。 信道编码的主要任务是为了区分通路和增加通信的可靠性。以区分通路 为主要目的的编码常采用正交码，正交码也具有很强的抗干扰能力，广泛用 于通信、雷达、导航、遥控、遥测和保密通信等领域，而以增加通信可靠性 为主要目的的编码常采用纠错码，纠错码接收到错误的码字后能在译码时自 动纠正错误，它是一种重要的抗干扰码，通常分为分组码和卷积码两类。增 加通信可靠性的信道编码也可以采用检错码。检错码能发现错误，通常包括 奇偶校验码和等重码，采用检错码的通信系统当发现收到的信号有错误时， 将通过反馈通道发出自动请求重发信号。 4 第1 章绪论 保密编码主要是为了隐藏敏感信息，防止窃译而进行的再编码，它常采 用替换或乱置或两者兼有的方法。1 9 4 9 年，香农发表了密码学的先驱性著作 保密系统的通信理论，1 9 7 6 年狄菲和赫尔曼首次提出公开密钥体制，到 了7 0 年代，密码学引入计算机复杂性理论，出现了所谓p 类、n p 类和n p 完全类问题。算法的复杂性函数呈指数型增长，使密码的分析和搜索越来越 困难，密码学开始向纵深方向发展。一个密码体制通常包括两个基本部分： 加( 解) 密算法和可以更换的控制算法的密钥。密码根据它的结构分为序列 密码和分组密码两类。序列密码广泛用于通信系统中，其算法在密钥控制下 产生一种随机序列，并逐位与明文混合而得到密文，其主要优点是不存在误 码扩散，但对同步有较高的要求。分组密码通常用于消息的确认和数字签名 中，其算法在密钥控制下对明文按组加密，所产生的密文位一般与相应的明 文组和密钥中的位有相互依赖性，能引起误码扩散。密码学还研究破译方法 来截获密文。破译方法有确定性分析法和统计性分析法两类，其中确定性分 析法是利用一个或几个未知量来表示所期望的未知量从而破译密文，而统计 分析法是利用存在于明文与密文或密钥之间的统计关系破译密文。 1 2 2 数据压缩编码 由于本文研究的组合编码主要应用于无记忆信源的压缩，而压缩编码属 于信源编码，在此本文进一步描述信源编码中的数据压缩技术。 数据压缩技术的发展始终伴随着数字世界的变迁。数据压缩最初作为信 息论研究中的课题，在信息论中属于信源编码。但近来已形成较为独立的体 系。有关信息如何被高效存储和传输一直是军事科学家、数学家、电子学家 关注的事情。数据压缩技术经过多年的发展，已经积累了许多理论基础。科 学家们在研究中发现，大多数信息的表达都存在一定的冗余度，通过采用一 定的模型和编码方法，可以降低这种冗余度。1 9 4 8 年，贝尔实验室的c l a u d e s h a n n o n 在提出信息熵理论的同时，给出了s h a n n o n 编列。随后不久，麻省 理工学院的r m f a n o 提出了f a n o 编码。而d a h u f f i n a n 子1 9 5 2 年提出了 “最小冗余度代码的构造方法”【2 】。从此，数据压缩开始在商业程序中实现 并被应用在许多领域。2 0 世纪6 0 年代、7 0 年代乃至8 0 年代的早期，数据压 缩领域几乎一直被h u f f m a n 编码及其分支所垄断。 哈尔滨1 二程大学博士学何论文 1 9 6 8 年前后，p e l i a s 发展了s h a n n o n 和f a n o 的编码方法，构造出更完 美的s h a n n o n f a n o e l i a s 编码。沿着这一思路，j r i s s a n e n 又设计出另一种更 为精确的、更能接近信息论中“熵极限的编码方法一算术编码【3 4 1 。算术 编码可以得到更好的压缩效果，但却要耗费几十倍的计算时间。l ：9 8 2 年， r i s s a n e n 和g g l a n g d o n 一起改进了算术编码。之后，人们又将算术编码与 j g c l e a r y 和i h w i a e n 于1 9 8 4 年提出的部分匹配预测模型相结合【5 1 ，使得 压缩效果逼近信息熵的极限。七十年代末，以色列人j a c o bz i v 和a b r a h a m l e m p e l 先后发表了论文“顺序数据压