Master MPRI

Cours 2-16 : Modélisation par automates

Nous présenterons une application des automates finis à un problème de codage qui fait également le lien avec la théorie des systèmes dynamiques symboliques. Les contraintes de la technologie du stockage ou de la transmission de l'information entrainent que les suites de bits qui peuvent etre inscrits sur un médium donné ou transmis sur un canal ne sont pas quelconques.

Une solution, dite "par codage à canal contraint", consiste à construire des transducteurs qui transforment des suites quelconques de bits en des suites satisfaisant les contraintes voulues et avec la propriété supplémentaire que le décodage peut se faire sans propagation d'erreurs.

• Systèmes dynamiques symboliques de type fini et sofiques. Entropie.

• Transducteurs et applications locales.

• Eclatement et fusion d'états.

• Modélisation des contraintes.

• Codage de Franaszek.

Bibliographie

M.-P. Béal, Codage symbolique, Masson, 1993.

M.-P. Béal et D. Perrin, Symbolic dynamics and finite automata. Handbook of Formal Languages, Vol. 2, pp. 463--503 (1997), Springer Verlag. Version corrigée 1999 téléchargeable ici.

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.

B. Marcus, R. Roth, P. Siegel, Introduction to Coding for Constrained Systems. Téléchargeable ici.