• Author / Uploaded
• SilviTaPinOs

• Categories
• Algoritmos
• Informática
• Tecnología
• Física y matemáticas
• Matemática

Citation preview

G6 Erika González [email protected] Pedro Cuzco [email protected] Alex Yunga [email protected] UNIVERSIDAD POLITECNICA SALESIANA COMUNICACIONES DIGITALES (TEL) G1

Abstract.- The following report shows the coding fano and huffman implemented in the words Universidad Politecnica Salesiana. Key words— coding, fano, huffman.

I. Estos

códigos

Los códigos Huffman son códigos compactos. Es decir, el algoritmo de Huffman produce un código con una longitud media, L, que es la más pequeña posible de alcanzar para el número dado de símbolos fuente, código alfabético y estadísticas de la fuente.

INTRODUCCION. generan

una

representación

de

la

información de la fuente de forma que su tamaño se aproxime a la entropía teórica de esa fuente produciendo una comprensión.

II.

RESULTADO 3.3

MARCO TEORICO

A. Codificación Fano Ahora describimos un esquema de codificación para el diseño de códigos instantáneos llamado el Fano, o el código Shannon-Fano en relación con el hecho de que el régimen. Fue publicado independientemente por Shannon y Fano, que puede rendir cerca de la mayoría de los casos. Aunque principalmente de interés histórico por su falta de optimalidad, la codificación de Fano puede ser considerada como el precursor de Huffman óptimo. Para el caso importante de los códigos binarios, la codificación Fano divide cada grupo en dos equiprobables que agregan un 0 a un grupo y 1 al otro grupo. Los grupos se dividen sucesivamente hasta que no se pueden dividir más grupos (es decir, cada grupo tiene sólo un símbolo en ella). B. Codificación Huffman Códigos Huffman Ahora describimos una clase importante de códigos instantáneos conocidos como códigos de Huffman que se atribuyen a la obra pionera de Huffman. Códigos de Huffman surgen cuando se utiliza el algoritmo de Huffman para el diseño de códigos instantáneos dada. El Huffman Algoritmo intenta asignar a cada símbolo una palabra de código de longitud proporcional a la cantidad de información transmitida por ese símbolo. Los códigos Huffman son importantes porque del siguiente resultado .

2.10.2 DEFINICIÓN 3.11 Fuente Reducida Considera la fuente S con q Símbolos: {𝑆𝑖 : 𝑖 = 1,2, … 𝑞}. Y probabilidades de símbolos asociados {𝑃(𝑆𝑖 ): 𝑖 = 1,2, … 𝑞}. Deje que los símbolos se vuelvan a numerar para que 𝑃(𝑆1 ) ≥ 𝑃(𝑆2 ) ≥ ⋯ ≥ 𝑃(𝑆𝑞 ). Combinando el último r símbolos de S, {𝑆𝑞−𝑟+1 , 𝑆𝑞−𝑟+2 , … 𝑆𝑞 }. Cabe señalar que sólo podremos reducir una fuente exactamente r Símbolos si La fuente original tiene 𝑞 = 𝑟+∝ (𝑟 − 1) Símbolos donde es un entero no negativo. Para un binario (r=2) Código que se celebrará para cualquier valor de 𝑞 ≥ 2 . Para códigos no binarios Si 𝑞 = 𝑞−𝑟 No es un valor entero entonces símbolos "ficticios" (𝑟−1)

con probabilidad cero se añaden para crear una fuente con 𝑞 = 𝑟 + [∝](𝑟 − 1) Símbolos, dónde [∝] es el menor entero mayor o igual que ∝. El código trivial para la fuente reducida con r símbolos se utiliza entonces para diseñar el código compacto para la fuente reducida precedente como se describe en la siguiente resultado. RESULTADO 3.4 Supongamos que tenemos un código compacto para la fuente reducida 𝑆𝑗 . Designe los últimos símbolos de r 𝑆𝑗−1 , {𝑆𝑞−𝑟+1 , 𝑆𝑞−𝑟+2 , … 𝑆𝑞 }, Como los símbolos que fueron combinados para formar el símbolo combinado, 𝑆̂𝑞−𝑟+1 de 𝑆𝑗 . Asignamos a cada símbolo de 𝑆𝑗−1 , Excepto el último símbolo r, la palabra de código utilizada por el símbolo 𝑆𝑗 . Las palabras de código para el último r símbolo de 𝑆𝑗−1 se forman agregando {0,1,…r} a la palabra clave de 𝑆̂𝑞−𝑟+1 de formar 𝑆𝑗 nuevas palabras de código. Algoritmo Binario de Codificación de Huffman

Para el diseño de códigos binarios de Huffman, el algoritmo de codificación de Huffman es el siguiente: 1. 2.

3.

4.

Reordenar los símbolos fuente en orden decreciente de probabilidad de símbolo Reducir sucesivamente la fuente S a 𝑆1 , entonces 𝑆2 , y así sucesivamente, combinando los últimos dos símbolos de 𝑆𝑗 en un símbolo combinado y volver a ordenar el nuevo conjunto de probabilidades de símbolos para 𝑆𝑗+1 en orden decreciente. Para cada fuente mantener pista de la posición del símbolo combinado, 𝑆̂𝑞−1+1 . Terminar la fuente cuando se produce una fuente de dos símbolos. Para una fuente con q símbolos la fuente reducida con dos símbolos será 𝑆𝑞−2 . Asigne un código compacto para la fuente final reducida. Para una fuente de dos símbolos el código trivial es {0,1}. Retroceder a la fuente original S asignar un código compacto para la reducción fuente por el método descrito en el Resultado 3.4. El código compacto asignado a S es el código Huffman binario.

