Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Théorie de l'information et du codage : signal analogique, signal numérique et applications en télécommunications (Electronique pour le traitement du signal avec problèmes corrigés Vol. 5)

De
502 pages
La théorie de l'information avec le codage de source à travers les algorithmes de Fano et Huffman et la théorie du codage de canal (détecteur et correcteur d'erreurs) avec l'étude des codes en blocs, cycliques et convolutifs y sont développées, pour mener au traitement analogique et numérique du signal avec son application en télécommunication. La théorie de l'échantillonnage comme discrétisation dans le temps et la théorie de la quantification comme discrétisation en amplitude, avec l'estimation des erreurs associées est décrite. Les limitations du canal de transmission avec le théorème de Nyquist sont également développées ainsi que les techniques d'égalisation usuelles. L'auteur analyse les deux modes de transmission usuels, la transmission en bande de base avec tous les modes, RZ, NRZ, Bi phase, HDBn, entrelacés, etc. ainsi que la transmission sur fréquence porteuse avec les techniques de modulations analogiques discrètes comme les modulations FSK et PSK multicadence, et une approche sur les probabilités d'erreurs associées à travers la notion d'espace de signal. Les problèmes importants de récupération d'horloge et de synchronisation sont précisés.
Théorie de l'information. Théorie du codage. Signal analogique, signal numérique. Exercices et corrigés. Bibliographie / Index.
Voir plus Voir moins








Electronique pour le traitement du signal – volume 5

Théorie de l'information et du codage


































© LAVOISIER, 2006
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN volume 5 2-7462-1343-5
ISBN général 2-7462-1338-9



Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part,
que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, October 2006. Electronique pour le traitement du signal – volume 5







Théorie


de l'information


et du codage




signal analogique, signal numérique

et applications en télécommunications




Yvon Mori









Pour Monika, Arnaud et Sylvain.



Préambule

Après avoir pendant près de vingt ans, enseigné des cours du soir au CNAM de Nice,
(Conservatoire National des Arts et Métiers), cycle B, filière électronique et ceci dans tous
les domaines de l'électronique au sens large, ainsi que des cours de télécommunication à
l'IUT Génie des Télécommunications et Réseaux de Nice Sophia Antipolis, il m'a semblé
indispensable de transmettre toute cette connaissance aux auditeurs intéressés et de la
rendre plus pérenne à travers cette édition. Ceci d'autant plus qu'elle a été élaborée avec un
esprit pédagogique de professeur d'université, associé à l'approche plus pragmatique et
pratique du responsable de laboratoire d'une grande entreprise industrielle française, ce qui
devrait la rendre plus attrayante et qui fait une grande partie de son intérêt.

L'architecture générale adoptée constitue une collection intitulée Electronique pour le
traitement du signal. Elle comprend huit volumes, chaque volume s'appuie sur un certain
nombre de chapitres, traitant chacun d'un sujet spécifique et comportant des exercices
variés ainsi que leurs corrections détaillées. Ces différents chapitres ont été constitués à
partir des notes personnelles de l'auteur prises pendant son cursus au CNAM de Nice avec
ses différents professeurs, qu'ils soient tous vivement remerciés ici pour les connaissances
qu'ils ont su si généreusement lui dispenser, en particulier Jean Paul Marage, professeur
CNAM et ami, sans qui rien n'aurait été possible, ainsi que des synthèses de certains
chapitres des documents de la bibliographie générale proposée qui accompagne chaque
volume.

L'objectif principal de cette collection est de donner un outil pratique à la portée de tous
les étudiants des cycles de niveau B3 ou licence professionnelle, soit du premier cycle des
études supérieures, ainsi qu'aux élèves des écoles d'ingénieurs, qui leur permettra
d'appréhender les concepts principaux utilisés pour mettre en œuvre les moyens modernes
de traitement du signal appliqué aux télécommunications et pour préparer dans les
meilleures conditions, la poursuite de leurs études. Pour cela elle à été élaborée dans un
esprit pédagogique de cours magistral, de manière à faciliter sa lecture et son assimilation.
Les développements mathématiques sont volontairement limités et traités avec la rigueur
suffisante pour la compréhension des outils utilisés. Les principaux concepts sont
développés de manière homogène, ce qui doit permettre au lecteur intéressé d'avoir une vue
complète sur ces derniers et de les approfondir s'il le souhaite à l'aide de la bibliographie
fournie, qui contient la plupart des références encore unanimement reconnues dans les
domaines concernés.

