Redundancia (teoría de la información)

En teoría de la información , la redundancia 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]} Informalmente, es la cantidad de "espacio" desperdiciado que se usa para transmitir ciertos datos. La compresión de datos es una forma de reducir o eliminar la redundancia no deseada, mientras que las sumas de verificación son una forma de agregar la redundancia deseada para fines de detección de errores cuando se comunica a través de un canal ruidoso de capacidad limitada .

Definición cuantitativa

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 va al infinito, de la entropía conjunta de los primeros n símbolos divididos por n . Es común en la teoría de la información hablar de "tasa" o " entropía " de un idioma. Esto es apropiado, por ejemplo, cuando la fuente de información es la prosa inglesa. La tasa de una fuente sin memoria es simplemente${\displaystyle H(M)}$, ya que por definición no hay interdependencia de los sucesivos mensajes de una fuente sin memoria. ^{[ cita requerida ]}

La tasa absoluta de un idioma o fuente es simplemente

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

el logaritmo de la cardinalidad del espacio del mensaje, o alfabeto. (Esta fórmula a veces se denomina función de Hartley ). Esta es la velocidad máxima posible de información que se puede transmitir con ese alfabeto. (El logaritmo debe llevarse a 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 se puede definir como

${\displaystyle D=R-r,\,}$

la diferencia entre la tasa absoluta y la tasa.

La cantidad ${\displaystyle {\frac {D}{R}}}$se denomina redundancia relativa y proporciona la máxima tasa 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}$da la máxima relación de compresión que se puede lograr.) Complementario al concepto de redundancia relativa es la eficiencia , definida como${\displaystyle {\frac {r}{R}},}$ así que eso ${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$. Una fuente sin memoria con una distribución uniforme tiene cero redundancia (y por lo tanto una eficiencia del 100%) y no se puede comprimir.

Otras nociones

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 datos comprimidos de${\displaystyle n}$ mensajes ${\displaystyle L(M^{n})\,\!}$ (o tasa 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).${\displaystyle L(M^{n})/n-r\,\!}$ puede ser arbitrariamente pequeño como ${\displaystyle n\,\!}$ aumentado, la diferencia real ${\displaystyle L(M^{n})-nr\,\!}$, no puede, aunque teóricamente puede tener un límite superior en 1 en el caso de fuentes sin memoria de entropía finita.

Ver también

• 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
• Sobrecompletar

Referencias

1. Aquí se supone${\displaystyle {\mathcal {A}}_{X}}$ son los conjuntos en los que se definen las distribuciones de probabilidad.
2. MacKay, David JC (2003). "2.4 Definición de entropía y funciones relacionadas". Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge . pag. 33. ISBN 0-521-64298-1. La redundancia mide la diferencia fraccional entre H (X) y su valor máximo posible,${\displaystyle |\log(|{\mathcal {A}}_{X}|)}$

• 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; López-Sánchez, M .; Cerquides, J. (2010). "Comparación de medidas de relevancia y redundancia para la selección de características en la clasificación de tejidos de imágenes de TC". Avances en minería de datos. Aplicaciones y aspectos teóricos . Saltador. págs. 248-262. CiteSeerX  10.1.1.170.1528 .