Файл: Programming Microcontrollers in C, 2-nd edit (Ted Van Sickle, 2001).pdf

Data Compression 239

If you look at Figure 5-1, you will note that the letters e, m, and t require only 2 bits each to determine the value. These letters were selected to be represented by 2-bit values because they are the most frequently occurring letters in the message. The remainder of the letters require more bits but they do not occur so often in the message.

l

Figure 5-1: Huffman Code Tree

The code must be designed specifically for the messages to be represented. First, all of the characters in all of the messages are collected into a histogram of the occurrence of each character. Remember to include spaces and other such characters in the list. Once you have determined the number of different characters in the list, you can design a tree that will compress the code. If the list contains n different characters, there will be 2n – 1 nodes in the tree. Each level in the tree, starting from the root node at the zeroth level, can contain 2k nodes or leafs. This tree cannot be balanced like a binary sort tree because we want some of the leafs to be determined by as few as 2 bits, and we do not care about the number of bits needed to determine a character that occurs infrequently. In Figure 5-1, levels 0 and 1 contain only nodes with no leaves. Level 0 contains three leaves and one node. It is through this single node that all of the remainder of the characters must be found.

A series of avionics-related items were put together and an analysis of the frequency of characters in these messages was completed. A Huffman code that will encode these data effectively was created. This

242 Chapter 5 Programming Large 8-Bit Systems

{

if((mask & M[i])==0)

j++; /* use next node entry if bit is zero */ else

j+=Node[j];/*jump to designated node when one */

if(Node[j]<0)

{/* if a printable, send it out */ putchar(k=Node[l]&0x7f);

j=0; /* also go to the root node */

}

if((mask>>=1)==0) /* if the mask is zero,turn on MSB */

{

mask = 0x80;

i++; /* and get the next byte from message */

}

}

}

Listing 5-1: Huffman Decode Function

The next part of the program is the Huffman tree needed to decode the data. This tree was constructed to decode data specifically for the nine messages of this problem. You will note that each byte in the table is a node. Intermixed in the table are numbers that dictate jumps to the next node depending on whether the incoming bit is a zero or a one. The leaves each contain a negative number that is generated by the inclusive OR of the character to be printed and the number 0x80.

The messages are sent to the function decode as a pointer to a bit array. The data must be examined one bit at a time to implement the decoding. The bit selection is accomplished by ANDing the data in the incoming message with the contents of the variable mask. Mask is initially set to 0x80, so the most significant bit of the first byte of the incoming data is selected. Later in the routine, the value of mask will be shifted right to select other bits in the incoming sequence. The variable k is loaded with the character to be output during the program. The linefeed character ‘\n’ was used to determine the end of message, so the decoding sequence will be executed until the

Data Compression 243

character that was output from the program is a ‘\n’. Recall the way that the tree was built. If an incoming bit is 0, the next node in the tree will be taken. If the incoming bit is 1, the content of the current node will be added to the node pointer to determine the next node in the tree. If at any time a negative number is found in the tree, a leaf has been found. The data portion of this byte, bits 0 through 6, will be sent out to the screen.

After each bit is processed, the next bit in the sequence must be processed. The next bit is selected by shifting the mask byte to the right one bit. If the result of this shift creates a zero mask, a new mask with a value of 0x80 is created and the next byte from the incoming message code is selected when i is incremented.

The simple program below causes the nine messages to be printed on the screen:

main()

{

decode(M1);

decode(M2);

decode(M3);

decode(M4);

decode(M5);

decode(M6);

decode(M7);

decode(M8);

decode(M9);

}

Listing 5-2: Message Printing Program

The result of execution of this program is shown below. The nine messages contain 124 characters that would require 992 bits of memory to store the messages in standard ASCII format. The encoded sequence requires 500 bits or 63 bytes of storage.

ALTITUDE

HEADING

DISTANCE REMAINING

FUEL REMAINING

AIR SPEED

244 Chapter 5 Programming Large 8-Bit Systems

IN HOURS

TIME

