35
2 ème année Génie Des Systèmes De Télécommunications et Réseaux Théorie de l’information LES CODES CONVOLUTIFS Réalisé par : Proposé par : Assia MOUNIR Mr. LYHYAOUI Anas BENNANI Anouar LOUKILI Ali Broma SIDIBE Année scolaire 2008-2009

Codes Convolutifs

Embed Size (px)

DESCRIPTION

Codage canal : Codes convolutifs

Citation preview

  • 1. 2me anne Gnie Des Systmes De Tlcommunications etRseaux
    Thorie de linformation
    LES CODES CONVOLUTIFS
    Ralis par:Propospar :
    Assia MOUNIRMr. LYHYAOUI
    Anas BENNANI
    Anouar LOUKILI
    Ali Broma SIDIBE
    Anne scolaire 2008-2009

2. PLAN
Introduction
Codes convolutifs
Gnralits
Encodeurs
Codes NSC/ RSC
Diagramme d'tats
Arbre
Treillis
Algorithme de dcodage: Viterbi
Matlab
Convenc
poly2trellis
vitdec
Exemples & Applications
2
3. INTRODUCTION
Thorie de linformation
Bruit
Thorme de Shannon
Tout canal de transmission admet un paramtre C, appel capacit du canal, tel que pour tout e > 0 et pour tout R < C, il existe un code de taux R permettant la transmission du message avec un taux derreurs binaire de e.
3
4. 4
La famille des codes correcteurs derreurs
Codes correcteurs
Codes en blocs
Codes en treillis
Codes non linaires
Modulation en treillis
Codes convolutifs
Modulation en bloc
Codes linaires
Turbo codes
Codes non cycliques
Codes cycliques
Non rcursifs
rcursifs
5. Codes convolutifs
Gnralits
Le principe des codes convolutifs, invents par ''Peter Elias'' en 1954, est de considrer des squences semi-infinies a0a1a2 de symboles qui passent travers une succession de registres dcalage, dont le nombre est appel mmoire du code, et de gnrer des squences semi-infinies.
Les codes convolutifs constituent une classe extrmement flexible et efficace de codes correcteurs d'erreurs. Ce sont les codes les plus utiliss dans les communications fixes et mobiles.
5
6. Principe du codage convolutif
Encodeurs

