EXPOSi~ SlMPLIFII~ DE LA THEORIE " INFORMATIONNELLE " DE SHANNON

EN VUE DE SON APPLICATION AUX PROBL~,,MES DE T]~LF,,COMMANDE,

TI~LEMESURE OU M E S U R E *

par Julien LOEB Ing6nieur en Chef des P. T. T. **

SOMMAIRE. - - Apr~s une i n t roduc t i on (1) consacrde ~i prgciser, justifier et dg~,elopper les intentions annone~es d ins le titre de l'article, I'auteur dgfinit (2) les notions corrJIatives de quantit6 d'information et d'entropie : - - le logon unitd logarithmique binaire (2,1) ; - - le codage des messages dans les cas de probabilitgs ind@endantes @ales (2,2) ou di//drentes (2,3), puis dins le cas d e s , processus de Marko[/ )) (2,4) ; - - effets du codage (2,5), notamment q~ant ~ la vitesse de production de l'information (2,51), a~,ec desex exemples illu.~trati[s ; - - condition d'entropie maximum (2,6), et notion de ~ redondance ~, (2,6~), crit~re d'inflaenee du codage (2,62).

L'auteur traite ensuite (3) de la (~ vole de transmission )*, d'abord en l'absence de bruit (3,t) : il donne la [ormale dJfinissant la capacitg de la vole en indiquant des exemples d'application respecti~ement dans les cas de symboles de m~me dur6e (3,~1) ct de symboles de dur6es diff6rentcs et de suites de Markoff (3,12) ; puis il gnonce le th6or~me fondamental de la vole sans bruit (3,13) et traite le cas des symboles d'6gales dur6e selon que les proba- bilitds sont @ales (3,13t) ou diffgrentes (3,t32) ; il montre que ie probl~me de l'adaptation d'une source ~ une ~oie se ram~ne d la recherche d'un codage o p t i m u m (3,14). Le probldme ea pr6sence de bru i t s (3,2) est tout dif/drent ; la notion d 'en t ropie condil ionnel]e (3,2t) pcrmet d'~r la perte d ' i n f o r m a t i o n due au b ru i t (3,22) et lacapacitfi d ' a n e vole avec bru~t ; l'auteur termine par le th~or6me fondamen ta l de la voie avec b ru i t (3,23) dont le syst~.me BAUDoT-VEnDAN a constitug une application anticip6e. La conclusion (4) met l'accent sur les points essen- tiels et sur les r@les d'action ~ d@ager de cette thgorie.

P R I ~ A M B U L E . - - Ce titre comporte un n6ologisme, le mot c~ Informationnel ~>. L a langue fran~aise permet moins facilement que la langue anglaise la cr6ation de roots nouveaux, car l 'anglais trans- forrne ais6mentun suhstantif en adjectif ou en verbe, sans changer sa forme grammaticale.

Les mots <~ Th6orie Informationnelle de... ~ sont ici la t raduct ion exacte de l'anglais << Communi- cation Theory of... ~. Ce nouvel adjectif, que nous proposons d'introduire dans le langage technique, signifie donc ~ qui se rapporte h la th6orie de 1' Infor- mation :).

] , I N T R O D U C T I O N .

Les techniques de la t~16commande et de la t~Ig- mesure ont gagn6 sans cesse davantage h tirer parti des donn6es acquises dans le domaine g6n6ral des tglgcommunications, et elles apparaissent net tement maintenant comme l 'un des secteurs sp6cialis6s de ee domaine. Dans le bilan des 6changes avec les autres secteurs, tout n'est d'ailleurs pas ~ porter h leur d6bit : il convient de les cr6diter de contributions substantielles aux progr~s consid6rables enregistr6s dans ce domaine technique particuli~rement 6volutif.

Jusqu'~ ces derni~res ann6es, ce progr~s g6n6ral des t616communications avait consist6 h apporter des perfectionnements ou des innovations h l'en- semble des moyens (tels que : amplificateurs, relais, etc.) utilisables pour l'61aboration et la trans- mission des signaux. Par signal il convient d'en- tendre la mani/estat ion physique de , ce qu'il s'agit

de t ransmettre )): une succession de paroles, poul la t616phonie ; un ordre, pour la t616commande ; une mesure (d'un courant 61ectrique, de la vitesse d 'une piece m~canique,...) pour la t616mesure. Ainsi con~ue, la mission du technicien des tgl6com- munications est d'utiliser, perfectionner, cr6er quand il le faut, et agencer (en recherchant naturellement l'~conomie maximum de mati~res, main,d'oeuvre, 6nergie...) les moyens ~ consacrer, dans des circons- tances d6termin6es, h la transmission d 'un signal de nature d6termin6e, d ins des limites de tol6rance de fid61it6.

Un nouveau courant d'id6es enl~ve au signal lui- m~me ce r61e de donn6e fondamentale du probl~me, pour l 'at tr ibuer h c~ ce qu'i l s 'agit de transmettre ~, c'est-h-dire au message. C'est le message qui est la r6alit6 fonci~re ; le signal n'en constitue en quelque sorte qu'une empreinte ; des signaux tou t h fait distincts peuvent traduire de faqon 6quivalente un m~me message: ainsi la teneur d 'un texte peut donner lieu de fa~on 6quivalente ~ un t6t6gramme ou h u n message t~16phon6.

Le simple expos6 d'une telle notion - - dont la fertilit6 paralt devoir gtre grande - - fair apparaltre la vraie nature des liens qui unissent les diff6rentes sp6cialit6s des t616communications (y compris la t616commande et la t616mesure) : il ne s'agit pas d 'une simple analogie th6orique ou formelle, ni d 'une simple communaut6 de moyens ou de proc6d6s, mais bien d 'une unit6 profonde fond6e sur une iden- tit6 de buts, h savoir la transmission de l ' in/ormation, en appelant ainsi le contenu des messages.

* Cet article a fait l 'objet d 'un expos6 oral le 23 janvier t 95 l d ins [e cadre des Con#fences d u CE NTnE D 'ETUDES DE LA M~CAr~tqVE OV VOL, organis6es par la Section des Engins Sp~ciaux du SErtV~C~ TEEHNIQTJE DE L'25LERONAUTIQUE.

** Au C. N. :E. T., Chef du Dgpartement TALACO~A~D~ •1; CONTRE-MEsuRES.

[ ] Pour tout reavo~ entre crochets, se reporter ~n fine ~ ]a bibliographic.

i 67 - -

2/10 Cette notion a 6t6 bien d6gag6s par St~Ar~NON [lJ,

qui a 6tudi6 un canal de transmission et les r6per- cussions que peuvent avoir les imperfections d 'un tel canal sur le message transrnis, et dont l 'analyse a port6 sur deux points essentiels :

i ~ la d6finition quant i ta t ive de l ' information eontenue dans un message ;

2 ~ le eodage suivant lequel cette information appa- ralt sous forme de grandeurs physiques concretes.

La th6orle de Srt~r~r~o~ a provoqu6 diff6rents t ravaux, dont Fun a 6t6 publi6 duns ces colonnes [2]. Ce qui suit eherche h fournir de cette th6orie un expos6 simplifi6 et abr6g6 dans l'esprit suivant :

d 'une part, en visant h pr6senter le sujet au technicien sous une forme qui soft pour lui plus concrete, plus habituelle, que les d6veloppements assez abstraits du promoteur ( ' ) ;

