Code comma-free

En informatique théorique, et notamment en théorie des codes, et aussi en bio-informatique et notamment en génétique, un code comma-free (terme que l'on pourrait traduire par « code sans virgule ») est un code en bloc ou code uniforme dans lequel aucun mot du code n'est facteur interne[1] du produit de deux mots du code[2].

Les codes comma-free sont aussi connus sous le terme de « self-synchronizing block codes »[3],[4] parce qu'aucune synchronisation n'est nécessaire pour trouver le début d'un mot du code.

Motivation historique

Le code génétique est formé de codons. Chaque codon est une suite de trois nucléotides pris dans un « alphabet » de quatre lettres A, U, G, C (adénine, uracile, guanine, et cytosine). L'ensemble de 64 codons possibles forme un code uniforme. Chacun des codons possibles peut synthétiser l'un des 20 acides aminés naturels. Au début de la génétique, la question a été posée si l'ensemble des codons des 20 acides aminés était un code comma-free ; en effet le nombre maximum d'éléments d'un code comma-free de longueur 3 sur 4 lettres est exactement 20. S'il y avait bijection entre acides aminés et codons, le décodage pouvait se faire sans synchronisation[5]. De fait, il n'en est rien[6].

Définitions

Un code sur un alphabet est un ensemble de mots non vides sur tel que tout produit de mots de se factorise de manière unique comme produit : formellement, si

pour et , alors

et pour tout .

Un autre formulation de la propriété est que le sous-monoïde engendré par est librement engendré par , donc que est une base du sous-monoïde . Les mots composant un code sont appelés les « mots du code », un produit de mots du code est un « message ». Si est un alphabet en bijection avec , une fonction bijective s'étend naturellement en un morphisme de sur qui, à tout mot sur associe le message

).

L'application est un « morphisme de codage », l'application inverse est le « décodage ».

Un code uniforme ou code en bloc est un code dont tous les mots ont même longueur, appelée la longueur du code. Un code comma-free est un code uniforme tel qu'aucun mot du code n'est facteur interne du produit de deux mots du code : Si pour des mots du code , alors ou est le mot vide. Golomb et. al.[2] donnent la formulation explicite suivante : si et sont éléments du code , alors aucun des mots , , ..., n'est dans .

Taille d'un code comma-free

Tous les mots d'un code comma-free sont primitifs. La taille, c'est-à-dire le nombre d'éléments d'un code comma-free de longueur est donc majorée par le nombre de mots primitifs de longueur , qui est aussi le nombre de colliers apériodiques de longueur  ; ce nombre est égal à

pour un alphabet à k lettres. Ici, est la fonction de Möbius. Si on note la taille maximale d'un code comma-free de longueur sur un alphabet à lettres, on a donc . Golomb et al. ont démontré[2] qu'il y a égalité si la longueur des mots du code est impaire et inférieure à 15 ; le cas général a été prouvé par Willard L. Eastman[7]. On a donc:

si est impair.

Willard L. Eastman donne de plus un algorithme pour construire ces codes. Un autre algorithme est donné par Robert A. Scholtz[8]. Pour lettres et des mots de longueur , on trouve la valeur 20, en concordance avec la conjecture de Crick et. al.

Knuth parle du premier algorithme dans sa conférence de Noël. L'algorithme d'Eastman est développé par Knuth comme exemple de backtracking[4]. Il existe des liens entre codes comma-free et les ensembles Hall et les ensembles de Lazard[9]. Le résultat sur la maximalité est faux pour les mots de longueur paire, et aucune formule n'est conjecturée pour la cardinalité d'un code comma-free de longueur paire n sur k lettres[4].

Notes et références

  1. Un mot est facteur interne d'un mot si pour deux mots non vides et .
  2. Golomb et Gordon Welch.
  3. (en) Universal Commafree Codes, Donald Knuth () Stanford University.
  4. Knuth 2017, p. 9-10.
  5. Francis H. C. Crick, John Stanley Griffith et Leslie Orgel, « Codes without commas », Proceedings of the National Academy of Sciences of the U.S.A, vol. 43, , p. 416–421 (lire en ligne, consulté le ).
  6. The most beautiful wrong ideas in science sur Chemistry Blog
  7. Eastman 1965.
  8. Scholtz 1969.
  9. Perrin et Reutenauer 2018.

Bibliographie

  • Solomon W. Golomb, Basil Gordon et Lloyd R. Welch, « Comma-free codes », Canadian Journal of Mathematics, vol. 10, , p. 202–209 (ISSN 1496-4279, DOI 10.4153/CJM-1958-023-9, lire en ligne).
  • Willard L. Eastman, « On the construction of comma-free codes », IEEE Trans. Inform. Theory, vol. IT-11, , p. 263–267.
  • Robert A. Scholtz, « Maximal and variable length comma-free codes », IEEE Trans. Inform. Theory, vol. IT-15, , p. 300–306.
  • Donald E. Knuth, « Introduction to backtracking. », dans The Art of Computer Programming, vol. 4. pre-fascicule 5b, Addison-Wesley, (lire en ligne)
  • Dominique Perrin et Christophe Reutenauer, « Hall sets, Lazard sets and comma-free codes », Discrete Mathematics, vol. 341, no 1, , p. 232-243 (ISSN 0012-365X, DOI 10.1016/j.disc.2017.08.034, lire en ligne)

Articles connexes

Lien externe

  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.