Introducción a la Teoría de la Información Contenido 1. − Introducción 2. − Fuentes de información 2.1. − Tipos 2.2. − Fuentes digitales 3. − Entropía de fuentes sin memoria 3.1. − Concepto intuitivo de información 3.2. − Información de un símbolo 3.3. − Información de una fuente: entropía 3.4. − Fuentes extendidas: agrupación de símbolos 4. − Entropía de fuentes con memoria 4.1. − Interpretación de la simulación de una fuente con memoria 5. − Codificación y compresión de datos 5.1. − Primer Teorema de Shannon 5.2. − Justificación del Primer Teorema de Shannon 6. − Simulación de una fuente con memoria 6.1. − Código y comentarios 1. − Introducción Hay gente que habla por los codos, pero dicen muy poco. En cambio hay otros que todo lo que dicen es útil. Estos son los dos casos de datos con redundancia y datos sin redundancia. Aunque el primer caso puede ser deseable en alguna circunstancia (actos sociales...), no lo es en la mayoría. La transmisión de datos no es tan rápida como quisiéramos, los dispositivos de almacenamiento no tienen capacidad ilimitada, las cantidades muy grandes de datos son poco manejables... los que menos deseamos es que la mitad de los datos que recibimos, encima, no sirvan para nada. Sería interesante reducir la cantidad de datos, pero sin perder información. La Teoría de la Información nos muestra, entre otras cosas, el camino a seguir para determinar la cantidad de 1 información útil de unos datos y para comprimir la información de manera que los datos se representen de una manera eficiente. La Teoría de la Información se desarrolla en términos de probabilidades, ya que la información tiene una naturaleza aleatoria (si supiésemos de antemano la información, ¿para qué la querríamos?). Por supuesto, en la realidad no disponemos a priori de las probabilidades necesarias, por lo que habrá que estimarlas de los datos existentes. En este trabajo supondremos conocidas las características estadísticas de nuestros datos. No vamos a tratar en este trabajo de lo que probablemente sean los resultados más interesantes (o por lo menos, más sorprendentes) de la Teoría de la información, ya que se necesitan algunos conocimientos de transmisión digital de datos. Estos resultados establecen la capacidad máxima de transmisión fiable de datos de un canal, entre otras cosas. 2. − Fuentes de información Una fuente de información es un elemento que entrega información, como pueden ser una persona hablando, un ordenador entregando datos... La visión de la persona hablando (por ejemplo), nos puede servir para ver los elementos más importantes en la emisión de la información. La información viaja sobre la voz de la persona (como una onda de presión). La voz es lo que llamamos señal, que es el soporte de la información. Pero es el hombre quien emite la voz, y es el hombre la verdadera fuente de información. Esto se puede formalizar con unas definiciones más rigurosas. Una fuente de información es un elemento que entrega una señal, y una señal es una función de una o más variables que contiene información acerca de la naturaleza o comportamiento de algún fenómeno. Es decir, vamos a considerar señal tanto al fenómeno físico que transporta la información como a la función matemática que representa a ese fenómeno. Cualquiera de las dos formas sirve como soporte a la información. En esta discusión, consideraremos únicamente señales unidimensionales, es decir, aquellas que dependen únicamente de una variable. Además a esta variable la llamaremos tiempo, aunque no represente necesariamente el tiempo. Las fuentes de información se clasifican basándose en el tipo de señal que entregan. Se pueden clasificar, según el tipo de variable independiente (tiempo) en: • Fuentes de tiempo continuo: la función está definida para cualquier valor de la variable independiente. • Fuentes de tiempo discreto: la función sólo está definida para un conjunto contable de instantes de tiempo. Pero se pueden clasificar también según el rango de valores que cubren las señales. En este caso los tipos de fuentes de información serán: • Fuentes continuas o de amplitud continua: el valor de la función toma un rango continuo de valores. • Fuentes discretas o de amplitud discreta: el valor de la función sólo toma un conjunto finito de valores. A cada uno de estos valores lo llamamos símbolo. El conjunto de todos los símbolos se suele llamar alfabeto. La elección del alfabeto es, en cierto modo, arbitraria, ya que podemos varios símbolos para crear otros, por ejemplo. Estas dos clasificaciones son ortogonales, es decir, existen fuentes continuas de tiempo continuo, fuentes continuas de tiempo discreto, fuentes discretas de tiempo continuo y fuentes discretas de tiempo discreto. Aunque en la práctica sólo se encuentran dos tipos: las llamadas fuentes analógicas, que son fuentes continuas 2 de tiempo continuo; y las llamadas fuentes digitales, que son fuentes discretas de tiempo discreto. Las fuentes digitales se suelen clasificar según la relación que tenga un símbolo con los que le preceden de la siguiente manera: • Fuentes sin memoria: los símbolos son estadísticamente independientes entre sí. De esta manera, los símbolos que hayan aparecido hasta el momento no van a condicionar al símbolo presente ni a posteriores. • Fuentes con memoria: la aparición de los símbolos no es estadísticamente independiente. Es decir, si han aparecido M−1 símbolos, el símbolo M−ésimo está condicionado por los anteriores. 3. − Entropía de fuentes sin memoria Vamos a analizar en este apartado las fuentes sin memoria, es decir, aquellas en que los símbolos son estadísticamente independientes. Esto se puede expresar matemáticamente como: siendo si y sj dos símbolos cualquiera de la fuente. 3.1. − Concepto intuitivo de información Tenemos una fuente sin memoria que entrega símbolos de entre un alfabeto S = {s0, s1, ... sK−1} con probabilidades de aparición p0, p1, ... pK−1 para cada símbolo, respectivamente. Por supuesto se cumple que . En un momento dado la fuente entrega símbolo si. Si la probabilidad de este símbolo es pi = 1, es decir, sabemos de antemano qué símbolo va a entregar, la fuente no está entregando información ya que todo es conocido. En cambio, cuando la fuente entrega un símbolo que no esperábamos para nada (es decir, la probabilidad de aparición de ese símbolo es pequeña) la información que aporta es grande. En realidad, el proceso de aparición de un símbolo puede describir mediante los siguientes pasos: • Antes de la aparición del símbolo: estado de incertidumbre, desconocimiento del símbolo que aparecerá. • En la aparición del símbolo: sorpresa, debida a la aparición de un símbolo no esperado. • Tras la aparición del símbolo: aumento en la información que tenemos ya que no tenemos la incertidumbre anterior. Podemos ver, por tanto, que el concepto de información está estrechamente ligado con las ideas de incertidumbre y sorpresa. 3.2. − Información de un símbolo Como hemos visto, a mayor sorpresa (probabilidad de aparición de un símbolo menor) mayor es la información que aporta ese símbolo. De esta manera se define la información que aporta un símbolo en función de su probabilidad de aparición como: 3 Aunque la base del logaritmo se puede tomar arbitrariamente, se suele tomar base 2. De este modo, la información de un símbolo se mide en bits. La información de un símbolo tiene las siguientes propiedades: • • • • , ya que la probabilidad siempre está comprendida entre 0 y 1. Esta propiedad nos dice que un símbolo podrá aportar mucha, poca o ninguna información, pero nunca supondrá una pérdida de información. . Como habíamos visto antes, si sabemos de antemano que símbolo va a aparecer, éste no aporta ninguna información nueva. , es decir, a mayor sorpresa, mayor información. . Esto quiere decir que la información aportada por un símbolo que es la concatenación de otros dos es la suma de las informaciones de ambos símbolos. 3.3. − Información de una fuente: entropía Si consideramos que un símbolo si tiene una probabilidad de aparición muy pequeña, estamos afirmando que la información que aporta es muy grande, pero debido a que su aparición es muy esporádica, la información que aporta la fuente con el conjunto de todos los símbolos no es tan grande. De hecho, veremos que la información de una fuente está acotada. Por ahora nos conformaremos con ver que la información que aporta un símbolo en media está acotado, ya que depende de su frecuencia de aparición. A continuación se ve representada la función cuando la probabilidad varía de 0 a 1. Concretamente, la función tiene un máximo en p(s) = e−1. La información que entregue la fuente será el valor medio de las informaciones que entregue cada símbolo individualmente cada vez que aparezcan. Este parámetro se llama Entropía de la fuente, y se puede expresar como: donde E{·} es la esperanza matemática. Como podemos ver la entropía es una suma de un número finito de términos como el analizado anteriormente, por lo que también va a estar acotada. La entropía de una fuente tiene las siguientes propiedades: 4 • • • , es decir, que la entropía de una fuente no es negativa y está acotada superiormente. Esto quiere decir que la fuente no puede suponer una pérdida de información, así como tampoco puede entregar una cantidad de información ilimitada (para un número de símbolos limitado). para algún i. En este caso el resto de las probabilidades serán nulas. No habrá sorpresa y por tanto la entropía será nula. . Cuando todos los símbolos sean equiprobables, la incertidumbre sobre lo que va a ocurrir será máxima, y por tanto nos encontraremos en el límite superior de la entropía. • Se mide en bits/símbolo. Para comparar la entropía de fuentes con diferente número de símbolos, podemos definir una entropía normalizada como de manera que . Es como si estuviésemos normalizando en número de símbolos a 2 (número mínimos de símbolos). 3.4. − Fuentes extendidas: agrupación de símbolos Dada una fuente que entrega símbolos pertenecientes a un alfabeto S = {s0, s1, ... sK−1} con probabilidades de aparición p0, p1, ... pk−1 para cada símbolo respectivamente, podemos reagrupar los símbolos para formar otro alfabeto en que cada símbolo es la concatenación de M símbolos. Por tanto este nuevo alfabeto S' tiene KM símbolos. Un símbolo cualquiera sisj...sl tendrá una probabilidad de aparición pi·pj·...·pl. La entropía para este nuevo alfabeto está relacionada con el anterior mediante: Debido a que el alfabeto se elige arbitrariamente, debe cumplirse que la entropía de la fuente sea igual para un alfabeto cualquiera. Para hacer esta comparación hacemos uso de la entropía normalizada: Aquí vemos claramente que la entropía normalizada depende de la fuente, y no del alfabeto elegido. Por lo tanto en la representación de la entropía normalizada podemos prescindir de S (el alfabeto) como parámetro, y escribir para una fuente concreta. 5 4. − Información y Entropía de fuentes con memoria El estudio de las fuentes con memoria es algo más complejo que el de las fuentes sin memoria, por lo que no vamos a entrar en detalles. Contrastaremos los resultados teóricos con los resultados de una simulación. En una fuente con memoria los símbolos no son estadísticamente independientes, es decir, . Se puede ver que se va a producir una reducción de la información entregada por la fuente, ya que una vez que han aparecido M−1 símbolos, el símbolo M−ésimo va a depender de los anteriores, por lo que contendrá menor información que si fuese independiente. Supongamos que tenemos dos fuentes con el mismo alfabeto y la misma probabilidad de aparición de cada símbolo. HM(S)sin memoria y HM(S)con memoria son las entropías de la fuente sin memoria y con memoria con agrupaciones de M símbolos respectivamente. En la fuente con memoria hay una reducción de la entropía respecto de la fuente con memoria, de tal manera que se cumple que: HM(S)sin memoria > HM(S)con memoria La entropía (normalizada) de la fuente con memoria se puede definir como: Como vemos, la entropía normalizada de una fuente con memoria no es independiente del alfabeto elegido. De hecho, agrupaciones grandes de símbolos siempre proporcionan una entropía menor que agrupaciones menores. El valor más pequeño (cuando las agrupaciones son de símbolos) es la entropía de la fuente con memoria. 4.1. − Interpretación de la simulación de una fuente con memoria En este ejemplo vamos a simular una fuente con memoria que entrega dos símbolos que llamaremos {0, 1} (fuente binaria) y cada símbolo está condicionado sólo por el anterior. Podemos caracterizar la fuente, en función de las probabilidades condicionadas: Podemos calcular la entropía normalizada de esta fuente con memoria de la siguiente manera. Las siguientes expresiones se pueden aplicar a una fuente con un número cualquiera de símbolos, en que cada símbolo sólo dependa del anterior: La segunda ecuación nos da la entropía de la fuente conociendo el símbolo que acaba de entregar. De esta manera, para cada símbolo, se tiene en cuenta la dependencia con el símbolo anterior. Así la formula comprende el efecto de la reducción de información debido a la memoria. 6 La entropía total de la fuente será el valor medio de las entropías condicionadas, como se muestra en la primera ecuación. Aplicando estas ecuaciones para nuestro caso, obtenemos el siguiente resultado: En la simulación de la fuente hemos estimado los siguientes parámetros finales: siendo la entropía normalizada para agrupaciones de M símbolos. El resultado más importante es que las entropías son decrecientes con M, y tienden asintóticamente a , resultado que habíamos visto en teoría. 5. − Codificación y compresión de datos Como ya hemos comentado en la introducción, sería interesante reducir el volumen de datos a manejar, siempre que se pueda. ¿Estamos a favor de comprimir? Sí, siempre que no se pierda información, claro. O dicho de otra forma, debe poderse recuperar los datos originales a partir de los datos comprimidos. Para poder manejar apropiadamente los símbolos (y por tanto los datos) debemos representarlos mediante un alfabeto binario, típicamente Sb = {0, 1}. Los símbolos de este alfabeto Sb binario los llamamos bits. Además, será conveniente poder convertir de nuevo la representación binaria en símbolos. El proceso de asociar a cada símbolo otros símbolos del alfabeto binario se llama codificación. Dado el alfabeto S = {s0, s1, ... sK−1} que entrega una fuente sin memoria, la codificación se puede representar como una aplicación C: S ! Sb de tal manera que exista la función inversa C−1: S ! Sb . Hay que tener en cuenta que el número de bits para codificar los símbolos tiene que ser suficiente para poder recuperar los datos originales, y que no es necesario asignar un número fijo de bits a cada símbolo. Pero ¿hay alguna manera especialmente buena de codificar? Si pensamos en asociar muy pocos bits a los símbolos que aparecen mucho (a los que tienen una alta probabilidad de aparición) y más bits a los símbolos que parecen rara vez (probabilidad de aparición baja), conseguiremos una codificación eficiente. Esto es lo que se llama un código de longitud variable. La longitud media por símbolo de este código es el número medio de bits por símbolo, y se puede expresar como: 7 donde pi es la probabilidad de aparición del símbolo si y li es el número de bits asociados a ese símbolo. Nuestro propósito es que sea lo menor posible, de manera que la información esté comprimida al máximo. ¿Pero cuánto se puede comprimir? 5.1. − Primer teorema de Shannon Es evidente que la longitud media del código tendrá un límite inferior mayor que cero, ya que los datos no se pueden comprimir infinitamente. Tendremos por tanto que . ¿Pero cuál es ese límite por debajo de cual ya no se puede comprimir la información? El Primer Teorema de Shannon nos da la respuesta a esta pregunta, y se puede enunciar así: Dada una fuente digital sin memoria con entropía , la longitud media del código para cualquier código sin pérdidas está acotado inferiormente por . Un código será tanto mejor cuanto más se aproxime su longitud media a la entropía de la fuente. Para medir esto podemos calcular la eficiencia de un código que se define como: donde es la eficiencia de la codificación. De esta manera sabemos si la codificación ha sido eficiente o por el contrario sigue habiendo redundancia y podríamos haber diseñado mejor nuestro codificador. 5.2. − Justificación del Primer Teorema de Shannon Supongamos que tenemos una fuente de información sin memoria que entrega símbolos del alfabeto S = {A, B, C, D} con una probabilidad de aparición: P(A) = 0.5 P(B) = 0.25 P(C) = 0.125 P(D) = 0.125 La información contenida en cada símbolo, medida en bits por símbolo, será: I(A) = 1 I(B) = 2 I(C) = 3 I(D) = 3 Como ya comentamos anteriormente, tienen mayor información los símbolos menos probables. Si además tenemos que asociar más bits del alfabeto binario Sb a los símbolos menos probables y menos a los más probables por razones de eficiencia, ¿por qué no asociar a cada símbolo un número de bits igual a la información por símbolo que contienen? Si hacemos esto, la eficiencia del código es máxima, es decir, la longitud media del código coincidirá con la entropía de la fuente: 8 Esta resultado es el deseable para todos los casos, pero hay factores que impiden que esto se logre fácilmente, como en este caso. Por ejemplo, en el caso de que la información contenida en cada símbolo sea un número no entero. Quizá en este caso debiéramos utilizar agrupaciones de símbolos. Un problema que se plantea al utilizar códigos de longitud variable es cómo distinguir unos símbolos de otros. O mejor planteado el problema: cómo asignar los bits a los símbolos para que la secuencia se pueda decodificar unívocamente. Una condición suficiente (pero no necesaria) para lograr esto es conseguir que ningún símbolo sea prefijo de otro símbolo. Vamos a ver esto con el ejemplo que hemos presentado antes. Las secuencias de bits que asociamos a los símbolos son: A = 0 B = 10 C = 110 D = 111 Vemos que ningún símbolo empieza por la secuencia de A (`0'), ni por la secuencia de B (`10'), y por obviamente ni por la secuencia de C ni la de D. Esta condición nos garantiza que la secuencia `0110010101100011101111000110010...' puede ser decodificada unívocamente. Para un número reducido de símbolos, este proceso puede hacerse manualmente. Pero si el número de símbolos crece, es conveniente tener un algoritmo. El algoritmo debe constar de dos parte, un `compresor' que aplique la codificación y un `descompresor' que decodifique la secuencia recuperando los datos originales. 6. − Simulación de una fuente con memoria En esta simulación hemos tratado de reproducir el comportamiento de una fuente con memoria con las siguientes características: • La fuente es binaria, es decir, sólo entrega dos símbolos. • Cada símbolo depende solamente del anterior con una probabilidad dada. Los símbolos entregados por la fuente serán {0, 1}, y las probabilidades condicionadas serán las siguientes: Con estos datos sobre la probabilidad, es posible hallar el resto de los datos de la siguiente manera: Podemos representar esta fuente mediante un diagrama de estados: 9 Mediante un código generamos una secuencia de longitud N con las propiedades estadísticas deseadas. El tamaño de la secuencia lo elegiremos adecuadamente más tarde. Una vez generada la secuencia estimamos la probabilidad de aparición de los símbolos del alfabeto extendido compuestos por la agrupación de uno, dos, tres y cuatro símbolos. Esta estimación se realiza simplemente contando el número de veces que aparece cada símbolo. Hay que tener en cuenta que aunque la secuencia se genere a partir de unos parámetros estadísticos bien conocidos, estamos haciendo una estimación a partir de un número finito de muestras, por lo que los parámetros estimados no coinciden con los teóricos, aunque sí se aproximan. Para aumentar la precisión en la estimación de las probabilidades podemos, bien generar una secuencia más larga, o bien realizar la simulación varias veces y hallar la media de los estimadores. En nuestro caso hemos generado una secuencia lo suficientemente larga para que el número de símbolos en el caso peor (agrupación de cuatro símbolos iniciales) sea representativo. Además debemos tener en cuenta que la secuencia debe tener una longitud tal que haya un número entero de símbolos. En nuestro caso, para que esto se cumpla, basta con que el número de elementos de la secuencia sea múltiplo de 12, es decir, . El tamaño de la secuencia que hemos elegido es 120.000 elementos, con lo que en el caso pero se dispone de 30.000 símbolos para estimar las probabilidades. Aunque aumentar el tamaño de las agrupaciones de símbolos no sólo afecta al número de símbolos disponibles, sino que, como el número de símbolos existentes es mucho mayor, el número de símbolos para determinar cada probabilidad es menor. Estos dos efectos afectan perjudicialmente en la precisión de la estimación. Los resultados obtenidos mediante la simulación se pueden obtener analíticamente a partir de los parámetros estadísticos ideales de la secuencia. Vamos a comparar los resultados analíticos con los resultados estimados: Tabla 1: Agrupación de un símbolo Teoría Simulación P(0) 0.900 0.897 P(1) 0.100 0.103 Tabla 2: Agrupación de dos símbolos Teoría Simulación P(00) 0.855 0.853 P(01) 0.045 0.044 P(10) 0.045 0.045 P(11) 0.055 0.058 Tabla 3: Agrupación de tres símbolos 10 Teoría Simulación P(000) 0.8123 0.8094 P(001) 0.0428 0.0430 P(010) 0.0248 0.0197 P(011) 0.0248 0.0261 P(100) 0.0428 0.0430 P(101) 0.0023 0.0024 P(110) 0.0303 0.0242 P(111) 0.0303 0.0323 Hemos podido comparar en este caso los resultados teóricos con los reales. ¿Dónde está entonces el sentido de la simulación? Con esta simulación pretendemos mostrar el camino a seguir para estimar experimentalmente a entropía de una fuente, bien para fuentes sencillas como esta o para fuentes más complicadas. En muchos casos, una solución analítica es impracticable. 6.1. − Código y comentarios El código, escrito en MATLAB, es muy sencillo e intuitivo. Aunque se podría haber escrito de forma más compacta, hemos preferido la claridad a la eficiencia. Hay que tener en cuenta que MATLAB es un lenguaje interpretado y no compilado, por lo que su ejecución es lenta. Para conseguir un código eficiente, habría que programarlo en un lenguaje compilado (por ejemplo C) y utilizar las funciones y métodos apropiados. Para nuestra simulación hemos utilizado una función que nos genera la secuencia y un código que la analiza. Estos códigos son los siguientes: Función que genera la secuencia: function z=secuencia(N); %Sintaxis: z=secuencia(N) % % N: Número de puntos de la secuencia % z=[]; if rand<0.9, z=0; else z=1; end; for k=2:N, if z(k−1)==0, if rand<0.95, z=[z 0]; else 11 z=[z 1]; end; else if rand<0.45 z=[z 0]; else z=[z 1]; end; end; end; Código que analiza la secuencia: %ASUNTO: %Análisis experimental de la informaciónde una fuente con memoria % N=120000; z=secuencia(N); %Para tuplas de k símbolos % psk(n)= probabilidad del símbolo n % Hk = entropía % Hkn = entropía normalizada %%%%%%%%%%%%%%%%%%%%Grupos de un símbolos%%%%%%%%%%%%%%%%%%%%%%% ps1(1)=1−sum(z)/N; ps1(2)=sum(z)/N; H1=−ps1*log2(ps1)'; H1n=H1; %%%%%%%%%%%%%%%%%%%%Grupos de dos 12 símbolos%%%%%%%%%%%%%%%%%%%%%%% ps2=zeros(1,2^2); for l=1:2:N, if z(l:l+1)==[0 0], ps2(1)=ps2(1)+2/N; elseif z(l:l+1)==[0 1], ps2(2)=ps2(2)+2/N; elseif z(l:l+1)==[1 0], ps2(3)=ps2(3)+2/N; else, ps2(4)=ps2(4)+2/N; end; end; H2=−ps2*log2(ps2)'; H2n=H2/2; %%%%%%%%%%%%%%%%%%%%Grupos de tres símbolos%%%%%%%%%%%%%%%%%%%%%%% ps3=zeros(1,2^3); for l=1:3:N, if z(l:l+2)==[0 0 0], ps3(1)=ps3(1)+3/N; elseif z(l:l+2)==[0 0 1], ps3(2)=ps3(2)+3/N; elseif z(l:l+2)==[0 1 0], ps3(3)=ps3(3)+3/N; elseif z(l:l+2)==[0 1 1], ps3(4)=ps3(4)+3/N; 13 elseif z(l:l+2)==[1 0 0], ps3(5)=ps3(5)+3/N; elseif z(l:l+2)==[1 0 1], ps3(6)=ps3(6)+3/N; elseif z(l:l+2)==[1 1 0], ps3(7)=ps3(7)+3/N; else, ps3(8)=ps3(8)+3/N; end; end; H3=−ps3*log2(ps3)'; H3n=H3/3; %%%%%%%%%%%%%%%%%%%%Grupos de cuatro símbolos%%%%%%%%%%%%%%%%%%%%%%% ps4=zeros(1,2^4); for l=1:4:N, if z(l:l+3)==[0 0 0 0], ps4(1)=ps4(1)+4/N; elseif z(l:l+3)==[0 0 0 1], ps4(2)=ps4(2)+4/N; elseif z(l:l+3)==[0 0 1 0], ps4(3)=ps4(3)+4/N; elseif z(l:l+3)==[0 0 1 1], ps4(4)=ps4(4)+4/N; elseif z(l:l+3)==[0 1 0 0], ps4(5)=ps4(5)+4/N; elseif z(l:l+3)==[0 1 0 1], 14 ps4(6)=ps4(6)+4/N; elseif z(l:l+3)==[0 1 1 0], ps4(7)=ps4(7)+4/N; elseif z(l:l+3)==[0 1 1 1], ps4(8)=ps4(8)+4/N; elseif z(l:l+3)==[1 0 0 0], ps4(9)=ps4(9)+4/N; elseif z(l:l+3)==[1 0 0 1], ps4(10)=ps4(10)+4/N; elseif z(l:l+3)==[1 0 1 0], ps4(11)=ps4(11)+4/N; elseif z(l:l+3)==[1 0 1 1], ps4(12)=ps4(12)+4/N; elseif z(l:l+3)==[1 1 0 0], ps4(13)=ps4(13)+4/N; elseif z(l:l+3)==[1 1 0 1], ps4(14)=ps4(14)+4/N; elseif z(l:l+3)==[1 1 1 0], ps4(15)=ps4(15)+4/N; else, ps4(16)=ps4(16)+4/N; end; end; H4=−ps4*log2(ps4)'; H4n=H4/4; Hn=[H1n H2n H3n H4n]; 15 Debemos tener en cuenta que en realidad no existen fuentes digitales. El concepto de fuente digital se fundamenta en la manera de interpretar la señal que entrega la fuente. Comentaremos esto más detenidamente cuando veamos Fuentes extendidas: agrupación de símbolos. Veremos también esto cuando hablemos de Fuentes extendidas: agrupación de símbolos. También existe compresión con pérdidas principalmente para imágenes y audio, en que una pérdida de información se traduce en una reducción de la calidad. Si quiere decir una probabilidad de aparición de un símbolo es la unidad y el resto son cero, con lo cual los datos no contienen información y son unos datos inútiles. El algoritmo más sencillo que implementa este tipo de compresión es el código Huffman. 11 17 p s ( ) I s ( ) ð p s ( ) 0 0.2 0.4 16 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 17