1. THEORIE DE L INFORMATION · Vahid Meghdadi 2008/2009 4 Exercice : Calculer l'entropie d'une source qui émet 3 symboles A, B et C avec des probabilités 1/2, 1/4 et 1/4. Exercice,

Théorie de l'information 3ème année ENSIL

Vahid Meghdadi 2008/2009 1

1. THEORIE DE L ' INFORMATION 1

1.1. Introduction

La théorie de l'information essai de répondre à deux questions essentielles sur l'analyse et la synthèse des systèmes de télécommunication : - Supposons un générateur d'informations, quel est le débit de l'information en sortie du

générateur ? - Supposons un canal de transmission bruité, quel est le débit maximal de transfert de

l'information à travers ce canal ? Dans ces deux questions, il existe des mots à définir. D'abord, nous distinguons deux types de source : analogique et discrète. Un microphone est une source d'informations analogique produisant un signal analogique en amplitude et en temps. Une source d'information discrète produit des symboles (ou des lettres comme un clavier). La sortie est une chaîne (ou une séquence) de symboles. La sortie d'une source d'information analogique peut être transformé en symboles discrets moyennant un échantillonnage et une quantification. Dans le cours de la théorie de l'information, nous traitons les sources discrètes à cause de leur importance en télécommunication numérique. Une source discrète de l'information dispose d'un ensemble (souvent appelé alphabet) des symboles (ou des lettres). Elle choisit un symbole dans cet ensemble (suivant une règle connue par la source) et l'envoie en sortie. Nous avons finalement une séquence des symboles à des instants discrets. Un dé par exemple, choisit le symbole à sortir dans l'ensemble de {1, …, 6}. Une séquence possible peut être {1,5,4,1,2,4,1,1}. La question essentielle est la suivante : quel est le montant de l'information émise par cette source ? Et ensuite, quelle unité de mesure choisit-on pour l'information ? La théorie de l'information est basée principalement sur les travaux de Claud Shannon en 1948. Il établit la limite théorique de performance pour les systèmes de télécommunication. Il démontre qu'on peut atteindre cette limite "mythique" utilisant des codes correcteurs d'erreur performants. Il a fallu des dizaines d'années pour approcher à ces limites fixées il y a presque un demi-siècle. Ce n'est qu'en 1993 que nous avons pu nous approcher de cette limite grâce à l'invention de turbo code. Nous essayons dans le cadre de ce cours, de présenter les principes de la théorie de l'information. La deuxième partie de cours est destiné à présenter le codage de source et de canal pour maximiser le débit de l'information transmis sur un canal donné.

1 Références : K. Sam Shanmugam, "Digital and Analog Communication Systems", John Wiley & sons 1979 Simon Haykin, "Communication systems", 3rd edition, John Wiley & sons, 1994



1.2. Mesure de l'information

1.2.1. Information contenue dans un message

Une source d'informations produit des messages. Pendant un message, la source sélectionne de manière aléatoire (aléatoire vu du système de transmission) un symbole dans l'ensemble des symboles qu'elle a à sa disposition. On peut considérer par exemple la météo comme une source d'informations. Imaginez qu'elle essaye de prévoir le temps de demain à Brest. L'ensemble des symboles contient les mots comme "pluvieux", "ensoleillé", nuageux", "avec éclairci", …. Imaginez de plus que c'est l'automne et demain c'est un dimanche! Alors lesquelles de ces informations ci-dessous porte plus d'information : 1. Chaud et ensoleillé 2. Pluvieux 3. Il neigera Il est clair que ces trois possibilités ne portent pas le même montant d'informations. La deuxième n'a que très peu d'information car "c'est normal" qu'il pleut en automne à Brest. La première et la troisième phrases par contre, contiennent plus d'informations car leur probabilité de réaliser est peu. C'est à dire qu'il y a une relation directe entre la probabilité de l'occurrence et le montant de l'information. En théorie de l'information, notre interprétation sur chaque message est indépendant de la quantité de l'information générée par la source! Par exemple si on vous dit les numéros gagnant de Loto de la semaine prochaine, la quantité de l'information est indépendante du montant à gagner. Nous essayons maintenant d'inventer une relation mathématique pour quantifier l'information. Supposons qu'une source d'informations émet un des q messages possibles m1, m2, …, mq. avec les probabilités de réalisation p1, p2, …, pq. (p1+p2+…+pq=1). Par intuition, on sait que l'information portée par kième message ( I(mk) ) doit être inversement proportionnelle à pk. L'autre critère par intuition est que quand pk tend vers 1, la quantité de l'information tend vers zéro. On sait aussi que I(mk) est toujours positif. C'est à dire :

I(mk) > I(mj) si pk < pj

I(mk) � 0 quand pk � 1

I(mk) >0 quand 0<pk<1

Avant de trouver une fonction satisfaisant toutes ces contraintes, nous allons imposer une autre. Si nous avons deux messages indépendants, l'information contenue dans les deux est la somme de l'information de chacun. Cette nouvelle contrainte est parfaitement justifiée par l'intuition. Une fonction logarithmique satisfait toutes les requis ci-dessus. Ainsi nous définissons le montant de l'information contenue dans un message qui se produit avec une possibilité pk comme suit :

I(mk)=log(1/pk)



L'unité de mesure dépend de la base de la fonction logarithme. Si on prend la base 2, l'unité sera "bit" (pour Binary digIT). Exemple :

Une source met en sortie un des 5 symboles possibles dans chaque intervalle de symbole. La probabilité de réalisation de chaque symbole est donnée ci-dessous :

P1=1/2, P2=1/4, P3=1/8, P4=1/16, P5=1/16 Calculer le contenu de l'information concernant chaque message (symbole).