d 'autre part, en 61aguant les d6veloppements qui, dans l 'article originel, concernent particuli~rement la transmission d 'un langage parl6 ou 6crit, pour extraire et pr6c~er ee qui est au contraire partieu- li~rement applicable au domaine de la t616commande et de la t616mesure, et rassembler ainsi le bagage requis pour la bonne compr6hension d 'un article qui fait suite h celui-ci [4].

Cette presentation particuli~re peut en outre n'gtre pas d6nu6e d 'un int6rgt plus g6n6ral, comme vole d'aec~s h la th6orie informationnelle : la teneur d 'un message de commande ou de mesure paralt avoir des limites mieux marqu6es que celle d 'un message de roots (expressions de la pens6e) ou de donn~es sensorielles telles que voix, musique, images. Par tant , assigner h un tel message un con- tenu d' information risque moins de prater h des subtilit6s d'analyse et ~ des 6chapp6es vers la contro- verse philosophique ou grammatieale.

2. D]~FINITION D E L A QUANTITI~ D~INFORMATION. - -

ENTROPIE.

Intui t ivement, si l 'on cherche h affecter h un signal ou h u n message un hombre qui mesure la ~( quantitd d'In[ormation ~ qui s 'y trouve contenue, on se rend compte que ce nombre mesure l'imprd~islbilitd du message ou du signal. Aussi, une th6orie de l 'Infor- mation est-elle n6cessairement tributaire du calcul des probabilitds.

2,1. - - D~flnlt ion du ~( L o g o n ~).

Pour construire la th6orie, nous allons d'abord examiner une source de signal particuli~rement simple, celle qui ne fournit que deux symboles possibles, par exemple les symboles (( oui )) ou ~( non )). Si, de plus, nous supposons que les probabiiit6s de ces deux r6ponses sont 6gales, nous aurons construit une source qui chaque fois qu'elle 6mettra un sym- bole fournira une unitd de quantitg d'In/ormatio~.

Srt~,~t~ON appelle eette unit6 (( Binary digit )) (ce qui

J. LOEB [ANNALES DES TI~-LI~COMMUNICATIONS

signifie : chiffre blnaire). La tenflance qui se fait jour en Europe, consisterait plutSt h appeler (( Logon ~ cette unit6 d 'Information

2,2. - - Codage (cas d 'une distribution uniforme de probabilit6s).

N'importe quel message peut, par un c( codage ~) appropri6, se mettre sous la forme d 'un hombre d6tcrmin~ de messages ~ oui ou non ~. Prenons par exemple l'envoi par t61bmesure d 'un nombre qui repr6sente une tension 61ectrique. Comme la prbei- sion de la t~lOnesure n'est pas infinie, ce que l'on chcrche h t ransmcttre en r6alit6, c'est l ' indieation d'une case duns laquelle dolt se trouvcr la grandeur physique h transmettre. La transmission du rensei- gnement peut se sch6matiscr par une suite altern6e de questions et de r6ponses par (( oui ou non )), qui arn~nent h localiscr exactement la grandeur dans la c a s e v o u l u e .

La repr6sentation math6matlque de ce question- naire n'est rien d 'autre que la num6ration en base 2 servant h figurer le nombre. La transmission en question n6cessite donc un certain hombre N de chiffres binaires ou logons, qui mesure pr6cis6ment la quantlt6 d ' Information contenue dans un tel message. Le nombre d'6tats discrets possibles d 'un tel syst~me ~tant M - - 2 ~, ]a quantit6 d 'Infor- mat[on N aff6rente "~ ]a transmission d'une valeur d6finie appara~t done comme mesure par le loga- rithme h base2 (**) du hombre t o t a l M d'6tats discrets possibles Nous d6signcrons g~n6ralement cette quantit~ par H. La transmission d 'uu message apparatt ainsl chez SHA.~.~ON comme un tirage au sort entre un certain nombre de r6alisations possibles, et nous avons dans un cas particulier d6fini la quan- tit6 d ' ]nformatlon relative h un tel tirage au sort. C'est ce que SnA~o.~ appe]]e (( Quantitd d'In/or- mation ~, ou c( Entropie par degrd de libertd )).

2,3. - - Cas de probabilitfis diffarentes.

Jusqu'h pr6sent, nous avons suppos6 que les pro- babilitds des symboles r oui ou non )) 6taient 6gales entre elles. La t.h6orie a 6t6 g6n6ralis6e par SUANNON dans le cas off les diff6rents symboles sont 6mis avec des probabilit6s diff6rentes. Dans ce cas, supposons qu'il y air N symboles caract6ris6s par l'indice i, et susceptibles d 'Ore produits par la source avec une probabilit6 P~. Bicn entendu, la somme de toutes ces probabilit6s est @ale h 1. II faut chercher une fonc- tion de ces diverses probabilit6s qui puisse repr6- senter la quantit6 d ' lnrormation raise en jeu par le choix, dans la collection des symboles, de l ' und ' en t re e u x .

L'6tude de SH~NON [t] ainsi que l 'article d'AmRArN [2] contiennent un certain hombre de raisonnements qui tous conduisent h d6finir pour H la quantit6 suivante :

('l) II Z P~ lo~. P;. i

(*) I1 convient de signaler toutefois queSHANNONIUi-m~me (**) Les logarithmes qtti intcrviendront par la suite seront a publi6 un article de vulgarisation [3]. toujours des logarithmes h base 2.

- - 6 8 - -

t . 6, n ~ 3, 1951] EXPOSI~ SIMPLIFII~: D E LA T H E O R I E

Une 6tude approfondie du probl6me, bas6e sur l'analyse fonetionnelle, h 6t6 6galement eonduite par MM. FOtlTET [5] et V1LLE [6]. Nous nous conten- terons ici de faire remarquer que, Iorsque les proba- bilit6s deviennent 6gales, nous retombons dans le cas 6tudi6 au paragraphe 2,2 et nous trouvons pr6ci- s6ment que H devient 6gel au logarithme du nombre d'6tats discrets possibles.

2 , 4 . - - P r o c e s s u s d e M a r k o f f .

S H A N N O N e o n s a c r e de tr6s importants dgvelop- pements h des probl6mes plus compliqu6s (qui se pr6sentent par cxemple dans le t61figraphe) et dent la complication est due au fait que, dens ees eas, on ne pout plus parler d'unc probabilit6 aff6rente h un symhole d6tcrmin6.

Dans ces eas, la probabilit6 ne pout plus 6trc d6finie d'une fa~on uniforme pour tous les tirages, mais d6pend des tirages pr6e6dents. Prenons avec SHANNON le eas d'une vole t616graphique : on peut d6finir un certain nombre de symboles produits par la source : ce sent :

un trait, compos6 d'un silence (une unit6 de temps) suivi d'une 6mission prolong6e (de dur6e triple);

un point, comprenant un silence suivi d'une 6mission br6ve (de dur6e 6gale au silence) ;

un intercalle entre lettres, eonsistant en un silence occupant 3 unit6s de temps ;

un intervalle entre rnots, eonstitu6 par un silence occupant 6 unit6s de temps.

Les probabilit6s de chaeun de ces symholes d6pendent tr6s 6videmment de l'6tat dans lequet la source se trouve avant le tirage : la probabilit6 d'apparition d'un intervalle de mots apr6s un inter- valle de roots est nulle, tandis quc la probabilit6 d'apparition d'un trait h la suite d'un point n'est pas nulle.

Dans le domaine'de la t616commande aussi de semblables complications peuvent tr6s bicn se pr6senter : certaines manoeuvres peuvent 4tre subor- donn6es h l'ex6cution de manoeuvres pr6paratoires ; ou bien (dans le cas de la t616commande d'un engin a partir du sol) il peut fort bien se faire que la plus grande partie des ordres soil donn4e sous la forme d'une alternance quasi r6guli6re d'ordres (( Droite ~) puis (( Gauche ~) et que l'on n'assiste qu'exception- nellement ~ l'6mission d'ordres dirig6s dans le mgme sens.

Toutefois, pour ne pas alourdir le pr6sent expos6, nous nous contenterons de renvoyer le lecteur 'a l'6tude fondamentale de SaANNON ['11.

2 , 5 . - - E f f e t s d u c o d a g e .

Le codage a pour objet de substituer h l'6mission d'un certain groupe de symboles l'6mission d'un autre groupe de symboles sans pour cela changer la teneur mgme du message. Si l'on ~tablit un codage, la sortie du eodeur constitue elle-m4me unc nouvetle source de symboles qui aura sa propre loi de proba- bilit6 et pour laquelle on pourra d6finir une n3uvelle entropie H' par symbole.

I N F O R M A T I O N N E L L E }) D E S H A N N O N 3/I0

Une grande partie du travail fondamental de SHANNON a pour objet d'examiner comment, grace au codage, on peut chercher h am61iorer le fonction- nement des T61gcommunications. Pour le suivre dans ses raisonnements, nous devons maintenant intro- duire le facteur ~ temps ,.

2,51. - - Vitesse de production de I'lnformatlon.

La source originelle sera suppos6e d6biter [es symboles h une cadence d6termin6e, soit n symboles

la seconde. Si l'on se trouve dans le cas simple o6 les suites de MARKOr~ sent exclues, et o5 l'entropie aff6rente "~ un tirage au sort quelconque est une constante H, la quantit6 n H repr6sentera le d~bit d' in[ormation de la source. Si l'on est oblig6 d'intro- duire les processus de MARXOFF, chacun des ~( 6tats ~ de la source, d6sign6 par l'indice i aura une probabi- lit6 P~, et le d6bit sera nNP~H~, o6 H~ est l'entropie aff6rente h chacun des 6tats d'indice i. Comme on lc verra, n H mesurera la dill3cult6 qu'on aura h 6tablir la vole de transmission.

Les types m~mes de codage destin6s ~ des 6co- nomies de ce genre existent depuis bien longtemps : ce sent tousles codes commerciaux, qui arrivent h repr6senter la plus grande quantit6 possible d'id$es sous forme de groupes de chiffres ou de lettres, beaucoup plus 6conomique h transmettre que les mots des langues habituelles (franCais, anglais, etc.).

Pour permettre de saisir le m6canisme de l'effet du codage nous allons (avec SHANNON) donner deux exemples de codage.

2,5tl. - - I er exemple.

Soit une source qui peut produire 4 symboles A, B, C, D, ayant respeet~vement les probabiIit6s 1/2, 1/4, t /8 , 1/8. Ces probabilit6s ne d6pendant pas des tirages ant6rieurs, on a alors :

7 H = - - Z p~ l~ p~ = / t logons par symbole.

Si nous avons n = t0 symboles par seconde (les 4 symboles seront suppos6s d'6gale dur6e) nous avons:

nH = 17,5 logons par seconde.

Effectuons maintenant un codage qui ne eom- prendra plus que deux symboles, 0 et t , selon le tableau suivant :

A B C D 0 10 110 1tt

Caleulons les probabilit6s P0 et Pl de tirage d e s

deux symboles 0 et 1. L'esp6rance math6matique des 0 s e r a :

:ix ~ 1 2 + l x 114+1x 1/8=7/8

L'espgrancc math6matique des I sere :

0 • 2 1 5 :tlS=71,a

Les espgranees math6matiques 6rant figales, les

6 9 - -

4/~0 probabilit6s P0 et Pl auront la m~me valour 1/2, e t o n a u r a :

~, log.~ + ~ log ~ ~ I logon par symbole.

Cherehons maintenant le nombre moyen n' de symboles (0 ou i) par seconde. L'esp6ranee mathgma- tique du nombre des symboles (0 et 1), par tirage des A, B, C ou D sera :

~12 + 2 x 114 + 3 x 1/8 + 3 x 118 = t418 = L75;

donc le nombre de symboles par seconde et la vitesse de transmission seront respectivement :

n' = 1,75 n = 17,5 tirages par seconde, n 'H' = 17,5 logons par seconde.

Le codage conserve clonc ici la vitesse de transmission de l'In[ormation. Est-ce h dire qu'il est sans action ? Certes non : il a chang6 chacun des deux facteurs n et H, mais en conservant leur produit constant. Partis d'un (c langage ~ qui demandait la trans- mission de 4 symboles discernables les uns des autres, ces symboles 6tant (c tir6s au sort ~, 10 fois par seconde, nous arrivons h une autre repr6sentation du mgme langage, qui ne n6cessite plus que 2 symboles (0 et 1) mais qui, par contre, n6cessite la transmission, 17,5 fois par seconde, de Fun de ces nouveaux symboles.

0n pout ainsi comparer les relations entre n e t H avec celles qui existent entre le courant et la tension dont le produit est la puissance. Un codeur joue ainsi le r61e de transformateur. Tout ceci suppose bien entendu que le codage dolt pouvoir retrans- mettre routes les nuances du langage originel.

2,5t2. - - 2e exemple.

Supposons qu'une source puisse d6biter 2 sym- boles A e t B, le premier avec une probabilit6 trbs petite 1 /N et le second avec la probabilit6 eompl6- mentaire (N - - I ) /N .

C'est hun tel type que correspondrait le cas eit6 plus haut d'une t616commande qui, de fa~on quasi r6guli~re, donnerait une s6rie d'ordres alternati- vement positifs et n6gatifs. Dans cecas, sans avoir h reeourir aux eomplications de la suite de MARXOFF, il suffira de coder par le symbole B une alternance de deux ordres oppos6s (ce symbole 6tant le plus fr6quent), et par le symbole A l'envoi de deux ordres successifs mgme signe (ce symbole 6tant tr~s peu probable). I1 est certain qu'on gagnera beaucoup dans c e c a s en codant la transmission de cette fa~on.

L'entropie par symbole est donn6e par la formule suivante :

log N si N>>I.

Cette quantit6 tend vers 0 lorsque N devient tr~s grand. Ceci traduit le fair que, dans un message

J . L O E B [ANNALES DES TI~LI~COMMUNICATION$

compos6 de ces deux symboles A et B, le symbole B reviendra tr6s fr6quemment (sa probabilit6 ~tant tr~s voisine de l'unit6), de sorte qu'on n'apprendra que fort peu de chose chaque fois qu'on le recevra. Le codage choisi ne permet ainsi de transmettre que tr~s peu d'Information pour chaque symbole. S'il y a n symboles par seconde, le dSbit est

H n == n log N N

Supposons maintenant qu'on passe au codage suivant: on enverra sur la ligne un nouveau symbole r dont la signification sera le nombre de symboles B cons6cutifs (terminus inclus). L'exis- tence d'un symbole A terminant une suite de sym- boles B sera seulement traduite par l'6mission du symbole r suivant indiquant le nouveau nombre de symboles B jointifs. Notons qu'il faut prendre la pr6caution de comprendre le chiffre 0 dans Fen- semble des symboles repr6sentant le hombre des B jointifs : ce chiffre 0 signifiera alors qu'apr~s le symbole A on rencontre encore un symbole A ; bien que tr~s rare, cecas ne dolt pas ~tre 61imin6.

Soit P~ la probabilit6 pour que r symboles B se suivent.

oo

I ( N _ ~ ) ~ , et Z P r = l " P~ = r = 0

Ici on n'est pas oblig6 de limiter le nombre des symboles d6finissant le nombre des B jointifs, ce dernier pouvant gtre infini, l~videmment, ce n'est lh qu'un aspect th6orique, et on sera oblig6 en pratique d'6tablir une limite h r, mais la validit6 des r6sultats ci-apr~s calcul6s subsiste pratiquement. Tous cal- culs fairs, il vient pour N >> I :

H' = - - Z P~ log P~ = log N.

La cadence n' de l'6mission des nouveaux sym- boles est 6gale h n multipli6e par leur fr6quence statistique (ou moyenne), qui est celle du symbole A, soit I / N

n log N n ' = / ~ et H~, = n N

Iei encore nH = n'H' . Cette fois-ci, nous sommes partis d'une source

donnant 2 symboles, h une cadence n par seeonde, et le codage l'a remplae6e par une autre d'entropie N lois plus grande, mais comportant N fois moins de tirages par seeonde..Ce r~sultat est gdn~ral. Le codage change les facteurs n e t H de ]a vitesse de transmission de l'Information, mais ne change pas le produit ni l .

2 , 6 . - - E n t r o p i e m a x i m u m .

Consid6rons une source, capable d'6mettre des symboles $1,$2 . . . . . S~ avec les probabilit6s respectives Pl, P2 . . . . . P, , A chacun des (( tirages }~ correspond une entropie H ~(la m~me si les P~ sont ind6pendantes des tirages ant6rieurs). Cette entropie H d6pend des Pi. StIAr~No~ d6montre que H est

7 0 - -

t. 6, n ~ 3, 1951] EXPOSI~ SIMI>LITII~ DE LA TUI~ORIE ((

maximum lorsque les P~ sont ggales. 0n appelle (< entropie relative )> la quantit~ H, = H / H m ~ .

2,61. - - Redondance.

On appelle (( redondance )) la quan6t 6 D = 1 .... H,. Cette nouvelle quanti t6 jouera un r61e ' important lorsque nous examinerm~s la transmission du message dans une vole de t$16eommunications. SnxN~O~ donne [:l] une s~rie de considerations tr~s int&essantes sur ta e redondance ~ des langages parl6s.

2,62. - - ~ffet du codage,

Le codage, s'il laisse intacte la vitesse de trans- mission de l ' tnformat ion, agit sur la redondance.

Reprenons dans l 'exemple du paragraphe 2,511, la source donnant les 4 symboles A, B, C, D, a v e c l a r fpar t i t ion P A = I / 2 , P/~ = ] /[~, PC ~ PO =- 1/8, et l 'entropie H = 7/~ (logons par symbole).

C'est pour la r6part i t ion

que s 'obt ient la plus grande entropie Hmax = 2. L 'entropie relative est H~ = 7/8.

et ta redondanee D = I ~ 7 /8 = ~l/8. Si, maintenant , on p r e , d le nouveau code, los

probabilit6s des symboles 0 et t sont 6gales, et l 'entropie est alors ~gale h l 'entropie maximum. La redondaace est alors hullo.

De mgme, dans Fexemple du paragraphe 2,512, la redondance est

. h,~ N D = ' I - ' ~ - ~ , si N 2 > I .

3/

Le ealeul de l 'entropie maximum ne pout se faire di reetement dans ee eas, car il y a une infinit6 de symboles possibles, ce qui donnerai t une entropie infinie. Si on limitait h N te hombre de cos symboles, on aurait :

Hm~x = Log N

et on aurait H ' - - H ~ et D' = 0. Le codage a, en tou t ~tat de cause, consid6ra-

blement diminu6 la redondanee D.

3. LA VOlE DE TIRANSMISSION.

Jusqu'iei , nous n 'avons parl6 que de la source du message, et n 'avons fair porter nos statist{ques que sur les symboles qu'elle produit , en examinant Ies offers du codage. [l faut mait t tenant aborder i '6tude de la voie de transmission. S g ~ o ~ distingue deux c a s : la vole sans bruit , et ta voie avec bruit.

I[ pout semhler curieux, paur qui se rappe~le ta formule de HAn'rLEY (*), de vouloir a t taeher h une voie sans brui t une capacit6 finie. Mais il ne faut pas

INFORMATIONNELLE ~) DE SHANNON 5/i0

oublier que, jusqu'ici, SaANNOr~ ne consid~re que des sources discr~tes de symboles du type << T616graphie ~. (Certaines t616commandes sont de ce type.) Le hombre d%tats discernables est fini, m~mc en l 'absence de bruit .

3,:L - - V o i e d e t r a n s m i s s i o n e n l ' a b s e n c e d e b r u i t .

SHANNON donne, comme d6finition de la capacit$ C d 'une vo ie :

(2) c = lira 1o~ ~ (T) r - ->~ T

ou N(T) est le nombre total des messages possibles de dur6e T. Notons que le mot ~c voie de trans- mission ~ prend, h ce stade de l'expos~ de SHANNON, un sens un pea particulier. Alors q u e e e mot 6voque habituel lement un dispositif physique (ligne, liaison radio), en fait il s 'agit ici plut6t de syst6mes conven- tionnels de reprfsentat ion des messages par des symboles.

3 , 1 t . - - Symboles de m~.me duroc.

Reprenons, par exemple, Ie eas du paragraphe 2 ,5 IL La source peut d6biter 4 symboles A, B, C, D, que nous supposerons encore de dur6es ggales h l 'unit6 de temps z.

Par ~c voie ~ on entendra iei un dispositif capable d'6eouler les signaux correspondant a un message form6 d 'un assemblage quelcouque de symboles choisis parmi 4 symboles donn6s, de mgme durge, A, B, C et D.

Un message eomprenant P symboles, et dont ]a dur6e est T == ":P peut fitre realis6 de N ~ 4 P mani~res diff6rentes. L 'applicat ion de la formule 2 donne :

C ~ 2 par unit~ de temps.

On re t rouve iei, aver une cadence de I symbole par unit6 de temps, la paleur de I'entropie maximum. Comme nous le verrons, ee r6sultat est g6n6ral.

3 , t 2 . - - Symboles de durdes diff~rentes. Suites de Marko f f .

lci, le probl~me se eomplique beaueoup. Le r6- sultat d 'ensemble subsiste, e n c e sens que pour de

log N i T ) tongues s6ries, Ie rappor t T tend toujours

vers une timite. SHAN~O~ donne de ceci deux exemples :

i ~ S6quenee de symbole~ S~, 5'~ . . . . S,, de durges respectives t> t2 . . . . t,,. Dans ee eas :

C = Log X,

o/t X~ e~t ta plus grande racine positive de l '6qua- t ion

X-~, + X- t , + . . . + X-~,, = 1 (**).

(*) Su ivan t la formule de H.*.I~,TI-~:Y, le d6bi t d: I n f o r m a t i o n d ' une voie avec un bru i t B, t r a n s p o r t a n t un signal S aver une b a n d e passan te W, est : W log (1 4- S/B).

(**) I1 est tou jours un peu g~?nant, pour Fing~nieur ou le physieien, de voir figurer en exposanl. , ou sous le ~igae log, une quan t i t6 non d6pourvue de dime~siol>. 1J,:t lel I~ctet~r

g~ rec t i l ic ra i t de lui-mfm~e cn 6cr ivant , au. lieu de ti, ~., v ~tant

une dur6e in t r ins6que prise pour unit6 de t emps . Ceci n ' e s t pas une s imple obse rva t ion de forme. Dans les app l i ca t ions (61ectriques pa r exemple) z appa ra l t r a sous la forme de

L constante,s de temps relies que CR, ~, etc. Nous verrons

d 'a i l leurs par la sui te q u ' o n gagnc beaucoup de c[arth e.n r6cr ivant de faqon homog6ne los formules de SHANNON.

- - 7 t - -

6/10

2 ~ Cas du t616graphe, off il y a 4 symboles de dut ies diff6rentes, avec des servitudes suppl6men- taires.

3,t3. - - Le thdor~me f o n d a m e n t M de la vole sans br td t .

Ce thfor6me s'6nonce ainsi : Soient une source ayan t une entropie H ( e n logons

par symbole) et une vole ayan t une capacit6 C (en logons par unit6 de temps). I1 est possible de coder les symboles issus de la source de far h t ransmettre l ' information h une vitesse moyenne 6gale h C / H -~- z par unit6 de temps (r 6rant aussi petit que l 'on veut).

I1 est impossible de t ransmet t re l ' information h une vitesse moyenne plus grande.

3,13t. - - Cas des symboles d'dgale durde.

L'6galit6 formelle des deux hombres nH et C (n 6tant le hombre de symboles 6mis par la source dams l 'unit6 de tamps) est ici tr~s facile h 6tabllr dams le cas suivant :

Soit N le hombre des symboles (c'est & la [ols le hombre des symboles pouvant gtre 6mis ~par la source et celui des symboles pouvant gtre v6hicul6s par la voie). L'entropie maximum H ~ x est obtenue pour une r6partition 6quiprobable des N symboles de la source. ComBe, dams ce cas, P~ ---- ~ /N :

(3) Hmax -=-- log N.

La capacit6 C s'6crit, d'apr~s la d6finition :

C = l ib -i T log P(T).

Le hombre P(T) de s6quences de dur6e totale T se calcule de ]a fa~on suivante :

S'il y a n symboles par unit~ de temps il y en aura n T pendant la temps T. Le nombre de s6quences possibles de dur6e totale T, c'est-h-dire comprenant n T symboles, est :

P(T) = N ~ ;

donc la capacit6 (en logons par unit6 de temps) est C --~ n log N ~ nHmax.

Partons maintenant d 'une source comportant une certaine (( redondance ~). Son entropie par symbole est H at elle d6bite m symboles par unit6 de temps. Supposons qu'on puisse la coder de relic fa~on que, dams le nouveau code, l 'entropie soit 6gale h l'en- tropic maximum Hm~x. On salt que, dams ces conditions :

n . H m a x ~ rn . H ;

donc, dams ce cas-llmlte :

C = m H et m = C / H .

3 , 1 3 2 - Cas gdndral : Probabilitds di/~drentes.

Consld6rons un long message, de N = m T symboles choisls dams la collection $1, $2, . . . . , Sk. I1 contiendra, area une grande probabilit6, N P 1

J . L O E B [ANNALES DES TI~LI~COMMUNICATXONS

symboles $1, N P 2 symboles $2, etc .... La probabilit6 d 'un tel message est :

p = p ~ pNe, pN~k 2 . . . . . k

et

log s P = N E P~ log Ps = - - NH.

H peut ainsi ~tre interpr6t6e comBe le quotient par N de log (1/P), P 6rant la probabilit6 d 'un long message-type.

On aurait doric P = 2 -Nz. Les longues s6quences ont doric routes la mgme

probabilit6. Or la somme de ces probabilit6s dolt ~tre 6gale h i ; nous connaissons doric leur nombre moyen M, qui est :

M = 2 ~v~ = 2~rH.

I1 s'aglt ici des messages de probabillt6 (r suffisam- Ben t grande ~) (SHANNON pr6cise ce point).

Effectuons maintenant un codage tel que Fen- tropic maximum Hmax soit r6alis6e, et soit n la cadence d'6mission des nouveaux symboles. Le hombre moyen des s6quences de dur6e totale T e s t :

2nT Hmax.

La capacit6 C du canal 6tant, on le salt, d6finie comBe

C = liB T log M,

est doric 6gale h C = nHma,. Le r~sultat du paragraphe 3 , i3 i se trouve ainsi

g6n6ralis6. I1 n 'y a d'ailleurs pas de diff6rence essen- tielle entre la d6finition de SHANNON et le r6sultat de l 'application de la formule de HARTLEY au cas continu. Dams la formule (3), Hm~ n'est rien d'autre, dams le cas des probabilit6s 6gales, que le logarithme du hombre d'6tats discernables que peut prendre la vole. ComBe nous le savons et comBe cela sera pr6cis6 par la suite, le hombre d'6tats discernables d'une vole peut ~tre d6fini par le rapport signal/bruit.

Quant h n, il figure ici h la place de la bande passante : on conCeit que, si la vole est capable de t ransmet t re n symboles par unit6 de temps, elle peut 6galement en t ransmet t re un hombre inf6rieur.

3,14. - - Le codage o p t i m u m .

Le probl~me de l ' adapta t ion d'une source h une vole se rambne h la recherche d 'un codage. Celui-ci dolt conduire n6cessairement - - pour avoir Fen- tropic maximum - - h l 'utilisation de symboles 6qui- probables, en hombre 6gal au hombre de symboles diff6rents que la vole est susceptible de transmettre. SKANNO~ g6n6ralise le proc6d6 indiqu6 au para- grapha 2,5i i , en faisant en sorte de repr6senter les symboles les plus fr6quents par les codes les plus courts (MoRsr. avait d6jh fait quelque chose dams ce genre).

I1 semble qu'il manque un point ~ sa d6monstra- tion ; pour ~tre efflcace, le codage doit conduire h l 'entropie maximum, c'est-h-dire qu'on dolt avoir

7 2 - -

t . 6 , n o 3 , 1 9 5 1 ] E X P O S I ~ S I M P L I F I E D E L A T H E O R I E

(comme au paragraphe 2,511) un code dont les 616ments binaires sont 6quiprobables.

Par ailleurs, il faut remarquer avec P. AmnAIN [2] qu 'un tel codage n6cessite la connalssance de la r6partition statistique de l 'ensemble des symboles, c'est-~-dire qu'il suppose au pr6alable l '6coulement d 'un temps - - th6oriquement infini - - permet tant et d 'en faire la statistique. Bien entendu on est folld6

admettre en pratique que eette connaissance statistique s 'obtient avec une approximation sufli- sante au bout d 'un temps relativement court.

3 ,2 - - V o i e de t r a n s m i s s i o n a v e c brui t .

Jusqu'ici , nous n'avons 6tudi6 que l 'adapta t ion d 'une source fi la vole de transmission. Nous avons suppos6 que cette vole achemine ]e message sans (<rien en perdre )) en route, c'est-h-dire qu'elle 6tablit une relation bi-univoque entre le symbole qu'elle re~oit et celui qu'elle d61ivre. Lorsqu'un circuit est le si6ge d 'un bruit, eette relation bi-uni- voque eesse d'exister, et lorsqu'on regoit un symbole

t , . , S i ~ 1 arrlvee, on ne sait plus avee certitude quel a 6t6 le symbole Sk qui l 'a produit.

Nous ferons porter l 'analyse sur le eas le plus simple, eelui des probabilit6s ind6pendantes.

Nous sommes en pr6senee de deux ph6nom~nes al6atoires, le signal et le bruit. Soient x~ les symboles

l'entr6e, et y~ les symboles ~ la sortie. L'existence du bruit se t radui t par le fait qu'au

symbole re~u y~ peuvent correspondre un certain et hombre de symboles xi. Nous appellerons Pi(i) la probabilit6 pour que, x~ 6rant donn6 ~ l'entr6e, on re~oive y~ h la sortie. En l'absenee de bruit, on a :

P~(i) = a~ - - l 0 si i # i l s i i = i .

Nous appellerons P(i, i) la probabilit6 pour que l 'on ait ensemble un symbole xi h l'entr6e et un symbole y~ ~ la sortie.

I1 faut remarquer que la collection des P(i,]) d6pend h la fois de la r6partition statistique des xr et de celle du bruit sur la vole de transmission. Dans le cas de l 'absence de bruit,

P(i, i) = 8 q. La r 6 p a r t i t i o n en p robab i l i t6 des x,i est donn6e par

s p(i) = p(i , i)

( h u n facteur de normalisation pros). Pour ealculer P~(]'), il suffit d'appliquer la formule

des probabilit6s compos6es P(i, ]) - - P(i) P~(i), qui t radui t le th6or~me : la probabilit6 pour que l'on ait en mSme temps xi et y~. est 6gale au produit de la et probabilit6 pour que, x 6tant x~, on ait y = Yi, par la probabilit6 de trouver x~. Done :

P,(i) = p(i, i)/P(i) = p(i, i) / ,~ P(i, i). et I i

On d6finirait de mCme

p~(i) = p(~, i ) /P(i) , av~o P(i) = ) -~ p ( i , i ) 4

(( I N F O R M & T I O N N E L L E )) D E S H A N N O N 7/10

3 ,21 . - - E n t r o p i e c o n d i t i o n n e l l e .

D6signons par H(x) et H(y) respectivement l 'entropie des symboles 6mis et celle des symboles re~us :

H(x) = - - Z P~.log Pi

H(y) = - - ~ P~.log Pj. J

Dgsignons de m~me par H(x, y) la somme - - Y~P(i, i ) . l og P ( i , 1).

Formons maintenant , pour ehaque valeur d'indiee i du symbole x, l 'entropie

Hi = - - s Pi(]) log P*(i)

et d6signons par H~(y) la somme pond6r6e de toutes ces expressions :

H~(y) = - - s H,P(i) = - - s e(i, ])log P,(]) i i , j

