Rhouma Rhouma
École Supérieure d’Économie Électronique
Avril 2015
1 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
2 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
3 / 37
Propriétés
Les codes de convolution sont des codes binaires qui constituent une alternative aux codes de blocs par leur simplicité de génération grâce à quelques registres à décalage.
Introduits par Elias (1955)
Ils permettent de générer en ligne le code sans passer par une bondérisation préalable comme c’est le cas avec les codes BCH ou RS.
g ( i ) = 0 = ⇒ connexion absente et g ( i ) = 1 = ⇒ connexion présente C ( j ) = [ ] i = [−] 0 [1] [(] [)] [ ·][ m] [(] [−] [)] l’opération de convolution est aussi décrite polynomialement : C ( x ) = g ( x ) · m ( x )
4 / 37
K est appelé la longueur de contrainte du code : elle renseigne sur le nombre de fois qu’un bit participe à l’élaboration des bits de parités
K est égale au nombre de bascules +1
les coefficients gi forment un polynôme générateur g(x).
On peut générer simultanément des bits parités de deux générateurs différents g 1( x ) et g 2( x ) ou plus
les sorties vont être entrelacés
le rapport de code r est égal à 1 /n avec n est le nombre de sorties entrelacés
5 / 37
soit un code avec r=1/2 de longueur de contrainte K=3 et g 1 = [ g 1(0) g 1(1) g 1(2)] = [0 0 1] et g 1 = [ g 2(0) g 2(1) g 2(2)] = [1 1 1] les codes de chaque sortie est :
K − 1
g 1( i ) · m ( j − i )
i =0
K − 1
g 2( i ) · m ( j − i )
i =0
et
C 1( j ) =
C 2( j ) =
6 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
Publicité
8 Algorithme de Viterbi
7 / 37
8 / 37
Fonctionnement temporel
Avec le message m = [ m (0) m (1) m (2) . . . m ( L − 1)] = [1 0 0 1 1]
le mot de code final est donc : C = [01 01 11 01 00 10 11]
9 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
10 / 37
Chaque mot binaire est définit avec un polynôme.
Avec le même exemple : g 1( x ) = x [2]
et g 2( x ) = 1 + x + x [2] et m ( x ) = 1 + x [3] + x [4]
on a C 1( x ) = m ( x ) · g 1( x ) = x [2] + x [5] + x [6]
et C 2( x ) = m ( x ) · g 2( x ) = 1 + x + x [2] + x [3] + x [6]
avec la notation binaire C 1 = [0 0 1 0 0 1 1]
et C 2 = [1 1 1 1 0 0 1]
d’où C = [01 01 11 01 00 10 11]
11 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
12 / 37
13 / 37
à la base de la table précédente, on peut dessiner les graphes d’états avec comme convention : mj = 0 = ⇒ déplacement vers le haut et mj = 1 = ⇒ déplacement vers le bas
14 / 37
l’arbre du code représente la succession des états possibles. Les Conventions usuelles :
L’évolution temporelle est représentée de la gauche vers la droite chaque nouveau bit entré provoque un déplacement vers le haut s’il s’agit d’un "0" et vers le bas s’il s’agit d’un "1" sur chaque branche est porté le résultat de l’encodage (la sortie) conformément à la table de convolution
Pour le msg m = [ m 0 m 1 m 2 . . . mL− 1] = [10011] nous vérifions bien l’obtention du mot de code :
C = [01 01 11 01 00 10 11]
15 / 37
Représentation Graphique
16 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
17 / 37
Publicité
Par convention la représentation du treillis du code utilise les normes suivantes :
Le passage d’un état à un autre par la prise en compte d’un bit "0" est représenté en trait continu. Le passage d’un état à un autre par la prise en compte d’un bit "1" est représenté en trait pointillé. Sur le trait, est indiquée la sortie générée c’est à dire la portion du mot de code correspondante.
Dans le Treillis, on définit :
Cellule élémentaire Phase initiale Phase finale
18 / 37
En utilisant soit l’arbre du code soit les éléments de base constitutifs on peut dessiner une cellule élémentaire du treillis reliant l’instant t à l’instant t+1.
Cette cellule comporte 2 [−] [1] entrées et sorties.
19 / 37
Pendant M = K-1 instants, une partie de l’état des bascules est constitué des "0" d’initialisation.
Pendant tous ces instants, toutes les combinaisons ne sont pas possibles et tous les états ne sont pas accessibles.
Le treillis comporte donc à l’origine M (ici M=2) cellules correspondant à cette phase initiale.
20 / 37
A la fin du codage nous sommes amenés à introduire des "0" de queue.
De ce fait, seules les transitions en trait plein deviennent possibles et le treillis se résume à M (ici M=2) cellules ne comportant que ces transitions.
21 / 37
Treillis du code
Avec ce treillis nous vérifions que le message m = [ m 0 m 1 m 2 . . . mL− 1] = [1 0 0 1 1] génère le mot de code :
22 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
23 / 37
un sommet représente un état interne un arc orienté représente une transition. En trait plein pour celles induites par un "0" et en trait pointillé pour celles induites par un "1" la sortie ou portion de code généré est porté sur l’arc correspondant.
Avec ce graphe nous vérifions que le message m = [ m 0 m 1 m 2 . . . mL− 1] = [1 0 0 1 1] donne le mot de code : C = [01 01 11 01 00 10 11] sans oublier les bits de queue.
24 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
25 / 37
m : vecteur message et m : estimation du vecteur message
[ ]
C : Mot de code émis et C : mot de code estimé
[ ]
R : Mot de code reçu et e : erreur de transmission
Effet de la transmission+codage : m → C → R = C + e
role du décodeur : R → C [ ] → m [ ]
décodage : connaissant R, l’estimation C est optimale si la probabilité
[ ] d’effectuer une erreur de décodage est minimale.
Le maximum de vraisemblance choisit l’estimation C qui maximise
[ ] prob ( R/C ). Soit C [ ] = {prob ( R/C ) }max
avec prob ( R/C ) est la probabilité conditionnelle d’avoir reçu R sachant qu’on a envoyé C
26 / 37
La fonction log est une fonction monotone,
Publicité
donc C [ ] = {log [ prob ( R/C )] }max
Si le canal binaire symétrique est sans mémoire, tous les bits de message sont statistiquement indépendants et prob ( R/C ) = [ ] i =1 [(] [/] [)][ donc] log [ prob ( R/C )] = [ ] i =1 [[] [(] [/] [)]]
Pour le canal binaire symétrique, la prob d’erreur est p . Donc
- _prob_ ( _Ri_ _/Ci_ ) = 1 _−_ _p_ _Si_ _Ri_ = _Ci_
prob ( Ri /Ci ) = p if Ri = Ci
Si R et C sont différents de d bits (nb d’erreur =dans un mot de code de n − bits ) alors la distance de hamming entre C et R est égale à d .
donc log [ prob ( R/C )] = d·log ( p )+( N−d ) ·log (1 −p ) = d·log ( 1 −p p [)+] [·] [(][1] [−] [)]
27 / 37
la probabilité d’erreur vérifie généralement p < 1 / 2, donc d · log ( 1 −p p [)] [ <] [ 0 et puisque] [ N][ ·][ log] [(][1] [ −] [)][ est constante,] log [ prob ( R/C )] est maximale, si d est minimale.
C - est donc aussi choisit de manière à minimiser la distance de Hamming entre C et R
[ ]
Pour cela, C est bien sûr inconnu mais nous avons à notre connaissance le treillis du code et, à la réception de R, nous chercherons à minimiser la distance de Hamming entre le code reçu et tous les codes possibles. Le plus "proche de R" constituera l’estimation la plus vraisemblable.
Autrement dit : le décodeur compare le code reçu avec toute les possibilités de C et choisit celle qui est la plus proche de R .
28 / 37
1 Propriétés
2 Fonctionnement temporel
3 Méthode polynomiale
4 Représentation Graphique
5 Treillis du code
6 Diagramme d’état
7 Décodage par Maximum de Vraisemblance
8 Algorithme de Viterbi
29 / 37
En utilisant le treillis nous réalisons les opérations suivantes :
1 nous examinons chaque portion de code reçue puis nous calculons la distance entre cette portion de code et la sortie du treillis pour toutes les possibilités.
2 Cette distance ajoutée à celle associée au nœud d’origine (état présent) est portée sur le nœud ainsi atteint (état suivant). Un nœud comportera deux indications puisqu’il y a deux façons de l’atteindre.
3 Pour l’étape suivante, nous ne conservons pour un nœud que la distance minimale ce qui revient à ne conserver qu’un certain nombre de "trajets" probables : les survivants.
4 Nous recommençons l’opération 1 jusqu’à épuisement du code reçu.
5 Le code le plus probable sera celui qui à la suite de ces opérations correspondra à la distance totale la plus faible et le message est reconstitué en interprétant la suite des "pleins" et "pointillés" associés au trajet le plus probab ~~le~~
30 / 37
Soit le mot de code reçu suivant Y = [01 01 01 01 00 10 11]
et recherchons la meilleure estimation grâce au treillis et aussi au fait que nous savons qu’il existe une phase initiale et une phase finale toutes les deux de longueur M = K-1. Ici M = 2.
31 / 37
Phase initiale : elle dure deux coups. L’état initial est nécessairement l’état interne "0" soit a dans notre exemple.
32 / 37
Algorithme de Viterbi
Phase centrale : premiere cellule élémentaire
33 / 37
Algorithme de Viterbi
Phase centrale : deuxième cellule élémentaire
34 / 37
Algorithme de Viterbi
Phase centrale : troisième cellule élémentaire
35 / 37
Algorithme de Viterbi
Phase finale : on sait que les M derniers blocs correspondent à la phase finale pendant laquelle seuls les "0" (trait plein) sont introduits.
Premier "0" de queue :
36 / 37
Algorithme de Viterbi
Phase finale : deuxième "0" de queue.
Le dernier trajet survivant est le plus vraisemblable et correspond au message [ 1 0 0 1 1 ] . L’erreur de transmission a ainsi été corrigée.
37 / 37