Codificacion Huffman Modificado.docx

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS

IMPLEMENTACION DE UNA MODIFICACION DEL ALGORITMO DE HUFFMAN UTILIZANDO REDES NEURONALES

Autor Ing. William Javier Castillo Gámez Directora Ing. Martha Ruth Ospina

MAESTRÍA EN TELECOMUNICACIONES MÓVILES FACULTAD DE INGENIERÍA Bogotá – Colombia (Agosto– 2018)

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

1

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

Contenido Resumen................................................................................................................................3 Palabras Clave .......................................................................................................................3 Introducción............................................................................................................................4 1.

Planteamiento del Problema ...........................................................................................5

2.

Objetivos .........................................................................................................................6 2.1.

Objetivo General ......................................................................................................6

2.2.

Objetivos Específicos ...............................................................................................6

3.

Justificación ....................................................................................................................7

4.

Delimitación ....................................................................................................................8

5.

Marco Teórico .................................................................................................................9 5.1.

Sistemas de comunicaciones digitales .....................................................................9

5.2.

Codificación de la Fuente .......................................................................................10

5.3.

Compresión de la Información................................................................................11

5.4.

Complejidad en Algoritmos de Compresión sin Pérdidas .......................................12

5.5.

Técnicas de Compresión de Datos.........................................................................14

5.6.

Algoritmos de Compresión .....................................................................................15

5.7.

Comparativo entre Algoritmos ................................................................................18

5.7.1.

Graficas Comparativas de complejidad...............................................................19

5.8. Redes neuronales artificiales .....................................................................................20 6.

Metodología ..................................................................................................................26 6.1.

Cronograma ...........................................................................................................27

Bibliografía ...........................................................................................................................28

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

2

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

Resumen Este trabajo pretende implementar un algoritmo de compresión, que se use en el proceso de codificación de la fuente de información en un sistema de telecomunicaciones, esta implementación incluye una modificación en la estructura de datos manejada en el algoritmo de Huffman, que de forma canónica utiliza un grafo tipo árbol binario para distribuir los caracteres o símbolos de la ráfaga de información a codificar, clasificándolos dependiendo de las frecuencias relativas de aparición; este árbol puede ser reemplazado por una red neuronal que es similar en su estructura a un grafo con pesos en las conexiones, de esta manera lograr entrenar la red neuronal para que encuentre patrones en las ráfagas de información y aumentar la tasa de compresión de la información que se quiere enviar hacia el canal; si se logra reducir el volumen de información, significaría una mejora en el grado de servicio y desempeño de la red de telecomunicaciones aumentando la capacidad sin depender del tipo del canal ni de su ancho de banda.

Palabras Clave Complejidad algorítmica, red neuronal, tasa de compresión, algoritmo Huffman, codificación de la fuente.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

3

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

Introducción La demanda de conectividad por parte de múltiples dispositivos y el aumento del volumen de información que es transmitida por las redes de telecomunicaciones es exponencial, requiriendo canales más robustos que soporten altas tasas de transmisión, incrementando los requisitos funcionales de las redes, este fenómeno se incrementa en las redes dispuestas para dispositivos móviles en canales inalámbricos, que es a lo que apunta la tendencia de uso; con base en lo anterior puede pensarse que la compresión de datos se hace necesaria en los escenarios de las comunicaciones; esta compresión de datos se realiza antes del envió sobre el canal, por lo general en la fuente, para tal fin se usa comúnmente el algoritmo de Huffman, con el que se codifica la información. El algoritmo de Huffman para compresión se aplica en archivos de texto, pero puede aplicarse a cualquier tipo de información si se lleva previamente a una forma digital, donde caracteres o símbolos están codificados en códigos de palabras, que mediante el cálculo de su frecuencia son distribuidos en un grafo tipo árbol binario llamado árbol de Huffman, sin embargo, al aumentar el volumen de información a transmitir o al tratar datos muy heterogéneos, aumentará la cantidad de elementos (nodos) del grafo de Huffman, por lo tanto aumenta la complejidad temporal y operacional del algoritmo, este aumento genera una desventaja en los equipos que hacen uso de la conectividad, debido al incremento de recursos de hardware necesarios y que en dispositivos móviles muchas veces son limitados, también influyen las limitaciones del ancho del canal en el desempeño de la red de comunicaciones. Para tratar de encontrar una solución, las investigaciones hasta la fecha han usado comúnmente la compresión Huffman con redes neuronales utilizando pesos de red cuantificados, los cuales facilitan la transferencia de datos en ráfaga, donde la dispersión y la repetición de los pesos es común, sin embargo, se utiliza la compresión de Huffman por separado en múltiples bloques, cada uno ejecutado por separado en hilos de procesamiento distintos, con lo que se aumenta la complejidad del algoritmo. Según todo lo anterior se puede llegar a implementar una red neuronal que determine los patrones de compresión basado en distribuciones estadísticas y realice directamente la compresión de la información en su forma digital modificando el algoritmo de Huffman, además de esto, se puede intentar modificar la

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

4

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

codificación Huffman convencional con una aplicación directa de una red neuronal que se utilice como estructura de datos en las ponderaciones del grafo, para estudiar su comportamiento y desempeño.

1. Planteamiento del Problema Uno de los aspectos más relevantes en la actualidad, con respecto a las telecomunicaciones es el aumento masivo de la información que se desea transmitir a través de las redes de comunicación, otro aspecto importante es que los equipos electrónicos que hacen uso de tales redes, dejó de ser convergente a un solo tipo de dispositivo para ser una diversa cantidad de objetos que se comunican entre sí y con sus usuarios, ambos factores desencadenan que el volumen y los tipos de información que se transmite, no solo aumente en diversidad, sino también en tamaño, para dar soporte físico a esta demanda de transmisión, los canales deben hacerse más amplios y robustos, sin embargo, esto por sí solo no es suficiente ya que debe ir trabajando en paralelo con la codificación de la información que permite comprimir los datos de su forma natural a una forma que sea más fácil de enviar a su receptor, allí es donde se hace importante la codificación en la fuente, para lograr que el tamaño original de la información se reduzca sin tener pérdidas o distorsión. Se utilizan varios algoritmos para el proceso de codificación, el más utilizado es el algoritmo de Huffman, el cual ha tenido varias modificaciones buscando una tasa más alta de compresión, obteniendo mejoras en los resultados, no obstante, la implementación de redes neuronales directamente en el funcionamiento del algoritmo de Huffman, trazando la red como una representación del grafo de Huffman y estudiar su comportamiento, comparándolo con otros tipos de código podría llevar a encontrar una metodología para compresión de la fuente que permita la transmisión de altos volúmenes de información con una tasa más alta de compresión mejorando el grado de servicio de redes de telecomunicaciones independientemente del canal. ¿Se puede mejorar el grado de servicio de una red de telecomunicaciones al encontrar un método de codificación de la fuente que haga compresión de la información utilizando redes neuronales directamente en la implementación del algoritmo de Huffman?

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

