Tips and Tricks (Part 27)

Previous T&T

This T&T deals with the compression of numerical data. Using the proposed algorithm, you will be able to compress a 16 bits unsigned integer (so as to say an uint16_t or an unsigned int data type). into an 8 bits unsigned integer (so as to say an uint8_t or an unsigned char data type). How come ?

Well, this algorithm takes advantage of the principle of operation of integer to float conversion. On completion of the compression algorithm, we get an 8 bits integer from which the 4 most significant bits (msb) contain the exponent and the 4 least significant bits (lsb) contain the mantissa. This arrangement has a drawback: the loss of precision. Next figure illustrates the errors which result from of a compression/decompression cycle:

error_plot

These errors (up to 6%) are the price to pay for compressing data ranging from 0 to 65.535 down to a small compact integer ranging from 0 to 255 that uses only 2 bytes of memory…

Next diagram illustrates the way compression works

compress

and this one illustrates the way decompression works

decompress

These diagrams are inspired by the Application Note AN498 from Silicon Labs, related to the Si114X light sensor.

Next is the code containing the compress and the decompress functions:

/* Compress an unsigned 16 bits integer into an unsigned 8 bits integer */
uint8_t Compress(uint16_t data)
{
	uint8_t res;
	if (data == 0) {
		res = 0x00;
	} else if (data == 1) {
		res = 0x0F;
	} else {
		uint8_t exponent = 15;
		while((data & 0x8000) != 0x8000){
			data <<= 1; /* Shift all bits one step to the left */
			exponent -= 1;
		}
		uint8_t msb = exponent;
		/* Right align and mask the 4 fraction bits  */
		uint8_t lsb = ((data >> 11) & 0x0F);	
		/* Compute result */
		res = ((msb << 4) | lsb);
	}
	/* Returned value */
	return(res);	
}

/* Uncompress an unsigned 8 bits integer into an unsigned 16 bits integer */
uint16_t Uncompress(uint8_t data)
{
	/* Extract bits */
	uint8_t lsb = (data & 0x0F);
	uint8_t msb = ((data >> 4) & 0x0F);
	/* Compute value */
	float fraction = ((float)lsb / 16.0);
	if (msb != 0) {
		/* Applies to compressed 0s and 1s */
		fraction += 1.0;
	}
	float exponent = (1UL << msb);
	uint16_t res = round(exponent * fraction);
	/* Returned value */
	return(res);
}

Note: Please check carefully the way the compressor manages the “0” and “1” values which have special behaviors in the domain of multiplication.

Enjoy !

One Comment

  1. Didier says:

    For the curious who want to get one step further, who do not own a PhD (yet), here is a real nice introduction to Floating Points https://goo.gl/k3ieTb

Leave a Reply

You must be logged in to post a comment.