Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n � T e o ría d e la In fo rm a c ió n � T e o re m a F u n d a m e n ta l d e la T e o ría d e la In fo rm a c ió n . � T e o ría m a te m á tic a d e la s c o m u n ic a c io n e s � P rin c ip io s d e la tra n s m is ió n d e In fo rm a c ió n � M o d e lo d e u n S is te m a d e T ra n s m is ió n d e In fo rm a c ió n � C o n c e p to d e In fo rm a c ió n � M e d id a d e la in fo rm a c ió n � E n tro p ía � R e d u n d a n c ia . R e d u n d a n c ia d e u n a F u e n te � T a s a d e in fo rm a c ió n � C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o � C o d ific a c ió n d e lo s M e n s a je s � C o d ific a c ió n d e la F u e n te Te o ría d e la In fo rm a ció n La Teo ría d e la In fo rm ació n es u n a teo ría m atem ática cread a p o r C lau d e E. Sh an n o n y W arren W eaver en el añ o 1 9 4 8 y q u e fo rm a la p ied ra an gu lar so b re la q u e se h a d esarro llad o to d a la teo ría actu al d e la co m u n icació n y la co d ificació n . La Teo ría d e la In fo rm ació n se en cu en tra aú n h o y en d ía en relació n co n u n a d e las tecn o lo gías en b o ga,In tern et. D esd e el p u n to d e vista so cial, In tern et rep resen ta u n o s sign ificativo s b en eficio s p o ten ciales, ya q u e o frece o p o rtu n id ad es sin p reced en tes p ara d ar p o d er a lo s in d ivid u o s y co n ectarlo s co n fu en tes cad a vez m ás ricas d e in fo rm ació n d igital. En gen eral, el p ro b lem a q u e se p lan tea d e reso lver co n la Teo ría d e la In fo rm ació n es la d e: “P o d e r tra n sm itir in fo rm a ció n a la m á xim a ve lo cid a d p o sib le p o r u n ca n a l d e co m u n ica cio n e s, co n u n a m ín im a ca n tid a d d e e rro re s p o sib le ” U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Sh an n o n se p lan teo elsigu ien te p ro b lem a: “D a d o u n co n ju n to d e m e n sa je s p o sib le s q u e u n a fu e n te p u e d e p ro d u cir, ¿ C ó m o d e b e n re p re se n ta rse e sto s m e n sa je s p a ra q u e la in fo rm a ció n se a co n d u cid a d e la m e jo r m a n e ra so b re u n siste m a d a d o co n su s lim ita cio n e s física s in h e re n te s? ” La id ea es p o d er d eterm in ar la fo rm a en q u e esto es p o sib le y si existe algu n a co ta m áxim a p o sib le d e alcan zar La Teo ría d e la In fo rm ació n es u n tem a m atem ático q u e trata co n tres co n cep to s b ásico s: 1 . La m e d id a d e la in fo rm a ció n 2 . La ca p a cid a d d e u n ca n a l d e co m u n ica ció n p a ra tra n sfe rir in fo rm a ció n 3 . La co d ifica ció n co m o u n m e d io d e u tiliza r lo s ca n a le s a to d a su ca p a cid a d . Te o ría d e la In fo rm a ció n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Esto s co n cep to s están ligad o s al teo rem a fu n d am en tal d e la teo ría d e la in fo rm ació n , q u e p u ed e resu m irse d e la sigu ien te m an era: “D a d a u n a Fu e n te d e in fo rm a ció n y u n ca n a l d e co m u n ica ció n , e xiste u n a té cn ica d e co d ifica ció n ta l q u e la in fo rm a ció n p u e d e se r tra n sm itid a so b re e l ca n a l a cu a lq u ie r ra p id e z m e n o r q u e la ca p a cid a d d e l ca n a l y co n u n a fre cu e n cia d e e rro re s a rb itra ria m e n te p e q u e ñ a a p e sa r d e la p re se n cia d e ru id o ” El asp ecto so rp ren d en te d e este teo rem a es la tran sm isió n lib re d e erro res so b re u n can al ru id o so , lo q u e se o b tien e p o r m ed io d e la co d ificació n . Te o re m a F u n d a m e n ta l d e la Te o ría d e la In fo rm a ció n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Te o ría m a te m á tica d e la s co m u n ica cio n e s Sh an n o n d esarro lló la “Teo ría m atem ática d e las co m u n icacio n es” q u e ten ia co m o o b jetivo : H a ce r lo m a s e ficie n te p o sib le la tra n sm isió n d e in fo rm a ció n , co n u n n ú m e ro m ín im o d e e rro re s. La co d ificació n se em p lea p ara ad ap tar la fu en te alcan alp ara u n a tran sferen cia d e in fo rm ació n co n u n m áxim o d e co n fiab ilid ad . N o s lim itarem o s a lo s co n cep to s d e m ed id a d e la in fo rm ació n y a la cap acid ad d el can al. C o n lo cu al se resp o n d erá a las sig., p regu n tas: � ¿C o m o restrin gen a la tran sm isió n d e in fo rm ació n las lim itacio n es físicas fu n d am en tales ( an ch o d e b an d a y ru id o ,etc.) ? � ¿Existe algo así co m o u n sistem a d e co m u n icació n id eal y d e h ab erlo cu ales serian su s características? U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S P rin cip io s d e la tra n sm isió n d e In fo rm a ció n La C o m u n ica ció n : e s e l p ro ce so m e d ia n te e l cu a l se tra n sfie re in fo rm a ció n d e sd e u n p u n to e n e l e sp a cio y e n e l tie m p o , d e n o m in a d o “fu e n te d e in fo rm a ció n ”, h a sta o tro p u n to d e n o m in a d o “d e stin o d e la in fo rm a ció n , co n e l m ín im o d e p e rd id a s o p e rtu rb a cio n e s. La rep ro d u cció n p erfecta d elm en saje n o es p o sib le,p ero d esd e u n p u n to d e vista p ractico es su ficien te q u e la rep ro d u cció n se a h ech a co n u n a ap ro xim ació n o fid elid ad q u e d ep en d e d e la calid ad o fin q u e se p ersiga ( Q o S?) En to d o caso , en el p ro ceso d e tran sm isió n , la in fo rm ació n exp erim en tara siem p re u n a cierta d egrad ació n , cu yo s lim ites d ep en d erán d elem p leo q u e se h aga d e d ich a in fo rm ació n . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M o d e lo d e u n S iste m a d e T ra n sm isió n d e In fo rm a ció n Fu en te d e In fo rm ació n : La in fo rm ació n o in teligen cia a tran sm itir se o rigin a en la fu en te d e in fo rm ació n . Esta se m ate rializa co m o u n co n ju n to (sin e n tra r e n d e ta lle s) fin ito y d iscreto ,d e N sím b o lo s o m en sajes d istin to s e in d ep en d ien tes cu yo sign ificad o es co n o cid o en eld estin o . H ay m u ch as clases d e fu en tes d e in fo rm ació n , in clu yen d o p erso n as y m aq u inas, d e m an era q u e lo s sím b o lo s o m en sajes p u ed en to m ar u n a gran varied ad d e fo rm as: secu e n cias d e sím b o lo s,letras,u n a m agn itu d q u e varia en el tie m p o , etc. P ero sin im p o rtar la n atu raleza d el m en saje el p ro p ó sito d el sistem a d e co m u n icació n es el d e p ro p o rcio n ar u n a rep lica m as o m en o s exacta d elm ism o en eld estin o . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M o d e lo d e u n S iste m a d e T ra n sm isió n d e In fo rm a ció n Tran sd u cto r d e En trad a: C o m o regla ge n eral, el m en saje q u e se p ro d u ce en la fu en te d e in fo rm ació n n o es d e n atu raleza eléctrica y p o r lo tan to se n ecesita u n tran sd u cto r o co d ificad o r q u e co n vie rta elm en saje en u n a señ alco m p atib le co n eltip o p articu lar d elsistem a d e tran sm isió n q u e se em p leara.En to n ces: � In fo rm ació n es la in telige n cia o sign ificad o q u e se va a tran sm itir, e s u n a en tid ad IN TA N G IB LE � M en saje es la m aterializació n d e la in fo rm ació n en u n a can tid ad M EN SU R A B LE. O se a e l m e n sa je e s e l so p o rte d e la in fo rm a ció n y q u e e l n u m e ro d e e le m e n to s d e l co n ju n to d e la s se ñ a le s d e sa lid a d e l tra n sd u cto r d e b e se r ig u a l a l n u m e ro d e e le m e n to s d e l co n ju n to d e sím b o lo s o m e n sa je s d e la fu e n te d e in fo rm a ció n . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M o d e lo d e u n S iste m a d e T ra n sm isió n d e In fo rm a ció n A n ch o d e B an d a y Po te n cia d e Tran sm isió n : So n d o s p arám etro s d e gran im p o rtan cia. Lo s siste m as d e co m u n icació n d eb e n d iseñ arse p ara u tilizar esto s d o s re cu rso s en la fo rm a m as eficien te p o sib le. En gen eral, es d ifícil o p tim izar am b o s recu rso s sim u ltán eam en te, o sea, u n recu rso p u ed e co n sid erarse m as im p o rtan te o m as e scaso q u e el o tro . Lo s can ales se lo s p u ed e asi clasificar co m o “lim itad o s en p o ten cia” o “lim itad o s e n an ch o d e b an d a”. Eje m p lo s: Lo s can ales telefó n ico s so n can ales lim itad o s en an ch o d e b an d a,lo s can ales d e R F (in alám b rico s) so n lim itad o s m as en p o ten cia. La m e ta id e a l e n e l d ise ñ o d e u n siste m a d e co m u n ica ció n e s la d e tra n sm itir in fo rm a ció n a la m á x im a v e lo cid a d co n e l m ín im o d e p o te n cia y a n ch o d e b a n d a . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n ce p to d e In fo rm a ció n En to n ces… el p ro p ó sito d e u n sistem a d e co m u n icació n es el d e TR A N SM ITIR IN FO R M A C IO N . Sin em b argo n o se h a esp ecificad o lo q u e realm en te sign ifica el term in o “In fo rm ació n ”, y m u ch o m en o s co m o se la p u ed e cu an tificar o m ed ir. C o n sid érese u n a situ ació n h ip o tética q u e se p resen ta: A . M añ an a sald rá el so l. B . M añ an a caerá gran izo C . M añ an a h ab rá u n sism o ¿C u ál es la in fo rm ació n m as p ro b ab le? O b viam en te la d eclaració n A ap o rta p o ca in fo rm ació n , p u es es la m as p ro b ab le. In tu itivam en te, se sab e q u e el en u n ciad o C co n tien e gran can tid ad d e in fo rm ació n , p u es tien e m u y p o ca p ro b ab ilid ad d e o cu rren cia, es d ecir P (C ) << 1 U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n ce p to d e In fo rm a ció n Po r co n sigu ien te, P (C ) < P (B ) < P (A ) y la in fo rm ació n I(C )> I(B ) > I(A ) Se o b serva q u e cu an d o m en o r sea la p ro b ab ilid ad d e u n en u n ciad o , m ayo r es la in fo rm ació n ap o rtad a p o r el m ism o ‚ y p o r tan to u n a m ayo r in certid u m b re o so rp resa en el m en saje. Es d ecir q u e la in fo rm ació n es u n a fu n ció n in versa a la p ro b ab ilid ad d e o cu rren cia d e u n even to . I = f (1 /P ), d o n d e f es u n a fu n ció n m atem ática a d eterm in ar. Esto co n d u ce a exp resar q u e la m ed id a d e la in fo rm ació n esta relacio n ad a co n la in certid u m b re, la in certid u m b re d e p arte d el u su ario acerca d e cu al será el m en saje. A . M añ an a sald rá el so l. B . M añ an a caerá gran izo C . M añ an a h ab rá u n sism o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n ce p to d e In fo rm a ció n IN C E R T ID U M B R E: � Se refiere a lo d esco n o cid o � N o se sab e si su ced erá � A lo in esp erad o � A lo im p revisib le LA IN FO R M A C IÓ N D ISM IN U YE LA IN C ER TID U M B R E P O R Q U E A P O R TA M A YO R C O N O C IM IEN TO SO B R E U N TEM A . P R O B A B ILID A D : Se en carga d e evalu ar to d as aq u ellas activid ad es en d o n d e se tien e in certid u m b re, acerca d e lo s resu ltad o s q u e se p u ed e esp erar. � La p ro b ab ilid ad es u n a escala en tre 0 y 1 � A l su ceso im p o sib le le co rresp o n d e el valo r “0 ” � A l su ceso segu ro le co rresp o n d e el valo r “1 ” � El resto d e lo s su ceso s estarán co m p ren d id o s en tre la escala d e 0 y 1 . LA P R O B A B ILID A D N U N C A P U ED E SER U N V A LO R N EG ATIV O LA SU M A D E TO D A S LA S P R O B A B ILID A D ES EN IG U A L A 1 U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n ce p to d e In fo rm a ció n : R e su m e n � En el extrem o Tran sm iso r la m ed id a d e la in fo rm ació n es u n a in d icació n d e la lib ertad d e elecció n ejercid a p o r la fu en te en la selecció n d e u n m en saje. � Si la fu en te p u ed e elegir lib rem en te en tre m u ch o s m en sajes d iferen tes, el u su ario ten d rá u n a gran in certid u m b re acerca d e cu al será el m en saje seleccio n ad o . � Pero si n o h ay p o sib ilid ad d e elecció n , si so lo h ay u n m en saje p o sib le, n o h ay in certid u m b re y en co n secu en cia tam p o co in fo rm ació n . � Es evid en te q u e la m ed id a d e in fo rm ació n in clu ye las p ro b ab ilid ad es. � Lo s m en sajes d e alta p ro b ab ilid ad in d ican p o ca in certid u m b re d el u su ario y llevan u n a p eq u eñ a can tid ad d e in fo rm ació n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M e d id a d e la In fo rm a c ió n En to n ces la au to in fo rm ació n aso ciad a co n u n even to A seria: Se d eb ería d eterm in ar la fu n ció n q u e cum p la lo s sigu ien tes req u erim ien to s: 1 . 2 .3. U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M e d id a d e la In fo rm a c ió n C u an d o se tran sm ite el m en saje A , el u su ario recib e IA u n id ad es d e in fo rm ació n . Si se tran sm ite tam b ién u n segu n d o m en saje B , la in fo rm ació n to tal recib id a d eb e ser la su m a d e las au to in fo rm acio n es : IA + IB Po d em o s h ab lar en to n ces d e u n m en saje co m p u esto : C = A B Si A y B so n estad ísticam en te in d ep en d ien te: P C = P A .P B y IC = f (P A .P B ) Pero la in fo rm ació n recib id a es au n IC = IA + IB IC = f (P A ) + f (P B ) Po r lo tan to : f (P A .P B ) = f (P A ) + f (P B ) 4 . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M e d id a d e la In fo rm a c ió n 1 . 2 .3. 4 . H artley-1 9 2 8 , d em o stró q u e la ú n ica fu n ció n q u e satisface las cu a tro co n d icio n es es u n a fu n ció n lo garítm ica d e la fo rm a: A sí la au to in fo rm ació n o in fo rm ació n m u tu a se d efin e co m o : La b ase d el lo garitm o d efin e la u n id ad d e in fo rm ació n . La m as u sad a es la b ase 2 y su u n id ad es el b it (co n tracció n d e “b in a ry d ig it”) U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M e d id a d e la In fo rm a c ió n : E je m p lo s Existen m u ch as razo n es p ara u sar esta b ase 2 p ara m ed ir in fo rm ació n , ya q u e el exp erim en to aleato rio m ás sim p le q u e u n o p u ed e im agin arse es aq u el co n d o s resu ltad o s igu alm en te p ro b ab les, co m o p o r ejem p lo el d e arro jar u n a m o n ed a n o d efectu o sa alaire y o b servar lo s resu ltad o s: P ca ra = P se ca = ½ Ica ra = lo g 2 1 /P ca ra = lo g 2 2 = 1 b it Ise ca = lo g 2 1 /P se ca = lo g 2 2 = 1 b it E l co n o cim ie n to d e ca d a re su lta d o tie n e a so cia d o a : 1 b it d e in fo rm a ció n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S P A = 1 /4 y P B = 3 /4 IA = lo g 2 1 /P A = lo g 2 4 = 2 b it IB = lo g 2 1 /P B = lo g 2 4 /3 = 0 ,4 1 4 b it IT O TA L = 2 + 0 ,4 1 4 = 2 ,4 1 4 b it P T O TA L = 1 /4 x 3 /4 = 3 /1 6 IT O TA L = lo g 2 1 /P T O TA L = lo g 2 1 6 /3 = 2 ,4 1 4 b it Ejem p lo : U n a fu en te d e m em o ria n u la gen era d o s sím b o lo s cu yas p ro b ab ilid ad es so n P A =1 /4 y P B =3 /4 , d eterm in ar la au to in fo rm ació n d e cad a sím b o lo y la can tid ad to tal d e in fo rm ació n d e la fu en te. M e d id a d e la In fo rm a c ió n : E je m p lo s U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Ejem p lo : Su p o n gam o s q u e u n a fu en te p ro d u ce lo s sím b o lo s A , B , C y D co n p ro b ab ilid ad es: P A = 1 /2 , P B = 1 /4 , P C = 1 /8 , P D = 1 /8 IA = lo g 2 2 = 1 b it, IB = lo g 2 4 = 2 b it, IC = lo g 2 8 = 3 b it, ID = lo g 2 8 = 3 b it Si lo s sím b o lo s so n in d ep en d ien te, calcu lar la in fo rm ació n co n ten id a en el m en saje B A C A : P B A C A = 2 + 1 + 3 + 1 = 7 b it C o m p ro b ar: f (P A .P B ) = f (P A ) + f (P B ) Ejem p lo : Si se lan za u n a m o n ed a tres veces segu id as, lo s o ch o resu ltad o s (m en sajes) eq u ip ro b ab les p o d rían ser: 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 La P M SJ =1 /8 y la IM SJ = lo g 2 (8 ) = 3 b it M e d id a d e la In fo rm a c ió n : E je m p lo s U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S M e d id a d e la In fo rm a c ió n : E je m p lo Ejem p lo : C o n sid erem o s u n a im agen d e televisió n fo rm ad a p o r u n a estru ctu ra d e p u n to s n egro s, b lan co s y grises, d isp u esto s en 5 0 0 filas y 6 0 0 co lu m n as ap ro xim ad am e n te. A d m itirem o s q u e cad a u n o d e eso s 5 0 0 X 6 0 0 = 3 0 0 .0 0 0 p u n to s p u ed e ad o p tar u n o d e 1 0 n iveles d e b rillo d iferen tes, d e m an era q u e p u ed e h ab er 1 0 3 0 0 .0 0 0 im ágen es d istin tas d e TV. Si to d as so n igu alm en te p ro b ab les, la p ro b ab ilid ad d e u n a im agen cu alq u ier es igu al a 1 / 1 0 3 0 0 .0 0 0 y la can tid ad d e in fo rm ació n q u e co n tien e: IIM G = lo g 2 1 /P IM G = 3 0 0 .0 0 0 lo g 2 1 0 = 9 9 6 .5 7 8 b it ≈ 1 0 6 b it IIM G = 1 M b it U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S ¿Q u é can tid ad d e in fo rm ació n co n tien en la o b servació n d e lo s sigu ien tes o b jeto s? � La tirad a d e u n d ad o eq u ilib rad o . � H allar la in fo rm ació n q u e se tien e cu an d o se co n o ce q u e la carta d e u n m azo d e 5 2 cartas es d e: co razo n es, u n a figu ra, u n a figu ra d e co razo n es � La elecció n d e u n a letra d e alfab eto esp añ o l (2 7 letras) � En viar la p alab ra M IG U EL M e d id a d e la In fo rm a c ió n : E je m p lo s a re s o lv e r U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía La can tid ad d e in fo rm ació n d efin id a en la ecu ació n : IA = lo g 2 1 /P A (b its) H a sid o o b ten id a p ara u n so lo m e n saje, o sea cu an ta in fo rm ació n b rin d a (d a) u n cierto even to o m en saje, p ero n o d escrib e a u n a fu e n te q u e p ro d u ce u n co n ju n to d e d iferen tes m en sajes. U n sistem a d e co m u n icació n n o esta d ise ñ ad o p ara tran sm itir u n m e n saje en p articu lar, sin o p ara tran sm itir TO D O S lo s m en sajes p o sib les p ro d u cid o s p o r la fu en te. Po r co n sigu ien te cu an d o el flu jo d e in stan tán eo d e in fo rm ació n p ro d u cid o p o r u n a fu en te es aleato rio , es m ejo r d escrib ir la in fo rm ació n d e la fu en te en térm in o s d e la “ in fo rm ació n p ro m ed io ” p ro d u cid a. U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : D e fin ic ió n Es u n p arám etro q u e n o s p erm ite d eterm in ar el co n ten id o p ro m ed io d e in fo rm ació n d e u n a fu en te o u n m en saje en p articu lar. En u n p ro ceso d e co m u n icació n , tran sm itim o s u su alm en te secu en cias largas d e sím b o lo s, y estam o s m as in teresad o s en el co n ten id o p ro m ed io d e in fo rm ació n q u e la fu en te p ro d u ce, q u e en la in fo rm ació n co n ten ida en cad a sím b o lo U n sistem a d e co m u n icació n está d iseñ ad o p ara acep tar to d o s lo s m en sajes p ro b ab les sin d istin ció n d e o cu rren cia, p o r lo tan to , la in fo rm ació n p ro m ed io q u e p ro d u ce u n a fu en te se d en o m in a EN TR O P ÍA D E LA FU EN TE U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : D e fin ic ió n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : D e fin ic ió n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : E je m p lo s U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : E je m p lo s Ejem p lo : C alcu lar la en tro p ía aso ciad a a u n d ad o , cu an d o : •El d ad o es “co rrecto ” •C u an d o el d ad o se m an ip u la d e m an era d e q u e salga u n U N O o u n SEIS es el d o b le d e la p ro b ab ilid ad d e las o tras caras. Ejem p lo : C o n sid erem o s la in fo rm ació n p ro d u cid a p o r u n a m aq u in a d e escrib ir d e 2 6 letras y el esp acio en tre letras, en o tras p alab ras, la fu en te p ro d u ce 2 7 sím b o lo s Si lo s sím b o lo s tu vieran la m ism a p ro b ab ilid ad U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S La m ayo ría d e las fu en tes d e in fo rm ació n p ro d u cen m en sajes q u e n o co n sisten en u n a ú n ica elecció n en tre p o sib ilid ad es d e igu al p ro b ab ilid ad , sin o en eleccio n es su cesivas en tre p o sib ilid ad es d e p ro b ab ilid ad variab le y d ep en d ien te . A este tip o d e secu en cias se les d en o m in a p ro ceso s esto cástico s. El caso m ás típ ico so n las letras y p alab ras q u e co n fo rm an el len gu aje. El escrib ir en esp añ o l co n stitu ye u n p ro ceso d e eleccio n es d ep en d ien tes. Po r ejem p lo , al fo rm ar u n a p alab ra se elige u n a p rim era letra d e to d as las p o sib les p rim eras letras co n d iferen tes p ro b ab ilid ad es; lu ego , se elige la segu n d a letra cu ya p ro b ab ilid ad d ep en d e d e la p rim era letra seleccio n ad a, y así su cesivam en te h asta fo rm ar la p alab ra d esead a. Lo m ism o o cu rre en el caso d e las p alab ras p ara fo rm ar o racio n es. R e d u n d a n c ia U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Lo im p o rtan te aq u í es señ alar el h ech o d e q u e, en la m ed id a q u e se avan za en la fo rm ació n d e u n a p alab ra u o ració n , el ran go d e p o sib les letras o p alab ras a ser seleccio n ad as va d ism in u yen d o y la p ro b ab ilid ad d e q u e ciertas letras o p alab ras esp ecíficas sean seleccio n ad as va au m en tan d o . D ich o d e o tra fo rm a, “ta n to la in ce rtid u m b re co m o la in fo rm a ció n d e la s ú ltim a s le tra s d e u n a p a la b ra o d e la s ú ltim a s p a la b ra s d e u n a o ra ció n e s m e n o r co m p a ra d a co n la s p rim e ra s” R e d u n d a n c ia U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S R e d u n d a n c ia 1 .- La m ayo ría d e lo s m en sajes se co n stitu yen a p artir d e u n n ú m ero lim itad o d e p o sib ilid ad es,p o r ejem p lo ,só lo 2 7 letras en elcaso d e n u estro id io m a. 2 .- La p ro b ab ilid ad d e o cu rren cia d e u n a d e estas p o sib ilid ad es d en tro d e u n m en saje d ep en d e d e las p o sib ilid ad es seleccio n ad as p reviam en te; p o r ejem p lo , la p ro b ab ilid ad d e q u e o cu rra la letra "q " lu ego d e u n a "p " es O . So n esto s d o s h ech o s lo s q u e en co n ju n to d eterm in an q u e to d o m en saje co n ten ga cierto grad o d e red u n d an cia. En o tras p alab ras, la re d u n d a n cia se re fie re a q u e la s p o sib ilid a d e s d e n tro d e u n m e n sa je se re p ite n , y se re p ite n d e u n a cie rta m a n e ra p re d e cib le.M ien tras m ayo r sea,en to n ces,la red u n d an cia d e u n m en saje,m en o r será su in certid u m b re y m en o r la in fo rm ació n q u e co n ten ga U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S R e d u n d a n c ia d e u n a F u e n te Se d ice q u e u n a fu en te es red u n d an te cu an d o p ro d u ce sím b o lo s d ep en d ien tes, es d ecir sím b o lo s ad icio n ales gen erad o s q u e n o so n n ecesario s en fo rm a ab so lu ta p ara p ro d u cir in fo rm ació n .Po r ejem p lo u n texto en in gles tien e u n a red u n d an cia d e alred ed o r d el 5 0% , e s d ecir q u e la m itad d e lo s sím b o lo s so n in n ecesario s. La red u n d an cia d e u n a fu en te p u ed e exp resarse co m o : Ejem p lo : calcu lar la red u n d an cia d e u n a fu en te b in aria q u e tien e P (0 )=1 /4 y P (1 )=3 /4 . R d = [(1 -0 .8 )/1 ]* 1 0 0 = 2 0 % . Si P (0 )=P (1 ), R d = 0 % U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E n tro p ía : C o n c e p to s � C u an d o to d o s lo s sím b o lo s so n igu alm en te p ro b ab les (d istrib u ció n d e p ro b ab ilid ad p lan a), to d o s ap o rtan in fo rm ació n relevan te y la en tro p ía es m áxim a. � La en tro p ía tam b ién se p u ed e co n sid erar co m o la can tid ad d e in fo rm ació n p ro m ed io q u e co n tien en lo s sím b o lo s u sad o s. � La en tro p ía p u ed e ser co n sid erad a co m o u n a m ed id a d e la in certid u m b re y d e la in fo rm ació n n ecesaria p ara, en cu alq u ier p ro ceso ,p o d er aco tar,red u cir o elim in ar la in certid u m b re � R ed u n d an cia es aq u ello q u e es p red ecib le o co n ven cio n al en u n m en saje,su o p u esto es la En tro p ía. � La red u n d an cia es el resu ltad o d e u n a alta p ro b ab ilid ad y la e n tro p ía d e u n a b aja p ro b ab ilid ad � U n m en saje co n b aja p red ecib ilid ad es en tró p ico y tien e alto co n ten id o in fo rm ático � U n m en saje co n alta p red ecib ilid ad es red u n d an te y tien e b ajo co n ten id o in fo rm ático U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S T a s a d e In fo rm a c ió n Su p o n gam o s q u e d o s fu en tes tien en la m ism a en tro p ía, p e ro u n a es m as ráp id a q u e la o tra, es d ecir p ro d u ce m as sím b o lo s p o r u n id ad d e tiem p o . En u n p erio d o d ad o , m as in fo rm ació n será tran sferid a d e la fu en te m as ráp id a lo cual co lo ca n ecesid ad es m ayo res so b re el sistem a d e co m u n icació n . Po r lo tan to la d escrip ció n d e u n a fu en te n o so lo es su en tro p ía (b it/sím b o lo s), sin o tam b ién (o m as b ien ..) su TA S A D E IN F O R M A C IO N m ed ia en b its/segu n d o (b p s). La tasa d e In fo rm ació n d e u n a fu en te d iscreta se d efin e co m o : �= �� ���/ D o n d e � es la d u ració n p ro m ed io d el sím b o lo : �= � � � �� � Po r lo tan to �� es igu al al n u m ero p ro m ed io d e sím b o lo s p o r u n id ad d e tiem p o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S T a s a d e In fo rm a c ió n : E je m p lo C alcu lar la tasa d e in fo rm ació n d e u n a fu en te telegráfica ten ien d o : ������ = 23 ,����� = 13 � ������ = 0,2 ! ,����� = 0,4 ! � = 23 #$! 32 + 13 #$!3= 0,920 [ ��� �(�$#$ ] �= *+ ∗0,2+ �+ ∗0,4= 0,267 [ !/ �(�$#$ ] �= �� = 0,920 0,267 = 3,44���/ U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S T a s a d e In fo rm a c ió n : En to n ces d efin íam o s la tasa d e In fo rm ació n d e u n a fu en te d iscreta co m o : R= Hσ bit/s D o n d e � es la d u ració n p ro m ed io d el sím b o lo : σ= � P7 87�� σ7 A h o ra si su p o n em o s q u e to d o s lo s sím b o lo s tien en la m ism a d u ració n �= 9 O sea: := �� = �;< (símbolos/segundo) En to n ces la tasa d e in fo rm ació n será: �= �� = �9 = :∗� = :∗� � H �� #$! 1� (�I ) Y si lo s sím b o lo s so n eq u ip ro b ab les: �= :∗� = :∗#$! 1� = 1/9 ∗#$!J U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S T a s a d e In fo rm a c ió n : E je m p lo U n a fu en te p ro d u ce cu atro sím b o lo s A , B , C y D cu yas p ro b ab ilid ad es so n : �K = 0,5, �M = 0,25 �N = 0,125, �O = 0,125 La En tro p ía d e la fu en te será: � = 0,5 #$ ! 2 + 0 ,2 5 #$ ! 4 + 0 ,1 2 5 #$ ! 8 + 0 ,1 2 5 #$ ! 8 = 1 ,7 5 � ��/ �( � $ #$ Si lo s sím b o lo s fu eran eq u ip ro b ab les, o sea P i =1 /4 , en to n ces: � = #$ ! 4 = 2 ���/ �(�$#$ A h o ra lo s sím b o lo s se p ro d u cen a u n a velo cid ad d e r=1 0 0 0 sím b o lo s/seg, en to n ces la tasa d e in fo rm ació n R será: � Si lo s sím b o lo s tien en d iferen tes p ro b ab ilid ad es: �= :∗� = 1000 �(�$#$ ! ∗1,75 ��� �(�$#$ = 1750 �I � Si lo s sím b o lo s so n eq u ip ro b ab les: �= :∗� = 1000 �(�$#$ ! ∗2 ��� �(�$#$ = 2000 �I O sea la velo cid ad R es m áxim a cu an d o lo s sím b o lo s so n eq u ip ro b ab les C O N C LU S IO N ? ? ? U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o d ific a c ió n d e lo s M e n s a je s La F u e n te d iscre ta gen era, aleato riam en te, m en sajes d igitales arb itrariam en te largo s, es d ecir, secu en cias arb itrariam en te largas d e sím b o lo s d e u n cierto alfab eto (alfab eto d e la fu en te). Es u n d isp o sitivo q u e em ite co n regu larid ad y d e fo rm a aleato ria sím b o lo s p erten ecien tes a u n cierto co n ju n to d iscreto y fin ito llam ad o alfab eto d e la fu en te. U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o d ific a c ió n d e lo s M e n s a je s El C o d ifica d o r tran sfo rm a lo s m en sajes gen e rad o s p o r la fu en te; es d ecir, co n vierte u n a secu en cia d e sím b o lo s d ad a en o tra d istin ta (en gen eral,co n sím b o lo s d e u n alfab eto tam b ién d istin to d elalfab eto d e la fu en te, q u e se d en o m in a alfab eto d e co d ificació n , y q u e h ab rá d e ser n ecesariam en te igu al q u e el alfab eto d e en trad a d el can al). Esta tran sfo rm ació n , cu yo o b jetivo es la tran sm isió n fiel y eficien te d e lo s m en sajes d e la fu en te d ad a, u tilizan d o el can al d ad o , d eb erá h acerse ten ien d o en cu en ta tan to las características estad ísticas d e lo s m en sajes d e la fu en te (es d ecir, d e la fu en te) co m o las d el ru id o q u e se p ro d u ce en elcan al. U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o d ific a c ió n d e lo s M e n s a je s El C a n a l d iscre to ru id o so realiza, aleato riam en te, u n a tran sfo rm ació n in d eseab le so b re lo s m en sajes q u e lo atraviesan , d e fo rm a q u e el m en saje q u e recib e eld eco d ificad o r n o es,en gen eral,elm ism o q u e h a gen erad o elco d ificad o r El D e co d ifica d o r tien e q u e ad ivin ar q u é m en saje d e la fu en te co rresp o n d e al m en saje recib id o , co n o cid as las reglas d e tran sfo rm ació n q u e ap lica el co d ificad o r U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S A h o ra b ien , en la p ráctica, resu lta co n ven ien te aislar elefecto q u e tien e la fu en te en elsistem a d elefecto q u e tien e elcan al,d esco m p o n ien d o el co d ificad o r/d eco d ificad o r. � U n C o d ifica d o r d e F u e n te , cu ya co n stru cció n h a d e ad ap tarse a las características d e la fu en te d e fo rm a q u e co n siga rep resen tar lo s m en sajes d e la fu en te co n el m en o r n ú m ero p o sib le d e sím b o lo s d e u n cierto alfab eto d e co d ificació n (típ icam en te lo s sím b o lo s q u e se p u ed en tran sm itir p o r elcan ald ad o ) � U n C o d ifica d o r d e C a n a l, cu ya co n stru cció n h a d e ad ap tarse a las características d elcan ald e fo rm a q u e p erm ita la co n secu ció n d e u n a tran sm isió n fiab le so b re u n can alru id o so co n u n co ste m ín im o . C o d ific a c ió n d e la F u e n te U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S La d esco m p o sició n d el p ro ceso d e co d ificació n en d o s su b p ro ceso s in d ep en d ien tes, co d ificació n d e fu en te y co d ificació n d e can al, facilita el an álisis d el siste m a, p o r u n a p arte; y, p o r o tra p arte, p ro p o rcio n a u n a gran flexib ilid ad en la im p lem en tació n , p o rq u e h ace virtu alm en te in d ep en d ien tes lo s d iseñ o s d elco d ificad o r d e can aly d elco d ificad o r d e fu en te C o d ific a c ió n d e la F u e n te U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U n co d ificad o r ó p tim o es aq u el q u e u tiliza el m ín im o n ú m ero d e b its p ara co d ificar u n m en saje d e la fu en te.U n co d ificad o r ó p tim o u sará: � C ó d igo s co rto s p ara co d ificar m en sajesfrecu en tes � C ó d igo s d e m ayo r lo n gitu d p ara aq u ello s m en sajes q u e se an m e n o s frecu en tes. D e esta fo rm a se o p tim iza el ren d im ien to d el can al o zo n a d e alm acen am ien to y el sistem a es eficien te en térm in o s d el n ú m ero d e b its p ara rep resen tar lo s m en sajes. Po r ejem p lo , el có d igo M o rse se ap ro vech a d e este p rin cip io p ara o p tim izar eln ú m ero d e caracteres a tran sm itir a p artir d elestu d io d e las letras m ás frecu en tes d elalfab eto in glés. “E l có d ig o M o rse n o e s u n co d ifica d o r ó p tim o p e ro sí a sig n a a la s le tra s m á s fre cu e n te có d ig o m á s co rto s, ju sta m e n te p a ra o p tim iza r su e ficie n cia ” U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S LA EN TR O P ÍA D E U N A V A R IA B LE A LEA TO R IA ES EL N Ú M ER O M ED IO D E B ITS Q U E SE N EC ESITA R Á N PA R A C O D IFIC A R C /U D E LO S ESTA D O S D E LA V A R IA B LE: SI SE Q U IER E R EP R ESEN TA R (C O D IFIC A R ) LO S D IEZ D ÍG ITO S D EC IM A LES U SA N D O SEC U EN C IA S D E B ITS: � C O N 3 D IG ITO S B IN A R IO S N O ES SU FIC IEN TE, SE N EC ESITA M Á S. � SI SE U SA N 4 D IG ITO S B IN A R IO S TA L V EZ SEA D EM A SIA D O . � LA EN TR O P ÍA D E 1 0 SU C ESO S EQ U IP R O B A B LES ES: � EL V A LO R C A LC U LA D O ES EL LÍM ITE TEÓ R IC O , Q U E N O R M A LM EN TE N O SE P U ED E A LC A N ZA R . � SE P U ED E D EC IR Q U E N O EX ISTE N IN G U N A C O D IFIC A C IÓ N Q U E EM P LEE LO N G ITU D ES P R O M ED IO D E M EN SA JE IN FER IO R ES A L N Ú M ER O C A LC U LA D O . E n tro p ía : E je m p lo s � = � 110 �QR�� #$!* 10= #$!* 10= 3,32 ��� S ⁄�!��$ U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Po d em o s co n stru ir u n co d ificad o r ó p tim o b asán d o n o s en la en tro p ía d e u n a variab le aleato ria d e in fo rm ació n x. En efecto , la e n tro p ía n o s d a el n ú m ero m ed io d e b its n ecesario s p ara co d ificar el m en saje a través d e u n co d ificad o r ó p tim o y p o r tan to n o s d eterm in a el lím ite m áxim o alq u e se p u ed e co m p rim ir u n m en saje u san d o u n e n fo q u e sím b o lo a sím b o lo sin n in gu n a p érd id a d e in fo rm ació n (d e m o strad o an alíticam en te p o r Sh an n o n ), el lím ite d e co m p resió n (en b its) es igu al a la en tro p ía m u ltip licad a p o r el largo d el m en saje.R eescrib ien d o la ecu ació n d e cálcu lo d e la en tro p ía p o d em o s d ecir: C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o � = � I(U ) V #$! 1I(U ) p o r tan to la in fo rm ació n q u e ap o rta u n d eterm in ad o sím b o lo x i , W(UR )= log* �X(VY ) = -log* �(UR ) Esta exp resió n rep resen ta el n ú m ero n ecesario d e b its p ara co d ificar el m en saje x i en el co d ificad o r ó p tim o y p o r tan to la en tro p ía tam b ién se p u ed e co n sid erar co m o u n a m ed id a d e la in fo rm ació n p ro m ed io co n ten id a en cad a sím b o lo d el m en saje. U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o Su p o n gam o s q u e el n ú m ero d e estad o s d e u n m en saje es igu al a 3 [M 1 , M 2 y M 3 ], d o n d e la p ro b ab ilid ad d e M 1 es 5 0 % , la d e M 2 2 5 % y la d e M 3 2 5 % . Po r ejem p lo p o d ríam o s co d ificar M 1 co n " 0 ", M 2 co n "1 0 " y M 2 co n "1 1 ". U san d o este co n ven io p ara co d ificar el m en saje M 1 M 2 M 1 M 1 M 3 M 1 M 2 M 3 u saríam o s " 0 1 0 0 0 1 1 0 1 0 1 1 " y p o r tan to 1 2 b its. La lo n gitu d p ro m ed io d el có d igo seria: W Z � = log* 1 � Z � =log* 2= 1��� WZ * = log* 1 � Z * =log* 4= 2��� W Z + = log* 1 � Z + =log* 4= 2��� � = 0,5#$!2+ 0,25#$!4+ 0,25#$!4= 1,5 ��� ⁄�(�$#$ Po r tan to el co d ificad o r ó p tim o n ecesita d e m ed ia 1 ,5 b its p ara co d ificar cu alq u ier valo r d e X . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o Su p o n gam o s q u e el n ú m ero d e estad o s d e u n m en saje es igu al a 3 [M 1 , M 2 y M 3 ], d o n d e la p ro b ab ilid ad d e M 1 es 5 0 % , la d e M 2 2 5 % y la d e M 3 2 5 % . Po r ejem p lo p o d ríam o s co d ificar M 1 co n " 0 ", M 2 co n "1 0 " y M 2 co n "1 1 ". U san d o este co n ven io p ara co d ificar el m en saje M 1 M 2 M 1 M 1 M 3 M 1 M 2 M 3 u saríam o s " 0 1 0 0 0 1 1 0 1 0 1 1 " y p o r tan to 1 2 b its. La lo n gitu d p ro m ed io d el có d igo seria: W Z � = log* 1 � Z � =log* 2= 1��� WZ * = log* 1 � Z * =log* 4= 2��� W Z + = log* 1 � Z + =log* 4= 2��� � = 0,5#$!2+ 0,25#$!4+ 0,25#$!4= 1,5 ��� ⁄�(�$#$ Po r tan to el co d ificad o r ó p tim o n ecesita d e m ed ia 1 ,5 b its p ara co d ificar cu alq u ier valo r d e X . [ \$S�!$ = 0,5∗1+ 0,25∗2+ 0,25∗2= 1,5 ��� U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S C o n c e p to s d e c ó d ig o s : E l c o d ific a d o r o p tim o U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E l A lg o ritm o d e H u ffm a n Su p o n gam o s q u e se d isp o n e d e u n a fu en te co n tin u a q u e d iscretizam o s em p lean d o u n cu an tificad o r u n ifo rm e co n 8 n iveles. A co n tin u ació n co d ificam o s su s salid as, asign án d o le a cad a m u estra d e en trad a u n sím b o lo co m p u esto p o r tres b its. Las p ro b ab ilid ad es d e cad a u n o d e esto s sím b o los so n :P (0 0 0 ) =0 .2 ,P (0 0 1 ) =0 .0 1 ,P (0 1 0 ) =0 .4 ,P (0 1 1 ) =0 .0 4 , P (1 0 0 ) =0 .1 , P (1 0 1 ) =0 .0 2 , P (1 1 0 ) =0 .0 7 y P (1 1 1 ) =0 .1 6 . En co n secu en cia,la en tro p ía d e esta fu en te es q u e es sign ificativam en te in ferio r a lo s 3 b its p o r m u estra q u e estam o s em p lean d o si to m am o s d irectam en te la salid a d el co d ificad o r. La co d ificació n d e H u ffm an le va asign ar a cad a cad en a d e 3 b its u n a cad en a d e lo n gitu d variab le q u e m in im ice el n ú m ero d e b its m ed io p o r sím b o lo . U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S E l A lg o ritm o d e H u ffm a n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S U n a vez q u e el árb o l está co m p letam en te co n stru id o (es d ecir, en el m o m en to en q u e to d o s lo s sím b o lo s se h an ju n tad o en u n o so lo co n p ro b ab ilid ad 1 ), se reco rre el árb o l d e d erech a a izq u ierd a (p arte h acia atrás d el algo ritm o ), aso cian d o co n cad a b ifu rcació n (esto es, d o n d e se h an su m ad o 2 p ro b ab ilid ad es) u n 0 y u n 1 en cad a u n a d e su s ram as (se p u ed e h acer d e m an era arb itraria). E l A lg o ritm o d e H u ffm a n U N ID A D 4 T e o ría d e la In fo rm a c ió n y C o d ific a c ió n U T N -F R T – IS I - C O M U N IC A C IO N E S Po r ú ltim o , se leen lo s b its d e d erech a a izq u ierd a h asta llegar al sím b o lo o rigin al, y d ich a cad en a d e b its es la q u e se le asign a a cad a sím b o lo d e en trad a La calid ad d e u n có d igo d e fu en te se p u ed e m ed ir E l A lg o ritm o d e H u ffm a n
Compartir