5

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

2. Objetivos 2.1. Objetivo General Crear un método de compresión en la fuente de información utilizando redes neuronales y aplicándolas directamente en la construcción del grafo tipo árbol binario del algoritmo de Huffman. 2.2. Objetivos Específicos Diseñar e implementar una red neuronal que se comporte como la representación de una estructura de datos tipo grafo, con pesos ponderados, para lograr la interacción con ráfagas de información en las entradas. Diseñar e Implementar el algoritmo de Huffman, integrando una red neuronal que reemplace el árbol binario, para codificar información utilizando reconocimiento de patrones en las ráfagas de información. Realizar pruebas del algoritmo utilizando bloques de información de distinta naturaleza para medir la tasa de compresión y tiempo empleado en la ejecución. Evaluar el Algoritmo propuesto mediante la medición de complejidad computacional, realizando comparaciones con otros algoritmos utilizados para el mismo fin.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

6

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

3. Justificación En la actualidad el aumento de usuarios de las redes de telecomunicaciones se ha incrementado de forma exponencial, estos usuarios son diversos dispositivos electrónicos que usan los canales de las redes para transmitir distintos tipos de información, como el número de usuarios sigue aumentando el volumen de información también aumenta; una solución a esta tendencia es la búsqueda de canales con amplios anchos de banda que permitan transmitir mayor cantidad de información en igual o menor tiempo, para mejorar el desempeño de la red, sin embargo la búsqueda de mayores anchos de banda es directamente sobre el canal que por sí mismo presenta limitaciones físicas; otra solución se puede buscar codificando la información antes de ser enviada, comprimiéndola de forma que se transmita una representación más pequeña de los datos, utilizando una parte reducida del ancho del canal, de esta manera se puede enviar mayor cantidad de información en un mismo instante de tiempo. Existen varios algoritmos que se implementan en la fuente de información para codificar y comprimir los datos, pero siempre se está en busca de mejorar las tasas de compresión, ya que, así fuese en un bajo porcentaje, aumentaría significativamente el desempeño de la red, optimizando el uso del ancho del canal. Esto muestra la importancia de la manipulación que se le da a la información que se quiere transmitir en una red de comunicaciones, ya que los canales tienen limitaciones físicas, los algoritmos y métodos de codificación y compresión brindan mejoras en el desempeño de las redes, evidenciándose en su tiempo de respuesta. Este proyecto propone el diseño, implementación y evaluación de un método de compresión de la información directamente en la fuente utilizando el algoritmo de Huffman y la estructura de datos generada por este, modificando el árbol binario por un grafo que será representado mediante una red neuronal, que se entrenará para reconocer patrones basados en la estadística que usa el algoritmo de Huffman. Lo esperado es que la tasa de compresión aumente con respecto a otros algoritmos que se utilizan en el mismo proceso, se debe tener en cuenta también la complejidad computacional que presente el algoritmo en tiempo de ejecución tanto en la codificación como en la decodificación, colocando en una balanza el costo y el

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

7

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

beneficio que arrojaría en las pruebas, buscando mejorar el desempeño de una red de comunicaciones.

4. Delimitación Este trabajo se enmarca en el contexto de los sistemas de comunicaciones digitales, en particular en el proceso de codificación de la fuente; este proceso es el encargado de tomar la información que es generada por una fuente de cualquier tipo y variedad, por ejemplo, señales de radiodifusión, imágenes, audio y video etc. Esta información pasa por una conversión a su forma digital para que sea transmitida, esta codificación utiliza modelos matemáticos basados en probabilidad y procesos estocásticos aplicados a algoritmos de codificación, aquí es donde se centra este trabajo al realizar una implementación de un algoritmo de codificación común como lo es el algoritmo de Huffman, luego hacerle una modificación estructural, para que trabaje con una red neuronal, al trabajar con este algoritmo se medirá su complejidad y desempeño para determinar si la codificación mediante este genera una taza de compresión más alta comparada con otros algoritmos que sean utilizados para el mismo proceso.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

8

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

5. Marco Teórico 5.1. Sistemas de comunicaciones digitales Los sistemas de comunicaciones digital son el modelo utilizado en la actualidad como forma para transmitir información de un sitio a otro, independientemente de la distancia, también independiente del medio o canal de enlace; los sistemas de comunicación digitales toman información de la fuente de origen, la transforman en su forma digital y la transportan a uno o más destinos, para luego pasarla de su forma digital a su forma original[1]; un aspecto importante de las comunicaciones digitales es el que se encarga del tratamiento del canal por el cual se transmitirá la información y los métodos con los que es tratada la información para representarla en sus diferentes formas, digitales, analógicas, este aspecto es importante ya que se debe garantizar que las pérdidas o distorsiones sean mínimas. 5.1.1.

Elementos de las comunicaciones Digitales

Un sistema de comunicaciones, puede representarse, en su nivel más alto de abstracción como un diagrama de bloques funcionales con un orden secuencial; empezando por la fuente, que puede emitir información de cualquier tipo, como: imágenes, video, texto, etc. Esta información puede tener una forma analógica o digital dependiendo de la aplicación que la esté manejando; esta información se puede representar como una señal discreta en el tiempo, conformada por un número finito de caracteres que la definen, puede estar contenida en un mensaje o un bloque de mensajes, estos son convertidos a una secuencia binaria (1,0) de variada longitud; este proceso de tomar la información y convertirla a una cadena binaria se denomina codificación de la fuente (Source Coding), en este proceso se codifica la información, también puede comprimirse o se puede hacer ambos tratamientos sobre la información original[1]. El siguiente paso es llevar la información codificada al medio de transmisión, un proceso de codificación del canal, para luego modular la señal que será enviada por el canal físico, que puede ser un medio cableado o aire en el caso que la comunicación sea inalámbrica. Para que en el receptor la información pueda ser utilizada se sigue la misma secuencia de componentes dentro del sistema, con la diferencia que se hace de forma inversa; William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

