Theory of codes.

*(English)*Zbl 0587.68066
Pure and Applied Mathematics, 117. Orlando etc.: Academic Press, Inc. XIV, 433 P. $ 60.00; £60.00 (1985).

This book is the first treatise on variable-length codes; it provides a systematic exposition of the topic, showing its connection with theoretical computer science (automata, semigroups, formal languages), probability, noncommutative algebra, permutation groups, combinatorics. The subject is part of what is called effective mathematics and presents many algorithms and constructions of families of codes - although the construction of all finite maximal codes is still an open problem.

The authors have chosen to develop the theory in the most general way, in order to point out the main arguments. Indeed, they treat the case of thin codes, which generalize finite and even recognizable codes. Chapter 0 is an introductory chapter on monoids, words, automata, formal series and permutation groups. Chapter 1 is the real beginning: codes, a test for codes, complete and maximal codes. Chapter 2 gives a systematic study of prefix codes; this chapter is very intuitive, particularly because of the use of trees; however, it ends with a deep result on deciphering delay. Chapter 3 presents the beautiful combinatorial theory of biprefix codes, and the various characterizations of the degree. Chapter 4 is rather technical, but necessary for the syntactic approach which is used in the next chapter; it presents a special class of automata, the unambiguous automata; the first application is the theorem of synchronization of semaphore codes. In chapter 5 the permutation groups associated with biprefix codes are studied; the main result states that if the code is moreover finite and indecomposable, then this group is doubly transitive. Chapter 6 gives the probabilistic approach of codes; the formula relating degree and density is proved. Chapter 7 deals with problems about conjugacy; it gives results on circular codes and various results on constructions of optimal circular codes and factorization of free monoids. Chapter 8 presents the commutative factorization theorem; see the last chapter of the forthcoming book of J. Berstel and the reviewer (Rational series and their languages, Springer Verlag) for the extension of this theorem to the noncommutative case; the last result links biprefix codes and semisimple algebras.

The whole book is written at an elementary level and may be used for courses at various levels in computer science, algebra or probability theory. Each chapter ends with an exercise section and bibliographical and historical notes.

The authors have chosen to develop the theory in the most general way, in order to point out the main arguments. Indeed, they treat the case of thin codes, which generalize finite and even recognizable codes. Chapter 0 is an introductory chapter on monoids, words, automata, formal series and permutation groups. Chapter 1 is the real beginning: codes, a test for codes, complete and maximal codes. Chapter 2 gives a systematic study of prefix codes; this chapter is very intuitive, particularly because of the use of trees; however, it ends with a deep result on deciphering delay. Chapter 3 presents the beautiful combinatorial theory of biprefix codes, and the various characterizations of the degree. Chapter 4 is rather technical, but necessary for the syntactic approach which is used in the next chapter; it presents a special class of automata, the unambiguous automata; the first application is the theorem of synchronization of semaphore codes. In chapter 5 the permutation groups associated with biprefix codes are studied; the main result states that if the code is moreover finite and indecomposable, then this group is doubly transitive. Chapter 6 gives the probabilistic approach of codes; the formula relating degree and density is proved. Chapter 7 deals with problems about conjugacy; it gives results on circular codes and various results on constructions of optimal circular codes and factorization of free monoids. Chapter 8 presents the commutative factorization theorem; see the last chapter of the forthcoming book of J. Berstel and the reviewer (Rational series and their languages, Springer Verlag) for the extension of this theorem to the noncommutative case; the last result links biprefix codes and semisimple algebras.

The whole book is written at an elementary level and may be used for courses at various levels in computer science, algebra or probability theory. Each chapter ends with an exercise section and bibliographical and historical notes.

Reviewer: C.Reutenauer

##### MSC:

68Q45 | Formal languages and automata |

68Q70 | Algebraic theory of languages and automata |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

94-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory |

94A45 | Prefix, length-variable, comma-free codes |

20M35 | Semigroups in automata theory, linguistics, etc. |

20M05 | Free semigroups, generators and relations, word problems |

20M12 | Ideal theory for semigroups |

20B20 | Multiply transitive finite groups |

60B99 | Probability theory on algebraic and topological structures |

16S10 | Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.) |