= - - s p~.j [log P(i,]) - - log P(i)]

= H(x, y) - - H(x).

On d6finirait de m~me

H~ = - - s Pj(i) log Pr i

XI XI H~(x) = - - ff.~ HiP(i) = - - ff.~ P(i,])log Pj(i)

= H(x, y) - - H(g).

3 , 2 2 . - Pe r t e d ' In format lon due au brui t .

La quantit6 H~(x) mesure l ' incertitude moyenne apport6e par le bruit sur x, y &ant donn6. SHANNON l'appelle (~ ]~quivoeation )). Nous eonviendrons d'appeler vitesse de transmission effective ]a quan- tit6 :

n R = n ( H ( x ) ~ H~(x)) (*).

Les figures I a, I b, I c repr6sentent la probabi- lit6 P~j par un point de coordonn6es i e t ]. Les proba- bilit6s 61ev6es y sont repr6sent6es par des cercles (fig. t a), les probabilit6s moyennes par des croix (fig. I b), les probabilit6s tr~s petites par de simples points (fig. i c).

Enl 'absenee de bruit (fig. i a), P( i,]) = P~( i) = ~, pour

i # i, P( i , i )=O

p( i , i) log p~(i) = o

i = ], Pj(i) = t, log Pa(i) = 0

P( i, i) log pj( i) = o.

