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

354 Chapter 7 Advanced Topics

Here the least significant byte of data is assigned to the smaller ad­ dress and the most significant byte goes to the larger address. Almost all Motorola chips use big endian, and almost all Intel chips use little endian. There can be some confusion when developing code to run on one style of data storage on a machine with the opposite. This problem is seen in the following program.

#include <stdio.h>

main()

{

unsigned array[25]; int i;

numbdup(“123456789098765”,array,25);

for(i=0;i<8;i++)

printf(“%x”,array[i]);

putchar(‘\n’);

}

Listing 7-2: Numeric Encode Test

If this program is compiled with a PC (Intel-based) compiler, the result will not appear to be correct. However, if the program is com­ piled on an HC12, or 68HC16, or 683XX, or 68HC11, or 68HC05 compiler, it will seem to work correctly. In fact, both results are cor­ rect, only the numeric representation in memory is different.

Numeric Decoding

Once the numeric data are encoded and stored, they must be de­ coded to be used by other parts of the program. The decode routine is called putbcd(). This function is shown below.

void putbcd(char *s,char *number)

{

int c,i=0; char *sa; sa=s;

while(*sa!=’\0')

{

Numeric Decoding 355

if(isdigit(c=(*sa>>4)+’0'))

number[i++]=c; else if(c==’0'+0xa)

number[i++]=’0';

if(isdigit(c=(*sa&0xf)+’0'))

number[i++]=c; else if(c==’0'+0xa)

number[i++]=’0';

sa++;

}

number[i++]=’\n’;

number[i++]=0;

}

Listing 7-3: Numeric Decoding Routine

In this function the output data is called number[] and the in­ put is s[]. The encoded data in s[] is converted one BCD 4-bit field at a time to ASCII characters. In the event that a character re­ ceived has a value ‘0’+0xa, it is then a character zero or ‘0’. Each byte is converted from two 4-bit BCD values to two ASCII charac­ ters that represent the proper digits.

The test program for this routine is a combination of the encode test routine with one to decode the encoded data. As one would ex­ pect, when both the encode and the decode routine are used together, the result is correct. This observation is true on either the Intel or the Motorola style chip. The endian-ness of the chip is immaterial when the entire encode/decode operation is completed.

#include <stdio.h> #define ARRAY_SIZE 100

int decode(unsigned M[],char *s);

int encode(char *a,unsigned *array,int length);

main()

{

char a[ARRAY_SIZE] ; int c,i=0;

unsigned array[ARRAY_SIZE]; char s[ARRAY_SIZE];

356 Chapter 7 Advanced Topics

while((c=getchar())!=’\n’)

a[i++]=c;

a[i]=’\n’; encode(a,array,ARRAY_SIZE); decode(array,s); printf(“%s”,s);

}

Listing 7-4: Numeric Decode Test

Coding the alpha data

For encoding and decoding the name data to be stored in our phone book, we will use a Huffman code. We saw the decoding of a Huffman code in Chapter 5 and the decoding approach used here will be almost the same as was used there. In the discussion in Chap­ ter 5 there was no encoding and that feature must be added here. To do justice to the encoding technique, it is necessary to try to build the code to encode the type of text that a phone book represents. There is no reason to suspect that a collection of English names will contain the same character frequency as standard English text. It is necessary to understand the frequency of occurrence of each letter in the text to be encoded. With this understanding, you can write a code that as­ signs few bits to frequently occurring letters and more bits to letters that occur less frequently.

The program below reads in data, counts the occurrences of let­ ters, both upper and lower case, in a document. The occurrence of letters is sorted in order of decreasing occurrence. These data are printed out. The program calculates the average theoretical entropy, bits per character, of each character in the document and displays this number. Also included in the calculations are the space, ‘ ’, char­ acter and the new line, ‘\n’, character. These characters cause the output to be distorted, so the character ‘>’ is used to indicate a space character and a ‘<’ indicates a new line. These data will then be used to create a Huffman code used to compress the data prior to storage in the internal EEPROM.

This particular program, along with many variations, has been an exercise used for years in classes. It does demonstrate some im­ portant considerations. The shell sort was used in Chapters 2 and 5 to sort data, and here we will use it again. In this case, the data to be

360 Chapter 7 Advanced Topics

The purpose of this code is to calculate frequency of occurrence of letters in a document and provide some guidance as to how well the compression approach developed works. This program was run with a ten-page instruction manual and then with a telephone book with 200 entries. The results of these two executions are shown below.

There are 11393 characters

The theoretical average bits per character is 3.797302

Output 7-1: Calculation of entropy for the document manual.doc

The outputs shown above follow very closely the expected occurrence of letters found in the typical technical text. The bits per character should be about 4.5, but this value is distorted because the space character is included in the count, and its very frequent occurrences distort the overall averages and hence the entropy per character found in the document.

Shown below in Output 2 is a repeat of the same calculation on the contents of a phone book. Note here that occurrences of the letters and other characters are quite different from those found above. Even though the phone book used to create the table below contained only about 200 entries, these data will be used to create a Huffman code to compress the data when storing names into the microcomputer EEPROM.

Coding the Alpha Data 361

There are 2488 characters

The theoretical average bits per character is 4.392597

Output 7-2: Calculation of Entropy for Phone Book

Next, a Huffman code will be created to encode the data from the phone book. A Huffman code is built into a complete binary tree. Such a tree always has two descendents from every node unless the node is a leaf node. As such, whenever a Huffman tree is created to encode n characters, there will be 2n–1 nodes in the tree. Figure 7.1 shows an instance of such a tree. This tree encodes the data shown in Output 2 above. As with most trees, analysis, or encoding, starts at the root node at the top of the page. Whenever you traverse to the left, a code value of zero is recorded. When traversing to the right, a code value of 1 is recorded. For example, the character R will be encoded as 0010, and the character M will be 111100. This table is constructed and filled to keep the most frequently occurring letters at the top of the tree and the least frequently occurring letters at the bottom. Therefore, the number of bits for each character is inversely proportional to its frequency of occurrence. This choice for the letter codes requires less than the number of bits one would expect when using the standard 8 bits per character.

362 Chapter 7 Advanced Topics

E

' ' ' \n '

A R O I N L

T H C M S D

B

K

G J Y U P V

F W Z

X Q

Figure 7-1: Huffman Tree for Encoding the Phone Book Data

We have seen above that the minimum number of bits per character for the telephone book is 4.39. We cannot expect to reach this level, but we should expect to be significantly fewer than 8 bits per character. The code corresponding to the tree in Figure 7-1 is shown in the following table:

a0001

b0000111

c000010

d111110

e01

f0000110110

g000011000

Coding the Alpha Data 363

h000001

i1100

j000011001

k1111111

l1110

m111100

n1101

o0011

p111111001

q11111101111

r0010

s111101

t000000

u111111000

v111111010

w0000110111

x11111101110

y000011010

z1111110110

Table 7-1: Huffman Code for CompressingTelephone Book Names

The encoding routine is shown in Listing 7-6. Contained in the listing of the encoding routine is a look-up table that contains all of the codes. In this table, the first two entries correspond to a space character and a new line character. The following entries correspond to the letters in the alphabet. In other words, the third entry corresponds to the letter A and the seventh entry corresponds to the letter E. Notice that this table is defined as external, but it is labeled static so that there is no linkage to the table outside of the file encode.c.

In operation, this function receives three parameters. The first is a pointer to an array that contains the data to be encoded. This array contains a zero terminated string. The second array of unsigned integers is named array. Its length is the third passed parameter length. Encoded data are all loaded into this array. All of the local variables used by encode are straightforward. The variable bitbase is an unsigned int with its most significant bit set to one and the remainder of its bits zero. When the function is executed, the array[] is first filled with zeros. The variable i is initialized