zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

94A45Prefix, length-variable, comma-free codes (communication theory)
11B39Fibonacci and Lucas numbers, etc.
Full Text: DOI Link
[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)
[3] Berstel, J.; Perrin, D.: Theory of codes. (1985) · Zbl 0587.68066
[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, 122-130 (1985)
[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. NATO ASI series F12, 169-183 (1985)
[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) · Zbl 0649.94004
[16] Heaps, H. S.: Information retrieval. Computational and theoretical aspects (1978) · 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, 1098-1101 (1952) · Zbl 0137.13605
[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)
[26] Williams, R. N.: Adaptive data compression. (1990)
[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