On retrouve R = H(x).

(*) Rernarquons que H(x) - - H~(x) -= H(x) + H(y) - - H(x, y).

- - 73

@

@

g

i F~r ~l a. ~ Absence de b r u i t :

correspondanee b l -univoque entre ies ~ymboles xr et y~.

J . L O E B

/ / /

/ / / / / /

4 - / j , / / / /

+ + +~ /~ + + + §

4 - + + + ~ + + + + §

$ + 4 - + +

I 4 - + + 1

Fr~. I b. - - Bruit mod6r6 : un symbote Yi re~u correspond fi 5 sym- boles x~ possibles.

Avec un bruit mod6r6 (fig. i b) l '6quivocation est diff6rente de 0, mais faible.

Enfin (fig. t c) le bruit est tel qu'il n 'y a plus aucune corr61ation entre x et y :

P(i, i) = P(i).P(i)

P , ( i ) = - P ( i ) . P ( i ) / ~ P ( i , i ) = P ( i )

Hdx) = - - ~_~ P(i) P(i) log P(i) ~,J

= H(x) E P(]) =- H(x),

et l~ = 0, comme on devait s 'y attendre.

3,221. - - Capacit~ d'une r avec bruit.

Par extension de ce qui a 6t6 dit nous appellerons capacit6 C le produit :