9

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

se empieza tomando la señal que se envió por el canal físico, pasarla a un demodulador, luego al de-codificador del canal, después tendrá que decodificarse la cadena de bits de manera que esta decodificación arroje la información original y en su forma natural para que pueda ser interpretada[1].

Figura 1. Elementos básicos de un sistema de telecomunicaciones digitales [2]

5.2. Codificación de la Fuente Los sistemas de comunicación, son diseñados con el propósito, de transmitir información desde la fuente hasta su destino, también debe considerarse muy importante el hecho de que la información puede tomar variedad de formas, un ejemplo de esto es que existen fuentes de información como la televisión (video), las estaciones de radio (voz, música) y dispositivos electrónicos como computadores, celulares etc. Estas fuentes de información pueden ser analógicas o digitales, discretas o continuas [1]. Sin importar el tipo de la fuente de información, en los sistemas de comunicación digital, las señales de información deben convertirse en su forma digital, tarea realizada por el codificador de la fuente [1], en esta parte del proceso, se debe garantizar que la información tenga la cantidad mínima de pérdidas y deformaciones, con el objetivo que en este mismo paso en la decodificación, se obtenga una información muy parecida a la que se envió desde la fuente. Dentro de este proceso de los sistemas de comunicaciones digitales; existen dos enfoques, con propósitos diferentes: el primero es el proceso de convertir la información sin importar su naturaleza de fuente en tramas binarias, y la segunda William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

10

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

consiste en tomar cada trama de símbolos y transformarlos en códigos o claves, para representar la señal de información en un menor espacio, para luego transmitir una representación de la misma información con un menor tamaño, este último proceso es denominado compresión de la información. 5.3. Compresión de la Información. Esta práctica en las comunicaciones digitales es muy útil en el momento de codificar el canal y modular las señales que se transmiten, ya que si se logra transmitir menos cantidad de datos, se usará menos ancho de banda del disponible en el canal y se consumirá menos energía, simplificando la capa física de la red; las tramas en codificación vienen dadas por el sistema digital con que se trabaja y no se puede alterar el número de bits arbitrariamente; por ello, se utiliza la compresión, para transmitir la misma cantidad de información en un número inferior de bits, la compresión es un caso particular de la codificación, cuya característica principal es que el código resultante tiene menor tamaño que el original [3]. La compresión de datos implica la reducción en el número de caracteres transmitidos así mismo la probabilidad de error en la transmisión se reduce, aumentando las prestaciones del sistema. Existen 2 tipos sobre los cuales se clasifican los algoritmos de compresión de datos, son compresión con pérdida y compresión sin pérdida[4]. Un algoritmo de compresión con pérdida se basa en eliminar datos de la señal para reducir el tamaño, con lo que se suele reducir la calidad [2]. En la compresión con pérdida, la tasa de bits (bit rate) puede presentar una longitud constante o variable [5]; una vez realizada la compresión, no se puede obtener la señal original, aunque sí una aproximación cuya semejanza con la original está en función del tipo de compresión. Estos algoritmos se aplican principalmente en la compresión de imágenes, videos y sonidos [6]. Los algoritmos de compresión de datos sin pérdida se caracterizan, por recuperar la señal original partiendo de la señal procesada, con lo que no se tiene una pérdida en la información; la tasa de compresión en este tipo de algoritmos es menor, que en los de compresión con pérdidas, esto debido a los métodos empleados en cada tipo de compresión [7]. William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

11

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

5.3.1.

Compresión sin Pérdidas

La compresión sin pérdidas es un método que permite recuperar información muy parecida a la original, este tipo de compresión es la utilizada para tratar información que no pueda tener distorsiones debido a su aplicación y uso de cara al usuario final[8].

Para realizar la compresión de datos se emplean algoritmos de codificación aplicados en la fuente, que da como resultado la información en su forma digital; existen tres tipos de algoritmos de codificación para compresión de información estos con los: adaptativos, semi-adaptativos y no adaptativos.

Los algoritmos de compresión no adaptativos, son aquellos que tienen asociado una tabla o diccionario de códigos, que representan las cadenas de bits que más se repiten, determinados mediante un estudio estadístico de la información, se divide en tramas de bits, a cada trama se le asigna secuencias más cortas, he irán incrementando su tamaño son proporcionalidad inversa al valor de la probabilidad de ocurrencia[9].

Los algoritmos semi adaptativos, empiezan revisando la cadena completa de información, para luego generar la tabla de códigos, con mucha más precisión y efectividad, logrando mayor compresión, pero empleando mayor tiempo en el procesamiento, debido a que tiene que pasar dos veces por la trama total de información.

Por último, los adaptativos, son algoritmos que sustituyen tramas cortas por tramas más largas que se repiten y así logra reducir el tamaño de la información.

5.4. Complejidad en Algoritmos de Compresión sin Pérdidas Los algoritmos se pueden clasificar no solo porque lleven a cabo la tarea para la que fueron diseñados, también pueden clasificarse en cuanto a los costos de su ejecución; entendiéndose por costo, la cantidad de recursos físicos y temporales que consume

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

12

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

el algoritmo en tiempo de ejecución desde que inicia hasta que termina la tarea, a este indicador se le conoce como medida de la complejidad del algoritmo o también como medida de la eficiencia[10]. 5.4.1.

Análisis de algoritmos

Cuando existen varias soluciones algorítmicas para un mismo problema, se debe escoger aquella que tenga menos complejidad a la hora de utilizarla, esta complejidad toma como referencia dos indicadores de complejidad: la complejidad temporal y la complejidad espacial. El análisis de algoritmos también da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta satisfaga las restricciones de recursos de un problema. 5.4.2.

Complejidad Temporal

Se denomina complejidad temporal a la función T(n) que mide el número de instrucciones realizadas por el algoritmo para procesar los n elementos de entrada. Cada instrucción tiene asociado un costo temporal en unidades de tiempo, normalmente medidas en microsegundos.

