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

234 Chapter 8 Programming in C and C++

The code is rather like Morse code, in that frequently used characters are coded as
short strings of bits, just as the often-used letter "e" is a single dot in Morse code. To
insure that code words are unique and to suggest a decoding strategy, the code is defined
by a tree having two branches at each branching point (binary tree), as shown in Figure
8.4. The letters at each end (leaf) are represented by the pattern of Is and Os along the
branches from the left end (root) to the leaf. Thus, the character string MISSISSIPPI can
be represented by the bit string 111100010001011011010. Note that the ASCII string
would take 88 bits of memory while the Huffman string would take 21 bits. When you
decode the bit string, start at the root, and use each successive bit of the bit string to
guide you up (if 0) or down (if 1) the next branch until you get to a leaf. Then copy the
letter, and start over at the root of the tree with the next bit of the bit string.
A C program for Huffman coding is shown below. The original ASCII character
string is stored in the char vector strng. We will initialize it to the string
MISSISSIPPI for convenience, although any string of M I S and P letters could be
used. The procedure converts this string into a Huffman coded 48-bit bit string stored in
the vector code[ 3 ] . It uses the procedure shift { ) to shift a bit into code. This
procedure, shown after main, is also used by the decoding procedure shown after it.

int code [ 3 ], bitlength; /* output code and its length */

char strng [12] = "MISSISSIPPI"; /* input code, terminated in a NULL */
struct table{ char letter; char charcode[4]; } codetable[4]
1
= { 'SV'XXO", 'I'/'XIO", 'P ,"110",'M',"111" };
void main(){ int row, i; char *point, letter;
for (point=strng; *point ; point++ ){
row = 0; do{
if (((*point) & 0x7f) == codetable[row++].letter){
i = 0; while(i < 3){
letter = codetable{row].charcode[i++];
if (letter != 'X' )
{ shift(); code[2]|=(letters1); bitlength++;}
}
}
} while(row < 4);
}
i- bitlength; while ((i++) <4 8) shift () ; /* shift out unchanged bits */
}

int shift() { int i;
i = (0x8000 & code[0]) == 0x8000; code[0] «= 1;
if (code[l] & 0x8000) code[0]++; codefl] = code[l] «1;
if (code[2] & 0x8000) code[l]++; code[2] - code[2] «1;
return(i);
}