GLAST/LAT > DAQ and FSW > FSW > Doxygen Index > LDT / V0-0-0

Constituent: encdec     Tag: rad750

Interface   Data Structures   File List   Data Fields   Globals  

APM.c File Reference

This builds the modeling table for the Arithmetic Encoder. More...

#include "LDT/APM.h"
#include "APC.h"

Include dependency graph for APM.c:

Include dependency graph

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.

Detailed Description

This builds the modeling table for the Arithmetic Encoder.

Author:
JJRussell - russell@slac.stanford.edu

   CVS $Id: APM.c,v 1.1.1.1 2005/09/23 06:41:07 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.

  1. The encoder writes the modeling table with the data.
  2. The encoder writes the original frequency distribution and, amd the decoder, agrees to use the same rules to transform the frequency table to a modeling table

The minimum transformation would be to simple replace the frequency distribution with the cumulative sum of the frequencies. This scheme has two deficiencies

  1. If the frequency distribution contains symbols with 0 probability of occuring and such symbols appear in an encoding stream, the will effectively be ignored.
  2. Since the cumulative sum of an arbitrary frequency distribution is itself an arbitrary number and the sum is used in a two divisions during the symbol encoding process, the model table is arbirtrarily renormalized such that the sum of the frequencies is precisely a power of 2, thus allowing the division to be replaced by a shift.

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.

Function Documentation

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.

Returns:
The sum of the frequency distribution (not all that interesting)
Parameters:
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.
As a performance hint, symbols that have 0 probability of occurring should not be present in the frequency distribution. In this case, one should define a lookup table mapping only the non-zero values.

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.

Generated on Sat Sep 24 20:30:24 2005 by doxygen 1.3.3