El orden en que se procesen los elementos de entrada afecta el costo temporal del algoritmo. Podría considerarse que los valores de los n casos que se presentan como entrada son los correspondientes: a un caso típico, o a un caso promedio, o de peor caso. El peor caso es el más sencillo de definir (el que demore más para cualquier entrada), pero si se desea otros tipos de entrada habría que definir qué se considera típico, o la distribución de los valores en el caso promedio, para los algoritmos de compresión de información los bloques de entrada es la información en su forma digital que se desea comprimir.

5.4.3.

Complejidad Espacial

La complejidad espacial de los algoritmos hace referencia a la cantidad de memoria de procesamiento requerida en tiempo de ejecución, la complejidad espacial, en general, tiene mucho menos interés. El tiempo es un recurso mucho más valioso que el espacio.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

13

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

5.5. Técnicas de Compresión de Datos Existen dos categorías principales de técnicas de compresión de datos: aquellos que utilizan métodos estadísticos y los que requieren del uso de un diccionario de prefijos[8]. Ambas técnicas son muy utilizadas, pero los esquemas basados en diccionario tienden a ser más usados para aplicaciones de compresión de ficheros en máquinas locales, mientras que las situaciones de tiempo real típicamente requieren esquemas de compresión estadísticos[11]. El motivo es que los métodos basados en diccionario tienden a ser lentos en la compresión y más veloces para descomprimir, mientras que los métodos estadísticos son igualmente veloces en ambas operaciones. En el dominio estudiado, la compresión de los datos intenta realizarse con una aproximación de tiempo real, tomando como tiempo real la necesidad de usar el menos tiempo posible para la compresión, él envió y descompresión de los datos, para que puedan ser usados por el receptor, otra forma de explicar esto es que los métodos de compresión estadísticos se usan para comprimir datos que se envían por una red de comunicaciones[8]. Entonces en un proceso de compresión, cada bloque de datos que se comprima eventualmente será descomprimido, la velocidad combinada de compresión y descompresión puede ser tan importante como las velocidades de cada una de estas operaciones por separado[8], por lo que, los algoritmos se clasifican por su complejidad temporal, cantidad de recursos físicos que pueda consumir. 5.5.1.

Métodos Estadísticos

Los esquemas estadísticos de compresión determinan el código de salida basados en la probabilidad de ocurrencia de los símbolos de entrada y son típicamente utilizados en aplicaciones de tiempo real. Como los algoritmos de compresión y descompresión tienden a ser simétricos, la compresión y descompresión usualmente requiere la misma cantidad de tiempo para completarse[12]. 5.5.2.

Métodos con uso de Diccionario de prefijos

La compresión por diccionario no usa modelos de predicción estadística para determinar la probabilidad de ocurrencia de un símbolo particular, sino que almacena cadenas de símbolos de entrada en un diccionario. Estas técnicas son típicamente usadas en aplicaciones de archivos locales, porque el proceso de decodificación William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

14

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

tiende a ser más rápido que el de codificación, además no se tienen limitaciones de recursos como el ancho de banda[13]. 5.6. Algoritmos de Compresión La primera persona que trabajó sobre la información y la forma de transmitirla fue Claude Elwood Shannon; ingeniero estadounidense, padre de la moderna teoría de la información, que es una formulación matemática que analiza las unidades de información (bits) y su pérdida en los procesos de transmisión [3]. Shannon empezó a trabajar sobre el problema de la eficacia de los diferentes métodos existentes de transmisión de la información, tanto mediante el flujo a través de hilos o cables como el aéreo, por medio de corrientes eléctricas fluctuantes o bien moduladas por la radiación electromagnética. Shannon orientó sus esfuerzos hacia la comprensión fundamental del problema y en 1948 desarrolló un método para expresar la información de forma cuantitativa [3]. Las publicaciones de Shannon en 1949 demostraron cómo se podía analizar dicha cuantificación (expresada en una magnitud que denominó bit) mediante métodos estrictamente matemáticos. Así, era posible medir la verosimilitud de la información mutilada por pérdidas de bits, distorsión de los mismos, adición de elementos extraños, etc., y hablar con precisión de términos antes vagos, como «redundancia» (elementos del mensaje que no aportan nueva información, pero se anticipan a posibles pérdidas) o «ruido» (perturbaciones en la comunicación) e, incluso, expresar el concepto físico de entropía como un proceso continuado de pérdida de información [5]. 5.6.1.

Cronología de los Algoritmos de Compresión más Representativos

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

15

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

Esta línea de tiempo relaciona los algoritmos más utilizados en la compresión de datos, con fines en las telecomunicaciones, desde su año de creación hasta el tiempo estimado donde se usaron con mayor aplicabilidad, se puede notar que hay varios algoritmos que hacen parte de grupos con características similares en su funcionamiento, como los LZ, que culminó su evolución en los algoritmos LZW y LZ0, también se puede ver que desde su creación en el año de 1952, el Algoritmo de compresión de Huffman, está aún vigente, una modificación y mejora del algoritmo Huffman son los llamados Huffman Adaptativos. 5.6.2.

Compresión Huffman

El método Huffman es tal vez la técnica más comúnmente utilizada de compresión estadística[14]. Durante el proceso de codificación, este método construye una lista de todos los símbolos de entrada, ordenados en base a sus probabilidades. El algoritmo luego construye un árbol, con un símbolo en cada hoja, y recorre el árbol para determinar los códigos para cada símbolo. Los símbolos con más probabilidad de ocurrencia tienen códigos más cortos. La decodificación utiliza el código para recorrer el árbol hasta llegar al símbolo. La complejidad en el tiempo de una implementación adaptativa de la codificación Huffman es lineal: N (n + log (2n-1)) + Sn, donde N es el número total de símbolos de entrada, n es el número real de símbolos distintos y S es el tiempo requerido para rebalanceo del árbol si fuera necesario[15].

5.6.3.

Codificación Aritmética

Las implementaciones reales de la codificación aritmética son muy similares a las de codificación Huffman, aunque superan a estas últimas en la realidad, el método Huffman asigna un número entero de bits a cada símbolo, mientras que la codificación aritmética asigna un único código extenso a la cadena de entrada completa. Por ejemplo, idealmente a un símbolo con probabilidad 0,4 se le debería asignar un código de 1.32 bits, pero será codificado con 2 bits usando el método Huffman. Es por esta razón que la codificación aritmética tiene el potencial de comprimir datos en el límite teórico. La codificación aritmética combina un modelo estadístico con un paso de William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

