treillis

En théorie des communications et en traitement du signal, un treillis est une structure graphique qui représente l'évolution d'un système à états finis sur des pas de temps discrets. Chaque tranche verticale représente un instant, les nœuds représentant les états possibles du système. Les arêtes relient les états à des pas de temps consécutifs, montrant quelles transitions d'état sont autorisées par le schéma d'encodage ou de modulation. Cette structure devient essentielle lorsque vous devez trouver la séquence d'états la plus probable qui a produit un signal reçu corrompu par le bruit.

Le treillis doit sa puissance à l'algorithme de Viterbi, qui exploite la structure du graphe pour décoder efficacement les données reçues. Au lieu de vérifier chaque chemin possible à travers tous les pas de temps, l'algorithme de Viterbi ne conserve que le chemin le plus probable menant à chaque état à chaque instant, puis élague les branches impossibles. Pour un code convolutif avec une longueur de contrainte de 7 et des symboles binaires, le treillis a généralement 26 = 64 états par tranche de temps, ce qui rend la recherche réalisable même pour de longs messages.

Les diagrammes en treillis apparaissent partout où un encodage basé sur des contraintes est utilisé: codes convolutifs dans les communications par satellite et mobiles, turbocodes, codes LDPC et même dans l'égalisation des canaux dispersifs. La structure du treillis encode directement les polynômes générateurs ou les relations de contrôle de parité du code. Un encodeur convolutif de débit 1/2 avec deux prises de rétroaction produira une topologie de treillis différente d'un code de débit 1/3, et cette différence est visible dans le nombre d'arêtes par nœud et le motif des connexions.

Le nom «treillis» vient de sa ressemblance avec une treille de jardin ou une structure de support de vigne: des colonnes verticales (pas de temps) avec des connexions diagonales (transitions d'état). Cette métaphore visuelle est restée parce que le diagramme aide réellement les ingénieurs à voir comment les états prolifèrent et reconvergent au fil du temps. Dans les variantes de treillis à «tail-biting» et circulaires, le dernier pas de temps se connecte aux états initiaux, permettant des codes sans bits de remplissage inutiles.

Un treillis n'est pas propre à une modulation ou à un code unique; c'est un outil de représentation qui s'adapte aux contraintes du système. La même structure de treillis peut être parcourue par différents algorithmes: Viterbi pour le décodage à maximum de vraisemblance, l'algorithme avant-arrière pour le décodage à sortie douce, ou les méthodes de propagation de croyance pour les graphes factoriels. Comprendre la structure du treillis est essentiel pour les concepteurs de matériel qui implémentent des décodeurs, car le chemin critique et les exigences de mémoire dépendent directement de la topologie des branches et des états.