Redundancia (teoría de la información)

En teoría de la información , la redundancia (redundación) mide la diferencia fraccional entre la entropía H(X) de un conjunto X y su valor máximo posible.${\displaystyle \log(|{\mathcal {A}}_{X}|)}$. ^{[ 1 ] [ 2 ]} De manera informal, es la cantidad de "espacio" desperdiciado utilizado para transmitir ciertos datos. La compresión de datos es una forma de reducir o eliminar la redundancia no deseada, mientras que la corrección de errores hacia adelante es una forma de agregar la redundancia deseada para fines de detección y corrección de errores cuando se comunica a través de un canal ruidoso de capacidad limitada .

Al describir la redundancia de datos brutos, la tasa de una fuente de información es la entropía promedio por símbolo. Para fuentes sin memoria, esto es simplemente la entropía de cada símbolo, mientras que, en el caso más general de un proceso estocástico , es

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),}$

en el límite, cuando n tiende a infinito, de la entropía conjunta de los primeros n símbolos dividida por n . Es común en la teoría de la información hablar de la "tasa" o " entropía " de un lenguaje. Esto es apropiado, por ejemplo, cuando la fuente de información es prosa inglesa. La tasa de una fuente sin memoria es simplemente${\displaystyle H(M)}$, puesto que por definición no existe interdependencia entre los mensajes sucesivos de una fuente sin memoria.

La tasa absoluta de un idioma o fuente es simplemente

${\displaystyle R=\log |\mathbb {M} |,\,}$

el logaritmo de la cardinalidad del espacio de mensajes o alfabeto. (Esta fórmula a veces se denomina función de Hartley ). Esta es la tasa máxima posible de información que se puede transmitir con ese alfabeto. (El logaritmo debe tomarse en una base apropiada para la unidad de medida en uso). La tasa absoluta es igual a la tasa real si la fuente no tiene memoria y tiene una distribución uniforme .

La redundancia absoluta puede definirse entonces como

${\displaystyle D=Rr,\,}$

la diferencia entre la tasa absoluta y la tasa.

La cantidad${\displaystyle {\frac {D}{R}}}$se denomina redundancia relativa y proporciona la máxima relación de compresión de datos posible , cuando se expresa como el porcentaje en el que se puede reducir el tamaño de un archivo. (Cuando se expresa como una relación entre el tamaño del archivo original y el tamaño del archivo comprimido, la cantidad${\displaystyle R:r}$proporciona la relación de compresión máxima que se puede lograr.) Complementario al concepto de redundancia relativa es la eficiencia , definida como${\displaystyle {\frac {r}{R}},}$de modo que${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$Una fuente sin memoria con una distribución uniforme no tiene redundancia (y por lo tanto, tiene una eficiencia del 100%) y no se puede comprimir.

Una medida de redundancia entre dos variables es la información mutua o una variante normalizada. Una medida de redundancia entre muchas variables viene dada por la correlación total .

La redundancia de datos comprimidos se refiere a la diferencia entre la longitud esperada de los datos comprimidos.${\displaystyle n}$mensajes${\displaystyle L(M^{n})\,\!}$(o velocidad de datos esperada)${\displaystyle L(M^{n})/n\,\!}$) y la entropía${\displaystyle nr\,\!}$(o tasa de entropía)${\displaystyle r\,\!}$). (Aquí asumimos que los datos son ergódicos y estacionarios , por ejemplo, una fuente sin memoria). Aunque la diferencia de tasas${\displaystyle L(M^{n})/nr\,\!}$puede ser arbitrariamente pequeño como${\displaystyle n\,\!}$aumentó, la diferencia real${\displaystyle L(M^{n})-nr\,\!}$, no puede, aunque teóricamente puede estar limitado superiormente por 1 en el caso de fuentes sin memoria de entropía finita.

La redundancia en contextos de teoría de la información también puede referirse a la información que es redundante entre dos informaciones mutuas. Por ejemplo, dadas tres variables${\displaystyle X_{1}}$,${\displaystyle X_{2}}$, y${\displaystyle Y}$Se sabe que la información mutua conjunta puede ser menor que la suma de las información mutua marginal:${\displaystyle I(X_{1},X_{2};Y)<I(X_{1};Y)+I(X_{2};Y)}$En este caso, al menos parte de la información sobre${\displaystyle Y}$revelado por${\displaystyle X_{1}}$o${\displaystyle X_{2}}$es lo mismo. Esta formulación de redundancia es complementaria a la noción de sinergia, que se produce cuando la información mutua conjunta es mayor que la suma de las marginales, lo que indica la presencia de información que solo se revela mediante el estado conjunto y no mediante ninguna colección más simple de fuentes. ^{[ 3 ] [ 4 ]}

• Codificación de redundancia mínima
  • Codificación de Huffman
• Compresión de datos
• Función de Hartley
• Negentropía
• Teorema de codificación de fuente
• Exceso de exhaustividad

• Reza, Fazlollah M. (1994) [1961]. Introducción a la teoría de la información . Nueva York: Dover [McGraw-Hill]. ISBN 0-486-68210-2.
• Schneier, Bruce (1996). Criptografía aplicada: protocolos, algoritmos y código fuente en C. Nueva York: John Wiley & Sons, Inc. ISBN 0-471-12845-7.
• Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). "Comparación de medidas de redundancia y relevancia para la selección de características en la clasificación de tejidos en imágenes de TC". Avances en minería de datos. Aplicaciones y aspectos teóricos . Springer. pp. 248–262 . CiteSeerX 10.1.1.170.1528 .