US5748121A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Generation of huffman tables for signal encoding
Assignee: Intel Corp
•
Filing: 1995-12-06
•
Granted: 1998-05-05
•
Expires: 2015-12-06
Abstract
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.
Inventors
- 👤 Joseph N. Romriell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:48
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H04; H04N; H04N19/00; H04N19/10; H04N19/169; H04N19/1883; H04N19/60; H04N19/61; H04N19/63; H04N19/70; H04N19/102; H04N19/13; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
96 words
A computer-implemented process for generating Huffman tables for encoding signals, comprising the steps of: (a) providing a plurality of training sets of signals; (b) defining the plurality of training sets as a group of training sets; (c) generating a group Huffman table corresponding to the group of training sets; (d) generating a new group Huffman table defining an additional group of training sets; (e) redistributing the plurality of training sets among the groups based on the group Huffman tables; and (f) repeating steps (d) and (e) until a desired number of group Huffman tables are generated.
Claim 2
Dependent Claim
96 words
A computer-implemented process for generating Huffman tables for encoding signals, comprising the steps of: (a) providing a plurality of training sets of signals; (b) defining the plurality of training sets as a group of training sets; (c) generating a group Huffman table corresponding to the group of training sets; (d) generating a new group Huffman table defining an additional group of training sets; (e) redistributing the plurality of training sets among the groups based on the group Huffman tables; and (f) repeating steps (d) and (e) until a desired number of group Huffman tables are generated.
Claim 3
Dependent Claim
11 words
The process of claim 1, wherein the signals comprise video signals.
Claim 4
Dependent Claim
65 words
The process of claim 1, wherein: step (a) comprises the steps of: (1) generating an individual histogram for each training set; and (2) generating the individual Huffman table from the individual histogram for each training set; and step (c) comprises the steps of: (1) generating a group histogram for the group of training sets; and (2) generating the group Huffman table from the group histogram.
Claim 5
Dependent Claim
40 words
The process of claim 1, wherein step (d) comprises the steps of: (1) selecting a group to split; (2) perturbing a group histogram for the selected group; and (3) generating the new group Huffman table from the perturbed group histogram.
Claim 6
Dependent Claim
41 words
The process of claim 4, wherein step (d)(1) comprises the steps of: (i) characterizing efficiency with which each group is encoded using a single group Huffman table; and (ii) selecting the group to split as the group having the lowest efficiency.
Claim 7
Dependent Claim
44 words
The process of claim 5, wherein the efficiency is characterized based on a difference in number of bits between encoding the group using the group Huffman table and encoding each training set in the group using the individual Huffman table for the training set.
Claim 8
Dependent Claim
21 words
The process of claim 4, wherein step (d)(2) comprises the step of perturbing the group histogram towards a specified ideal distribution.
Claim 9
Dependent Claim
82 words
The process of claim 1, wherein step (e) comprises the steps of: (1) determining a number of bits for encoding each training set using each group Huffman table; and (2) moving a training set from an old group to a different group if the number of bits to encode the training set using the group Huffman table for the different group is less than the number of bits to encode the training set using the group Huffman table for the old group.
Claim 10
Dependent Claim
51 words
The process of claim 8, wherein step (e)(1) comprises the step of generating, for each training set and each group Huffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
Claim 11
Dependent Claim
43 words
The process of claim 8, wherein step (e) comprises the further step of: (3) generating an updated group Huffman table for each group that changed as a result of steps (e)(1) and (e)(2); and (4) repeating steps (e)(1) to (e)(3) until processing converges.
Claim 12
Dependent Claim
32 words
The process of claim 10, wherein processing converges when the total number of bits required to encode the training sets fails to decrease between consecutive iteration loops through steps (e)(1) to (e)(3).
Claim 13
Dependent Claim
198 words
The process of claim 11, wherein: the signals comprise video signals; step (a) comprises the steps of: (1) generating an individual histogram for each training set; and (2) generating the individual Huffman table from the individual histogram for each training set; step (c) comprises the steps of: (1) generating a group histogram for the group of training sets; and (2) generating the group Huffman table from the group histogram; step (d) comprises the steps of: (1) selecting a group to spit; (2) perturbing a group histogram for the selected group; and (3) generating the new group Huffman table from the perturbed group histogram; step (d)(1) comprises the steps of: (i) characterizing efficiency with which each group is encoded using a single group Huffman table; and (ii) selecting the group to split as the group having the lowest efficiency; step (d)(2) comprises the step of perturbing the group histogram towards a specified ideal distribution; and (e)(1) comprises the step of generating, for each training set and each group Huffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
Claim 14
Independent Claim
107 words
An apparatus for generating Huffman tables for encoding signals, comprising: (a) means for providing a plurality of training sets of signals; (b) means for defining the plurality of training sets as a group of training sets; (c) means for generating a group Huffman table corresponding to the group of training sets; (d) means for generating a new group Huffman table defining an additional group of training sets; (e) means for redistributing the plurality of training sets among the groups based on the group Huffman tables; and (f) means for repeating the processing of means (d) and (e) until a desired number of group Huffman tables are generated.
Claim 15
Independent Claim
107 words
An apparatus for generating Huffman tables for encoding signals, comprising: (a) means for providing a plurality of training sets of signals; (b) means for defining the plurality of training sets as a group of training sets; (c) means for generating a group Huffman table corresponding to the group of training sets; (d) means for generating a new group Huffman table defining an additional group of training sets; (e) means for redistributing the plurality of training sets among the groups based on the group Huffman tables; and (f) means for repeating the processing of means (d) and (e) until a desired number of group Huffman tables are generated.
Claim 16
Dependent Claim
11 words
The apparatus of claim 13, wherein the signals comprise video signals.
Claim 17
Dependent Claim
53 words
The apparatus of claim 13, wherein: means (a): generates an individual histogram for each training set; and generates the individual Huffman table from the individual histogram for each training set; and means (c): generates a group histogram for the group of training sets; and generates the group Hoffman table from the group histogram.
Claim 18
Dependent Claim
33 words
The apparatus of claim 13, wherein means (d): selects a group to split; perturbs a group histogram for the selected group; and generates the new group Huffman table from the perturbed group histogram.
Claim 19
Dependent Claim
35 words
The apparatus of claim 16, wherein means (d): characterizes efficiency with which each group is encoded using a single group Hoffman table; and selects the group to split as the group having the lowest efficiency.
Claim 20
Dependent Claim
44 words
The apparatus of claim 17, wherein the efficiency is characterized based on a difference in number of bits between encoding the group using the group Huffman table and encoding each training set in the group using the individual Huffman table for the training set.
Claim 21
Dependent Claim
17 words
The apparatus of claim 16, wherein means (d) perturbs the group histogram towards a specified ideal distribution.
Claim 22
Dependent Claim
76 words
The apparatus of claim 13, wherein means (e): determines a number of bits for encoding each training set using each group Huffman table; and moves a training set from an old group to a different group if the number of bits to encode the training set using the group Huffman table for the different group is less than the number of bits to encode the training set using the group Huffman table for the old group.
Claim 23
Dependent Claim
47 words
The apparatus of claim 20, wherein means (e) generates, for each training set and each group Hoffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
Claim 24
Dependent Claim
27 words
The apparatus of claim 20, wherein means (e): generates an updated group Huffman table for each group that changed; and repeats its processing until the processing converges.
Claim 25
Dependent Claim
34 words
The apparatus of claim 22, wherein the processing converges when the total number of bits required to encode the training sets fails to decrease between consecutive iteration loops through the processing of means (e).
Claim 26
Dependent Claim
151 words
The apparatus of claim 23, wherein: the signals comprise video signals; means (a): generates an individual histogram for each training set; and generates the individual Huffman table from the individual histogram for each training set; means (c): generates a group histogram for the group of training sets; and generates the group Huffman table from the group histogram; means (d): characterizes efficiency with which each group is encoded using a single group Huffman table; selects a group to split as the group having the lowest efficiency; perturbs the group histogram for the selected group towards a specified ideal distribution; generates the new group Huffman table from the perturbed group histogram; and means (e) generates, for each training set and each group Huffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
Claim 27
Dependent Claim
114 words
A storage medium encoded with machine-readable computer program code for generating Huffman tables for encoding signals, wherein, when executed by a computer, the program code causes the computer to: (a) provide a plurality of training sets of signals; (b) define the plurality of training sets as a group of training sets; (c) generate a group Huffman table corresponding to the group of training sets; (d) generate a new group Huffman table defining an additional group of training sets; (e) redistribute the plurality of training sets among the groups based on the group Huffman tables; and (f) repeat the processing of means (d) and (e) until a desired number of group Huffman tables are generated.
Claim 28
Dependent Claim
114 words
A storage medium encoded with machine-readable computer program code for generating Huffman tables for encoding signals, wherein, when executed by a computer, the program code causes the computer to: (a) provide a plurality of training sets of signals; (b) define the plurality of training sets as a group of training sets; (c) generate a group Huffman table corresponding to the group of training sets; (d) generate a new group Huffman table defining an additional group of training sets; (e) redistribute the plurality of training sets among the groups based on the group Huffman tables; and (f) repeat the processing of means (d) and (e) until a desired number of group Huffman tables are generated.
Claim 29
Dependent Claim
12 words
The storage medium of claim 25, wherein the signals comprise video signals.
Claim 30
Dependent Claim
60 words
The storage medium of claim 25, wherein, when executed by the computer, the program code causes the computer to: generate an individual histogram for each training set; generate the individual Huffman table from the individual histogram for each training set; generate a group histogram for the group of training sets; and generate the group Huffman table from the group histogram.
Claim 31
Dependent Claim
43 words
The storage medium of claim 25, wherein, when executed by the computer, the program code causes the computer to: select a group to split; perturb a group histogram for the selected group; and generate the new Huffman table from the perturbed group histogram.
Claim 32
Dependent Claim
48 words
The storage medium of claim 28, wherein, when executed by the computer, the program code causes the computer to: characterize efficiency with which each group is encoded using a single group Huffman table; Huffman table; and select the group to split as the group having the lowest efficiency.
Claim 33
Dependent Claim
45 words
The storage medium of claim 29, wherein the efficiency is characterized based on a difference in number of bits between encoding the group using the group Huffman table and encoding each training set in the group using the individual Huffman table for the training set.
Claim 34
Dependent Claim
28 words
The storage medium of claim 28, wherein, when executed by the computer, the program code causes the computer to perturb the group histogram towards a specified ideal distribution.
Claim 35
Dependent Claim
87 words
The storage medium of claim 25, wherein, when executed by the computer, the program code causes the computer to: determine a number of bits for encoding each training set using each group Huffman table; and move a training set from an old group to a different group if the number of bits to encode the training set using the group Huffman table for the different group is less than the number of bits to encode the training set using the group Huffman table for the old group.
Claim 36
Dependent Claim
58 words
The storage medium of claim 32, wherein, when executed by the computer, the program code causes the computer to generate, for each training set and each group Huffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
Claim 37
Dependent Claim
38 words
The storage medium of claim 32, wherein, when executed by the computer, the program code causes the computer to: generate an updated group Huffman table for each group that changed; and repeat its processing until the processing converges.
Claim 38
Dependent Claim
35 words
The storage medium of claim 34, wherein the processing converges when the total number of bits required to encode the training sets fails to decrease between consecutive iteration loops through the processing of item (e).
Claim 39
Dependent Claim
155 words
The storage medium of claim 35, wherein: the signals comprise video signals; when executed by the computer, the program code causes the computer to: generate an individual histogram for each training set; generate the individual Huffman table from the individual histogram for each training set; generate a group histogram for the group of training sets; and generate the group Huffman table from the group histogram; characterize efficiency with which each group is encoded using a single group Huffman table; select a group to split as the group having the lowest efficiency; perturb a group histogram for the selected group towards a specified ideal distribution; generate the new group Huffman table from the perturbed group histogram; and generate, for each training set and each group Huffman table, a sum of products of a frequency of occurrence of each signal value times a code length for a group Huffman table variable-length code corresponding to the signal value.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-04 | 2001-11-03 | 2002-05-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-04 | 2005-11-03 | 2006-05-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-04 | 2009-11-03 | 2010-05-05 | $7700.00 | Window Closed / Lapsed |