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 ${\displaystyle A}$ est un ensemble ${\displaystyle C}$ de mots non vides sur ${\displaystyle A}$ tel que tout produit de mots de ${\displaystyle C}$ se factorise de manière unique comme produit : formellement, si

${\displaystyle c_{1}c_{2}\cdots c_{n}=d_{1}d_{2}\cdots d_{m}}$

pour ${\displaystyle n,m\geq 1}$ et ${\displaystyle c_{i},d_{j}\in C}$, alors

${\displaystyle n=m}$ et ${\displaystyle c_{i}=d_{i}}$ pour tout ${\displaystyle i}$.

Un autre formulation de la propriété est que le sous-monoïde ${\displaystyle C^{*}}$ engendré par ${\displaystyle C}$ est librement engendré par ${\displaystyle C}$, donc que ${\displaystyle C}$ est une base du sous-monoïde ${\displaystyle C^{*}}$. Les mots composant un code ${\displaystyle C}$ sont appelés les « mots du code », un produit de mots du code est un « message ». Si ${\displaystyle B}$ est un alphabet en bijection avec ${\displaystyle C}$, une fonction bijective ${\displaystyle f:B\to C}$ s'étend naturellement en un morphisme de ${\displaystyle B^{*}}$ sur ${\displaystyle C^{*}}$ qui, à tout mot ${\displaystyle w=b_{1}\cdots b_{n}}$ sur ${\displaystyle B}$ associe le message

${\displaystyle f(b_{1}\cdots b_{n})f(b_{1})\cdots f(b_{n}}$).

L'application ${\displaystyle f}$ est un « morphisme de codage », l'application inverse ${\displaystyle f^{-1}}$ 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 ${\displaystyle pcs=c_{1}c_{2}}$ pour des mots du code ${\displaystyle c,c_{1},c_{2}}$, alors ${\displaystyle p}$ ou ${\displaystyle s}$ est le mot vide. Golomb et. al.^[2] donnent la formulation explicite suivante : si ${\displaystyle a_{1}a_{2}\cdots a_{n}}$ et ${\displaystyle b_{1}b_{2}\cdots b_{n}}$ sont éléments du code ${\displaystyle C}$, alors aucun des mots ${\displaystyle a_{2}\cdots a_{n}b_{1}}$, ${\displaystyle a_{3}\cdots a_{n}b_{1}b_{2}}$, ..., ${\displaystyle a_{n}b_{1}b_{2}\cdots b_{n-1}}$ n'est dans ${\displaystyle C}$.

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 ${\displaystyle n}$ est donc majorée par le nombre de mots primitifs de longueur ${\displaystyle n}$, qui est aussi le nombre de colliers apériodiques de longueur ${\displaystyle n}$ ; ce nombre est égal à

${\displaystyle M_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}}$

pour un alphabet à k lettres. Ici, ${\displaystyle \mu }$ est la fonction de Möbius. Si on note ${\displaystyle W_{k}(n)}$ la taille maximale d'un code comma-free de longueur ${\displaystyle n}$ sur un alphabet à ${\displaystyle k}$ lettres, on a donc ${\displaystyle W_{k}(n)\leq M_{k}(n)}$. Golomb et al. ont démontré^[2] qu'il y a égalité si la longueur ${\displaystyle n}$ 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:

${\displaystyle W_{k}(n)=M_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}}$ si ${\displaystyle n}$ 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 ${\displaystyle k=4}$ lettres et des mots de longueur ${\displaystyle n=3}$, 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

Bibliographie

• Solomon W. Golomb, Basil Gordon et Lloyd R. Welch, « Comma-free codes », Canadian Journal of Mathematics, vol. 10,‎ 1958, 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,‎ 1965, p. 263–267.
• Robert A. Scholtz, « Maximal and variable length comma-free codes », IEEE Trans. Inform. Theory, vol. IT-15,‎ 1969, p. 300–306.
• Donald E. Knuth, « Introduction to backtracking. », dans The Art of Computer Programming, vol. 4. pre-fascicule 5b, Addison-Wesley, septembre 2017 (lire en ligne)
• Dominique Perrin et Christophe Reutenauer, « Hall sets, Lazard sets and comma-free codes », Discrete Mathematics, vol. 341, n^o 1,‎ 2018, p. 232-243 (ISSN 0012-365X, DOI 10.1016/j.disc.2017.08.034, lire en ligne)

Articles connexes

• Théorie des codes
• Code correcteur
• Méthode de décodage

Lien externe

• (en) Universal Commafree Codes, Donald Knuth (11 décembre 2015) Stanford University.

• Portail de l'informatique théorique