US 5,848,195 AGranted

Selection of huffman tables for signal encoding

AssigneeIntel Corporation

InventorJoseph N. Romriell

Life of this patent

Estimating the term…

Loading patent…

Abstract

Selecting a Huffman table to encode a set of signals, such as video signals, from a set of predefined Huffman tables. A histogram is generated for the set of signals and used to determine the number of bits to encode the set of signals for each of the predefined Huffman tables. The Huffman table that provides the smallest number of bits to encode is selected for encoding the set of signals into the encoded bitstream. In a preferred embodiment, a dynamic Huffman table is also generated for the set of signals and used to estimate the number of bits to encode the set of signals including the number of bits to encode the dynamic Huffman table. If using the dynamic Huffman table results in fewer bits in the encoded bitstream, then the dynamic Huffman table is used (and explicitly encoded in the bitstream) instead of the selected predefined Huffman table.

Claims21

Dependent claims

A computer-implemented process for encoding signals, comprising the steps of:

(a) generating a histogram for a set of signals;
(b) using the histogram to select a Huffman table from a set of two or more pre-defined Huffman tables;
(c) generating a dynamic Huffman table for the set of signals;
(d) using the dynamic Huffman table to determine a number of bits to encode a set of signals using the dynamic Huffman table including a number of bits to encode the dynamic Huffman table;
(e) encoding the set of signals using the dynamic Huffman table, if the number of bits to encode the set of signals using the dynamic Huffman table including the number of bits to encode the dynamic Huffman table is less than the number of bits to encode the set of signals using the selected pre-defined Huffman table;
(f) encoding the set of signals using the selected pre-defined Huffman table, if the number of bits to encode the set of signals using the dynamic Huffman table including the number of bits to encode the dynamic Huffman table is not less than the number of bits to encode the set of signals using the selected pre-defined Huffman table;
and
(g) generating an encoded bit stream from the variable-length encoded signals.

5 more elements

A storage medium encoded with machine-readable computer program code for encoding signals, comprising:

(a) means for causing a computer to generate a histogram for a set of signals;
(b) means for causing the computer to use the histogram to select a Huffman table from a set of two or more pre-defined Huffman tables;
(c) means for causing the computer to generate a dynamic Huffman table for the set of signals;
(d) means for causing the computer to use the dynamic Huffman table to determine a number of bits to encode the set of signals using the dynamic Huffman table including a number of bits to encode the dynamic Huffman table;
(e) means for causing the computer to encode the set of signals using the dynamic Huffman table, if the number of bits to encode the set of signals using the dynamic Huffman table including the number of bits to encode the dynamic Huffman table is less than the number of bits to encode the set of signals using the selected pre-defined Huffman table;
(f) means for causing the computer to encode the set of signals using the selected pre-defined Huffman table, if the number of bits to encode the set of signals using the dynamic Huffman table including the number of bits to encode the dynamic Huffman table is not less than the number of bits to encode the set of signals using the selected pre-defined Huffman table;
and
(g) means for causing the computer to generate an encoded bit stream from the variable-length encoded signals.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/568,021Filed 6 Dec 1995
Granted: 8 Dec 1998
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

H04N 19/149
Data rate or code amount at the encoder output: by estimating the code amount by means of a model, e.g. mathematical model or statistical model
H03M 7/42
Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code: using table look-up for the coding or decoding…
H04N 19/179
Characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the…: the…
H04N 19/61
Using transform coding: in combination with predictive coding