Page 258 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

8,6 An Example 235

Huffman decoding, using the same shift (), is done as follows:

int codefS] = {Oxfll6, OxdOOO, 0}, bitlength = 21; /* input string */
!
1
1
1
char ary[3][2] = {{ S',1},{'I ,2},{'P ,'M }};
char strng[ 20 ]; /* buffer for output characters */
void main(){ int row,entry; char *point;
point=strng; row =0;
while((bitlength—)>=0){
if((entry = ary[row][shift()]) < 0x20) row = entry;
else {row =0; *(point++) = entry &0x7f; }
}
*point = ' \ 0' ; /* terminate C string with NULL character */
;
We suggest that you compile these procedures and step through them using a high-
level debugger. We will discuss each of the features of this program below.
While a for loop can be used for the encoder's outermost, middle, and innermost
loops, we have shown the loops using the different constructs to provide different
examples. Each execution of the encoder's outermost for loop takes a character from
strng. The next inner loop, a do while loop, looks up the character in table, a
vector of structs. When it finds a matching character, the innermost loop, a while
loop, copies the encoded bits into the 48-bit bit vector code.
Bits are stored in the global vector code by the subroutine shift () . The leftmost
16 bits are stored in code [ 0 ], the next 16 bits are stored in code [ 1 ], and the
rightmost 16 bits are stored in code [ 2 ]. shift ( ) shifts the bit vector left, outputting
the leftmost bit. shift( ) first makes local variable i I if the bit vector's most
significant bit is 1, otherwise i is 0 (i is the return value). code[0] is shifted left,
clearing its least significant bit, then code[0] is incremented if code[ l]'s most
significant bit is 1. Note that incrementing shifts the most significant bit of code [ 1 ]
into code [ 0 ]. Then code [ 1 ] is shifted, and then code [ 2 ] is shifted, in like manner.
Observe that the least significant bit of code [ 2 ] is cleared by the last shift. The
encoder procedure, after it calls shif t () , ORs a 1 into this bit if it reads an ASCII
character 1 from the struct table.
The decoder program shifts a bit out of code, for bitlength bits, using
shift( ). This bit is used as an index in the two-dimensional array ary. This array
stores the next node of the tree shown in Figure 8.4. A row of the array corresponds to a
node of the figure, and a column corresponds to an input code bit. The element stored in
this array is an ASCII character to be put in the output buffer string if its value is
above the ASCII code for space (0x20). If it is a character, decoding proceeds next at the
root of the tree, or row zero of the array. Otherwise the value is the node number of the
tree, or row number of the array, where decoding proceeds next.
Now that we have shown how nice the Huffman code is, we must admit a few
problems with it. To efficiently store some text, the text must be statistically analyzed
to determine which letters are most frequent, so as to assign these the shortest codes.
Note that S is most common, so we gave it a short code word. There is a procedure for
generating the best Huffman code, which is presented in many information theory books,
but you have to get the statistics of each letter's occurrences to get that code.