Variable-length codes and finite automata

Marie-Pierre Béal (1) , Jean Berstel (1) , Brian H. Marcus (2) , Dominique Perrin (1) , Christophe Reutenauer (3) , Paul H. Siegel (4)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 UBC - University of British Columbia
3 LaCIM - Laboratoire de combinatoire et d'informatique mathématique [Montréal]
4 Department of Electrical and Computer Engineering

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 probability distributions. The chapter contains numerous examples and exercises with solutions.

Mots clés: Variable-length codes; finite automata; prefix codes; bifix codes

Domaines: Algorithme et structure de données [cs.DS]

Marie-Pierre Béal, Jean Berstel, Brian H. Marcus, Dominique Perrin, Christophe Reutenauer, et al.. Variable-length codes and finite automata. I. Woungang, S. Misra et S. Chandra Misra. Selected Topics in Information and Coding Theory, World Scientific, pp.505-584, 2010, Series on Coding Theory and Cryptology, 978-981-283-716-5. ⟨hal-00620817⟩