Loja- Ecuador 12/01/2016

UNIVERSIDAD NACIONAL DE LOJA ÁREA DE LA ENERGÍA, LAS INDUSTRIAS Y LOS RECURSOS NATURALES NO RENOVABLES

CARRERA DE INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES

TEORÍA DE LA INFORMACIÓN Y CODIFICACIÓN

INECUACIÓN DE MCMILLAN

Docente: Ing. Paulo Samaniego.

Estudiante: Jenny J. Luzuriaga Jiménez.

Ciclo: 6to “B”

TEORIA DE LA INFORMACIÓN Y CODIFCACIÓN

Inecuación de McMillan

Jenny Luzuriaga 2

Inecuación de McMillan

La desigualdad de McMillan es un teorema de la teoría de códigos que reduce la

existencia de códigos unívocamente descifrables al cumplimiento de la desigualdad de

Kraft. Es decir, si existe un código unívocamente descifrable con longitudes de palabra

prescritas entonces es un código instantáneamente descifrable que satisface la

desigualdad de Kraft.

Tenemos:

∑ 𝑟−𝑙𝑖 ≤ 1

𝑞

𝑖=1

(1)

Donde:

q: es la cantidad de mensajes de la fuente.

r: es la cantidad de símbolos diferentes en el alfabeto del código y

𝑙𝑖: es la longitud de las palabras código.

Esta inecuación constituye una condición suficiente que deben cumplir las longitudes de

palabras de un código instantáneo, construyendo un código con tales longitudes.

Puesto que lo códigos instantáneos son una subdivisión de los códigos unívocos, la

condición suficiente se aplica también a ellos; es decir, si las longitudes 𝑙1, 𝑙2, … , 𝑙𝑞

satisfacen la relación de Kraft, puede construirse con ellas un código unívoco.

La demostración de la necesidad de la inecuación de Kraft, por el contrario, no puede

extenderse a los códigos unívocos. Realmente la condición necesaria de la inecuación

sugiere el análisis de los requisitos que deben cumplir las longitudes de las palabras

códigos unívocos.

Se sabe que la inecuación de Kraft expresa una condición necesaria para los códigos

instantáneos. ¿Es válida la misma condición para los códigos unívocamente

decodificables de carácter general?, contestando a la pregunta se llegó a probar que la

condición de la inecuación de Kraft es igual de válida para los códigos unívocos, y esto

fue probado primeramente por McMillan en 1956, y luego Karush en 1961 simplifico la

demostración.

Partiendo de la demostración de la inecuación de Kraft consideremos la expresión:

Inecuación de McMillan

Jenny Luzuriaga 3

(∑ 𝑟−𝑙

𝑞

𝑖=1

)

𝑛

= (𝑟−𝑙1 + 𝑟−𝑙2 + ⋯ + 𝑟−𝑙𝑞)𝑛

(2)

Su desarrollo tendrá 𝑞𝑛 términos, de la forma

𝑟−𝑙11−𝑙𝑖2− ⋯.−𝑙𝑖𝑛 = 𝑟−𝑘 (3)

Donde, por definición tenemos

𝑙𝑖1+ 𝑙𝑖2

+ ⋯ + 𝑙𝑖𝑛= 𝑘 (4)

Si tenemos que 𝑙 es la mayor de las longitudes 𝑙𝑖, k puede entonces tomar un conjunto

de valores comprendido entre n y nl.

Y si definimos 𝑁𝑘 como el número de términos de la forma 𝑟−𝑘 existente en la ecuación

(2).

Entonces:

(∑ 𝑟−𝑙

𝑞

𝑖=1

)

𝑛

= ∑ 𝑁𝑘𝑟−𝑘

𝑛𝑙

𝑘=𝑛

(5)

Ahora con la ecuación (4), vemos que 𝑁𝑘 representa también el número de porciones

de n palabras código que pueden formarse de modo que cada porción tenga una

longitud de exactamente K símbolos. Si el código es unívocamente decodificable, 𝑁𝑘 no

debe ser mayor de 𝑟𝑘, número de secuencias de orden r distintas de longitud k. Por

tanto

(∑ 𝑟−𝑙

𝑞

𝑖=1

)