16

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

codificación que consiste en algunas operaciones aritméticas. El modelo más sencillo tendría una complejidad temporal lineal de N (log (n) + a) + S n, donde N es el número total de símbolos de entrada, n es el número real de símbolos distintos, a es la aritmética a ser realizada y S es el tiempo requerido, si se necesita, para mantener las estructuras de datos internas [3].

5.6.4.

Modelos basados en el contexto

Prediction with Partial string Matching (PPM) es un modelo estadístico basado en el contexto, muy sofisticado, usado con codificadores aritméticos. La idea es asignar una probabilidad a un símbolo dependiendo no solo de su frecuencia de ocurrencia, sino que también se toma en cuenta la forma en que aparece. PPM intenta mapear el contexto de orden más alto con el símbolo actual. Si no se encuentra una coincidencia, el algoritmo busca un contexto de más bajo orden. Buscar los contextos mencionados puede ser costoso, especialmente si la entrada es muy desestructurada. La complejidad temporal depende de cuantos contextos busca el algoritmo [4]. Como modelo estadístico, Context-Tree Weighting (CTW) es un método para predecir la probabilidad de ocurrencia del próximo símbolo de entrada. El algoritmo examina una cadena de entrada dada y los d bits que la preceden, conocida como el contexto. Se construye un árbol de profundidad D donde cada nodo corresponde a un subnivel del contexto. Luego se examina el próximo bit de la entrada y el árbol es actualizado para agregar el bit a la nueva cadena y usarla para predecir la probabilidad de un contexto. Esta información luego es usada por un codificador aritmético para comprimir los datos. CTW, como PPM alcanza una relación de compresión alta, pero la complejidad temporal depende de la cantidad de contextos que tenga que analizar el algoritmo [4].

5.6.5.

Familia de algoritmos Lempel-Ziv

La codificación Lempel-Ziv y sus muchas variaciones son, probablemente, los métodos más populares de compresión utilizados en aplicaciones de compresión de archivos. La variante más común, LZ77 o Compresión Living Windows, hace uso de una ventana deslizante que consiste en un buffer de búsqueda, o diccionario, y un buffer no comprimido. Una cadena de símbolos es leída del buffer no comprimido, y William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

17

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

se busca una coincidencia con la misma cadena en el buffer de búsqueda. Si se encuentra, se escribe en la salida un índice a la ubicación del Sting en el diccionario. Idealmente, el codificador selecciona la coincidencia más larga disponible en el buffer de búsqueda, aunque esto suele ser configurable ya que condiciona el desempeño del algoritmo, ya que los métodos de compresión Lempel-Ziv requieren tiempo para buscar en el diccionario, la compresión es usualmente mucho más costosa que la descompresión. Muchas técnicas de compresión tienen sus raíces en LZ77 y su sucesor LZ78. Por ejemplo, LZO (Lempel-Ziv-Oberhumer) es una implementación moderna de este algoritmo que tiene una complejidad temporal cuadrática de aproximadamente N (d) donde N es el número total de símbolos de entrada y d es el tamaño del diccionario. Posee algunas características interesantes y por lo tanto es muy utilizada para aplicaciones en entornos embebidos:

5.7. Comparativo entre Algoritmos ALGORITM

TIPO

O

COMPLEJIDAD

COMPLEJIDAD

TAZA DE

RADIO DE

TEMPORAL

ESPACIAL

COMPRESION

COMPRESIO

𝑻𝑻

N

𝑻𝑻 = 𝑂(𝑂) = 𝑂(𝑂 +𝑂𝑂𝑂 𝑂𝑂𝑂 (2𝑂 − 1)) + 𝑂 Huffman

Estadístico

𝑂(𝑂) = 2𝑂 − 1 Donde c es el

Donde n es el número de la

número

entrada de datos y s es el

de nodos en el

tiempo de balanceo del árbol.

árbol de Huffman

Complejidad de Tipo Lineal

Complejidad

𝑻𝑻

𝑻𝑻𝑻%

Aproximadament

0,6940

e 30,6%

máximo

de

Tipo Lineal 𝑂(𝑂) = 𝑂(𝑂𝑂𝑂 𝑂𝑂𝑂 (𝑂) + 𝑂) +𝑂

Aritmética

Estadístico

𝑂(𝑂) = 𝑂𝑂 + 1 Donde c es el

Donde n es el número de la

número

entrada de datos, s es el

de elementos de

tiempo de repaso sobre la

la estructura de

estructura de datos y a es el

datos.

polinomio

Complejidad

aritmético

correspondiente al código.

Aproximadament

0,712

e 35%

máximo

de

Tipo Lineal

Complejidad de Tipo Lineal

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

18

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA Familia de

𝑂(𝑂) = (𝑂2 ) + 2)

Memoria de tipo

Aproximadament

Algoritmos

Donde n es la entrada de

persistente, para

e 40%

datos,

el

Orden cuadrático

almacenamiento

LZ LZ77, LZ78,

Diccionario

LZW, LZO

de

0,1214

los

diccionarios.

Tabla 1. Comparación entre los algoritmos de compresión utilizados en la codificación de la fuente de transmisión, en sistemas de comunicaciones digitales [5], [12], [16], [4]

5.7.1.

Graficas Comparativas de complejidad LZW

Aritmética

ad O(n)

Complejid

Huffman

Volumen de Datos

Grafica 2. Comparativa entre la cantidad de datos codificados contra el nivel de complejidad temporal.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

19

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

LZW

d O(c)

Complejida

Aritmética

Huffman

Volumen de Datos

Grafica 3. Comparativa entre la cantidad de datos codificados contra el nivel de complejidad Espacial.

5.8. Redes neuronales artificiales Una red neuronal artificial (RNA) puede definirse como un sistema de procesamiento de información compuesto por un determinado número de elementos de procesamiento (neuronas), conectados entre sí a través de canales de comunicación denominados sinapsis[17]. Estas conexiones establecen una estructura jerárquica y permiten la interacción, representando las abstracciones del mundo real, estos sistemas computacionales tratan de emular al sistema nervioso biológico. A diferencia de la computación tradicional, basada en algoritmos predecibles, la computación neuronal permite desarrollar sistemas que resuelvan problemas complejos cuya formalización matemática es sumamente difícil [18], esto se logra porque los sistemas que trabajan con RNA tienen características de funcionamiento que permiten un tipo de aprendizaje de máquina, estas características son las siguientes: Aprendizaje adaptativo: esta es quizás la característica más importante de las RNA, ya que pueden comportarse en función de un entrenamiento con una serie de ejemplos ilustrativos. De esta forma, no es necesario elaborar un modelo a priori, ni establecer funciones probabilísticas. Una RNA es adaptativa porque puede William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