C : n X maximum de [H(x) - - H~(x)]

n ~tant le hombre de symboles par unit6 de temps, et le maximum dtant obtenu en ]aisant varier, pour routes les sources compatibles a~ec la ~oie, les lois de proba- bilit~s.

3,23. ~ Thgor~rne i o n d a m e n t ~ l de 1~ vole ~ v e c b r u i t .

I1 s'6nonce de la fa~on suivante : Soit une voie de capacit6 C (nouvelle d6finition du

w 3,22t) et une source, d'entropie H, d6bitant h la cadence de n symboles par unit~ de temps. (*)

Si n H < C, il existe un syst~me de codage tel que les symboles fournis par la source puissent etre transmis sur la vole avec une fr~quence d'erreurs aussi petite que l'on vent (ou une 6quivocation aussi petite que l 'on veut).

Si nH > C, on peut coder la source de telle fa~on que l '6quivocation soit inf6rieure h n H - C - ~ r (z arbitrairement petit). On ne peut pas trouver de code tel que l '6quivocation soit inf6rieure ~ nH - - C.

L'id6e de base vient d 'un proc~d6 connu depuis longtemps, et destin6 h permettre la transmission

[ A N N A L E S D E S T ~ L ~ C O M M U N I C A T I O N S

p �9 o �9 �9 �9 I �9 �9 �9 I

u �9 Q �9 a �9 �9 �9 �9 �9 *

Q �9 �9 �9 Q �9 , �9 @ �9 9

u �9 �9 �9 �9 ~ e) �9 �9 �9 �9

�9 �9 �9 �9 e �9 �9 �9 �9 �9

�9 �9 @ �9 �9 �9 �9 �9 �9 �9 �9

�9 �9 �9 �9 ~ 4J �9 �9 �9 �9 �9

�9 �9 �9 �9 �9 �9 �9 �9 �9 �9 �9

l

FI~. 1 c. - - Brui t intense : un symbole yi quelconque a pu ~tre produi t pa r n ' impor te quel sym- bole x~.

correcte des messages h travers le bruit : la r6p6- t i t ion des symboles. Par exemple M. VERDXN, Ing6nieur en Chef des P. T. T., a r6alis6 un syst6me de transmission radio61ectrique du t61~graphe BAUDOT, consistant darts la r6p6tition des signaux, Si chaque signal est r6p6t6 3 fois, et si ]e bruit compro~nct la transmission de I sat 3, il reste e , moyenne deux signaux corrects. On adoptera comme signal re~u celui qui sera r6p6t6 au moins 2 fois. On volt donc que si le bruit' ne d6passe pas un certain niveau, tout en 6rant capable d'alt6rer i signal sur 3, on pourra coder l'6mission de fa~on h ne perdre prat iquement aucun symbole.

