Skip to Main content Skip to Navigation
Book sections

Variable-length codes and finite automata

Abstract : 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.
Document type :
Book sections
Complete list of metadata

Cited literature [68 references]  Display  Hide  Download
Contributor : Jean Berstel Connect in order to contact the contributor
Submitted on : Monday, August 12, 2013 - 5:19:39 PM
Last modification on : Saturday, January 15, 2022 - 3:58:21 AM
Long-term archiving on: : Wednesday, November 13, 2013 - 2:25:10 AM


Files produced by the author(s)


  • HAL Id : hal-00620817, version 1


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⟩



Record views


Files downloads