任意概率分布下Golomb码和扩展Gamma码的性能分析

杨胜天; 仇佩亮

任意概率分布下Golomb码和扩展Gamma码的性能分析

计量
- 文章访问数: 2408
- HTML全文浏览量: 165
- PDF下载量: 945
- 被引次数: 0
出版历程
- 收稿日期: 2003-09-18
- 修回日期: 2004-05-20
- 刊出日期: 2005-04-19

Performance Analysis of Golomb Codes and Extended Gamma Codes for Arbitrary Probability Distributions

摘要

摘要: 以信源的平均值给出了任意概率分布下Golomb码的平均码长的上下界和最优的参数选择准则。在Golomb码的基础上，进一步推广了Elias的码，提出了扩展的码，同时给出了其性能界和最优的参数选择准则。扩展码是一类通用码，而且在一定的条件下可以达到渐近最优的性能。最后，提出了一个低复杂性的基于Golomb码和扩展码的通用数据压缩框架，并通过构建一个样例系统说明了该数据压缩框架的实际应用价值。
- 信源编码; 整数编码; Golomb码; Elias; 码
Abstract: The upper and lower bounds of the average codeword length of Golomb codes for arbitrary probability distributions as well as an optimal rule for choosing parameters are given in terms of the mean of sources. Furthermore, a class of extended gamma codes which are the generalization of Elias gamma code is constructed based on Golomb codes. The performance bounds and an optimal rule for choosing parameters are also given. Extended gamma codes are universal and can achieve asymptotically optimal performance under some conditions. Finally, a low complexity universal data compression framework based on Golomb codes and extended gamma codes is presented, and a sample system is constructed to indicate the significance of the data compression framework in practice.

HTML全文

参考文献(1)

Golomb S W. Run-length encodings [J].IEEE Trans. on Info.Theory.1966, 12(3):399-[2]Weinberger M J, Seroussi G, Sapiro G. The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS [J].IEEE Trans. on Image Processing.2000, 9(8):1309-[3]Rice R F. Some practical universal noiseless coding techniquesPart Ⅲ [R]. Technical Report JPL-91-3, Jet Propulsion Laboratory,Pasadena, CA, 1991.[4]Gallager R G, Voorhis D C V. Optimal source codes for geometrically distributed integer alphabets [J].IEEE Trans. on Info. Theory.1975, 21(2):228-[5]Szpankowski W. Asymptotic average redundancy of Huffman (and other) block codes [J].IEEE Trans. on Info. Theory.2000,46(7):2434-[6]Merhav N, Seroussi G, Weinberger M J. Optimal prefix codes for sources with two-sided geometric distributions [J].IEEE Trans.on Info. Theory.2000, 46(1):121-[7]Howard P G. The design and analysis of efficient lossless data compression systems [D]. Rhode Island: Brown University, 1993.[8]Fenwick P. Punctured Elias codes for variable-length coding of the integers [R]. Technical Report 137, Dept of Computer Science,The University of Auckland, New Zealand, December 1996.[9]Elias P. Universal codeword sets and representations of the integers [J].IEEE Trans. onInfo. Theory.1975, 21(2):194-[10]Lakshmanan K B. On universal codeword sets [J].IEEE Trans. on Info. Theory.1981, 27(5):659-[11]Amemiya T, Yamamoto H. A new class of the universal representation for the positive integers [J]. IEICE Trans. on Fundamentals, 1993, E76-A(3): 447 - 452.[12]Wyner A D. An upper bound on the entropy series [J].Information and Control.1972, 20(2):176-[13]Apostolico A, Fraenkel A S. Robust transmission of unbounded strings using Fibonacci representations [J].IEEE Trans. on Info.Theory.1987, 33(2):238-[14]Wang M. Almost asymptotically optimal flag encoding of the integers[J].IEEE Trans. on Info. Theory.1988, 34(2):324-[15]Yamamoto H, Ochi H. A new asymptotically optimal code for the positive integers [J].IEEE Trans. on Info. Theory.1991, 37(5):1420-[16]Burrows M, Wheeler D J. A block-sorting lossless data compression algorithm [R]. Technical Report SRC 124, Digital System Research Center, Palo Alto, CA, 1994.[17]Bentley J L, Sleator D D, Tarjan R E, et al.. A locally adaptive data compression scheme[J].Commun. ACM.1986, 29(4):320-[18]Muramatsu J. On the performance of recency-rank and block-sorting universal lossless data compression algorithms[J].IEEE Trans. on Info. Theory.2002, 48(9):2621-

施引文献

资源附件(0)

访问统计