20

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

modificarse constantemente con el fin de adaptarse a nuevas condiciones de trabajo[17]. Autoorganización: mientras que el aprendizaje es un proceso donde se modifica la información interna de la RNA, la autoorganización consiste en la modificación de toda la red completa con el fin de llevar a cabo un objetivo específico. Autoorganización significa generalización, de esta forma una red puede responder a datos o situaciones que no ha experimentado antes[18], pero que puede inferir en base a su entrenamiento. Esta característica es muy útil sobre todo cuando la información de entrada es poco clara o se encuentra incompleta[17]. Tolerancia a fallos: en la computación tradicional la pérdida de un fragmento pequeño de información puede acarrear comúnmente la inutilización del sistema. Las RNA poseen una alta capacidad de tolerancia a fallos. La tolerancia a fallos se entiende aquí en dos sentidos: primero, las redes pueden reconocer patrones de información con ruido, distorsión o incompletos (tolerancia de fallos respecto de los datos)[19]; y segundo, pueden seguir trabajando (con cierta degradación) aunque se destruya parte de la red (tolerancia a fallos respecto de la estructura)[20]. La explicación de este fenómeno se encuentra en que, mientras la computación tradicional almacena la información en espacios únicos, localizados y direccionables, las redes neuronales lo hacen de forma distribuida y con un alto grado de redundancia[17]. Operación en tiempo real: de todos los métodos existentes, la RNA son las más indicadas para el reconocimiento de patrones en tiempo real, debido a que trabajan en paralelo actualizando todas sus instancias simultáneamente[21]. 5.8.1.

Estructura de una RNA

Las RNA están compuestas por una serie de elementos de procesamiento o neurona (microestructura).

Conectando

varias

neuronas

de

un

determinado

modo

conseguimos una red (mesoestructura). Existen infinitas variaciones de topologías, pero podemos clasificarlas según los siguientes criterios; primero por el número de niveles o capas, segundo por el número de neuronas por nivel, tercero por las formas de conexión[17].

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

21

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

En cuanto a la cantidad de capas, se puede decir que una red puede estar formada por un mínimo de una capa y un máximo de n capas. Cuando existe una sola capa, esta oficia tanto de entrada como de salida. En el caso de una red de dos capas, la primera será de entrada y la segunda de salida. Para el caso de redes con más de tres capas, la primera será de entrada, la última de salida y las restantes serán las capas ocultas. El número de neuronas por nivel puede variar desde 1 hasta n, y depende de la topología de cada modelo en particular[17]. 5.8.2.

Modelos de RNA

Existen varios modelos diferentes de redes neuronales clasificados por su estructura. Cada una de ellos ha sido diseñado para fines más o menos específicos, lo que quiere decir que en su momento cada modelo fue pensado como la solución particular a un problema específico[22], no obstante, existen varios que han sido aplicados a la solución de diversos problemas distintos, en el siguiente cuadro se muestran los modelos más utilizados en problemas relacionados con las telecomunicaciones[23]: Modelo

Aplicaciones

Características

Limitaciones

Creadores

Teoría de

Reconocimiento de

Es una RNA

Sensible a la

Gail

resonancia

patrones (radar,

sofisticada, poco

translación,

Carperrter,

adaptativa

sonar, y enlaces de

utilizada debido a su

distorsión, escala y

(ART)

satélite.)

gran consumo de

disposición de

Stephen

recursos

recursos de

Grossberg

computacionales[24]

procesamiento[24].

ADALINE/

Filtrado de señales.

Rápida, fácil de

Sólo es posible

Bernard

MADALINE

Ecualizador

implementar con

clasificar espacios

Widrow

adaptativo,

circuitos analógicos.

linealmente

módems, y

separados[26]

codificaciones del canal[25]. Back

Síntesis de voz

La red más popular.

Necesita mucho

Paul Werbos,

Propagation

desde texto.

Numerosas

tiempo para el

David Parker,

Control

aplicaciones con

aprendizaje y

David

de robots.

éxito. Facilidad de

muchos

Rumelhart

Predicción

aprendizaje.

ejemplos[28]

Reconocimiento

Potente, para

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

22

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA de patrones[27]

problemas que necesiten una estructura de datos dinámica y reconocimiento de patrones[23].

Self-

Reconocimiento de

Realiza mapas

Requiere mucho

Teuvo

Organizing-

patrones,

de características

entrenamiento

Kohonon

Map (SOM)

codificación de

comunes de

datos,

los datos

optimización[29]

aprendidos[30]

5.9. Algoritmo de Huffman y las aplicaciones con redes neuronales u otros métodos de inteligencia computacional La utilización del algoritmo de Huffman para realizar la codificación de información es común en las aplicaciones de transmisión de datos, por esta razón, son varias las investigaciones que han abordado los enfoques de compresión de datos en la codificación, no solo con este algoritmo sino con varios de los que ya se hizo mención anteriormente, la tasa compresión de estos algoritmos es cuantificada por el tamaño de la información a la entrada y a la salida del sistema, esto indica el desempeño del proceso de codificación. Al tratarse de un algoritmo que utiliza procesos estocásticos y probabilísticos, este ejecuta procesos iterativos de reconocimiento de cadenas similares en la ráfaga de información, por esta razón se han hecho estudios de cómo utilizar herramientas de la inteligencia artificial para trabajar con el algoritmo de Huffman, sin embargo las investigaciones alrededor de este tema tratan la compresión de datos como bloques independientes donde en hilos separados se ejecuta el algoritmo de codificación y en otro la compresión de la cadena. A continuación, se mencionan algunos de los trabajos más recientes y cercanos al tema de investigación de este trabajo: Convolutional Neural Network Based Synthesized View Quality Enhancement for 3D Video Coding, “Mejora de la calidad de la vista sintetizada basada en una red neuronal convolucional para la codificación de video 3D”. William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

23

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