𝑛

≤ ∑ 𝑟𝑘𝑟−𝑘

𝑛𝑙

𝑘=𝑛

≤ 𝑛𝑙 − 𝑛 + 1

≤ 𝑛𝑙 (6)

La ecuación (6) es la prueba que se buscaba, ya que si 𝑥 > 1, 𝑥𝑛 > 𝑛𝑙, con tal de tomar

un valor n suficientemente grande. La expresión (6) se cumple para cualquier valor

entero de n, de modo que tendremos:

∑ 𝑟−𝑙𝑖 ≤ 1

𝑞

𝑖=1

(7)

Inecuación de McMillan

Jenny Luzuriaga 4

Ejemplos:

1. Tenemos el siguiente alfabeto código 𝑨 = {𝒂𝟏,𝒂𝟐, … , 𝒂𝒏} = {𝟎, 𝟏𝟎, 𝟏𝟏𝟎, 𝟏𝟏𝟏}

con sus respectivas longitudes de palabra código 𝑳 = {𝒍𝟏,𝒍𝟐, … , 𝒍𝒏} =

{𝟏, 𝟐, 𝟑, 𝟑} usando la desigualdad determinar si es un código unívocamente

decodificable.

∑ 𝑟−𝑙𝑖 ≤ 1

𝑞

𝑖=1

∑ 2−𝑙𝑖 = 2−1 + 2−2 + (2)2−3 ≤ 1

4

𝑖=1

1 = 1

Lo que indica que es un código unívocamente decodificable y por ser igual a uno también se denomina compacto.

2. Se desea diseñar un código unívocamente decodificable ternario (r=3) con sus respectivas longitudes de palabra código 1, 1, 2, 2, 3, 3. Ya que un código unívocamente decodificable satisface la Inecuación de Kraft por el Teorema de McMillan nosotros comprobamos si este es el caso.

Usando la inecuación de Kraft tenemos:

∑ 𝑟−𝑙𝑖 ≤ 1

𝑞

𝑖=1

∑ 3−𝑙𝑖 = (2)3−1 + (2)3−2 + (2)3−3 ≤ 1

4

𝑖=1

0.963 ≤ 1

Podemos observar que un código unívocamente decodificable se puede encontrar con

dichas longitudes.

Pero la misma inecuación de Kraft puede satisfacerse para códigos instantáneos y

debido a que estos mismos códigos instantáneos pueden construirse de forma

sistemática siguiendo un procedimiento se puede decir que el siguiente código

instantáneo, que es unívocamente decodificable, puede designarse como:

Inecuación de McMillan

Jenny Luzuriaga 5

0 1 20 21

220 221

Para realizar la construcción de este código, una forma sistemática de hacer esto es

enumerar o contar a través del alfabeto código.

3. Diseñamos un código binario con las siguientes longitudes de palabra

código: 2, 3, 2, 2, 2.

Usando la inecuación tenemos:

∑ 𝑟−𝑙𝑖 ≤ 1

𝑞

𝑖=1

∑ 2−𝑙𝑖 = (4)2−2 + 2−3 ≤ 1

5

𝑖=1

2.125 > 1

Como podemos observar no se cumple la inecuación por lo que podemos decir que no

es un código instantáneo y por lo tanto tampoco es un código unívocamente

decodificable.

Conclusiones:

Kraft dice que si satisface la desigualdad entonces existe un código prefijo

(instantáneo) de longitud L, en cambio McMillan dice que ese código es

unívocamente decodificable.

La desigualdad de Kraft es la misma que la de McMillan, la diferencia radica en

que Kraft la definió para códigos prefijo, mientras que McMillan para códigos

unívocamente decodificables.

Inecuación de McMillan

Jenny Luzuriaga 6

Bibliografía:

[1] Teoría de la Información. 11/02/2016. http://ovandos-

blog.blogspot.com/2010/05/desigualdad-de-kraft-mcmillan.html

[2] TOGNERI, Roberto, J.S de SILVA, Christopher; Fundamentals of Information Theory

and Coding Design; 2006.

[3] ABRAMSON, Norman; Teoría de la Información y Codificación; Quinta Edición; 1981.