Code comma-free

Modèle:Titre mis en forme 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 du produit de deux mots du code.

Les codes comma-free sont aussi connus sous le terme de « self-synchronizing block codes »Modèle:, 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. De fait, il n'en est rien.

Définitions

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

$c_1{c}_2\cdots c_n=d_1{d}_2\cdots d_m$

pour $n,m\ge 1$ et $c_i,d_j\in C$, alors

$n=m$ et $c_i=d_i$ pour tout $i$.

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

$f(b_1\cdots b_n)f(b_1)\cdots f(b_n$).

L'application $f$ est un « morphisme de codage », l'application inverse $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 $pcs=c_1{c}_2$ pour des mots du code $c,c_1,c_2$, alors $p$ ou $s$ est le mot vide. Golomb et. al. donnent la formulation explicite suivante : si $a_1{a}_2\cdots a_n$ et $b_1{b}_2\cdots b_n$ sont éléments du code $C$, alors aucun des mots $a_2\cdots a_n{b}_1$, $a_3\cdots a_n{b}_1{b}_2$, ..., $a_n{b}_1{b}_2\cdots b_{n-1}$ n'est dans $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 $n$ est donc majorée par le nombre de mots primitifs de longueur $n$, qui est aussi le nombre de colliers apériodiques de longueur $n$ ; ce nombre est égal à

$M_k(n)=\frac{1}{n}\sum _{d\mid n}\mu (d)k^{n/d}$

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

$W_k(n)=M_k(n)=\frac{1}{n}\sum _{d\mid n}\mu (d)k^{n/d}$ si $n$ est impair.

Willard L. Eastman donne de plus un algorithme pour construire ces codes. Un autre algorithme est donné par Robert A. Scholtz. Pour $k=4$ lettres et des mots de longueur $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. Il existe des liens entre codes comma-free et les ensembles Hall et les ensembles de Lazard. 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.

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre
• Modèle:Article

Articles connexes

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

Lien externe

• Modèle:Lien vidéo