El funcionamiento del binario Huffman algoritmo de codificación se muestra mejor por la siguiente ejemplo. RESULTADO 3.5 Si el símbolo combinado, 𝑆̂𝑞−1 se coloca en la posición más alta disponible para asignación de probabilidad cuando la fuente reducida es reordenada, entoncesel código compacto tendrá la varianza de longitud media más pequeña. Implementación de software de codificación Huffman binario El binario Huffman algoritmo de codificación puede ser implementado en el software como una secuencia de operaciones de fusión y ordenación en un árbol binario. El algoritmo de codificación de Huffman es un codicioso que construye el árbol de decodificación de Huffman. Asignando inicialmente cada símbolo como el nodo raíz de un árbol de nodo único. La descodificación árbol se construye sucesivamente fusionando los dos últimos nodos, etiquetando loa bordes de los pares hijo izquierdoderecho de la operación de combinación con un 0 y 1, respectivamente, y ordenar los nodos restantes hasta que solo quede un nodo raíz. Es entonces la secuencia de etiquetas en los bordes que conectan la raíz con el nodo de la hoja de los detalles del algoritmo incluyendo una prueba de la optimalidad de los códigos de Huffman. r-ary Huffman Códigos Para el diseño de los códigos Huffman r-ary generales, el algoritmo de codificación de Huffman es como se presenta a continuación:

1.

2. 3.

4.

5.

𝑞−𝑟

Calcular ∝= (𝑟−1). Si ∝ es un valor no entero y añade símbolos "ficticios" a la fuente con probabilidad cero hasta que hay 𝑞 = 𝑟 + [∝](𝑟 − 1) símbolos. Reordenar los símbolos fuente en orden decreciente de probabilidad de símbolos. Reducir sucesivamente la fuente S para 𝑆1 , entonces 𝑆2 , y así sucesivamente, combinando los últimos r símbolos de 𝑆𝑗 en un símbolo combinado y volver a ordenar el nuevo conjunto de probabilidades de símbolos para 𝑆𝑗+1 en orden decreciente. Para cada fuente mantener pista de la posición del símbolo combinado, , 𝑆̂𝑞−1 .Terminar la fuente cuando se produce una fuente con exactamente r símbolos. Para una fuente con q símbolos la fuente reducida con r símbolos será 𝑆[∝] . Asigne un código r-ary compacto para la fuente final reducida. Para una fuente con r símbolos el código trivial es {0,1,…r}. Retroceder a la fuente original S asignar un código compacto para la jth reducción fuente por el método descrito en el Resultado 3.4. El código compacto asignado a S, menos las palabras de código asignadas a cualquier símbolo "ficticio", es el r-ary código de Huffman.

III.

DESARROLLO

Codificar usando CODIFICACIÓN FANO Y HUFFMAN: UNIVERSIDAD POLITÉCNICA SALESIANA, luego calcular eficiencia de cada código. Codificación mediante Fano “Universidad politécnica Salesiana” 1) UNIVERSIDAD_POLITECNICA_SALESIANA Como primer paso para codificar mediante fano, es necesario calcular la probabilidad de cada símbolo del mensaje como se muestra en la siguiente tabla.

Tabla 1.

Tabla 3.

Como segundo paso se divide en 2 grupos equiprovables en el grupo superior se pone en valor de “0” y en el grupo inferior el valor de “1” como se muestra en la columna 3 de la tabla 2. Después loa s valor que tienen el valor de 1 se reagrupan por segunda vez obteniendo una segunda división como se muestra la columna 2d de la tabla 2. Después se realiza la mismo para la columna de 2d reagrupando y obtenemos los valores de la columna 3d. Tabla 2.

Después procedemos a calcular la eficiencia con la siguiente formula:

𝜂=

𝐻(𝑝) 𝐿

Dónde: 𝑁

1 𝐻(𝑃) = ∑ 𝑃(𝑠𝑖 )log( ) 𝑃(𝑠𝑖 ) 𝑖=1

𝐻(𝑃) = 3.66609 𝑞

𝐿 = ∑ 𝑃𝑖 𝑙𝑖 𝑖=1

𝐿 = 3.69697 𝜂=

𝐻(𝑝) 𝐿

𝜂 = 99.1648% Después obtenemos los valores binarios de cada símbolo de la tabla 2.

Codificación mediante politécnica Salesiana”

Huffman

“Universidad Tabla 5

1) UNIVERSIDAD_POLITECNICA_SALESIANA Tabla 4

En la tabla 4 calculamos la probabilidad de cada símbolo Luego procedemos a diseñar el árbol

En la tabla 5 muestra el código binario de cada símbolo para luego poder transmitirlo Después procedemos a calcular la eficiencia con la siguiente formula:

𝜂=

𝐻(𝑝) 𝐿

Dónde: 𝑁

1 𝐻(𝑃) = ∑ 𝑃(𝑠𝑖 )log( ) 𝑃(𝑠𝑖 ) 𝑖=1

𝐻(𝑃) = 3.66609 𝑞

𝐿 = ∑ 𝑃𝑖 𝑙𝑖 𝑖=1

𝐿 = 3.69697 Figura 1. Codificación Huffman

𝜂=

𝐻(𝑝) 𝐿

𝜂 = 99.1648%

IV.

CONCLUSIONES.

Con la frase planteada en el ejercicio se comprobó que la eficiencia tanto para la codificación mediante Fano es igual a la eficiencia mediante Huffman, la eficiencia en este ejercicio resulto un 99%, que es una eficiencia bastante alta, y la transmisión del código se realizara con éxito. La codificación mediante Huffman es más complejo que la codificación mediante fano.

V.

BIBLIOGRAFIA.

[1] Togneri y Christopher J.S. deSilva, Fundamentals of Information Theory and Coding Desing 2006.