On peut calculer la redondance des signaux BA.UDoT-VERDAN, ell supposant que le codage h l signal conduit ~ l 'entropie maximum H ~ x . L'en- tropie du BAUDoT-VERDAN est H m ~ / 3 et la redon- dance est 2/3. On aarai t pu croire, dit S~A~or~, qu'il aurait fallu une redondance infinie, pour annuler pratiquement toute chance d'erreur. I1 n'en est heureusement rien.

Le th6or~me fondamental se t radui t par le dia- gramme de la figure 2, off l 'on a port6 en abscisses n fois les entropies des messages h envoyer, et en ordonn6es n fois l '6quivocation r~siduelle que Iaissera Ie meilIeur codage. L'abscisse C repr6- sentant la capacit6 de la voie, taut que n H (x) < C, on peut atteindre une transmission statistiquement par[aite. D~s que ni l(x) > C, nH~ (x) ne peut pas descendre au-dessous de ni l(x) - - C.

Nous allons examiner la d6monstration de SHAr~Or~ en insistant sur les' hypoth6ses faites plus que sur les d6veloppements math6matiques. l%marquons d 'abord qu'ici le mot ~ codage ~ n'a pas le m~mc sens qu 'au paragraphe 2,5. I1 ne s'agit plus ici de choisir un nouveau groupe de symboles, dont le nombre diff6re du nombre des symboles de base, de fa~.on h s 'adapter h la constitution de la voie. Nous savons qu'unc telle op6ration modifie corr61ativement le nombre n de symboles par unit6 de t e m p s ; or maintenant Snx~Nor~ ne fair pas figurer n dans ses calculs, et ce fait montre qu'il ne