Le Volume 5 qui est proposé ici, développe les outils principaux qui permettent de
comprendre les systèmes modernes de télécommunications.
Son titre est Théorie de l'information et du codage, il est constitué de trois chapitres.
La théorie de l'information avec le codage de source à travers les algorithmes de Fano et
Huffman et la théorie du codage de canal (détecteur et correcteur d'erreurs) avec l'étude des
codes en blocs, cycliques et convolutifs y sont développées, pour mener finalement au
traitement analogique et numérique du signal avec son application en télécommunication,
domaine on ne peut plus d'actualité.
On y trouvera donc la théorie de l'échantillonnage comme discrétisation dans le temps et
la théorie de la quantification comme discrétisation en amplitude, avec l'estimation des
erreurs associées. Les limitations du canal de transmission avec le théorème de Nyquist est
aussi développée ainsi que les techniques d'égalisation usuelles.
Seront précisés aussi les deux modes de transmission usuels, la transmission en bande
de base avec tous les modes, RZ, NRZ, Bi phase, HDB , entrelacés, etc. et la transmission n
sur fréquence porteuse avec les techniques de modulations analogiques discrètes comme 6 Electronique pour le traitement du signal, volume 5
les modulations FSK et PSK multivalence ainsi qu'une approche sur les probabilités
d'erreurs associées à travers la notion d'espace de signal.
Les problèmes importants de récupération d'horloge et de synchronisation seront
précisés.

Le volume 1, sert d'introduction et propose des outils pour aborder les autres volumes
dans de bonnes conditions.
Son titre est Outils mathématiques et espaces transformationnels. Il est constitué de neuf
chapitres, qui précisent de manière synthétique et pratique, les outils habituellement utilisés
dans ce domaine et qu'il est indispensable de connaître. On y trouve donc une approche sur
les espaces de signaux, la notion de convolution associée et son extension à la distribution
de Dirac, l'opération de corrélation qui prépare aux signaux aléatoires, le calcul
transformationnel avec la transformée et la série de Fourier, la fonction de la variable
complexe avec la transformée de Laplace, comme outil fondamental pour l'analyse des
réseaux et circuits linéaires. La transformée en Z est aussi développée comme outil
fondamental d'étude des systèmes numériques discrets et prépare aux techniques de filtrage
numériques étudiées dans le volume 5.

Le volume 2 concerne tout ce qui se rapporte à la notion de signal.
Son titre est Notions de signal et de bruit. Il est constitué de trois chapitres, avec une
approche sur la notion de bruits que l'on ne peut dissocier de celle de signal, la distinction
entre signaux déterministes et aléatoire ou processus stochastiques, ainsi que la notion de
linéarité, de circuit linéaire et fonction de réseaux associée.
On y trouvera donc toutes les propriétés des fonctions de réseaux en régime isochrone ou
isomorphe, les techniques de détermination des modules et phase connaissant F(p) ou les
parties réelles et imaginaires et l'extension à la notion d'immittance à caractère positif réel,
pour établir les technique de synthèse des structures physiquement réalisables.
Ensuite la théorie des probabilités, la notion de variable aléatoire à une et deux dimension
préparera au concept de fonction ou processus aléatoire avec une application particulière
aux processus discrets utilisés dans les systèmes numériques.
La notion de bruit est ensuite développée à travers la notion de facteur de bruit et source
équivalent de bruit et les calculs associés en fonction des différentes sources de bruit
analysées.

Le Volume 3 développe tout l'aspect des opérations de filtrage analogiques.
Son titre est Circuits linéaires. Il est constitué de quatre chapitres. Les modèles
mathématiques des fonctions de transferts en « p » avec les approximations classiques de
Butterworth, Tchebychev, Papoulis et Legendre pour les filtres à temps de propagation de
groupe y sont développées. Ensuite les notions de stabilité des fonctions de transferts en
« p » et en « z » associées, sont étudiées à travers le critère de Nyquist, de Hurwitz, de
Routh et la détermination du lieu d'Evans. Avec comme application la synthèse des filtres
actifs RC, qui sont les plus utilisés car plus faciles en mettre en œuvre technologiquement, à
l'aide de structures à amplificateurs opérationnels et convertisseurs d'impédance. La
synthèse des filtres passifs LC utilisés en filtrage de puissance par exemple, comme évoqué
dans le volume 8 qui traite de la Compatibilité ElectroMagnétique (CEM) est développée
avec la synthèse des dipôles LC, RC de Foster et de Cauer ainsi que celle des quadripôles
passifs avec Darlington. Une approche de synthèse des fonctions de transfert est aussi
proposée.


Préambule 7
Le Volume 4 aborde les techniques de modulation.
Son titre est Techniques de modulation. Il est constitué de quatre chapitres. Après une
introduction à la notion de signal analytique nécessaire pour la modulation BLU, les trois
types de modulations classiques, linéaires, non linéaires, discrètes et numériques sont
développées, avec l'analyse des circuits usuels de leur mise en œuvre.
On y trouvera donc la modulation d'amplitude avec et sans porteuse, la modulation à
bande latérale unique, la modulation de phase et de fréquence, les modulations d'impulsions
en amplitude, position, durée, fréquence et intervalle. L'étude des rapports signal à bruit est
faite dans le cas des signaux déterministes et aléatoire.
Les modulations numériques sont présentées avec les convertisseurs analogique
numérique (CAN) et numérique analogique (CNA), à simple et double rampe, à intégrations
successives et autres dans un premier temps. Ensuite la technique de modulation par
impulsion ou codage MIC est développée pour finir avec les convertisseurs à
suréchantillonnage comme le codage delta, sigma delta à compression et adaptatif qui sont
les techniques modernes de plus en plus utilisées.

Le Volume 6 traite du filtrage numérique.
Son titre est Filtrage numérique. Il est constitué d'un seul chapitre et de sept travaux
pratiques sur Matlab comme exercices de mise en application, avec les corrections
associées. On y trouvera en préalable la transformée de Fourier discrète (TFD) et sa relation
avec la transformée en Z (TZ), ainsi que la notion de transformée de Fourier rapide (TFR)
qui prépare au filtrage numérique. La synthèse des filtres à réponse impulsionnelle finie RIF
et infinie RII avec les méthodes à échantillonnage et les techniques de fenêtrage associées,
à réponse impulsionnelle, à transformation bilinéaire. Une approche sur les erreurs et
troncatures, débordement est aussi proposée.
Les travaux pratiques proposés sont orientés pour la mise en évidence et la résolution
des problèmes classiques rencontrés dans ce domaine.

TP1 – « Systèmes numériques »,
TP2 – « Analyse de signaux échantillonnés »,
TP3 – « Transformée de Fourier Discrète »,
TP4 – « Echantillonnage et quantification » ,
TP5 – « Signal aléatoire »,
TP6 – « Synthèse RIF »,
TP7 – « Synthèse RII ».

Le volume 7 aborde l'électromagnétisme sous l'aspect de ses applications pratiques.
Son titre est Electromagnétisme. Il est constitué de deux chapitres. Après une introduction
synthétique à l'électromagnétisme où les lois de base à travers les équations de Maxwell
sont explicitées, une introduction à l'électronique des impulsions et à la théorie des lignes est
développée. Elle permet, à travers les concepts des systèmes à constantes réparties, de
bien appréhender la nécessité de maîtriser les impédances caractéristiques dans les
systèmes modernes de télécommunications qui travaillent à des fréquences de plus en plus
élevées.

Enfin le volume 8 s’intitule Compatibilité ElectroMagnétique (CEM), domaine encore trop
peu exposé dans les cours traditionnels et qu'il est absolument indispensable de prendre en
compte dans les réalisations industrielles de tout système électronique. En effet, le passage
du théorique au pratique nécessite de prendre en compte l'environnement perturbé dans
lequel on baigne, ainsi que les limitations physiques de tous les paramètres et matériaux qui
interviennent dans les phases de conceptions et qui sont à l'origine des perturbations et
dysfonctionnement que l'on peut rencontrer en phase d'installation. De plus les réalisations 8 Electronique pour le traitement du signal, volume 5
industrielles sont toujours soumise à des Spécifications Techniques de Besoin (STB), qui
appellent toutes des documents normatifs civils ou militaires qui évoquent des normes de
CEM, qu'il est donc indispensable de connaître dans le monde du travail.

Les chapitres de chaque volume sont accompagnés d'exercices qui sont généralement de
difficulté croissante. Ceci de manière à bien comprendre dans un premier temps, les
concepts de base, pour ensuite proposer des applications un peu plus complexes que l'on
peut rencontrer en pratique et qui mettent en œuvre les outils développés dans tout le
manuel. Les concepts de base des cours y sont rappelés de manière synthétique, avec des
prolongements complémentaires sur des outils ou des applications spécifiques aux thèmes
des cours et qui n'ont pas été développé dans le corps du cours proprement dit. Les
corrections sont volontairement détaillées pour faciliter la compréhension du lecteur, car c'est
ce que j'aurais aimer y trouver lorsque j'étais encore étudiant. Quelques exercices
demandent à utiliser le tableur Excel, à la portée de tous, de manière à vérifier les calculs
faits « à la main » et montrer le bien fondé des méthodes employées. Il n'est pas toujours
nécessaire en effet, d'utiliser des moyens lourds pour effectuer la plupart des calculs
proposés. C'est de plus un bon moyen pédagogique pour bien appréhender les concepts mis
en œuvre.

J'ai l'intime conviction, de par les retours favorables des auditeurs et étudiants pendant
toutes ces années, que ce cours, qui couvre une grande partie de l'électronique au sens
général, sera extrêmement utile pour ceux dont la motivation d'apprendre est suffisante pour
l'appréhender, l'étudier et pratiquer les nombreux exercices qui y sont proposés.

















Table des matières

Chapitre 1. Théorie de l'information . .... ... ... ... .... ... ... .... ... ... . 15
1.1. Source d'information .... ... ... .... ... ... ... .... ... ... .... ... ... . 16
1.1.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 16
1.1.2. Transmission de l'information, code . ... ... ... .... ... ... .... ... ... . 16
1.1.3. Code à décodage unique . ... .... ... ... ... .... ... ... .... ... ... . 17
1.1.3.1. Codes à décodage unique.... ... ... .... ... ... ... .... ... ... . 17
1.1.3.2. Règle de reconnaissance d'un code à décodage unique... .... ... ... . 17
1.1.4. Codes instantanés ou irréductibles . ... ... ... .... ... ... .... ... ... . 19
1.1.4.1. Construction d'un code à l'aide d'un graphe . .... ... ... .... ... ... . 19
1.1.4.2. Conditions d'existence d'un code instantané. .... ... ... .... ... ... . 20
1.2. Codage de l'information . . ... ... .... ... ... ... .... ... ... .... ... ... . 21
1.2.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 21
1.2.2. Codage de l'information sur une voie sans bruit . . .... ... ... .... ... ... . 21
1.2.3. Définition de l'entropie ... ... .... ... ... .... ... ... ... .... ... ... . 23
1.2.3.1. Entropie comme mesure de la quantité d'information . . ... .... ... ... . 23
1.2.3.2. Entropie d'une source à deux états . ... ... .... ... ... .... ... ... . 24
1.2.3.3. Entropie d'une source uniforme ... ... ... .... ... ... .... ... ... . 25
1.2.3.4. Cas particulier du traitement binaire de l'information . . ... .... ... ... . 25
1.2.4. Propriétés de l'entropie . . ... .... ... ... .... ... ... ... .... ... ... . 26
1.2.4.1. Entropie d'un vecteur aléatoire . ... ... ... .... ... ... .... ... ... . 26
1.2.4.2. Entropie comme mesure de l'incertitude. .... ... ... ... .... ... ... . 28
1.2.5. Information mutuelle entre l'entrée et la sortie d'une voie... ... .... ... ... . 28
1.2.6. Capacité d'un canal de transmission ... ... ... .... ... ... .... ... ... . 29
1.2.7. Modélisation d'un canal de transmission bruité dans le cas discret . . . . . . . . . . 29
1.2.8. Exemple du canal binaire symétrique... ... ... .... ... ... .... ... ... . 31
1.3. Recherche des codes optimaux. . . .... ... ... ... .... ... ... .... ... ... . 32
1.3.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 32
1.3.2. Limite inférieure de n . Théorème du codage sans bruit ... ... .... ... ... . 32
1.3.3. Méthode de R.M. Fano .. ... .... ... ... .... ... ... ... .... ... ... . 34
1.3.4. Méthode de Huffman. ... ... .... ... ... .... ... ... ... .... ... ... . 35
1.3.5. Efficacité et redondance d'un code . ... ... ... .... ... ... .... ... ... . 36
1.3.6. Débit et vitesse de transmission ... ... ... .... ... ... ... .... ... ... . 37
1.4. Codage et espaces de signaux. Théorème de Shannon ... ... ... .... ... ... . 40
1.4.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 40
1.4.2. Construction de l'espace de signaux ... ... ... .... ... ... .... ... ... . 41
1.4.2.1. Transmission de l'information « utile » . . .... ... ... ... .... ... ... . 41
1.4.2.2. Bruit du canal de transmission . ... ... ... .... ... ... .... ... ... . 42
1.4.2.3. Représentation géométrique des signaux . . .... ... ... .... ... ... . 43
1.4.2.3.1. Application aux signaux binaires simples.... ... ... .... ... ... . 46
1.4.2.3.2. Application aux signaux composés ou mots binaires . . . . . . . 46
1.4.2.3.3. Application aux signaux orthogonaux . . .... ... ... .... ... ... . 47
1.4.2.4. Représentation du bruit. . .... ... ... ... .... ... ... .... ... ... . 47
1.4.2.5. Conclusion .... ... ... .... ... ... ... .... ... ... .... ... ... . 48
1.4.3. Critère de décision .. ... ... .... ... ... ... .... ... ... .... ... ... . 49
1.4.3.1. Cas du bruit n(t) nul . ... .... ... ... ... .... ... ... .... ... ... . 49
1.4.3.2. Cas où le bruit n(t) existe. .... ... ... ... .... ... ... .... ... ... . 50
1.4.4. Calcul des probabilités d'erreur .... ... ... .... ... ... ... .... ... ... . 55
1.4.4.1. Cas des signaux binaires simples N = 2. .... ... ... ... .... ... ... . 55
1.4.4.2. Cas des signaux binaires composés ... .... ... ... ... .... ... ... . 58
1.4.5. Source discrète séquentielle. . .... ... ... ... .... ... ... .... ... ... . 60
























10 Electronique pour le traitement du signal, volume 5
1.4.5.1. Comparaison du taux d'erreur de deux procédés de codage.
Codage binaire composé et codage binaire orthogonal ... ... ... .... ... ... . 62
1.4.6. Théorème de Shannon . . . . . . . .... ... ... .... ... ... ... .... ... ... . 64
1.4.6.1. Propriété de la capacité d'un canal de transmission ... ... .... ... ... . 69
1.4.6.2. Conclusion .... ... ... .... ... ... ... .... ... ... .... ... ... . 69
Chapitre 2. Théorie du codage .. ... .... ... ... .... ... ... ... .... ... ... . 71
2.1. Notions de codage. . .... ... ... .... ... ... .... ... ... ... .... ... ... . 72
2.1.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 72
2.1.2. Types de codages .. ... ... .... ... ... ... .... ... ... .... ... ... . 72
2.1.3. Codage des mots numériques .... ... ... .... ... ... ... .... ... ... . 72
2.1.4. Classement adopté .. ... ... .... ... ... ... .... ... ... .... ... ... . 73
2.2. Rappels d'algèbre linéaire. Corps de Galois. Préalables mathématiques . . . . . . . . . 74
2.2.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 74
2.2.2. Loi de composition interne sur un ensemble E (espace) ... ... .... ... ... . 74
2.2.3. Monoïde .. ... .... ... ... .... ... ... ... .... ... ... .... ... ... . 74
2.2.4. Groupe ... ... .... ... ... .... ... ... ... .... ... ... .... ... ... . 74
2.2.5. Groupe quotient .... ... ... .... ... ... ... .... ... ... .... ... ... . 75
2.2.6. Anneau ... ... .... ... ... .... ... ... ... .... ... ... .... ... ... . 75
2.2.7. Idéal . . ... ... .... ... ... .... ... ... .... ... ... ... .... ... ... . 75
2.2.8. Anneau quotient. Classes résiduelles... ... ... .... ... ... .... ... ... . 76
2.2.9. Corps de Galois .... ... ... .... ... ... ... .... ... ... .... ... ... . 77
2.2.10. Préalables mathématiques simplifiés . . ... ... .... ... ... .... ... ... . 78
2.3. Etude des codes en blocs (Hamming, BCH, Reed Salomon) ... ... .... ... ... . 82
2.3.1. Généralités sur les codes. ... .... ... ... ... .... ... ... .... ... ... . 82
2.3.2. Définitions : détection, correction d'erreurs . . .... ... ... ... .... ... ... . 82
2.3.3. La métrique de Hamming. ... .... ... ... ... .... ... ... .... ... ... . 83
2.3.4. Codes linéaires .... ... ... .... ... ... ... .... ... ... .... ... ... . 84
2.3.4.1. Extension aux espaces vectoriels .. ... ... .... ... ... .... ... ... . 85
2.3.4.2. Notion de code systématique et de matrice G réduite. . ... .... ... ... . 86
2.3.4.3. Indépendance des vecteurs de base ... .... ... ... ... .... ... ... . 87
2.3.4.4. Orthogonalité... ... ... .... ... ... ... .... ... ... .... ... ... . 87
2.3.4.5. Matrice de contrôle ou parity check matrice . .... ... ... .... ... ... . 88
2.3.4.6. Notion de syndrome . ... .... ... ... ... .... ... ... .... ... ... . 89
2.3.4.7. Notion d'erreur (vecteur (e)) ... ... ... .... ... ... ... .... ... ... . 90
2.3.4.8. Notion de tableau de décodage (standard array) . . . . . . . . .... ... ... . 91
2.3.4.9. Code parfait ... ... ... .... ... ... ... .... ... ... .... ... ... . 93
2.3.4.10. Distance minimale. Bornes pour les codes linéaires.
Probabilité d'erreur sur les mots. . .... ... ... ... .... ... ... .... ... ... . 93
2.3.4.11. Précisions sur les propriétés précédentes. Exemple. . ... .... ... ... . 99
2.3.5. Codes de Hamming . ... ... .... ... ... .... ... ... ... .... ... ... 102
2.3.5.1. Codes de Hamming étendus. Codes optimaux de distance d = 4 . . . . . . . 105
2.4. Les codes cycliques (ou codes CRC) . . . . . . . . . .... ... ... ... .... ... ... 106
2.4.1. Introduction et formalisme . . . .... ... ... ... .... ... ... .... ... ... 106
2.4.2. Les circuits associés aux codes cycliques... .... ... ... ... .... ... ... 112
2.4.2.1. Circuit de multiplication de polynômes .. .... ... ... ... .... ... ... 113
2.4.2.2. Circuit de division de polynômes... ... ... .... ... ... .... ... ... 115
2.4.2.3. Utilisation de ces circuits en algèbre modulo 2 ... ... ... .... ... ... 116
2.4.3. Encodage des codes cycliques.... ... ... .... ... ... ... .... ... ... 118
2.4.4. Décodage des codes cycliques. Décodeur de Meggitt . ... ... .... ... ... 122
2.4.5. Relation entre polynôme générateur et matrice génératrice des codes en bloc . 123
2.4.6. Les codes BCH ( Bose, Chandhuri, Hocquenghem) ... ... ... .... ... ... 125
2.4.7. Les codes de Reed Salomon (RS).. ... ... .... ... ... ... .... ... ... 129
2.4.8. Codes pour détection d'erreurs en paquet... .... ... ... ... .... ... ... 130
2.5. Les codes convolutifs ou récurrents .... ... ... .... ... ... ... .... ... ... 131



























Table des matières 11
2.5.1. Définition.. ... .... ... ... .... ... ... ... .... ... ... .... ... ... 131
2.5.2. Le codage . .... ... ... ... .... ... ... .... ... ... ... .... ... ... 132
2.5.3. Matrice génératrice . . ... ... .... ... ... ... .... ... ... .... ... ... 133
2.5.4. Représentations .... ... ... .... ... ... ... .... ... ... .... ... ... 134
2.5.4.1. Représentation sous forme d'arbre . ... ... .... ... ... .... ... ... 136
2.5.4.2. Représentation sous forme de treillis... .... ... ... ... .... ... ... 137
2.5.5. Décodage . .... ... ... ... .... ... ... .... ... ... ... .... ... ... 138
2.5.5.1. Algorithme de Viterbi ... .... ... ... ... .... ... ... .... ... ... 138
2.5.5.2. Décodage séquentiel . . . .... ... ... ... .... ... ... .... ... ... 141
2.5.6. Notion de codes catastrophiques... ... ... .... ... ... ... .... ... ... 144
2.5.7. Notion de distance dans les codes convolutifs ... .... ... ... .... ... ... 145
2.5.8. Exemple pratique de code spécifié . ... ... ... .... ... ... .... ... ... 146
2.5.9. Conclusion ... .... ... ... .... ... ... .... ... ... ... .... ... ... 146
2.6. Les turbo codes ... .... ... ... .... ... ... .... ... ... ... .... ... ... 147
2.7. Procédé d'entrelacement . ... ... .... ... ... .... ... ... ... .... ... ... 147
2.8. Construction des codes . . ... ... .... ... ... ... .... ... ... .... ... ... 148
2.8.1. Construction à partir d'un code C(n, m, d) ... .... ... ... ... .... ... ... 149
2.8.2. Constructions combinant deux codes... ... ... .... ... ... .... ... ... 150
2.9. Aide à la décision. Systèmes experts ... ... ... .... ... ... ... .... ... ... 152
2.9.1. Une organisation possible des critères de choix. . .... ... ... .... ... ... 154
2.9.2. Exemples de règles.. ... ... .... ... ... ... .... ... ... .... ... ... 157
2.9.3. Conclusion ... .... ... ... .... ... ... .... ... ... ... .... ... ... 158
Chapitre 3. Signal analogique, signal numérique. Applications en télécommunications 161
3.0. Introduction ... ... .... ... ... .... ... ... ... .... ... ... .... ... ... 162
3.1. Généralités. ... ... .... ... ... .... ... ... ... .... ... ... .... ... ... 168
3.2. Source analogique échantillonnée . .... ... ... ... .... ... ... .... ... ... 169
3.2.1. Source analogique permanente . . . . . . . . . .... ... ... ... .... ... ... 169
3.2.2. Source analogique échantillonnée idéale . . . .... ... ... ... .... ... ... 170
3.2.3. Source analogique échantillonnée pratique (discrétisation du temps) . . . . . . . 172
3.2.4. Source discrète analogique (discrétisation de l'amplitude) .. ... .... ... ... 173
3.3. Source discrète binaire (transformation du concret à l'abstrait) . . ... .... ... ... 175
3.3.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... 175
3.3.2. Conversion A/N avec codage PCM . ... ... ... .... ... ... .... ... ... 176
3.3.3. Conversion A/N avec codage redondant. ... ... .... ... ... .... ... ... 176
3.3.4. Généralités sur le codage détecteur et correcteur d'erreur. . . . . .... ... ... 177
3.4. Théorie de l'échantillonnage . . . . . .... ... ... .... ... ... ... .... ... ... 178
3.4.1. Définition.. ... .... ... ... .... ... ... ... .... ... ... .... ... ... 178
3.4.2. Exemple d'échantillonnage analogique par suiveur ... ... ... .... ... ... 182
3.4.3. Cas de l'échantillonnage avec maintien . ... ... .... ... ... .... ... ... 183
3.4.4. Problème des erreurs d'échantillonnage . . . . . . . .... ... ... .... ... ... 185
3.4.4.1. Recouvrement des spectres ou erreur d'aliassage. ... ... .... ... ... 185
3.4.4.2. Erreur dans le processus de reconstitution .. .... ... ... .... ... ... 187
3.4.5. Echantillonnage dans le domaine des fréquences .... ... ... .... ... ... 191
3.4.6. Eclonnage des fonctions passe-bande . .... ... ... ... .... ... ... 192
3.4.7. Echantillonnage stroboscopique . . . . . . . . . .... ... ... ... .... ... ... 197
3.5. Quantification .. ... .... ... ... .... ... ... ... .... ... ... .... ... ... 198
3.5.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... 198
3.5.2. Loi de quantification uniforme . .... ... ... ... .... ... ... .... ... ... 200
3.5.2.1. Rapport signal à bruit du quantificateur uniforme.. ... ... .... ... ... 201
3.5.2.2. Notion de dynamique de codage .. ... ... .... ... ... .... ... ... 202
3.5.3. Loi de quantification non uniforme ou non linéaire .... ... ... .... ... ... 203
3.5.3.1. Analyse des différents types d'erreurs . . .... ... ... ... .... ... ... 203
3.5.3.2. Loi de compression idéale .... ... ... .... ... ... ... .... ... ... 204
3.5.3.3. Loi de compression de type μ.. ... ... .... ... ... ... .... ... ... 205























12 Electronique pour le traitement du signal, volume 5
3.5.3.4. Loi de compression de type A (ou à 13 segments). ... ... .... ... ... 206
3.5.3.5. Rapport signal à bruit de quantification (distribution uniforme du bruit) . . . 208
3.5.3.6. Comparaison des rapports signaux à bruit . . .... ... ... .... ... ... 210
3.6. Types de transmissions . . ... ... .... ... ... ... .... ... ... .... ... ... 211
3.6.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... 211
3.6.2. Types de codages PCM. . ... .... ... ... .... ... ... ... .... ... ... 213
3.6.2.1. Codes linéaires . ... ... .... ... ... .... ... ... ... .... ... ... 215
3.6.2.2. Codes non linéaires . ... .... ... ... ... .... ... ... .... ... ... 215
3.6.2.3. Conclusion .... ... ... .... ... ... ... .... ... ... .... ... ... 215
3.6.3. Codage des mots numériques .... ... ... .... ... ... ... .... ... ... 216
3.6.3.1. Codes pondérés ... ... .... ... ... .... ... ... ... .... ... ... 216
3.6.3.2. Codes non pondérés ... .... ... ... ... .... ... ... .... ... ... 217
3.6.4. Codes alphanumériques . ... .... ... ... ... .... ... ... .... ... ... 222
3.6.5. Rappel sur le codage de canal avec détection et correction d'erreur . . . . . . . . 223
3.7. Limitations des transmissions dues au canal de transmission ... ... .... ... ... 224
3.7.1. Transmission idéale . ... ... .... ... ... .... ... ... ... .... ... ... 224
3.7.1.1. Cas analogique. ... ... .... ... ... .... ... ... ... .... ... ... 224
3.7.1.2. Cas numérique . ... ... .... ... ... .... ... ... ... .... ... ... 225
3.7.2. Codage de source et codage de canal . . ... ... .... ... ... .... ... ... 225
3.7.2.1. Pour la source d'information... ... ... .... ... ... ... .... ... ... 225
3.7.2.2. Pour le canal de transmission . ... ... ... .... ... ... .... ... ... 229
3.7.3. Conditions de transmission du canal ... ... ... .... ... ... .... ... ... 230
3.7.3.1. Notion de bande passante.... ... ... .... ... ... ... .... ... ... 230
3.7.3.2. Résolution dans le temps. Premier théorème de Nyquist . . .... ... ... 231
3.7.3.3. Résolution en amplitude. Théorème de Shannon . ... ... .... ... ... 232
3.7.3.4. Condition de transmission. Adaptation au canal de transmission . . . . . . . 232
3.7.4. Les différents critères de Nyquist relatifs à l'interférence intersymbole. . . . . . . 234
3.7.4.1. Signaux numériques. ... .... ... ... ... .... ... ... .... ... ... 234
3.7.5. Interférence entre symboles .. .... ... ... ... .... ... ... .... ... ... 239
3.7.5.1. Mesure de l'interférence intersymbole . . .... ... ... ... .... ... ... 241
3.7.5.2. Premier critère de Nyquist .... ... ... .... ... ... ... .... ... ... 241
3.7.5.3. Deuxième critère de Nyquist .. ... ... .... ... ... ... .... ... ... 243
3.7.5.4. Critère de Nyquist élargi . .... ... ... ... .... ... ... .... ... ... 244
3.7.6. Egalisation et Diagramme de l'œil . . ... ... .... ... ... ... .... ... ... 246
3.7.6.1. Egaliseur temporel à filtre transversal .. .... ... ... ... .... ... ... 247
3.7.6.2. Diagramme de l'œil . ... .... ... ... ... .... ... ... .... ... ... 248
3.8. Transmissions numériques en bande de base ... .... ... ... ... .... ... ... 249
3.8.1. Généralités ... .... ... ... .... ... ... .... ... ... ... .... ... ... 249
3.8.2. Occupation spectrale d'un mode ou « code » de transmission . . .... ... ... 250
3.8.2.1. Représentation des digits et des mots .. .... ... ... ... .... ... ... 250
3.8.2.2. Distribution spectrale des divers modes . .... ... ... ... .... ... ... 252
3.8.3. Types de modes ou « codes » usuellement utilisés ... ... ... .... ... ... 255
3.8.3.1. Types de signaux temporels utilisés ... .... ... ... ... .... ... ... 255
3.8.3.2. Mode NRZ (sans retour à zéro) ... ... ... .... ... ... .... ... ... 256
3.8.3.3. Mode RZ (avec retour à zéro) . ... ... ... .... ... ... .... ... ... 257
3.8.3.4. Mode Biphase (Bi Φ) appelé aussi mode Manchester . . ... .... ... ... 260
3.8.3.5. Mode de Miller.. ... ... .... ... ... ... .... ... ... .... ... ... 262
3.8.3.6. Autres formes de modes . .... ... ... ... .... ... ... .... ... ... 263
3.8.3.7. Modes bipolaires ou type AMI (Alternate marked inversion) .... ... ... 263
3.8.3.8. Mode bipolaire entrelacé . .... ... ... ... .... ... ... .... ... ... 264
3.8.4. Modes à haute densité HDB (high density bipolar code) ... ... .... ... ... 265
3.8.5. Comparaison des différents modes usuels évoqués ... ... ... .... ... ... 267
3.8.5.1. Densités de puissance ou spectres en fréquence . ... ... .... ... ... 267
3.8.5.2. Efficacité d'un mode . ... .... ... ... ... .... ... ... .... ... ... 267
3.8.5.3. Choix d'un mode ... ... .... ... ... .... ... ... ... .... ... ... 268




























Table des matières 13
3.9. Modulation analogiques discrètes. Transmission en bande translatée .... ... ... 269
3.9.1. Rappel sur les types de modulations ... ... ... .... ... ... .... ... ... 269
3.9.2. Modulation d'une sous porteuse ... ... ... .... ... ... ... .... ... ... 271
3.9.2.1. Modulation de fréquence FM à déplacement de fréquence
(FSK = frequency shift keying)... .... ... ... ... .... ... ... .... ... ... 271
3.9.2.2. Modulation de phase PM à déplacement de phase
(PSK = phase shift keying) .. ... .... ... ... .... ... ... ... .... ... ... 274
3.9.3. Modulation directe d'une porteuse .. ... ... .... ... ... ... .... ... ... 277
3.9.3.1. Modulation directe de phase .. ... ... .... ... ... ... .... ... ... 277
3.9.3.2. Modulation directe de fréquence FM . . . .... ... ... ... .... ... ... 281
3.9.4. Première conclusion sur les types de codage et de modulation . .... ... ... 282
3.9.5. Modulations discrètes m-aire . .... ... ... ... .... ... ... .... ... ... 283
3.9.5.1. Modulation mixte d'amplitude et de phase A+PSK . ... ... .... ... ... 285
3.9.5.2. Modulation en quadrature QAM ... ... ... .... ... ... .... ... ... 286
3.9.6. Démodulations discrètes m-aire. .. . ... .. . . .. . . . .. . .... . .........287
3.9.6.1. Démodulation par déplacement de fréquence (FSK) m-aire ..87
3.9.6.2. Démodulation par déplacement de phase (FSK) m-aire. . . . . . . . . . . . . . 290
3.10. Systèmes de transmission à modulation digitale . .... ... ... ... .... ... ... 293
3.10.1. Introduction . . .... ... ... .... ... ... .... ... ... ... .... ... ... 293
3.10.2. Principe du multiplexage temporel . ... ... ... .... ... ... .... ... ... 293
3.10.3. Organisation du message... .... ... ... ... .... ... ... .... ... ... 294
3.10.4. Réception, décommutation .. .... ... ... ... .... ... ... .... ... ... 297
3.10.4.1. Circuit d'identification des digits. Transmission en bande de base . . . . . 297
3.10.4.2. Transmission avec porteuse. Réception en bande translatée. . . . . . . . . 302
3.10.4.2.1. Démodulation de phase PM (type PSK).... ... ... .... ... ... 302
3.10.4.2.2. Démodulation de fréquence FM (type FSK) . ... ... .... ... ... 303
3.10.4.2.3. Comparaison PSK, FSK . ... ... ... .... ... ... .... ... ... 306
3.11. Récupération des rythmes d'horloge... ... ... .... ... ... ... .... ... ... 307
3.11.1. Généralités . . .... ... ... .... ... ... .... ... ... ... .... ... ... 307
3.11.2. Boucle d'estimation d'un signal ... ... ... .... ... ... ... .... ... ... 310
3.11.2.1. Boucle d'asservissement de phase analogique (PLL) . . . . .... ... ... 310
3.11.2.1.1. Phasemètre d'entrée équivalent .. .... ... ... ... .... ... ... 312
3.11.2.1.2. Générateur de signal sinusoïdal .. .... ... ... ... .... ... ... 313
3.11.2.2. Mise en équation dans le cas général . .... ... ... ... .... ... ... 316
3.11.2.2.1. Equation linéarisée .... ... ... .... ... ... ... .... ... ... 316
3.11.2.2.2. Fonctionnement dans le domaine linéaire .. ... ... .... ... ... 321
3.11.2.2.3. Equations non linéarisées. Caractéristique d'accrochage . . . . . . . . 333
3.11.2.3. Dispositifs d'aide à l'acquisition... ... ... .... ... ... .... ... ... 342
3.11.3. Variantes numériques .. ... .... ... ... .... ... ... ... .... ... ... 342
3.11.3.1. Exemple pour la modulation de phase à deux états MDP2 .... ... ... 343
3.11.3.2. Exemple pour la modulation de phase à quatre états MDP4 . . . . . . . . . 346
3.11.3.3. Notion de codage différentiel . ... ... ... .... ... ... .... ... ... 346
3.11.4. Conclusion... .... ... ... .... ... ... .... ... ... ... .... ... ... 351
3.12. Décommutation du message. Restitution des mots .. .... ... ... .... ... ... 351
3.12.1. La synchronisation primaire . .... ... ... ... .... ... ... .... ... ... 351
3.12.2. Synchronisation secondaire . .... ... ... ... .... ... ... .... ... ... 354
3.12.3. Stratégie d'acquisition de la synchronisation ... .... ... ... .... ... ... 371
3.12.4. Conclusion... .... ... ... .... ... ... .... ... ... ... .... ... ... 372
Exercices et corrigés . .. . .... . .................... . .... . .. . . . .. . . .373

Bibliographie générale ............. . .... . .. . . . .. . . .. . . . .. . ........487

Index .... . .................... . .... . .. . . . .. . . .. . . . .. . .... . ....491

































Chapitre 1

Théorie de l'information




Ce chapitre est une introduction à la théorie de l'information, à travers la définition de
l'entropie et/ou d'Incertitude attachée à un message, ainsi que les divers paramètres et
mesures associés au modèle du canal sans bruit symétrique.
Le codage de source sera approché avec les méthodes de Huffman et Fano. Le canal
bruité sera étudié avec l'approche géométrique et vectorielle des signaux pour déboucher
sur le théorème de Shannon du canal bruité.
Les aspects taux d'erreurs, ainsi que échange bande passante, rapport signal à bruit
seront abordés, ainsi que la théorie du récepteur optimum.











16 Electronique pour le traitement du signal, volume 5
[26, 29, 32, 33, 34, 35, 43]1.1. Source d'information
1.1.1. Généralités
Une source d'information est un modèle de représentation mathématique d'un processus
susceptible « d'engendrer de l'information ». Cette information n'a d'utilité que dans la
mesure où elle permet un échange de connaissance entre (au moins) deux correspondants
de manière à permettre au récepteur de « prendre une décision signifiante ».
Le modèle utilisé peut se schématiser de la manière suivante :

S = {s ,…. ,s ) A = {a1, …. ,aN) 1 q

c S(t,c) m X(t ˆ ˆc m K S C E R D


Récepteur DécodeurEmetteur Canal Source Codeur
d'information
ou de
messages fig.1.1. Modèle de canal de communication

S = Source de messages m = message
C = Codeur c = message codé
E = Emetteur S(t,c) = signal émis
K = Canal X(t) = signal reçu ou observé
R = Réception cˆ = signal démodulé
D = Décodage mˆ = message décodé estimé

La source est assimilée à une variable aléatoire S susceptible de prendre un certain
nombre de valeurs ou d'états « s » avec la probabilité « p ». On admet donc dans un i i
premier temps que pour l'ensemble des états « finis » ou « dénombrables », on a un
ensemble complet soit :
p = 1 (1.1) ∑ i
i
L'ensemble S = {s ,s ,.......,s ,.......,s } est l'Alphabet de la source, et un message est 1 2 i q
formé d'une Séquence d'états « s » de longueur donnée n. Les états s peuvent être i i
considérés comme des messages indépendants.

Exemple : m = s s s 1 1 2 1
m = s s 2 4 3

1.1.2. Transmission de l'information, code
Considérons un ensemble A = {a ,a ,......,a } contenant un nombre N d'éléments a . i1 2 N
L'ensemble A est donc appelé « Alphabet », les éléments a des « Symboles », N est fini ou i
dénombrable. Le rôle du codeur est d'assigner à chaque état s, une séquence de symboles i
et donc aussi à chaque message m . i
Pour cela le codeur dispose de l'alphabet {A} de base N. Une telle séquence est alors
appelée mot du code (ou mot code), l'ensemble des mots code constitue ce que l'on appelle
le code. Théorie de l’information 17
Exemple : S ={}s ,s ,s ,s A = {a ,a ,......,a } 1 2 3 4 1 2 N
s est un état a est un symbole ii ii
m = s s s est un message de séquence s s s et de longueur n = 3 1 1 2 1 1 2 1
s=→a a mot code de séquence a a ⎫112 12
⎪sa=21 ⎪ code⎬
sa=32 ⎪
⎪sa= aa4212 ⎭
On définit alors dans la séquence s s = a a par exemple : 23 1 2
⎧a = préfixe de a12

a = suffixe de a⎩21

1.1.3. Code à décodage unique
Un code à décodage unique est un code formé de telle manière qu'à tout message émis
ne corresponde qu'une et qu'une seule séquence de symboles du code.
Pour obtenir un code à décodage unique, il faut et il suffit qu'à toute séquence de
message de la source de longueur n, ne corresponde qu'une et une seule séquence de
symbole du code.

NB : La définition d'un code à décodage unique n'implique pas l'égalité de la longueur des
mots du code.

Exemple : Soit le code suivant :
états de la source code avec {A } = {0,1 } messages
s 1 m = s s s → 10011 1 1 2 1
s 00 m = s s → 1001 2 2 4 3
s 01
3
s 104
Donc ce code n'est pas à décodage unique.

1.1.3.1. Codes à décodage unique
Exemple :
états de la source code avec {A } = {0,1 } états de la source code avec {A } = {0,1 }
s 00 s 01 1
s 01 s 01 2 2
s 11 s 0113 3
s 10 s 01114 4

1.1.3.2. Règle de reconnaissance d'un code à décodage unique
Pour reconnaître si un code est à décodage unique on forme à partir de ce code les suites
de séquences notées C , C , C , ……… ,C , en opérant comme suit, avec : 0 1 2 n
Séquences appartenant à C : 0
- C'est la suite des mots du code C = c , c , c ,………… 0 01 02 0318 Electronique pour le traitement du signal, volume 5
Séquence appartenant à C : 1
- On compare les mots du code deux a deux, si l'un des mots du code c est préfixe d’un 0i
autre mot du code, on place son suffixe dans la suite C . 1

Séquences appartenant à la suite C : n
- Si dans la suite C , une séquence c admet un mot du code comme préfixe tel que : n-1 (n-1)j
c = c b, alors on place le suffixe b dans la suite C . (n-1)j 0i n
- Si dans la suite C , une séquence c est préfixe d'un mot du code tel que : n-1 (n-1)i
c = c c, alors on place le suffixe c dans la suite C . 0j (n-1)i n

Le processus s'arrête à la suite C dès que la suite C ne peut plus être formée, et alors m m+1
la règle est la suivante :

Règle : Un code est à décodage unique SSI aucune des suites C ,C ,…..,C 1 2 m
obtenues ne contient un mot du code.

D’où le tableau général suivant des suites C ,C ,…..,C 0 1 m
C C .................... C C
0 1 n −1 n
c c ↓ c
01 11 n1
c c ↓ ↓02 12
↓ ................................................ c ........ ↓(n −1)i

↓ ↓ ↓ ↓
↓ ↓ c b → b(n −1)j
c = c c.................................................... → c
0j (n −1)i
c = c a → a0k 0i

Exemple : Rechercher si le code C = a, ae, b, bc, bdd, ced, dbe, ddace, eed, est à 0
décodage unique. Formons le tableau des suites C , C , ..., C . 0 1 n

C C C C C C C C 0 1 2 3 4 5 6 7
a e ed ce d be e ed

a e c ace dace

b dd

b c

b d d

c e d

d b e

d d a c e

e e d

Théorie de l’information 19
Ce code est donc à décodage unique puisque dans les séquences des suites C , C , C , 1 2 3
C , C , C , C , on ne retrouve pas les mots du code. Après C , les suites sont vides donc 4 5 6 7 7
arrêt.

NB : On remarque que pour ce type de code, il faut attendre la fin du message pour pouvoir
décoder. Ce qui pénalise la vitesse de transmission.

1.1.4. Codes instantanés ou irréductibles
Un code est dit instantané si on peut décoder chaque mot du code sans avoir à se référer
à d'autres symboles qu'à ceux qui le compose. Pour qu'un code soit instantané, il faut que la
juxtaposition ou concaténation de deux mots du code c et c , ne donne pas un mot du code 1 2
c = c c , et donc évidemment qu'aucun mot du code ne soit préfixe d'un autre mot du code. 3 1 2

1.1.4.1. Construction d'un code à l'aide d'un graphe

Soit A ={}a ,a ,......,a l'ensemble des symboles de l'alphabet. Cet ensemble peut 1 2 N
toujours être remplacé par l'ensemble suivant :
A = {0,1,2,3.......,i,......,N − 1 } (N = base du code)
On peut alors représenter par un graphe la suite de tous les mots du code. Le nombre N
des symboles de l'alphabet est « l'ordre » du graphe ou de l'arbre, la longueur maximale n
des mots du code est sa « taille ». La figure suivante donne deux exemples d'arbres avec :

- Les différents sommets du graphe sont les mots du code.
- Un sommet représentant un mot de longueur (i - 1) étant lié par une arête à un sommet
de longueur i, si les (i - 1) symboles du sommet i sont égaux à ceux du premier et placés
dans le même ordre.

On a donc tous les choix possibles pour construire un code donné, avec une solution
donnée par l'exemple suivant.

000 xExemple : 0000
a = 0 1 xx 01 001 x 02
a = 0 x1 010 x
10 x
a = 1 2 11x 01 011 x
12

100 x1020 xa = 2 3 x 21 101 x
22 x a2 = 1 110 x

x
ordre 3 111 ordre 3 11 x


taille 1 taille 2 ordre 2 ordre 2 ordre 2


taille 1 taille 2 taille 3

fig.1.2. Exemple de représentation d'un code sous forme de graphe 20 Electronique pour le traitement du signal, volume 5
1.1.4.2. Conditions d'existence d'un code instantané

Supposons donné, un code instantané de base N (nombre de symboles de l'alphabet
{A}). Les mots du code ayant des longueurs n ≤ n ≤ n ........ ≤ n . Chaque mot du code 1 2 3 M
peut être identifié à un sommet d'un arbre de taille n = M (longueur maximale d'un mot du M
code) et d'ordre N. Or, puisque aucun mot du code ne doit être le préfixe d'un autredu
code, dès qu'un mot du code à été choisi sur une branche, il n'est plus possible de choisir
d'autres mots du code sur des arêtes incidentes au sommet représentant le mot choisi.

Exemple :

x00 X
x
0 x 010X
x
011 01 X
x
x
x
1 X x
x
x

taille M

(n −n )M i On peut donc dire que tout mot code choisi de longueur n exclut N sommets i
terminaux de l'arbre, c'est-à-dire les séquences de longueurs supérieures à n . Pour le code i
donné, le total des sommets terminaux exclus sont donc au nombre de :
M
n −nM iN avec : n ≤ n ∑ i M
i =1
nMLe nombre total de sommets d'un arbre de taille n = M, étant: N , Il faut donc que le M
nombre de sommets disponibles soit supérieur au nombre de mots code choisi, donc :
M
n −n nM i MN ≤ N∑
i =1

M
−n
iSoit : N ≤ 1 (1.2)∑
i =1
La classe des codes instantanés constitue une sous classe de celle des codes à
décodage unique. Il est en effet évident qu'un code instantané est à décodage unique , mais
l'inverse n'est pas vrai. Il en résulte que la condition (1.2) précédemment établie pour les
codes instantanés, est une condition nécessaire pour les codes à décodage unique. On
montre aussi qu'elle est suffisante.
Donc on sait construire de tels codes si la relation (1.2) est vérifiée. C'est la « condition de
Kraft-Mac-Milan ».

Exemple : On veut coder les dix états d'une source d'information S = {s , s ,………, s } à 1 2 10
l'aide d'un alphabet ternaire A = {0 , 1 , 2 } avec les contraintes suivantes :
- Un mot seulement de longueur 1 et au maximum 3 mots de longueur maximale 3.
Cette opération est-elle possible ?
Théorie de l’information 21
- Combien d'états de la source peut-on effectivement coder au maximum ?
Construisons donc un arbre d'ordre 3 et de taille 3. On a par exemple :

0 X
10X
111 Xx
12X

20X
22021 X2 x X
221Xx
222X

Donc on ne peut coder que 9 états de S et pas 10 comme demandé, avec :
9
−n −n −n −ni 1 2 93 = 3 + 3 + ............. + 3∑
i =1
avec : n = 1 , n = n = ..... = n = 2 , n = n = n = 3 1 2 3 6 7 8 9
9 1 5 3 9 + 15 + 3−n −1 −2 −3isoit : 3 = 3 + 5 ⋅ 3 + 3 ⋅ 3 = + + = = 1∑ 2 33 273 3i =1
Donc pour 9 états le code choisi est unique.

NB : On a bien sûr plusieurs solutions équivalentes possibles.

1.2. Codage de l'information
1.2.1. Généralités
On a vu que l'opération de codage consiste à affecter à chaque état s de la source une i
« séquence de n symboles » de l'alphabet de base N du code choisi. Il est nécessaire que le i
code obtenu soit à décodage unique, afin de pouvoir discerner les différents messages. De
plus chaque état s et donc chaque séquence de n symboles a la probabilité p d'apparaître. i i i

1.2.2. Codage de l'information sur une voie sans bruit
Ayant défini une séquence n pour chaque mot code et connaissant la probabilité i
d'apparition p de ces mots code, il est possible de déterminer la longueur moyenne des mots i
code par la moyenne d'ensemble suivante :
M
n = E[n ] = np (1.3) i ∑ i i
i =1
Si l'on suppose le code à décodage unique, il est évident que la plus grande vitesse de
ntransmission sera obtenue lorsque sera minimum, ce qui revient à minimiser la fonction
suivante :
F(n ) = n = n p + n p + n p + ............ + n p i 1 1 2 2 3 3 1 1

Ceci sous la contrainte du code à décodage unique de la relation (1.2), qui peut s'exprimer
sous la forme suivante :
−n −n −n −n1 2 3 MG(n ) = N + N + N + ............N −1 ≤ 0 j22 Electronique pour le traitement du signal, volume 5
Ce minimum (ou maximum) peut être obtenu en annulant les premières dérivées de
l'expression suivante (méthode du multiplicateur de Lagrange) :
Ψ(n ) = F(n ) − λG(n ) i i j
où λ est un paramètre arbitraire qui s'élimine en utilisant l'équation de la contrainte G(n) j
( λ est appelé multiplicateur de Lagrange). On obtient donc le système d'équations relatif aux
dérivées partielles suivant :
⎧d Ψ −n1= p + λN LogN = 01⎪dn1⎪
⎪ d Ψ −n2 −n⎪ = p + λN LogN = 0 i2 d()N⎪ -n −nLogN −nLogN ni i i idn(S) = avec : N = e → = −LogNe = −N LogN2 ⎨
dni⎪............................................⎪
⎪ d Ψ −nM⎪ = p + λN LogN = 0M⎪dnM⎩

Chacune des dérivées devant être nulle simultanément, on peut écrire la condition sous la
forme condensée suivante :
M M
−njp + λLogN ⋅ N = 0j∑ ∑
j =1 j =1
M - 1
et puisque l'ensemble est complet : p = 1, il vient : λLogN =∑ i M
−njj =1 N∑
j =1
Le système d'équation (S) donne alors les conditions à remplir pour minimiser la fonction
Mp −n-n i jiF(n ) pour chaque n , par : N = − = p ⋅ Ni i i ∑λLogN
j =1
Pour chacun des i avec : 1 ≤ i ≤ M, la variable inconue n donne (avec Logx/LogN = log x) :i N
M M⎛ ⎞ ⎛ ⎞
−n −nj j⎜ ⎟ ⎜ ⎟-n = log p ⋅ N → −n = log p + log N
i N i ∑ i N i N ∑⎜ ⎟ ⎜ ⎟
j =1 j =1⎝ ⎠ ⎝ ⎠
M M⎡ ⎤⎛ ⎞
−nj⎜ ⎟La relation (3) pour n minimum s'écrira donc : n = − ⎢log p + log N ⎥ ⋅ pmin∑∑N i N i⎜ ⎟⎢ ⎥i==1 j 1⎝ ⎠⎣ ⎦
M M M⎛ ⎞−n
j⎜ ⎟Soit : n = − p log p − log N pmin ∑ i N i N ∑ ∑ i⎜ ⎟ i =1 j =1 i =1⎝ ⎠
M M M⎛ ⎞−n
j⎜ ⎟Comme : p = 1 il vient : n = − p log p − log N∑ i min ∑ i N i N ∑⎜ ⎟
i =1 i =1 j =1⎝ ⎠
M
−njOr par hypothèse la relation (1.2) donne: N ≤ 1, car par hypothèse il faut que le code ∑
j =1
soit à décodage unique. Théorie de l’information 23
M⎛ ⎞
−nj⎜ ⎟Donc il vient: − log N ≥ 0. On peut alors écrire n sous la forme de l'inégalité N ∑ min⎜ ⎟
j =1⎝ ⎠
M
− p logp∑ i i M
i =1suivante : n ≥ − p log p min ∑ 1 N ilogN
i =1
M
−njLe minimum minimorum est alors obtenu pour n avec un code tel que: N = 1, et m.min ∑
j =1
alors on a l'égalité dans l'expression précédente, avec :
m
n = − p log p m.min ∑ i N i
i =1
L'étude de la concavité de la courbe montre alors que c'est bien un minimum.

1.2.3. Définition de l'entropie
Par définition « l'entropie d'une source S notée H(S), est une mesure du plus petit nombre
de symboles qui représente en moyenne chaque état codé », on écrira donc :
M
n > n = H(S) = − p log pm.min ∑ i N i
i =1

M M 1
Soit : H(S) = − p log p = p log (1.4)∑ i N i ∑ i N p
i =1 i =1 i

L'unité de mesure de l'entropie est le Shannon/état = [Sh/état]

NB : Bien entendu cette notion peut s'appliquer à tout ensemble fini d'éléments
probabilisables.

1.2.3.1. Entropie comme mesure de la quantité d'information

Il existe une autre approche de la définition de l'Entropie basée sur la « notion subjective
d'information ». En effet, on peut intuitivement admettre que le contenu informationnel d'un
message est d'autant plus important, que ce dernier nous « surprend » d'autant plus qu'il
contient une grande part « d'incertitude ». Lorsqu'on connaît à l'avance ce que l'on va nous
dire on ne gagne aucune information !
Pour des raisons mathématiques l'ingénieur des télécommunications américain Shannon
a proposé de mesurer la « quantité d'information H a priori », attachée à un message ou un i
symbole i particulier par la fonction suivante :
⎛ 1 ⎞
H = log ⎜ ⎟ = −log[]prob(i) = −log[p]i 2 2 2 i⎜ ⎟prob(i) ⎝ ⎠
prob(i) = probabilité associée au message ou au symbole (i).
Le choix de cette mesure à été dicté entre autres par les aspects mesure suivants :
- L'information doit être d'autant plus grande que la probabilité est petite.
- La mesure de l'information doit être une fonction croissante continue.
- On doit mesurer l'information de deux sources simultanées indépendantes par la somme
des informations de chacune d'elle. 24 Electronique pour le traitement du signal, volume 5
- L'information est mesurée par un nombre réel positif.
- Le choix de la base 2 pour le logarithme permet de restituer dans le cas où p = 0,5 la valeur
1 pour H. L'unité ainsi définie a reçu le de « Shannon (Sh) ».

- Ainsi la « quantité d'information moyenne H produite par une source ou entropie de la S
source », qui contient M messages ou symboles, est alors égale à la « moyenne » des
quantités d'information contenue dans chaque message (comme on est dans le cadre d'une
approche probabiliste on ne peut travailler qu'en terme de moyennes). On montre alors que
l'on a pour la source :
M −1 M −1
H = p H = − p log (p ) [Sh / message] s ∑ i i ∑ i 2 i
i =0 i =0

NB : On retrouve bien par cette approche la relation (1.4) précédemment définie.

- L'unité de mesure de l'information moyenne peut bien sûr être donnée indifféremment en
terme de [Sh/état] , [Sh/message] , [Sh/symboles], etc. Sachant qu'il faut associer une
probabilité à chaque élément analysé dont on veut mesurer la quantité d'information.
- Ainsi de la même manière pour un alphabet de n caractères équiprobables (p = 1/n)
c'est-à-dire pour lequel on ne sait rien a priori, l'incertitude ou l'entropie est alors maximale et
égale à : H = log n. Pour la langue Française des tests statistiques ont montré que max 2
H # 1,5 Sh/lettre.

1.2.3.2. Entropie d'une source à deux états

Soit une source pouvant émettre deux états distincts. Si p est la probabilité d'émission de
l'état 1, q la probabilité de l'état 2, il est alors évident que l'on a :
q = 1 – p et p = 1 – q (ensemble complet)
L'entropie H de la source s'écrit donc: H = −plog p − qlog q 2 2 2 2
Comme l'on est en présence de deux états seulement, on peut toujours coder « 0 » et
« 1 » les deux possibilités, donc un alphabet de base deux est suffisant.
Enfin on peut écrire :
⎡ p ⎤
H = −[plog p + (1 − p)log (1 − p)] = − plog + log (1 − p) 2 2 2 2 2⎢ ⎥1 − p⎣ ⎦
On peut alors étudier les variations de H en fonction de p. 2

Ainsi la valeur maximale H = 1, est-elle atteinte pour p = 0,5. 2
p p'H (p) = log = 0 → = 1 → p = 0,52 2
1 − p 1 − p
H (0,5) = −()0,5log 0,5 + 0,5log 0,5 = 1 soit p = q = 0,52 2 2
Donc pour toute valeur de p ≠ 0,5 on a donc toujours ici H < 1. De plus comme 2
x log x → 0 pour x → 0, H est nulle pour p = 0 et p = 1, ce qui est normal puisque l'une et 2
l'autre des deux éventualités de l'alternative est alors certaine et donc l'incertitude et
l'entropie nulle.

Théorie de l’information 25
D’où l’allure du graphe corrrespondant :

H (p)2
1




0 0,5 1 p

fig.1.3. Entropie d'une source à deux états

1.2.3.3. Entropie d'une source uniforme

Chacun des états a ici la même probabilité d'être émis, donc pour M états distincts et un
ensemble complet on a :
MM11111 11⎛⎞
p== donc : H− log=−log .=−log . M .= log M∑∑iNN N ⎜⎟2MMMMMMMi1==i1 ⎝⎠
attention aux notations !
H==-log (1/ M) log MNN

On peut ainsi montrer que dans tous les cas possibles on aura toujours :
H ≤ log M (1.5) N

- L'entropie est donc maximale lorsque les probabilités de tous les états sont égales
(équiprobabilité ou loi uniforme), ce qui correspond bien sûr au cas d'incertitude maximale.
Quand on ne sait rien sur la source, on fait toujours l'hypothèse que les éléments sont
équiprobables a priori (que l'on peut éventuellement corriger par une mesure a posteriori).

1.2.3.4. Cas particulier du traitement binaire de l'information

Les techniques de traitement binaire de l'information, c'est-à-dire pour la base 2, et donc
N = 2 pour l'alphabet du code, a vulgarisé la dénomination de « bit » (pour binary digit) pour
chaque symbole « 0 » ou « 1 » d'un message codé en binaire.
Soit pour une source de M états équiprobables que l'on veut coder en binaire, on a donc :
k kM = 2 et donc : H = log M = log 2 = k 2 2
Dans ce cas équiprobable, k représente alors la longueur maximale d'un mot du code.

k On peut toujours coder par des mots de k bits chacun des M = 2 états possibles de la
source. Plus k est grand et plus on peut « dire de chose ». On peut donc dire que k mesure
la capacité informative de « k sources indépendantes », avec ici du point de vue unité :
H = k [Shannon/état]

Et chaque bit transporte donc l'information suivante :
H
= 1 [Schannon / bit]
k
Exemple : L'entropie comme mesure de l'incertitude. Elle permet aussi de mesurer
l'incertitude de la prévision du résultat d'une épreuve ou d'une expérience aléatoire donnée. 26 Electronique pour le traitement du signal, volume 5
Par exemple : E = tirer une boule d'une urne de composition donnée, disposant des trois
compositions suivantes :
- U = 1 B noire et 1 B blanche 1
- U = 9 B noires et 1 B blanche 2
- U = 99 B noires et 1 B blanche

Il faut alors définir la v.a X par : X = {N = Boule noire ∪ B = boule blanche}, et l'on
cherche à évaluer l'incertitude du résultat d'une épreuve dans chaque cas.
Les lois de probabilité des 3 cas sont alors données par :

N B N B N B
1/2 1/2 9/10 1/10 99/100 1/100
U1 U2 U3

Ainsi si l'on calcule « a priori » les entropies relatives à chaque catégorie d'épreuve dans
le système binaire par exemple, il vient :
U U U1 2 3H = 1 bit H = 0.47 bit H = 0.08 bit
2 2 2
Donc le résultat de la première catégorie est plus incertain que celui de la deuxième qui
est lui même plus incertain que celui de la troisième pour laquelle l'événement {apparition
d'une boule noire} est évidemment presque certain.

1.2.4. Propriétés de l'entropie
Soit H(X) ou H(p , p , p ,…….. ,p ), l'entropie d'une variable aléatoire X définie par sa loi 1 2 3 M
de probabilité p[X = x ] = p . On vérifie les propriétés suivantes liées à la nature de la fonction i i
log (qui on l'a vu à été choisie pour cela) :

- a - L'entropie H(X) est toujours positive ou nulle.
- b - Si H(X) = 0, la variable aléatoire X est presque sûrement égale à une quantité
certaine x . i0
1
- c - L'entropie H(X) est maximale pour la distribution uniforme p = , on aura donc i
M
toujours : H(X) ≤ log M N

1.2.4.1. Entropie d'un vecteur aléatoire

Pour deux variables aléatoires : {X } = {x ,x ,............,x } et {Y } = {y ,y ,............,y }, on 1 2 n1 1 2 n2
définit l'entropie relative au couple de v.a {X,Y} par la « mesure » suivante :
n1 n2
H(X,Y) = − p(x ,y )log [p(x ,y )] (1.6) ∑∑ i j N i j
i==1 j 1
On montre alors que l'on a de manière générale :
H(X,Y) ≤ H(X) + H(Y) (1.7)
Ainsi l'entropie d'un couple de v.a est toujours inférieure ou égale à la somme des
entropies de chacune des variables. Plus généralement pour un vecteur d'un espace à
m dimensions X , X , X , ………., X , on a : 1 2 3 m
n1 n2 nm
H(X ,X ,.....,X ) = − ....... p(i ,i ,.....i )log [p(i ,i ,.....i )] 1 2 m ∑∑ ∑ 1 2 m N 1 2 m
i1 ==1i2 1 im = 1Théorie de l’information 27
a) - Ensembles indépendants

Les deux expériences sont alors indépendantes. Ceci signifie que l'issue de l'expérience
x , ne dépend pas de l'issue de l'expérience y, et donc dans ce cas : i j
p(x ,y ) = p(x ) ⋅ p(y )i j i j

donc : H(X,Y) = H(X) + H(Y) (1.8)

On remarque que ce résultat est aussi issu comme on l'a vu précédemment de la
construction de la mesure de l'entropie.

b) - Ensembles liés

L'issue de l'expérience x est maintenant conditionnée par le résultat préalablement i
obtenu de l'expérience y, on peut alors écrire ici : j
p(x ,y ) = p(x ) ⋅ p (y / x ) = p(y ) ⋅ p (x / y )i j i j i j i j
On définit alors l'entropie conditionnelle H(X/y ) de X quand y à été choisi, par : j j
n1
H(X/y ) = − p(x / y )log[]p(x / y ) (1.9)j ∑ i j N i j
i =1
et ainsi l'entropie conditionnelle H(X/Y) de l'alphabet X lié à l'utilisation de l'alphabet Y est
définie par l'entropie moyenne suivante :
H(X / Y) = p(y )H(X / y ) + p(y )H(X / y ) + .................. + p(y )H(X / y )1 1 2 2 n2 n2
n2
que l'on écrit : H(X/Y) = p(y ) ⋅H(X / y )∑ j j
j =1
soit encore :
n2 n1 n2 n1 ⎧ ⎫
H(X/Y) = p(y ) − p(x / y )log[]p(x / y ) = − p(y ) ⋅ p(x / y ) ⋅ log[]p(x / y )⎨ ⎬∑∑j i j N i j ∑∑ j i j N i j
j==1 i 1 j==1 i 1⎩ ⎭
et ainsi :
n1 n2
H(X/Y) = − p(x ,y ) ⋅ log[]p(x / y ) (1.10)∑∑ i j N i j
i==1 j 1
Mais on peut développer cette expression et en utilisant la relation (1.6) il vient :

n1 n2 n1 n2
H(X,Y) = − p(x ,y )log [p(x ,y )] = − p(x ,y )log [p(x )p(y / x )]∑∑ i j N i j ∑∑ i j N i j i
i==1 j 1 i==1 j 1
n1 n2 n1 n2
H(X,Y) = − p(x ,y )log [p(x )] − p(x ,y )log [p(y / x )]∑∑ i j N i ∑∑ i j N j i
i==1 j 1 i==1 j 1

n1 n2
H(X / Y) = − p(x ,y )log [p(x )] + H(Y / X)i j N i∑∑
i==1 j 1
n2
mais comme on a : p(x ,y ) = p(x ) (densité conjointe)∑ i j i
j28 Electronique pour le traitement du signal, volume 5
n1 n2 n1
il vient : − p(x ,y )log [p(x )] = − p(x )log [p(x )] = H(X)∑∑ i j N i ∑ i N i
i==1 j 1 i =1
soit enfin pour deux ensembles liés :
H(X,Y) = H(X) + H(Y / X)⎧⎪
(1.11)⎨
⎪H(X,Y) = H(Y)H(X / Y)⎩

qui donne donc l'entropie de l'ensemble produit dans le cas d'ensembles liés.

1.2.4.2. Entropie comme mesure de l'incertitude

On a vu que l'on peut présenter l'entropie comme une mesure de l'incertitude
(voir 1.2.3.1) que l'on a quand aux messages émis. Ainsi au paragraphe 1.2.3.2, si p est très
petit on voit que H est faible, l'incertitude de recevoir l'état 1 est donc faible aussi. On 2
s'attend fortement à recevoir le message de probabilité q = 1 – p. L'incertitude est alors
maximale pour l'équiprobabilité, c'est ce que l'on retrouve pour le jeu de pile ou face par
exemple où l'on a p = q = 0,5.
L'ingénieur des télécommunications américain Shannon a proposé d'attribuer à chaque
symbole émis, « une incertitude Ι a priori » qui est donc mesurée par la grandeur suivante :
1
Ι = log = −log p (1.12) n N i
pi
De cette façon, l'incertitude est d'autant plus grande que le choix du symbole est a priori
peu probable. Elle est nulle lorsque le choix du symbole est certain, c'est-à-dire quand
p = 1,soit Ι = 0. L'incertitude peut alors être considérée comme une variable aléatoire i
discrète prenant la valeur Ι = −log p , avec la probabilité p. Ainsi la valeur moyenne de iN i
l'incertitude est alors donnée par :
M M M 1
E[y] = y =()− p log p = − p log p = p log ∑ i N i ∑ i N i ∑ i N pii =1 i =1 i =1

On retrouve donc bien la définition de l'entropie de la relation (1.4) qui montre donc que
les deux approches, par mesure de la « longueur moyenne minimale » de la séquence , et
par la « notion d'incertitude », sont équivalentes. On peut donc utiliser la même notation pour
la mesure de l'incertitude ou de l'information.

1.2.5. Information mutuelle entre l'entrée et la sortie d'une voie
Le modèle « de représentation de la transmission » utilisé est alors le suivant :


Voie de Source {X} Récepteur {Y}
transmission

y ∈ {Y} jx ∈ {X} i
fig.1.4. Modèle de voie ou canal de transmission

- Avant la transmission d'un message, l'entropie pour un observateur est bien
évidemment l'entropie « a priori » de la source soit H(X) dans l'alphabet {X}. Théorie de l’information 29
- Après transmission, ayant pris connaissance du message dans l'alphabet {Y} du
récepteur, l'entropie devient l'entropie « a posteriori » H(X/Y), et l'information « gagnée »
par l'observateur est définie de manière naturelle comme la différence entre ces deux
entropies, soit :
Ι(X,Y) = H(X) − H(X / Y) (1.13)

C'est l'information moyenne par symbole contenue dans l'alphabet Y au sujet de
l'alphabet X, on pourrait écrire de la même façon que :
Ι(X,Y) = H(Y) − H(Y / X) (1.14)

Ainsi la quantité d'information contenue dans X au sujet de Y est la même que celle
contenue dans Y au sujet de X, d’où le terme « d'information mutuelle » entre X et Y.
L'information transmise à un observateur est donc la différence entre l'incertitude de X et
l'incertitude qui lui reste après l'observation de Y.
Ι(X,Y) précise et mesure la corrélation pouvant exister entre l'émetteur et le récepteur, ainsi :

- Si Ι(X,Y) = 0, l'entrée de récepteur ne contient aucune information au sujet du message
émis et réciproquement et :
H(X) = H(X/Y).

La sortie du récepteur est totalement indépendante de l'émetteur.

- Si H(X/Y) = 0, la réalisation de Y est certaine et alors :
Ι(X,Y) = H(Y) = H(X).

La sortie du récepteur est entièrement liée à l'émetteur.

1.2.6. Capacité d'un canal de transmission
La capacité C d'un canal de transmission est, par définition, mesurée par la valeur
maximale de l'information mutuelle moyenne Ι(X,Y), lorsque l'on considère toutes les
distributions possibles pour X, soit :
C = max { Ι(X,Y) } (1.15)
i

- La capacité d'un canal est donc la plus grande quantité d'information qui peut être
transmise par lui.
- La capacité d'un canal ne dépend que de la voie de transmission et de la manière dont
est distribuée la variable aléatoire d'entrée.

1.2.7. Modélisation d'un canal de transmission bruité dans le cas discret
A l'entrée du canal apparaissent donc les x choisis par la source pour composer le i
message émis. Si le canal est non bruité, les symboles sont reçus par le récepteur sans
erreur et l'on peut recomposer le message émis sans erreur. On a vu alors que dans ce cas
pour transmettre le maximum d'information il faut rendre les messages de la source
équiprobables par les méthodes que l'on verra plus loin (codage de source et canal sans
bruit). 30 Electronique pour le traitement du signal, volume 5
Dans le cas général le canal est bruité et à la réception, l'alphabet de réception est
constitué par les y qui correspondent aux x à travers une matrice de probabilité j i
conditionnelle, qui traduit la probabilité de recevoir le symbole y quand x a été émis. Ces j i
probabilités sont aussi appelées « probabilités de transition », la « matrice de transition »
s'écrivant alors sous la forme suivante, avec :
Le modèle de représentation du canal bruité qui devient alors le suivant :


Canal bruité Source {X} Récepteur {Y}

p(x ) p(y /x ) p(y ) i j i j

fig.1.5. Modèle de canal bruité

Et la matrice de transition associée qui est la suivante :
⎡ p(y / x ) .......... p(y / x ) .......... p(y / x ) ⎤1 1 j 1 n2 1
⎢ ⎥
............ .......... p(y / x ) (1.16) j i⎢ ⎥
⎢ ⎥p(y / x ) .......... p(y / x ) p(y / x )1 n1 j n1 n2 n1⎣ ⎦

La somme des éléments d'une même ligne est égale à 1 puisque nécessairement un
symbole de Y est reçu chaque fois qu'un symbole de X est émis, soit :
n2
p(y / x ) = 1 ∀x ∈ [X} (1.17) ∑ j i i
j =1
Pour représenter cette situation on utilise en général le modèle de représentation du canal
bruité suivant :

p(x) x X X y p(y ) 1 1 1 1p(y /x ) 1 i

p(y /x ) j iSource p(x) x X X y p(y) Récepteur i i j j
{X} {Y}

p(y /x) p(x ) x X n2 i X y p(y ) n1 n1 n2 n2

fig.1.6. Modèle de matrice de transition d'un canal bruité


La transmission fait donc apparaître le processus aléatoire de la source, caractérisé par
les x et p et le canal de transmission, caractérisé par sa matrice de transition. On supposera i iii ii
toujours que ces deux processus, « source et canal, sont indépendants ». Donc chaque fois
qu'un symbole x est émis, un symbole y est reçu. ii jji j
Ainsi la probabilité de recevoir y , p(y) se calcule facilement à partir des données du jj jjj j
problème avec :
n1
p(y ) = p(x ) ⋅ p(y / x ) (1.18) j i j i∑
i =1
Il est donc possible de calculer toutes les entropies possibles concernant les deux
alphabets X et Y.
Théorie de l’information 31
1.2.8. Exemple du canal binaire symétrique
Le modèle est alors le suivant :

p
p(a ) = p a X 0 0 0 X b0 q
q X b1
p(a ) = p a X 0 1 1 p

fig.1.7. Modèle de canal binaire symétrique


⎧a ≈ x p(b ) = p p + p q⎧p + p = 1 ⎧i i 0 0 10 1Ici , avec bien sûr : ⎨ ⎨ ⎨
b ≈ y p + q = 1 p(b ) = p p + p qj j ⎩ ⎩ 1 1 0⎩
Les probabilités de la matrice de transition sont alors données par :
p(b / a ) = p⎧ 0 0
⎪p(b / a ) = q⎪ 0 1 ⎨
p(b / a ) = q1 0⎪
⎪p(b / a ) = p⎩ 1 1
On peut alors calculer l'information mutuelle à partir des relations suivantes :
⎧ Ι(A,B) ≈ ici à : Ι(X,Y))
⎪⎪
Ι(A,B) = H(B) - H(B/A) ⎨ ⎧⎪
⎪ ⎨
⎪⎪ Ι(A,B) = H(A) − H(A /B)⎩⎩
Or il est ici (et pratiquement toujours) plus simple de calculer p(B/A) et donc H(B/A) à
partir des données « a posteriori » du problème, soit avec :
1 1
H(B/a) =− p(b /a) ⋅log p(b /a ) et: H(B/A) = p(a) ⋅H(B/a)ji∑∑j2ij j j
i0= j0=
⎧H(B / a ) =−p(b / a )log p(b / a ) − p(b / a )log p(b / a )000 200 10 210soit : ⎨
H(B / a ) =−p(b / a )log p(b / a ) − p(b / a )log p(b / a )⎩ 101 201 11 211
⎧H(B / a ) =−plog p − qlog q02 2et donc : ,⎨
H(B / a ) =−qlog q − plog p⎩ 12 2
identiques bien sûr par symétrie→=H(B / a ) H(B / a ). Ainsi :01
H(B/A)=+p(a )H(B / a ) p(a )H(B / a )= p H(B / a )+ p H(B / a )= p H(B / a )+ p H(B / a )0 0 1 1 00 1 1 00,1 1 0,1
H(B / A)(p p )H(B / a )=+(p p )H(B / a )= H(B / a ) puisque : (p + p ) = 101 0 0 1 1 101
donc par exemple : H(B / A)==H(B / a )−p(b / a )log p(b / a )− p(b / a )log p(b / a )101 201 11 211
H(B / A) =−plog p − qlog q
22

32 Electronique pour le traitement du signal, volume 5
Il nous reste donc à calculer H(B) qui est donné à partir du théorème des probabilités
composées, avec :
H(B) = −p(b )log p(b ) − p(b )log p(b ) = −(p p + p q)log (p p + p q)
0 2 0 1 2 1 0 1 2 0 1
− (p p + p q)log (p p + p q)1 0 2 1 0
On peut donc maintenant calculer l'information mutuelle avec :
Ι(A,B) = H(B) - H(B/A)
Ι(A,B) ={}− (p p + p q)log (p p + p q) − (p p + p q)log (p p + p q) + plog p + qlog q0 1 2 0 1 1 0 2 1 0 2 2
La capacité du canal étant par définition, donnée pour le maximum de l'information
mutuelle Ι(A,B) = Ι (A,B), et donc pour le maximum de H(B) (qui est une fonction de p max 0
avec p = 1 – p ). 0 1
Or on a vu que ce maximum est égal à1 pour la répartition équiprobable en entrée, c'est-
à-dire pour p = p =0,5 ici, il vient donc pour la capacité du canal binaire symétrique : 0 1
C = Ι (A,B) = 1 + plog p + qlog qmax 2 2
C = 1 + plog p + (1 − p)log (1 − p)2 2
C = 1 + qlog q + (1 − q)log (1 − q) 2 2
⎧C = 1- H(p)⎪
que l'on peut écrire aussi : (1.19)⎨
⎪C = 1- H(q)⎩
suivant que l'on exprime l'entropie en fonction de p ou de q (liées par p + q = 1)

NB : On remarque que si p = q = 0,5, alors C = 0, qui est le cas le plus défavorable puisque
à ce moment le symbole reçu devient indépendant du symbole émis.
Par contre la capacité est bien sûr maximale et égale à 1 pour p = 0 ou p = 1 qui
correspond à une simple permutation des symboles (avec xlogx →0, qd x →0).

1.3. Recherche des codes optimaux
1.3.1. Généralités
Pour une source {X} définie par l'ensemble {x , x ,…….., x ) et par les probabilités 1 2 M
d'émission p(x ), p(x ), ..., p(x ), on dira qu'un code est optimal, si la longueur moyenne du 1 2 M
code est minimale, soit :
M
n = p(x ) ⋅n i i∑
i =1
On se limitera à la recherche des codes instantanés. Dans ce cas la on peut alors poser
p(x ) = p sans risque de confusion. 1 i

1.3.2. Limite inférieure de n . Théorème du codage sans bruit
−niN
Posons : f = , avec: M = nombre d'états de la source et N = base de l'alphabet i M
−niN∑
i =1
du code.
Théorie de l’information 33
On peut alors écrire pour l'entropie H(S) (log dans une base b quelconque), que :
M
H(S) = − p logp ∑ i i
i =1
M M
Or on ne peut écrire : H(S) = − p logp = − p logf , que SSI f = p , c'est-à-dire si i ii i i i∑ ∑
i =1 i =1
M M
−n -ni ip = N puisque en effet on a alors N = p = 1 (ensemble complet), et donci ∑ ∑ i
i =1 i =1
f = p cqfd. On peut donc écrire dans ce cas là que : i i
M -n M M Mi ⎛ ⎞⎛ ⎞N -n -nji ⎜ ⎟⎜ ⎟H(S) = - p log = − p logN + p log N∑ i ∑ i ∑ i ∑M ⎜ ⎟ ⎜ ⎟
i =1 -n i =1 ⎝ i =1 ⎠ j =1i ⎝ ⎠N∑
i =1
M M M⎛ ⎞ ⎛ ⎞-n -nj j⎜ ⎟ ⎜ ⎟H(S) = p ⋅ n logN + 1 ⋅ log N = nlogN + log N ∑ i i ∑ ∑⎜ ⎟ ⎜ ⎟
i =1 j =1 j =1⎝ ⎠ ⎝ ⎠

(H(S) et logN étant exprimés dans la même base ici).

Or si par hypothèse le code est à décodage unique (car par hypothèse instantané), on
sait alors que l'on a la relation suivante :
M M
−n −n −nj jiN ≤ 1 pour p ≠ N ici, alors : log N ≤ 0 i∑ ∑
j =1 j =1
Donc dans ces conditions on peut écrire :
H(S)
H(S) ≤ nlogN soit : n ≥ (1.20)
logN
M
Donc en conclusion si n = p n , est la longueur moyenne des mots du code instantané ∑ i i
i =1
H(S)
pour une source S, alors dans le cas général on aura toujours l'inégalité suivante : n ≥ ,
logN
−nil'égalité n'étant possible que SSI l'on a : p = N pour i = 1 à M. i

NB : On remarque par ailleurs que l'on retrouve bien sûr , pour la longueur minimale de la
séquence la relation de l'entropie de la source S calculée dans la base N, puisque en effet
on a alors :
M MH (S) log pb b in → n = = − p = − p log p min ∑ i ∑ i N ilog N log Nb i =1 b i =1
- Ainsi un code « absolument optimal » est un code admettant comme longueur moyenne
des mots code la limite inférieure donnée par :
H(S)
n =
logN
NB : Il n'est pas toujours possible d'obtenir n entier, mais on peut démontrer que le choix se
fait alors à partir de la relation suivante, qui montre qu'il existe un n entier tel que :

H(S) H(S)
≤ n ≤ + 1 (1.21)
logN logN34 Electronique pour le traitement du signal, volume 5
Exemple :

00 0 X Source (S) probabilités p mots code i
00 X s 1/2 1 1 001 X0 X
s /4 01 2 01 X
s /8 000 3 1 X
s /8 001 Arbre de taille 3 et d'ordre 2 4
Le code est bien instantané
Et ici on a :
4 1 1 1
n = n p = 1 ⋅ + 2 ⋅ + 2 ⋅ 3 ⋅ = 1,75. on retrouve bien aussi dans ce cas∑ i i 2 4 8i =1
4 1 1 1 2⎛ ⎞n ≡ H(S) = − p log p = Log2 + Log4 + Log8 = 1,75⎜ ⎟i 2 i∑ Log2 2 4 8⎝ ⎠i =1
Et on a bien la longueur moyenne du code absolument optimal égale à l'entropie de la
source.

NB : Il faut bien remarquer que l'intérêt de ces codes du point de vue transmission, c'est
qu'ils transmettent le maximum d'information dans le temps le plus court.

1.3.3. Méthode de R.M. Fano
Le principe de ce type de codage est de séparer successivement la source de message
{X} en B groupes de messages tels que les sommes des probabilités des messages de
chaque groupe soient aussi voisines que possible (équiprobabilité).
Pour obtenir un code binaire R.M. Fano a imaginé la méthode suivante :

a) - Classer les différents messages de la source dans l'ordre des probabilités décroissantes.
b) - Diviser l'ensemble des messages en deux sous ensembles de probabilité aussi proche
que possible.
c) - Attribuer un premier chiffre binaire respectivement 0 et 1 aux messages du premier et
deuxième sous ensemble.
d) - Diviser successivement chacun des deux sous ensembles obtenus en procédant comme
en c.
Le tableau suivant donne un exemple qui illustre la méthode :

