GLAST/LAT >
DAQ and FSW >
FSW >
Doxygen Index >
LDT / V0-4-0
Constituent: encdec Tag: rad750
Interface Data Structures File List Data Fields Globals
_HUFF.dox File Reference
Huffman Encode/Decode, extended documentation. More...
Detailed Description
Huffman Encode/Decode, extended documentation.
- Author:
- JJRussell - russell@slac.stanford.edu
The advent of Google and other such WEB crawlers has led to public exposure of material that was never really meant for such a wide audience. Such as it is with this document. This is the internal documentation generated for use by the GLAST Flight Software team. While we certainly having nothing to hide and Stanford University encourages free access, neither do we have a lot to advertise.
So if you happen to encounter this document when searching the WEB, be advised. While every attempt has been made to be accurate, a document on the WEB, particularly one as informal as this, is not the same as a peer reviewed paper.
Having said that, the basic knowledge for this code came from a WEB site, although, in contrast to this document, the purpose of that site was to educate one about huffman encoding. So giving credit where credit is due, my knowledge of canconical huffman codes came from the site http://www.compressconsult.com/huffman written by Michael Schindler.
It as a good place to both learn and act as a catalyst when adopting huffman encoding to your particular needs.
While huffman encoding has been around a long time and there are numerous implementations, the particular constraints of executing in a realtime flight environment eliminate the use of many of these. In particular, the code must obey the following rules
- Rule: Do not do any on the fly allocation from a global pool, e.g. no mallocs
Rational: This potentially fragments memory and leaves one with the sinking feeling of what to do if the allocation fails.
- Rule: Do not use undue amounts of stack space.
Rational: This is a piece of utility code that could get called from almost any task. Since tasks in an RTOS environment have finite stacks (20Kbytes being typical), a utility that consumes a large amount of stack space could lead to a corruption. This is really a constraint of least surprise. While it helps to document the stack usage of utility, once the utility is buried 3 or 4 call layers deep, it is very unlikely that the caller at the top of the call tree has any direct knowledge of the potential danger lurking below. Best to avoid the problem altogether rather than construct a dangerous piece of code and put out a flashing danger sign.
- Rule: The encode side must be fast.
Rational: This encoder is the basis of much of the on-board compression. Being that is executed by a flight computer that is not particularly fast (equivalent to a 100MHz PPC), and that time in orbit is precious, speed is important.
One of the anti-constraints is that it does not have to be particularly easy to use. The rational for this is that these routines have a very narrow and sophisicated audience. They are experienced in dealing with constraints such as those listed above, so certain demands can be made on them that one would not normally do in such a general purpose utility.
This version eliminates the use of memory allocation and recursive calls, making the HUFF routines OK for use in flight software by bringing it into conformance with the above rules.
Another major change is the switch to using canonical huffman codes. See Canonical Codes.
This implementation limits the maximum possible code length to 27 bits. There are couple of ways one can determine whether your appplication meets this criteria.
- If the number of symbols is less than or equal to 28, then the maximum code length must be less than 27. It is impossible to construct an encoding tree that has more than Nsymbols-1 levels.
- If the sum total of all the entries in the frequency distribution is less than 514229 (the 29th Fibnocci number), then one is assured that no tree deeper than 27 levels may be constructured.
- Of course the 514229 limit demands that the nodes in the tree that results in the course of constructing the table each are a member of the Fibnocci series, so it is very likely that many input distributions with many more entries will also work.
If this proves to be a severe limitation, a future improvement might to rescale the input distribution down until this constraint is meant. This will sacrifice some compression, but make the routines at least function in all cases. My general feeling is that distributions that would cause this implementation of the huffman encoding to choke are likely candidates for another type (e.g. Arithmetic Probability) encoder.
This version uses an internal implementation of a heap sort that does not require allocation from a global heap. In exchange for eliminating memory allocation and recursive calling, the caller is saddled with the responsibility of providing a temporary scratch memory area. Macros, that size the temporary scratch memory are provided.
The temporary scratch space comes in two pieces. The first piece is truly an internal scratch area, that except for its size, is of no interest to the user. The second piece can be thought of in two sections. The first section is precisely the frequency table. The second piece is a piece that must follow contigiously and is of the same size as the frequency table. If the caller chooses, he can specify to the build routines that the frequency table has enough room to accomodate this extra storage. Doing so saves both storage and a copy of the frequency table. The caller is also free to specify that this area plus the area of original frequency distribution can be carved out of the temporary scratch area.
This version also changes the codes to be the canonical codes. For a precise definition of canonical codes, check the literature on huffman encoding. The WEB site listed in the introduction is a good place to start.
Briefly the idea is that, in general, while there are many valid huffman code assignments for a given distribution, the use of one particular set, called the canonical codes, simplifies both the storage of the table and decoding process. The generation of canonical codes and the advantages of using them when decoding are the subject of the next sections.
The generation of the canonical code needs, only the array of symbol lengths. The codes are then assigned by going through the array of lengths, processing each group of symbols by length, starting at the longest and ending with the shortest. After the first symbol with the maximum length is located it is assigned the value 0. The next symbol with the maximum length is assigned the value 1, and so on. After the last symbol with the maximum length is assigned, the first symbol with the next longest length is located. It assigned the current value (the value that would have been assigned to the next maximum length symbol if it had existed) right shifted by 1 (divided by 2). The same procedure is carried up iteratively until all symbols have been processed.
Because the codes can be generated using only the symbol lengths as input, the array of symbol lengths is all that needs to be stored in the output. This means that only log2 (max_sym_size) bits are needed for each symbol. For example if the maximum symbol size is 6 bits, then only a 3 bit number is needed to represent these values. As an optimization on very long arrays of symbol lengths, one could, in turn, encode the symbol lengths, with, for example, a huffman table generated from the table, or another encoder, for example the Arithmetic Probability encoder.
The decoding of canonical huffman codes can be done much more efficiently than the time-honored follow the links down the tree method. Because the codes assigments are dense (i.e. assigned as consecutive integers) within each symbol length, once one determines the length of a given symbol, a simple index operation yields the symbol. The technique used here is to grab the number bits corresponding to the longest symbol from the input stream. A table of values representing the starting code value for each symbol is then searched. Once the correct table is found, it is consulted for a pointer to the beginning of its list of symbols and the number of bits to consume. The base code value is subtracted off the code value and the resulting value shifted down by number of bits associated with this table. The resulting value is used as an index into the table. (Actually in practice, the symbol table pointer is preadjusted by this amount to avoid the subtraction.) This indexing yields the symbol. Again, one consults the table to see how many bits were consumed by this symbol. The appropriate number of bits are removed from the input bit string and refreshed with this many new bits.
The table search can be optimized by observing that there can be at most (in this implementation), 27 tables. This is because the maximum code length is limited to this number. This leads to a search algorithm that efficiently maps the space spanned by something on the order of the maximum code value size to 27. A hashing algorithm would be a good choice. A good choice for a hashing algorithm is one that computes the offset to the first set bit. It is fast (available as a machine instruction in many architectures, While in many codes, this uniquely identifies the table, in general, it does not. So, as with most hash searches, one must provide a list of the possible candidates. Here that list can be efficiently stored and presented as bit array (a single 32-bit integer is sufficient), where each set bit corresponds to a possible table. Thus a Find First Set routine (which, on many machines is available as a single machine instruction), one can perform the hash on the input value and scan the resulting candidate list.
- Note:
- In other implementations, the maximum symbol length may be larger but it is, in general, much smaller than the number of symbols in the dictionary, so that the storage devoted to the lookup table will be small compared to the storage devoted to the symbol dictionary.)
Consider the following example. The first two columns specify the input, that is they give the symbol value (here just a monotonically increassing index) and the number of times that symbol appears in the distribution.
The third column is the number of bits each symbol consumes and is computed (the computational step is not illustrated in this example) from the frequency distribution.
The next three columns show the code assignment algorithm. The starting code value is set to 6 0's, i.e. 000000 and assigned to the first symbol with length 6, i.e. symbol 3.The code value is incremented by 1 to 000001 and assigned to the next symbol of length 6, i.e. symbol 13. The code value is then incremented by 1 again to 000010, but with no more symbols of length 6, it is shiftedright by 1, to 00001, and assigned to the first symbol of length 5, i.e. symbol 4. This process is repeated until all symbols have been assigned a code value.
-
Example: Code Table Construction
| Symbol | Frequency | Length | Size 6 codes | Size 5 codes | Size 4 codes | Size 3 codes |
0 | 11 | 3 | . | . | . | 101 |
1 | 3 | 4 | . | . | 0100 | . |
2 | 3 | 4 | . | . | 0101 | . |
3 | 1 | 6 | 000000 | . | . | . |
4 | 2 | 5 | . | 00001 | . | . |
5 | 5 | 4 | . | . | 0110 | . |
6 | 1 | 5 | . | 00010 | . | . |
7 | 2 | 5 | . | 00011 | . | . |
8 | 6 | 3 | . | . | . | 110 |
9 | 2 | 5 | . | 00100 | . | . |
10 | 4 | 4 | . | . | 0111 | . |
11 | 5 | 3 | . | . | . | 111 |
12 | 3 | 4 | . | . | 1000 | . |
13 | 1 | 6 | 000001 | . | . | . |
14 | 2 | 5 | . | 00101 | . | . | |
15 | 4 | 4 | . | . | 1001 | . |
16 | 3 | 5 | . | 00110 | . | . |
17 | 2 | 5 | . | 00111 | . | . |
The following illustrates the advantages of using canonical codes when doing the decode step. The underlying idea is to take advantage of the fact that the code values for symbols of the same length are dense. Once the length of the symbol associated with present decode string is determined, it is a simple matter of array indexing to recover the symbol.
The process goes as follows
- Construct an array, indexed by the code length, containing two pieces of information
- The starting code value for that code length. Note that for codes less than the maximum code length, right pad code with as many 0's as necessary to reach the maximum code length
- A pointer to the list of symbol values for that symbol length. The order of the array is the order in which the code values where assigned.
- Retrieve the number of bits from the input source corresponding to the maximum code length.
- Using the word defined in Step 2, search the array defined in Step 1, to find which table contains the symbol.
- Form the index into the symbol array associated with this table of code lengths. This is done by first subtracting the base value for codes of this length. This value is either implicitly devired as part of the search routine or can be explicitly stored with the table information. After performing the subtraction, right shift this value down by difference of the maximum code length and the code length associated Use this resulting value as the index into the symbol array.
This section illustrates to construct and use the decoding data structures.
First construct a table of the beginning code values for each symbol length. In general, this array will be from 0 (must be unused since no symbol can have a code length of 0), to the maximum code length. In our example, the code lengths run from 3 - 6. The following table is constructed by looking a Table 1, reading off the starting code values for each of the symbol lengths and then constructing the list of symbols with that symbol length. Note that the base code value has been constructed by always right padding the base code value out to, in this case, 6 bits.
Example: Decoding Structures
| Code Length | Base Code Value | List |
| 6 | 000000 | 3,13 |
| 5 | 000010 | 4,6,7,9,14,16.17 |
| 4 | 010000 | 1,2,5,10,12,15 |
| 3 | 101000 | 0,8,11 |
To illustrate the decoding processing consider the string of bits which would result from encoding the symbols 0-17 in that order
10101000101000000000001011000010000111100010001111111000000001001010011000111
This is the step-by-step prescription for decoding.
- Extract the first 6 bits 101010
- Locate this is the table above, since this value is greater than the base value of symbols with code length 3, the first symbol is within that table.
- Subtract off the base vale, 101010 - 101000 = 010
- Right shift down by 6-3 bits (the maximum code length - the length of this code, 010 >> 3 = 0,
- Use this value to index the array of symbols associated with this table. Since the value of is 0, it is the first element in the the list 0,8,11, i.e. 0.
- Replenish the input stream with three new bits, 010001
- Repeat Step 2. Since 0100001 greater than the base value of symbols with code length 4 (and less than that of symbols with code length 3), it is a code of length 4
- Repeat Step 3, 010001 - 010000 = 000001
- Repeat Step 4, 000001 >> (6-4) = 0
- Repeat Step 5, the symbol is the first of the list 1,2,5,10,12,15 i.e. symbol 1.
- Repeat Step 6, this time stripping the first 4 bits and getting 4 bits more from the input stream 010100
- Repeat Step 2, learning that this is code with length 4.
- Repeat Step 3, 010100 - 010000 = 000100
- Repeat Step 4, 000100 >> 2 = 1
- Repeat Step 5, the symbol is the second in the list 1,2,5,10,12,15 i.e. symbol 2.
- Repeat untill the string is exhausted.
Generated on Fri Jun 19 01:48:02 2009 by
1.5.3