Le codeur qui gnre un code convolutif comporte un effet mmoire:
Le mot de code ne dpends pas que du bloc de k symboles entrants, mais aussi desm codes qui l'on prcd, stock dans des registres.
6
7. Proprits
Le rendement du code est: R=k/n
La quantit (m+1).k s'appelle longueur de contrainte du code.
Linarit
Stationnarit
7
8. Codes NSC/ RSC
Code convolutif non systmatique (NSC):
Les codes NSC, prsentent lavantage par rapport aux codes systmatiques de fournir plus dinformation : tout bit de sortie du codeur renseigne sur plusieurs bits du message cod. Le dcodeur dispose donc de plus dlments dans un code NSC, et permet donc de corriger plus derreurs.
Code convolutif systmatique rcursifs (RSC):
Un code convolutif est dit rcursif si la squence passant dans les registres dcalages est alimente par le contenu de ces registres.
Exemple:
8
9. Exemple
Soit lecodeur convolutif non systmatique (k=1, n=2, m=2)
Transforme en D
9
10. Reprsentation des codes convolutifs
Diagramme d'tat :
Il reprsente la succession des tats possibles. Ce sera donc une arborescence constitue des lments de base prcdents et dont la complexit sera croissante.
10
11. Arbre:
Les conventions adoptes:
- Le temps scoule de la gauche la droite
- Lorsque llment binaire dentre du codeur est gal 0 (resp. 1), le couple binaire en sortie du codeur est port par la branche suprieure (resp. infrieure)
Si par exemple la squence dinformation coder est: 1001
Le mot de code associ 1001 est donc11011111
11
12. Treillis:
Contrairement aux autres reprsentation prcdentes, celle en treillis met en vidence le paramtre temps: chaque nud=tat du codeur un instant j.
L'inconvnient essentiel de l'arbre du code est que l'arborescence est multiplie par 2 chaque bit supplmentaire et la reprsentation devient vite impossible raliser.
Les remarques faites sur le nombre limit d'tats possibles va nous permettre de compacter ce graphe en attribuant chaque instant un nud un tat.
13.Treillis:
Un chemin complet commence ltat S(0,0) et se termine S(o,L).
Un mot de code convolutif na pas de longueur fixe, cependant pour des contraintes pratiques la plupart des applications imposent une longueur max du mot .
A cet effet, on ajoute mbits (dits bitsde queue) nuls, on forceainsi le treillis revenir ltat S(0,L).
14.Treillis:
Dans ce cas , les codes convolutifs avec terminaison sont vus comme des codes en bloc de rendement:
La rduction du taux de codage:
diminue fortement pour des L>>m
15. Dcodage des Codes Convolutifs
La contrainte principale du dcodage convolutif rside dans le fait que le mot de code est trs long, ce qui a tendance compliquer le circuit dcodeur. Les algorithmes de dcodage les plus rpandus sont :
Dcodage squentiel : introduit par WONZENCRAFT(1961)
amlior par FANO(1963) et ZIGANGOROV(1968)
Dcodage par Seuil : introduit par MASSEY (1963)
bas sur la longueur de contrainte du bloc en cours de dcodage plutt que sur lutilisation de toute la squence reue, ce qui conduit des performances de dcodage infrieures aux autres mthodes.
Dcodage VITERBI : bas sur le principe de max de vraisemblance ( Max Likelihood)
Mthode optimale pour le dcodage des codes convolutifs.
Performances dpendantes de la qualit du canal.
Complexit croit exponentiellement avec (m+1)k (contrainte de code)
16. Algorithme de Viterbi:
Lalgorithme de Viterbi entre dans le cadre du dcodage maximum de vraisemblance des codes convolutifs.
Le dcodage maximum de vraisemblance correspond chercher dans le treillis du code C le chemin le plus proche (le plus vraisemblable) de la squence reue.
A chaque instant, deux branches appartenant deux chemins diffrents, convergent vers chaque nud.
De ces deux chemins, lun est plus vraisemblable, cest--dire se trouve une distance plus petite de la squence reue, que lautre chemin.
Les distances tant additives, il est possible de ne conserver en chaque nud que le chemin le plus vraisemblable, appel survivant.
Si deux chemins sont aussi vraisemblables, un seul chemin est arbitrairement conserv.

17. Algorithme de Viterbi: Exemple
Soit le treillis lmentaire d'un code convolutif :
On considre la squence dinformation suivante : 1001
La squence code est donc : 11 10 11 11
Une erreur survient dans la transmission du troisime bit.
La squence reue est donc : 11 00 11 11
18. Algorithme de Viterbi: Exemple
On dcode la squence reue en utilisant lalgorithme de Viterbi:
19.

  • On compare les bits de la squencereue avec les bits de transition 20.Le nombre de diffrences entre les deux est gal au poids quon affecte au nud

On continue avancer dans le treillis on faisant des mises jours
On construit les diffrents codes possible freet mesure
21. Au moment ou on obtient deux poids pour le mme nud on procde par limination sur le critre de minimum de poids
22. Si obtient sur un nuddeux poids gaux on limine lun deux au hazard
23. Aprs un certain nombre de transition on compare les poids des nuds
Le chemin ayant le nud extrme de poidsle plus faible est lu.
24. Partie Matlab
Convenc
Poly2trellis
Vitdec
24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. Exemples et applications
Satellites de communications
Satellites militaires
Sonde spatiale ( voyager)
Tlmtrie
Rseaux sans fils LAN/WAN
les standards de tlphonie mobile de 2G (GSM) & 3G (UMTS)
33
34. 34
Exemples :

  • La norme GSM (Global System for Mobile Communications) incorpore un code de longueur de contrainte Kc = 6 et de rendement 1/2. 35. La norme USDC utilise un code avec Kc = 6 et un rendement 1/2. 36. La norme IS-95 emploie un code avec Kc = 9 et un rendement de 1/2 en canal

montant et 1/3 en canal descendant,

  • Globalstarutilise un code de rendement 1/2 avec Kc = 9, 37. et pour Iridium le rendement est de 3/4 et la longueur de contrainte Kc = 7.

CONCLUSION
35