S p Probabilités des sous ensembles Longueur code i
ère ème ème ème ème
1 division 2 division 3 division 4 division 5 division n pi i
s 0,4 0,4 "0" 2x0,4 = 0,8 00 1
0,55 "0"
s 0,15 0.15 ,1" 2x0,15 = 0,3 01 2

s 0,15 0,15 "0" 3x0,5 = 0,45 100 3
0,25 "0"
s 0,1 0,1 "1" 3x0,1 = 0,3 101 4

s 0,1 0,1 "0" 3x0,1 = 0,3 110 5
0,45 "1"
s 0,06 0,06 "0" 4x0,06 = 0,24 1110 6
0,21 "1"
s 0,02 0,1 "1" 0,02 '"0" 5x0,02 = 0,1 11110 7
0,04 "1"
s 0,02 0,02 "1" 5x0,02 = 0,1 11111 8
Théorie de l’information 35
8
Le calcul de n donne alors : n==np 2,59 Sh/message ou chiffre binaire /message. ∑ ii
i1=
La longueur minimale étant donnée par l'entropie de la source avec ici :
8
H(S) = − p log p = −(0,4log 0,4 + 2x0,15log 0,15 + 2x0,1log 0,1 + 0,06log 0,06 +∑ i 2 i 2 2 2 2
i =1
2x0,02log 0,02) → H(S) = 2,48352
On remarque donc que le résultat n'est pas absolument optimal puisque 2,59 > 2,4845.

