Théorie de l'information et codage

Master de cryptographie

Cours 1 : Théorie de l'information

5 et 8 janvier 2009

Université Rennes 1

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 1 / 21

Introduction (1)

Wikipédia

La théorie de l'information se préoccupe des systèmes d'information, dessystèmes de communication et de leur e�cacité.Ce domaine trouve son origine scienti�que avec Claude Shannon qui en estle père fondateur en 1948.Parmi les branches importantes, on peut citer :

le codage de l'information,

la mesure quantitative de redondance d'un texte,

la compression de données,

la correction d'erreurs,

la cryptographie.

Principes de base

L'information diminue l'incertitude

Moins un évènement est probable, plus il contient de l'informationMaster Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 2 / 21

Intoduction (2)

Théorie de l'information = modèle théorique pour la source et le canal

→ approximation du comportement réel

Modèles

Source/canal discret ou continu avec ou sans mémoire

Canal bruité ou non bruité

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 3 / 21

Codage des sources discrètes sans mémoire

La sortie de la source est une séquence de lettres tirées d'un alphabet �niA = {a1, · · · , an}.Chaque lettre ai de l'alphabet apparaît avec une probabilité pi = p(ai )

Exemples d'alphabets

Binaire {0, 1}Hexadécimal {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c , d , e, f }Français {a, · · · , z} avec p(a) ≈ 0.06, · · · , p(z) ≈ 0.0004

Le codage de source consiste à représenter ces séquences en binaire le pluse�cacement possible.

Exemple de codage du français

Code ASCII : chaque lettre est codée par 1 octet (8 bits)

Code Morse : chaque lettre est codée par 1 à 4 bits

Un bon choix du code dépend de la loi de probabilité p.Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 4 / 21

Exemple de codage de source

Soit un alphabet A à 4 lettres (a1, a2, a3, a4)

Codage 1 Codage2

a1 → 00 a1 → 0a2 → 01 a2 → 10a3 → 10 a3 → 110a4 → 11 a4 → 111

Si p est la loi uniforme

Le codage 1 nécessite en moyenne 2 bits par lettre.Le codage 2 nécessite en moyenne 2.25 bits par lettre.

Le codage 1 est meilleur

Si p(a1) = 12, p(a2) = 1

4, p(a3) = p(a4) = 1

8

Le codage 1 nécessite toujours en moyenne 2 bits par lettre.Le codage 2 nécessite en moyenne 1.75 bits par lettre.

Le codage 2 est meilleur

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 5 / 21

Information et quantité d'information

Dé�nition

Une information désigne un ou plusieurs évènements possibles parmi unensemble �ni d'évènements.

Exemple : recherche d'un �chier

Si on précise le dossier, l'incertitude diminue.

De même si on précise le type du �chier.

On veut mesurer la valeur à priori d'une information.Si on a 2 informations, la valeur n'est forcément pas la somme des 2.

Dé�nition

Soit p(a) la probabilité qu'un évènement a se produise. La quantitéd'information ou information propre de l'évènement a est alors

I (a) = − log2 p(a).

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 6 / 21

Pourquoi un logarithme ?

On veut une fonction qui soit

Décroissante (plus la probabilité qu'un évènement se produise estforte, moins on en tire d'information)

Additive (La quantité d'information apportée par 2 informationsindépendantes est égale à la somme des quantités d'information)

→ Le log est naturel à utiliser

On souhaite qu'un bit d'information soit égal à la quantitéd'information fournie par le choix d'une alternative parmi 2équiprobables

→ La base 2 est imposée

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 7 / 21

Entropie d'une source

Plus qu'à la quantité d'information liée à un évènement, on s'intéresse àl'information fournie par une source donnée, autrement dit à la valeurmoyenne de l'information propre des informations fournies par la source.

Dé�nition

On appelle entropie d'une source A (ensemble des évènements possibles) eton note H(A) la quantité

H(A) =∑a∈A

p(a)I (a) = −∑a∈A

p(a) log2 p(a).

Théorème

Soit A un alphabet de cardinal n et p une loi de probabilité sur A. AlorsH(A) ≤ log2 n avec égalité si et seulement si p est la loi uniforme.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 8 / 21

Codes

Notations

Soit Σ un alphabet �ni. On note Σ∗ l'ensemble des mots �nis sur Σ dont lemot vide en général noté ε.La concatenation de 2 mots u et v est notée uv .La taille d'un mot u, notée |u| est le nombre de lettres de u.

Dé�nitions

Un code C sur un alphabet Σ est un sous ensemble de Σ∗.

Un code C est dit à déchi�rage unique ssi pour tous mots de Cu1, · · · , un et v1, · · · , vm,

u1 · · · un = v1 · · · vm ⇒ n = m et ∀i , ui = vi

Un code est dit pré�xe si aucun mot du code n'est le pré�xe (début)d'un autre.

Un code est dit à longueur �xe si tous ses mots ont même longueurMaster Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 9 / 21

Codages (binaires)

Dé�nition

Un codage d'un source discrète est une application injective qui associe àchaque séquence �nie de lettres de la source une séquence binaire �nie, i.e.une application de A∗ dans {0, 1}∗ si A est l'alphabet de la source.

Un cas particulier important

On associe à chaque lettre de A un mot de {0, 1}∗ (c : A→ {0, 1}∗).le codage d'un mot u1 · · · un de A∗ est donnée par c(u1) · · · c(un).

Si C , l'ensemble des codes possibles des lettres de A, est un code àdéchi�rage unique et si c est injective sur A, alors on obtient bien uncodage.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 10 / 21

E�cacité du codage

Dé�nition

