Codes convolutionnels et algorithme de viterbi

Codeurs convolutionnels 

Les techniques de codage de contrôle d’erreur jouent un grand rôle dans les systèmes de communications numériques. Les codes convolutionnels ou convolutifs constituent une grande famille de codes correcteurs d’erreurs.

Le principe du codage convolutionnel consiste en l’association du bit d’entrée à transmettre à plusieurs bits précédemment transmis par une opération logique (généralement des OU exclusifs), de façon à retrouver sa valeur en cas d’incident de transmission. Ainsi, cette façon d’introduire de la redondance dans l’information à transmettre donne au code sa capacité à détecter et à corriger les erreurs.

Représentation en arbre

Une façon pratique de décrire la relation entre les séquences d’entrée et de sortie d’un codeur est la représentation en arbre. Chaque branche représente une des possibilités de W bits d’entrée. De chaque nœud de l’arbre émergent 2w branches. Chaque branche contient une étiquette représentant les S symboles codés de sortie correspondants aux W bits d’entrée du codeur . Un bit d’entrée ‘0’ correspond à la branche du haut et un bit d’entrée ‘l’ correspond à la branche du bas. Donc, une séquence donnée de bits d’information passe par un chemin unique dans l’arbre. Les symboles, ou mots de code, lus au long de ce chemin forment la séquence correspondante de sortie du codeur. Si on prend pour conditions l’état de départ ’00’ et la séquence d’entrée 1101 alors, la séquence de sortie sera 11 10 10 00 .

Représentation en diagramme d’état 

Le codeur est une machine linéaire à états finis qui peut être facilement décrite par son diagramme d’état.  Les nœuds ou les états représentent le contenu du registre à décalage. Les branches, qui forment les transitions entre les états, indiquent la valeur du bit d’entrée. Si la branche est une ligne continue, elle indique que le bit d’entrée est un ‘0’. Si elle est une ligne pointillée, elle indique que le bit d’entrée est un ‘1 ‘. Le mot de deux bits qui étiquette la branche de transition représente les deux symboles codés correspondants de sortie du codeur.

Représentation en diagramme de treillis 

La réplication infinie du diagramme d’état résulte en une structure appelée le treillis. C’est une version indexée par le temps du diagramme d’état. Chaque nœud correspond à un des 2m états, à un temps donné. Chaque branche parmi les 2 w branches par état correspond à une transition entre deux états. Elle est associée aux W bits d’entrée et S symboles correspondants de sortie du codeur. N’importe quelle séquence de mots de code correspond à un chemin unique constitué de branches successives dans le diagramme de treillis.

Performances des codes convolutionnels 

Les performances d’un code se mesurent principalement par la probabilité d’erreur. Cette dernière dépend de la distance libre, dfree· C’est la distance de Hamming minimale entre toutes les paires de mots de code. La distance de Hamming entre deux mots de code est définie comme le nombre de positions dans les quels ils diffèrent. Dans cette section, nous faisons un survol des formules de calcul de la probabilité d’erreur par bit pour un système utilisant un canal binaire symétrique avec et sans codage. Le lecteur désirant savoir plus sur le calcul de ces formules est prié de se référer aux ouvrages suivants : [2], [ 4-6].

Le canal binaire symétrique, BSC (« Binary Symmetric Channel »), est un canal dont l’entrée est binaire et dont la sortie est aussi binaire ou quantifiée sur deux niveaux. On l’appelle aussi un canal à décision dure. La probabilité de transition dans un tel canal est p.  Ce modèle de canal est souvent utilisé pour mieux illustrer les performances d’erreur.

Quantification du signal reçu 

Théoriquement, un décodeur de Viterbi idéal travaille avec une précision infinie. Dans les systèmes pratiques, on quantifie les symboles reçus sur un bit de précision ou plus pour réduire la complexité du décodeur, sans parler des circuits qui le devancent. Si les symboles reçus sont quantifiés sur un bit (deux niveaux, exemple < OV = 1 et > OV = 0), le résultat est appelé décision dure. Si les symboles reçus sont quantifiés sur plus d’un bit, le résultat est appelé décision douce. La décision dure introduit une dégradation de 2.2 dB par rapport aux systèmes non quantifiés dans lesquels le décodeur opère directement avec le signal reçu [15]. La décision douce sur trois bits (huit niveaux) n’introduit qu’une légère perte de 0.2 dB par rapport à ces même systèmes non quantifiés [5]. Une quantification sur plus de huit niveaux n’apporte qu’une légère amélioration au prix d’une augmentation de complexité non justifiable [5].

Codes catastrophiques 

Un code est appelé catastrophique si dans une séquence de bits codés, un nombre fini de symboles en erreur engendre une séquence de bits décodés en erreur qui est arbitrairement longue. En générale, la condition nécessaire et suffisante pour qu’un code de taux R = W /S soit catastrophique est qu’au moins un chemin dans son diagramme d’état forme une boucle fermée avec un poids nul. Massey et Sain [2] ont trouvé une condition nécessaire pour tester si un code de taux 1/S est catastrophique. Il en résulte que les polynômes générateurs doivent avoir un facteur commun pour qu’une telle situation se produise.