1.3.4. Méthode de Huffman
La méthode de Huffman permet de donner à n « la meilleure valeur possible ». Pour
arriver à ce résultat, on code par les mots les plus longs les messages dont la probabilité est
la plus faible. Les messages de la source étant classés par probabilités décroissantes. En
combinant alors les deux derniers messages de probabilité la plus faible, on forme un seul
message s de probabilité p + p . On compare alors cette probabilité aux probabilités M(M-1) M M-1
des messages immédiatement supérieurs et on effectue le regroupement qui fournit des
messages dont la probabilité est la plus petite possible. On remonte par combinaisons
successives jusqu'aux messages de plus grande probabilité. Le codage s'effectue ensuite en
affectant par exemple « 0 » aux chemins horizontaux, et « 1 » aux chemins verticaux de
l'arbre ainsi obtenu. Cette méthode appliquée à l'exemple précédent donne :

Source probabilité code n n pi i i

0
s 0,4 0 0,4 1 1
1 0 0
s 0,15 100 0,45 2
1 0,35 0,60 0
s 0,15 10 0,45 3
10,25
1s 0,1 111 0,3 4

0s 0,1 010 0,4 5
0,210s 0,06 10110 0,3 6
0,1 1
0s 0,02 01110 0,12 7
1 0,04
s 0,02 101111 0,12 8

