Codificación de fuente

2025-10-30T18:34:16Z

Rmedina: Añadido un ejemplo en Python

{{Cab0_TSC
|Autores=[[user:JDíaz|J.M. Díaz Nafría]], [[User:Mario José Ruiz Asenjo]]
|Docentes=[[user:JDíaz|J.M. Díaz Nafría]]
}}
==Definiciones==
La '''codificación de fuente''' trata de lograr la forma más conveniente de representar los mensajes de la fuente, adaptándose a las características de la misma, utilizando el menor número posible de símbolos que sea posible para su transmisión a través del canal e ignorando los posibles errores que puedan darse en la transmisión por el canal. De esta última cuestión se encarga la [[codificación de canal]], que no debe confundirse con la de fuente, cumpliendo estas dos codificaciones funciones complementarias.

Así, el codificador de fuente convierte una secuencia de símbolos generados por la fuente (o tras el muestreo de la [[señal]] si esta fuera analógica en origen) en otra secuencia distinta, empleando símbolos de un [[alfabeto]] distinto llamado alfabeto de codificación, que será igual al alfabeto de entrada del canal.

La codificación de fuente asigna a cada elemento del alfabeto finito <math>F</math>, al que representamos por <math>F^n</math> (para un determinado valor de ''n''), una palabra del código, esto es, una secuencia de elementos del alfabeto de codificación finito <math>D</math>:

:<math>F^n, n \text{ dado}\longrightarrow\text{ palabra del código}=\{\text{secuencia de elementos de }D\}</math>

Dependiendo de si la asignación de <math>F^n</math> sobre <math>D</math> es o no unívoca, la codificación de fuente se denomina '''sin pérdidas''' o '''con pérdidas'''. Es evidente que si la aplicación <math>F^n\rightarrow D</math> no es inyectiva, el código ''<math>D</math>'' es insuficiente para determinar el código original y esto causa pérdidas. Los del primer tipo se basan generalmente en '''codificación estadística''', buscando códigos cuya longitud promedio sea inferior, como hicieron Samuel Morse y Alfred Vail al desarrollar el famoso código que adoptó el nombre del primero.<ref>Pierce, John R.; Noll, A. Michael (1995). ''Señales. La ciencia de las Telecomunicaciones''. Barcelona: Reverté.</ref>