ESTIMATED TIME OF ARRIVAL

GROUND SPEED

The function below was written to show the difference in memory required for the Huffman code and conventional ASCII coding. This program was compiled as a function to be run on the MC68HC11. The function decode given in Listing 5-1 was compiled to MC68HC11 code. The result of these two compilations showed that Listing 5-1 created an object module that was 255 bytes long, and Listing 5-2 created an object module that was 277 bytes long. The Huffman code for even the small message list in this case provided nearly 10% reduction in code size. A larger message list would provide an even greater memory savings because the code required to decode the messages would be allocated over more message characters to be sent out.

#include <stdio.h> char M1[]=”ALTITUDE”; char M2[]=”HEADING”;

char M3[]=”DISTANCE REMAINING”; char M4[]=”FUEL REMAINING”; char M5[]=”AIR SPEED”;

char M6[]=”IN HOURS”; char M7[]=”TIME”;

char M8[]=”ESTIMATED TIME OF ARRIVAL”; char M9[]=”GROUND SPEED”;

void decode(char *M)

{

while(*M !=0) putchar(*M++);

putchar(‘\n’);

}

Listing 5-3: Nonencoded Output Function

EXERCISES

1.How could the tree in Listing 5-1 be altered to reduce its size by 8 bytes? What effect would this change have on the routine decode? Would there be a net savings in overall code?

Timer Operations 245

2.Do an analysis of a substantial piece of writing and create a Huffman code that will encode the data efficiently. It is recommended that the first three pages of a novel be used for this analysis. Compute the average number of bits per character that this code generates. Hint: you might want to write a program in C for the host com­ puter to calculate the histogram and help create the Huffman codes.

3.Write a program that will implement the above code so that an operator can type the data into a computer and the Huffman code sequences will be generated. You should break the message se­ quences into moderate size bit strings, 500 to 1000 bits, and restart.

4.Create a Huffman tree table as was used in Listing 5-1 to decode the Huffman code developed in Exercise 2.

5.How can you double the number of entries in a Huffman tree by adding only one bit to the code strings?

Timer Operations

The programs written in the earlier sections on sorting and data compression were more computer programs than microcontroller programs. The code written would work on a desktop system or a mainframe computer if needed. In this section, we graduate to true microcontroller programming. The set up of the MC68HC11 family requires that the programmer have a detailed knowledge of the operation of the device. Even though the program is written in a high-level language, it is the responsibility of the programmer to properly set all of the necessary control bits to make the device work as desired. Unfortunately, there are few helpful tools that can guide you through this portion of the program. You must first understand what you want the device to do and then dig through its specifications to find the necessary bits to be set to make it perform as desired. It is highly recommended that prior to an attempt at programming this device that you familiarize yourself with the technical data manual for it as well as the reference manual for the family that is found on the CD-ROM.

The timer subsystem in the MC68HC11 family contains both input capture operations and output compare functions. In this section, we will explore these subsystems associated with the MC68HC11Ex series. The main difference between the Ex series and the other devices lies in the number of output compare and input capture systems on

246 Chapter 5 Programming Large 8-Bit Systems

each device. The Ex series has four output compares, three input captures, and one timer that can be programmed as either output compare or input capture. The other devices have three input captures and five output compares.

Output Compare Subsystems

What does an output compare do? The explanation of the timer subsystem must always begin with the 16-bit timer counter called TCNT that is always counting at some fraction of the system bus frequency. The bus frequency is always one-fourth of the system crystal frequency. The prescaler frequency is set to the bus frequency divided by either 1, 4, 8, or 16 depending on the bits PR1 and PR0 in the register TMSK2. The timer counter register can be read at any time but it cannot be written to. The Output Compare 1 is special. All of the discussion that follows is valid for all output compares, but—as will be shown later— Output Compare 1 has capability beyond the others.

