Décodeur Viterbi

Un décodeur Viterbi utilise l' algorithme de Viterbi pour décoder un flux binaire qui a été encodé à l'aide d'un code convolutif ou d'un code en treillis .

Il existe d'autres algorithmes pour décoder un flux codé par convolution (par exemple, l' algorithme de Fano ). L'algorithme de Viterbi est le plus gourmand en ressources, mais il effectue un décodage par maximum de vraisemblance . Il est le plus souvent utilisé pour décoder des codes convolutifs avec des longueurs de contrainte k ≤ 3, mais des valeurs allant jusqu'à k = 15 sont utilisées en pratique.

Le décodage Viterbi a été développé par Andrew J. Viterbi et publié dans l'article « Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm ».

Il existe des implémentations matérielles (dans les modems) et logicielles d'un décodeur Viterbi.

Le décodage de Viterbi est utilisé dans l' algorithme de décodage itératif de Viterbi .

Un décodeur Viterbi matériel pour code de base (non perforé) se compose généralement des blocs principaux suivants :

• unité métrique de branche (BMU)
• unité métrique de chemin (PMU)
• Unité de traçabilité (TBU)

La fonction d'une unité de métrique de branche est de calculer les métriques de branche , qui sont des distances normalisées entre chaque symbole possible dans l'alphabet de code et le symbole reçu.

Il existe des décodeurs Viterbi à décision dure et à décision souple. Un décodeur Viterbi à décision dure reçoit en entrée un flux binaire simple et utilise la distance de Hamming comme métrique. Un décodeur Viterbi à décision souple reçoit un flux binaire contenant des informations sur la fiabilité de chaque symbole reçu. Par exemple, dans un codage sur 3 bits, ces informations de fiabilité peuvent être codées comme suit :

Bien sûr, ce n'est pas la seule façon d'encoder des données de fiabilité.

La distance euclidienne au carré est utilisée comme métrique pour les décodeurs de décision souples.

Une unité de métrique de chemin agrège les métriques des branches pour obtenir les métriques des chemins, où K représente la longueur des contraintes du code, dont l'une peut être choisie comme optimale . À chaque cycle d'horloge, elle prend des décisions, en écartant volontairement les chemins non optimaux. Les résultats de ces décisions sont enregistrés dans la mémoire d'une unité de traçage.

Les éléments principaux d'une PMU sont des unités ACS (Ajouter-Comparer-Sélectionner) . Leur interconnexion est définie par le diagramme en treillis d'un code spécifique .