Los del segundo tipo son los que logran las mayores capacidades de comprensión y se basan en dos técnicas básicas: 1) la '''codificación predictiva''', que trata de prever los códigos de fuente siguientes a partir de los previos y se centra en codificar para su transmisión solo aquello que no puede predecir; 2) '''transformacional''', basado en una representación alternativa de la señal (normalmente transformadas de Fourier o derivadas) que haga más eficiente la codificación de la información relevante.<ref>Díaz Nafría, J.M. (2020). Unidad 2: Caracterización de la señal. Presentación disponible en el aula virtual de la asignatura “''Sistemas de transmisión. Comunicaciones ópticas''.” de la UDIMA. Consultado el 10/06/2023 en [https://aula.udima.es/course/view.php?id=46860 Aula virtual]. </ref> Otro elemento fundamental de la codificación de fuente con pérdidas radica en un estudio detallado de las características de los destinatarios de la información, que en el caso de las señales analógicas de sonido e imagen son los sentidos de la audición y la visión. La idea es sencilla: si algo no va a percibirse, no es necesario transmitirlo (v. artículo [[señal de audio]]).

Puede también considerarse que la [[cuantificación no uniforme]] en la que se logra una calidad percibida que es equivalente a la que se lograría mediante una [[Cuantificación|cuantificación uniforme]] que emplea un mayor número de dígitos binarios, es una técnica de codificación de fuente en la medida que responde al concepto y objetivo inicialmente planteado. Sin embargo, si bien estas técnicas se basan en una cuantificación escalar, es decir muestra a muestra, las otras técnicas recurren a la cuantificación vectorial a la que nos hemos referido en el artículo de [[Codificación de bloque (cuantificación vectorial)|codificación de bloque]].

== Tipos de codificación de fuente ==

=== Codificación estadística ===
De acuerdo a la teoría matemática de la comunicación, propuesta por [[Shannon, Claude Elwood|Shannon]], la cantidad de información que aporta una fuente viene determinada por su [[Entropía o cantidad de información|entropía]], y esta a su vez por las probabilidades de emisión de los mensajes que genera la fuente, como se discute en el artículo [[entropía o cantidad de información]]. El objetivo de la codificación estadística es la de considerar las características estadísticas para lograr que los códigos empleados <math>D</math> hagan que el flujo binario resultante –tras la codificación– tienda al valor de entropía de la fuente. Es decir, si llamamos <math>L_b\{D\}</math> a la longitud binaria de los códigos <math>D</math> entonces <math>E[L_b\{D\}]\rightarrow H\{F\}</math>.

Un tipo de codificación de fuente sencillo es el conocido '''Algoritmo de Huffmann'''.<ref>Sklar, B.; Harris, F. (2020). ''Digital Communications. Fundamentals and Applications''. London: Pearson.</ref> Éste nos permite construir un código óptimo en el sentido anterior, cuya longitud es variable sin requerir prefijo, y que para determinadas distribuciones de probabilidad puede lograr el objetivo <math>E[L_b\{D\}]= H\{F\}</math>. El algoritmo básico consiste en primero ordenar los símbolos de mayor a menor probabilidad, a continuación se juntan las parejas de menor probabilidad en un punto de bifurcación caracterizado por una probabilidad conjunta que se considera para una nueva reordenación de los símbolos o grupos de símbolos en orden de probabilidad decreciente para el siguiente reagrupamiento. De esta manera, se conforma progresivamente un árbol hasta llegar a un tronco común, que es el que servirá para la decisión de los códigos originales en el decodificador. Para garantizar una decodificación biunívoca, en las bifurcaciones del árbol se atribuyen los 0 y 1 en el mismo orden. Los códigos Huffman resultantes serán así de longitud variable, haciendo que los mensajes o códigos originales más frecuentes les corresponda un código Huffman de longitud menor y los más raros tendrán longitudes mayores, y que en promedio se encuentren máximamente próximos a la entropía de la fuente.

=== Codificación predictiva ===
[[File:Codificador predictivo.png|thumbnail|'''Figura 1''': Codificador y decodificador predictivo.]]
En la codificación predictiva, tanto el ''codificador'' como el ''decodificador'' (representados en la fig.1) hacen una predicción de la muestra actual <math>\tilde{x}(n)</math>, basada en las muestras previas de la señal reconstruida, <math>\hat{x}(n)</math> y solo se codifica y transmite por el canal la parte de la señal que no se logra predecir, <math>d(n)=x(n)-\hat{x}(n)</math>, o mejor dicho, su valor re-cuantificado <math>q(n)</math>. Obsérvese que cuanto menor sea el error de predicción, <math>d(n)</math>, menos intervalos de cuantificación será necesario emplear para codificar dicho error y, por tanto, tanto mayor será la capacidad del código de reducir el régimen binario de codificación. Por esa razón se denomina ganancia de codificación a la relación entre la varianza de la señal original y la del error:
:<math>G_p=\frac{\sigma_x^2}{\sigma_d^2}</math>

En los '''esquemas adaptativos''', tanto el predictor como el cuantificador y<sub>,</sub> por tanto, también el reconstructor pueden cambiar dinámicamente dependiendo de la capacidad de lograr predicciones más o menos precisas. Dependiendo de si los parámetros del predictor y de la cuantificación son transmitidos o no al decodificador, se habla de '''adaptación hacia adelante''' o '''hacia atrás''' respectivamente. En este último caso, los parámetros se determinan en base a las muestras reconstruidas, teniendo el decodificador la capacidad autónoma de determinarlos.

=== Codificación transformacional ===
[[File:Codificación transformacional.png|thumbnail|'''Figura 2''': Codificador transformacional.]]
En la codificación transformacional se busca representar la señal de un espacio alternativo en el que la energía esté concentrada en unos pocos coeficientes, lo que permite dedicar una cuantificación de mayor orden (precisión) para los coeficientes con mayor energía, o incluso hacerlo en función del efecto que estos coeficientes puedan tener en el destino (por ejemplo, el que vayan a tener un efecto perceptivo en el caso de señales de audio o video, como se hace en la aplicación de los patrones de enmascaramiento a los que nos hemos referido en el artículo de [[señal de audio]]). Entre las transformaciones lineales más usuales se encuentra la directa de coseno, que a diferencia de la de Fourier sus coeficientes son siempre reales y por tanto un bloque de N muestras se puede representar por otro bloque de ''N'' coeficientes.
[[File:Codificación de subbandas.png|thumbnail|'''Figura 3''': Codificador y decodificador de subbandas.]]
La '''codificación por sub-bandas''' puede considerarse un caso especial de codificación transformacional en la que se emplea un banco de filtros FIR contiguos, <math>H_1(\omega), H_2(\omega),...H_M(\omega)</math> que subdividen la banda de interés en varias subbandas, a cada una de las cuales se aplica una precisión de cuantificación diferente, normalmente en función de la capacidad perceptiva de las mismas. Como se ilustra en la figura 3, después de cada filtro la frecuencia de muestreo se reduce –en virtud del [[teorema de muestreo]]– mediante un diezmado de factor correspondiente a la razón entre el ancho de banda de la señal ''x(n)'' y el de <math>H_i(\omega)</math>, operación que se invierte –mediante interpolación– en la decodificación. La elección del banco de filtros de entrada y salida es un aspecto delicado del diseño de la codificación para garantizar que la combinación de los efectos de filtrado minimice la distorsión de la señal.<ref>Proakis, J. G.; Manolakis, D. G. (2007). ''Tratamiento digital de señales''. Madrid: Pearson.</ref>

==Código==
El siguiente código de MATLAB, propuesto en la documentación de ayuda,<ref> Mathworks (2006). huffmandict. En ''Help Center'' [ayuda en línea]. Consultado el 10/06/2023 de: [https://es.mathworks.com/help/comm/ref/huffmandict.html Help Center].</ref> muestra el uso de la función integrada <code>huffmandict</code> para la obtención del alfabeto de un código Huffman de cinco símbolos cuyas probabilidades se indican al principio, a la vez que presenta el resultado generado. Los código obtenidos en la variable <code>dict</code> se transforman en cadenas de caracteres para su visualización en el espacio de comandos mediante la función <code>cellfun</code> que aplica elemento a elemento la función <code>num2str</code> a cada código.
<syntaxhighlight lang="matlab">
symbols = (1:5); % Alfabeto (vector)
prob = [.3 .3 .2 .1 .1]; % Probabilidad de los símbolo (vector)
[dict, L_med] = huffmandict(symbols, prob);
dict(:, 2) = cellfun(@num2str, dict(:, 2), 'UniformOutput', false)
</syntaxhighlight>
Lo que devuelve en el espacio de comandos el código Huffman del alfabeto:
<syntaxhighlight lang="matlab">
dict=5×2 cell
{[1]} {'0 1' }
{[2]} {'0 0' }
{[3]} {'1 0' }
{[4]} {'1 1 1'}
{[5]} {'1 1 0'}
</syntaxhighlight>
Podemos determinar la eficiencia del código comparandolo con la entropía de la fuente:
<syntaxhighlight lang="matlab">
>> Efic = sum(prob.*log2(1./prob))/L_med
ans =
0.9868
</syntaxhighlight>

[[Category:65) Telecomunicación y telecontrol]]
[[Category:GlossaLAB.edu]]
[[Category:Sistemas de transmisión]]
[[Category:Teoría de la información]]
[[Category:Teoría de la señal y la comunicación]]

=== Ejemplo adicional en Python ===

A continuación se presenta un ejemplo complementario que ilustra la relación entre la entropía de una fuente y la longitud media de un código de longitud variable. Se asignan códigos más cortos a los símbolos más probables, y se compara el resultado con la entropía teórica de la fuente.

<syntaxhighlight lang="python">
import math

# Probabilidades de la fuente
symbols = ['A', 'B', 'C', 'D']
probs = [0.5, 0.25, 0.15, 0.10]

# Asignación de códigos sencilla: prefijos más cortos a símbolos más probables
codebook = {'A': '0', 'B': '10', 'C': '110', 'D': '111'}

# Cálculo de la longitud media del código
avg_length = sum(probs[i] * len(codebook[symbols[i]]) for i in range(len(symbols)))

# Cálculo de la entropía de la fuente
entropy = -sum(p * math.log2(p) for p in probs)

print("Código asignado:", codebook)
print(f"Longitud media del código: {avg_length:.3f} bits/símbolo")
print(f"Entropía de la fuente: {entropy:.3f} bits/símbolo")
</syntaxhighlight>

'''Salida esperada:'''
<pre>
Código asignado: {'A': '0', 'B': '10', 'C': '110', 'D': '111'}
Longitud media del código: 1.650 bits/símbolo
Entropía de la fuente: 1.742 bits/símbolo
</pre>

El resultado muestra que la longitud media del código se aproxima al valor de la entropía de la fuente, cumpliendo el principio de la codificación eficiente.

==Referencias==

[[Category:65) Telecomunicación y telecontrol]]
[[Category:GlossaLAB.edu]]
[[Category:Sistemas de transmisión]]
[[Category:Teoría de la señal y la comunicación]]
[[Category:Teoría de la información]]

