Page 252 - Programming Microcontrollers in C
P. 252
Data Compression 237
The purpose of the above discussion is to demonstrate that the
programmer must exercise much more care in the details of program
design for a microcontroller than is necessary for a larger machine. The
above sorting routine would be of no concern for a typical desktop
machine because RAM is usually of no consideration with such machines.
It might not be a problem for some microcontroller applications, but in
a case where RAM is limited and needed, it might make the difference
between being able to get the program to run or not.
In most instances, the elegance of recursive code has a cost of
RAM. Usually a recursive program will be slower than the equivalent
linear program. The microcontroller programmer must examine each
instance of code to determine if the elegant recursive program has
hidden side effects that end up costing more in computer resources
than is gained in small code size.
EXERCISES
1. Write a program to run on a host computer that will test the time
required to execute both a quick sort and a Shell sort on random
large arrays. Make the array sizes selectable from the keyboard.
2. Test both the quick sort and Shell sort for various array sizes. Ex
amine the time required to execute the sorts for several random
arrays. Explain what is happening when arrays of 4090, 4095, and
4096 entries are sorted.
Data Compression
Another program problem that can arise with microcontroller
applications is handling displays in which there are many phrases
and names each consisting of several letters. The question that must
be considered is the most efficient method of storing these phrases
and names, in memory so that they can be recalled for display. The
oldest, and yet very effective, method of compressing the data for
storage is to use a Huffman code. This code is developed based on
the statistical occurrence of each letter in the alphabet. A letter that
occurs frequently will be given a short code sequence. A letter that is
seen infrequently can be assigned a long code, which will not
appreciably affect the number of bits per letter in the message.