Example Code Table
Huffman Code Handling
Variable bit Length Coding (VLC) technique is widely used in many data compression algorithms. The CD24x0A DSP carries a special instruction to make a fast decoder for such coding techniques. The VLCD instruction (stands for Variable bit Length Code ? Decoding) makes a very simple yet fast decoding with a special data reference table format. The code table for a VLC needs to be in a standard tree structure data where two numbers are stored in a pair location of RAM1 and RAM0 words that represent two address distances on the table to next tree nodes. Each node has two branches for input code bit either "0" or "1". The VLCD instruction can handle this one bit decoding in one cycle.
Let's see an example of a Huffman decoder program using VLCD instruction.
Suppose you had 4-bit original binary code that was encoded using VLC technique based on the code table Tab.1. This table means your original code "0000" is encoded as "1", "0001" is encoded as "010", "0010" is encoded as "000110" and so on.
The code table in the Tab.1 needs to be stored in the DRAM with the form like Tab.2 so that the VLCD instruction can work properly for decoding of such encoded bit stream. (The data in the Tab.2 are represented in Hex format.)
A component of the DRAM table contains two 16-bit values. For example,
the Table_top + 8 address has the data H = Tt+09 and L = Tt+16.
These values are possible next table addresses. The next address we may need to reference is either Table_top + 9 or Table_top + 16 in this case. The values (H, L) give the absolute next table addresses to reference.
The Tab.2 is showing a binary tree for the Tab.1. When the first bit out of an encoded bit stream comes in, you are at the Table_top of the Tab.2. If the first bit was "1", you can see the Tab.1 to find the first original code was "0000" because all the code that begin with "1" on the encoded bit stream is "0000" only. On the Tab.2, you read the data and get H=Tt+01 and L=Tt+02. As the first bit of the encoded bit stream was "1", you choose H as the new table address. (If the encoded bit come in was "0" you would choose L as the new address.). So, new table data you read at Tt+1 will be H=0, L=0. Now, seeing the L = "0", you find you have reached the end of decoding, and the corresponding original code is found in H, that is "0".
Assuming the incoming bit stream was 010..., you can trace how you decode it with the Tab.2. You go through Table top, Tt+2, Tt+3, then reaches Tt+5 that gives an original code "1".
The CD24x0A DSP can process this tree searching in one cycle at every
node branching as follows.
LD TR,encoded_bit_stream
LDI R0,@Tt //Table Top
LDI R4,@Tt //Table Top
LDSI RC,15
VLCD (R0+),L
LD AH0,(R4)
// The "repeat loop" breaks once a decoding is completed.
// Zero flag is on if decoding is completed.
// A0 will have a decoded code.
// "Repeat" continues one more cycle after a "Break"
is detected.
// Once a decoding is completed, the RAM pointer content stays at the
same value.
// Consumed original code bit count should be placed in part of decoded
code data.
This example program executes one symbol decoding in 14 cycles in the
worst case for the example.