En este trabajo se hace referencia a una implementación que mejora la codificación de video 3D, para mejorar la eficiencia en la codificación, se utiliza una red neuronal convolucional (CNN), basado en el método de mejora de la calidad de la vista sintetizada, para codificación de video de alta eficiencia 3D (HEVC), se propone, en primer lugar, la eliminación de la distorsión en la vista sintetizada, se formula como una tarea de restauración de la imagen, con el objetivo de reconstruir el latente de la imagen sintetizada sin distorsiones, en donde se utiliza la RNA como predictor y corrector de errores, como pérdida de la información[31]. Modified Huffman based compression methodology for Deep Neural Network Implementation on Resource Constrained Mobile Platforms; “Metodología de compresión basada en una Modificación de Huffman con implementación de redes neuronales de aprendizaje profundo en plataformas móviles con restricciones de recursos” En este trabajo se implementa un RNA particular de aprendizaje profundo (DNN) que producen alta precisión en los resultados de aplicaciones algorítmicas, sin embargo, incurren en altos costos de complejidad computacional y requisitos de memoria, la propuesta que ofrece es una estructura de la RNA trabajando en forma paralela con el algoritmo de Huffman haciendo mejoras para la ejecución en un móvil con recursos limitados llegando a una compresión de datos mejorada, no obstante se trabaja el algoritmo de Huffman independiente de la RNA[32]. The Performance of Text File Compression Using Shannon-Fano and Huffman on Small Mobile Devices; “El rendimiento de la compresión de archivos de texto usando Shannon-Fano y Huffman en dispositivos móviles” Esta investigación realiza una evaluación y comparación de desempeño de los métodos de compresión de Huffman y Shannon- Fano, trabajando sobre dispositivos móviles y su interacción en la transmisión de información de cara a la red a la que se conecte el dispositivo, siendo estas redes de wifi o red móvil 3G, también se realiza el análisis del uso de estas metodologías de compresión en el momento de utilizarlas por aplicaciones que funcionan en estos dispositivos[14].

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

24

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

A Novel Encoding-Decoding Scheme using Huffman Coding for Multimedia Networks; “Un nuevo esquema de codificación y decodificación utilizando la codificación Huffman para redes multimedia” Este trabajo propone un nuevo esquema de codificación que utiliza la codificación Huffman para el cifrado de datos transmitidos a través de una red multimedia. El propósito técnico manipula el código Huffman para tratar datos comprimidos sin cambiar su relación de compresión. La codificación se realiza mediante un proceso de mutación que, en resumen, genera múltiples mutaciones del árbol Huffman intercambiando las ramas del árbol Huffman original[33].

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

25

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

6. Metodología En esta sección se describe la metodología que se usará para llegar al cumplimiento del objetivo general, así como el de los objetivos específicos propuestos en este trabajo. Se mencionan las herramientas de simulación utilizadas en el desarrollo del trabajo y se describen las actividades realizadas en cada objetivo específico. Documentación: Se realizarán actividades de documentación bibliográfica sobre los conceptos fundamentales de las herramientas teóricas que se utilizarán a través del proyecto, con el fin de construir el diseño de la RNA y la modificación del algoritmo de Huffman. Diseño: Se construirán los diseños estructurales y dinámicos del algoritmo de Huffman y su estructura de datos asociada definida por el diseño de la RNA. Implementación: Con los diseños terminados se procederá a la implementación del algoritmo junto a la RNA, para tal fin se hará el desarrollo en herramientas de software especializadas como Matlab y con la utilización de compiladores de lenguaje Java, para extender el proyecto a una posible implementación para dispositivos móviles o similares. Pruebas, evaluación y análisis: Teniendo la implementación del proyecto se harán pruebas utilizando varios tipos de fuentes de información, que se codificarán, midiendo la tasa de compresión del algoritmo y el desempeño del mismo basado en el indicador de complejidad temporal y computacional, de esta manera se podrá comparar con otros métodos de codificación y compresión analizando los resultados arrojados.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

26

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

6.1. Cronograma El cronograma del proyecto se estableció con la técnica de ruta crítica, en la cual se plantearon actividades, que posteriormente se desglosaron para determinar un tiempo de duración optimista, pesimista y esperado, este análisis dio como resultado unas duraciones contemplando holguras, para definir un esquema de trabajo para la investigación.

A B D E F

B C

F F F G

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

ESTIMADO

5

PESIMISTA

4

ESPERADO

3

OPTIMISTA

2

10 12 14 12,00 8 10 12 10,00 4 5 6 5,00 4 5 6 5,00 4 5 6 5,00 2 3 5 3,17 2 3 5 3,17 1 2 4 2,17 6 8 10 8,00 4 6 7 5,83 1 3 4 2,83 36 50 65 50,17

TIEMPOS

VARIANZA

D, C E F F F F H I, J G

1

TIEMPOS Semanas

DESVIACION

Revisión Bibliográfica (ANTEPROYECTO) A Diseño Red Neuronal B Diseño Dinámico del Algoritmo C Diseño de las Estructuras de Datos RNA D Entrenamiento de la Red Neuronal como ED E Diseño estructural del Algoritmo F Implementación Ensamble del algoritmo G Preparación de tramas de datos para las pruebas H Realización de Pruebas I Evaluación y Comparación con otros algoritmos J Conclusiones Cierre del Proyecto K TOTAL, EN SEMANAS

Predecesora

DESCRIPCION DE LAS ACTIVIDADES

Actividad

PREDECESORAS

DU

0,7 0,7 0,3 0,3 0,3 0,5 0,5 0,5 0,7 0,5 0,5 4,8

0,4 0,4 0,1 0,1 0,1 0,3 0,3 0,3 0,4 0,3 0,3 23

12 10 5 5 5 3,2 3,2 2,2 8 5,8 2,8 50

27

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

Bibliografía [1]

B. Sklar, “DIGITAL Fundamentals and Applications,” Ijcnwc, 2013.

[2]

J. G. Proalkis, Digital Comunications. 2009.

[3]

K. Denecker, J. Van Overloop, and I. Lemahieu, “An experimental comparison of several lossless image coders for medical images,” IEEE Conf. 1997. DCC, p. 435, 1997.

[4]

Y. Wiseman, “Compaction of RFID Devices Using Data Compression,” vol. 1, no. 3, pp. 4762–4766, 2018.

[5]

N. Abramson, Teoría de la Información y Codificación. 1981.

