Ejercicio 5.25 a)

Ejercicio 5.25 a)

de Diego Martin Celery Lopez -
Número de respuestas: 2

Hola, necesito aclararme con cual es la justificación, para decir que se encontró un codigo mejor cuando se logra construir un codigo con l1=1, menor que el supuesto absurdo de que l1>=2.

O sea, es mejor el código porque se encontró uno con el código de la palabra mas probable c1 de largo 1? eso alcanza para decir que es codigo mejor? o porque L=SUMATORIA(p1.l1) es mejor y habría que probarlo con cuentas?

No se si me explico, la pregunta es por que el código nuevo encontrado con L(c1)=1 alcanza para decir que es mejor que el código supuesto con L(c1)>=2 ?


Saludos

En respuesta a Diego Martin Celery Lopez

Re: Ejercicio 5.25 a)

de Federico Lecumberry -
Hola Diego, no entiendo tu consulta. Parece ser parte de un razonamiento por el absurdo que llega a ese punto.
Si te parece lo podemos ver en la clases de consulta del lunes (remota) o miércoles (presencial)
En general, si tenemos dos códigos C1 y C2, con largos medios, L(C1) y L(C2) respectivamente, y se cumple $$L(C1) Saludos.
En respuesta a Federico Lecumberry

Re: Ejercicio 5.25 a)

de Diego Martin Celery Lopez -
Disculpa, intento aclarar.
El ejercicio 5.25 del libro:
"Although the codeword lengths of an optimal variable
length code are complicated functions of the message probabilities {p1, p2, . . . , pm}, it
can be said that less probable symbols are encoded into longer codewords. Suppose
that the message probabilities are given in decreasing order p1 > p2 >= · · · >= pm .
parte a):
Prove that for any binary Huffman code, if the most probable message symbol has
probability p1 > 2/5 , then that symbol must be assigned a codeword of length 1."

Se intenta probar por el absurdo.
Asume que el largo del codigo mas probable c1 es l1=L(c1) >=2. Luego se arma un árbol binario cuyo largo a la hoja c1=00 es l1=2.
Luego restan 3 clases C01,C10, y C11 de palabras codificadas que son los códigos que empiezan con 01,10,11. Todos esos códigos tienen largo >=2.

Pero luego, transforma ese árbol, achicando el código c1 de 00 a 0, o sea l1=1 de la clase C0. El nuevo árbol tendrá otras 3 clases C10 con L>=2, C110 y C111 con L>=3.
Entonces las probabilidades de las clases de códigos quedan:
Pr(C0)<2/5
Pr(C10)+Pr(C110)+Pr(C111) > 3/5 ==> Pr(C10) > 1/5 ==> Pr(C110)+Pr(C111) <=2/5. Entonces logramos obtener un supuesto código mejor con el largo l(c1)=1. Pero por qué ese código es mejor? <=========== ESA ES MI DUDA.

Espero haberme expresado mejor! gracias!

Nota sobre Pr(C110)+Pr(C111) <=2/5 en el nuevo mejor código:
Las probabilidades totales mantienen este orden.
PR(C0) > PR(C10) >= PR(C110) >= PR(C111)
Dijimos que en el nuevo mejor código Pr(C110) + Pr(C111) <=2/5
Si fuera Pr(C110)+Pr(C111) > 2/5 ==> Pr(C110) > 1/5 ==>
PR(C0) + PR(C10) + PR(C110) + PR(C111) > 1 lo cual es absurdo
>2/5 >1/5 ambos > 2/5 > 1