Solution : I(m1)=log(1/(1/2))=1 bit I(m2)=log(1/(1/4))=2 bits I(m3)=log(1/(1/8))=3 bits I(m4)=log(1/(1/16))=4 bits I(m5)=log(1/(1/16))=4 bits

1.2.2. Entropie

Les messages produits par des sources d'informations sont des séquences de symboles. Du point de vue des systèmes de télécommunication, un message est composé des symboles individuels. Nous avons vu que l'information portée par un symbole peut varier suivant sa probabilité de l'occurrence. Nous sommes donc amenés à définir l'information moyenne portée par chaque symbole dans un message. L'autre point est que la dépendance des symboles dans un message peut changer la valeur totale de l'information. Par exemple, on sait que dans un télex, le "Q" et souvent suivi par un "U". Alors, les symboles individuels ne sont pas indépendants. Dans ce cas, l'information totale n'est plus égale à la somme des informations de chaque symbole. Imaginons que nous avons une source qui émet un des M symboles possibles s1, s2, …, sM, et de manière indépendante. Les probabilités correspondant sont p1, p2, …, pM. Dans un message long contenant N symboles nous avons en moyenne Np1 fois le symbole s1, Np2 fois le symbole s2 et ainsi de suite. Le montant de l'information concernant le symbole si est donc Npilog2(1/pi). Le contenu total de l'information dans le message est égal à :

bitspNppNpIM

iii

M

iiitotale ∑∑

==

−==1

21