(*) L ' a u t e u r pread iei ]a ]ibert6 de modifier la presenta t ion des formules de S~ANNON, de fa~on & leur re~ldre ] 'homog6- n6tt6 physique. Le seas g6n6ra[ de l 'expos6 ne s 'ea t rouve pas

modifl6, mais eette pr6sentat ion 6vite au leeteur de se poser des questions dont la r6ponse n 'es t pas imm~dia tement 6videate.

74 - -

t. 6, n ~ 3, 1951]

peut y avoir dans la suite de la d6monstration qu 'une seule r de n : la cadence des symboles /ournis par la source it l'entrde de la vole.

0 c Hgx) FIG. 2. - - L ' 6 q u i v o e a t i o n poss ible p o u r une v a l e u r d o n n @

de l ' en t rop i e des m e s s a g e s 6mis h l ' en t rbe d ' l lne voie de eapa - eit6 C.

EX['OSI:I SIMPLIFII:: DE LA TI IEORIE (( INFORMATIONNELLE )) DE SHANNON 9 / 1 0

Le (( eodage )) tel qu'il faut l 'entendrc maintenant (et qui cst en fair une g6n6ralisation du proe6d(~ BAUDoT-VEnDAN), eonsiste h a]outer au signal d'entr6e un message eompl6mentaire, dent les symboles auront une correspondanee d6finie avee eeux du message initial (double r6p6tition dans le cas du BAUI)oT-VnnDAN). Ce nouveau message n'apporte pas de nou~,elle in/orraation : il introduit la redondance n6cessaire.

Soit n B la cadence de d6bit d ' information de cette source (ni l < C). Pour le temps T, et dans les limites d 'une probabilit6 (( suftisamment grande )), la situa- tion est la suivante :

1 ~ une sdquence dmise par la source pendant ce temps fair pattie d 'une multiplieit6 (x) de 2 ~rn(xl possibles ;

2 ~ une sdquence refue pendant ee temps, fait partie d 'une multiplicit6 (y) de 2 ~zm~) possibles ;

30 toute sdquenee recue (y) provient d 'une sdquence dmise (x) qui est li6e par la condition d'appartenir

une muhiplieit6 de 2 nTnv(~) possibles. 4 ~ La source suppl6mentaire aura fourni de son

e6t6 pendant ee temps un appoint de symboles dent l 'agencement appart ient h une nmltiplieit6 de 2 "T~ ageneements possibles.

I1 y a maintenant une articulation du raison- nement sur laquel]e SHANNON passe tr6s rapidement, mais qu'il est essentiel de mentionner : la th6orie n6glige eompl~tement d'6noneer les relations entre ehaque symbole original et les symboles sura- jout6s ; elle se eontente de consid6rer toutes les eorrespondances possibles, portant sur les s6quences de probabilit6s (( sufIisament grandes )), et de faire la moyenne de la fr6quence des erreurs pour eette vaste classe de syst6mes codeurs possibles.