Comme les métriques de branche sont toujours nulles , un circuit supplémentaire (non représenté sur l'image) est nécessaire pour empêcher le débordement des compteurs de métriques. Une autre méthode, qui élimine la nécessité de surveiller la croissance des métriques de chemin, consiste à autoriser leur « rebond ». Pour ce faire, il est impératif de s'assurer que les accumulateurs de métriques de chemin contiennent suffisamment de bits pour que les valeurs « meilleure » ​​et « pire » ne soient pas à moins de 2 ^(n-1) l'une de l'autre. Le circuit de comparaison reste globalement inchangé.

Il est possible de surveiller le niveau de bruit du flux binaire entrant en suivant le taux de croissance de la métrique du « meilleur chemin ». Une méthode plus simple consiste à surveiller un seul état et à observer son évolution ascendante à travers quatre niveaux discrets dans la plage de l'accumulateur. À chaque franchissement de ces seuils, un compteur est incrémenté, reflétant le « bruit » présent sur le signal entrant.

L'unité de rétro-traçage rétablit un chemin (quasi) de vraisemblance maximale à partir des décisions prises par l'unité de gestion de programme (PMU). Comme elle effectue cette opération en sens inverse, un décodeur Viterbi utilise une mémoire tampon FILO (premier entré, dernier sorti) pour reconstituer l'ordre correct.

Notez que l'implémentation illustrée nécessite une fréquence double. Il existe des astuces permettant de s'affranchir de cette contrainte.

Pour exploiter pleinement les avantages du décodage à décision souple, il est nécessaire de quantifier correctement le signal d'entrée. La largeur optimale de la zone de quantification est définie par la formule suivante :

où est une densité spectrale de puissance du bruit , et k est un nombre de bits pour la décision souple.

La distance de norme au carré ( ) entre les symboles reçus et les symboles réels dans l'alphabet de code peut être simplifiée davantage en une forme de somme/différence linéaire, ce qui la rend moins gourmande en ressources de calcul.

Considérons un code convolutif 1/2 , qui génère 2 bits ( 00 , 01 , 10 ou 11 ) pour chaque bit d'entrée ( 1 ou 0 ). Ces signaux de retour à zéro sont convertis en une forme sans retour à zéro, illustrée ci-contre.

Chaque symbole reçu peut être représenté sous forme vectorielle comme v _r = {r ₀ , r ₁ }, où r ₀ et r ₁ sont des valeurs de décision souples, dont les magnitudes signifient la fiabilité conjointe du vecteur reçu, v _r .

De même, chaque symbole de l'alphabet du code peut être représenté par le vecteur v _i = {±1, ±1}.

Le calcul proprement dit de la distance euclidienne est le suivant :

Chaque terme au carré représente une distance normalisée, illustrant l' énergie du symbole. Par exemple, l' énergie du symbole v_{_i} = {±1, ±1} peut être calculée comme suit :

Ainsi, le terme d'énergie de tous les symboles de l'alphabet du code est constant (à la valeur ( normalisée ) 2).

L' opération Add-Compare-Select ( ACS ) compare la distance métrique entre le symbole reçu ||v _r || et deux symboles quelconques de l'alphabet de code dont les chemins convergent en un nœud du treillis correspondant, ||v _i ⁽⁰⁾ || et ||v _i ⁽¹⁾ || . Cela équivaut à comparer

et

Or, d'après ce qui précède, nous savons que l' énergie de v_{_i} est constante (égale à la valeur normalisée de 2) et que l' énergie de v_{_r} est la même dans les deux cas. Cela ramène la comparaison à une fonction de minima entre les deux termes du produit scalaire (intermédiaire).

car une opération min sur des nombres négatifs peut être interprétée comme une opération max équivalente sur des quantités positives.

Chaque terme de produit scalaire peut être développé comme

Dans ce contexte, les signes de chaque terme dépendent des symboles comparés , v _{_i} ⁽⁰⁾ et v _{_i} ⁽¹⁾ . Ainsi, le calcul de la distance métrique euclidienne au carré , nécessaire au calcul de la métrique de branche, peut être effectué par une simple opération d'addition/soustraction.

L'approche générale du traçage consiste à accumuler des métriques de chemin jusqu'à cinq fois la longueur de la contrainte (5 ( K - 1)), à trouver le nœud avec le coût accumulé le plus élevé et à commencer le traçage à partir de ce nœud.

La règle empirique couramment utilisée d'une profondeur de troncature de cinq fois la mémoire (longueur de contrainte K -1) d'un code convolutif n'est précise que pour les codes de taux 1/2. Pour un taux arbitraire, une règle empirique précise est 2,5( K - 1)/(1− r ) où r est le taux du code .

Cependant, le calcul du nœud qui a accumulé le coût le plus élevé (soit la métrique de chemin intégrale la plus élevée, soit la plus faible) implique la recherche des maxima ou minima de plusieurs (généralement 2 ^{K -1} ) nombres, ce qui peut prendre du temps lors de l'implémentation sur des systèmes matériels embarqués.

La plupart des systèmes de communication utilisent le décodage de Viterbi, qui repose sur des paquets de données de taille fixe, avec une séquence binaire ( bits / octets) fixe au début et/ou à la fin du paquet. En utilisant cette séquence binaire ( bits / octets ) comme référence, le nœud de départ peut être défini sur une valeur fixe, ce qui permet d'obtenir un chemin de vraisemblance maximale optimal lors du traçage.

L'implémentation physique d'un décodeur de Viterbi ne fournit pas un flux de vraisemblance maximale exact en raison de la quantification du signal d'entrée, des métriques de branchement et de chemin, et de la longueur finie du retour en arrière . Les implémentations pratiques s'en approchent néanmoins à moins de 1 dB de l'idéal.

Lors du décodage d'un message endommagé par un canal gaussien additif, le décodeur Viterbi génère des erreurs regroupées en rafales. Les codes correcteurs d'erreurs simples ne peuvent à eux seuls corriger ces rafales ; il est donc nécessaire soit de concevoir un code convolutif et un décodeur Viterbi suffisamment performants pour réduire le taux d'erreurs à un niveau acceptable, soit d'utiliser des codes correcteurs d'erreurs par rafales .

Un décodeur Viterbi matériel pour codes perforés est généralement implémenté de la manière suivante :

• Un déperceur, qui transforme le flux d'entrée en un flux qui ressemble à un flux original (non perforé) avec des marques ERASE aux endroits où des bits ont été effacés.
• Un décodeur Viterbi de base comprenant ces marques ERASE (c'est-à-dire ne les utilisant pas pour le calcul de la métrique de branche).

L'une des opérations les plus chronophages est un papillon ACS, qui est généralement implémenté en utilisant le langage assembleur et des extensions de jeu d'instructions appropriées (telles que SSE2 ) pour accélérer le temps de décodage.

L'algorithme de décodage de Viterbi est largement utilisé dans les domaines suivants :

• Communication radio : télévision numérique ( ATSC , QAM , DVB-T , etc.), relais radio , communications par satellite , mode numérique PSK31 pour la radio amateur .
• Décodage de la modulation à codage en treillis (TCM), la technique utilisée dans les modems de ligne téléphonique pour obtenir une efficacité spectrale élevée à partir de lignes téléphoniques analogiques de bande passante de 3 kHz.
• Dispositifs de stockage informatique tels que les disques durs .
• Reconnaissance vocale automatique