Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UFR de Sciences Université de Caen THEORIE DE L’INFORMATION ___ CODAGE DE SOURC

UFR de Sciences Université de Caen THEORIE DE L’INFORMATION ___ CODAGE DE SOURCE ___ G.BINET MdC 61 T_info_source p.1 UFR de Sciences Université de Caen THEORIE DE L’INFORMATION I. MODELISATION D’UNE SOURCE I.1 Modèle mathématique d’une source : I.2 Source discrète sans mémoire : II. MESURE DE L'INFORMATION: II.1 Quantité d'information: II.2 Entropie d'une source : II.3 Entropie jointe entre deux sources : II.4 Quantité d'information mutuelle : II.5 Entropie conditionnelle : II.6 Expressions de la quantité d'information mutuelle et de l'entropie conditionnelle moyenne : II.7 Intérêt de ces quantités et formulations : III. CODAGE DE SOURCES DISCRETES : III.1 Débit moyen d'information : III.2 Codage avec mots de longueur fixe, efficacité : Mots de codes de longueur fixe : Codage par blocs, extension de la source : Théorème du codage de source, 1er théorème de Shannon : III.3 Codage, mots de longueur variable : Codes préfixes : Longueur moyenne de code : Inégalité de Kraft : Théorème du codage de source, 2ème théorème de Shannon : III.4 Codage de Huffman : Algorithme : III.5 Codage de Fano-Shannon : G.BINET MdC 61 T_info_source p.2 UFR de Sciences Université de Caen IV. COMPRESSION DE L'INFORMATION IV.1 Les différentes méthodes : IV.2 Le codage statistique à longueur variable : IV.3 Codage par dictionnaire : méthode de Lempel-Ziv IV.4 Le codage par répétition : méthode RLE (RLC) G.BINET MdC 61 T_info_source p.3 UFR de Sciences Université de Caen THEORIE DE L’INFORMATION I. MODELISATION D’UNE SOURCE Il est possible de classer les sources en deux catégories selon les signaux ou messages qu’elles émettent : Les sources analogiques : domaine de la TV, la vidéo, la radio (l’audio en général). Les sources discrètes : disques optiques (Cd, DVD,…), les mémoires magnétiques (disques durs, bandes,…). Quelque soit le type de source, l’information doit être transmise sous forme numérique. L’encodeur de source est l’élément chargé de la transformation du format de l’information. Bien entendu, le problème est différent selon que nous avons à faire à une source continue ou discrète. I.1 Modèle mathématique d’une source : Une source transmet une information à un récepteur celui-ci ne connaissant pas l’information qui va lui être transmise. Un exemple simple permet d'introduire les idées nécessaires. Deux interlocuteurs discutent en français, l’un deux prononce un mot commençant par "cha", celui qui écoute peut avoir une idée de la suite du mot : "riot" "teau" "peau" ? sûrement pas "gnon". Que peut-on en déduire? L'information est en général imprédictible ou partiellement imprédictible. Nous pouvons même aller plus loin : qu'est-ce qui est intéressant pour celui qui écoute? Sûrement pas une suite qu'il connaît à coup sûr car ce n'est plus une information, il est d'autant plus intéressé qu'il ne peut pas prédire la suite. Ce petit exemple nous amène donc aux deux constatations suivantes: 1. Une source d'information émet en général un message non déterministe. D'un point de vue signal ce ne peut être qu'un signal aléatoire et la modélisation mathématique associée doit être stochastique ⇒ une information est un processus stochastique. 2. Ce qui rend une information intéressante est son caractère imprédictible. Une information est ainsi d'autant plus riche qu'elle est peu probable. I.2 Source discrète sans mémoire : Pour caractériser les sources, de nombreux termes sont empruntés à la description du langage courant. Une source dispose d'un "alphabet" constitué d'éléments ou symboles ou caractères {x1 , x2 , x3 ,…, xK} . K est la longueur de l'alphabet. Ces symboles sont associés pour constituer un message. Emettre un message revient à émettre une succession de symboles appartenant à une source. Chaque symbole xk de l'alphabet a une probabilité d'utilisation pk. Pour simplifier le problème, une catégorie de sources est plus simple à modéliser : celle des sources pour lesquelles la probabilité d'émission d'un caractère est indépendante de ce qui a été émis avant ou sera émis après. C'est ce qui défini une source sans mémoire. G.BINET MdC 61 T_info_source p.4 UFR de Sciences Université de Caen II. MESURE DE L'INFORMATION: II.1 Quantité d'information: A partir des remarques suivantes: • 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: 1. I(.) est une fonction continue de la probabilité pi. 2. I(pk) ↑ si pk ↓ ⇒ I(pk) est une fonction décroissante de pk. 3. I(pk et pj) = I(pk) + I(pj). 4. Un symbole certain possède une quantité d'information nulle : I(pk=1) = 0. Une fonction mathématique remplit les conditions 1, 3 et 4 : log(pk). Pour obtenir la propriété 2, il suffit de prendre –log(pk) = log(1/pk). La quantité d'information d'un symbole xk de probabilité pk a ainsi été définie par Shannon comme : ) p 1 log( ) p log( - ) x ( I k k k = = unités: Dans la définition de la quantité d'information il n'a pas été précisé la base du logarithme utilisée et c'est cette base qui définit l'unité. Plusieurs systèmes existent: • Base 2 : c'est celle historiquement choisie par Shannon qui est à l'origine de cette définition. L'unité ainsi obtenue est le bit pour binary digit ou binary unit. Cette unité a été rebaptisée le shannon en hommage à son inventeur mais cette appellation reste peu usitée. Pour une source binaire de deux symboles équiprobables, pk=1/2 et I(xk) = 1 bit . Le symbole d'une source binaire qui est un bit possède donc une quantité d'information de 1 bit, d'où l équivalence. Par la suite, sauf précision contraire, c'est l'unité que nous utiliserons. • Base e : utilisation du logarithme Népérien dit encore logarithme naturel. L'unité devient alors le nats pour natural units. Sachant que Ln(a) = Ln(2).log2(a) = 0,69315.log2(a) ⇒ 1 nats = 0,69315 bits et 1bit = 1,44269 nats. • Autres bases : d'autres bases ont été proposées mais à priori peu utilisées. En conformité avec le système décimal, la base 10 qui donne le dit pour décimal unit. Signalons enfin la base 3 à l'origine du trit pour trinary unit. Rappel sur les changements de base: Soit deux bases de logarithmes : base a et base b. Le passage entre les bases se fait par : logb( p ) = logb( a ) . loga( p ) G.BINET MdC 61 T_info_source p.5 UFR de Sciences Université de Caen II.2 Entropie d'une source : L'entropie H(S) d'une source S est la quantité d'information moyenne contenue dans l'alphabet X de cette source. Du point de vue mathématique, cela s'exprime par H(S) = E[ I(X) ] soit: ∑ ∑ = = k k k k k k ) p 1 og( l p ) x I( p ] X) ( I [ E ∑ = = K 1 k k k ) p 1 log( p ) S ( H exprimée en bits/symbole ou Shannon/symbole. Exemple: source binaire avec deux symboles "0" et "1" de probabilités respectives p et 1-p. 0,5 0 1 1 p H( X ) ) p - 1 1 log( p) - (1 ) p 1 log( p ) S ( H + = cette entropie est maximale pour p = 0,5 et vaut zéro pour p = 0 et p = 1. Cet exemple est un cas particulier d'une source ayant un alphabet de K symboles. On démontre que (voir TD) que son entropie est maximale lorsque tous les symboles sont équiprobables donc pk = 1/K et l'entropie devient: ) K log( ) K log( K 1 ) S ( H K 1 k = = ∑ = . Ce qui montre le théorème suivant sur l'entropie d'une source: ) K log( ) S H( 0 ≤ ≤ II.3 Entropie jointe entre deux sources : Cette notion permet de mesurer le degré de similitude entre deux sources. Soit deux sources : X d'alphabet {x1, x2,…,xN} Y d'alphabet {y1, y2,…,yM} Du point de vue aléatoire, il existe une densité de probabilité jointe entre deux caractères : p( xi , yj ). Ceci permet de définir la quantité d'information jointe due aux deux caractères: ) ) y , x p( 1 log( ) y , x p( ) y , x ( I j i j i j i = l'entropie jointe des deux sources est alors la quantité d'information moyenne jointe entre deux caractères de la source : ) ) y , x p( 1 log( ) y , x p( ) Y , X H( i j j i j i ∑∑ = G.BINET MdC 61 T_info_source p.6 UFR de Sciences Université de Caen Cas ou les deux sources sont indépendantes: p( xi , yj ) = p( xi ).p( yj ) ∑ ∑ ∑ ∑ ∑ ∑ ∑ + = + = = i ) Y H( j j j i j ) X H( i i i j j , i j j i j , i i j i j , i j i j i ) y uploads/Litterature/ codage-source.pdf