×

Robust universal complete codes for transmission and compression. (English) Zbl 0874.94026

Summary: Several measures are defined and investigated, which allow the comparison of codes as to their robustness against errors. Then new universal and complete sequences of variable-length codewords are proposed, based on representing the integers in a binary Fibonacci numeration system. Each sequence is constant and needs not be generated for every probability distribution. These codes can be used as alternatives to Huffman codes when the optimal compression of the latter is not required, and simplicity, faster processing and robustness are preferred. The codes are compared on several “real-life” examples.

MSC:

94A45 Prefix, length-variable, comma-free codes
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Apostolico, A.; Fraenkel, A. S., Robust transmission of unbounded strings using Fibonacci representations, IEEE Trans. Inform. Theory, 33, 238-245 (1987) · Zbl 0626.94007
[2] Bell, T.; Cleary, J. G.; Witten, I. H., Text Compression (1990), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[3] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press Orlando, FL · Zbl 1022.94506
[4] Bookstein, A.; Klein, S. T., Is Huffman coding dead?, Computing, 50, 279-296 (1993) · Zbl 0780.94003
[5] Choueka, Y.; Klein, S. T.; Perl, Y., Efficient variants of Huffman codes in high level languages, (Proceedings of the 8th ACM-SIGIR Conference. Proceedings of the 8th ACM-SIGIR Conference, Montreal (1985)), 122-130
[6] Elias, P., Universal codeword sets and representation of the integers, IEEE Trans. Inform. Theory, 12, 194-203 (1975) · Zbl 0298.94011
[7] Even, S.; Rodeh, M., Economical encoding of commas between strings, Comm. ACM, 21, 315-317 (1978) · Zbl 0371.94008
[8] Ferguson, T. J.; Rabinowitz, J. H., Self-synchronizing Huffman codes, IEEE Trans. Inform. Theory, 30, 687-693 (1984) · Zbl 0548.94011
[9] Fraenkel, A. S., All about the responsa retrieval project you always wanted to know but were afraid to ask, expanded summary, Jurimetrics J., 16, 149-156 (1976)
[10] Fraenkel, A. S., Systems of numeration, Amer. Math. Monthly, 92, 105-114 (1985) · Zbl 0568.10005
[11] Fraenkel, A. S., The use and usefulness of numeration systems, Inform. and Comput., 81, 46-61 (1989) · Zbl 0672.10008
[12] Fraenkel, A. S.; Klein, S. T., Novel compression of sparse bit-strings — preliminary report, (Combinatorial Algorithms on Words. Combinatorial Algorithms on Words, NATO ASI Series F12 (1985), Springer: Springer Berlin), 169-183
[13] Gilbert, E. N., Synchronization of binary messages, IRE Trans. Inform. Theory, 6, 470-477 (1960)
[14] Guibas, L. J.; Odlyzko, A. M., Maximal prefix-synchronized codes, SIAM J. Appl. Math., 35, 401-418 (1978) · Zbl 0394.94024
[15] Hamming, R. W., Coding and Information Theory (1986), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0952.65501
[16] Heaps, H. S., Information Retrieval, (Computational and Theoretical Aspects (1978), Academic Press: Academic Press New York) · Zbl 0471.68075
[17] Hirschberg, D. S.; Lelewer, D. A., Efficient decoding of prefix codes, Comm. ACM, 33, 449-459 (1990)
[18] Huffman, D., A method for the construction of minimum redundancy codes, (Proc. IRE, 40 (1952)), 1098-1101
[19] Jakobsson, M., Huffman coding in bit-vector compression, Inform. Process. Lett., 7, 304-307 (1978) · Zbl 0385.94018
[20] Jiggs, B. H., Recent results in comma-free codes, Canad. J. Math., 15, 178-187 (1963) · Zbl 0108.14304
[21] Kautz, W. H., Fibonacci codes for synchronization control, IEEE Trans. Inform Theory, 11, 284-292 (1965) · Zbl 0143.41305
[22] Lakshmanan, K. B., On universal codeword sets, IEEE Trans. Inform. Theory, 27, 659-662 (1981)
[23] Lelewer, D. A.; Hirschberg, D. S., Data compression, ACM Comput. Surveys, 19, 261-296 (1987) · Zbl 0647.94002
[24] McMillan, B., Two inequalities implied by unique decipherability, IRE Trans. Inform. Theory, 2, 115-116 (1956)
[25] Storer, J. A., Data Compression: Methods and Theory (1988), Computer Science Press: Computer Science Press Rockville, MD
[26] Williams, R. N., Adaptive Data Compression (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht
[27] Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liége, 41, 179-182 (1972) · Zbl 0252.10011
[28] Ziv, J.; Lempel, A., A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, 23, 337-343 (1977) · Zbl 0379.94010
[29] Ziv, J.; Lempel, A., Compression of individual sequences via variable-rate coding, IEEE Trans. Inform. Theory., 24, 530-536 (1978) · Zbl 0392.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.