Nous allons ealculer la probabitit6 pour q/re, un message yx 6tant regu, il y air plus d 'un message dans l'ensemble des causes possibles de y~, c'est-h- dire pour qu'il se produise une erreur.

I1 y a 2~zz messages (suppl6mentaires) distri-

bu6s au hasard parmi 2 nTHIz) points al6atoires, la probabilit6 616mentaire de localisation en tel de ces points en partieulier 6rant

2nTR/enTH(x) _~ 2n2[/~--//(~)1.

L'exposant est bien n6gatif, comme R - H(x) ; on a m~me :

n < H(x) - H~(x),

de sorte que l'on peut poser, ~1 6tant une certaine quantit6 positive :

B - - H(x) = - - Hv(x) - - "~.

En d6signant par q le nombre des causes possibles de l 'une quelconque des s6quences revues,

q -=-- 2nTHVx),

l'expression de la probabilit6 616mentaire en question est alors 2--'~T~/q, et la probabilit6 compl6men- taire t - - 2--'~T~/q. En 6levant "~ la puissance q cette derni~re probabilit6, on obtient la probabilit6 P pour qu 'aucun des points ne soit un message (sinon le message originel lui-m~me), c'est-~-dire pour qu'il n 'y air pas d'erreur :

P = [1 - - 2 - ~ / q ] q .

Lorsque T augmente ind6finiment, et q aussi par eons6quent, on a :

p t'~ 1 -- 2 -nT~l.

]len r6su]te bien que la probabilit6 pour que se produise une erreur tend vers z6ro, et cela de fa~on d ' au tan t plus aeeentu6e que sera plus grande la quantit6 ~ qui mesure en quelque sorte la marge avee laquelle se trouve r6alis6e l'infigalit6 admise par hypothbse, h savoir

B < H ( x ) - - H v ( x ) ou nIl < C.

I1 y a ici un 6change entre le message des x e t le message comp16mentaire d'entropie B. Le th6or~me est donn6 pour /{ , mais les deux sent 6videmment interchangeables.

Donc si n B < C il existe, sauf exceptions de probabilit6 prat iquement nulle, un codage (dent la th6orie n'indique pas comment le r6aliser) qui permet de faire correspondre une seule s6quence d'entr6e h une s6quence revue y.

La derni~re pattie du th6ordme se d6montre par l 'absurde : Supposons que nous sachions coder une source avee n B = C -}- a de fa~on h obtenir une 6quivocation Hv(x) telle que n H v ( x ) - = a - (e > 0), alors :

ni l = ni l (x) + ~ = C + a et

n(H(x) - - Hv(x)) = C + ~.

Ceei eontredit la d6finition de C comme maximum de H(x) - - H~(x).

~. CONCLUSION.

Le paragraphe 3,2 dolt nous conduire h des r~gles d'action diff6rentes de eelles que le paragraphe 3,1 nous avait sugg6r6es.

- - 7 5

1o/1o En l'absence de bruit, il y a int6r~t h presenter h

l 'entr6e de la vole de transmission des messages cod6s de fagon h rendre rentropie maximum. C'est la condition n6cessaire pour tirer de la vole de transmission le maximum de ce qu'elle peut rendre.

Mais, sous cette forme (( compacte )) le message est tr~s fragile, et si un de ses symboles est alt6r6 en cours de route, on ne peut compter sur le (( contexte )) pour le r6tablir.

Or le bruit a jus tement pour effet de d6t6riorer les messages en introduisant des erreurs. On est alors conduit h proc6der h une r6p6tition des symboles (ou h une op6ration analogue) qui produit une dimi- nution du rendement, mais une augmentat ion de Ia s6eurit6.

Un des r6sultats les plus int6ressants des t ravaux de SHAr(NON est le fair que la s6curit6 ne se paie pas trop cher : une diminution limit6e de l 'entropie permet d'~liminer les erreurs d 'une fa~on statisti- quement complete.

Le pr6sent expos6 simplifi6 ne concerne d'ailleurs que la premiere moiti6 du travail de SHANNON, consacr6e au cas discret, c'est-~-dire au cas off l 'on n'a affaire qu'h des sources susceptibles de produire un hombre fini de symboles. De mgme, l'expos6 qui fera suite a celui-ci [4] sera uniquement construit sur cette th6orie(( discrete )).

Dans la seconde moiti6 de son article, SHANNON consacre au cas continu, une 6rude extr~mement int6ressante, d 'un point de rue th6orique surtout. En ce qui concerne la T616commande et la T616- mesure, on peut prendre un (( raccourci )) fond6 en partie sur la formule de HAnTLEY (formule dont la prochaine 6tude ici mentionn6e donnera un cer- tain nombre de variantes). Une grandeur physique, continue en apparence, ne peut en r6alit6 prendre qu 'uu nombre fini de valeurs discernables.

On dolt conclure du pr6sent expos6 que SHANNON

J , L O E B [ANNAI.ES DES T~LI~COMMUNICATIONS

a fait faire un progras 6norme dans la th6orie des T616communications, en eessant de consid6rer le signal comme la r6alit6 fondamentale, et en mont ran t que ce dernier n'est qu 'un revgtement prot6iforme du message. I1 a de plus introduit une d6finition math6matique correcte et f6conde d 'une notion jusqu'ici peu pr6cis6e, la (( Quantit6 d' Information )~. Les techniciens doivent maintenant appliquer ces notions dans les probl6mes pratiques qu'ils ont traiter dans leurs domaines respectifs.

En terminant , j 'adresse rues plus vifs remer- ciements h M. Robert VILLENEUVE, ing6nieur en chef des P. T. T., dont les conseils et les critiques constructives ont beaucoup am61ior6 la forme et le fond de cet article.

Manuscrh remis le 12 ]anvier 1951.

BIBLIOGRAPHIE

[l] SHANNOr~ (C. E.), Une th6orie math6matique des t616communications. (A mathematical theory of communications.) Bell. Syst. Teehn. d., (U. S. A.) (Juillet 1948), 27, 3, pp. 379-423. (Octobre 1948), 27, 6, pp. 623-656.

[2] AICRAIN (P.), Th6orie des communications. Ann. Telecommttnic. (Fr.) (D6c. 1969), 4, n ~ 12, pp. 400-

[3] Si~xNrr (C. E), Rdcents d6veloppements dans la th6orie des communications. (Recent develop- ments in communication theory.) Electronics (U. S. A.) (Avril 1950), 23, n ~ 4, pp. S0-83.

[6] LOEB (J.), Une th6orie r informationnelle ~) de la mesure et de la t616mesure. Ann. Telecommunic. (~ paraltre).

[5] FORTET (R), Remarques math6matiques sur la notion d'Entropie. Note pr6sent6e h la IX ~ne as- sembl6e g6n6rale de I'U. R. S. I. (Zurich, Septembre 1950).

[6] VILL~ (J.), Rapport sur la Th6orie de l'Information. Note pr6sent6e "~ la IX ~me assembl6e g6n6rale de I'U. R. S. I. (Zurich, Septembre 1950).

- - 7 6