Draft:Entropía

2025-10-30T07:37:09Z

Rmedina: Created page with "= Entropía (Teoría de la Información) = La entropía, en el contexto de la Teoría de la Información, mide la incertidumbre asociada a una fuente de datos. El concepto fue introducido por Claude Shannon en 1948 y sirve como base para cuantificar la cantidad media de información que aporta un mensaje antes de ser recibido. Dicho de otro modo, la entropía nos indica cuánta sorpresa o imprevisibilidad hay en los resultados producidos por una fuente aleatoria. Cuand..."

= Entropía (Teoría de la Información) =

La entropía, en el contexto de la Teoría de la Información, mide la incertidumbre asociada a una fuente de datos. El concepto fue introducido por Claude Shannon en 1948 y sirve como base para cuantificar la cantidad media de información que aporta un mensaje antes de ser recibido. Dicho de otro modo, la entropía nos indica cuánta sorpresa o imprevisibilidad hay en los resultados producidos por una fuente aleatoria.

Cuando una fuente siempre produce el mismo símbolo, no obtenemos información nueva (entropía cero). En cambio, si los símbolos aparecen con probabilidades similares, resulta mucho más difícil anticiparlos, y la entropía aumenta.

== Interpretación intuitiva ==

La entropía puede verse como el promedio de información que recibimos cada vez que la fuente genera un símbolo. Si los resultados son previsibles, apenas hay información. Por el contrario, cuando todos los eventos son igualmente probables, cada observación aporta nueva información y la entropía es máxima.

