[PDF] Théorie de linformation - Chap 1: Codage Source

View - Download Théorie de linformation - Chap 1: Codage Source

Previous PDF

Next PDF

Théorie de l"information

Chap 1: Codage Source

Rhouma Rhouma

https://sites.google.com/site/rhoouma École Supérieure d"Économie Électronique

Avril 2015

1/55 Plan

1Problématique de la Communications

2Mesure de l"information et Entropie

3Codes de longueurs fixes

4Codes de longueurs variables, codes préfixes

5Algorithme de Huffman

6Algorithme de Fano-Shannon

7Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8Code par répétition

2/55

Problématique de la Communications

Plan

1Problématique de la Communications

2Mesure de l"information et Entropie

3Codes de longueurs fixes

4Codes de longueurs variables, codes préfixes

5Algorithme de Huffman

6Algorithme de Fano-Shannon

7Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8Code par répétition

3/55

Problématique de la Communications

Communication Analogique vs Numérique

Analogique : communique à travers une forme d"onde continue (ex: voltage d"un micro), via modulation d"amplitude (AM) ou modulation de fréquence (FM),...utilise l"electronique analogique la fidélité à la forme d"onde Numérique: communique à travers un message formé par des

symboles d"une source d"alphabet discretegénéralement codé sous forme d"autres séquences de symboles

adaptés au canal de transmission (ex: 0 et 1)utilise la communication analogique pour traverser le canal

fidélité au message approprié quant à la minimisation de l"energie, transmission du big data, storage, débruitage, immunité contre les erreurs,... 4/55

Problématique de la Communications

Syllabus

Notion de l"information et d"entropie: mesures et significations compression de données bruit, erreurs, détection d"erreur, correction d"erreur 5/55

Problématique de la Communications

Samuel Morse

1832: a inventé la télégraphie éléctrique: composants et

protocoles surtout le Code Morse jusqu"à 1857: la telegraphie a été vite adopté via le cable trans-atlantique (16 heures pour transmettre un message de 98 mots)1858, 1865, 1866: plusieurs amélioration sur le même cable: 8 mots/minute1861: le trans-continental -> the pony express

1902: le Trans-pacific

6/55

Problématique de la Communications

Pendant 100 ans après l"invention de Morse

1876 : Bell invente le telephone

1901: Marconi réussi à mettre au point la télégraphie sans fil

1906: Fessenden met au point la radio AM

1933: Armstrong met au point la radio FM

1936 : Diffusion television par BBC (British Broadcasting Channel)

Le laboratoire Bell continue les inventions avec des chercheurs comme Nyquist, Bode, Hartley,.. 7/55

Mesure de l"information et Entropie

Plan

1Problématique de la Communications

2Mesure de l"information et Entropie

3Codes de longueurs fixes

4Codes de longueurs variables, codes préfixes

5Algorithme de Huffman

6Algorithme de Fano-Shannon

7Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8Code par répétition

8/55

Mesure de l"information et Entropie

Claude Shannon

1937: finit son mastère (electrique) au MIT intitulé : "A

symbolic analysis of relay and switching circuits"il a introduit l"application de l"algebre booleene dans les

circuits logiques !

Most impor tantMaster thesis in the

century !1940: these (math) au MIT : "an algebra to theoretical genetics" pour analyser la dynamique de population1940: il a joint le labo Bell

1945/1949: A mathematical theory of cryptography

1948: A mathematical theory of communication

9/55

Mesure de l"information et Entropie

Mesure de l"information

Définition de Shannon:

Inf ormationis the resolution of uncer tainty

La quantité d"information d"un symbole est d"autant plus grande que celui-ci est peu probable.La quantité d"information de deux symboles successifs est la somme de leurs quantités

d"information.La quantité d"information notée I est une fonction qui doit ainsi avoir les propriétés

suivantes:1I(pk)est une fonction continue de la probabilitépk.2I(pk)"sipk#) I(pk)est une fonction décroissante depk3I(pket pj) =I(pk) +I(pj)4Un symbole certain possède une quantité d"information nulle :

I(pk=1) =0.une fonction qui vérifie les conditions 1, 3 et 4 estlog(pk). Pour obtenir la propriété 2 il

suffit de prendrelog(1p k) =log(pk)la quantité d"information d"un symbolexkde probpkest donc :

I(xk) =log(1p

k) =log(pk)unité:bitoushannonpourlog2.natpourLn.ditpourlog10.tritpourlog3 10/55

Mesure de l"information et Entropie

Entropie

Soit S une source de symboles discrètes1,s2, ...,sNde probp1, p

2, ...,pNL"entropie H(S) est la quantité d"information moyenne reçu de S:

H(S) =NX

k=1p kI(sk) =NX k=1p klog2(1p k)unité: bit/symbole ou Shannon/sybmole

Si tous les symboles sont equiprobables:

H(S) =log2N

et donc

N=2H(S)

=)C"est la valeur maximale que l"entropie peut atteindre 11/55

Mesure de l"information et Entropie

Exemple: Source binaire

Less1=0 sont de probabilité pless2=1 sont de probabilité 1-pdonc H(S) =plog2p(1p)log2(1p)le maximum est atteint si les 1 et les 0 sont équiprobables :H(S)max=1 si p=1p=0:512/55

Mesure de l"information et Entropie

Quel signifiance de l"entropie pour le codage binaire Sip=1=1024. une probabilité très petite pour avoir un 0 dans

1024 essais ! alors

H(S) =11024

log2(1024) +10231024 log2(10241023 ) =0:0112bitson a 0.0112 bits d"incertitude d"information par essai en moyenne. donc si on utilise 1024 digit binaire (Code= 0 ou 1) pour coder le résultat de 1024 essais semble être perte de ressources (1 digit binaire par essai).on peut arriver à coder ce message de 1024 symboles à une

moyenne de 0.0112 digit binaire/essai !!par confusion !!! ledigit binaireest appelébitLe Mapping binaire : Mapping des symboles de la source à des

digits binaires. 13/55

Mesure de l"information et Entropie

Signifiance de l"entropie

L"entropie

nous renseigne sur la quantité d"inf ormationmo yenne (en bits) qui doit être fournie pour résoudre l"incertitude sur le résultat d"un évènement (essai). Elle constitue donc la limite inférieure sur le nombre de digit binaire, en moyenne, qui doit être

donné pour coder nos symboles (qui constitue le message)si on envoie un nombre inférieur de digit binaire en moyenne, le

récepteur va avoir une incertitude pour décoder correctement le messagesi on envoie un nombre supérieur de digit binaire en moyenne, on

perd de ressources puisqu"on émet plus qu"on a besoin.atteindre la limite inférieure d"entropie lors du codage estla règle

quotesdbs_dbs3.pdfusesText_6

[PDF] codage de l'information sensorielle

[PDF] codage de l'information tronc commun

[PDF] codage informatique des couleurs

[PDF] codage informatique exemple

[PDF] codage informatique formation

[PDF] codage informatique pdf

[PDF] codage informatique pour les nuls

[PDF] codage informatique salaire

[PDF] code avantage france attelage

[PDF] code bert

[PDF] code général des impôts 2020 maroc pdf

[PDF] code in linguistics

[PDF] code postal 99 étranger

[PDF] code postal bouskoura

[PDF] code postal casablanca bournazel