Sot m le nombre moyen de symboles binaires utilisés par lettre de la source

m =∑a∈A

p(a)|c(a)|.

L'e�cacité du code est dé�nie par E = H(A)m

Code optimal

On cherche à ce que l'e�cacité soit la meilleure possible

Langage courant pas e�cace (cf TD)

Représenter les 26 lettres avec 5 bits → E ≤ 94%

Associer aux lettres les plus courantes des codes plus courts (Morse,Hu�man)

Peut on atteindre une e�cacité de 1 ? Le veut on ?

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 11 / 21

Codage avec un code de longueur �xe

Propriété

Si une source a pour cardinal n, il est possible de la coder avec un code delongueur �xe m tel que

log2 n ≤ m ≤ 1 + log2 n

E =H(A)

m

H(A) ≤ log2 n⇒ E ≤ 1 avec égalité si et seulement si

Les lettres de la source sont équiprobables.

Le cardinal de la source est une puissance de 2.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 12 / 21

Exemple

A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} avec la loi uniforme.On code cette source avec un code de longueur 4

E =H(A)

4=

log2 10

4≈ 0.83

Si on code plutôt les paires de chi�res, i.e.A2 = {00, 01, 02, · · · , 97, 98, 99}, on peut le faire avec un code de longueur7 et on a alors

E =H(A2)

7=

log2 100

7≈ 0.95

Et pourquoi pas les triplets ?

L'e�cacité croit mais le codage et le décodage se complexi�ent

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 13 / 21

Premier cas particulier du premier théorème de Shannon

Proposition

Soit A une source de cardinal n. Soit Al la source de l -uplets de lettres deA. Il existe un code de longueur �xe ml pour A

l tel que

log2 n ≤ml

l<

1

l+ log2 n.

L'e�cacité de ce code vaut alors H(A)ml

l

et converge vers H(A)log2 n

quand l

devient grand

Finalement, cela prouve que, pour une source munie d'une loi de probabilitéuniforme, l'e�cacité du codage peut être arbitrairement proche de 1.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 14 / 21

Le premier théorème de Shannon

Théorème

Pour toute source discrète sans mémoire, il existe un codage (injectif)permettant de coder la source et dont l'e�cacité est arbitrairement prochede 1.

Remarques

L'idée de la preuve est de coder les l -uplets avec des codes delongueur variable.

La preuve est e�ective.

Reste à coder le canal (présence de bruit).

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 15 / 21

Codage de canal

On considère un canal discret sans mémoireEntrée : alphabet �ni A = {a1, · · · , an}Sortie : alphabet �ni B = {b1, · · · , bm}Un tel canal est décrit par la donnée des probabilités conditionnelle p(ai |bj),i.e. la probabilité que la lettre émise soit ai sachant qu'on a recu bj .

Exemple : canal binaire symétrique

A = B = {0, 1}. On note p la probabilité pour qu'un bit soit changé.

p(1|0) = p(0|1) = p et p(0|0) = p(1|1) = 1− p

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 16 / 21

Quantité d'information perdue

Cas du canal binaire symétrique

Si une erreur se produit, la quantité d'information perdue est − log2 p.

Sinon, la quantité d'information perdue est − log2(1− p).

En moyenne on perd donc −p log2 p − (1− p) log2(1− p).

Entropie conditionnelle

Elle vaut H(A/B) = −∑

a∈A,b∈Bp(a, b) log2 p(a|b).

et représente la quantité d'information perdue

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 17 / 21

Information mutuelle

Dé�nition

L'information mutuelle de a et b vaut

I (a; b) = I (a)− I (a|b) = log2p(a|b)

p(a)

= log2p(a, b)

p(a)p(b)

Le signe de I (a; b) détermine si l'incertitude sur a augmente ou diminue.

Information mutuelle moyenne

I (A;B) = H(A)− H(A|B)

représente la quantité moyenne d'information transmise et est toujourspositive (ie l'incertitude sur A diminue toujours) ou nulle si A et B sontindépendants.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 18 / 21

Capacité d'un canal

Vocabulaire

Un canal est dit sans pertes si H(A|B) = 0 pour toute les distributionsd'entrée. L'entrée du canal est déterminée par sa sortie.

Un canal est dit déterministe si la sortie est déterminée par l'entrée.

Un canal est dit sans bruit si il est déterministe et sans pertes.

Un canal est dit inutile si I (A,B) = 0 pour toute les distributionsd'entrée.

Dé�nition

La capacité d'un canal est la plus grand quantité d'information moyennequ'il peut fournir sur A.

C = maxpA

I (A;B)

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 19 / 21

Rendement d'un code

Exemple : canal binaire symétrique

On cherche à diminuer la probabilité d'erreur.On peut utiliser par exemple un code de répétition

1→ 111, 0→ 000

Rendement 13

Rendement d'un code

Soit C un code de longueur n et de cardinal M. Son rendement est

R =log2M

n

En diminuant le rendement, on peut diminuer la probabilité d'erreur autantque l'on veut.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 20 / 21

Le second théorème de Shannon

Théorème

Soit C la capacité du canal de transmission et soient 2 réels ε > 0 etc < C . Il existe un code de rendement supérieur à c tel que la probabilitéd'erreur en sortie soit inférieure à ε.Réciproquement, pour tout code de rendement R > C , il existe uneconstante KR,C telle que la probabilité d'erreur en sortie soit supérieure àKR,C .

Remarque : Ce théorème n'est pas e�ectif.Conséquence : On va étudier les codes correcteurs d'erreurs et c'esttoujours un sujet de recherche.

Master Crypto (2008-2009) Théorie de l'information et codage 5 et 8 janvier 2009 21 / 21