Associated with each output compare system there is a single 16-bit output compare register containing the time that the program needs an event to occur. When TCNT contents matches that of OCx, an OCx event occurs. Note that I say an event, not output. What happens when the contents of the TCNT matches the contents of OCx is up to the program. Associated with each output compare is a pin that can be set, reset, or toggled when an output compare occurs. When an output compare occurs, the corresponding OCxF flag bit is set in the TFLG1 register. This bit can be examined asynchronously by the program to determine whether an output compare has occurred. If the corresponding bit in the TMSK1 register is set when the OCxF flag bit is set, an interrupt will be requested by the part and the event will be processed asynchronously. These are the operations of all output compare subsystems in the part.

There are three input captures, four output compares, and one timer that can be programmed as either an output or an input. This timer is controlled by the I4O5 bit in the PACTL register. When this bit is a zero, the programmable timer is an output compare. Otherwise when the bit is set, the programmable timer is an input capture. Often it is desirable to have an output compare operation be initiated by the completion of another output compare. Output Compare 1 is set up in just this manner. The bits in the OC1M and the OC1D registers control the coupling between the Output Compare 1 and the other

Timer Operations 247

output compare subsystems. When one of the mask bits, say OC1M5, is set in the OC1M and a compare occurs on OC1, in addition to the normal operation that usually occurs when OC1 happens, the contents of the corresponding bit, OC1D5, in the OC1D register is sent to the output compare pin, which in this case is OC3. Completely independent of the operation of OC1, OC3 could be set to toggle at some time. Output Compare 3 could be programmed to be a PWM output where Output Compare 1 establishes the period of the output, and Output Compare 3 establishes the on time.

The applications for use of the coupled output compares are unlimited. An accurate PWM is but one of several. These outputs could be set up to establish an output sequence to drive a stepper motor. The control of acceleration or deceleration of the motor is easily controlled by merely selecting the base time used with OC1.

If you recall, the output compare-based PWM system discussed for the MC68HC05 had several limitations. For example, that system required that the system operate from interrupt service routines. The latency time of interrupt service was so long that the minimum pulse width was considerably longer than one would expect. Also, the interrupt service timing dictated the maximum on time for the pulse, which again was not nearly 100%. Let us look at how we would do a PWM system with the coupled output compare systems.

#include “hc11e9.h”

/* This program will provide a PWM output to OC3, or

PA5. The period will be the integer value found in period, and the on time will be the integer value found in time_on. Keep time_on less than period. */

#define PERIOD 0X1000 #define TIME_ON 0x0800

WORD period=PERIOD, time_on=TIME_ON;

main()

{

OC1M.OC1M7=ON; /* sent OC1 out to PA7 */

248 Chapter 5 Programming Large 8-Bit Systems

OC1M.OC1M5=ON; /* couple OC1 to OC3 */ OC1D.OC1D5=ON; /* turn on OC3 when OC1 occurs */ TCTL1.OL3=ON; /* toggle OC3 when OC3 occurs */ PACTL.DDRA7=ON; /* make OC1 an output to PA7 */ TOC1=TCNT+period; /* set OC1 to the period */ TOC3=TOC1+time_on; /* set OC3 to the time on */ FOREVER

{

if(TFLG1&OC1F)

{

TFLG1=OC1F; /* reset OC1 interrupt flag */ TOC1+=period;

OC1D.OC1D7 ^=ON; /* toggle the output Compare 1 bit */

}

if(TFLG1&OC3F)

{

TFLG1=OC3F;/*reset OC3 interrupt flag */ TOC3=TOC1+time_on;

}

}

}

Listing 5-4: Pulse Width Modulation Routine PWM.C

This routine starts with the inclusion of the header file hc11e9.h. It is created as a main program to demonstrate how it will work, but should be changed to a subroutine later. The period and time_on interval are declared as global variables. They are declared to be the type WORD. WORD is a typedef synonym for the type unsigned int . The main program begins with a series of five initialization instructions. The first two instructions

OC1M.OC1M7=ON;

OC1M.OC1M5=ON;

declare that the output of OC1 should be sent to the outside, which will be to pin PA7, and that whenever OC1 occurs, OC3 through pin PA5 should be activated.