Automates cellulaires et correction d’erreurs

Les expériences numériques interactives de cette page on été développées pour l’article Automates cellulaires et correction d’erreurs sur Images des Maths.

"Comment corriger des erreurs dans un réseau, en l’absence d’autorité centrale permettant de contrôler l’ensemble du fonctionnement ? Cet article présente des travaux de recherche récents motivés par cette question de nature informatique. Pour y répondre, l’outil et les méthodes mathématiques s’avèrent essentiels, à la fois dans les étapes de modélisation et de résolution. L’informatique mathématique, est ainsi un domaine de l’informatique qui utilise non seulement des mathématiques, mais se révèle aussi créateur de nouvelles mathématiques."

Lire l’article complet sur "Image des Maths"

Automate cellulaire 1D

• Mode compteur : une cellule est coloriée en bleu au temps t+1 si au temps t , parmi les deux cellules voisines immédiates, à sa gauche et à sa droite, il y a exactement une cellule bleue. Dans la figure par défaut, la configuration initiale est constituée d’un ruban blanc avec une seule cellule bleue.

• Mode GKL : modèle le plus simple possèdant la propriété d’érosion.
  • Si une cellule (repérée par l’indice n sur le ruban) est blanche, elle prend comme nouvelle couleur celle qui est majoritaire parmi sa propre couleur, celle de sa voisine de gauche (cellule d’indice n−1), et celle de la cellule située trois places plus à gauche (cellule d’indice n−3).
  • Au contraire, si une cellule (d’indice n) est bleue, elle prend comme nouvelle couleur celle qui est majoritaire parmi sa propre couleur, celle de sa voisine de droite (cellule d’indice n+1), et celle de la cellule située trois places plus à droite (cellule d’indice n+3).
    Il est instructif de regarder opérer l’automate cellulaire GKL partant d’une configuration avec un intervalle fini de cellules bleues sur un ruban blanc, comme représenté ci-dessous.

Automate cellulaire 2D
On dit qu’un automate cellulaire a la propriété d’érosion si, à partir de n’importe quelle configuration ne contenant qu’un nombre fini de cellules bleues, son évolution est telle qu’au bout d’un certain temps, il n’y a plus aucune cellule bleue, et si, à partir de n’importe quelle configuration ne contenant qu’un nombre fini de cellules blanches, l’évolution est telle qu’au bout d’un certain temps, il n’y a plus aucune cellule blanche.
On peut voir la propriété d’érosion comme la capacité à effacer des « anomalies » qui apparaîtraient en nombre fini sur une configuration toute blanche ou toute bleue.

L’automate cellulaire de la majorité sur le voisinage de Toom ci-dessous possède la propriété d’érosion.