Réseaux Informatiques : Master 1 informatique mif11 reseau codage et elements de th
Télécharger PDFObtenir le pack complet des cours, TDs, examens sur Réseaux Informatiques!
Vous souhaitez maîtriser Réseaux Informatiques ? Ne cherchez plus, nous avons le pack bien choisi pour vous.
Accédez à une collection complète des supports de cours, des travaux dirigés (TD) corrigés, examens...
Télécharger packMaster 1 Informatique
MIF11 -Réseau
Codage et éléments de
théorie de l'information
Florent Dupont
Université Claude Bernard Lyon1 / Laboratoire LIRIS
Florent.Dupont@liris.cnrs.front Florent Dupont 2
Objectifs du cours
•Théorie des codes...liée aux transmissions numériques
–compression des signaux transmis (son, image, vidéo, 3D...)
–protection contre les erreurs de transmission
–cryptage, authentification des messages–... Florent Dupont 3
Objectifs du cours
•Rappeler quelques notions de base en transmission de données :
–Bande passante, capacité d'un canal ;
–Modulation ;
–Codage en bande de base ;
–Multiplexage.
•Avoir un avis éclairé pour répondre, par exemple aux questions suivantes :
–La transmission sans erreur sur un canal bruité est-elle possible? –Est-ce que transmettre sans erreur, c'est avoir un rendement tendant vers 0 ou bien existe-t-il un rendement optimal, pour un niveau de bruit donné ? Florent Dupont 4
Plan du cours
1.Notions de base en transmission de données 2.Théorie de l'information
3.Source discrète / Codage source
4.Canal discret / Codage canal
5.Codes détecteurs et codes correcteurs
9h de Cours Magistral
6h de Travaux Dirigés
Florent Dupont 5
Pour en savoir plus...
•Théorie des codes
Compression, cryptage, correction
(Ed. Dunod)
Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, Sébastien Varrette
Florent Dupont 6
1. Notions de base en transmission de données •Canal= dispositif permettant d'acheminer un message entre deux points distants
•Sur de courtes distances :
•Canal de transmission = support physique (câble coaxial, fibre optique, air...)
•ETTD : Équipement Terminal de Transmission de Données
Canal de transmission
Ordinateur ou Terminal
= ETTD
Ordinateur ou Terminal
= ETTD
Florent Dupont 7
Canal discret
•Sur de plus longues distances
•Ex : canal de transmission = Ligne téléphonique
•Modem : Modulateur / démodulateur
•ETCD: Équipement Terminal de Circuit de Données
•Les informations sont transmises sur des supports de transmission en faisant varier un ou plusieurs paramètres physiques des signaux.
Canal de transmissionModem ETCDModem ETCD
Circuit de données
Ordinateur ou Terminal
= ETTD
Ordinateur ou Terminal
= ETTD
Florent Dupont 8
Parenthèse
Traitement du signal
fréquence / discret
Florent Dupont 9
Fréquences : Fourier
•Toute fonction périodiqueg(t)ayant pour période T=1/fpeut se décomposer en une somme de fonctions périodiques sinusoïdales et cosinusoïdales:
•Les coefficients an et bn sont les amplitudes respectives des sinus et cosinus (harmoniques) et c est égal à la valeur moyenne du signal:
•Cette décomposition est appelée série de Fourier.
•Exemples : fréquences dans un signal, une image...1n n1n n
)nft2cos(b)nft2sin(ac)t(gT 0T 0n T0 ndt)t(g T1 c,dt)nft2cos()t(gT 2
b,dt)nft2sin()t(gT 2a Florent Dupont 10
Fréquences : Fourier
•Transformée de Fourier
Représentation d'un signal sur une base de fonctions exponentielles complexes
–Cas mono-dimensionnel
dxe).x(f)u(Fdue).u(F)x(f
jux2jux21 FF Florent Dupont 11
Exemple : réponse en fréquence de l'oeil
Florent Dupont 12
Numérisation / discrétisationTemps AmplitudeContinu Discret
ContinueDiscrète
Il n’y a que dans ce cas que l’on peut associer un nombre entier au signal
Signal «analogique»Signal quantifié
Signal numériqueSignal échantillonné
capa commutées / CCDCalculateur
Filtre analogique / ampliSignal logique idéalisé
Monde réel macros.
Échantillonnage
Quantification
Florent Dupont 13
Échantillonnage : Théorème de Shannon
Un signal incorrectement échantillonné ne pourra pas être reconstitué
ThéorèmeDe Shannon: Fe > 2 x Fmax(Signal)
Exemple:
Échantillons Signal reconstitué ? Florent Dupont 14
Fin de la parenthèse
Florent Dupont 15
Bande passante
La bande passante caractérise tout support de transmission, c'est la bande de fréquences dans laquelle les signaux sont correctement reçus :
W = Fmax –Fmin (en Hz)
Le spectre du signal à transmettre (éventuellement modulé) doit être compris dans la bande passante du support physique.
Florent Dupont 16
Bande passante
•Exemples: •l'atmosphère élimine les U.V.
•l'oreille humaine est sensible dans la bande 20 Hz-20 KHz
•Réseau téléphonique commuté (RTC)
AmplitudeA maxA max-3dB300 3400
3100 Hz
FréquenceHz Florent Dupont 17
Utilisation des bandes de fréquences
Florent Dupont 18
Utilisation des bandes de fréquences
Florent Dupont 19
Agence nationale des fréquences (
•Bandes de fréquences: attribuées aux différents services de radiocommunication par le Règlement des radiocommunicationsde l'Union internationale des télécommunications, élaboré par les conférences mondiales des radiocommunications. •En France, les bandes ainsi attribuées sont réparties entre 9 affectataires (7 administrations et 2 autorités indépendantes) –ACAdministration de l’aviation civile
–DEFMinistère de la défense
–ESPEspace
–INTMinistère de l’intérieur
–MTOAdministration de la météorologie
–PNMAdministration des ports et de la navigation maritime (ex phares et balises)
–RSTMinistère de l’éducation nationale, de la recherche et de la technologie
–CSAConseil supérieur de l'audiovisuel
–ARTAutorité de régulation des Télécommunications
Florent Dupont 20
Agence nationale des fréquences (
•+ des fréquences utilisables pour certains matériels de faible puissance et de faible portée
•Exemple :
Bande des fréquences2400 à 2454 MHz
Puissance max.100 mW
Largeur canalnon imposée
RéférencesDécisions ART N°xxx
Florent Dupont 21
Florent Dupont 22
Débit maximum d'un canal de transmission
•Si un signal quelconque est appliqué à l'entrée d'un filtre passe-bas ayant une bande passante W, le signal ainsi filtré peut être reconstitué avec un échantillonnage à 2W/s (Nyquist, Shannon)D max
= 2 W log2 V
en bit/s
si le signal comporte V niveaux significatifs (Valence).
La bande passante limite la rapidité de modulation.
Exemple: Pour un canal sans bruit dont la bande passante est de 3000 Hz qui ne peut transmettre qu'un signal binaire, D max = 6000 bit/s.
Florent Dupont 23
Bruit, capacité
•Bruits aléatoires dégradation de la transmission
•Quantité de bruit = rapport de la puissance du signal transmis à la puissance du bruit = rapport signal sur bruit, (SNR en anglais signal to noise ratio ou S/N).
•Pour un canal de transmission de bande passante W perturbé par du bruit dont le rapport signal sur bruit est S/N, la capacitéde transmission maximale C en bit/s vaut :
C = W log2 (1+PS /PN )
en bit/s
S/N est exprimé en dB en général, mais pas dans la formule !(S/N) dB
= 10 log10 (PS /PN ) PS /PN =10(S/N) dB/10 •Exemple: Pour un canal dont la bande passante est de 3000 Hz et un rapport S/N=30dB, (valeur typique du réseau téléphonique analogique), PS /PN =1000 => C = 30 000 bit/s.
Florent Dupont 24
Perturbations
•Perturbations l'information extraite du signal reçu peut conduire à des erreurs.
•Causes multiples, principale préoccupation dans les systèmes de télécommunication.
•Affaiblissement ou atténuation = perte d'énergie du signal pendant sa propagation
Atténuation (dB) = 10 log10 (P1 /P2 )
(-3 dB correspond à une perte de la moitié de la puissance)
•Affaiblissements différents suivant les harmoniques distorsions
En pratique affaiblissements d’amplitude négligeable jusqu’à fc appelée fréquence de coupure. Pour compenser cet affaiblissement et pour permettre des transmissions sur de longues distances amplificateurs ou répéteurs
•L'atténuation augmente avec la fréquence (passe-bas).
Florent Dupont 25
Perturbations
•La distorsion temporelle= toutes les composantes harmoniques d’un signal ne se propagent pas à la même vitesse.
•Un déphasagedu signal (distorsion de phase) constitue une perturbation. = (f) . Le déphasage dépend de la fréquence. Le temps de groupe est donné par :df ))f((d2 1)f(T Florent Dupont 26Bruit •Tout signal indésirable interprété par le récepteur et délivrant une information incohérente.
•Sources de bruit : –émetteur du signal ;
–media de transmission ;
–perturbation atmosphérique. •Bruit thermique= agitation thermique des électrons (source de bruit la plus courante)
•Diaphonie= influence mutuelle entre deux signaux utiles mais sur des conducteurs voisins.
Florent Dupont 27
Modulation / Démodulation •Transmission d’un signal à spectre étroit sur un support à large bande passante mauvaise utilisation du support techniques de modulationet de multiplexage
•Soit un signal périodique: y(t) = A sin (2ft + ) •Signal transporté sous forme d'une onde faisant varier une des caractéristiques physiques du support:
–différence de potentiel électrique;
–onde radioélectrique
–intensité lumineuse
Porteuse:p(t) = Ap cos (2fp t + p) •On fait ensuite subir des déformations ou modulations à cette porteuse pour distinguer les éléments du message.
Florent Dupont 28
Modulation •La modulation est la transformation d'un message à transmettre en un signal adapté à la transmission sur un support physique.
•Les objectifs de la modulation sont:
–une transposition dans un domaine de fréquences adapté au support de transmission;
–une meilleure protection du signal contre le bruit;
–une transmission simultanée de messages dans les bandes de fréquences adjacentes, pour une meilleure utilisation du support.
•Trois types de modulation de base existent, en faisant varier les trois paramètres de l'onde porteuse: Ap , fp , p. Florent Dupont 29
Modulation de fréquence
(FSK: Frequency Shift Keying)
•une valeur de fréquence une valeur du signal
Florent Dupont 30
Modulation de fréquence
•Porteuse sinusoïdale de fréquence F0 modulée par deux fréquences opposées +f0 et -f0 une fréquence est associée à chaque niveau logique.
1200 Hz1800 Hz2400 Hz
-600 Hz+600 Hz
Florent Dupont 31
Modulation de fréquence
•Liaison "full-duplex":
Émission / Réception simultanée on partage la bande passante du canal
une voie à l'émission F1 +/-f1 + une voie à la réception F2 +/-f2 1080 Hz1750 Hz
980 Hz1180 Hz1650 Hz
1850 Hz
Bande passante du canal
Florent Dupont 32
Modulation d'amplitude (ASK: Amplitude Shift Keying)
•une valeur d'amplitude une valeur du signal Florent Dupont 33
Modulation de phase (PSK: Phase Shift Keying)
•un déphasage une valeur du signal
•Avec des codes à plusieurs bits, on peut augmenter le débit sans changer la fréquence de modulation.
•Les vitesses de transmission sont plus élevées qu'en modulation FSK pour la même bande passante
Florent Dupont 34
Modulation de phase •Exemple: avis V22 du CCITT (1200 bauds) -phase codée sur 2 bits
Nombre de déphasages limité par le bruit pour retrouver le bon signal
Constellation V22
00 (90°)
01 (0°)
11 (270°)
10 (180°)
Florent Dupont 35
Modulation combinée
•Combiner plusieurs types de modulation parmi les trois types de modulation décrits auparavant.
Les normes actuelles utilisent des combinaisons des modulations de phase et d'amplitude.
Exemple: Modulation V29 à 7200 bits/s
•8 états de phase et 2 valeurs d'amplitude
Constellation V29
010 001100 111 011 000 110 101 33 2
Florent Dupont 36
Modulation combinée en quadrature
•Porteuses en quadrature : addition de deux porteuses de fréquence f0 en quadrature, on obtient une seule porteuse, toujours de fréquence f0 Florent Dupont 37
Modulation combinée en quadrature
Modulation de phase
4 états (2 bits)
Quadrature Amplitude Modulation
QAM 16
16 états(4 bits)0 00011011 101 0101 0000 11101110 Quadrant 01
Quadrant 00
Quadrant 11
Quadrant 1000 0001 011011 1011
Modulation des 2 porteuses
Florent Dupont 38
Modulation combinée en quadrature
Quadrature Amplitude Modulation
QAM 64
64 états (6 bits)
Quadrature Amplitude Modulation
QAM 128
128 états (7 bits)
Florent Dupont 39
Transmission en bande de base
•La transmission directe de la suite des symboles binaires n'est pas possible
le codage permet
d'adapter le signal au support de transmission.
•Un signal en bande de base ne subit pas de transposition en fréquence : ETCD = simple codeur
•Le signal occupe alors toute la bande passante disponible. Les principaux avantages sont la simplicité et le coût (pas de phase de modulation/démodulation).
•La suite des symboles transformés appartient à un alphabet fini = n x T, (nN, n>0).
Suite de symboles binaires de durée T
Codeur en bande de base
Suite de symboles transformés de durée Florent Dupont 40
Code NRZ et NRZI •Pour le codage NRZ (No Return to Zero), le signal binaire est transposé en tension pour éviter les valeurs nulles: 0 -a et 1+a
•Le spectre de puissance du signal NRZ est concentré au voisinage des basses fréquences
mauvaise transmission par le support
Utilisé dans les normes V24, RS232, RS421, RS422, RS485+a NRZ-a 10 +aNRZI -a
Répartition de la puissance en fonction de la fréquence
Florent Dupont 41
Code NRZI avec “bit stuffing” (NRZ Inverted with bit stuffing)
•Code du bus USB. •Le bus commence en ‘idle state’ (état haut à +A). Chaque fois qu’un bit est "1", il n'y a pas de changement de l'état de la ligne. Chaque fois qu'un bit est "0", la ligne change d'état (toggle). Lorsque six "1" consécutifs sont transmis, un "0" artificiel est inséré afin de garantir la récupération d'horloge.
Florent Dupont 42
Code biphasé (Manchester) •Introduction de transition au milieu de chaque intervalle, par exemple: 0 front montant et 1front descendant
•Signal transmis = signal binaire horloge
Rappel: = XOR = OU Exclusif
Une transition à chaque bit transposition hautes fréquences, transmission de l'horloge (embrouillage), synchronisation. •Spectre de puissance étalésur la bande de fréquence [0;2/Tm ].
•Ethernetsur câble coaxial, signal RDS(Radio Data System)
aba b000 011101 110+ a-a 10 Florent Dupont 43
Code biphasé différentiel
•On applique une transition systématique au milieu de chaque bit, pas de transition pour "1", une transition pour "0".
•Une transition à chaque bit transposition hautes fréquences, transmission de l'horloge (embrouillage), synchronisation. +a -a1 0
Florent Dupont 44
Code Miller •On applique une transition au milieu du bit "1", pas de transition au milieu du bit "0", une transition en fin de bit "0" si celui-ci est suivi d'un autre "0".
•Jamais 2 bits sans une transition transposition hautes fréquences
mais moins que code biphasé (Manchester ou différentiel)+ a-a 10 Florent Dupont 45
Code 4B/5B •Chaque groupe de 4 bits est transformé en un groupe de 5 bits avec pas plus de deux 0 de suite
111111101
111011100
110111011
110011010
101110111
101010110
100110011
100010010
011101111
011001110
000011110
000101001
010101011
010001010
001110101
001010100
Florent Dupont 46
Autres codes •Il existe bien d'autres variantes de codage en bande de base notamment avec des codages en symboles ternaires ou quaternaires
•Propriétés des codes en bande de base :
–Évitent les fréquences nulles (séquences de valeur constante)
–Ajoutent des transitions (embrouillage de l'horloge)
–S'adaptent au support de transmission
Florent Dupont 47
Multiplexage
•Objectif: optimiser l'usage des canaux de transmission pour un transit simultané du maximum d'informations partage(multiplexage) du support physique de transmission entre plusieurs signaux.
•Ces techniques peuvent se classer en deux grandes catégories: –multiplexage fréquentiel : MRF(Multiplexage par Répartition de Fréquence) ou FDM(Frequency Division Multiplexing)
–multiplexage temporel :
MRT(Multiplexage à Répartition dans le Temps) ou TDM(Time Division Multiplexing)
Florent Dupont 48
Multiplexage en fréquences
•Partage de la bande de fréquencesdisponible en plusieurs canaux (ou sous-bandes) plus étroits : en permanence chacun de ces canaux est affecté à un "utilisateur" exclusif CanauxFréquence
Filtrage
Démodulation
Modulation
Filtrage
Canal 1Canal 1
FiltrageModulation
Filtrage
Canal 2Canal 2
FiltrageModulation
Filtrage
Canal nCanal n
Ligne large bande
Démodulation
Démodulation1 n2 3
Ligne de transmission à large bande
Florent Dupont 49
Multiplexage fréquentiel de trois canaux téléphoniques
•3 liaisons téléphoniques multiplexées avec technique FDM.
•Des filtres appropriés limitent la bande passante à 3100 Hz par canal téléphonique. •Pour assurer un multiplexage correct, une bande de fréquences de 4000 Hz est attribuée à chaque canal afin de bien les séparer les uns des autres. 60646872KHz
Affaiblissement
3003400Hz60646872KHz
Bandes de fréquences originales
Bandes après transposition en fréquence
Bandes regroupées sur le canal multiplexé
Florent Dupont 50
Multiplexage temporel
chaque "utilisateur" a pendant un court instant et à tour de rôle, la totalité de la bande passante disponible (généralement réservé aux signaux numériques).Tampon Tampon
Canal 1Canal 1Tampon Tampon
Canal 2Canal 2Tampon Tampon
Canal nCanal nMUXMUX Trame ATrame BCanal1 Canal 2 Canal 3 Canal nTemps Voie compositeA1A2A3 ...
AnB1B2B3... BnC1... TTIT
Florent Dupont 51
Multiplexage temporel
•La vitesse de transmission des voies bas débit (d) est fonction de la vitesse de transmission de la ligne (D) et du nombre de voies n d=D/n
•La période Tdes trames est fonction du nombre de voies et de l'intervalle de temps élémentaire IT.
T= n x IT
Florent Dupont 52
Modulation par impulsions codées (MIC)
Multiplexage temporel pour les transmissions téléphoniques.
•échantillonnage des signaux analogiques de chacune des voies;
•quantification et codage des échantillons multiplexés pour obtenir un signal numérique. •multiplexage temporel des échantillons des différentes voies;
Codage du signal analogique
Échantillonnage
Te: période d'échantillonnaget t7 65 43 21 0
5 = %101 6 = %1105 = %1013 = %011
Amplitude
Quantification
Florent Dupont 53
Modulation par impulsions codées (MIC)
•Les échantillons sont ensuite multiplexés pour former un ensemble de trames. Multiplexage temporel des échantillons de trois voies
101 | 010 | 110 | 110 | 010 | 110
Trame 1
Trame 2
Florent Dupont 54
Multiplexage temporel statistique
•Multiplexage temporel simple : tranches de temps pas toujours utilisées des bits ou des caractères de remplissage sont insérés.
•Multiplexage temporel statistique ou asynchrone (ATDM: Asynchronous Time Division Multiplexing) •Allocation dynamique des tranches de temps aux seules voies qui ont des données à transmettre à un instant donné.
permet de raccorder plusieurs équipements sur une seule ligne, même si le débit cumulé de chaque voie est supérieur au débit maximum de la ligne.
Lemultiplexeurintègreunmicroprocesseuretdesmémoirestampon:
ilpermetdesdébitsetdesparamètresdetransmissiondifférents
surchaquevoieousous-canaletàchaqueextrémité.
Florent Dupont 55
Multiplexage temporel statistique
•Le multiplexeur :
–détecte les tampons non vides,
–prélève les données mémorisées, –supprime les bits non significatifs dans le cas d'une transmission asynchrone (start, stop, parité),
–comprime éventuellement les données et les insère dans les trames de la voie composite.d1 d2d5 Voie 1
Voie 2
Voie 3
Voie 4
Voie 5
Tampons à
l'instant tMUX |||d1|d2|d5|||MUX Tramed1 d2d5 Voie 1
Voie 2
Voie 3
Voie 4
Voie 5
Tampons à
l'instantt+t
Florent Dupont 56
Multiplexage en longueur d'onde WDM (Wavelength Division Multiplexing)
proche du multiplexage fréquentiel •Entrée : 2 fibres : flux lumineux d'énergie et de bande de fréquences différentes
Multiplexage WDM complètement passif très haute fiabilité.
•Fibre W 25000 GHZ
•un signal: qq GHz (limite = pb de conversion lumière/électricité)
Fibre n°1
Fibre n°2
Fibre n°3
Fibre n°4
Prismes (ou systèmes à diffraction)
Florent Dupont 57
2. Théorie de l'information
•Premières tentatives de définition de mesure de l'information 1920
•Théorie de l'information : à partir de 1948, travaux de Shannon
•Théorie de l'information : discipline fondamentale qui s'applique dans le domaine des communications.
–déterminer les limites imposées par les lois de la nature lorsqu'on doit stocker ou transmettre le contenu d'une source (d'information),
–proposer des dispositifs permettant d'atteindre ou d'approcher ces limites.
–La théorie de l'information ne cesse de se développer car les exigences actuelles s'orientent vers une augmentation constante de l'information à stocker ou à transmettre.
Florent Dupont 58
Théorie de l'information
Compression du contenu de la source d'information nécessaire.
Peut s'envisager sous deux formes :
–sans perte d'information;
–avec perte d'information.
Florent Dupont 59
Représentation du schéma d'une communication
•Le codage de source consiste à éliminer les redondances de la source afin d'en réduire le débit binaire.
•Le codage de canal a un rôle de protection contre les erreurs (dues à la transmission sur le canal) qui est assuré en ajoutant de la redondance (codes correcteurs d'erreurs).
•Les points de vue codage de source et codage de canal sont donc fondamentalement différents.
SourceCodage sourceCodage canal
Mots source
restitués
Décodage source
Décodage canalC AN AL Florent Dupont 60
Définition de l'«information»
•Incertitude d’un événement ou self-information ou quantité d’information.
•Une informationest un élément de connaissance qui peut être conservé (mis en mémoire), traité (traitement de l’information) ou transmis.
•La difficulté rencontrée pour définir la quantité d’information relative à un événement est liée au caractère subjectifde l'information effectivement apportée par la réalisation de cet événement.
•La quantité d’informationest relative à un contenu statistique,
plus grande si on ne s'attend pas à ce que l'évènement se réalise.
Florent Dupont 61
Définition
•Soit un événement E, une probabilité d’apparition p(E), la quantité d’information I(E)liée à l’apparition de E
s’exprime :
I(E) = -log [P(E)]
•Propriétés:
–I(E)est d’autant plus grande que P(E)est petite;
–Si E est toujours réalisé I(E)=0;
–Si Eest très rare, P(E)est proche de 0, I(E)tend vers l’infini;
–P(E) 1doncI(E) 0.
•Logarithme –népérien pour les signaux continus : –à base 2 pour les signaux discrets (l’unité est le bit, abréviation de binary unit).
Florent Dupont 62
Exemples
•Un événement qui a une chance sur 2 de se produire conduit à une quantité d’information de -log2 (1/2) = 1 bit
•Une source peut délivrer 8 événements équiprobables : Itotal = -8*log2 (1/8) = 24 bits
•I(E)peut être interprétée :
-a priori,
par l'incertitude qui règne sur la réalisation de E;
-a posteriori,
par l'information apportée par la réalisation de E.
Florent Dupont 63
Information mutuelle de 2 évènements
•L'information apportée par F sur E est la diminution de l'incertitude sur E lorsque F est réalisé.
•Information mutuelle
I(E;F)= IFE = I(E) -I(E / F) = IEF car E et F jouent le même rôle.
Démonstration :IFE = -log[P(E)]+log[P(E/F)]
= -log[P(E)]+log[P(EF)/P(F)]
= -log[P(EF)/ P(E)P(F)]= IEF Florent Dupont 64
Information mutuelle de 2 évène