8
Le calcul donne alors n = np = 2,54 ∑ i i
i =1
On voit donc que la longueur moyenne des mots code est inférieure à celle obtenue par la
méthode de Fano et se rapproche encore plus de 2,4835.
NB : Il existe bien sûr plusieurs solutions équivalentes en terme de longueur moyenne pour
ces méthodes. De plus le seul cas absolument optimal est celui pour lequel on retrouve
H(S). Ici les codes sont simplement optimaux. Samuel Morse a utilisé intuitivement une
méthode analogue pour réaliser un alphabet en affectant les mots code les plus courts
(ou signaux ici) aux lettres de l'alphabet les plus probables (pour la transmission d'un texte
en anglais), avec par exemple :
e
i
s

z 36 Electronique pour le traitement du signal, volume 5
On présente en général le codage par la méthode de Huffman sous la forme du tableau
suivant qui permet le calcul simple des caractéristiques des signaux codes.

N° -p Log p p graphe associé code n n p i i i i i i
3 3
x 10 X 10 x 10
1 145 222 00 2 444
0 0 1 407 10001
2 104 107 100 3 321
0 0 593 249
3 96,5 94 010 3 282
0 1 185
14 94,7 91 011 3 273 1

5 94,2 90 1100 4 360
0 0 179 344
16 93,5 89 1101 4 356
1