2 log)/1(log

L'information moyenne par symbole s'obtient en divisant l'information totale du message par le nombre de symboles :

symbolebitsppN

IH

M

iii

totale /)/1(log1

2∑=

==

L'information moyenne par symbole s'appelle l'entropie de la source. Ceci veut dire que "normalement nous recevons H bits d'information par symbole dans un message long".



Exercice : Calculer l'entropie d'une source qui émet 3 symboles A, B et C avec des probabilités 1/2, 1/4 et 1/4.

Exercice, entropie d'une source binaire sans mémoire :

Une source émet soit un soit zéro avec des probabilités P1=P et P0=(1-P). - Calculer l'entropie de cette source. - Tracer l'entropie de la source en fonction de P. Pour quelle valeur de P cette

entropie est maximale ? Quelle est cette valeur maximale ? remarque : En général, pour une source émettant ses symboles choisis dans un ensemble de M élément, l'entropie est maximale si tous les symboles sont équiprobables et indépendants.

On définit le débit d'informations, la somme des informations émises par seconde. Avec cette définition pour une source à entropie H et le débit de rs symboles par seconde, le débit de l'information émise par cette source est :

R=rsH bits/sec Exercice :

Une source d'information émet un des 5 symboles possibles toutes les milli-secondes. Calculer l'entropie de la source et le débit de l'information.

1.2.3. Modèle statistique de Markoff pour les sources d'informations

Nous supposons toujours qu'une source d'informations émet un symbole (choisi dans son alphabet) toutes les Ts secondes. La source va émettre des symboles suivant une probabilité qui dépend des symboles précédents et aussi du symbole en question. Une telle source appelée la source de Markoff peut être exprimée comme suit : 1. Juste avant de générer un nouveau symbole, la source est dans un des n états possibles. A

chaque émission d'un symbole, la source change son état disons de i à j. La probabilité de transmission est égale à pij. Cette probabilité dépend uniquement de l'état initial i et de l'état final j. De plus cette probabilité reste constante dans le temps.

2. En changeant l'état, la source émet un symbole. Ce symbole dépend uniquement de l'état initial et la transition i � j.

3. Soit s1, s2, …, sM l'alphabet et X1, X2, …, Xk, … la séquence des variables aléatoires représentant les symboles émis aux instants 1, 2, …, k, … . La probabilité que le symbole Xk soit égal à sq dépend des symboles précédemment émis. C'est à dire que sq est émis avec la probabilité conditionnelle ci-dessous:

P(Xk=sq|X1, X2, …, Xk-1)

4. L'influence de la séquence X1 à Xk-1 peut être résumée dans l'état dans lequel la source se

trouve juste avant l'envoi du symbole Xk, à savoir Sk. Alors, la probabilité ci-dessus peut être écrite :

P(Xk=sq|X1, X2, …, Xk-1)=P(Xk=sq|Sk)



Ceci veut dire que toute l'histoire de la source se résume dans l'état dans lequel elle se trouve.

5. Pour le premier symbole la source est dans un des n états possibles avec les probabilités

P1(1), P2(1), …, Pn(1). Nous avons donc

1)1(1

=∑=

n

iiP

6. Si la probabilité que le système (la source) soit dans l'état j au début du kième intervalle est

Pj(k), on a :

∑=

=+n

iijij pkPkP

1

)()1(

Nous pouvons présenter cette expression sous forme matricielle. Supposons P(k) un vecteur colonne avec les éléments Pi(k) et Φ une matrice n×n avec (i,j)ième élément égal à Pij . On a :

)()1( kk TPΦP =+ La matrice Φ s'appelle la matrice de probabilité de transition pour un processus Markoff. La processus est stationnaire si )()( kk TPΦP = pour k=1.

Les sources d'informations dont la sortie peut être modélisée avec un processus stationnaire Markoff, s'appellent les source stationnaire de Markoff. Les sources Markoff sont généralement présentées par un graphe qui montre les états, les transitions et les probabilités correspondant. Exercice :

Pour le schéma ci-dessous - calculer la matrice des transitions - calculer la probabilité que la source émet le message "AB"



A partir du diagramme ci-dessus, on peut dessiner le diagramme arborescent équivalant qui explose si on veut considérer des messages un peu longs.

1.2.4. Entropie d'une source Markoff

Considérons une source discrète et stationnaire de Markoff. De plus, supposons que cette source est ergodique (les moyennes statistiques peuvent être remplacées par des moyennes temporelles). Nous avons donc Pi(k)=Pi(k+j) pour tout k et j. L'entropie de la source est définie par la moyenne pondérée des entropies de tous les états. Si l'entropie des symboles émis dans l'état i est présentée par Hi l'entropie totale de la source est donnée par :

symbolebitsHPHn

iii /

1∑

=

=

où Pi est la probabilité que le système soit dans l'état i. De l'autre côté, Hi est calculé comme suit :



symbolebitsp

pHn

j ijiji /

1log

12∑

=

=

Le débit de l'information émise par la source sera donc :

R=rsH bits/seconde où rs est le nombre de transition par seconde ou de manière équivalente le débit symbole de la source. Exercice :

Considérons la source d'information dont le graphe est donné ci-dessous. - Calculer l'entropie de la source H - Dessiner le diagramme arborescent jusqu'à trois symboles - Calculer la valeur moyenne de l'information contenue dans chaque symbole dans

un message de un, deux et trois symboles.

Dans l'exercice ci-dessus, on constate que le contenue de l'information portée par un symbole diminue pour les messages plus longs et en limite, il tend vers H. Cette constatation est en général vrai pour les sources qui émettent des symboles dépendants. Le théorème ci-dessous formalise cette problématique. Théorème:

Prenons des messages mi de taille N issues d'une source Markoff. Sachant que l'information contenue dans cette séquence est égale à )(log2 imp− , l'information

moyenne par symbole est donc :

∑−=i

iiN mpmpN

G )(log)(1

2

La somme est effectuée sur tous les messages de taille N symboles. Il est montré que GN est une fonction monotone décroissante de N. De plus :

symbolebitsHGNN

/lim =∞→

Une des conséquences importante est que "le nombre moyen de bits par symbole nécessaires pour présenter un message diminue quand la taille de message augmente" (réfléchir sur la signification de cette phrase).



1.3. Codage de source

On entend par le codage de source le processus par lequel la sortie d'une source de l'information est transformée en séquence binaire. En entrée du codeur de source, nous avons une séquence en général binaire qui comporte une quantité de l’information. En sortie nous avons une autre séquence binaire qui représente plus au moins les mêmes informations, mais présenté autrement. Le but, dans la plupart des cas, est de diminuer le débit (ou la taille de la séquence). C’est la raison pour laquelle le codage de source est aussi appelé la compression de donnée.

Par fois, le but est de crypter les informations pour les sécuriser. Dans ce cas, il se peut que le débit binaire augmente. Ce cours aborde uniquement le premier aspect et non pas le cryptage. Dans le cadre de la compression de donnée, la tâche à remplir par le codeur est de présenter les mêmes informations (ou presque) avec des messages les plus courts possibles. Nous fixons deux conditions suivantes pour un codeur de source :

- le message généré en sortie du codeur est en binaire - les informations codées peuvent être décodées de manière plus au moins exacte par

un algorithme de décodage (reconstruction parfaite) La question essentielle est alors, jusqu'où peut-on compresser le message fourni par une source d'information. Cette question est abordée en partie par la théorie de l’information2. La figure ci-dessous donne une aperçue des techniques de codage compresseur. Le codage de source peut se diviser en deux catégories différents :

- Compression sans perte de l'information (ex. codage de Shannon, Huffman, LZW donnant lieu aux codages PKZIP, GIF et TIFF, etc.) où aucune information de la source n'est perdue dans le processus de codage. Le codage est réversible.

- Compression avec perte de l'information (ex. codage JPEG, MPEG, Wavelet, transform coding, sub-band coding…) où une partie de l'information jugée peu importante est perdue.

2 On dit « en partie » car le cas où on se permet de supprimer les informations peu importants dépend du jugement sur l’importance des informations ; et ceci par des moyens indépendant de la théorie de l’information.



Dans ce cours, nous présentons les bases nécessaires à la compréhension de fonctionnement des codeurs compresseurs en se concentrant uniquement sur les codeurs sans perte. Pour les codeurs de source avec perte, il faut étudier la nature de l’information à transmettre. Par exemple pour un signal audio, les fréquences autour d’un kilo hertz sont codées avec plus de précision que les signaux à très basse fréquence ou à très haute fréquence où l’oreille est moins sensible. Les codeurs sans perte se divise en trois catégories : - ad hoc où on essaye de diminuer la taille des fichiers (messages) avec des méthodes

"improvistes" - codage d'entropie où les propriétés statistiques de la source sont exploitées pour

compresser les messages émis - "codage dictionnaire" où les séquences d'un fichier sont répertoriées pour les remplacer

par une autre séquence en moyenne plus courtes. Le codeur dont on parle dans le cadre de notre cours, reçoit en entrée une séquence des symboles (binaire ou non binaire). En sortie, il génère une séquence binaire. Par exemple, s'il travaille sur des blocs de taille N symboles en entrée, il génère une séquence binaire de taille M en sortie. Sachant que pour les séquences de taille N, la quantité de l'information portée est de NGN bits. Chaque message est alors codé par une séquence binaire de taille moyenne supérieure ou égale à NGN. Utilisant le théorème du paragraphe 1.2.4, le débit binaire en sortie du codeur diminue en prenant des blocs en entrée de plus en plus grands. La performance d'un codeur de source est quantifiée comme le rapport du débit de l'information en entrée sur le débit binaire en sortie. Il existe un grand nombre de codeur de source chacun adapté à la nature des informations à coder. Par exemple pour une image animée, la quantité de l’information de la différence entre deux images consécutives est beaucoup moins importante que les images elles mêmes. Il est peut être très avantageux de ne coder que la différence des images et non pas les images elles mêmes. Nous n'allons pas développer les différentes méthodes de codage, mais nous nous contentons de présenter uniquement les principes par des exemples simples et classiques.



1.3.1. Algorithme de Shannon

D'abord, nous allons formuler la problématique :

L'entrée du codeur est un des q messages possibles chacun contient N symboles. Les probabilités correspondants sont p1, p2, …, pq. Le but est de remplacer (coder) le message mi par un code binaire unique ci (i=1,2,…,q) et que le nombre moyen de bits par symbole soit le plus proche possible à GN. C'est à dire :

∑∑==

→=q

iii

q

iiiN pp

Npn

NH

12

1

)/1(log11ˆ

où ni est le nombre de bits pour le code ci et NHN ˆ représente la taille moyenne des

mots du code. La solution présentée par Shannon est la suivante :

Nous rangeons d'abord les messages m1, m2, …, mq tels que qppp ≥≥≥ ⋯21 .

Prenons ∑−

==

1

1

i

kki pF avec F1=0 et que ni est un entier tel que :

)/1(log1)/1(log 22 iii pnp +<≤

Ainsi, le mot du code pour le message mi est le développement en binaire de Fi jusqu'à ni bits.

Avec cet algorithme, les propriétés ci-dessous en déduit :

1. Les messages plus probables sont codés par des codes courts et les messages peu probables par des codes longs. (pourquoi ?)

2. Tous les mots de codes sont distincts. 3. Le nombre moyen des bits par symbole en sortie est limité par : (pourquoi)

NGHG NNN /1ˆ +<≤

Par conséquence, quand ∞→N , HGN → et HH N →ˆ . La performance du codeur

est quantifiée par l'efficacité du code définie par

NHHe ˆ/=

Exercice :

Considérons le diagramme d'état ci-dessous. Suivre l'algorithme de Shannon pour trouver le mot de code concernant les messages de taille 1, 2 et 3. A chaque fois, calculer l'efficacité du code.



Solution : D'abord N=1. Les messages sont "A", "B" et "C". nous avons : P(A)=P(A|S=1)*p(S=1)=3/4*1/2=3/8 P(B)=P(B|S=2)*P(S=2)=3/4*1/2=3/8 P(C)=P(C|S=1)*P(S=1)+ P(C|S=2)*P(S=2)=1/4*1/2+1/4*1/2=2/8

Message pi ni Fi Développement

binaire ci

A B C

3/8 3/8 2/8

2 2 2

0 3/8 6/8

0.00000 0.01100 0.11000

00 01 11

1H =2 bits/symbole e=40.56% Pour N=2, les message sont "AA", "AC", "BB", "BC", "CA", "CB", "CC".


binaire ci

AA BB AC CB BC CA CC

9/32 9/32 3/32 3/32 3/32 3/32 2/32

2 2 4 4 4 4 4

0 9/32 18/32 21/32 24/32 27/32 30/32

0.0000000 0.0100100 0.1001000 0.1010100 0.1100000 0.1101100 0.1111000

00 01

1001 1010 1100 1101 1111

2H =1/2[2*(2*9/32)+4*(4*3/32)+4*2/32]=23/16=1.44 , e=56.34% Pour N=3 nous avons :


binaire ci

AAA BBB CAA CBB BCA BBC AAC ACB CBC CAC CCB CCA BCC ACC CCC

27/128 27/128 9/128 9/128 9/128 9/128 9/128 9/128 3/128 3/128 3/128 3/128 3/128 3/128 2/128

3 3 4 4 4 4 4 4 6 6 6 6 6 6 6

0 27/128 54/128 63/128 72/128 81/128 90/128 99/128 108/128 111/128 114/128 117/128 120/128 123/128 126/128

0.0000000 0.0011011 0.0110110 0.0111111 0.1001000 0.1010001 0.1011010 0.1100011 0.1101100 0.1101111 0.1110010 0.1110101 0.1111000 0.1111011 0.1111110

000 001 0110 0111 1001 1010 1011 1100

110110 110111 111001 111010 111100 111101 111111



3H =1/3*[2*3*27/128+6*4*9/128+6*6*3/128+6*2/128]=166/128=1.3

e=62.40%

Exercice : Comment la séquence ACBBCAAACBBB est codée par chacune des méthodes ci-dessus ?

1.3.2. Algorithme de Huffman

Référence : chapitre 2.3 du livre « coding techniques, an introduction to compression and error control » par Graham Wade, 2000.

1.3.3. Codage arithmétique

Un des défaut du codage Huffman est qu'il n'est optimal quand la probabilité d'occurrence d'un symbole est prépondérante. Exemple : Supposons une source qui émet un des quatre symboles ci-dessous avec les probabilités correspondantes : a1 : 0.9; a2 : 0.06; a3 : 0.02; a4 : 0.02; Avec la méthode Huffman, on obtient le code correspondant chaque symbole comme suit : a1 � 0; a2 � 10; a3 � 110; a4 � 111; Ce qui donne comme longueur moyenne :

symbitslapL jj /14.1)( ==∑

L'entropie de la source est :

symbitsapapH jj /6061.0)(log)( =−= ∑

Ce qui donne une efficacité de 53%. (très peu!)

En effet, le codage de Huffman est optimal avec une efficacité de 100% si jljap

−= 2)( . Si ce

n'est pas le cas, le nombre de bits optimal par symbole n'est plus entier, ce qui va causer une perte d'efficacité. Le codage arithmétique dans ce cas, donne une performance meilleure. Le principe du codeur est le suivant. Contrairement à l'algorithmes de Huffman qui associe à des symboles des motifs binaires dont la taille dépend de leur distribution, le codeur arithmétique traite un bloc de symbole en lui associant un unique nombre décimal rationnel. Chaque symbole est entré avec sa probabilité d’occurrence comprise entre 0 et 1, (en commencent par celui qui a la probabilité la plus élevée ), et le codage se traduit par l’affectation d’un nombre unique, à virgule flottante, compris entre 0 et 1, à un ensemble de symboles.



Décrivons le principe du codage et de décodage sur un exemple : Considérons le codage du message ATLAS. Les probabilités des caractères sont les suivante :

Caractère Probabilité A 1/10 L 2/10 S 1/10 T 1/10

Dans l’intervalle général de probabilité [0,1], chaque symbole se voit affecter un intervalle de probabilité (la manière d’affecter cet intervalle n’ayant pas d’importance)

Caractère Probabilité intervalle A 1/10 [0.1-0.2) L 2/10 [0.2-0.4) S 1/10 [0.4-0.5) T 1/10 [0.5-0.6)

Le codage s’effectue progressivement à partir de la première lettre du message. Puisque c’est A, le codage du message doit être compris entre 0,10 et 0,20. La deuxième lettre est T; dans le sous intervalle 0,10 à 0,20 , le codage sera compris entre 50 et 60 %. Autrement dit, à ce stade (AT) sera compris entre 0,10+(0,20-0,10)x0,50 et 0,10+(0,20-0,10)x0,60 , soit entre 0,15 et 0,16. Au niveau de la troisième lettre L, il doit être compris entre 0,15+(0,16-0,15)x0,20 et 0,15+(0,16-0,15)x0,40 soit entre 0,152 et 0,154 . En continuant, on arrive au tableau suivant :

Caractère successif

Limite inférieure

Limite supérieure

A 0.1 0.2 T 0.15 0.16 L 0.152 0.154 A 0.1522 0.1524 S 0.15228 0.1523

Le codage du message est constitué par la dernière limite inférieure, 0,15228. Le décodage s’effectuera de manière unique à partir de ce nombre, suivant le mécanisme inverse. Puisque 0,15228 est compris entre 0,1 et 0,2 la première lettre du message est A. On peut maintenant soustraire la limite inférieure correspondant à A, soit 0,10 ,ce qui donne : 0,05228 et diviser ce résultat par la longueur de l’intervalle correspondant à A, soit 0,10 ,ce qui donne : 0,5228. Ce nombre étant compris entre 0.5 et 0.6, la deuxième lettre est T. En continuant, on trouve dans l’ordre tous les symboles du message.

Nombre codé Limite Limite Symbole



inférieure supérieure 0,15228 0.1 0.2 A 0.5228 0.5 0.6 T 0.228 0.2 0.4 L 0.14 0.1 0.2 A 0.4 0.4 0.5 S

Cette technique se montre un peu plus lente que celle de Huffman mais elle présente des taux de compression.



1.4. Canaux de communication.

Il est possible de diviser un canal de transmission en un émetteur, un canal physique ou un média de transmission, et un récepteur. L’émetteur est composé d’un encodeur et d’un modulateur tandis que le récepteur est constitué d’un démodulateur et d’un décodeur. Le terme "canal de communication" porte différentes significations et interprétations qui dépendent de ses points terminaux et de sa fonctionnalité. Entre les points c et g du système montrés sur la Figure ci-dessous, nous avons un canal discret, souvent appelé canal de codage, qui accepte une séquence de symbole à son entrée et produit une séquence de symbole à sa sortie. Ce canal est complètement caractérisé par une série de probabilités de transition pij, où pij est la probabilité que l’on ait le jième symbole de l’alphabet en sortie du canal lorsque l’on a le ième symbole en entrée. Ces probabilités dépendront des paramètres du modulateur, du média de transmission, du bruit et du démodulateur.

Caractérisation d’un canal de communication binaire. Cependant, cette dépendance est transparente au concepteur du système qui s’occupe de la conception de l’encodeur et décodeur numérique. Le canal de communication entre les points d et f du système fournit la connexion électrique entre l’émetteur et le récepteur. L’entrée et la sortie sont des formes d’onde électriques analogiques. Cette portion de canal est souvent appelée canal de modulation ou continu. Les exemples les plus courants de canaux de communication analogiques sont les systèmes téléphoniques en bande de voix et large bande, les systèmes radio à haute fréquence et les troposcatter. Ces canaux sont sujets à plusieurs sortes de perturbations. Certaines sont dues aux variations de l’amplitude et de la réponse en fréquence du canal au sein de sa bande passante, d’autres aux variations des caractéristiques du canal comme les non linéarités et le temps passé dans le canal. Tout cela agit dans le canal modifiant ainsi le signal d’entrée de manière déterministe (bien que pas nécessairement connu). De plus, le canal peut aussi corrompre statistiquement le signal suite aux différents bruits additifs et multiplicatifs ainsi

Codeur de

canal Modulateur

Canal de Communication

Electrique ou

Média de transmission

Démodulateur Décodeur

de canal

Bruit

b c d e f g h

+

+

Canal de communication de données(discret)

Canal de Codage (discret)

Canal de Modulation (analogique)

Emetteur Canal Physique récepteur



que les fades (atténuation aléatoire qui change au sein du canal de transmission). Toutes ces perturbations introduisent des erreurs dans la transmission de donnée et limitent le taux maximum auquel les données peuvent être transmises au travers du canal. Dans les sections suivantes, nous développerons des modèles mathématiques simples pour les canaux de communication discrets ainsi que le concept de capacité d’un canal de communication discret. La capacité d’un canal est un des paramètres les plus importants d’un système de communication de donnée puisqu’il représente le taux maximum auquel des données peuvent être transmises entre deux points d’un système, avec arbitrairement, une faible probabilité d’erreur. Ensuite, nous traiterons des canaux discrets, puis du théorème de Shannon-Hartley qui définit la capacité de certains types de canaux continus.

1.5. Canaux de communication discrets

Le canal de communication entre les points c et g de la figure présentée au paragraphe précédent est discret par nature. Dans le cas général, l’entrée du canal est un symbole appartenant à un alphabet de M symboles. La sortie du canal est un symbole appartenant au même alphabet des M symboles d’entrée. Suite aux erreurs du canal, le symbole de sortie peut être différent du symbole d’entrée pendant quelques intervalles de symbole. Ces erreurs sont principalement dues au bruit dans la portion analogique du canal de communication. Le canal discret est complètement modélisé par une série de probabilité pti (i=1, 2, . . ., M) et pij (i, j=1,2, . . . .,M). pt

i est la probabilité d’avoir le ième symbole de l’alphabet en entrée du canal et pij est la

probabilité que le ième symbole est reçu comme le jième symbole de l’alphabet en sortie du canal. Les canaux conçus pour transmettre et recevoir un des M symboles possibles sont appelés canaux discrets M-aires (M>2). Dans le cas d’un alphabet binaire, nous pouvons statistiquement modéliser le canal numérique comme il est montré sur la figure ci-dessous. L’entrée du canal est une variable binaire X aléatoire et discrète et les deux nœuds situés à gauche du graphe représentent les valeurs 0 et 1 de la variable aléatoire X. La sortie du canal est aussi une variable aléatoire et binaire notée Y et les valeurs que cette variable peut prendre sont les nœuds situés à droite du graphe. 4 chemins relient les nœuds d’entrée aux nœuds de sortie. Le chemin supérieur du graphe représente une entrée 0 et une sortie correcte 0. Le chemin diagonal de 0 à 1 représente un bit d’entrée à 0 apparaissant incorrectement comme un 1 en sortie du canal suite au bruit. Les erreurs se produisent de manière aléatoire et il est possible de modéliser statistiquement l’occurrence des erreurs en assignant des probabilités aux chemins montrés à la figure. Afin de simplifier les analyses, nous supposerons que l’occurrence d’une erreur n’affecte pas le comportement d’un système pendant d’autres intervalles de bit ( i.e., nous supposerons que le canal est sans mémoire).



En posant ( ) tpXP 00 == , ( ) tpXP 11 == , ( ) rpYP 00 == , ( ) rpYP 11 == , on a les relations

suivantes : ( ) ( ) ( ) ( )0,11,0error ==+===≠== YXPYXPYXPPeP

( ) ( ) ( ) ( )1*100*01 ===+==== XPXYPXPXYP

ou

101010 ppppPe tt +=

On peut aussi exprimer rp0 et rp1 de la façon suivante :

1010000 ppppp ttr +=

1110101 ppppp ttr +=

Si ppp ==

1100 , le canal est dit binaire symétrique ( binary symmetric channel BSC ). p est

le seul paramètre nécessaire pour caractériser un canal BSC. Nous pouvons élargir notre modèle au cas général où l’entrée X peut recevoir M valeurs distinctes (M>2). Le modèle du cas général est illustré par la figure ci-dessous. L’étude de ce canal est similaire à celle effectuée précédemment sur le canal binaire discret. Par exemple,

ij

M

i

ti

rj ppp ∑

==

1

et

( )

== ∑∑

≠==

M

jijij

M

i

tie ppPP

,11

error

Valeur X transmise

Valeur Y reçue

0

1 1

0 p00

p11

p10

p01

t

r

t

t

ij

pYP

pYP

pXP

pXP

pp

pp

iXjYPp

1

0

1

0

1011

0100

)1(

)0(

)1(

)0(

1

1

)(

==

==

==

==

=+=+

===

Modèle d’un canal discret.



Dans un canal discret sans mémoire tel que celui présenté sur la figure ci-dessus, il y a 2 processus statistiques à prendre en compte : ce que l’on envoie sur le canal et le bruit. Il y a donc un nombre d’entropies ou d’informations que l’on peut calculer. Premièrement, nous pouvons déterminer l’entropie de la source X comme suit :

( ) ( ) symbolebitsppXH ti

M

i

ti /log2

1∑

=−=

où tip est la probabilité que le ième symbole de l’alphabet soit transmis. De façon similaire, on

peut définir l’entropie de la sortie Y par :

( ) ( ) symbolebitsppYH ri

M

i

ri /log2

1∑

=−=

où tip est la probabilité pour que le symbole présent à la sortie du canal soit le ième symbole de

l’alphabet. ( )YH représente le nombre moyen de bits nécessaires par symbole pour coder la

sortie du canal. Nous pouvons aussi définir une entropie conditionnelle ( )YXH , appelée

équivocation, par :

( ) ( ) ( )( )∑∑==

====−=M

j

M

i

jYiXPjYiXPYXH1 21

log,

et une entropie conjointe ( )YXH , comme :

( ) ( ) ( )∑∑==

====−=M

j

M

i

jYiXPjYiXPYXH1 21

,log,,

L’entropie conditionnelle ( )YXH représente l’incertitude moyenne sur des entrées X, quand

la sortie Y est connue. Le lecteur peut vérifier les relations suivantes entre ( )XH , ( )YH ,

( )YXH , ( )XYH et ( )YXH , :

Modèle d’un canal discret sans mémoire M-aire

ij

rj

ti

piXjYP

pjYP

piXP

===

==

==

)(

)(

)(



( ) ( ) ( )YHYXHYXH +=,

( ) ( )XHXYH +=

où

( ) ( ) ( )( )∑∑==

====−=M

j

M

i

iXjYPjYiXPXYH1 21

log,

Pour un canal binaire symétrique, ( ) ( )1,0=== iiYiXP donne l’incertitude quant au bit

transmis, par référence au bit reçu. Cette incertitude est minimale quand ( ) 1=== iYiXP

pour 1,0=i , ce qui rend le canal sans erreur. L’incertitude est maximale quand

( ) 2/1=== iYiXP pour 1,0=i . Si on définit l’incertitude par ( )[ ]iYiXP ==−2

log alors

on a un bit d’incertitude quand la sortie est indépendante de l’entrée. Quand on a un bit d’incertitude associé à chaque bit reçu, la valeur reçue du bit ne contient aucune information ! L’entropie conditionnelle ( )YXH est une mesure moyenne d’incertitude sur X quand on

connaît Y. A l’extrême, X et Y peuvent être reliés entre eux de façon très simple ( Y = X par exemple ). Dans ce cas, il n’y a pas d’incertitude quant à X quand on connaît Y ;

( ) ijjYiXP δ=== , où ijδ est la fonction delta qui vaut 0 pour ji ≠ et 1 pour ji = . On peut

facilement vérifier que ( ) 0=YXH pour Y = X . Dans un contexte de communication, un

canal pour lequel Y = X représente un canal sans erreur, et il n’y a pas d’incertitude relative à la connaissance de l’entrée quand la sortie est connue. Autrement dit, on peut dire qu’il n’y a pas d’information perdue dans le canal puisque la sortie est uniquement reliée à l’entrée. Sur un autre exemple, si nous considérons un canal de communication tellement bruité que la sortie soit statistiquement indépendante de l’entrée. Dans ce cas, on peut aisément vérifier que

( ) ( ) ( )YHXHYXH +=, , et ( ) ( )XHYXH = , ce qui signifie que Y ne contient aucune

information sur X.

1.5.1. Débit d'information sur un canal discret

1.5.2. Capacité d’un canal discret sans mémoire

La capacité d’un canal (discret et sans mémoire) bruité est défini comme le débit maximal possible de la transmission d’information sur le canal. Le débit maximal de transmission se produit lorsque la source est "assortie" au canal. La capacité C d’un canal est définie par :

C = max {Dt} P(X)

= max [ H(X) – H(X|Y)] rs P(X)

où le maximum concerne toutes les sources d’information possible, le maximum est pris parmi toutes les distributions de probabilité possible pour la variable X discrète et aléatoire. Exemple 4.8 Calculer la capacité du canal discret de la figure 4.11. On prendra rs = 1 symbole/sec.



Modèle du canal pour l’exemple 4.8

Solution. Posons α = - [ p log p + q log q] et posons P(X=0)=P(X=3)=P et (X=1)=P(X=2)=Q (ces probabilités étant égales dues à la symétrie). Avec la définition de la capacité d’un canal,

C = max [ H(X) – H(X|Y)]

P,Q

sujet à la contrainte 2P + 2Q = 1 (pourquoi ?). Avec la définition de H(X) et de H(X|Y), nous obtenons

H(X) = - 2P log2 P – 2Q log2 Q H(X|Y) = -2Q(p log2 p + q log2 q) = 2Qα

d’où

Dt = - 2P log2 P – 2Q log2 Q - 2Qα

Nous voulons maximiser Dt et en ce qui concerne P et Q, nous avons l’équation 2P+2Q = 1 ( ou Q = ½ - P). En remplaçant Q = ½ - P, nous avons

Dt = - 2P log2 P – 2(½ - P) log2 (½ - P) – 2(½ - P )α Pour trouver la valeur de P qui maximise Dt, il faut résoudre

dDt/dP = 0

ou

0= - log2 e - log2 P + log2 e + log2 (½ - P) + α = - log2 P + log2 Q + α

En résolvant l’équation, on obtient

P = Q2α=Qβ ou

β=2α

En remplaçant P = Qβ dans 2P+2Q = 1, nous pouvons obtenir les valeurs maximales de P et Q comme :

0

2

3

0

1 1

3

2

q = 1-p

p

p

X Y

P( X= 0 ) = P P( X= 1 ) = Q P( X= 2 ) = Q P( X= 3 ) = P



P=(β/(2(1+ β)) Q=(1/(2(1+ β)).

La capacité du canal est alors,

C = - 2(P log2 P +2Q log2 Q + Qα) C =2.[ (β/(2(1+ β)).log2 (β/(2(1+ β)) + (1/(2(1+ β)).log2(1/(2(1+ β)) + (1/(2(1+ β)).log2β

C = log2((2.(β+1))/β) bits/sec Une vérification avec des valeurs extrêmes de p=1 et p=0 révèle la chose suivante : Avec P=1, nous avons un canal sans erreur et le débit maximal de transmission d’information se produit lorsque les symboles en entrée se produisent avec la même probabilité. La capacité du canal pour ce canal idéal est de 2 bits/symbole ou 2 bits/sec avec un débit de symbole de 1 symbole/sec. Dans le cas bruité avec p= ½, la capacité du canal est C=log2 3. Dans ce cas, le premier et le quatrième symbole sont utilisés plus souvent que les deux autres du fait de leur immunité au bruit. Aussi, le deuxième et le troisième symbole ne peuvent pas être distingués du tout et agissent ensemble comme un symbole. Alors, la capacité log2 3 parait être une réponse raisonnable. Pour d’autres valeurs de p, la capacité du canal se situera entre log2 3 et log2 4 bits/sec. La justification pour définir une capacité pour un canal bruité quand nous savons que nous ne pouvons jamais envoyer une information sans erreur sur un tel canal est basé sur le fait que nous pouvons définitivement réduire la probabilité d’erreur en répétant les messages plusieurs fois et en étudiant les différentes versions reçues du message. En augmentant la redondance de l’encodage, la probabilité d’erreur peut être quasiment nulle. Ce résultat est spécifié comme un théorème. Théorème Soit C la capacité d’un canal discret sans mémoire et soit H l’entropie d’une source d’information discrète émettant rs symboles par seconde. Si rs.H <= C, il existe alors un schéma de codage telle que la sortie de la source puisse être transmise avec une probabilité d’erreur arbitrairement petite. Il n’est pas possible de transmettre une information à un débit excédant C sans une fréquence positive d’erreurs. Puisque une preuve de ce théorème est mathématiquement impressionnant, nous regarderons aux systèmes d’encodage qui accompliront la tâche mentionnée dans le théorème dans un prochain chapitre quand nous reviendrons aux systèmes d’encodeurs de canal. Pour le moment, il suffit de dire que si le débit d’information de la source est inférieure à la capacité du canal, alors nous pouvons mettre en œuvre un canal encodeur/décodeur qui nous autorisera à transmettre la sortie de la source sur un canal avec probabilité d’erreur arbitrairement petite.

1.6. Canaux continus

Le canal de communication entre les points "d" et "f" de la page 15 est de nature analogique ou continue. Dans cette partie du canal, les signaux d’entrée sont des fonctions continues du temps, et la fonction du canal est de restituer à ses sorties la forme de l’onde présentée à ses entrées. Un canal réel n’accomplit cette fonction qu’approximativement. Premièrement, le



canal modifie la forme d’onde de manière déterministe et cet effet peut être parfaitement modélisé en assimilant le canal à un système linéaire. Le canal modifie aussi le signal d’entrée de manière aléatoire par des bruits additifs et multiplicatifs. Dans ce cours, nous parlerons uniquement du bruit additif car il intervient plus souvent que le bruit multiplicatif. Le bruit additif peut être « impulsif » ou gaussien. Le bruit gaussien inclut le bruit des équipements et des radiations captées par l’antenne réceptrice. D’après le théorème de la limite centrale, le bruit résultant de la somme des effets des différentes sources suit une distribution gaussienne. A cause de son omniprésence, le bruit gaussien est plus souvent utilisé pour caractériser la portion analogique des canaux de communication. Les techniques de modulation et de démodulation sont choisies de façon à diminuer les effets du bruit gaussien. Un deuxième type de bruit, le bruit « impulsif », est aussi rencontré dans les canaux. Il est caractérisé par des alternances de longs intervalles de silence et des pics de bruit de forte amplitude. Ce type de bruit est dû aux commutations, aux décharges électriques, et aux heurts accidentels lors de la maintenance des appareils. Caractériser ce bruit est beaucoup plus difficile que de caractériser le bruit gaussien. Ainsi, pour ce bruit, les techniques de modulation analogique ne sont pas aussi adaptées que des méthodes de codage numérique pour résoudre les effets de ce bruit. C’est pour cela que les effets du bruit « impulsif » sont souvent inclus dans le modèle de la partie discrète du canal, et seul le bruit gaussien est inclus dans le modèle de la partie analogique du canal.

Portion analogique du canal de communication La partie analogique du canal de communication peut être modélisée comme le montre la figure ci-dessus. L’entrée du canal est un processus aléatoire Xc(t), qui est la somme des formes d’ondes générées par le modulateur. La largeur de bande de Xc(t) et du canal est de B Hz (par commodité, nous dirons que Xc(t) et le canal sont passe bas). Le bruit additif à la sortie du canal est un bruit blanc gaussien n(t) à bande limitée et de moyenne nulle. La capacité de cette portion de canal est trouvée en maximisant le taux d’information transmise en respectant la distribution de Xc(t). Bien que la formulation du problème est similaire à celle que l’on a utilisée pour les canaux discrets en ce qui concerne H(Xc) et H(Xc| Z), l’optimisation est très compliquée. Cependant, le résultat a une forme très simple ; nous prendrons le résultat comme théorème et allons discuter de quelle façon ce résultat peut être utilisé dans la conception des systèmes de communication.

canal ∑ +

+

Bruit blanc gaussien à bande limitée n(t)

Xc(t) ( du modulateur )

Vers le démodulateur Z(t) = Xc(t) + n(t)



1.6.1. Le théorème de Shannon-Hartley et ces implications

Théorème La capacité d’un canal de bande passante B et de bruit additif blanc gaussien à bande limité est

sec/)1(log2

bitsNSBC +=

où S et N sont la puissance moyenne du signal et du bruit , respectivement, à la sortie du canal. (N = ηB si la densité spectrale de puissance du bruit est η/2 watts/Hz. ) Ce théorème, connu sous le nom de théorème de Shannon-Hartley, est d’un importance fondamentale et a deux implications importantes pour les ingénieurs systèmes. Premièrement, il nous donne la limite supérieure que l’on peut atteindre en terme de taux de transmission de données fiables sur des canaux gaussiens. Ainsi, un concepteur système essaie toujours d’optimiser son système pour avoir un flux de données aussi près que possible de C avec un taux d’erreur acceptable.

Documents

1. THEORIE DE L INFORMATION · Vahid Meghdadi 2008/2009 4 Exercice : Calculer l'entropie d'une source qui émet 3 symboles A, B et C avec des probabilités 1/2, 1/4 et 1/4. Exercice,