Generation of huffman tables for signal encoding

Abstract

Generating Huffman tables based on off-line analysis of training sets of signals. Individual Huffman tables are generated for each training set, preferably from an individual histogram representing the training set. The training sets are grouped together, starting with a single group containing all of the training sets. A group Huffman table is generated for each group. A group is selected for splitting and a new Huffman table is generated for a new group. The group to be split is selected by identifying the group that is most inefficiently encoded using a single Huffman table. The new Huffman table is generated by perturbing the group histogram for the group to be split and then generating the new Huffman table from the perturbed histogram. After defining the new Huffman table for the new group, the training sets are redistributed among the existing groups. A training set is moved to a different group if the different group's Huffman table does a better job of encoding that training set than the Huffman table for the training set's old group. After the training sets are redistributed, the group Huffman tables are regenerated. Training-set redistribution is repeated until the redistribution processing converges (e.g., no training sets change groups). Groups are continued to be split until the desired number of group Huffman tables have been generated.