7 91,8 86 1110 4 344
0 165
18 87,2 79 1111 4 316

9 83,6 74 1010 4 296
0 142
110 79,3 68 1011 4 272

Tot. 969,8 3264

Avec les mesures suivantes :
10 Logp 969.83iH(S) = − p 10 = # 3,125∑ i Log2 0.3103
i =1
10
n = n = 3,264ip∑ i
i =1
n
redondance du code r = 1 − # 0,0425
H(S)
H(S)
efficacité du code η = # 0,862
n

1.3.5. Efficacité et redondance d'un code
L'entropie de la source H(S) étant le plus petit nombre de symboles qui représente en
moyenne chaque message codé (1.4), on pourra toujours coder avec une méthode
appropriée chaque message avec un code dont la longueur moyenne des symboles sera n .
Généralement on a bien sûr n ≥ H(S), car on peut toujours coder chaque message avec un
nombre moyen de symboles plus grand que H(S).
Les n − H(S) symboles supplémentaires ainsi utilisés, constituent une "redondance" que
l'on mesure par la relation suivante :
m n − H(S) H(S)
r = = r = 1 − (1.22)
n n n

n
une autre définition, mais peu utilisée est : r' = (1.23)
H(S)Théorie de l’information 37
On aura toujours H Sh/message puisque les symboles supplémentaires n'apportent pas
d'information, mais chaque symbole de l'alphabet apportera en moyenne la quantité
H(S)
Sh/symbole et donc chaque symbole apportant moins d'information, la transmission
n
sera moins sensible aux perturbations possibles lors de sa transmission. C'est tout l'intérêt
de la redondance par rapport à un code absolument optimal qui lui est très sensible aux
perturbations. On verra par la suite d'ailleurs que « la détection et la correction des erreurs »
ne peut se faire que s'il y a de la redondance, mais maîtrisée.

