Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Distance de Hamming
Soit A un ensemble fini, non vide, et n un entier naturel non nul .
Comme d’habitude, An désigne l’ensemble des x :(x1,x2,…xn)avec xi appartenant à A.
Soient x et y deux éléments de An, on appelle distance de Hamming entre x et y, le nombre de composantes pour lesquelles ces éléments diffèrent.
Plus précisément si x :(x1,x2,…xn) et y :(y1,y2,…yn) alors : D(x,y) = card{i ∈{1,2,…n}/xi≠ yi} (1.1). Exemple : Soit A :{a,b,c} et n = 5 alors pour x = (a,a,b,c,a) et y = (a,b,c,a,a).
On a d(x,y) = 3.
Les propriétés d e cette distance sont.
i) d(x,y) ∈R+.
ii) d(x,y) = 0 implique x=y.
iii) d(x,y) = d(y,x).
iv) d(x,y) ≤ d(x,z) + d(z,y).
condition de décodage d’ordre e, rayon de recouvrement
Un code C de longueur n sur un alphabet A vérifie la condition de décodage d’ordre e si pour tout x, de An, il existe au plus un mot x de C tel que d(x, x,) ≤ e. Cette condition est équivalente à ce que les boules fermés (pour la distance de Hamming )de rayon e ,centrés sur les mots de C, soient deux à deux disjointes.
Exemple :
soient A = {0,1}, n = 5,e = 1 et soit le code :
C = {x = (0,1,1,1,0), y = (1,0,1,0,1), z = (1,1,0,1,1)}
On désigne par B(a,r) la boule fermée de centre a et de rayon r ,on a :
B(x,1) = {(0,1,1,1,0),(1,1,1,1,0),(0,0,1,1,0),(0,1,0,1,0),(0,1,1,1,1),(0,1,1,0,0)} B(y,1) = {(1,0,1,0,1),(0,0,1,0,1),(1,1,1,0,1),(1,0,0,0,1),(1,0,1,1,1),(1,0,1,0,0)} B(z,1) = {(1,1,0,1,1),(0,1,0,1,1),(1,0,1,1,1),(1,1,1,1,1),(1,1,0,0,1),(1,1,0,1,0)}
Le code C vérifie la condition de décodage d’ordre 1 car les trois boules sont disjointes 2 à Un mot reçu pour lequel s’est introduit une erreur et une seule ne peut provenir, de cette manière que d’un seule mot de C et que l’on peut donc retrouver.
Par exemple, lorsqu’on reçoit le mot (1,1,1,0,1) en sachant qu’il y a une erreur au plus, le mot envoyé est y.
Contre –exemple :
Soient A = {0,1}, n = 3,e = 1 et soit le code.
C = {x = (0,0,0), y = (1,0,1)},on a :
B(x,1) = {(0,0,0),(1,0,0),(0,1,0),(0,0,1)}.
B(y,1) = {(1,0,1),(0,0,1),(1,1,1),(1,0,0)}.
Les deux boules ne sont pas disjointes. En effet :
B(x,1) ∩B(y,1) = {(1,0,0),(0,0,1)}.
Si le mot reçu est (1,0,0)(ou (0,0,1))il est donc impossible de savoir s’il provient de x ou de y.
Stratégies de correction d’erreur
Technique de retransmission (ARQ)
• Retransmission avec arrêt et attente : on transmet un bloc d’information puis on attend l’accusé de réception avant de transmettre le bloc suivant.
• Retransmission continue : les blocs d’informations arrivent sans arrêt jusqu’à ce que le décodeur signale une erreur dans un certain bloc, alors la retransmission reprend à partir du bloc erroné .
• .Retransmission avec répétition sélective :en cas d’erreur, on reprend la retransmission du bloc erroné, et le récepteur s’occupera de la réinsertion du bloc corrigé au bon endroit.
Codes conventionnelles
On procède comme précédemment, avec la différence qu’ici, chaque mot de code dépend d’un certain nombre de blocs d’information précédents.
La réalisation pratique du codeur nécessite des circuits séquentiels, notamment des registres à décalages .
Principe de la détection et de la correction des erreurs
En notant C le mot du code émis et R le mot reçu à l’entrée du décodeur, on a la relation suivante :
R=C+E (1.2).
Où E représente le mot correspondant à l’erreur de transmission.
Une composante du vecteur E égale à 1 indique la présence d’une erreur de transmission sur la position correspondante du mot C. La détection des erreurs de transmission se fait en utilisant la propriété d’orthogonalité de la matrice de contrôle de parité avec les mots du code et calculant le syndrome s, vecteur ligne à(n-k)composantes définies par : S = R Ht = ( C + E ) Ht = E Ht (1.3). Le syndrome S est nul si et seulement si,r est un mot du code. Un syndrome non nul implique la présence d’erreur de transmission.
Néanmoins, un syndrome nul n’implique pas forcément l’absence d’erreur de transmission car le mot R peut appartenir aux mots du code tout en étant différent de C. Pour cela, le vecteur E est un mot du code. En effet, pour un code linéaire, la correction des erreurs peut aussi être réalisée à partir du syndrome S dont le nombre de configuration 2n-k est généralement inférieur aux 2k mots du code. Le nombre de configurations non nulles du vecteur d’erreurs E,2n –1,etant supérieure au nombre de configurations du syndrome ,plusieurs configurations du vecteur e peuvent conduire à une même valeur du syndrome .
La règle de décodage peut alors consister à choisir chaque valeur non nulle du syndrome, la configuration d’erreur E de poids minimal.
On peut montrer que cette façon de procéder est équivalente à la recherche systématique du mot le plus vraisemblable. En effet, pour un code en blocs pouvant corriger t erreurs, toutes les configurations d’erreurs de poids inférieur ou égal à t correspondent à des valeurs différentes du syndrome. Le mot du code le plus vraisemblable est alors égal à R-E.
Décodage par maximum de vraisemblance
Dans le canal binaire symétrique, la probabilité pour qu’un bit reçu soit erroné est p .
La probabilité de recevoir un mot de longueur n sans erreur est (1-p)n.
La probabilité de recevoir un mot avec une erreur dans une position donnée est p(1-p)n-1.De même, la probabilité de recevoir un mot avec une configuration donnée de a erreurs est pa(1-p)n-a.
Puisque p< ½, l’occurrence d’une seule erreur est beaucoup plus probable que celle de deux erreurs dans le même mot, et celle de trois erreurs est encore moins probable.
Les probabilités précédentes s’ordonnent comme suit : (1-p)n>p(1-p)n-1> p2 (1-p)n-2>… pa(1-p)n-a
Il paraît donc raisonnable d’accepter que le mot erroné est une déformation du mot de code le plus proche (au sens de Hamming).C’est le principe du décodage selon le maximum de vraisemblance.
Code de Hamming
Pour un code de Hamming, les colonnes de la matrice de contrôle de parité sont les représentations des nombres de 1à n. Chaque colonne étant constitué de m= n-k éléments binaires, les paramètres du code de hamming sont donc :N=2m-1 k=2m-m-1
La distance minimale d’un code de Hamming est de 3,quelle que soit la valeur des paramètres n et k .
On peut démontrer cela de la façon suivante :
La distance minimale est égale au plus petit nombre de colonnes linéairement dépendantes de la matrice de contrôle de parité. Les colonnes étant constitués par toutes les combinaisons possibles de (n-k) éléments binaires, sauf [0 0 0…0],la somme de deux colonnes est égale à une colonne. Ainsi, le nombre minimal de colonnes linéairement dépendantes est de 3.
Le code de Hamming permet de corriger au moins une erreur dans un bloc de n éléments binaires et d’en détecter deux. Le décodage est encore très simple à réaliser puisque le syndrome s en présence d’une erreur est égal à une colonne de la matrice de contrôle de parité. Connaissant la position de colonnes dans la matrice de contrôle de parité, il est facile d’en déduire la position de l’erreur.
Performances des codes en blocs linéaires
Pour évaluer les performances d’un code en bloc linéaire, on peut essayer de déterminer la probabilité d’erreur sur les éléments binaires après décodage en fonction du rapport signal à bruit. Pour cela, considérons un code C(n,k) de distance minimale Dmin = 2t+1 c’est-à-dire permettant de corriger t erreurs dans un bloc de n éléments binaires. En supposant que les erreurs produites par le canal de transmission sont indépendantes ( transmission sur un canal binaire symétrique par exemple),la probabilité d’erreur par élément binaire Peb peut être bornée supérieurement par : 1 n Peb ≤ ∑(i + t)Cni pi (1− p)n−i (1.17).
Code cyclique sous- forme systématique
Un code est systématique si les éléments binaires d’information sont séparés des éléments binaires de redondance, et ainsi, le mot C(x) associé au polynôme m(x) est de la forme :
C(x) = V(x)+xn-km(x) (1.26).
Où v(x) est le polynôme de degré au plus égal à n-k-1, associé aux éléments binaires de redondance.
En tenant compte du fait que C(x) est un multiple du polynôme générateur et que les opérations sont effectués dans le corps F2 , cette expression peut s’écrire : xn-km(x) = k(x) g(x)+ v(x) (1.27)
Où v(x) est le reste de la division de xn-km(x) par le polynôme générateur.
Ainsi, le mot du code associé à m(x) est égal à xn-km(x) augmenté du reste de la division
xn-km(x) pour le polynôme générateur g(x).
Code de GOLAY [15]
Le code de Golay est un code cyclique de paramètres n = 23 ; k = 12,de distance minimale Dmin = 7 et de pouvoir de correction t = 3.
Deux polynômes équivalents g1(x) et g2(x) ,de degré 11 permettant d’engendrer un
code de Golay.
g (x) = 1+ x + x5 + x6 + x7 + x9 + x11.
g2 (x) = 1+ x2 + x4 + x5 + x6 + x10 + x11.
Ce code représente un intérêt tout particulier, car sa capacité de correction est élevée au regard de s on rendement. Il existe, de plus, pour ce code, des algorithmes de décodage relativement simples.
Dans certains cas , le code de Golay est également utilisé avec ajout d’un bit de parité, ce qui donne alors un code de rendement ½.
Correction des erreurs
Nous avons vu que pour la détection d’erreur, on choisissait essentiellement des codes en blocs. Pour la correction d’erreur, codes en blocs et codes convolutifs sont respectivement utilisés. Généralement, les codes en blocs sont préférés aux codes convolutifs chaque fois que l’on recherche un code de rendement élevé(R>0,9) ou lorsque transmission à coder est réalisée par paquets assez courts.
Lorsque les éléments binaires d’information sont transmis à flot continu et pour un rendement de codage pas trop élevé, les codes convolutifs avec décodage pondéré sont en général bien adapté. Pour corriger les paquets les plus longs et ayant la plus forte densité d’erreurs, il est nécessaire de choisir un code très performant et certainement très redondant. Le code voit alors ses capacités de correction sous- employés pendant une grande partie du temps. Pour éviter cet inconvénient, on utilise la technique de l’entrelacement.
Sous certaines conditions, cette technique permet de transformer un canal à paquets d’erreur en un canal à erreurs indépendants.
Générateur de syndrome
Si le mot reçu n’est pas erroné, c’est un multiple de g(x). S’il y a eu des erreurs, et si le mot reçu erroné n’appartient pas au code, la division du mot reçu par g(x) donnera un reste non nul. On peut ainsi considérer le reste de la division comme syndrome.
Une variante souvent employée du générateur de syndrome est basée sur le diviseur prémultiplié par xr. Son avantage est de permettre l’utilisation pratique du même circuit pour le codage et le générateur du syndrome. Cependant, il n’engendre pas exactement le syndrome mais son « décalé r fois »
Voici l’exemple du générateur de syndrome pour g(x) = x3+x+1.
Codage par multiplication
Tout mot appartenant à un code cyclique est divisible par son polynôme générateur.
Donc, pour c(x) ∈C(n,k), on a : C(x) = f(x).g(x) mod (xn+1) (2.2).
Le codage par multiplication part de cette formule en remplaçant f(x) par le mot d’information. Pratiquement, il suffit d’utiliser un circuit multiplieur dont g(x) est le multiplieur, donc fixe.
Le multiplicande est formé par le mot d’information.
Par ailleurs, il faut aussi noter que les coefficients du produit de deux polynômes formaient le produit de convolution discrète de coefficients des deux polynômes.
On forme le produit degré par degré en retournant le multiplieur et en multipliant pour chaque degré les termes qui se trouvent face à face.
Codage par division
C’est la méthode la plus adoptée pour l’opération de codage.
Théoriquement, le principe repose sur la propriété élémentaire du code cyclique.
Soit alors un code cyclique C de polynôme générateur g(x).
Soit a(x) = ∑ik=−01ai xi la représentation polynomiale de l’information.
Xn-k a(x)= g(x) m(x)+ r(x) avec deg r(x) inférieur ou égal à n-k-1.
Par définition C(x) la représentation polynomiale d’un mot du code est un multiple de g(x), d’où C(x)= Xn-k a(x)+r(x) avec r(x) le reste de la division de Xn-k a(x) par g(x).
Le codeur doit donc effectuer la division de Xn-k a(x) par le polynôme générateur g(x)
puis ajouter le reste r(x) de cette division à Xn-k a(x)
L’opération la plus délicate est ici le calcul du reste de la division.
De ce fait, l’étude approfondie d’un circuit diviseur s’avère indispensable.
|
Table des matières
Partie1 :THEORIE DES CODES CYCLIQUES
Chapitre I :généralités sur la théorie du codage
I.1 Introduction
I.2 Canal de transmission
I.3 Définitions et objectifs
I.3.1 Définitions
I.3.2 Objectif
I.4 Codes correcteurs d’ erreurs
I.4.1 Description
I.4.2 Distance de Hamming
I.4.3 Condition de décodage d’ ordre e
I.4.4 Stratégie de correction d’ erreur
I.4.4.1Technique de transmission
I.4.4.2 Correction automatique
a) Bit de parité
b) Parité croisée
c) Codes en bloc
d) Codes conventionnelles
e) Codes systématique
I.4.5 Principe de la détection et de la correction des erreurs
I.4 .6 Indice de qualité
I.4.6.1 Efficacité
I.4.6.2 Taux d’ erreur brute
I.4.6.3 Taux d’ erreur résiduel
I.4.6.4 Rendement d’un code
I.4.7 Décodage par maximum de vraisemblance
Chapitre 2 :Codes linéaires
II.1 Définitions
II.2 Propriétés
II.2.1 Poids d’ un vecteur
II.2.2 Condition de décodage
II.2.3 Capacité de correction d ‘ un code linéaire
II.3 Matrice génératrice et matrice de contrôle
II.3.1 matrice génératrice
II.3.1.1 Définition
II.3.1.2 Propriétés
II.3.1.3 Remarque
II.3.2 . Code systématique
II.3.3 Code dual et matrice de contrôle
II.3.3.1 Code dual
II.3.3.2 Matrice de contrôle
II.3.3.3 Exemple
II.4 Syndrome
II.4.1 Définition
II.4.2 Propriété
II.5 Décodage des codes linéaires
II.5.1 Définition
II.5.2 Décodage du voisin le plus proche
II.5.3 Décodage par le tableau standard
II.5.3.1 Tableau standard
II.5.3.2 Exemple
II.5.3.3 Algorithme de décodage
II.5.4 Décodage utilisant le tableau réduit
II.6 Quelques exemples de codes en blocs linéaires
II.6.1 code de parité
II.6.2 code à répétition
II.6.3 Code de Hamming
II.6.4 Code à longueur maximale
II.7 Performances des codes en bloc linéaires
Chapitre III : Codes cycliques
III.1 Définition et représentation polynomiale
III.1.1.Definition
III.1.2 Représentation polynomiale
III.2 Polynôme générateur
III.2.1 Définition
III.2.2 Matrice génératrice du code cyclique
III.2.3 Exemples
III.3 Polynôme de contrôle
III.3.1 Définition
III.3.2Matrice de contrôle H du code cyclique
III.4 Code cyclique sous forme systématique
III.4.1.Definition
III.4.2 Exemple
III.5 Exemple de code cyclique
III.5.1Code B.C.H
III.5.1.1Definition
III.5.1.2 Propriétés
III.5.1.3 Exemple
III.5.2 Code de REED-SOLOMON
III.5.2.1 Définition
III.5.2.2 Propriétés
III.5.2.3Exemple
III.5.2.4 Applications
III.5.3 Code de Golay
ChapitreIV : Mise en oeuvre du codage correcteur d’erreurs
IV.1 Détection des erreurs
IV.2 Correction des erreurs
IV.3 Association de plusieurs codes : concaténation
PARTIE 2/ REALISATION PRATIQUE DES CODES CYCLIQUES
Chapitre I : Algorithme de codage et décodage
I.1Principe de codage
I.2Principe de décodage
I.2.1 Générateur de syndrome
I.2.2 Circuit de correction
Chapitre II : Modélisation des opérations de codage et décodage
II .1 Codage
II .1.1 .Codage par multiplication
II .1.2 Codage par division
II .1.3 Circuit de division
II .1.4 Exemple de codeur
a) Codeur performant
II .2 Décodage
II .2.1 Décodage de Megitt
II .2.1.1 Principe de décodage
II .2.1.2 Algorithme de décodage de Megitt
II .2.1.3.Schema du décodeur de Megitt
II .2.1.4 Exemple
II .2.2. Décodage par piégeage d’erreur
II .2.2.1 Algorithme de décodage par piégeage d ‘ erreur
II.2.2.2 Schéma d’ un décodeur par piégeage d’ erreur
Partie 3 : SIMULATION
Chapitre 1 : Etude de fonctionnement
I.1 Présentation de Electronics Workbench
I.2 Décodeur
I.2.1 Généralités
I.2.2 Décodeur 1 parmi 8
I.2.3 Décodeur 1 parmi 32
I.2.4 Pilote/ décodeur DCB 7 segments
I.3. Codeurs
I.3.1. Codeur de priorité
I.3.2 Codeur d’interrupteurs
I.4.Multiplexeurs
I.4.1 Génération d’une fonction
I.4.2 Multiplexeur à 16 entrées
I.5.Demultiplexeur
I.6 Conversion numérique analogique
I.7 Conversion analogique numérique
I.7.1 CAN rampe numerique
I.7.2 CAN parallels (Flash)
Télécharger le rapport complet
