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.
   247   248   249   250   251   252   253   254   255   256   257