On défini par ailleurs « l'efficacité du code » par le rapport suivant :
Avec : A = alphabet du code, soit en binaire A = (0, 1) = 2
H(S) H(S)
Dans le cas général : η = en binaire : η = (1.24)
n.log A n2
Le codage est optimal pour η = 1
on a donc : r = 1- η (1.25)
Le codage est optimal pour r = 0

Exemple : Pour les exemples de codages précédents on trouve donc :

Méthode de Fano :
1()H(S) = − 0,4Log0,4 + 0,3Log0,15 + 0,2Log0,1 + 0,06Log0,06 + 0,04Log0,04
Log2
H(S) # 2,4835
2,4835
donc : η = # 0,959 r # 0,041
2,59

Méthode de Huffman :
entropie de même valeur bien sûr, avec : H(S) # 2,4835
2,4835
donc : η= # 0,978 r # 0,022
2,54

Donc la méthode de Huffman est plus efficace que celle de Fano.

1.3.6. Débit et vitesse de transmission
Jusqu'à présent une source à été étudiée du point de vue statistique. Mais dans la
pratique le facteur temps est primordial dans l'étude d'une transmission.
Considérons alors une source qui émet « en moyenne » D messages par unité de temps,
soit par seconde. « Le débit d'information » sera alors évidemment donné par les relations
suivantes:
Avant codage D.H [Sh/seconde]
(sous entendu, Sh/message/seconde)

La conversion des messages en mots code nécessitera n symboles en moyenne, avec
en général bien sûr comme on l'a vu :
n ≥ H 38 Electronique pour le traitement du signal, volume 5
Donc le débit réel après codage sera donné par :
D ⋅ n [symboles / sec onde].
Après codage
ou [bit / s] si messages binaires.

Et l'on définira alors la capacité du canal en dynamique, par :
C ≥ D ⋅ n ≥ D ⋅H (1.26)

« C » caractérise donc la capacité dynamique (ou capacité tout court) en
symboles/seconde du canal de transmission et on retrouvera donc pour la base 2 des
bits/seconde.

Ayant défini précédemment la capacité (statique) d'un canal de transmission à partir de la
notion d'incertitude max. ou d'information mutuelle max. par la relation (1.15), avec :
C = Ι max
On peut alors aussi définir le taux de transmission R, ou la quantité d'information
transmise par unité de temps par le canal par :
ΙmaxR = [Sh / sec onde]
T
T étant le temps de transmission de chaque Shannon d'information, le taux de transmission
maximum est alors défini par :
Ι CmaxR = = [Sh / s] (1.27)
T T
Si la source d'information possède une entropie H [Sh/message], la vitesse de
transmission des messages peut alors s'écrire de (1.26) :
C
D = (1.28) max H
En réalité on sait que D réel sera voisin de D , et on peut montrer (théorème de max
Shannon), que sous certaines conditions que l'on verra plus loin, on peut choisir D aussi
voisin que possible de D , et ceci avec une probabilité d'erreur aussi petite que l'on max
veut, avec un codage approprié. C'est l'intérêt fondamental du théorème de Shannon.

Exemple : Soit une voie de transmission binaire de capacité C = 9bits/s, dont la source
comprend 8 lettres équiprobables. On cherche le codage le plus efficace pour acheminer
l'information de la source sur la voie. On a donc ici :
8
3H = − p log p = log 2 = 3[bits/lettres]∑ i 2 i 2
i =1
C 9
et donc : D = = = 3 [lettres/ s]max
H 3
A priori, on peut donc penser que le codage le plus efficace est obtenu naturellement en
affectant à chaque lettre, une et une seule séquence de trois chiffres binaires. Théorie de l’information 39
Soit par exemple le code suivant :
messages code
A 000
B 001
C 010
D 011
E 100
F 101
G 110
H 111

On peut remarquer que dans ce cas le nombre de zéros et de 1 est le même et donc que
les deux chiffres « 0 » et « 1 » sont équiprobables. On est donc dans le cas de l'entropie
max. et de l'incertitude max. Le codage est alors absolument optimal.

Supposons alors maintenant que la source délivre des messages avec la distribution
suivante :
p(A) = 0,4 ; p(B) = p(C) = 0,15 ; p(D) = p(E) = 0,1 ; p(F) = 0,06 ; p(G) = p(H) = 0,02

Comme pour les exemples précédents.

On cherche de nouveau le codage le plus efficace pour écouler cette information sur la
voie. Or on a déjà vu qu'il était toujours possible de coder l'information de façon à
transmettre à la vitesse D # D . Ceci d'autant plus que le codage réalisé aura pour effet max
d'obtenir une équiprobabilité aussi exacte que possible entre les deux symboles d'entrée de
la voie. C'est ce souci qui va nous guider dans le choix du code. Reprenons les exemples
précédents des codages de Fano et Huffman :

- Pour Fano on a vu que le nombre moyen de chiffres binaires par lettre est alors donné par :
n = 2,59, or dans ce cas de distribution le codage idéal absolument optimal devrait avoir un
nombre moyen de chiffres binaires par lettre égal à l'entropie de la source, soit :
8
H = − p log p = 2,4835 [bits /lettre] ∑ i 2 i
i =1
l'efficacité est alors donnée par :
2,4835
η = = 0,959 [bits/chiffre binaire] 1 2,59

- De même avec Huffman on a vu que l'on avait:
2,4835
η = = 0,978 [bits/chiffre binaire] 2 2,54

- De même si on réutilisait le code envisagé dans le premier cas équiprobable, son efficacité
serait alors donnée par :
2,4835
η = = 0,828 [bits/chiffre binaire] 3 3
Ainsi le premier code utilisé est-il, dans ce cas de distribution proposé, moins efficace que
celui de Fano lui même moins efficace que celui de Huffman.
40 Electronique pour le traitement du signal, volume 5
1.4. Codage et espaces de signaux. Théorème de Shannon
1.4.1. Généralités
On se limitera pour simplifier, à des sources indépendantes avec en base binaire :
H = log N, codées par des mots binaires de même longueur n. 2
Un code Γ sera donc une liste de N suites (taille du code) de n symboles (longueur du
code). Les symboles seront ici « 0 » ou « 1 » (taille 2 pour l'alphabet binaire, base binaire,
nn nordre du code). Γ est donc une partie de l'ensemble : Κ = {0,1 } , des 2 mots possibles
dans le cas binaire.

1 - Le canal binaire symétrique

Comme on l'a vu, c'est le modèle le plus simple de canal binaire. Il est donc caractérisé
par la fraction q des chiffres 0 ou 1 erronés.

p
0 0
q


1 qp
1

La probabilité de recevoir 0 (ou 1) si 0 (ou 1) est émis, est égale à p.
La probabilité de recevoir 0 (ou 1) si 1 (ou 0) est émis, est égale à q.
Et comme il n'existe pas d'autres possibilités, on a : p + q = 1

Dans le cas général la probabilité d'erreur est faible et à tout mot émis, X = a , a , ..., a , i 1 2 n
correspond un mot reçu, Y = b , b , ..., b , parmi lesquels un certain nombre L de symboles i 1 2 n
peuvent être erronés. Y peut donc différer de X par L chiffres ou erreurs. i i

2 - La détection et la correction d'erreur

Le principe de la détection et de la correction des erreurs part d'une idée extrêmement
simple. On utilise une information surabondante (appelée redondance) pour compenser la
perte d'information produite par les erreurs de transmission.

Exemple : N = 2 source : H = log 2 = 1 2

a) - On choisit : X = 0 ; X = 1 1 2

Le destinataire est complètement démuni, aucun test ne peut lui dire si le symbole reçu
est correct ou non, puisque le mot reçu erroné fait partie des mots possibles. Donc si le code
est absolument optimal la détection d'erreur est impossible.
On a donc ici : H = 1 sh/mot H = 1 sh/bit

b) - On choisit : X = 00 ; X = 11 1 2

Si l'on trouve 01 ou 10 pour Y, une erreur est détectée, mais on est démuni contre deux i
erreurs successives.
Le prix à payer est ici de : H = 1 sh/mot H = 0,5 sh/bit
Théorie de l’information 41
c) - On choisit : X = 000 ; X = 111 1 2

Le code est ici encore plus redondant, une majorité de 1 ou de 0 permet de détecter une
erreur et de décider du mot émis qui peut alors être corrigé (il existe bien entendu toujours
une possibilité de se tromper).
Le prix à payer est ici de : H = 1 sh/mot H = 0,333 sh/bit

La procédure qui consiste à répéter avec une règle de majorité n'est pas très subtile mais
efficace. Elle entraîne un prix à payer exorbitant car elle fait tendre le débit d'information vers 0.

