rss

Artictles

Hi, thanks for visiting this page. Here I write about technology, in-depth analysis of some problems, sport management, among others. If you like these things, you will be glad to read the articles. Also, you can comment or ask questions whenever you want. I will try to respond as soon as possible...

Implementación de la compresión de datos en sistemas de tiempo real Bookmark

En el articulo Compresión de datos en tiempo real se explican muchos de los términos usados en la implementación que se describe en este articulo. Esta implementación esta orientada a señales de electrocardiografía, siendo estas parte de un sistema complejo de tiempo real.

Implementación de la compresión de datos en sistemas de tiempo real

Implementación de los algoritmos FGK y Vitter en C++

En la literatura existen algunas implementaciones de la codificación de Huffman y Huffman adaptiva en varios lenguajes de programación, tales como, PASCAL [1], C [2] [3], C++, C# [4], JAVA [5] [6], entre otros. Sin embargo, estos no están orientados a sistema de tiempo real, como la implementación que se describe a continuación. 

En la siguiente tabla se describen las cuatrpo (4) clases C/C++ creadas para poder realiza la compresión en tiempo real.

 Clases en C++ para la compresión de datos de ECG

Tabla 1. Clases en C++ para la compresión de datos de ECG

Estas clases aceptan datos de 16 bits de longitud, sin importar su procedencia. Vale la pena destacar que la clase CAdaptiveHuffman codifica la primera diferencia, como recomienda los estándares internacionales de almacenamiento de electrocardiografía.

A continuación se muestra el código para la compresión Huffman adaptiva:

   1: // Creamos el archivo donde se almacenaran los datos comprimidos
   2: CFile file(_T("file.bin"), CFile::modeCreate | CFile::modeWrite | File::typeBinary);
   3:  
   4: // Creamos el objeto para la codificación (escritura) usando el algoritmo FGK
   5: CAdaptiveHuffman adaptiveHuffman(&file, CBitStream::write, CAdaptiveHuffmanTree::FGK);
   6:  
   7: // Variable temporal
   8: WORD sample;                        
   9:  
  10: // Ciclo principal de compresor
  11: while (acquisition) {
  12:  
  13: sample = ReadSample();            // Leemos una muestra del MAD
  14:  
  15: adaptiveHuffman.WriteWord(sample);     // Codificación y almacenamiento
  16:  
  17: }

Para la decodificación (o descompresión del archivo) se usa un código similar, el cual se muestra a continuación:

   1: // Abrimos el archivo donde se encuentran los datos comprimidos
   2: CFile file(_T("file.bin"), CFile::modeRead | File::typeBinary);
   3:  
   4: // Creamos el objeto para la decodificación (lectura) usando el algoritmo FGK
   5: CAdaptiveHuffman adaptiveHuffman(&file, CBitStream::read, CAdaptiveHuffmanTree::FGK);
   6:  
   7: // Variables temporales
   8: WORD sample;
   9: int buffer;
  10:  
  11: // Ciclo principal del descompresor
  12: while (visualization) {
  13:  
  14: buffer = adaptiveHuffman.ReadWord();     // Leemos y decodificamos
  15:  
  16:         if(buffer < 0)                // No hay mas muestras en el archivo
  17:             break;
  18:         else
  19:         sample = (WORD)buffer;        // La muestra es valida
  20:  
  21:  VisulizationSample(buffer);            // Visualizamos la muestra
  22:  
  23: }

Métodos y variables de las clases en C++ implementadas

Las clases en C++ se implementaron en Visual C++ .NET (Versión 7.0). Éste posee un visor de clases en el cual, podemos visualizar las clases, sus métodos, sus variables, entre otras características, las cuales, se presentan en forma de árbol y se diferencian por los símbolos que se encuentran a su izquierda. Antes de mostrar con detalle cada clase, es necesario conocer alguno de los símbolos utilizados por el visor de clases de Visual C++ .NET, que se muestran en la siguiente tabla:

Símbolos mas usados en el visor de clases de Visual C++ .NET

Tabla 2. Símbolos mas usados en el visor de clases de Visual C++ .NET

A su vez existen ciertas señales que acompañan a los diferentes símbolos mencionados en la tabla anterior. Estas señales se muestran en la siguiente tabla.

Señales usadas en conjunto con los símbolos del visor de clases de Visual C++ .NET

Tabla 3. Señales usadas en conjunto con los símbolos del visor de clases de Visual C++ .NET

A continuación se muestran las clases implementadas con sus métodos y variables.

Métodos y variables de la clase CAdaptiveHuffman

Figura 1. Métodos y variables de la clase CAdaptiveHuffman

Métodos y variables de la clase CAdaptiveHuffmanTree

Figura 2. Métodos y variables de la clase CAdaptiveHuffmanTree

Métodos y variables de la clase CAdaptiveHuffmanTreeNode

Figura 3. Métodos y variables de la clase CAdaptiveHuffmanTreeNode

Métodos y variables de la clase CBitStream

Figura 4. Métodos y variables de la clase CBitStream

Factores a considerar en la implementación

A continuación se mencionan algunos factores a considerar en la implementación de ambos algoritmos.

El desbordamiento de los pesos

A medida que el programa se ejecuta, los valores de los pesos aumentan. El problema aparece cuando el peso del nodo raíz excede la capacidad del contador en el árbol.

Cuando se actualiza el árbol, se debe revisar el máximo valor. Si sobrepasa un valor límite predeterminado se necesita re-escalar todos los pesos, normalmente dividiendo por un factor fijo, con frecuencia 2.

Al hacer esto es probable que se tenga que reestructurar el árbol para mantener las propiedades de hermandad y de Huffman, dado que en las divisiones se trunca la parte fraccionaria del resultado.

Esto puede producir un cambio en los tamaños de los códigos, debido a que en el proceso de re-escalar se pierde precisión en nuestra base estadística, introduciendo errores en la información.

Mejora al re-escalar los pesos del árbol

Se pierde precisión al re-escalar los pesos, pero se ha comprobado empíricamente que se obtienen mayores factores de compresión al re-escalar periódicamente.

La operación de re-escala tiende a suavizar los efectos de los símbolos más viejos, incrementando la importancia de los símbolos nuevos. Esto parece tener un buen efecto de compresión.

Referencias

  1. J.S. Vitter, ALGORITHM 673, Dynamic Huffman Codes, J. ACM, 1989, Vol. 15, no. 2, pp. 158-167.
  2. Code for use in EECE 641. Pagina Web: http://www.eece.unm.edu/faculty/heileman/641/Sp99/641.html. Fecha de visita: Sábado, 21 de Diciembre de 2002, 09:20:35 a.m.
  3. Josh MacDonald. Pagina Web: http://www.xcf.berkeley.edu/~jmacd. Fecha de visita: Sábado, 21 de Diciembre de 2002, 09:20:35 a.m.
  4. Stephen Toub. Classes for performing Adaptive Huffman Coding (both FGK and modified Vitter algorithm). Email: stoub@microsoft.com. Fecha de consulta: Sábado, 21 de Diciembre de 2002, 09:14:38 a.m.
  5. Adaptive Huffman Compression. Pagina Web: http://www.cs.sfu.ca/cs/CC/365/li/squeeze/AdaptiveHuff.html. Sábado, 21 de Diciembre de 2002, 09:20:55 a.m.
  6. Java-applet. Pagina Web: http://members.lycos.nl/huffman/index.html. Sábado, 21 de Diciembre de 2002, 09:20:35 a.m.
blog comments powered by Disqus