Abstract
Consider a source providing finite sequences of symbols, zeros and ones in general, into a constrained format dictated by the data processor ; constraints are supposed to be time independant (of particular importance are those specified by a finite list of forbidden blocks of symbols, e.g. upper and lower bounds on runs length of zeros and ones). Factorial extendables languages are an appropriate mathematical model for strings of symbols, and for strings long enough to seem infinite we have to deal with entropy (Shannon) if we want to measure the quantities of information dispatched by the source : the greatest the entropy is, the greatest the information will be ; roughly speaking, the entropy is the exponential growth of the number of strings of n letters enclosed in the strings provided by the source.
A particular case is that of a source sending successive blocks m1, m2, ... randomly chosen in a set X of words on an alphabet A ; we obtain messages of the type m1 m2 ... mn ; we call X a variable length code if a word on X has only one decomposition on X ; if an is the number of words of n letters in X then the entropy of the associated phenomen is equal to log(1/r) where r is the positive real number so that : 1=a1/r+a2/r2+a3/r3+...; if you pick up a block m in the sequence dispatched by the source, the average of its length is (Berstel-Perrin) a=a1/r+2a2/r2+3a3/r3+... who is called the average length of the code ; for a given entropy, the smaller the average length is, the more economic the transmission will be and so we investigate the problem : how to minimize the average length of a code for a given entropy ?
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blanchard F. and Hansel G.: Systèmes codés. Th. Comp. Sci. 1986.
Berstel J. and Perrin D.: Theory of codes, Orlando Academic press 1985.
Denker M., Grillenberger C. and Sigmund K.: Ergodic Theory on Compact Spaces; Lectures Notes in Mathematics, Vol. 527 1976.
Bertrand-Mathis A. Développements en base θ, répartition modulo un, systèmes codés. Bulletin de la S.M.F. 1968.
Shannon C. A Mathematical Theory of Communication, Bell System Tech. 1946.
Parry W. On the β-expansions of reals numbers, Acta Math Sci. Hungar. 11, 1960.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bertrand, A. (1988). Specification, synchronisation, a verage length. In: Cohen, G., Godlewski, P. (eds) Coding Theory and Applications. Coding Theory 1986. Lecture Notes in Computer Science, vol 311. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-19368-5_9
Download citation
DOI: https://doi.org/10.1007/3-540-19368-5_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19368-5
Online ISBN: 978-3-540-39243-9
eBook Packages: Springer Book Archive