1.4.2. Construction de l'espace de signaux
Le calcul des probabilités d'erreur impose de connaître le type de support de l'information
transmise (c'est-à-dire le type de signal), ainsi que les caractéristiques du canal de
transmission.

1.4.2.1. Transmission de l'information « utile »

L'information utile est donc constituée par une suite ( 0 ou 1) de symboles binaires.
n symboles (consécutifs ou non) représentant un mot binaire. La transmission de ces mots
peut s'effectuer a priori de différentes manières :

- On affecte aux deux symbole « 0 » ou « 1 », deux valeurs particulières d'une tension :
« 0 » → V 0
« 1 » → V 1
(ex : TTL logique positive 0 → 0 V et 1 → 5 V)

- On affecte aux deux symboles « 0 » ou « 1 », deux signaux distincts reconnaissables par
le récepteur.
« 0 » → s (t) 0
« 1 » → s (t) 1

Les deux choix précédents se ramènent donc au codage bit à bit du mot binaire sous la
forme d'un signal émis X(t) donné par :
⎧0
X(t) = s[t , a(t)] avec : a (t) = i ⎨i 1⎩
Mais il est aussi possible de choisir d'affecter des signaux par blocs de bits supérieurs à 1
(valence supérieure à 1, signaux multivalence). Ces blocs peuvent être choisit supérieurs,
inférieurs, ou égal à la longueur n des mots du code.
Si l'on suppose que quatre signaux transmettent deux bits d'information chacun, on
choisira par exemple les quatre signaux suivants :
« 00 » → s (t) 0
« 01 » → s (t) 1
« 10 » → s (t) 2
« 11 » → s (t) 3

La valence est alors de quatre et on double le débit par cette méthode.
42 Electronique pour le traitement du signal, volume 5
1.4.2.2. Bruit du canal de transmission

On suppose le bruit du canal de transmission n(t) additif (indépendance du signal
d'information), de densité spectrale uniforme N /2 (processus sans mémoire plus général), 0
centré, de densité de probabilité gaussienne (loi des grands nombre, théorème central
limite).
L'espace des signaux étant défini et choisi, il est possible à partir des signaux s(t) de la i
source de message, de définir les vecteurs de base e de l'espace ou l'on travaille (par j
exemple par la procédure de Gramm-Smidt).
Par définition les vecteurs de base e ont alors les propriétés suivantes : j
∞⎧
∗ ∗< e / e >= e (t) e (t)dt → produit scalaire dans l'espace considéré⎪ i j i j∫⎪ − ∞
⎪ ∞
⎪ ∗ 2< e / e >= e (t) dt = 1 → espace normé ⎨ j j j∫
⎪ − ∞
⎪ ∞
⎪ ∗ ∗< e / e >= e (t) e (t)dt = 0 → si i ≠ j base orthonormée, vecteurs indépendantsi j i j∫⎪
⎩ − ∞

Si M est la dimension de l'espace considéré avec 0 ≤ i , j ≤ M-1, chaque signal s (t) s'écrira i
donc de la manière suivante dans la base choisie :
M −1
s (t) = α ⋅ e (t) (1.29) i ∑ ij j
j =0
α étant la composante du signal i sur l'axe j porteur du vecteur de base e(t) et donné par le ij j
produit scalaire suivant :

∗ ∗α =< s / e >= s (t)e (t)dt (1.30) ij i j i j∫
− ∞
(à rapprocher du calcul des coefficients α de la série de Fourier qui est une approche n
identique).
Et de manière générale pour un espace de dimension N finie :
∞ N −1
< s / s >= s (t)s (t)dt = α ⋅ β (1.31) i j i j ∑ ik jk∫
k =0− ∞
Si l'on considère le bruit n(t) gaussien, centré, stationnaire, il est alors possible, comme
pour α , de définir les composantes n du bruit n(t) suivants les vecteurs de base e(t) , par la ij j j
relation suivante :

∗n = n(t) e (t)dt (1.32) j j∫
− ∞
Les hypothèses de stationnarité plus d'ergodicité, permettent d'écrire l'espérance
(moment d'ordre un), comme moyenne temporelle et d'écrire pour la variance (moment
d'ordre deux centré) la forme suivante :
∗ ∗Var[n (t)] = E[n (u)n (v)] = E[n n ] = Var[n ]j j j j j j
∞ ∞ ∞⎡ ⎤
∗ ∗ ∗ ∗= E ⎢ n(u)e (u)du ⋅ n (v)e (v)dv ⎥ = E[n(u)n (v)] ⋅ e (u)e (v)dudvj j j j∫∫ ∫∫
⎢ ⎥⎣ − ∞ − ∞ ⎦ − ∞Théorie de l’information 43
Or le bruit étant de densité uniforme N /2, gaussien et centré, sa variance est aussi 0
donnée par la valeur de la fonction d'autocorrélation en 0, qui est la TF de la DSP du bruit
blanc, soit ici un Dirac pondéré par le terme constant N /2, donc : 0
N∗ 0E[]n(u).n (v) = δ(u − v)
2
∞ ∞
N0 ∗et : Var[]n = . δ(u − v).e (u).e (v).du.dv
j j j∫ ∫ 2
− ∞ − ∞
Cette fonctionnelle ou intervient un Dirac n'existe donc que pour : u - v = 0

2 2N0On en déduit donc : Var[]n = n = . e .duj j j∫2
− ∞
=1 par définition
N0Var[]n =j 2
Les composantes n du bruit sont donc aussi gaussiennes, de moyenne nulle et de j
variance N /2, (puissance moyenne totale de la composante car centré). La densité de 0
probabilité de chacune d'elle s'écrit donc :
2⎧ ⎫n1 ⎪ ⎪jP(n ) = exp − (1.33) j ⎨ ⎬NπN ⎪ ⎪0 0⎩ ⎭
N2 0avec ici : σ ≡ j 2
Les composantes sont de plus statistiquement indépendantes du fait de l'orthogonalité
des vecteurs de base. Les M variables n étant indépendantes, la densité de probabilité j
composée devient le produit des densités de probabilités élémentaires, soit :
2M −1 ⎧ ⎫n1 ⎪ ⎪jP[n ,n ,........,n ,.....,n ] = exp −⎨ ⎬0 1 j M −1 ∏ NπN ⎪ ⎪0j =0 0 ⎩ ⎭
soit :
M −1⎧ ⎫1 ⎪ 1 ⎪2P[n ,...,n ,..,n ] = exp − n (1.34)⎨ ⎬0 j M −1 ∑ jM/ 2 N()πN ⎪ ⎪0 j =00 ⎩ ⎭

1.4.2.3. Représentation géométrique des signaux

La représentation échantillonnée d'un signal s(t) (échantillonnage idéal) appartenant à la
classe des signaux d'énergie finie permet d'écrire s(t) sous la forme suivante (interpolation
de Shannon, voir chapitre 3) :
∞ ⎛ ⎞n sin [ π(2f t − n) ]~ cs(t) = s ⎜ ⎟∑ ⎜ ⎟2f π(2f t − n)
n = −∞ ⎝ c ⎠ c


∗avec pour son énergie : E[s(t)] = s(t)s (t)dt < ∞, pour s(t) signal déterministe choisit.∫
− ∞


44 Electronique pour le traitement du signal, volume 5
On peut alors considérer que cette décomposition est associée à une base orthonormée
formée des vecteurs de base e (t) tels que : n
sin [ π(2f t − n) ]ce (t) = k
n π(2f t − n)c
en effet on peut montrer que pour de tels signaux on a :

sin[]π(2f t − n) sin[]π(2f t − m) c c< e / e >= 2f ⋅ 2f dtn m c c∫ π(2f t − n) π(2f t − m)c c− ∞
1 si m = n⎧⎪= (les fonctions sont donc orthogonales)⎨
⎪0 si m ≠ n⎩
On peut donc former une base pour l'espace des signaux à énergie finie et écrire :
∞ ⎛ ⎞1 n~ ⎜ ⎟s(t) = s e (t) (1.35)∑ n⎜ ⎟2f2f cc n = −∞ ⎝ ⎠
⎛ ⎞n~avec ici s ⎜ ⎟ calculé à partir de :⎜ ⎟2f⎝ c ⎠
∞⎛ ⎞n sin[ π(2f t − n)]~ cs ⎜ ⎟ =< s(t)/ e (t) >= 2f s(t) dt n c⎜ ⎟ ∫2f π(2f t − n)⎝ c ⎠ c− ∞
l'énergie d'un tel signal est alors bien evidemment donnée par :
2 ∞∞1 ⎛ n ⎞ 2~E[s(t)] = s ⎜ ⎟ = s(t) dt < ∞∑ ⎜ ⎟ ∫2f 2fc n = −∞ ⎝ c ⎠ − ∞
Relation à rapprocher de l'énergie des raies de la SF qui est en fait une puissance, et de
la relation de Parceval correspondante.
L'ensemble des signaux échantillonnés à énergie finie forme alors un espace vectoriel de
dimension dénombrable.
Nous considérons ici un sous espace de M signaux (M étant la dimension de l'espace
considéré comme fini) que nous appelons alors :

Espace des signaux « S ».

La théorie des espaces vectoriels indique alors qu'il existe pour ce sous espace une base
orthonormée contenant un nombre d'éléments N tel que :
N ≤ M
L'égalité ayant lieu bien évidemment lorsque les M signaux considérés sont linéairement
indépendants.
Si e(t) 0 ≤ i ≤ N-1 sont alors les vecteurs de base, on aura par définition : i

∞⎧
2 ∗⎪e (t) = e (t)e (t)dt = 1 i = ji i i∫
⎪⎪ − ∞

∞⎪
∗< e / e >= e (t)e (t)dt = 0 i ≠ j⎪ i j i j∫⎪⎩ − ∞Théorie de l’information 45
Exemple de vecteurs de base :

On peut par exemple dans le cas des signaux numériques, choisir pour vecteurs de
base e, des impulsions rectangulaires ne se recouvrant pas et ayant une énergie unitaire, i
soit :


T0 1/2 V0=(N/T)
e (t) 0

2Avec : E = V T = 10 0 0
e (t) 1


e2(t)


Autres exemples
e (t) N-1

0 T =T/N 0 (N-1)T/N T t

fig.1.8. Exemple de vecteurs de base (espace à N dimensions)


Ces fonctions vérifient bien évidemment les relations précédentes et forment donc une
base orthonormée pour chaque signaux s (t). i
On pourra écrire pour ces signaux :
N −1
s (t) = α ⋅ e (t)i ∑ ij j
j =0
et les composantes α de chaque signaux s (t) sont alors données par : ij i
N −1
α = s (t) ⋅ e (t)ij ∑ i j
j =0
2
avec pour l'énergie du signal s (t) [et < e /e >= 0 et e = 1] :i i j i
∞ N −1
2 2 2∀i ∈ [0,1,2,....,N - 1] E = s (t) = s (t)dt = α i i i ∑ ij∫
j =0− ∞
On remarque donc que l'énergie du signal est représentée « par le carré de la distance »
du point représentatif du vecteur s à l'origine (somme des carrés des composantes). i
Ainsi la représentation géométrique vectorielle d'un signal s (t) ∈ S, par un point d'un i
espace vectoriel de dimension finie, est-elle possible et permet d'appliquer la théorie des s vectoriels aux signaux à énergie finie. Sa distance au point 0 origine étant alors
donnée par : E. i



46 Electronique pour le traitement du signal, volume 5
Exemple : Cas d'une base de dimension 3 facilement visualisable.
x2
αi2
Si

x1 ρ = Ei i 2
2 2E = ρ = α i i ∑ ij
αi1 j =0

αi0 x0

fig.1.9. Base de dimension 3

1.4.2.3.1. Application aux signaux binaires simples

Dans le cas des signaux binaires simples (digits binaires), l'espace S ne contient que
deux signaux s (t) et s (t). Dans le cas général où ils sont linéairement indépendants 0 1
l'espace est à deux dimensions et on a la représentation suivante :


S1 α1

M = 2 orthogonaux
E1N = 2 si α0 S0 linéairement
e2=1 indépendants
E0

α e =1 α1 0 0

fig.1.10. Signaux binaires. Espace à deux dimensions


NB : Si les signaux binaires simples sont antipodaux, alors la dimension se réduit à 1
(signaux opposés).

1.4.2.3.2. Application aux signaux binaires composés ou mots binaires

Considérons un espace vectoriel de dimension N (mots binaires) et l'ensemble S des
signaux décomposés sur une base orthonormée de dimension N. On écrit pour chaque
signal s (t) : i
s (t) = α ⋅ e (t) + α ⋅ e (t) + ....... + α ⋅ e (t) i i0 0 i1 1 i(N −1) N −1
Supposons alors que chaque composante α peut prendre deux valeurs distinctes ij
N+A et -A, on peut ainsi définir M = 2 signaux différents, occupant les M sommets d'un
2hypercube de dimension N, tous les signaux ayant bien sûr la même énergie A , l'énergie
totale sera donc donnée par :
E = N A² s

Chaque signaux s (t) sera la somme de N signaux élémentaires orthogonaux de la forme : i
α e (t) ij j
chacun de ces signaux pouvant prendre les deux valeurs opposées :
+ A.e (t) ou -A.e (t) j j
Théorie de l’information 47
On peut par exemple visualiser le cas classique N = 3 (si dim. Supérieure impossible à
visualiser), avec : e2

S7 S6


S5
S4
eA N 1
0

S1
S2



e0 S3 S0
fig.1.11. Représentation d'un mot binaire (dim 3)

NB : Les signaux s'inscrivent dans un cube (car ± A) et en représentation matricielle, la
matrice est pleine avec des termes diagonaux et extra diagonaux.

1.4.2.3.3. Application aux signaux orthogonaux

Dans ce cas les vecteurs s(t) sont colinéaires avec les vecteurs de base et on peut écrire i
ici s(t) = α e(t). De plus comme la base est orthonormée, et les signaux s(t) aussi par i i i i
hypothèse, on peut écrire :
2 22 2s = α ⋅ e = α = Ei i i i i
On peut donc les exprimer sous la forme suivante :
s (t) = E ⋅ e (t) (1.36)
i i i

Une représentation géométrique pour N = 3 donne ici avec M = N = 3 aussi :
e2

S2

E2

e1E0 0 S1E1
S 0
e0
fig.1.12. Cas orthogonal

NB : Ici la représentation matricielle donne une matrice diagonale, car les termes
dépendants extra diagonaux sont nuls.

1.4.2.4. Représentation du bruit

On a montré précédemment que chaque composante indépendante du bruit n avait pour j
densité de probabilité, une densité gaussienne avec :
1 ⎧ 1 ⎫2P(n ) = exp − n ⎨ ⎬j jNπN ⎩ 0 ⎭048 Electronique pour le traitement du signal, volume 5
On peut alors introduire le processus aléatoire dans l'espace S fini, à travers la définition
N −1
du vecteur aléatoire suivant : ν(t) = n ⋅ e (t) (1.38) j j∑
j =0
Ce processus est représenté par un point aléatoire, extrémité du vecteur aléatoire ν(t),
dans l'espace S et le carré de sa distance à l'origine (ou sa norme aussi), comme pour les
signaux, est alors par définition donnée par :
N −1
2 2ν = n ∑ j
j =0
La distance moyenne à l'origine compte tenu de l'indépendance statistique des
composantes, est donnée elle par (N composantes de variance N /2) : 0
⎛ N ⎞2 0ν = N ⋅ ⎜ ⎟ ⎜ ⎟2⎝ ⎠
elle représente « la valeur moyenne de l'énergie du processus ν(t) » et donc la densité de
probabilité composée peut s'écrire sous la forme plus générale suivante :
2⎧ ⎫ν1 ⎪ ⎪P (n ,n ,.......,n ) = P( ν) = exp − (1.39) ν 0 1 N −1 ⎨ ⎬N / 2 N()πN ⎪ 0 ⎪0 ⎩ ⎭
Cette relation montre que la densité de probabilité du vecteur de bruit ν(t) est sphérique
(les divers points de l'extrémité de ν(t) se distribuent sur une sphère), car elle ne dépend que
de la longueur du vecteur ν(t) (distance au point 0) donnée par ν et pas de sa direction.
NB : Donc en moyenne et lorsque N est suffisamment grand, l'extrémité du vecteur de bruit
ν(t) tend à se répartir uniformément sur une sphère de rayon :
1/ 2
⎛ N ⎞0ρ = N (1.40) ⎜ ⎟ν
2⎝ ⎠
D’où la représentation du vecteur de bruit dans le cas N = 3 par exemple :

e2

1/ 2 Boule de bruit 2⎛ ⎞ρ = ν = νν ⎜ ⎟ ⎝ ⎠

e1 0

e0


fig.1.13. Représentation géométrique du bruit. Boule de bruit
1.4.2.5. Conclusion

On a donc construit un espace vectoriel « S » de dimension finie « N » où les symboles
« a » des messages sont représentés par des points « S » . La distribution dans cet espace i i
S des points dépend de la forme particulière des signaux utilisés, avec :

- La distance D (0,S) = ρ = s = E , est égale à la racine carrée de l'énergie du signal i i i i i
s (t). i