[6]

L. Plata, “Compresion transparente para sistemas embebidos,” 2007.

[7]

B. Zhang, Z. Wang, J. Wang, and H. Wang, “and Transmission technology for Structure Healthy Monitoring,” 2017.

[8]

R. P. Tripathi, “Study Of Various Data Compression Techniques Used In Lossless Compression of ECG Signals,” 2018.

[9]

K. Sharma, “Lossless Data Compression Technique With Encryption Based Approach,” pp. 2–6, 2017.

[10] L. S. Cohen and T. Wendling, “Técnicas de diseño,” Técnicas de diseño, pp. 15– 18, 1998. [11] Y. Liu and I. Engineering, “Lossless Compression of Full-Surface Solar Magnetic Field Image Based on Huffman Coding,” pp. 899–903, 2017. [12] J. M. Hurtado, “Simulación y Análisis de Algoritmos de Compresión Empleados en un Sistema de Comunicaciones Digitales .,” vol. 2, pp. 1–10, 2015. [13] Á. Zavala, E. Salvador, E. Salvador, M. Linares, and E. Salvador, “Development of an Application for Data Compression by Using the Huffman Algorithm .,” 2017. [14] T. Mantoro, M. A. Ayu, and Y. Anggraini, “The Performance of Text File Compression Using Shannon-Fano and Huffman on Small Mobile Devices,” 2017. [15] K. M. Shivkumar and N. Kashyap, “A maximization problem related to Huffman William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

28

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

codes,” 2017 23rd Natl. Conf. Commun. NCC 2017, 2017. [16] D. Salomon, Data Compression. 2014. [17] F. de Moya Anegón, V. Herrero Solana, and V. Guerrero Bote, “La aplicación de Redes Neuronales Artificiales (RNA): a la recuperación de la información,” Bibliodoc Anu. Bibl. Doc. i Inf., pp. 147–164, 2007. [18] H. K. Roni, M. Abdul, and G. Khan, “An Artificial Neural Network Based Predictive Approach for Analyzing Environmental Impact on Combined Cycle Power Plant Generation,” 2017 2nd Int. Conf. Electr. Electron. Eng., no. December, pp. 1–4, 2017. [19] J. Zhu, L. Wu, Y. Lu, J. Jiao, and X. Song, “Convolutional Neural Networks Based for High Spectral Dimensional Data Classification,” 2018 IEEE Third Int. Conf. Data Sci. Cybersp., pp. 768–772, 2018. [20] M. Amir and T. Givargis, “Priority Neuron: A Resource-Aware Neural Network for Cyber-Physical Systems,” IEEE Trans. Comput. Des. Integr. Circuits Syst., vol. PP, no. XX, pp. 1–1, 2018. [21] I. Ruban, K. Smelyakov, M. Vitalii, P. Dmitry, and N. Bolohova, “Method of Neural Network Recognition of Ground-based Air Objects,” 2018 IEEE 9th Int. Conf. Dependable Syst. Serv. Technol., pp. 589–592, 2018. [22] W. Li, “Design and Analysis of a Novel Finite-Time Convergent and NoiseTolerant Recurrent Neural Network for Time-Variant Matrix Inversion,” IEEE Trans. Syst. Man, Cybern. Syst., vol. PP, pp. 1–15, 2018. [23] C. V. Regueiro, S. Barro, E. Sánchez, and M. Fernández-Delgado, “Modelos básicos de redes neuronales artificiales,” Computación neuronal. pp. 181–218, 1995. [24] Q. Song, Y. Wu, and Y. C. Soh, “Robust adaptive gradient-descent training algorithm for recurrent neural networks in discrete time domain.,” IEEE Trans. Neural Netw., vol. 19, no. 11, pp. 1841–53, 2008. [25] R. Dogaru, P. Julian, L. O. Chua, and M. Glesner, “The simplicial neural cell and its mixed-signal circuit implementation: An efficient neural-network architecture

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

29

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS FACULTAD DE INGENIERIA

for intelligent signal processing in portable multimedia applications,” IEEE Trans. Neural Networks, vol. 13, no. 4, pp. 995–1008, 2002. [26] A. G. Blanco, “Method to approximate initial values for training lineal neural networks,” Proc. - Electron. Robot. Automot. Mech. Conf. CERMA 2008, pp. 443–446, 2008. [27] U. Saxena, D. Kaushik, M. Bansal, U. Sahu, and D. Bhowmik, “Low-Energy Implementation of Feed-Forward Neural Network With Back-Propagation Algorithm Using a Spin-Orbit Torque Driven Skyrmionic Device,” IEEE Trans. Magn., vol. PP, pp. 1–5, 2018. [28] Z. Zhang, X. Cui, X. Lin, and L. Zhang, “An algorithm of training sample selection for integrated circuit device modeling based on artificial neural networks,” 2016 IEEE Int. Conf. Electron Devices Solid-State Circuits, pp. 314–317, 2016. [29] Y. Shiraishi, K. Hirasawa, J. Hu, and J. Liurata, “Self-organizat ion in Probabilistic Neural Networks,” Neural Networks, pp. 2533–2538, 2000. [30] V. G. Arkhangelsky, S. A. Alyushin, and A. V Alyushin, “Development and Analysis of Analog-Digital Neural Net for Speech Stress Detection,” pp. 1817– 1822, 2018. [31] L. Zhu, Y. Zhang, S. Wang, H. Yuan, S. Kwong, and H. H. S. Ip, “Convolutional Neural Network Based Synthesized View Quality Enhancement for 3D Video Coding,” IEEE Trans. Image Process., vol. PP, no. XX, pp. 1–1, 2018. [32] C. Pal, S. Pankaj, W. Akram, A. Acharyya, and D. Biswas, “Modified Huffman based compression methodology for Deep Neural Network Implementation on Resource Constrained Mobile Platforms,” 2018 IEEE Int. Symp. Circuits Syst., pp. 1–5, 2018. [33] M. R. Usman, M. A. Usman, and S. Y. Shin, “A novel encoding-decoding scheme using huffman coding for multimedia networks,” CCNC 2018 - 2018 15th IEEE Annu. Consum. Commun. Netw. Conf., vol. 2018–Janua, no. 2, pp. 1–6, 2018.

William Javier Castillo Gámez – 2018 – Periodo (1 / 3)

30