数据压缩技术在通信中的应用
|
摘要
数据压缩技术，作为信息论研究中的一个重要课题，一直受到人们的广泛关注。数据压缩技术的主要目的是力求用最少的数据表示信源所发出的信号，使信号占用的存储空间尽可能小，以达到提高信息的传输速度的目的。各种压缩算法在一定程度上说都具有个性，他们对某一类型的数据其压缩率可能很大，但对于另一类型数据其压缩率则可能很小。所以在应用中，若想得到较好的综合压缩性能，必须考虑各种因素并对现有算法进行综合比较，最终确定合适的压缩算法。
数据压缩技术主要分为无损压缩和有损压缩。在本论文中研究的是无损压缩技术，对HUFFMAN算法、ARITHMETIC算法、LZSS以及在LZSS基础上进行改进的LZSSD、LZSSB、LZHUF算法，LZW、在LZW基础上进行改进的ILZW算法进行了分析研究并编写了C语言程序，将上述程序在计算机上进行了分析模拟，比较了压缩率的大小，最终选取压缩率较好的LZSSB算法，应用于现有的通信平台。
根据通信应用中的特点，将程序进行了以下改进，以满足实际要求。
(1)BIT位的转换。在所选的DSP上，不能对存储空间进行8bit位的访问，而如果在程序中采用以16位、32位或48位为比较单位，将减小压缩率。在程序中设置了两个存储空间大小不一样的缓冲区，通过外围数据的转换，来满足程序中8bit的比较要求，从而大大提高了压缩率
(2)数据流结束标志的处理。在通信的发端，通过两种方法来判断数据流处理结束：一种是通过监控数据流结尾处的控制信号；另一种是通过缓冲区指针的变化来判断。
(3)字典的处理。在论文中，采用了两种字典的处理方法。一种是字典在建立过程中不断的更新，另一种是当处理完缓冲区中的数据后，立即全部更新字典。第二种方法虽然在一定程度上减小了压缩率，但是因为减小了程序的复杂度，从而减小了程序执行时间，给其他数据处理提供了更大的运算空间。
(4)其他改进。为了程序的灵活性，缓冲区的设置不是在程序中进行，而是由整个通信系统来决定。压缩程序在执行之初，到某个地址中去读出该值。输出压缩代码之前先输出缓冲区大小值，这样解压程序可从压缩代码中得到该值，从而确保压缩与解压模型的一致性。
将所选的LZSSB算法经过上述改进后，成功的在现有的通信平台上运行，其压缩率与实时性都满足了要求。
As an important problem in the information science, the data compression technology has been given widly attention. The main purpose of data compression is to represent the origin information sent by the information resource with minimum data, thus to decrease the storage space of the information, and to increase the transport speed of it. To some special data, the compressing ratio of the existing arithmetics may be very high, but to others, it may be very low. So, in order to find arithmetic with good integrated capability, it is essential to compare arithmetics according to all factors in application.
The noise coding and noiseless coding are main parts of data compression technology. In this paper, the latter is studied.Some arithmetics such as HUFFMAN. ARITHMETIC. LZSS series (LZSS and LZSSB,LZSSD and LZHUF which were improved on the base of LZSS) and LZW series(LZW and ILZW improved on the base of LZW) are studied.Acrodding to these arithmetics, some C programs are written to simulate the compressing status of different arithmetics .In the end, for its high compressing ratio, the LZSSB arithmetic is selected and is applied to the existing communication plat.
According to the characteristic of the communication plat, the program is improved as follows:
(1) The conversion of bits. The data in the storage space can't be visited by the unit of 8bit on the choosen DSP. But if 16 bit. 32bit. or 48bit is choosen as the comparing unit, the compressing ratio will decrease. So two buffers of different size are setup to convert the outside data to meet the request of DSP, and through this method, the compressing ratio is increased.
(2) Deal with the end sign of the datum. Two methods are selected to judge the end of data from the data source: one is to monitor the control signal of the data end, the other is to test the change of buffer pointer.
(3) Deal with the dictionary. In this paper, two methods are selected to deal with the dictionary. One is updating it as setting up. Another is updating the dictionary after the data in the buffer are dealt with. The second method debases the compressing ratio, but it decreases the runing time of the program because it lessens the complication of the program. Through this, the other programs can get bigger running space.
(4) Other improvements. To enhance the agility of the program, the setup of buffer is not in program but decided by communication system. In the begining of the program, the program read the buffer_size in some address. The buffer_size must be transported before the compressed data, thus the expanding program can read out the size in it. So the consistency of compression and
PI
expanding model can be ensured.
Through these improvments, the arithmetic of LZSSB is succeeded in the running on the existing communication plat. Its compressing ratio and real-time are all meet the need of the project.
数据压缩技术主要分为无损压缩和有损压缩。在本论文中研究的是无损压缩技术，对HUFFMAN算法、ARITHMETIC算法、LZSS以及在LZSS基础上进行改进的LZSSD、LZSSB、LZHUF算法，LZW、在LZW基础上进行改进的ILZW算法进行了分析研究并编写了C语言程序，将上述程序在计算机上进行了分析模拟，比较了压缩率的大小，最终选取压缩率较好的LZSSB算法，应用于现有的通信平台。
根据通信应用中的特点，将程序进行了以下改进，以满足实际要求。
(1)BIT位的转换。在所选的DSP上，不能对存储空间进行8bit位的访问，而如果在程序中采用以16位、32位或48位为比较单位，将减小压缩率。在程序中设置了两个存储空间大小不一样的缓冲区，通过外围数据的转换，来满足程序中8bit的比较要求，从而大大提高了压缩率
(2)数据流结束标志的处理。在通信的发端，通过两种方法来判断数据流处理结束：一种是通过监控数据流结尾处的控制信号；另一种是通过缓冲区指针的变化来判断。
(3)字典的处理。在论文中，采用了两种字典的处理方法。一种是字典在建立过程中不断的更新，另一种是当处理完缓冲区中的数据后，立即全部更新字典。第二种方法虽然在一定程度上减小了压缩率，但是因为减小了程序的复杂度，从而减小了程序执行时间，给其他数据处理提供了更大的运算空间。
(4)其他改进。为了程序的灵活性，缓冲区的设置不是在程序中进行，而是由整个通信系统来决定。压缩程序在执行之初，到某个地址中去读出该值。输出压缩代码之前先输出缓冲区大小值，这样解压程序可从压缩代码中得到该值，从而确保压缩与解压模型的一致性。
将所选的LZSSB算法经过上述改进后，成功的在现有的通信平台上运行，其压缩率与实时性都满足了要求。
As an important problem in the information science, the data compression technology has been given widly attention. The main purpose of data compression is to represent the origin information sent by the information resource with minimum data, thus to decrease the storage space of the information, and to increase the transport speed of it. To some special data, the compressing ratio of the existing arithmetics may be very high, but to others, it may be very low. So, in order to find arithmetic with good integrated capability, it is essential to compare arithmetics according to all factors in application.
The noise coding and noiseless coding are main parts of data compression technology. In this paper, the latter is studied.Some arithmetics such as HUFFMAN. ARITHMETIC. LZSS series (LZSS and LZSSB,LZSSD and LZHUF which were improved on the base of LZSS) and LZW series(LZW and ILZW improved on the base of LZW) are studied.Acrodding to these arithmetics, some C programs are written to simulate the compressing status of different arithmetics .In the end, for its high compressing ratio, the LZSSB arithmetic is selected and is applied to the existing communication plat.
According to the characteristic of the communication plat, the program is improved as follows:
(1) The conversion of bits. The data in the storage space can't be visited by the unit of 8bit on the choosen DSP. But if 16 bit. 32bit. or 48bit is choosen as the comparing unit, the compressing ratio will decrease. So two buffers of different size are setup to convert the outside data to meet the request of DSP, and through this method, the compressing ratio is increased.
(2) Deal with the end sign of the datum. Two methods are selected to judge the end of data from the data source: one is to monitor the control signal of the data end, the other is to test the change of buffer pointer.
(3) Deal with the dictionary. In this paper, two methods are selected to deal with the dictionary. One is updating it as setting up. Another is updating the dictionary after the data in the buffer are dealt with. The second method debases the compressing ratio, but it decreases the runing time of the program because it lessens the complication of the program. Through this, the other programs can get bigger running space.
(4) Other improvements. To enhance the agility of the program, the setup of buffer is not in program but decided by communication system. In the begining of the program, the program read the buffer_size in some address. The buffer_size must be transported before the compressed data, thus the expanding program can read out the size in it. So the consistency of compression and
PI
expanding model can be ensured.
Through these improvments, the arithmetic of LZSSB is succeeded in the running on the existing communication plat. Its compressing ratio and real-time are all meet the need of the project.
引文
1．樊昌信 张甫翊 通信原理 国防工业出版社，2000
2．袁玫 袁文．数据压缩技术及其应用 电子工业出版社，1994：3-6
3．骆新 陈睿 数据压缩实用技术 学苑出版社，1993：5
4．陈德荣 周继成 殷益群等 通信新技术续篇 北京邮电大学出版社，1997
5．[美]Mark Nelson 著 数据压缩技术原理与范例 贾起东译 科学出版社，1995
6．桑林 郝建军 刘丹谱 数字通信 北京邮电大学出版社，2002
7．苏涛 吴顺军等 高性能DSP与高速实时信号处理 第二版 西安电子科技大学出版社，2002
8．张雄伟 曹铁勇 DSP芯片的原理与开发应用 第二版 电子工业出版社，2000：7-9
9．严蔚敏 吴伟民 数据结构 清华大学出版社，1997
10．林家薇 王兴亮 等 军事通信技术基础 西安电子科技大学出版社，2001
11．仇佩亮 信息论及其基础 浙江大学出版社，1999
12．李小平 数据压缩及传输编码软件速查手册 科学出版社，2001
13．姜丹 信息论与编码 中国科学技术大学出版社，2001
14．王平 茅忠明 LZSS文本压缩算法实现与研究 计算机工程，2001，8
15．赵耀 袁保宗 数据压缩的概念及现状 中国数据通信网络，2000，11：48-51
16．赵耀 袁保宗 国际数据编码标准简介 中国数据通信网络，2000，11
17．刘方 一种数据无损压缩技术的研究 南京航空航天大学学报，1995，12：804—809
18．谭兆信 数据压缩的综合字典模型 计算机工程与设计，1997，2：10-15
19．王忠效 姜丹 关于Lempel ziv 77压缩算法及其实现的研究 计算机研究与发展，1996，5：329—340
20．于洪斌 马俊光 多标志位的LZ数据压缩算法 微型机与应用，1998，6：8—22
21．张桂玲 王正光 一种实时处理的无失真数据压缩技术遥测遥控，1994，8：9—13
22．王林译 智能化压缩编码的应用研究 兰州铁道学院学报，1996，3
23．谭兆信 散列高阶字典编码及其实现 软件学报，1998，8
24．王忠敏 基于字符串匹配的通用数据压缩算法 计算机应用，1995，2
25．胡元福 基于字符频率的快速通用数据压缩算法 计算机应用，1995，10
26．华强 中西文文本压缩的LZWCH算法 计算机工程与应用，1999，3
27．裴文强 吴坚 一种新的数据压缩算法 无线电通信技术，2001，3
28．华强LZ77和LZ78再数据压缩中的组合带参运用 小型微型机算机系统，2000，2
29．张柏雄 数据压缩的原理与实践 微电子学与计算机，1994，5
30．严剑 Huffamn算法及其在数据压缩中的应用 计算机与现代化，1996，4
31．薛晓辉 高文 小字母表的高性能算术编码 计算机学报，1997，11
32．徐秉铮 吴立忠 中文文本压缩的LZW算法 华南理工大学学报(自然科学版)，1989，17(3)
33．贺前华 徐秉铮 彭磊 中文文本压缩的自适应算法 中文信息学报，1993，7
34．陈俭 王铁丹 侯迪等 关于ZL数据压缩算法性能的实验研究 计算机应用 1992，12
35．陈伟等LZW压缩算法的实现 计算机世界月刊，1994，3
36. Ziv J,Lempel A. Compression of Individual Sequences via Variable_Rate Coding IEEE Transcations on Information Theory, 1978, 5:530—536
37. Ziv J,Lempel A. A Universal Algorithm for Sequential Data Compression IEEE Transcations on Information Theory, 1977,3: 337—343
38. Hidetoshi Yokoo Improved Variations Relating the Ziv-Lempel and Welch-Type Algorithms for Sequential Data Compression IEEE Transcations on Information Theory, 1992,1
39. Printz H, Stubley P, Multialphabet arithmetic coding at 16 Mbytes/sec.In Proc IEEE Data Compression Conf. Snowbird,UT, 1993
40. Witeen I H ,Bell T C The zero frequency problem:estimating the probilities of novel events in adaotive text compression IEEE Trans Information Theory, 1991,37
41. Bell T C, Cleary J G. Arithmetic coding for data compression CACM, 1987,30
42. Pennebaker W B,Mitchell J L,Langdon Jr G G et al An overview of the basic principles of the Q-coder adaptive binary arithmetic coder IBM Journal of Research and Development, 1988,32
43. Bell T C, Cleary J G, Witten I H Text Compression Englewood Cliffs:
Prentice-Hall, 1990
44. A Welch A Technique for High-performance Data Compression IEEE Computer 1984,9(17)
45. Bender P E,Wolf J K New asymptotic bounds and improvements on the lempell-ziv data compression algorithm IEEE Trans Information Theory 1991,3
46. LZJH Algorithm Description ITU-T SG16 Delayed Contribution 2000,2
47. A New Mehhod of Data Compression ITU-T SG 16 Delayed Contribution 2000,2
48. Upgrading V.42bits to LZJH ITU-T SG 16 Delayed Contribution 2000,2
49. T C Chen etc An adaptive High-Speed lossy data compression PDCC 1992,349
50. R Baseri Vector quantization of monochrome images Universiity of Utah, 1991
51. J A Stored 2nd Proceedings of data compression conference Snowbird, Utah, U.S.A 1992
52. J A Stored 3rd Proceedings of data compression conference Snowbird, Utah,U.S.A 1992
53. D.A Huffman Amethod for the construction of Minimum Redundancy Code 1952,9
54. James a. Storer Data Compression:Methods and Theory Computer Science Press, Inc. 1988
2．袁玫 袁文．数据压缩技术及其应用 电子工业出版社，1994：3-6
3．骆新 陈睿 数据压缩实用技术 学苑出版社，1993：5
4．陈德荣 周继成 殷益群等 通信新技术续篇 北京邮电大学出版社，1997
5．[美]Mark Nelson 著 数据压缩技术原理与范例 贾起东译 科学出版社，1995
6．桑林 郝建军 刘丹谱 数字通信 北京邮电大学出版社，2002
7．苏涛 吴顺军等 高性能DSP与高速实时信号处理 第二版 西安电子科技大学出版社，2002
8．张雄伟 曹铁勇 DSP芯片的原理与开发应用 第二版 电子工业出版社，2000：7-9
9．严蔚敏 吴伟民 数据结构 清华大学出版社，1997
10．林家薇 王兴亮 等 军事通信技术基础 西安电子科技大学出版社，2001
11．仇佩亮 信息论及其基础 浙江大学出版社，1999
12．李小平 数据压缩及传输编码软件速查手册 科学出版社，2001
13．姜丹 信息论与编码 中国科学技术大学出版社，2001
14．王平 茅忠明 LZSS文本压缩算法实现与研究 计算机工程，2001，8
15．赵耀 袁保宗 数据压缩的概念及现状 中国数据通信网络，2000，11：48-51
16．赵耀 袁保宗 国际数据编码标准简介 中国数据通信网络，2000，11
17．刘方 一种数据无损压缩技术的研究 南京航空航天大学学报，1995，12：804—809
18．谭兆信 数据压缩的综合字典模型 计算机工程与设计，1997，2：10-15
19．王忠效 姜丹 关于Lempel ziv 77压缩算法及其实现的研究 计算机研究与发展，1996，5：329—340
20．于洪斌 马俊光 多标志位的LZ数据压缩算法 微型机与应用，1998，6：8—22
21．张桂玲 王正光 一种实时处理的无失真数据压缩技术遥测遥控，1994，8：9—13
22．王林译 智能化压缩编码的应用研究 兰州铁道学院学报，1996，3
23．谭兆信 散列高阶字典编码及其实现 软件学报，1998，8
24．王忠敏 基于字符串匹配的通用数据压缩算法 计算机应用，1995，2
25．胡元福 基于字符频率的快速通用数据压缩算法 计算机应用，1995，10
26．华强 中西文文本压缩的LZWCH算法 计算机工程与应用，1999，3
27．裴文强 吴坚 一种新的数据压缩算法 无线电通信技术，2001，3
28．华强LZ77和LZ78再数据压缩中的组合带参运用 小型微型机算机系统，2000，2
29．张柏雄 数据压缩的原理与实践 微电子学与计算机，1994，5
30．严剑 Huffamn算法及其在数据压缩中的应用 计算机与现代化，1996，4
31．薛晓辉 高文 小字母表的高性能算术编码 计算机学报，1997，11
32．徐秉铮 吴立忠 中文文本压缩的LZW算法 华南理工大学学报(自然科学版)，1989，17(3)
33．贺前华 徐秉铮 彭磊 中文文本压缩的自适应算法 中文信息学报，1993，7
34．陈俭 王铁丹 侯迪等 关于ZL数据压缩算法性能的实验研究 计算机应用 1992，12
35．陈伟等LZW压缩算法的实现 计算机世界月刊，1994，3
36. Ziv J,Lempel A. Compression of Individual Sequences via Variable_Rate Coding IEEE Transcations on Information Theory, 1978, 5:530—536
37. Ziv J,Lempel A. A Universal Algorithm for Sequential Data Compression IEEE Transcations on Information Theory, 1977,3: 337—343
38. Hidetoshi Yokoo Improved Variations Relating the Ziv-Lempel and Welch-Type Algorithms for Sequential Data Compression IEEE Transcations on Information Theory, 1992,1
39. Printz H, Stubley P, Multialphabet arithmetic coding at 16 Mbytes/sec.In Proc IEEE Data Compression Conf. Snowbird,UT, 1993
40. Witeen I H ,Bell T C The zero frequency problem:estimating the probilities of novel events in adaotive text compression IEEE Trans Information Theory, 1991,37
41. Bell T C, Cleary J G. Arithmetic coding for data compression CACM, 1987,30
42. Pennebaker W B,Mitchell J L,Langdon Jr G G et al An overview of the basic principles of the Q-coder adaptive binary arithmetic coder IBM Journal of Research and Development, 1988,32
43. Bell T C, Cleary J G, Witten I H Text Compression Englewood Cliffs:
Prentice-Hall, 1990
44. A Welch A Technique for High-performance Data Compression IEEE Computer 1984,9(17)
45. Bender P E,Wolf J K New asymptotic bounds and improvements on the lempell-ziv data compression algorithm IEEE Trans Information Theory 1991,3
46. LZJH Algorithm Description ITU-T SG16 Delayed Contribution 2000,2
47. A New Mehhod of Data Compression ITU-T SG 16 Delayed Contribution 2000,2
48. Upgrading V.42bits to LZJH ITU-T SG 16 Delayed Contribution 2000,2
49. T C Chen etc An adaptive High-Speed lossy data compression PDCC 1992,349
50. R Baseri Vector quantization of monochrome images Universiity of Utah, 1991
51. J A Stored 2nd Proceedings of data compression conference Snowbird, Utah, U.S.A 1992
52. J A Stored 3rd Proceedings of data compression conference Snowbird, Utah,U.S.A 1992
53. D.A Huffman Amethod for the construction of Minimum Redundancy Code 1952,9
54. James a. Storer Data Compression:Methods and Theory Computer Science Press, Inc. 1988
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |