Marie-Pierre Béal

Jean Berstel

Brian H Marcus

Dominique Perrin

Christophe Reutenauer

Paul H Siegel

M.-P Béal

Variable-Length Codes and Finite Automata

probability distributions. The chapter contains numerous examples and exercises with solutions.

Codes and Automata 5

Thoughts for practitioners

In this chapter, a wide variety of variable-length coding techniques are presented.

We consider source and channel models that take into account the statistical properties of the source and the costs associated with transmission of channel symbols. Given these models, we define a measure of code optimality by which to evaluate the code design algorithms. The resulting families of variable-length codes are intended for use in a range of practical applications, including image and video coding, speech compression, magnetic and optical recording, data transmission, natural language representation, and tree search algorithms. In practice, however, there are often system-related issues that are not explicitly reflected in the idealized source and channel models, and therefore are not taken into account by the code design algorithms. For example, there are often tradeoffs between the efficiency of the code and the complexity of its implementation in software or hardware. Encoding and decoding operations may be subject to latency constraints or a requirement for synchronous input-output processing. There is often a need for resilience against errors introduced by the channel, as well as robustness in the presence of variability in the source and channel characteristics. There may also be a system interface that dictates the incorporation of specific code properties or even a specific code. Finally, intellectual property concerns, such as the existence of patents on certain codes or coding methods, can play a role in practical code design. Such realities provide a challenge to the coding practitioner in applying the various design methods, as well as a stimulus for further research and innovation.

To illustrate some of these points, we examine two applications where variablelength coding has found pervasive use -data compression and digital magnetic recording.

The aim of this chapter is to present, in appropriate perspective, some selected topics in the theory of variable-length codes. One of the domains of applications is lossless data compression. The main aspects covered include optimal prefix codes and finite automata and transducers. These are a basic tool for encoding and decoding variable-length codes. Connections with codes for constrained channels and sources are developed in some detail. Generating series are used systematically for computing the parameters of encodings such as length and

Introduction

Variable-length codes occur frequently in the domain of data compression. Historically, they appeared at the beginning of modern information theory with the seminal work of Shannon. One of the first algorithmic results is the construction, by Huffman, of an optimal variable-length code for a given weight distribution. Although their role in data communication has been limited by their weak tolerance to faults, they are nonetheless commonly used in contexts where error handling is less critical or is treated by other methods.

Variable-length codes are strongly related to automata, and one of the aims of this chapter is to highlight connections between these domains. Automata are labeled graphs, and their use goes beyond the field of coding. Automata can be used to implement encoders and decoders, such as for compression codes, modulation codes and convolutional error correcting codes.

The use of variable-length codes in data compression is widespread. Huffman's algorithm is still frequently used in various contexts, and under various forms, including in its adaptive version. In particular, Huffman codes are frequently used in the compression of motion pictures. In another setting, search trees are strongly related to ordered prefix codes, and optimal ordered prefix codes, as constructed later, correspond to optimal binary search trees.

Coding for constrained channels is required in the context of magnetic or optical recording. The constraints that occur can be represented by finite automata, and a coding method makes use of finite transducers. In this context, the constraints are defined by an automaton which in turn is used to define a state-dependent encoder. Even if this encoder operates at fixed rate, it can also be considered as a memoryless encoder based on two variable-length codes with the same length distribution, that is with the same number of words for each length.

Although convolutional error correcting codes are fixed-length codes, their analysis involves use of finite automata because encoders and decoders are described in terms of labeled graphs.

Specific properties of automata correspond to properties of variable-length codes. Typically, unambiguity in automata corresponds to unique decipherability.

Variable-length codes also are used for the representation of natural languages. They play a role for instance in phonetic transcription of languages and in the transformation from text to speech, or in speech recognition. We will mention examples in Section 1. [START_REF] Berstel | Theory of Codes[END_REF].

The mathematical relation between codes and automata is very deep, as shown in early, pioneering investigations by Schützenberger. He discovered and developed a new branch of algebra relating unique decipherability of codes with the theory of

Codes and Automata 3

semigroups. There are still difficult open problems in the theory of variable-length codes. One of them is the commutative equivalence conjecture. It has practical significance in relation with optimal coding. We will discuss this and other open problems in Section 1. [START_REF] Bruyère | Variable-length maximal codes[END_REF]. The material covered by the chapter is the following. We start with a few definitions and examples, and then address the problem of constructing optimal codes under various types of constraints. Typically, we consider alphabetic coding under cost conditions.

We study in detail prefix codes used for representing integers, such as Elias and Golomb codes.

Automata and transducers are introduced insofar as coding and decoding operations are concerned. These are applied to two special domains, namely coding with constraints on channels, and constraints on sources. They are important in applications which are described here.

Reversible codes, also called bifix codes, have both practical significance and deep mathematical properties which we only sketch here.

The final section is concerned with synchronization. This is important in the context of error recovery, and we present very recent theoretical results such as the road coloring theorem.

The chapter is written at a level accessible to nonspecialists. There are few formal proofs, but key algorithms are described in considerable detail and many illustrative examples are given. Exercises that reinforce and extend the material are given at the end of most sections, and sketches of solutions are provided. Some elementary questions and answers are also included.

The authors would like to thank Frédérique Bassino, Julien Clément, Éric Incerti, Claire Kenyon, Éric Laporte and Olivier Vénard for their help in the preparation of this text, and the anonymous referees for their helpful comments.

Background

The topic of this chapter is an introduction to some syntactic and algorithmic problems of data transmission. In this sense, it is connected with three main fields:

(1) coding and information theory (2) automata and formal language theory (3) algorithms In this section, we describe these connections, their historical roots and the notions to which they relate.

The relation between codes and automata can be traced back to Shannon, who used labeled graphs to represent information sources. Later, the notion of information lossless machine was introduced as a model for reversible encoding [START_REF] Kohavi | Switching and Automata Theory[END_REF]. These are the unambiguous transducers defined below. The term lossless has remained in common use with the notion of lossless methods for data compression. The main motivation for studying variable-length codes is in data compression. In many coding systems, encoding by variable-length codes is used in connection with other coding components for error correction. The search for efficient data compression methods leads to algorithmic problems such as the design of optimal prefix codes under various criteria. One of the main tools for encoding and decoding as presented here are finite automata and transducers. In this context, finite automata are particular cases of more general models of machines, such as pushdown automata which can use an auxiliary stack and, more generally, Turing machines which are used to define the notion of computability. The theory of automata has also developed independently of coding theory with motivations in algorithms on strings of symbols, in the theory of computation and also as a model for discrete processes.

The basic result of automata theory is Kleene's theorem asserting the equivalence between finite automata and regular expressions and providing algorithms to convert from automata to regular expressions and conversely. This conversion is actually used in the context of convolutional codes to compute the path weight enumerator (also called the transfer function) of a convolutional code [START_REF] Mceliece | The Theory of Information and Coding[END_REF].

Inside the family of finite automata, several subclasses have been studied which correspond to various types of restrictions. An important one is the class of aperiodic automata which contains the classes of local automata frequently used in connection with coding, in particular with sliding block encoders and decoders.

One of the possible extensions of automata theory is the use of multiplicities, which can be integers, real numbers, or elements of other semirings (see [START_REF] Eilenberg | Automata, Languages and Machines[END_REF] or [START_REF] Berstel | Rational Series and their Languages[END_REF]). The ordinary case corresponds to the Boolean semiring with just two element 0, 1. This leads to a theory in which sets of strings are replaced by functions from strings to a semiring. This point of view has in particular the advantage of allowing the handling of generating series and gives a method, due to Schützenberger, to compute them. We will often use this method to compute generating series.

The well-known Huffman algorithm, described below, is the ancestor of a family of algorithms used in the field of information searching. Indeed, it can be used to build search trees as well as optimal prefix codes for source compression. The design and analysis of search algorithms is part of an important body of knowledge encompassing many different ideas and methods, including, for example, the theory of hashing functions (see [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]). Text processing algorithms find application in variety of domains, ranging from bioinformatics to the processing of large data sets such as those maintained by Internet search engines (see [START_REF] Lothaire | Applied Combinatorics on Words, volume 105 of Encyclopedia of Mathematics and its Applications[END_REF] for an introduction).

The topic of coding with constraints is related to symbolic dynamics which is a field in its own right. Its aim is to describe dynamical systems and mappings between them. Codes for constrained channels are a particular case of these mappings (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

Codes for data compression. In Section 1.6, we present the classical Huffman algorithm for designing an optimal prefix code for a memoryless source with specified symbol statistics and equal channel symbol costs. Codes produced by this algorithm and its variants have been extensively employed in data compression applications. Practical system issues are often addressed during the code design process, or by using a modification of the standard design approach.

As will be described later in the chapter, for a binary channel alphabet, the Huffman algorithm builds a binary code tree from the bottom up by combining two nodes with the smallest probabilities. If there are multiple possibilities for selecting such pairs of nodes, all choices lead to codes with the same average codeword length. However, this is not true of the variance of the codeword lengths, and a large variance could have an impact on the implementation complexity if the code is incorporated into a data transmission system that calls for a constant transmission rate. This problem can be mitigated if the practitioner follows a simple rule for judiciously combining nodes during the generation of the code tree, resulting in a Huffman code with the smallest possible variance. There are also variants of Huffman coding that help to control the maximum length of a codeword, a parameter that also may influence implementation complexity of the code. Another practical consideration in applying Huffman codes may be the ease of representing the code tree. The class of canonical Huffman codes have a particu-

{ c a n o n i c a l H u f f m a n c o d e } { H u f f m a n c o d e ! c a n o n i c a l }
larly succinct description: the codewords can be generated directly from a suitably ordered list of codeword lengths. Canonical codes are also very amenable to fast decoding, and are of particular interest when the source alphabet is large. Fortunately, a code designed using the standard Huffman algorithm can be directly converted into a canonical code.

The practitioner may also encounter situations where the source statistics are not known in advance. In order to deal with this situation, one can use adaptive Huffman coding techniques. Application of adaptive coding, though, requires

{ a d a p t i v e H u f f m a n c o d i n g } { H u f f m a n c o d e ! a d a p t i v e }
careful attention to a number of implementation related issues. Huffman codes are generally not resilient to channel symbol errors. Nevertheless they have some inherent synchronization capabilities and, for certain length distributions, one can design synchronized Huffman codes. Typically, though, in order to ensure recovery within a reasonable time after a channel error, substantial modifications to the coding scheme are necessary.

Despite the availability of more efficient data compression methods, such as arithmetic coding, Huffman coding and its variants continue to play a role in many text and multimedia compression systems. They are relatively effective, simple to implement, and, as just discussed, they offer some flexibility in coping with a variety of practical system issues. For further details, see, for example, [START_REF] Salomon | Variable-Length Codes for Data Compression[END_REF].

Codes for digital magnetic recording. In Section 1.9, we consider the problem of encoding binary source sequences into binary channel sequences in which there are at least d and at most k 0's between consecutive 1's, for specified 0 ≤ d < k. This [d, k]-constraint is used as a channel model in magnetic recording.

One simple approach to encoding a binary source sequence into the [d, k]constraint uses the idea of a bit-stuffing encoder. The bit-stuffing encoder generates

{ b i t -s t u f f i n g e n c o d e r }
a code sequence by inserting extra bits into the source sequence to prevent violations of the [d, k]-constraint. It uses a counter to keep track of the number of consecutive 0's in the generated sequence. When the number reaches k, the encoder inserts a 1 followed by d 0's. Whenever the source bit is a 1, the encoder inserts d 0's. The decoder is correspondingly simple. It also keeps track of the number of consecutive 0's. Whenever the number reaches k, it removes the following d + 1 bits (the 1 and d 0's that had been inserted by the encoder). When the decoder encounters a 1, it removes the following d bits (the d 0's that had been inserted by the encoder). The bit-stuffing encoder can also be recast as a variable-length code, as shown for the special case [d, k] = [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF] in Figure 1 [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF] bit-stuffing code.

In Section 1.9, we present another variable-length [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF] code, the Franaszek code, whose encoder mapping is shown in Figure 1.2 below. This encoder has a fixed encoding rate of 1/2, since each source word is mapped to a code word with twice its length. In fact, as shown in Section 1.9, this code can be implemented by a rate 1:2, 6-state encoder that converts each source bit synchronously into 2 channel bits according to simple state-dependent rules. The decoder is also synchronous, and it decodes a pair of channel bits into a single source bit based upon the contents of an 8-bit window containing the channel-bit pair along with the preceding pair and the next two upcoming pairs. This sliding-window decoding limits to 4 bits the propagation of decoding errors caused by an erroneous channel bit. This code is also efficient, in the sense that the theoretical upper bound on the rate of a code for the [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF] constraint is approximately 0.5172. Moreover, among M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel [2, k]-constraints, the [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF]-constraint has the smallest k constraint that can support a rate 1/2 code. This code was patented by IBM and was extensively used in its commercial disk drive products.

Source

The construction of the Franaszek code involved certain choices along the way. For example, a different choice of the assignment of source words to channel codewords would potentially affect the implementation complexity as well as the worstcase decoder error propagation. Virtually all code design methodologies share this characteristic, and the practitioner has to exercise considerable technical insight in order to construct the best code for the particular situation.

For example, using the state-splitting algorithm discussed later in the chapter, one can construct another rate 1:2 code for the [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF]-constraint that requires only 5 encoder states, but the resulting maximum error propagation of the decoder is increased to 5 bits. It is also possible to construct fixed-rate encoders for the [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF]constraint that have a higher code rate than the Franaszek code, but the encoder and decoder implementation will very likely be more complex.

While some of the earliest [d, k]-constrained codes designed for disk drives were standardized by the interface between the drive and the host computer drive controller, the encoding and decoding functions eventually migrated into the drive itself. This allowed coding practitioners to exercise their creativity and invent new codes to meet their particular system requirements. For further details about practical constrained code design, see, for example, [39; 47].

Definitions and notation

We start with some definitions and notation on words and languages. Some notation. Given a finite set A called alphabet , each element of A is a letter , { a l p h a b e t } { l e t t e r } and a sequence of letters is called a word . The length of a word is the number of its

{ p r e f i x } { s u f f i x }
y is called a factor (or also a subword or a block) of w.

{ f a c t o r }
Given sets X and Y of words over some alphabet A, we denote by XY the set of all words xy, for x in X and y in Y . We write X n for the n-fold product of X, with X 0 = {ε}. We denote by X * the set of all words that are products of words in X, formally

X * = {ε} ∪ X ∪ X 2 ∪ • • • ∪ X n ∪ • • • . If X = {x}, we write x * for {x} * . Thus x * = {x n | n ≥ 0} = {ε, x, x 2 , x 3 , . . . , }.
The operations of union, set product and star ( * ) are used to describe sets of words by so-called regular expressions.

{ r e g u l a r e x p r e s s i o n } Generating series. Given a set of words X, the generating series of the lengths of { g e n e r a t i n g s e r i e s ! o f l e n g t h s } { g e n e r a t i n g s e r i e s } the words of X is the series in the variable z defined by

f X (z) = x∈X z |x| = n≥0 a n z n ,
where a n is the number of words in X of length n. It is easily checked that

f X∪Y (z) = f X (z) + f Y (z) , (1.1)
{ e q : 0 1 } whenever X and Y are disjoint, and

f XY (z) = f X (z)f Y (z) , (1.2)
{ e q : 0 2 } when the product XY is unambiguous, that is whenever

xy = x ′ y ′ with x, x ′ ∈ X, { u n a m b i g u o u s p r o d u c t } { p r o d u c t ! u n a m b i g u o u s } y, y ′ ∈ Y imply x = x ′ , y = y ′ .
We will also make use of an extension (introduced later) of these series to the case where words are equipped with a cost.

Encoding. We start with a source alphabet B and a channel alphabet A. Consider a mapping γ that associates to each symbol b in B a nonempty word over the alphabet A. This mapping is extended to words over B by γ(s

1 • • • s n ) = γ(s 1 ) • • • γ(s n ).
We say that γ is an encoding if it is uniquely decipherable (UD) in the sense that Every property of an encoding has a natural formulation in terms of a property of the associated code, and vice-versa. We will generally not distinguish between codes and encodings.

Let C be a code. Since C n and C m are disjoint for n = m and since the products C n are unambiguous, we obtain from (1.1) and (1.2) the following fundamental equation

f C * (z) = n≥0 (f C (z)) n = 1 1 -f C (z) . (1.3)
{ e q : 0 3 } the alphabet is extended to words lexicographically, that is u < v if either u is a proper prefix of v or u = zaw and v = zbw ′ for some words z, w, w ′ and letters a, b with a < b.

An encoding γ is said to be ordered or A common way to represent an encoding -one that is especially enlightening for prefix encodings -is by a rooted planar tree labeled in an appropriate way.

alphabetic if b < b ′ =⇒ γ(b) < γ(b ′ ).
Assume the channel alphabet A has q symbols. The tree considered has nodes which all have at most q children. The edge from a node to a child is labeled with one symbol of the channel alphabet A. If this alphabet is ordered, then the children are ordered accordingly from left to right. Some of the children may be missing.

Each path from the root to a node in the tree corresponds to a word over the channel alphabet, obtained by concatenating the labels on its edges. In this way, a set of words is associated to a set of nodes in a tree, and conversely. If the set of words is a prefix code, then the set of nodes is the set of leaves of the tree. Thus, a prefix encoding γ from a source alphabet B into words over a channel

Codes and Automata 11

alphabet A is represented by a tree, and each leaf of the tree may in addition be labeled with the symbol b corresponding to the codeword γ(b) which labels the path to this leaf. Figure 1.3 represents the tree associated to the ordered encoding γ of Table 1.1.

Example 1.2. The Morse code associates to each alphanumeric character a se-

{ M o r s e c o d e }
quence of dots and dashes. For instance, A is encoded by ".

-" and J is encoded by ". ---". Provided each codeword is terminated with an additional symbol (usually a space, called a "pause"), the Morse code becomes a prefix code. Example 1.3. There are many representations of integers. The unary representation of an integer n is composed of a sequence of n symbols 1. The usual binary representation of positive integers is exponentially more succinct than the unary representation, and thus is preferable for efficiency. However, it is not adapted to representation of sequences of integers, since it is not uniquely decipherable: for instance, 11010 may represent the number 26, or the sequence 6, 2, or the sequence 1, 2, 2. The Elias code [START_REF] Elias | Universal codeword sets and representations of the integers[END_REF] maps a positive integer into a word composed of its

{ E l i a s c o d e }
binary representation preceded by a number of zeros equal to the length of this representation minus one. For instance, the Elias encoding of 26 is 000011010. It is easily seen that the set of Elias encodings of positive integers is a prefix code. The corresponding tree is given in Figure 1.4.

Example 1.4. There exist codes, even quite simple ones, which are neither prefix nor suffix. This is the case of the encoding of a, b and c by 00, 10 and 100. To see that this is indeed uniquely decipherable, one considers the occurrences of 1. If the number of 0's following a 1 is even, this block is decoded as ca • • • a, otherwise as ba • • • a.

Basic properties of codes

We start with stating a basic numerical inequality on codes. It gives a restriction on the distribution of lengths of codewords. [START_REF] Ash | Information Theory[END_REF])

{ K r a f t --M c M i l l a n
i n e q u a l i t y

} c∈C k -|c| ≤ 1 . (1.4)
{ e q : K M }

We prove the inequality below. Before that, we note that (1.4) is easy to prove for a finite prefix code. Indeed, the inequality above can also be written as

i m i k -i ≤ 1 ,
where m i is the number of elements in C of length i. Multiply both sides by k n , where n is the maximal length of codewords. One gets i m i k n-i ≤ k n . The left-hand side counts the number of words of length n that have a prefix in C, and the inequality expresses the fact that each word of length n has at most one prefix in C.

For general codes, the inequality (1.4) can be proved as follows. Consider the generating series of the lengths of the words of the code C

{ g e n e r a t i n g

s e r i e s } f C (z) = c∈C z |c| = n≥0 a n z n ,
where a n is the number of codewords of length n. Then, since C is a code, we have by (1.3): There is a converse statement for the Kraft-McMillan inequality: For any sequence ℓ 1 , . . . , ℓ n of positive integers such that i k -ℓi ≤ 1, there exists a prefix code

f C * (z) = 1 1 -f C (z) . Set f C * (z) = n≥0 b n z n . Since C * is a subset of A * ,
C = {c 1 , . . . , c n } over A such that |c i | = ℓ i .
This can be proved by induction on n as follows. It is clearly true for n = 1. Suppose that n > 1 and consider ℓ 1 , . . . , ℓ n satisfying

n i=1 k -ℓi ≤ 1. Since also n-1 i=1 k -ℓi ≤ 1, there exists by induction hypothesis a prefix code C = {c 1 , . . . , c n-1 } such that |c i | = ℓ i for 1 ≤ i ≤ n -1.
We multiply both sides of the inequality n-1 i=1 k -ℓi ≤ 1 by k ℓn , and we obtain

n-1 i=1 k ℓn-ℓi ≤ k ℓn -1 . (1.5)
{ e q : 0 4 }

Codes and Automata 13

Each of the terms k ℓn-ℓi of the left-hand side of (1.5) counts the number of words of length ℓ n -ℓ i , and can be viewed as counting the number of words of length ℓ n with fixed prefix c i of length ℓ i . Since the code C is prefix, the sets of words of length ℓ n with fixed prefix c i are pairwise disjoint, so the left-hand side of (1.5) is the number of words of length ℓ n on the alphabet A which have a prefix in C. Thus, (1.5)

H = - n i=1 p i log p i ,
where log is the logarithm to base 2. Actually, this expression defines what is called the entropy of order 1. The same expression defines the entropy of order k, when the p i 's are the probabilities of the blocks of length k and n is replaced by n k .

Channel. In the context of encoding the symbols of a source alphabet B, we consider a channel alphabet A with a cost, denoted cost(a), associated to each channel symbol a ∈ A. The cost of a symbol is a positive integer. The symbol costs allow us to consider the case where the channel symbols have non-uniform lengths, and the cost of each symbol can be interpreted as the time required to send the symbol.

A classic example is the alphabet composed of two symbols {., -}, referred to as dot and dash, with costs 1 and 2, respectively. This alphabet is sometimes referred to as the telegraph channel.

The channel capacity is log 1/ρ where ρ is the real positive root of In the case of an alphabet with k symbols, each having cost equal to 1, this reduces to ρ = 1/k. In the case of the telegraph channel, the capacity is the positive root of ρ + ρ 2 = 1, which is ρ ≈ 0.618. The cost of a word w over the alphabet A is denoted by cost(w). It is by definition the sum of the costs of the letters composing it. Thus

cost(a 1 • • • a n ) = cost(a 1 ) + • • • + cost(a n ) .
We extend the notation of generating series as follows. For a set of words, X, denote (1.6)

{ e q : K M r h o }
The proof follows the same argument as for the Kraft-McMillan inequality using the generating series of the costs of the words of

C f C (z) = c∈C z cost(c) = n≥0 a n z n ,
where a n is the number of words in C of cost equal to n. Similary,

f A * (z) = w∈A * z cost(w) = n≥0 b n z n ,
where b n is the number of words in A * of cost equal to n. Now

f A * (z) = 1 1 -f A (z) ,
and the radius of convergence of f A * (z) is the number ρ which is the real positive root of a∈A z cost(a) = 1. When the weights are probabilities, Shannons fundamental theorem on discrete noiseless channels [START_REF] Shannon | A mathematical theory of communication[END_REF] implies a lower bound on the weighted cost,

W (γ) ≥ H log 1/ρ
To show this, we set B = {b 1 , . . . , b n }, p i = weight(b i ), and q i = ρ cost(γ(bi)) . We can then write (log ρ) W (γ) = p i log q i . Invoking the well-known inequality ln x ≤ x -1, where ln denotes the natural logarithm, and applying (1.6), we find (log ρ) W (γ) -p i log p i = p i log q i /p i = (log e) p i ln q i /p i ≤ (log e) p i (q i /p i -1) ≤ (log e) q i -1 ≤ 0 , from which the bound follows.

The optimal encoding problem is the problem of finding, for given sets B and A encoding. Most research on optimal coding has been devoted to this second problem, both because of its practical interest and because of the conjecture that an optimal encoding can always be chosen to be prefix (see [START_REF] Karp | Minimum redundancy codes for the discrete noiseless channel[END_REF] and also the discussion below).

There is another situation that will be considered below, where the alphabets A and B are ordered and the encoding is required to be ordered.

In the case of equal letter costs, that is where all cost(a) are equal, the cost of a letter may be assumed to be 1. The cost of a codeword γ(b) is then merely the length |γ(b)|. In this case, the weighted cost is called the average length of { a v e r a g e l e n g t h }

codewords. An optimal encoding can always be chosen to be prefix in view of the Kraft-McMillan inequality, as mentioned above.

Commutative equivalence. In the case of unequal letter costs, the answer to the problem of finding a prefix encoding which has the same weighted cost as an optimal encoding is not known. This is related to an important conjecture, which we now formulate. Two codes C and D are commutatively equivalent if there is a one-to-one correspondence between C and D such that any two words in correspondence have the same number of occurrences of each letter (that is, they are anagrams). Observe that the encodings corresponding to commutatively equivalent codes have the same weight, and therefore one is optimal if the other is. It is conjectured that any finite maximal code (that is, a code that is not strictly tzenberger}

{ c o n j e c t u r e ! S c h { ü { c o d e ! m a x i m a l }
contained in another code) is commutatively equivalent to a prefix code. This would imply that, in the case of maximal codes, the optimal encoding can be obtained with a prefix code. For a discussion, see [10; 13]. The conjecture is known to be false if the code is not maximal. A counter-example has been given by Shor [START_REF] Shor | A counterexample to the triangle conjecture[END_REF]. Note that if equality holds in the Kraft-McMillan inequality (1.4), then the code must be maximal. Conversely, it can be shown (see e.g. [START_REF] Berstel | Codes and Automata[END_REF]) that for a finite maximal code, (1.4) is an equality.

Optimal prefix codes

In this section, we describe methods used to obtain optimal prefix codes under various constraints, such as equal or unequal letter costs, as well as equal or unequal letter weights, and finally encodings which are alphabetic or not. The different cases are summarized in Figure 1.5, where the vertices are associated to the inventors of some corresponding algorithm. For instance, vertex 3 denotes the problem of finding an optimal alphabetic tree in the case of unequal weights and unequal letter costs, and it is solved by Itai's algorithm described later. All these algorithms, Karp's algorithm excepted, have polynomial running time. We consider first the two cases (vertices 4 and 1 in Figure 1.5) of unequal weights without the constraint on the encoding to be alphabetic. Unequal letter costs. The computational complexity of the optimal prefix encoding problem in the case of unequal letter costs (vertex 4 in Figure 1.5) is still unknown, in the sense that no polynomial time algorithm is known for this, nor is it known whether the corresponding recognition problem (is there a code of cost ≤ m?) is NP-complete. It has been shown to be reducible to an integer programming problem by Karp [START_REF] Karp | Minimum redundancy codes for the discrete noiseless channel[END_REF]. We explain how an optimal prefix code can be found by solving an integer programming problem. Let ρ be the positive real number such that f A (ρ) = 1. Thus, log 1/ρ is the channel capacity. Recall that, for any code C, one has

{ K a r p a l g o r i t h m } { H u f f m a n a l g o r i t h m } { V a r n a l g o r i t h m } { G a r s i a --W a c h s a l g o r i t h m } { I t a i a l g o r i t h m } { a l g o r i t h m ! K a r p } { a l g o r i t h m ! H u f f m a n } { a l g o r i t h m ! V a r n } { a l g o r i t h m ! G a r s i a --W a c h s } { a l g o r i t h m ! I t a i }
{ c h a n n e l ! c a p a c i t y } { c a p a c i t y o f a c h a n n e l } f C (ρ) ≤ 1 .
(1.7)

{ e q P r o b a C o d e }
However, given a series f (z), the inequality f (ρ) ≤ 1 is not sufficient to imply the existence of a prefix code C such that f (z) = f C (z). For example, if the alphabet A has a single letter of cost 2, then f A (z) = z 2 , and so ρ = 1. The polynomial f (z) = z satisfies f (ρ) = 1, but there can be no codeword of cost 1.

Despite this fact, the existence of a code C with prescribed generating series of costs can be formulated in terms of solutions for a system of linear equations, as we describe now.

Let C be a prefix code over the channel alphabet A, with source alphabet B equipped with weights denoted weight(b) for b ∈ B, and let P be the set of prefixes of words in C which do not belong to C. Set

f A (z) = i≥1 a i z i , f C (z) = i≥1 c i z i , f P (z) = i≥1 p i z i .
Here a i is the number of channel symbols of cost i, c i is the number of codewords of cost i, and p i is the number of words in P of cost i. The following equality holds between the sets C, P and A (see Exercise 1.6.2).

P A ∪ {ε} = P ∪ C .
Since the unions are disjoint, it follows that

c 1 + p 1 = a 1 c 2 + p 2 = p 1 a 1 + a 2 • • • c n + p n = p n-1 a 1 + • • • p 1 a n-1 + a n • • • (1.8) { e q L i n }
Conversely, if c i , a i are non-negative integers satisfying these equations, there is a prefix code C such that f C (z) = i≥1 c i z i . Thus, an optimal prefix code can be found by solving the problem of finding non-negative integers u b for b ∈ B which will be the costs of the codewords, and integers c i , p i for i ≥ 1 which minimize the linear form b u b weight(b) such that Equations (1.8) hold and with c i equal to the number of b such that u b = i.

There have been many approaches to partial solutions of the optimal prefix encoding problem [49; 25]. The most recent one is a polynomial time approximation scheme which has been given in [START_REF] Golin | Huffman coding with unequal letter costs[END_REF]. This means that, given ǫ > 0, there exists a polynomial time algorithm computing a solution with weighted cost (1 + ǫ)W , where W is the optimal weighted cost.

Equal letter costs. The case of equal letter costs (vertex 1 in Figure 1.5) is solved by the well-known Huffman algorithm [START_REF] Huffman | A method for the construction of minimum redundancy codes[END_REF]. The principle of this algorithm in the The corresponding trees are given in Figure 1.6. Alphabetic encoding is motivated by searching problems. Indeed, a prefix code can be used as a searching procedure to retrieve an element of an ordered set. Each node of the associated tree corresponds to a query, and the answer to this query determines the subtree in which to continue the search.

{ H u f f m a n a l g o r i t h m } { a l g o r i t h m ! H u f f m a n }
Example 1.7. In the binary tree of Example 1.1, one looks for an occurrence of an English word. The query associated to the root can be the comparison of the first letter of the word to the letter T.

In contrast to the non-alphabetic case, there exist polynomial-time solutions to the optimal alphabetic prefix encoding problem. It has been considered mainly in the case where the channel alphabet is binary. Again, there is a distinction between equal letter costs and unequal letter costs. We consider now the case of equal letter costs, represented by vertex 2 in Figure 1.5. Let B = {b 1 , . . . , b n } be an ordered alphabet with n letters, and let p i be the weight of letter b i . There is a simple algorithm for computing an optimal ordered tree based on dynamic programming. It runs in time O(n 3 ) and can be improved to run in time O(n 2 ) (see [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]).

We present a more sophisticated algorithm due to Garsia and Wachs [START_REF] Adriano | A new algorithm for minimum cost binary trees[END_REF]. The The algorithm is composed of three parts. In the first part, called the combination part, one starts with the sequence of weights p = (p 1 , . . . , p n ) and constructs an optimal binary tree T ′ for a permutation b σ(1) , . . . , b σ(n) of the alphabet. The leaves, from left to right, have weights

{ G a r s i a --W a c h s a l g o r i t h m } { a l g o r i t h m ! G a r s i a --W a c h s } intuitive idea
p σ(1) , . . . , p σ(n) .
In general, this permutation is not the identity, so the tree is not ordered, see Figure 1.8 (a).

The second part, the level assignment, consists of computing the levels of the leaves. In the last part, called the recombination part, one constructs a tree T which has the weights p 1 , . . . , p n associated to its leaves from left to right, and where each leaf with weight p i appears at the same level as in the previous tree T ′ . This tree is ordered, see Figure 1.8 (b).

Since the leaves have the same level in T and in T ′ , the corresponding codewords have the same length, and therefore the trees T and T ′ have the same weighted cost. Thus T is an optimal ordered tree. We now give the details of the algorithm and illustrate it with this specific example. For ease of description, it is convenient to introduce some terminology.

A sequence (p 1 , . . . , p k ) of numbers is 2-descending if p i > p i+2 for 1 ≤ i ≤ k -2.
{ d e s c e n d i n g s e q u e n c e @ $ 2 $ -d e s c e n d i n g s e q u e n c e } Clearly a sequence is 2-descending if and only if the sequence of "two-sums" (p 1 + p 2 , . . . , p k-1 + p k ) is strictly decreasing. Let p = (p 1 , . . . , p n ) be a sequence of (positive) weights. The left minimal pair

{ l e f t m i n i m a l p a i r }
or simply minimal pair of p is the pair (p k-1 , p k ), where (p 1 , . . . , p k ) is the longest 2-descending chain that is a prefix of p. The index k is the position of the pair. In other words, k is the integer such that

p i-1 > p i+1 (1 < i < k) and p k-1 ≤ p k+1 .
with the convention that p 0 = p n+1 = ∞. The target is the index j with 1 ≤ j < k such that

p j-1 ≥ p k-1 + p k > p j , . . . , p k .
Example 1.10. For [START_REF] Dalai | Non prefix-free codes for constrained sequences[END_REF][START_REF] Deppe | On q-ary fix-free codes and directed deBrujin graphs[END_REF][START_REF] Berstel | Theory of Codes[END_REF][START_REF] Berstel | Codes and Automata[END_REF][START_REF] Berstel | Rational Series and their Languages[END_REF][START_REF] Béal | The method of poles: a coding method for constrained channels[END_REF][START_REF] Béal | Extensions of the method of poles for code construction[END_REF][START_REF] Ahlswede | Some properties of fix-free codes[END_REF], the minimal pair is [START_REF] Berstel | Theory of Codes[END_REF][START_REF] Berstel | Codes and Automata[END_REF], the target is 1, whereas for the sequence [START_REF] Girod | Bidirectionally decodable streams of prefix code words[END_REF][START_REF] Béal | Extensions of the method of poles for code construction[END_REF][START_REF] Deppe | On q-ary fix-free codes and directed deBrujin graphs[END_REF][START_REF] Fan | Lossless sliding-block compression of constrained systems[END_REF][START_REF] Béal | Codage symbolique[END_REF][START_REF] Ash | Information Theory[END_REF], the minimal pair is [START_REF] Béal | Extensions of the method of poles for code construction[END_REF][START_REF] Deppe | On q-ary fix-free codes and directed deBrujin graphs[END_REF] and the target is 2.

The three phases of the algorithm work as follows. Let (p 1 , . . . , p n ) be a sequence of weights.

Combination. Associate to each weight a tree composed of a single leaf. Repeat the following steps as long as the sequence of weights has more than one element.

(i) compute the left minimal pair (p k-1 , p k ) . (ii) compute the target j . (iii) remove the weights p k-1 and p k , (iv) insert p k-1 + p k between p j-1 and p j .

Codes and Automata 21

(v) associate to p k-1 + p k a new tree with weight p k-1 + p k , and which has a left (right) subtree the correponding tree for p k-1 (for p k ).

Level assignment. Compute, for each letter b in B, the level of its leaf in the tree T ′ .

Recombination. Construct an ordered tree T in which the leaves of the letters have the levels computed by the level assignment. The initial sequence of trees is given in Figure 1.9. The left minimal pair is 12, 10, its target is 2, so the leaves for c and d are combined into a tree which is inserted just to the right of the first tree, as shown on the left in Figure 1.10. Now the minimal pair is [START_REF] Fan | Lossless sliding-block compression of constrained systems[END_REF][START_REF] Dalai | Non prefix-free codes for constrained sequences[END_REF] (there is an infinite weight at the right end), so the leaves for letters b and e are combined, and inserted at the beginning. The resulting sequence of trees is shown on the right in Figure 1.10. The optimal ordered tree with these levels is given by recombination. It is the tree given in For a correctness proof, see [START_REF] Kingston | A new proof of the Garsia-Wachs algorithm[END_REF] or [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]. The time bound is given in [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]. The Garsia-Wachs algorithm is simpler than a previous algorithm due to Hu and Tucker [START_REF] Te | Optimal computer search trees and variablelength alphabetical codes[END_REF] which was also described in the first edition of Knuth's book, preceding [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]. For { H u --T u c k e r a l g o r i t h m } a proof and a detailed description of the Hu-Tucker algorithm and variations, see [34; 36].

Alphabetic coding with unequal costs. This is the most general case for alphabetic encoding (vertex 3 in Figure 1.5). There is a dynamic programming algorithm due to Itai [START_REF] Itai | Optimal alphabetic trees[END_REF] which computes an optimal solution in polynomial time.

{ I t a i a l g o r i t h m } { a l g o r i t h m ! I t a i }
Given a source alphabet B = {1, . . . , n} with n symbols, and weights weight(1), . . . , weight(n), one looks for an optimal alphabetic encoding γ on the ordered channel alphabet A with costs cost(a), for a in A. The weighted cost is n i=1 weight(i)cost(γ(i)). For convenience, the first (resp. the last) letter in A is denoted by α (resp. by ω). We also write a + 1 for the letter following a in the order on A.

Define W a,b [i, j] as the minimal weight of an alphabetic encoding for the symbols k with i ≤ k ≤ j, using codewords for which the initial symbol x satisfies a ≤ x ≤ b.

The following equations provide a method to compute the minimal weight

W α,ω [1, n]. First, for a < b, i < j, W a,b [i, j] = min W a+1,b [i, j], V a,b [i, j], W a,a [i, j] , (1.9)
{ e q : i t a i 1 }

where

V a,b [i, j] = min i≤k<j (W a,a [i, k] + W a+1,b [k + 1, j]) .
This formula expresses the fact that either the first codeword does not start with the letter a, or it does, and the set of codewords starting with a encodes the interval

Codes and Automata 23

[i, k] for some k < j, or finally all codewords start with a. Next, for i < j, W a,a [i, j] = cost(a)

j k=i weight(k) + min i≤k<j α≤x<ω {W x,x [i, k] + W x+1,ω [k + 1, j]} . (1.10)
{ e q : i t a i 2 }

In this case, all codewords start with the letter a. Moreover, the second letter cannot be the same for all codewords (otherwise this letter can be removed and this improves the solution). Finally, for a ≤ b, the boundary conditions are

W a,b [i, i] = min a≤x≤b {W x,x [i, i]} , W x,x [i, i] = cost(x)weight(i) . (1.11)
{ e q : i t a i 3 }

The appropriate way to compute the W 's is by increasing values of the difference j -i, starting with (1.11) and, for a fixed value of j -i, by increasing lengths of the source alphabet intervals, starting with (1.10), followed by (1.9). This method gives an algorithm running in time O(q 2 n 3 ) where q is the size of the channel alphabet. Indeed, each evaluation of (1.10) requires time O((j -i)q), and each evaluation of (1.9) is done in time O(j -i). Itai [START_REF] Itai | Optimal alphabetic trees[END_REF] has given an improvement of the algorithm that leads to a better bound of O(q 2 n 2 ). So the minimal weight of an encoding is W a,c [START_REF] Adler | Algorithms for sliding block codes[END_REF][START_REF] Ash | Information Theory[END_REF] [START_REF] Ahlswede | Some properties of fix-free codes[END_REF][START_REF] Ash | Information Theory[END_REF] = 86, there are, by (1.9), two optimal trees. Inspection of the matrices yield the trees given in Figure 1.12. Optimal encodings with equal weights. In the case where all source symbols have the same weight (vertices 5 -8 in Figure 1.5), this weight can be assumed to be 1. The weighted cost becomes simply

= 86. Since W a,a [1, 2] + W b,c [3, 5] = W a,a [1, 3] + W b,c
W (γ) = b∈B cost(γ(b)) .
The prefix coding problem in this case is known as the Varn coding problem. It has

{ V a r n c o d i n g p r o b l e m }
an amazingly simple O(n log n) time solution [START_REF] Varn | Optimal variable length codes (arbitrary symbol cost and equal code word probability)[END_REF]. We assume that A is a k-letter alphabet and that n = q(k -1) + 1 for some integer q. So the prefix code (or the tree) obtained is complete with q internal nodes and n leaves. Varn's algorithm starts with a tree composed solely of its root, and iteratively replaces a leaf of minimal cost by an internal node which has k leaves, one for each letter. The number of leaves increases by k -1, so in q steps, one gets a tree with n leaves. Note that this solves also the cases numbered 5, 6 in Figure 1.5.

Example 1.13. Assume we are looking for a code with seven words over the ternary alphabet {a, b, c}, and that the cost for letter a is 2, for letter b is 4, and for letter c is 5. The algorithms starts with a tree composed of a single leaf, and then builds the tree by the algorithm. There are two solutions, both of cost 45, given in Figure 1.13. Tree 1.13(d) defines the prefix code {aa, ab, ac, ba, bb, bc, c}, and tree 1.13(e) gives the code {aaa, aab, aac, ab, ac, b, c}.

Exercises

Exercise 1.6.1. Show that for any distribution p i of probabilities, the sequence

ℓ i = ⌈log 1/p i ⌉ satisfies the inequality 2 -ℓi ≤ 1.
Conclude that for any source with equal letter costs, there is a prefix code with weighted cost W ≤ H +1 where H is the entropy of the source with probabilities p i .

Exercise 1.6.2. Let A be a k-letter alphabet. A k-ary tree is complete if each of its nodes has 0 or k children. A prefix code is complete if its tree is complete. Let C be a finite complete prefix code and let P be the set of prefixes of the words of C which are not in C. Show that where, for a finite set S, Card(S) denotes the cardinality of S.

P A ∪ {ε} = P ∪ C .
Exercise 1.6.3. For a nonempty binary word s of length p, denote by Q the set of words w of length strictly less than p such that sw has s as a suffix. Let X be the set of binary words which have s as a suffix but no other factor equal to s. Show that X is a maximal prefix code and that the generating series of the lengths of X is

f X (z) = z p z p + (1 -2z)f Q (z) , (1.12)
{ e q S e m } where f Q (z) is the generating series of the lengths of Q (called the autocorrelation polynomial of s).

f X (z) = z 3 1 -2z + z 2 -z 3 .
Exercise 1.6.5. A set of binary words is said to be a prefix synchronized code if all { c o d e ! p r e f i x s y n c h r o n i z e d } words have the same length n and share a common prefix s which does not appear elsewhere in the sequences of codewords. For each s and n, there is a maximal set C n,s which satisfies this condition. For example, C 5,101 = {10100, 10111}. Table 1.2 shows the cardinalities of some of the sets C n,s . Let U be the set of binary words u such that s is a proper prefix of u and us does not have s as a factor except as a prefix or a suffix. Show that

f U (z) = 2z -1 z p + (1 -2z)f Q (z) + 1 ,
where p is the length of s and f Q (z) is the autocorrelation polynomial of the word s. (Hint: use the fact that s ∪ {0, 1}X = X ∪ U s where X is as in Exercise 1.6.3). Show that for each n ≥ p, C n,s is the set of words of length n in U .

Exercise 1.6.6. Let π be a Bernoulli distribution on the source alphabet B. A Tunstall code of order n is a maximal prefix code with n codewords over the alphabet

{ T u n s t a l l c o d e }
B which has maximal average length with respect to π. Such a code is used to encode the words of the source alphabet by binary blocks of length k for n ≤ 2 k . For example, if B = {a, b} and π(a) = .8, π(b) = .2, the code C = {aaa, aab, ab, b} is a Tunstall code of order 4. Its average length is 2.44 and thus coding each word of C by a binary block of length 2 realizes a compression with rate 2/2.44 ≈ 0.82. Show how Varn's algorithm can be used to build a Tunstall code. (Tunstall codes were introduced in [START_REF] Parker | Synthesis of noiseless compression codes[END_REF], see also [START_REF] Salomon | Variable-Length Codes for Data Compression[END_REF].)

Prefix codes for integers

Some particular codes are used for compression purposes to encode numerical data subject to a known probability distribution. They appear in particular in the context of digital audio and video coding. The data encoded are integers and thus these codes are infinite. We will consider several families of these codes, beginning with the Golomb codes introduced in [START_REF] Golomb | Run-length encodings[END_REF]. We have already seen the Elias code which belongs to one of these families.

Codes and Automata 27

Golomb codes. The Golomb code of order m ≥ 1, denoted by G m , is the maximal

{ G o l o m b c o d e }
infinite prefix code

G m = 1 * 0R m .
Thus words in G m are composed of a (possibly empty) block of 1's, followed by 0, and followed by a word in R m , where the prefix codes R m are defined as follows.

If m = 2 k is a power of 2, then R m is the set of all binary words of length k. In particular, R 1 is composed of the empty word only. For other values of m, the description is more involved. Set

m = 2 k + ℓ, with 0 < ℓ < 2 k . Setting n = 2 k-1 , R m = 0R ℓ ∪ 1R 2n if ℓ ≥ n , 0R n ∪ 1R n+ℓ otherwise .
The codes R m for m = 1 to 7 are represented in Figure 1.14. Note that, in particular, the lengths of the codewords differ at most by one. an integer n < m as its representation on r -1 bits if n < 2 r -m and on r bits otherwise (adding 0's on the left if necessary). The encoding of the integer n in G m is formed of n/m 1's followed by 0, followed by the adjusted binary representation of n modulo m. A geometric distribution on the set of integers is given by

{ g e o m e t r i c d i s t r i b u t i o n } π(n) = p n q , (1.13)
{ g e o m e t r i c } for positve real numbers p, q with p + q = 1. Such a distribution may arise from run-length encoding where a sequence of 0 n 1 is encoded by n. If the source produces { r u n -l e n g t h e n c o d i n g } 0 and 1's independently with probability p and q, the probability of 0 n 1 is precisely π(n). This is of practical interest if p is large since then long runs of 0 are expected and the run-length encoding realizes a logarithmic compression. We will show that for a source of integers with the geometric distribution corresponding to a given p, there is an integer m ≥ 1 such that the Golomb code G m is an optimal prefix code.

For this, consider, following [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], the integer m such that

p m + p m+1 ≤ 1 < p m + p m-1 . (1.14)
{ e q G a l l a g e r }

For each p with 0 < p < 1, there is a unique integer m satisfying (1.14). Indeed, (1.14) is equivalent with

p m (1 + p) ≤ 1 < p m-1 (1 + p) or equivalently m ≥ - log(1 + p) log p > m -1.
Note that when m is large, (1.14) implies p m ∼ 1/2, and that (1.14) holds for p m = 1/2. Let us show that the application of the Huffman algorithm to a geometric distribution given by (1.13) can produce the Golomb code of order m where m is defined by (1.14). This shows the optimality of the Golomb code. Actually, we will operate on a truncated, but growing source since Huffman's algorithm works only on finite alphabets. Set Q = 1 -p m . By the choice of m, one has p -1-m ≥ 1/Q > p 1-m . We consider, for k ≥ -1, the bounded alphabet

B k = {0, . . . , k + m} .
In particular, B -1 = {0, . . . , m -1}. We consider on B k the distribution

π(i) = p i q for 0 ≤ i ≤ k , p i q/Q for k < i ≤ k + m .

Codes and Automata 29

Clearly π(i) > π(k) for i < k and π(k+i) > π(k+m) for 1 < i < m. Observe that also π(i) > π(k+m) for i < k since π(k+m) = p k+m q/Q ≤ p k+m q/p m+1 = π(k-1). Also π(k

+ i) > π(k) for 1 < i < m since indeed π(k + i) > π(k + m -1) = p k+m-1 q/Q > p k q = π(k).
As a consequence, the symbols k and k + m are those of minimal weight. Huffman's algorithm replaces them with a new symbol, say k ′ , which is the root node of a tree with, say, left child k and right child k + m. The weight of k ′ is

π(k ′ ) = π(k) + π(k + m) = p k q(1 + p m /Q) = p k q/Q .
Thus we may identify B k \ {k, k + m} ∪ {k ′ } with B k-1 by assigning to k the new value π(k) = p k q/Q. We get for B k-1 the same properties as for B k and we may iterate.

After m iterations, we have replaced B k by B k-m , and each of the symbols k -m + 1, . . . , k now is the root of a tree with two children. Assume now that k = (h + 1)m -1 for some h. Then after hm steps, one gets the alphabet B -1 = {0, . . . , m-1}, and each of the symbols i in B -1 is the root of a binary tree of height h composed of a unique right path of length h, and at each level one left child i + m, i + 2m, . . . , i + (h -1)m. This corresponds to the code P h = {0, 10, . . . , 1 h-1 0, 1 h }. The weights of the symbols in B -1 are decreasing, and moreover π(m -2) + π(m -1) > π(0) because p m-2 + p m-1 > 1. It follows from Exercise 1.7.2 below that the code R m is optimal for this probability distribution.

Thus we have shown that the application of Huffman's algorithm to the truncated source produces the code R m P k . When h tends to infinity, the sequence of codes converges to R m 1 * 0. Since each of the codes in the sequence is optimal, the code R m 1 * 0 is an optimal prefix code for the geometric distribution. The Golomb code G m = 1 * 0R m has the same length distribution and so is also optimal.

Golomb-Rice codes. The Golomb-Rice code of order k, denoted GR k , is the par-

{ G o l o m b -R i c e c o d e }
ticular case of the Golomb code for m = 2 k . It was introduced in [START_REF] Rice | Some practical universal noiseless coding techniques[END_REF]. Its structure is especially simple and allows an easy explicit description. The encoding assigns to an integer n ≥ 0 the concatenation of two binary words, the base and the offset. The base is the unary expansion (over the alphabet {1}) of ⌊n/2 k ⌋ followed by a 0. The offset is the remainder of the division written in binary on k bits. Thus, for k = 2, the integer n = 9 is coded by 110|01. The binary trees representing the Golomb-Rice code of orders 0, 1, 2 are represented in Figure 1. [START_REF] Désarménien | La division par ordinateur des mots français: application à T E X[END_REF].

Another description of the Golomb-Rice code of order k is given by the regular expression { r e g u l a r e x p r e s s i o n

} GR k = 1 * 0{0, 1} k . (1.15) { e q : G R }
This indicates that the binary words forming the code are composed of a base of the form 1 i 0 for some i ≥ 0 and an offset which is an arbitrary binary sequence of

f GR k (z) = 2 k z k+1 1 -z = i≥k+1 2 k z i .
The weighted generating series of a code C with probability distribution π is The average length of C is then

λ C (z) = x∈C |x|π(x) = p ′ C (1)
.

For a uniform Bernoulli distribution on the channel symbols, the weighted generating series for the resulting probabilities of the Golomb-Rice codes GR k and the corresponding average length λ GR k are

p GR k (z) = f GR k (z/2) = z k+1 2 -z , λ GR k = p ′ GR k (1) = k + 2 . (1.16) { e q : a v L e n g t h G R }
Observe that in the case where p m = 1/2, the series p GR k (z), and thus also the average length λ GR k , happens to be the same for the probability distribution on the code induced by the geometric distribution on the source. Indeed, the sum of the probabilities of the codewords for rm to (r + 1)m -1 is p rm (1-p m ), and since p m = 1/2, this is equal to 2 -r-1 . The sum of the probabilities of m words of length r + k + 1 with respect to a uniform Bernoulli distribution is m2 -r-k-1 = 2 -r-1 (recall that m = 2 k ). Thus we get the same value in both cases, as claimed. mentioned and introduced in [START_REF] Elias | Universal codeword sets and representations of the integers[END_REF]. Exponential Golomb codes are used in practice in digital transmissions. In particular, they are a part of the video compression standard technically known as H.264/MPEG-4 Advanced Video Coding (AVC) [START_REF] Richardson | 264 and MPEG-4 Video Compression: Video Coding for Nextgeneration Multimedia[END_REF].

The codeword representing an integer n tends to be shorter for large integers. The base of the codeword for an integer n is obtained as follows. Let x be the binary expansion of 1 + ⌊n/2 k ⌋ and let i be its length. The base is made of the unary expansion of i-1 followed by x with its initial 1 replaced by a 0. The offset is, as before, the binary expansion of the remainder of the division of n by 2 k , written on k bits. Thus, for k = 1, the codeword for 9 is 11001|1. Figure 1.17 represents the binary trees of the exponential Golomb codes of orders 0, 1, 2. An expression describing the exponential Golomb code of order k is

EG k = i≥0 1 i 0{0, 1} i+k ,
and we have the simple relation

EG k = EG 0 {0, 1} k .
The generating series of the lengths of words in EG k is

f EG k (z) = 2 k z k+1 1 -2z 2 .
The weighted generating series for the probabilities of codewords corresponding to a uniform Bernoulli distribution and the average length are For handling signed integers, there is a simple method which consists of adding a bit to the words of one of the previous codes. More sophisticated methods, adapted to a two-sided geometric distribution, have been developed in [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF].

p EG k (z) = z k+1 2 -z 2 λ EG k = k + 3 .

Exercises

Exercise 1.7.1. Show that the entropy H = -π(n) log π(n) of the source emitting integers with a geometric distribution (1. [START_REF] Bruyère | Variable-length maximal codes[END_REF]) is

H = -(p log p + q log q)/q .
Verify directly that, for p 2 k = 1/2, the average length of the Golomb-Rice code

GR k satisfies λ GR k ≤ H + 1. Exercise 1.7.2. Let m ≥ 3. A nonincreasing sequence w 1 ≥ w 2 ≥ . . . ≥ w m of integers is said to be quasi-uniform if it satisfies w m-1 + w m ≥ w 1 .
Let T be an { q u a s i -u n i f o r m s e q u e n c e } optimal binary tree corresponding to a quasi-uniform sequence of weights. Show that the heights of the leaves of T differ at most by one.

Encoders and decoders

In this section, we present the basic notions of automata theory, as far as encoding and decoding processes are concerned. The notion of finite automata allows us to define a state-dependent process which can be used both for encoding and decoding. We give the definition of two closely related notions, namely automata and transducers, which are both labeled directed graphs.

A finite automaton A over some (finite are quadruples (p, u, v, q) where p and q are states and u is a word over A and v is a word over B. An edge is also denoted by p u|v → q. The main purpose for transducers is decoding. In this case, A is the channel alphabet and B is the source alphabet.

)
A path in an automaton or in a transducer is a sequence of consecutive edges. The label of the path is obtained by concatenating the labels of the edges (in the case of a transducer, one concatenates separately the input and the output labels). We write p w → q for a path in an automaton labeled with w starting in state p and ending in state q. Similarly, we write p x|y --→ q for a path in a transducer. A path is

Codes and Automata 33

successful if it starts in an initial state and ends in a terminal state.

{ s u c c e s s f u l p a t h }

An automaton A recognizes a set of words, which is the set of labels of its mapping from the input words into the output words, and also as a multi-valued mapping from the output words into the input words. For practical purposes, this definition is too general and will be specialized. We consider transducers called literal , which by definition means that each input label is a single letter. For Transducers for decoding are more interesting. For the purpose of coding and decoding, we are concerned with transducers which define single-valued mappings in both directions. We need two additional notions.

An automaton is called deterministic if it has a unique initial state and if, for

{ d e t e r m i n i s t i c ! a u t o m a t o n } { a u t o m a t o n ! d e t e r m i n i s t i c } each state p and each letter a, there is at most one edge starting in p and labeled with a. This implies that, for each state p and each word w, there exists at most one path starting in p and labeled with w. Consider a finite deterministic automaton with a unique terminal state which is equal to the initial state i. The closed paths from i to i such that no initial segment ends in i are called first return paths. The set of labels of these paths is a regular all words w, there is at most one path from p to q labeled with w. Clearly, a deterministic automaton is unambiguous.

A literal transducer defines naturally an automaton over its input alphabet, called its input automaton. For simplicity, we discard the possibility of multiple An important result is that for any encoding (with finite source and channel alphabets), there exists a literal unambiguous transducer which realizes the associated decoding. When the code is prefix, the transducer is actually deterministic.

The construction is as follows. Let γ be an encoding. Define a transducer T by taking a state for each proper prefix of some codeword. The state corresponding to the empty word ε is the initial and terminal state. There is an edge p a|---→ pa, where -represents the empty word, for each prefix p and letter a such that pa is a prefix, and an edge p a|b → ε for each p and letter a with pa = γ(b). When the code is prefix, the decoder is deterministic. In the general case, the property of unique decipherability is reflected by the fact that the transducer is unambiguous. As a consequence of this construction, it can be shown that decoding can always be realized in linear time with respect to the length of the encoded string (considering the number of states as a constant). Indeed, given a word w = a 1 • • • a n of length n to be decoded, one computes the sequence of sets S i of states accessible from the initial state for each prefix a 1 • • • a i of length i of w, with the convention S 0 = {ε}. Of course the terminal state ε is in S n . Working backwards, we set q n = ε and we identify in each set S i the unique state q i such that there is an edge q i ai → q i+1 in the input automaton. The uniqueness comes from the unambiguity of the transducer. The corresponding sequence of output labels gives the decoding. This construction The notion of deterministic transducer is too constrained for the purpose of coding and decoding because it does not allow a lookahead on the input or equivalently a delay on the output. The notion of sequential transducer to be introduced now fills this gap. A sequential transducer is composed of a deterministic transducer and an output { s e q u e n t i a l t r a n s d u c e r } { t r a n s d u c e r ! s e q u e n t i a l } M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel function. This function maps the terminal states of the transducer into words on the output alphabet. The function realized by a sequential transducer is obtained by appending, to the value of the deterministic transducer, the image of the output function on the arrival state. Formally, the value on the input word x is

f (x) = g(x)σ(i • x) ,
where g(x) is the value of the deterministic transducer on the input word x, i • x is the state reached from the input state i by the word x, and σ is the output function. This is defined only if the state i • x is a terminal state.

Example 1.18. The sequential transducer given in Figure 1.22 realizes the partial function aw → wa, for each word w. The output function σ is given by σ(0) = ε and σ(1) = a.

It is a well-known property of finite automata that any finite automaton is equivalent to a finite deterministic automaton. The process realizing this transformation is known as the determinization algorithm. This remarkable property does not hold { d e t e r m i n i z a t i o n a l g o r i t h m } { a l g o r i t h m ! d e t e r m i n i z a t i o n } in general for transducers.

Nonetheless, there is an effective procedure to compute a sequential transducer S that is equivalent to a given literal transducer T , whenever such a transducer exists, see [START_REF] Lothaire | Applied Combinatorics on Words, volume 105 of Encyclopedia of Mathematics and its Applications[END_REF]. The algorithm goes as follows.

The states of S are sets of pairs (u, p). Each pair (u, p) is composed of an output word u and a state p of T . For a state s of S and an input letter a, one first computes the set s of pairs (uv, q) such that there is a pair (u, p) in s and an edge p a|v → q in T . In a second step, one chooses some common prefix z of all words uv, and one defines the set t = {(w, q) | (zw, q) ∈ s}. There is a transition from state s to a state t labelled with (a, z). The initial state is (ε, i), where i is the initial state of T . The terminal states are the sets t containing a pair (u, q) with q terminal in T . The output function σ is defined on state t of S by σ(t) = u. If there are several pairs (u, q) in t with distinct u for the same terminal state q, then the given transducer does not compute a function and thus it is not equivalent to a sequential one.

The process of building new states of S may not halt if the lengths of the words which are the components of the pairs are not bounded. There exist a priori bounds for the maximal length of the words appearing whenever the determinization is possible, provided that, at each step, the longest common prefix is chosen. This makes the procedure effective. (ca n-1 , ε). Thus the algorithm does not terminate, and there is no equivalent sequential transducer. Exercise 1.8.3. Show that a finite code is weakly prefix if and only if it can be decoded by a sequential transducer.

Exercises

Codes for constrained channels

The problem considered in this section arises in connection with the use of communication channels which impose input constraints on the sequences that can be transmitted. User messages are encoded to satisfy the constraint; the encoded messages are transmitted across the channel and then decoded by an inverse to the encoder.

In this context, we will use a more general notion of encoding. Instead of a memoryless substitution of source symbols by codewords, we will consider finite transducers: the codeword associated to a source symbol depends not only on this symbol, but also on a state depending on the past.

We require, in order to be able to decode, that the encoder is unambiguous on its output in the sense that for each pair of states and each word w, there is at most one path between these states with output label w. For ease of use, we will also assume that the input automaton of the encoder is deterministic. if the encoding starts in state 1. A more complicated example of a deterministic encoder that will be described later is depicted in Figure 1.31.

A stronger condition for a decoder than unambiguity is that of having finite look-ahead . This means that there exists an integer D ≥ 0 such that, for all states q { l o o k -a h e a d } and all channel sequences w of length D + 1, all paths that begin at state q and have channel label w share the same first edge (and therefore the first source symbol). In other words, decoding is a function of the current state, the current channel symbol, and the upcoming string of D channel symbols [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. These decoders correspond to sequential transducers as introduced in Section 1.8.

However, even this condition is heavily state-dependent, and so a channel error which causes the decoder to lose track of the current state may propagate errors forever. For this reason, the following stronger condition is usually employed.

A sliding block decoder operates on words of channel symbols with a window → r and p ′ u → q ′ v → r ′ imply that q = q ′ . A transducer is said to be local if its input automaton is local. A sliding block decoder can be realized by a local transducer with the same parameters. Conversely, a transducer which is (m, a)-local and such that the input label and the output label of each edge have the same length is a sliding block decoder.

Codes and Automata 39

While input constraints have been imposed in some communication channels, they arise more commonly in data recording channels, such as those found in magnetic and optical disk drives. Constraints on inputs are of various types and have changed over the course of the fifty-year history of magnetic disk drives. For illustration, we focus on the [d, k]-constraint, where 0 ≤ d ≤ k. A binary sequence is said to satisfy the [d, k]-constraint if the number of contiguous symbols 0 between consecutive symbols 1 is at least d and at most k.

These constraints arise for the following reasons. An electrical current in the write head, situated over the spinning disk, creates a magnetic field which is reversed when the current polarity is reversed. These write field reversals, in turn, induce reversals in the orientation of the magnetization along the recorded track on the disk. During the data recovery process, the read head senses the recorded pattern of magnetization along the track. Each transition in magnetization direction produces a correspondingly oriented pulse in the readback voltage.

Two problems should be avoided. The first is called intersymbol interference. If polarity changes are too close together, the induced magnetic fields tend to interfere and the pulses in the readback signal are harder to detect. The second problem is called clock drift. This problem arises when the pulses are separated by intervals of time which are too large. When the read head senses a pulse it sends information through a phase lock loop which keeps the bit clock running accurately; if the separation between pulses is too large, the clock can lose synchronization and skip through a complete bit period.

Several values of the parameters d, k are of practical importance. The simplest case is the constraint [START_REF] Adler | Algorithms for sliding block codes[END_REF][START_REF] Adler | Equivalence of topological Markov shifts[END_REF]. This means that the blocks 11 and 0000 are forbidden. The binary sequences satisfying this constraint are those which label paths in the graph of Figure 1.25. We consider an encoding of all binary sequences by sequences satisfying the [START_REF] Adler | Algorithms for sliding block codes[END_REF][START_REF] Adler | Equivalence of topological Markov shifts[END_REF]-constraint. This encoding is not realizable by a sequential encoder without modifying the output alphabet, because there are more binary source sequences of length n than admissible binary channel sequences of length n. However, it is possible to operate at rate 1 : 2, by encoding a source bit by one of the 2-bit symbols a = 00, b = 01 or c = 10. A particular way of doing this is the MFM (Modified Frequency Modulation, see e.g. [START_REF] Marcus | Constrained systems and coding for recording channels[END_REF]) code of Figure 1.26, which was used on floppy disks for many years.

Observe that the second bit of the output is always equal to the input bit, and The result of the development that follows will be the sequential transducer for encoding known as the Franaszek encoder depicted in Figure 1.31. It must be checked that this encoder satisfies the [START_REF] Adler | State splitting for variable-length graphs[END_REF][START_REF] Béal | Codage symbolique[END_REF]-constraint and that, for practical applications, it admits a sliding block decoder. A direct verification is possible but complicated.

The encoder design process we now describe is the one historically followed by Franaszek [START_REF] Franaszek | Run-length-limited variable length coding with error propagation limitation[END_REF]. It starts with the graph in Figure 1 that the set C has the same length distribution as the maximal binary prefix code P of words appearing in the right column.

The pair of prefix codes of Figure 1.30 is used as follows to encode a binary word at rate 1 : 2. A source message is parsed as a sequence of codewords in P , possibly followed by a prefix of such a word. For example, the word 011011100101110111100010011

• • • is parsed as 011 | 011 | 10 | 010 | 11 | 10 | 11 | 11 | 000 | 10 | 011 • • • .
Next, this is encoded row-by-row using the correspondence between P and C as follows This stands for the channel encoding 001000|001000|0100|100100|1000|0100|1000|1000|000100|0100|001000 .

aca | aca | ba | cba | ca | ba | ca | ca | aba | ba |
Figure 1.31 represents an implementation of this transformation, up to some shift. The encoder is a deterministic transducer which outputs one symbol for each input symbol. State 1 is the initial state, and all states are terminal states. All inputs of at least 2 symbols produce an output sequence that begins with ba, followed by the sequence generated by the encoder described above, up to the last two symbols. For example, for the input word 011011, the corresponding path in the deterministic encoder is

1 0|b → 2 1|a → 5 1|a → 6 0|c → 2 1|a → 5 1|a → 6 .
So, the output is ba|aca|a, which, following the initial ba, corresponds to one codeword aca followed by the beginning of a second occurrence of aca. This encoder can be obtained as follows from the pair (C, P ) of prefix codes. Consider first the transducer of Figure 1.32. This is obtained by composing a decoder for P with an encoder for C, and merging common prefixes. We omit the details.

We build a deterministic transducer by determinization of the transducer of Figure 1.32, by the algorithm presented in Section 1.8. In this case, we are able to maintain a constant rate of output by keeping always in the pairs of the sequential transducer an output word of length 2 (this represents the two symbols to be output later). Thus the output is delayed with two symbols.

The states of the result are given in Table 1.3. In this table, and also in Figure 1.31, we only report the states which have an output delay of exactly two symbols. They correspond to the strongly connected part of the encoder. In particular, the initial state (ε, 1) is not represented. Figure 1.33 gives the states reached by the first two symbols.

.34 represents the decoder, which can be realized with a sliding window of size 4. Indeed, the diagrams of Figure 1.34 show that for any content xyzt of the window, we can define the output r corresponding to the third symbol. If y = b, then r = 0. Indeed, an inspection of Table 1.30 shows that any b is followed by an a which is coded by a 0. In the same way, if y = c, then r = 1. If y = a, then four cases arise. If z = a, then r = 0 (in particular any initial a of C is coded 0). If z = c, then r = 0 or 1 according to t = b or a. Finally, if z = b, then r = 0 if z = b and r = 1 otherwise (the x in the last frame stands for b or c).

There are many approaches to the design of encoder-decoder pairs for input constraints. The approach illustrated above was extended to a technique called the method of poles, developed by Béal [6;[START_REF] Béal | Codage symbolique[END_REF][START_REF] Béal | Extensions of the method of poles for code construction[END_REF].

Another approach is the state-splitting algorithm, also known as the ACH algo-{ s t a t e -s p l i t t i n g a l g o r i t h m } { a l g o r i t h m ! s t a t e -s p l i t t i n g } rithm [START_REF] Adler | Algorithms for sliding block codes[END_REF], which transforms a finite-state graph representation of a constraint into

{ A C H a l g o r i t h m } { a l g o r i t h m ! A C H }
a sliding-block decodable finite-state encoder. The rough idea is as follows.

One starts with a finite-state graph representation of the constraint and then chooses a feasible encoding rate p : q; here, feasibility means that p/q does not exceed the capacity of the constraint, which is a measure of the "size" or "complexity" of the constraint and generalizes the notion of capacity of a variable-length code given in Section 1.5. The capacity can be computed explicitly, and for a feasible code rate, one can compute a vector, called an approximate eigenvector, which effectively assigns non-negative integer weights to the states of the graph [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. Next, one replaces the original representation with a new one whose symbols are q-bit strings, just as in the transformation of Figure 1.27 to Figure 1.28 above. Then by an iterative sequence of state splittings, guided by an approximate eigenvector, one is guaranteed to arrive at a final representation upon which a sequential finite-state encoder can be built. The splittings are graph transformations in which states are split according to partitions of outgoing edges. In the final representation, each state has at least 2 p outgoing edges, enabling an assignment of p-bit input labels and therefore a sequential finite-state encoder at rate p : q. It is also guaranteed, under mild conditions, that such an encoder is sliding-block decodable. The state splitting algorithm has been modified in many ways. For instance, one could consider finite-state variable-length representations of input constraints or transform fixed-length representations into more compact variable-length representations. There is a variable-length version of the state splitting algorithm, which again iteratively splits states. In this setting, instead of aiming for a graph with sufficient out-degree at each state, the sequence of state splittings results in a final representation in which the lengths of outgoing edges at each state satisfy a reverse Kraft inequality. This technique was introduced in [START_REF] Adler | State splitting for variable-length graphs[END_REF] and further developed in [START_REF] Heegard | Variable-length state splitting with applications to average runlength-constrained (ARC) codes[END_REF]. In the latter reference the method was illustrated with two examples, one of which is an alternative derivation of the Franaszek code described above.

The theory and practice of coding for constrained channels is very well developed.

For more information, the reader may consult Béal [START_REF] Béal | Codage symbolique[END_REF], Immink [START_REF] Kees | Codes for Mass Data Storage Systems[END_REF], Lind-Marcus [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] and Marcus-Siegel-Roth [START_REF] Marcus | Constrained systems and coding for recording channels[END_REF] (or the latest version at http://www.math.ubc.ca/˜marcus/Handbook/index.html).

Codes and Automata 45

Exercises Exercise 1.9.1. A code C over the alphabet A is a circular code if, for any words

{ c i r c u l a r c o d e } { c o d e ! c i r c u l a r }
u, v on the alphabet A, the cyclically shifted words uv and vu can be in C * only when u and v are. Let C be a circular code and let x be a word of C. Show that a set D of words of the form x i y, for i ≥ 0 and y in C \ x, is a circular code. Note: the terminology circular code stems from the fact that the unique decipherability property holds for words written on a circle (see [START_REF] Berstel | Theory of Codes[END_REF]).

Exercise 1.9.2. Use Exercise 1.9.1 to show that the set C = {ba, ca, aba, cba, aca, acba, aaca} appearing in the first column of Figure 1.30 is a circular code.

Codes for constrained sources

In the same way as there exist codes for constrained channels, there exist codes for constrained sources. As for constraints on channels, the constraints on sources can be expressed by means of finite automata. This leads us to use encodings with memory.

We limit the presentation to two examples, the first drawn from linguistics, and the second reflecting a more general point of view.

The first example gives an interesting encoding from a constrained source to an unconstrained channel [START_REF] Gönenç | Unique decipherability of codes with constraints with application to syllabification of Turkish words[END_REF]. It starts with a simple substitution which is not uniquely decipherable, but it appears to be uniquely decipherable by taking into account the constraints on the source. The example is taken from the field of natural language processing where codings and automata are heavily used (see for instance [START_REF]Finite-State Language Processing[END_REF]).

Example 1.22. We start with a source alphabet composed of a sample set of six syllable types in the Turkish language. The concatenation of syllables is subject to constraints that will be explained below. The types of syllables are denoted by A to F . The structure of a syllable is the binary sequence obtained by coding 0 for a vowel and 1 for a consonant. We consider the structure of a syllable as its encoding. The decoding is then to recover the sequence of syllables from the encoding. Thus the source alphabet is {A, . . . , F }, the channel alphabet is {0, 1}, and the encoding is A → 0, . . . , F → 1011.

Symbol

There are linguistic constraints on the possible concatenations of syllable types which come from the fact that a syllable ending with a consonant cannot be followed by one which begins with a vowel. These constraints are summarized by the following matrix, where a 0 in entry x, y means that x cannot be followed by y.

M =          A B C D E F A 1 1 1 1 1 1 B 1 1 1 1 1 1 C 0 1 0 1 0 1 D 0 1 0 1 0 1 E 0 1 0 1 0 1 F 0 1 0 1 0 1         
.

The encoding can be realized in a straightforward manner with a 2-state transducer given in Figure 1.35 which reflects the legal concatenations of source symbols. The decoder is built by applying the methods of Section 1.8 to this transducer. We start by exchanging input and output labels in Figure 1. [START_REF] Te | Optimal computer search trees and variablelength alphabetical codes[END_REF]. In a second step, we introduce additional states in order to get literal output. An edge is broken into smaller edges. For instance, the edge 0

011|E → 1 is replaced by the path 0 0|- → E 1 1|- → E 2 1|E
→ 1. Each state x i stands for the prefix of length i of the encoding of x. The state x i can be used for several edges, because the arrival state depends only on x. The transducer is given in Figure 1. 36. It happens that the resulting transducer can be transformed into a sequential one. The result is shown in Figure 1.37. The correspondence is given in Table 1.4. The value of the output function is given in the node.

The decoder is deterministic in its input and it outputs the decoded sequence with finite delay (this means that it uses a finite look-ahead on the input). On termination of a correct input sequence, the last symbol to be produced is indicated by the corresponding state. This coding is used in [START_REF] Gönenç | Unique decipherability of codes with constraints with application to syllabification of Turkish words[END_REF] to build a syllabification algorithm which produces for each word a parsing in syllables.

Codes and Automata 47

0 D 1 D 2 1 1|- 0|- 1|D 1|- C 1 0|- 1|- B 1 1|- 0|- 1|- E 1 E 2 0|- 1|- 1|E 0|- F 1 F 2 F 3 1|- 0|- 1|- 1|F 0|-
A, 0 ε, C 1 ε, E 1 A, B 1 C, 1 ε, E 2 A, D 1 A, F 1 C, B 1 C, D 1 C, F 1 E, 1 CB, 0 C, D 2 C, F 2 ε, B 1 ε, D 1 ε, F 1 B, 0 ε, D 2 ε, F 2 B, B 1 B, D 1 , B, F 1 D, 1 ε, F 3 D, D 1 , D, F 1 D, B 1 F, 1 output A C E CB B D F
This kind of problem appears more generally in the framework of hyphenation in text processing software (see [START_REF] Désarménien | La division par ordinateur des mots français: application à T E X[END_REF] for example), and also in "text-to-speech" synthesis ( [START_REF] Dutoit | An Introduction to Text-To-Speech Synthesis[END_REF]).

{ t e x t -t o -s p e e c h s y n t h e s i s }

The next example of codes for constrained sources is from [START_REF] Dalai | Non prefix-free codes for constrained sequences[END_REF]. It illustrates again how an ambiguous substitution can be converted into a uniquely decipherable encoding.

The three examples below have decoders which are local (that is realizable by a sliding block decoder) for the first one, sequential for the second one, and simply unambiguous for the third one.

Example 1.23. Consider the constrained source on the symbols A, B, C with the constraint that B cannot follow A. We consider the substitution that maps A, B and C to 0, 1 and 01 respectively. The mapping is realized by the transducer on the left of Figure 1.38. It is easily seen that the constraint implies the unique decipherability property. Actually, a decoder can be computed by using the determinization algorithm. This yields the sequential decoder represented on the right of We now give a second, slightly more involved example. The source has four symbols A, B, C, D with the constraints of concatenation given by the matrix

M 2 =     A B C D A 1 0 1 0 B 0 1 0 1 C 1 1 1 1 D 1 1 1 1     .
We consider the encoding assigning 0, 1, 01 and 10 to A, B, C and D respectively. The decoder is given in Figure 1.39. This transducer is sequential with output function indicated in the states. However, it is not local in input since there are two cycles labeled by 01.

The third example uses the same substitution but a different set of constraints given by the matrix

M 3 =     A B C D A 1 0 1 1 B 0 1 1 1 C 0 1 1 1 D 1 0 1 1    
The substitution is realized by the transducer shown on the left of Figure 1 These examples are variable-length, and in fact variable-rate, codes. In applications where error propagation may be a problem, one can use fixed-rate block codes [START_REF] Kees | A practical method for approaching the channel capacity of constrained channels[END_REF] or fixed-rate sliding-block codes [START_REF] Fan | Lossless sliding-block compression of constrained systems[END_REF]. The construction of the latter is dual to the state splitting method mentioned in the previous section.

The connection between variable-length codes, unambiguous automata and local constraints has been further developed in [53; 52; 9].

Bifix codes

Recall that a set of words C is a suffix code if no element of C is a proper suffix of another one. A set of words is called a bifix code if it is at the same time a prefix

{ b i f i x c o d e } { c o d e ! b i f i x }
code and a suffix code. Bifix codes are also known as reversible variable-length codes (RVLC) . The idea to study bifix codes goes back to [START_REF] Schützenberger | On an application of semigroup methods to some problems in coding[END_REF] and [START_REF] Gilbert | Variable length binary encodings[END_REF]. These papers already contain significant results. The first systematic study is in [START_REF] Schützenberger | On a special class of recurrent events[END_REF], [START_REF] Schützenberger | On a family of submonoids[END_REF]. The One example is given by prefix codes which are equal to their reversal. The reversal of a word w = a 1 • • • a n , where a 1 , . . . , a n are symbols, is the word w = { r e v e r s a l } a n • • • a 1 obtained be reading w from right to left. The reversal of a set C, denoted C, is the set of reversals of its elements. For example, 01 * 0 is a bifix code since it is prefix and equal to its reversal.

The use of bifix codes for transmission is linked with the possibility of limiting the consequences of errors occurring in the transmission using a bidirectional decoding scheme as follows. Assume that we use a binary bifix code to transmit data and that for the transmission, messages are grouped into blocks of N source symbols, encoded as N codewords. The block of N codewords is first decoded by using

→ x 1 x 2 • • • x i-1 x i • • • x N ← Fig. 1.41.:
The transmission of a block of codewords.

an ordinary left-to-right sequential decoding. Suppose that the codewords x 1 up to x i-1 are correctly decoded, but that an error has occurred during transmission that makes it impossible to identify the next codeword in the rest of the message.

Then a new decoding process is started, this time from right to left. If at most one error has occurred, then again the codewords from x N down to x i+1 are decoded correctly. Thus, in a block of N encoded source symbols, at most one codeword will be read incorrectly. These codes are used for the compression of moving pictures. Indeed, there are reversible codes with the same length distribution as the Golomb-Rice codes, as shown in [START_REF] Wen | Reversible variable length codes for efficient and robust image and video coding[END_REF]. The Advanced Video Coding (AVC) standard mentioned previously recommends the use of these codes instead of the ordinary Golomb-Rice codes to obtain an error resilient coding (see [START_REF] Richardson | 264 and MPEG-4 Video Compression: Video Coding for Nextgeneration Multimedia[END_REF]). The difference from the ordinary codes is that, in the base, the word 1 i 0 is replaced by 10 i-1 1 for i ≥ 1. Since the set of bases forms a bifix code, the set of all codewords is also a bifix code. Figure 1.42 represents the reversible Golomb-Rice codes of orders 0, 1, 2.

There is also a reversible version of the exponential Golomb codes, denoted by REG k , which are bifix codes with the same length distribution. The code REG 0 is given by It is a bifix code because it is equal to its reversal. This comes from the fact that the set {00, 10} * {0, 1} is equal to its reversal because it is the set of words of odd length which have a 0 at each even position, starting at position 1.

REG 0 = {0} ∪ 1{00, 10} * {0, 1}1 .
The code of order k is

REG k = REG 0 {0, 1} k .
The codes REG k are represented for k = 0 and 2 on Figure 1.43. We now consider the length distribution of bifix codes. In contrast to the case of codes or of prefix codes, it is not true that any sequence (u n ) n≥1 of non-negative integers such that n≥1 u n k -n ≤ 1 is the length distribution of a bifix code on k letters. For instance, there is no bifix code on the alphabet {a, b} which has the same distribution as the prefix code {a, ba, bb}. Indeed, such a code must contain a letter, say a, and then the only possible word of length 2 is bb. On the other hand, the following result provides a sufficient condition for a length distribution to be realizable by a bifix code [START_REF] Ahlswede | Some properties of fix-free codes[END_REF]. there exists a bifix code on an alphabet of k letters with length distribution (u n ) n≥1 .

Proof. We show by induction on n ≥ 1 that there exists a bifix code X n of length distribution (u i ) 1≤i≤n on an alphabet A of k symbols. It is true for n = 1 since u 1 k -1 ≤ 1/2 and thus u 1 < k. Assume that the property is true for n. We have by Inequality (1.17)

n+1 i=1 u i k -i ≤ 1 2
or equivalently, multiplying both sides by 2k n+1 ,

2(u 1 k n + . . . + u n k + u n+1 ) ≤ k n+1 whence u n+1 ≤ 2u n+1 ≤ k n+1 -2(u 1 k n + . . . + u n k) . (1.18)
{ e q -i n t e r m e d i a i r e } Since X n is bifix by the induction hypothesis, we have

Card(X n A * ∩ A n+1 ) = Card(A * X n ∩ A n+1 ) = u 1 k n + . . . + u n k.
Thus, we have

Card((X n A * ∪ A * X n ) ∩ A n+1 ) ≤ Card(X n A * ∩ A n+1 ) + Card(A * X n ∩ A n+1 ) ≤ 2(u 1 k n + . . . + u n k) .
It follows from Inequality (1.18) that

u n+1 ≤ k n+1 -2(u 1 k n + . . . + u n k) ≤ Card(A n+1 ) -Card((X n A * ∪ A * X n ) ∩ A n+1 ) = Card(A n+1 -(X n A * ∪ A * X n ))
.

This shows that we can choose a set Y of u n+1 words of length n + 1 on the alphabet A which do not have a prefix or a suffix in X n . Then X n+1 = Y ∪ X n is bifix, which ends the proof.

C is (1/k)f ′ C (1/k). Indeed, setting f C (z) = n≥1 u n z n , one gets f ′ C (z) = n≥1 nu n z n-1 and thus (1/k)f ′ C (1/k) = n≥1 nu n k -n .
It is known that the average length of a regular maximal bifix code is an integer, called the degree of the code [26; 61]. For example, the maximal bifix code C represented in Figure 1.44 has degree 3. One has

f C (z) = z 2 + 4z 3 + 4z 4 , f ′ C (z) = 2z + 12z 2 + 16z 3 ,
and thus f C (1/2) = 1 and (1/2)f ′ C (1/2) = 3. Table 1.6 lists the length distributions of finite maximal bifix codes of degree d ≤ 4 over {a, b}. For each degree, the last column contains the number of bifix codes with this distribution, with a total number of 73 of degree 4. Note that for the highlighted distribution (0, 1, 4, 4), there are two distinct bifix codes. One is the code of Figure 1.44, and the other is obtained by exchanging 0 and 1.

We have seen (Equation (1.16)) that the Golomb-Rice code of order k has average length k + 2 for the uniform Bernoulli distribution on the alphabet. The same holds of course for the reversible one. The fact that the average length is an integer is a necessary condition for the existence of a reversible version of any regular prefix code, as we have already mentioned before. The average length of the Golomb code G 3 is easily seen to be 7/2 for the uniform Bernoulli distribution. Since this is not an integer, there is no regular bifix code with the same length distribution (0, 1, 3, 3, . . .). Actually, one may verify that there is not even a binary bifix code with length distribution (0, 1, 3, 3, 2).

Codes and Automata 55

Table 1.6.: The length distributions of binary finite maximal bifix codes of degree at most 4.

Exercises

Exercise 1.11.1. The aim of this exercise is to describe a method, due to Girod [START_REF] Girod | Bidirectionally decodable streams of prefix code words[END_REF] (see also [START_REF] Salomon | Variable-Length Codes for Data Compression[END_REF]), which allows a decoding in both directions for any finite binary prefix code. Let C be a finite binary prefix code and let L be the maximal length of the words of C. Consider a concatenation c

1 c 2 • • • c n of codewords. Let w = c 1 c 2 • • • c n 0 L ⊕ 0 L c1 c2 • • • cn (1.19) { e q G i r o d }
where c is the reverse of the word c and where ⊕ denotes addition mod 2. Show that w can be decoded in both directions.

Synchronizing words

A word v is said to be synchronizing for a prefix code C if for any words u, w, one has uvw in C * only if uv and w are in C * . Thus the decoding of a message where v appears has to break at the end of v. A prefix code is said to be synchronized if there exists a synchronizing word. An occurrence of a synchronizing word limits the propagation of errors that have occurred during the transmission, as shown in the following example. On the contrary v = 0110 is synchronizing. Indeed, the only possible parsings of v in some context are

• • • 0|110| • • • and • • • |01|10| • • • .
In both cases, the parsing has a cut point at the end of v. To see how an occurrence of v avoids error propagation, consider the message in the first row below and the corrupted version below it produced when an error has changed the third bit of the message from 0 to 1.

0 1|0 1|1 0|1 1 1|0 1|1 0|0 1|0 1 0 1|1 1 1|0 1|1 1 0|1 1 0|0 1|0 1
After the occurrence of 0110, the parsings on both rows become identical again. Thus the occurrence of the word v has stopped the propagation of the error. Note that it can also happen that the resulting message does not have a decoding anymore. This happens for example if the second bit of the message is changed from 1 to 0. In this case, the error is detected and some appropriate action may be taken.

In the previous case, the error is not detectable and may propagate for an arbitrary number of bits.

Example 1.25. The word 010 is synchronizing for the prefix code C used in the Franaszek code (see Figure 1.30).

A synchronizing word can also be defined for a deterministic automaton. Let A be a deterministic automaton. A word w is said to be synchronizing for A if { s y n c h r o n i z i n g w o r d } all paths labeled w end at the same state. Thus the state reached after reading a synchronizing word is independent of the starting state. A deterministic automaton is said to be synchronized if there exists a synchronizing word for the automaton. Let i be a state of a strongly connected deterministic automaton A. Let C be the prefix code of first returns from i to i. Then C has a synchronizing word if and only if A is synchronized. First, let v be a synchronizing word for C. Then any path labeled v ends at state i. Indeed, if p v → q let u, w be such that i u → p and q w → i. Then uvw is in C * , which implies that uv is in C * . This implies that q = i since the automaton is deterministic. Thus v is synchronizing for the automaton A. Conversely, if v is synchronizing for A, then since A is strongly connected, there is a word w such that all paths labeled vw end at state i. Then vw is a synchronizing word for C.

Example 1.26. Let A be the automaton represented on Figure 1.45. Each word w defines an action on the set of states which is the partial function which maps a state p to the state reached from p by the path labeled by the input word w. The set of first returns to state 1 is the maximal prefix code C = {00, 01, 110, 111} of Example 1.24. In Table 1.7 are listed the actions of words of length at most 4. The words are ordered by their length, and within words of the same length, by lexicographic order. Each column is reported only the first time it occurs. We stop at the first synchronizing word which is 0110. It is important to note that for equal letter costs, an optimal prefix code can always be chosen to be synchronized (provided the greatest common divisor of the lengths is 1). Indeed, the relabeling of an automaton accepting such a code does not change its length distribution. The Franaszek code of Section 1.9 is actually chosen in such a way that the code on the right of Figure 1.30 is synchronized (010 is a synchronizing word).

For unequal letter costs, it has been proved that the result holds for finite maximal codes. Indeed, it is proved in [START_REF] Perrin | Synchronizing prefix codes and automata and the road coloring problem[END_REF] (see also [START_REF] Berstel | Codes and Automata[END_REF]) that any finite maximal prefix code is commutatively equivalent to a synchronized prefix code.

Directions for future research

The field of variable-length codes and automata has a number of challenging mathematical open problems. They are often formulated as conjectures, some of which have been open for many years. Their solution would increase our understanding of these objects and give rise to new algorithms. Let us mention the following ones of particular importance.

The structure of finite maximal codes. It is not known whether it is decidable whether a finite code is or is not contained in a finite maximal code. In contrast, it is known that any finite code is contained in a regular maximal code (see e.g. [START_REF] Berstel | Codes and Automata[END_REF]).

Another open question is the status of the conjecture concerning the commuta-

Codes and Automata 59

tive equivalence of any finite maximal code to a prefix code. This conjecture would itself be solved if one could prove the factorization conjecture asserting that for any finite maximal code on the alphabet A, there exist two finite sets of words P, Q on the alphabet A such that any word on the alphabet A has a unique expression of the form pc 1 c 2 • • • c n q with p ∈ P , c i ∈ C and q ∈ Q.

Optimal prefix codes. There is still some work to be done to derive efficient methods for building an optimal prefix code corresponding to a source with an infinite number of elements.

Synchronized automata. It is conjectured that for any synchronized deterministic automaton with n states, there exists a synchronizing word of length at most (n -1) 2 . This conjecture is known as Černy's conjecture. The length of the shortest synchronizing word has practical significance since an occurrence of a synchronizing word has an error-correcting effect. The best known upper bound is cubic. The conjecture is known to be true in several particular cases.

Constrained channels. For a given constrained channel and allowable code rate, the problem of designing codes that achieve the minimum possible number of encoder states or the minimum sliding block decoder window size remains open.

Bifix codes. No method similar to the Huffman algorithm is known for building an optimal bifix code given a source with weights. It is perhaps related to the fact that the length distributions of bifix codes are not well understood. In particular, the question whether any sequence (u n ) n≥1 such that n≥1 u n k -n ≤ 3/4 is the length distribution of a bifix code over a k-letter alphabet is still open.

Conclusion

We have described basic properties of variable-length codes, and some of their uses in the design of optimal codes under various constraints. We have shown some of the relations between codes, finite state automata and finite transducers, both devices for encoding and decoding.

Optimal codes. Among variable-length codes, the most frequently used are prefix codes. These codes are instantaneously decipherable codes. The Elias, Golomb and Golomb-Rice codes are examples of prefix codes that are infinite, and that encode non-negative integers by an algorithm that is easy to implement. Other prefix codes that encode integers have been designed. For a systematic description, see [START_REF] Salomon | Variable-Length Codes for Data Compression[END_REF]. Optimal prefix codes for various constraints have been given in this chapter.

It is interesting to note that the general problem is still open, and the research is still going on (see [START_REF] Golin | Huffman coding with unequal letter costs[END_REF] for a recent contribution). General codes. Prefix codes are special codes. Other families of codes have been studied, and a general theory of variable-length codes addresses the properties of these codes. In this context, it is natural to associate to any code C an automaton that recognizes the set C * of all sequences of codewords. Many properties or parameters of codes are reflected by features of these automata. It appears that properties of codes are combinatorial in nature, but they can also be described in an algebraic way based upon the structural properties of the associated automaton or the algebraic properties of the transition monoid of the automaton, also called the syntactic monoid. See [START_REF] Berstel | Codes and Automata[END_REF].

Constrained channels. We have also briefly investigated constraints on the channel. The theory of sliding block codes is much broader in scope than we could convey here. Research is motivated by applications, as we have illustrated by the example of the Franaszek code. For more information along these lines, see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] and [START_REF] Béal | Codage symbolique[END_REF].

Solutions to exercises

Solution to 1.6.1. One has l i ≥ log 1/p i and thus

i 2 -ℓi ≤ i 2 -log 1 p i = i 2 log pi = i p i = 1
Let C be a prefix code with length distribution ℓ i . Since ℓ i ≤ log 1/p i + 1 its average length W satisfies

W = p i ℓ i ≤ p i (log 1 p i + 1) = p i log 1 p i + 1 = H + 1.
Solution to 1.6.2. Each word of P followed by a letter is either in P or in C, but not in both. Moreover, any nonempty word in C or P is obtained in this way. This shows that P A ∪ {ǫ} = P ∪ C. Counting the elements on both sides gives Card(P ) Card(A) + 1 = Card(P ) + Card(C).

Solution to 1.6.3. Let P be the set of words on the alphabet A which do not have s as a factor. Then P is also the set of proper prefixes of the words of the maximal prefix code X. Thus, we have P {0, 1} ∪ {ǫ} = X ∪ P , whence f P (z)(1 -2z) = 1 -f X (z). On the other hand, we have P s = XQ and thus

z p f P (z) = f X (z)f Q (z).
Combining these relations and solving in f X gives the desired solution.

Solution to 1.6.4. One has Q = {ǫ, 01} and thus f Q

(z) = 1 + z 2 .
Solution to 1.6.5. Since z p + 2zf X (z) = f X (z) + f U (z), the result follows from (1.12). Prefix synchronized codes were introduced by Gilbert [START_REF] Gilbert | Synchronization of binary messages[END_REF], who conjectured that for any n ≥ 1, the maximal cardinality is obtained for an unbordered word such Conversely, if C is a weakly prefix code, the determinization algorithm gives a sequential decoder.

Solution to 1.9.1. First, observe that D, viewed as a code over the alphabet C, is a prefix code. Thus D is a code. Assume now that u, v are such that uv and vu are in D * . Then, since C is circular, u and v are in

C * . Set u = x 1 • • • x n and v = x n+1 • • • x n+m . Since uv is in D * , we have x n+m = x and thus v is in D * .
Similarly, since vu is in D * , we have x n = x and thus u is in D * . Thus D is circular.

Solution to 1.9.2. We use repeatedly Exercise 1.9.1 to form a sequence C 0 , C 1 , . . . of circular codes. To form C i+1 , we choose one element x i in C i and select words of the form x k i y with y = x i . We start with C 0 = {a, b, c} which is obviously circular, and we choose x 0 = c. Then C 1 = {a, b, ca, cb} is a circular code. Choosing next x 1 = cb, we build C 2 = {a, b, ca, cba}. Then, we choose x 2 = b to obtain C 3 = {a, ba, ca, cba}. A final choice of x 3 = a shows that C is of the required form.

Note: this construction is used in a more general setting in the study of circular codes ( [START_REF] Berstel | Theory of Codes[END_REF]).

Solution to 1.11.1. The definition of w being symmetrical, it is enough to show that w can be decoded from left to right. By construction, c 1 is a prefix of w and the first codeword can therefore be decoded. But this also identifies the prefix of length L + |c 1 | of the second term of the right side of (1.19). Adding this prefix to the corresponding prefix of w gives a word beginning with c 1 c 2 and thus identifies c 2 , and so on. Answer. There are only two possibilities to obtain two factorizations starting at the same point. Both alternate indefinitely and never come to coincide. Thus, the code is uniquely decipherable. Answer. The general method gives the unambiguous transducer of Figure 1.51 with a = 0 and b = 001. The procedure described in Section 1.8 applied to the transducer of Figure 1.51 gives the sequential transducer of Figure 1.52. We obtain three states given in Table 1.16 with the values of the output function in the last column. Answer. The expression of the reversal of RGR k is RGR k = RGR 0 {0, 1} k since RGR 0 is its own reversal. The corresponding trees are represented in Figure 1.54.

Keywords

The following list of keywords is a kind of dictionary of terms used in this chapter with an explanation of each entry.

finite automaton A finite set of states, together with two distinguished subsets called the sets of initial and terminal states, and a set of edges which are triples consisting of a pair of states and a symbol in some (finite) alphabet A. unambiguous automaton A finite automaton such for every pair of states and every word over the alphabet, there is at most one path (i.e., sequence of edges) from the first state of the pair to the second that is labeled with the word. deterministic automaton A finite automaton with a unique initial state such that, for each state and each symbol in an alphabet, there is at most one edge starting in that state and labeled with that symbol. determinization algorithm An algorithm that transforms any finite automaton into an equivalent deterministic finite automaton.

Codes and Automata 67

regular set A set of words generated by paths in a finite automaton, starting at an initial state and ending in a terminal state. transducer A finite state automaton with output realizing a relation between words on an input alphabet A and words on an output alphabet B. It is similar to an automaton, but edges are quadruples consisting of a pair of states, a word over A, and a word over B. The main purpose for transducers is decoding. In this case, A is the channel alphabet and B is the source alphabet. literal transducer A transducer such that each input label is a single letter. unambiguous transducer A literal transducer whose associated input automaton is unambiguous. deterministic transducer A literal transducer whose associated input automaton is deterministic. sequential transducer A deterministic transducer and an output function. This function maps the terminal states of the transducer into words on the output alphabet. The function realized by a sequential transducer is obtained by appending, to the value of the deterministic transducer, the image of the output function on the arrival state. alphabetic coding An order preserving encoding. The source and the channel alphabets are ordered, and the codewords are ordered lexicographically. optimal source coding An encoding which minimizes the weighted cost. The weights are on the source alphabet and the costs on the channel alphabet. code A set of nonempty words over an alphabet A such that every concatenation of codewords is uniquely decipherable. prefix (suffix) code A set of nonempty words over an alphabet A such that no word in the set is a proper prefix (suffix) of another one. reversible code A code which is prefix and which is also prefix when the words are read from right to left. Such a code is also called bifix. maximal code A code (the image of an encoding) that is not strictly contained in another code. constrained channel A communication channel which imposes input constraints on the channel symbol sequences that can be transmitted. constrained source A source that imposes constraints on the sequences of source alphabet symbols that it generates. symbolic dynamics The study of symbolic representations of dynamical systems and code mappings between such representations. sliding block decoder A decoder that operates on strings of channel symbols with a window of fixed size. The decoder uses m symbols before the current one and a symbols after it (m is for memory and a for anticipation). According to the value of the symbols between time n -m and time n + a, the value of the n-th source symbol is determined. state splitting algorithm An algorithm that transforms a finite-state graph representation of a constraint into a sliding-block decodable finite-state encoder. commutative equivalence A relation between two codes in which there is a oneto-one correspondence between codewords such that corresponding pairs of words have the same number of occurrences of each alphabet symbol (that is, they are anagrams). channel capacity The maximum amount of information that can be transmitted over the channel per unit cost. In many applications, the cost of a symbol corresponds to the number of channel uses or the time required to transmit it. The capacity is then a measure of the amount of information that can be transmitted over the channel per channel use. binary source entropy A measure of the average number of bits per symbol required to represent a source with weighted source symbols. generating series The power series whose coefficients are the number of words or the probabilities of words of each length. synchronizing word A word for a finite automaton such that all paths labeled by this word end in the same state. geometric distribution A probability distribution π on the set of nonnegative integers such that π(n + 1)/π(n) is constant.

Index

Fig. 1 .

 1 Fig. 1.2.: The [2,7] Franaszek code.

{

  w o r d } { l e n g t h ! o f a w o r d } letters. The length of a word w is denoted by |w|. The empty word , usually denoted { e m p t y w o r d } { w o r d ! e m p t y } by ε, is the unique word of length 0. The set of all words over the alphabet A is denoted by A * . We denote by juxtaposition the concatenation of words. If w, x, y, z { c o n c a t e n a t i o n } are words, and if w = xy, then x is a prefix , and y is a suffix of w. If w = xyz, then

{ s o u r c e a l p

  h a b e t } { a l p h a b e t ! s o u r c e } { c h a n n e l ! a l p h a b e t } { a l p h a b e t ! c h a n n e l }

{

  e n c o d i n g } { u n i q u e l y d e c i p h e r a b l e } γ(w) = γ(w ′ ) =⇒ w = w ′ for each pair of words w, w ′ . In this case, each γ(b) for b in B is a codeword , and { c o d e w o r d } the set of all codewords is called a variable-length code or VLC for short. We will { v a r i a b l e -l e n g t h c o d e } { V L C } call this a code for short instead of the commonly used term uniquely decipherable { c o d e } code (or UD-code).

{

  e n c o d i n g ! o r d e r e d } { e n c o d i n g ! a l p h a b e t i c } A set C of nonempty words over an alphabet A is a prefix code (suffix code) if { p r e f i x c o d e } { c o d e ! p r e f i x } { s u f f i x c o d e } { c o d e ! s u f f i x } no element of C is a proper prefix (suffix) of another one. An encoding γ of B is called a prefix encoding if the set γ(B) is a prefix code.Prefix codes are especially interesting because they are instantaneously decipherable in a left to right parsing.

  3.: The tree of the binary ordered encoding of the five most frequent English words.

Fig. 1 .

 1 Fig. 1.4.: The Elias code.

  one has b n ≤ k n . Thus the radius of convergence of f C * (z) is at least equal to 1/k. Since f C (r) is increasing for real positive r, the radius of convergence of f C * (z) is precisely the positive real number r such that f C (r) = 1. Thus f C (1/k) ≤ 1. This proves the Kraft-McMillan inequality.

{

  c h a n n e l ! c a p a c i t y } { c a p a c i t y o f a c h a n n e l } a∈A z cost(a) = 1 .

  c∈C ρ cost(c) ≤ 1 .

Optimal encoding.

  Consider an encoding γ which associates to each symbol b in B a word γ(b) over the alphabet A. The weighted cost is { w e i g h t e d c o s t } W (γ) = b∈B weight(b) cost(γ(b)) .

{

  o p t i m a l ! e n c o d i n g p r o b l e m } with associated weight and cost functions, an encoding γ such that W (γ) is minimal. The optimal prefix encoding problem is the problem of finding an optimal prefix { o p t i m a l ! p r e f i x e n c o d i n g p r o b l e m }

Example 1 . 5 .

 15 The code C = {00, 10, 100} seen in Example 1.4 is neither prefix nor suffix. It is commutatively equivalent to the prefix code D = {00, 01, 100} and to the suffix code D ′ = {00, 10, 001}.

Fig. 1 .

 1 Fig. 1.5.: Various hypotheses. Front plane (1, 2, 3, 4): unequal weights. Right plane (3, 4, 7, 8): unequal letter costs. Top plane (2, 3, 6, 7): alphabetic encodings. The two unnamed vertices 5, 6 are easy special cases.

Example 1 . 6 .

 16 binary case is the following. Select two symbols b 1 , b 2 in B with lowest weights, replace them by a fresh symbol b with weight weight(b) = weight(b 1 ) + weight(b 2 ), and associate to b a node with children labeled b 1 and b 2 . Then iterate the process. The result is a binary tree corresponding to an optimal prefix code. The complexity of the algorithm is O(n log n), or O(n) if the weights are available in increasing order. The case where all weights are equal (vertex 5 in Figure 1.5) is an easy special case. M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel Consider the alphabets B = {a, b, c, d, e, f } and A = {0, 1}, and the weights given in the table

5 fFig. 1 .

 51 Fig. 1.6.: Computing an optimal Huffman encoding by combining trees.

Example 1 . 8 .

 18 Consider the alphabet B = {a, b, c}, with weight(a) = weight(c) = 1 and weight(b) = 4.

Figure 1 .Fig. 1 .

 11 Fig. 1.7.: Two trees for the given weights. Tree (a) has weighted cost 8, it is optimal but not ordered. Tree (b) is ordered and has weighted cost 11.

Example 1 . 9 .

 19 of the algorithm is to use a variant of Huffman's algorithm by grouping together pairs of elements with minimal weight which are consecutive in the ordering. The algorithm can be implemented to run in time O(n log n). Consider the following weights for an alphabet of five letters. a b c d e weight 25 20 12 10 14

20 MFig. 1 .

 201 Fig. 1.8.: The two steps of the algorithm: (a) the unordered tree obtained in the combination phase, and (b) the final ordered tree, obtained by recombination. Both have weighted cost 184.

14 e

 14 Fig. 1.9.: The initial sequence of trees.

10 d

 10 Fig. 1.10.: The next two steps.

Fig. 1 .

 1 Fig. 1.11.: The two last steps of the combination part.

Example 1 . 12 . 1

 1121 Consider a five symbol source alphabet and a three letter channel alphabet {a, b, c} with weights and costs i

4 c

 4 Fig. 1.12.: Trees built with Itai's algorithm.

Fig. 1 .

 1 Fig. 1.13.: Varn's algorithm for 7 words over a 3-letter alphabet. At each step, a leaf of minimal cost is replaced by a node with all possible leaves. There are two choices for the last step. Both give a minimal tree. Deduce that

{

  a u t o c o r r e l a t i o n p o l y n o m i a l } Exercise 1.6.4. Show that, for s = 101, one has

Fig. 1 .

 1 Fig. 1.14.: The sets R 1 to R 7 .

Fig. 1 .

 1 Fig. 1.15.: The Golomb codes of orders 1, 2, 3.

30 MFig. 1 .

 301 Fig. 1.16.: The Golomb-Rice codes of orders 0, 1, 2. length k.It follows from (1.15) that the generating series of the lengths of words of the Golomb-Rice code of order k is

{

  w e i g h t e d g e n e r a t i n g s e r i e s } { g e n e r a t i n g s e r i e s ! w e i g h t e d } p C (z) = x∈C π(x)z |x| .

Codes and Automata 31 Exponential

 31 Golomb codes. The exponential Golomb codes, denoted EG k for k ≥ 0, { e x p o n e n t i a l G o l o m b c o d e } form a family of codes whose length distributions make them better suited than the Golomb-Rice codes for encoding the integers endowed with certain probability distributions. They are introduced in [64]. The case k = 0 is the Elias code already { E l i a s c o d e }

Fig. 1 .

 1 Fig. 1.17.: The exponential Golomb codes of orders 0, 1, 2.

  M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

{ r e c o g n i z e d s e t }Fig. 1 .

 1 Fig. 1.18.: A simple encoder. The only state is both initial and terminal.

{Example 1 . 14 .

 114 l i t e r a l t r a n s d u c e r } { t r a n s d u c e r ! l i t e r a l } example, an encoding γ, as defined at the beginning of the chapter, can be realized by a one-state literal transducer, with the set of labels of edges being simply the pairs (b, γ(b)) for b in B. Consider the encoding defined by γ(a) = 00, γ(b) = 1, and γ(c) = 01. The corresponding encoding transducer is given in Figure 1.18

Fig. 1 .

 1 Fig. 1.19.: A deterministic decoder. A dash represents the empty word. An incoming (outgoing) arrow indicates the initial (terminal) state.

{

  i n p u t a u t o m a t o n } edges in the resulting automaton. A literal transducer is called deterministic (resp. { d e t e r m i n i s t i c ! t r a n s d u c e r } { t r a n s d u c e r ! d e t e r m i n i s t i c } unambiguous) if its associated input automaton is deterministic (resp. unambigu-{ u n a m b i g u o u s ! t r a n s d u c e r } { t r a n s d u c e r ! u n a m b i g u o u s } ous). Clearly, the relation realized by a deterministic transducer is a function.

Example 1 . 15 .

 115 The decoder corresponding to the prefix code of Example 1.14 is represented in Figure 1.19. Example 1.16. Consider the code C = {00, 10, 100} of Example 1.4. The decoder given by the construction is represented in Figure 1.20.

Fig. 1 .{ S c h üt z e n b e r g e r c o v e r i n g } Example 1 . 17 .Fig. 1 .

 11171 Fig.1.20.: An unambiguous decoder for a code which is not prefix.

Fig. 1 .

 1 Fig. 1.22.: A sequential transducer realizing a cyclic shift on words starting with the letter a, with σ(0) = ε and σ(1) = a.

Example 1 . 19 .Fig. 1 .

 1191 Fig. 1.23.: Another transducer realizing a cyclic shift on words starting with the letter a.

Exercise 1 . 8 . 1 .Exercise 1 . 8 . 2 .

 181182 A set of words C is said to be weakly prefix if there is an integer { w e a k l y p r e f i x c o d e } { c o d e ! w e a k l y p r e f i x } d ≥ 0 such that the following condition holds for any elements c, c ′ of C and any words w, w ′ of C * . If the prefix of length |c| + d of cw is a prefix of c ′ w ′ , then c = c ′ . The least integer d such that this property holds is called the deciphering delay and { d e c i p h e r i n g d e l a y } a weakly prefix code is also said to have finite deciphering delay. { c o d e ! w i t h f i n i t e d e c i p h e r i n g d e l a y } Show that a weakly prefix set is uniquely decipherable. Which of the following sets C and C ′ is a weakly prefix code? C = {00, 10, 100} and C ′ = {0, 001}.

Example 1 . 21 .

 121 The encoder in Figure 1.26 is deterministic. The source alphabet is {0, 1} and the channel alphabet is {a, b, c}. The sequence 0011 is encoded by acbb M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

{ s l i d i n g b l o c k d e c

  o d e r } { d e c o d e r ! s l i d i n g b l o c k }of fixed size. The decoder uses m symbols before the current one and a symbols after it (m is for memory and a for anticipation). According to the value of the symbols between time n -m and time n + a, the value of the n-th source symbol is determined. Figure1.24 depicts a schematic view of a sliding block decoder. It is not hard to show that sliding-block decodability implies the weaker finite lookahead property mentioned above. Note that a sliding block decoder avoids possible problems with error propagation because any channel error can affect the decoding only while it is in the decoder window and thus can corrupt at most m + a + 1 source symbols.Transducers realizing sliding block decoders are of a special kind. An automaton is called local if the knowledge of a finite number of symbols in the past and in the { a u t o m a t o n ! l o c a l } { l o c a l a u t o m a t o n } future determines the current state. More precisely, for given integers m, a ≥ 0 (m stands for memory and a for anticipation), an automaton is said to be (m, a)-local if for words u and v of length m and a respectively, p u → q v

{

  l o c a l t r a n s d u c e r } { t r a n s d u c e r ! l o c a l }

Fig. 1 .

 1 Fig. 1.24.: A sliding block decoder.

Fig. 1 .

 1 Fig. 1.25.: The [1, 3]-constraint.

Fig. 1 .Fig. 1 .Fig. 1 .

 111 Fig. 1.26.: The MFM code.

3 baFig. 1 .Fig. 1 .

 311 Fig. 1.29.: The poles.

Fig. 1 .

 1 Fig. 1.31.: The Franaszek encoder.

Fig. 1 .Fig. 1 .

 11 Fig. 1.32.: The construction of the Franaszek encoder.

1 Fig. 1 .

 11 Fig. 1.34.: The associated sliding block decoder.

Fig. 1 .

 1 Fig. 1.35.: A 2-state encoder reflecting the legal concatenations.

Fig. 1 .

 1 Fig. 1.36.: Literal decoder for phonetization.

Fig. 1 .

 1 Fig. 1.37.: A sequential transducer for the phonetization.

48 M

 48 .-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

Figure 1 . 38 .Fig. 1 .

 1381 Fig. 1.38.: An encoder and a local decoder.

Fig. 1 .

 1 Fig. 1.39.: A sequential decoder.

Fig. 1 .

 1 Fig. 1.40.: An encoder and an unambiguous decoder.

{

  R V L C c o d e s } { r e v e r s i b l e v a r i a b l e -l e n g t h c o d e s }

Codes and Automata 51 Fig. 1 .

 511 Fig. 1.42.: The reversible Golomb-Rice codes of orders 0, 1, 2.

Fig. 1 .

 1 Fig. 1.43.: The reversible exponential Golomb codes of orders 0 and 1.

Fig. 1 .

 1 Fig. 1.44.: A maximal bifix code of degree 3.

{ p r e f i x c o d

  e ! s y n c h r o n i z e d } { s y n c h r o n i z e d ! p r e f i x c o d e }

{

  a u t o m a t o n ! s y n c h r o n i z e d } { s y n c h r o n i z e d ! a u t o m a t o n }

Fig. 1 .Fig. 1 .

 11 Fig. 1.46.: Two different labelings: a non-synchronized and a synchronized automaton.

{ u n b o r d e r e d w o r d } {

 } w o r d ! u n b o r d e r e d } as 11 . . .

Answer.Fig. 1 .Question 1 . 3 .Fig. 1 .Fig. 1 . 2 . 1 . 5 .Question 1 . 6 .Question 1 . 7 .

 113112151617 Fig. 1.48.: The result of Huffman's algorithm.

Fig. 1 .

 1 Fig. 1.51.: An unambiguous decoder.

1 2 10 1 0 2 0 1 0 2 0 1 1 2 11 1 0 2 0 1 0 2 0 1

 111 The method described in Section 1.8 gives the unambiguous transducer of Figure 1.50. Question 1.8. Design a sequential transducer decoding the weakly prefix code C = {0, 001}.

Fig. 1 .Question 1 . 9 .Fig. 1 .Fig. 1 .Question 1 . 10 .

 11911110 Fig. 1.52.: A sequential transducer.

  1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thoughts for practitioners . . . . . . . . . . . . . . . . . . . . . 5 1.4 Definitions and notation . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Basic properties of codes . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Optimal prefix codes . . . . . . . . . . . . . . . . . . . . . . . . 16 1.7 Prefix codes for integers . . . . . . . . . . . . . . . . . . . . . . 26 1.8 Encoders and decoders . . . . . . . . . . . . . . . . . . . . . . . 32 1.9 Codes for constrained channels . . . . . . . . . . . . . . . . . . 37 1.10 Codes for constrained sources . . . . . . . . . . . . . . . . . . . 45 1.11 Bifix codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 1.12 Synchronizing words . . . . . . . . . . . . . . . . . . . . . . . . 55 1.13 Directions for future research . . . . . . . . . . . . . . . . . . . 58 1.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 1.15 Solutions to exercises . . . . . . . . . . . . . . . . . . . . . . . 60 1.16 Questions & answers . . . . . . . . . . . . . . . . . . . . . . . . 63 1.17 Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4

  M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

6

  M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

  .1. A source sequence can be uniquely parsed Codes and Automata 7into a sequence of the source words shown, possibly followed by a prefix of a word.Each source words is then encoded into a corresponding channel word according to the table. Although the encoding and decoding operations are extremely simple conceptually, and the decoder resynchronizes with only a moderate delay following an erroneous channel bit, this code is not suitable for use in a disk drive because it does not have fixed encoding and decoding rate.

	Source Channel
	1	001
	01	0001
	001	00001
	0001 000001
	00001 0000001
	00000 00000001
	Fig. 1.1.: Variable-length

Table 1 .

 1 1.: A binary ordered encoding of the five most frequent English words. An ordered prefix encoding γ of these words over the binary alphabet {0, 1} is given in Table1.1.

	b	γ(b)
	A	000
	AND	001
	OF	01
	THE	10
	TO	11

Example 1.1. The set B is composed of five elements in bijection with the five most common words in English, which are A, AND, OF, THE and TO.

  For any code C over an alphabet A with k letters, one has the inequality, called the Kraft-McMillan inequality (see for instance

	12	M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel
	Kraft-McMillan inequality.

  implies that there exists a word c n of length ℓ n over the alphabet A which does not have a prefix in C. The set {c 1 , . . . , c n } is then a prefix code. This proves the property.

		w e i g h t s }
	Entropy. Consider a source alphabet B. We associate to each symbol b ∈ B a weight which we denote by weight(b). For now, we assume that B is finite. The symbol weights are often normalized to sum to 1, in which case they can be interpreted as probabilities. The entropy of the source B = {b 1 , . . . , b n } with probabilities p i = weight(b i ) is the number	{ n o r m a l i z e d { e n t r o p y }

Table 1 .

 1 2.: The cardinalities of the codes C n,s

	11 10 111 110 101 1111 1110 1010 1001
	3 1 2 0 1 1
	4 1 3 1 2 1	0	1	0	1
	5 2 4 1 4 2	1	2	2	2
	6 3 5 2 7 4	1	4	3	3
	7 5 6 4 12 7	2	8	4	6
	8 8 7 7 20 12	4 15	9 11
	9 13 8 13 33 21	8 28 18 21
	10 21 9 24 54 37 15 52 32 39
	11 34 10 44 88 65 29 96 60 73
	12 55 11 81 143 114 56 177 115 136

  aca 42 M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

Table 1 .

 1 3.: The states of the Franaszek encoder.

	state	1	2	3	4	5	6
		ba, 1 ac, 4 ab, 6 ac, 4 cb, 6 ca, 1
	content		aa, 2 ac, 3 ab, 6 ac, 3
					aa, 5
	output ba					ca

Table 1 .

 1 4.: The states of the transducer for the phonetization.

	state	0	1	2	3	4	5	6	7	8
	content ε, 0

  50M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel development of codes for video recording has renewed the interest in bifix codes [27; 69; 70].

  52M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel Proposition 1.1. For any sequence (u n ) n≥1 of non-negative integers such that

	n≥1	u n k -n ≤	1 2	(1.17)	{ D o u b l e K r a f t }

  54M.-P. Béal, J.Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel for any sequence (u n ) 1≤n≤N with N ≤ 4 such that u(1/2) ≤ 3/4, there exists a binary bifix code C such that u(z) = n≥1 u n z n is the generating series of lengths of C. For a maximal bifix code C which is a regular set, the generating series of the lengths of the words of C satisfies f C (1/k) = 1, where k is the size of the alphabet. The average length of

  56M.-P.Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel Example 1.24. Consider the prefix code C = {01, 10, 110, 111}. The word 110 is not synchronizing. Indeed, it appears in a nontrivial way in the parsing of 111|01.

  60 M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

  10 (a word is called unbordered if no nonempty prefix is also a suffix). This 62 M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

  Compute the entropy of the source consisting of the five most frequent words in English with the normalized weights given in Table1.8. Compare the result with the average length of the prefix code of Example 1.1. Table 1.8.: Normalized weights of the five most frequent English words. Answer. One obtains H = 2.197. The average length is λ = 2.29. Thus the average length is slightly larger than the entropy. Question 1.2. What is the result of the Huffman algorithm applied to the five most frequent words in English with the frequencies given in Question 1.1? What is the average length?

		Codes and Automata	63
	1.16. Questions & answers
	Question 1.1. A	AND	OF	THE	TO
	0.116	0.174	0.223	0.356	0.131

Table 1 .

 1 9.

	name		output
	1	(ǫ, e)	ǫ
	2	(a, e), (ǫ, 0)	a
	3	(aa, e), (ǫ, 00)	aa

  68M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

M.-P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer and P. H. Siegel

Codes and Automata 53

Table 1.5.: Maximal 2-realizable length distributions of length N = 2, 3 and 4. The bound 1/2 in the statement of Proposition 1.1 is not the best possible. It is conjectured in [START_REF] Ahlswede | Some properties of fix-free codes[END_REF] that the statement holds with 3/4 instead of 1/2. Some { c o n j e c t u r e ! A h l s w e d e } attempts to prove the conjecture have led to improvements over Proposition 1.1. For example, it is proved in [START_REF] Yekhanin | Improved upper bound for the redundancy of fix-free codes[END_REF] that 1/2 can be replaced by 5/8. Another approach to the conjecture is presented in [START_REF] Deppe | On q-ary fix-free codes and directed deBrujin graphs[END_REF].

For convenience, we call a sequence (u n ) of integers k-realizable if there is a bifix code on k symbols with this length distribution.

We fix N ≥ 1 and we order sequences (u n ) 1≤n≤N of integers by setting

We give in Table 1.5 the values of the maximal 2-realizable sequences for N ≤ 4, with respect to this order. Set u(z) = n≥1 u n z n . For each value of N , we list in decreasing lexicographic order the maximal realizable sequence with the corresponding value of the sum u(1/2) = u n 2 -n . The distributions with value 1 correspond to maximal bifix codes. For example, the distribution (0, 1, 4, 4) highlighted in Table 1.5 corresponds to the maximal bifix code of Figure 1.44.

It can be checked in this table that the minimal value of the sums u(1/2) is 3/4. Since the distributions listed are maximal for componentwise order, this shows that

The road coloring theorem. There are prefix codes which are not synchronized. For example, if the lengths of the codewords of a nonempty prefix code are all multiples of some integer p ≥ 2, then the code is not synchronized. The same observation holds for a strongly connected automaton. If the period of the underlying graph (i.e. the greatest common divisor of the lengths of its cycles) is not 1, then the automaton is not synchronized. The road coloring theorem asserts the following. Let G be a strongly connected graph with period 1 such that each vertex has two outgoing edges. Then there exists a binary labeling of the edges of G which turns it into a synchronized deterministic automaton.

The road coloring theorem was proposed as a conjecture by Adler, Goodwin and Weiss [START_REF] Adler | Equivalence of topological Markov shifts[END_REF]. It was proved by Trahtman [START_REF] Trahtman | The road coloring problem[END_REF].

The name of this theorem comes from the following interpretation of a synchronizing word: if one assigns a color to each letter of the alphabet, the labeling of the edges of an automaton can be viewed as a coloring of the edges of the underlying graph. One may further identify the vertices of the graph with cities and the edges with roads connecting these cities. A synchronizing word then corresponds to a sequence of colors which leads to a fixed city regardless of the starting point.

Example 1.27. Consider the automata represented on Figure 1.46. These automata have the same underlying graph and differ only by the labeling. The automaton on the left is not synchronized. Indeed, the action of the letters on the subsets {1, 3} and {2, 4} exchanges these sets as shown on Figure 1.47.

On the other hand, the automaton on the right is synchronized. Indeed, 101 is a synchronizing word.

Codes and Automata 61

conjecture was solved positively by Guibas and Odlyzko [START_REF] Guibas | Maximal prefix-synchronized codes[END_REF] who also showed that the generalization to alphabets with k symbols is true for k ≤ 4 but false for k ≥ 5.

Solution to 1.6.6. Consider the cost on B defined by cost(b) = -log π(b). Then cost(c) = -log π(c) for each codeword and thus a code with minimal cost (with equal weights) will have maximal average length with respect to π.

Solution to 1.7.1. One has, using the fact that n≥0 np n q = p/q, H = -n≥0 p n q log p n q = -n≥0 p n q log p n -n≥0 p n q log q = -n≥0 np n q log p -log q = -p/q log p -log q whence the result. If

Taking the logarithm of both sides gives log 1 q ≥ k. On the other hand, since log x ≥ x -1 for 1 ≤ x ≤ 2, we have p/q log(1/p) ≥ 1. Combining these inequalities, we obtain

Solution to 1.7.2. We use an induction on m. The property clearly holds for m = 3. Let m ≥ 4 and set w 0 = w m-1 + w m . The sequence w 0 ≥ w 1 ≥ . . . ≥ w m-2 is quasi-uniform since w m-3 + w m-2 ≥ w m-1 + w m . By the induction hypothesis, an optimal binary tree for the sequence w 0 ≥ w 1 ≥ . . . ≥ w m-2 has leaves of heights k and possibly k + 1 for some k ≥ 1. The leaf corresponding to w 0 has to be at height k since it has maximal weight. We replace it by two leaves of level k + 1 with weights w m-1 and w m . The result is clearly an optimal binary tree with leaves at height k and k + 1. This argument appears in [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF].

We may suppose that the length of the word c 2 • • • c n is larger than d, padding both sides on the right by an appropriate number of words c from C. Then, the condition implies that c 1 = c 2 , and so on.

Solution to 1.8.2. The set C is the code of Example 1.4. It is not weakly prefix since for any n, (10)(00) n is a prefix of (100)(00) n .

The code C ′ is weakly prefix. Indeed, the decoding of a word beginning with 001 • • • has to start with 001.

Solution to 1.8.3. Suppose first that C has a sequential decoder. Let d be the maximal length of the values of the output function. Then C is weakly prefix with delay dL, where L is the maximal length of the codewords.