Esta idea está conectada con la noción de “sorpresa”: un evento poco probable aporta más información cuando ocurre, mientras que un evento muy probable aporta menos.

== Definición matemática ==

Sea una variable aleatoria discreta X, que toma valores {x1, x2, ..., xn} con probabilidades P(xi). La entropía se define como:

<math>
H(X) = -\sum_{i=1}^{n} P(x_i)\log_2(P(x_i))
</math>

El logaritmo se toma en base 2 porque la unidad habitual de información en este contexto es el bit.

Un caso particular ocurre cuando todos los valores posibles tienen la misma probabilidad n. En ese caso:

<math>
H(X) = \log_2(n)
</math>

lo que indica que la entropía máxima se alcanza cuando todos los resultados son igualmente probables.

== Ejemplo práctico ==

Supongamos una fuente que genera dos símbolos, A y B, con probabilidades:

* P(A)=0.75
*P(B)=0.25

Entonces:

<math>
H(X)= -\left[0.75\log_2(0.75) + 0.25\log_2(0.25)\right] \approx 0.811 \text{ bits}
</math>

Si ambos símbolos tuvieran probabilidad 0.5, la entropía sería:

<math>
H(X)=1 \text{ bit}
</math>

Este resultado refleja que cuanto más equilibradas están las probabilidades, mayor es la incertidumbre y, por tanto, la entropía.

== Ejemplo en Python ==

<syntaxhighlight lang="python">
import math

def entropy(probabilities):
return -sum(p * math.log2(p) for p in probabilities if p > 0)

print(entropy([0.75, 0.25])) # ≈ 0.811 bits
</syntaxhighlight>

== Conceptos relacionados ==

* [[Información]]
* [[Fuente de información]]
* [[Ruido]]
* [[Redundancia]]
* [[Codificación]]
* [[Capacidad del canal]]
== Referencias ==

<references/>

* Shannon, C. E. (1948). ''A Mathematical Theory of Communication''. Bell System Technical Journal, 27(3), 379–423. https://archive.org/details/bstj27-3-379

* MacKay, D. J. C. (2003). ''Information Theory, Inference, and Learning Algorithms''. Cambridge University Press. https://www.inference.org.uk/itprnn/book.pdf

User:Rmedina

2025-10-29T20:55:37Z

Rmedina: create user page

{{Person}}[[Category:Person]]

glossaLAB - User contributions [en]

Codificación de fuente

Draft:Entropía

User:Rmedina