Trellis : Du treillis de jardin aux chemins de signaux

Pour la plupart des gens, un « trellis » (treillis) est une structure en bois ou en métal, généralement en forme de losange ou de carré, qui soutient les plantes grimpantes dans un jardin. Il est purement structurel et ornemental, une simple grille de bandes qui s'entrecroisent. Mais en génie électrique et en théorie de l'information, un « trellis » est quelque chose de beaucoup plus abstrait : un graphe orienté étalé dans le temps, où chaque instant forme une tranche verticale, et les nœuds représentent les états possibles d'un signal ou d'un code.

En termes pratiques, un diagramme en « trellis » montre comment un flux de données peut emprunter différents chemins à travers une séquence d'états. Chaque tranche verticale représente un instant discret. Les nœuds à chaque pas de temps se connectent aux nœuds du pas précédent et du pas suivant, formant des branches qui divergent et reconvergent. Les ingénieurs électriciens utilisent les diagrammes en « trellis » pour décoder les codes convolutionnels, une technique courante de correction d'erreurs dans les télécommunications et le stockage numérique. L'algorithme de Viterbi, qui trouve le chemin le plus probable à travers le « trellis », dépend entièrement de cette structure pour identifier la séquence transmise originale malgré le bruit et les interférences.

L'analogie visuelle avec un treillis de jardin est claire mais inversée dans sa signification. Un « trellis » physique est rigide et passif ; il existe simplement pour que les plantes y grimpent. Un « trellis » de signal est dynamique et algorithmique ; il représente activement des possibilités de ramification contraintes par les règles du code. Le motif en treillis apparaît dans les deux, mais dans la version jardin, il est purement géométrique, tandis que dans la version ingénierie, il encode la causalité et la probabilité.

Le terme a été emprunté de l'architecture classique et du jardinage aux mathématiques et au traitement du signal au milieu du 20e siècle, alors que les ingénieurs recherchaient des modèles visuels intuitifs pour les transitions d'état complexes. La métaphore a fonctionné parce que les deux structures partagent l'idée essentielle d'un chemin tracé à travers un réseau d'intersections. Une vigne suit un chemin sur un treillis ; un signal codé suit un chemin (parmi de nombreux chemins possibles) à travers l'espace d'états. Le mot est resté parce que le diagramme ressemble à une clôture en treillis lorsqu'il est dessiné sur papier, et parce qu'il capture le sens de la possibilité parallèle et du parcours sélectif.