GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> LDT / dev > encdec / rhel6-32
#include <LDT/APM.h>
#include <APC.h>
Functions | |
unsigned int | APM_build (unsigned int *table, const unsigned int *f, int cnt) |
Creates an appropriately scaled probability table based on the the frequency distribution, f. |
CVS $Id: APM.c,v 1.3 2011/03/25 23:57:13 russell Exp $
The modeling table is the template used to encode symbols. From an organizational viewpoint, it can be used by both the encoding side and the decoding side.
Both sides must agree on how a frequency distribution of symbols is transformed into a modeling table. There are two ways this can be accomplished.
The minimum transformation would be to simple replace the frequency distribution with the cumulative sum of the frequencies. This scheme has two deficiencies
In addressing the first, if the user truly means that a particular symbol has 0 probability of occurring, it should be removed from the frequency table, and some lookup or translation mechanism should be used to translate the original symbol into the symbol to be encoded. This process is a straight-forward and precise prescription.
The second issue is not as straight-forward and precise. Given the limits of integer arthimetic, there are many ways an input frequency distribution can be scaled to sum to a power of 2. Therefore the routine APM_build, by necessity, uses a particular scheme. This scheme was chosen because it is relatively fast in doing the transformation and can be easily shown to converge.
Another point of interest on the building of this table, is that it is not normalized to an arbitrary power of 2, but rather to that power of 2 that, after performing a 32-bit x 32-bit multiple, forces the significant digits to all be in the upper 32-bits. On the PPC, this allows the scaling and division to be replaced by one instruction, the multiple high unsigned word.
unsigned int APM_build | ( | unsigned int * | table, | |
const unsigned int * | f, | |||
int | cnt | |||
) |
Creates an appropriately scaled probability table based on the the frequency distribution, f.
table | The table to be filled out. This must be an array of cnt + 2 values. The first entry is used to hold the number of entries in the table for integrity purposes, and the other extra entry is to hold the sum of the frequencies. | |
f | The frequency distribution of the symbols. There must be one entry, indexed by the symbol value, for each symbol | |
cnt | The number of entries (or the number of symbols, they are equivalent) in f. |
If symbols with a frequency of 0 appear in the input, this code will interpret such symbols as having a small, but finite, possibly of being present in an encoding scheme. Such symbols will be set to the lowest value probability, ensuring that they will get encoded.