US5650905A — Variable length decoder with adaptive acceleratio…

Claim 1

Independent Claim 270 words

A variable length decoder with adaptive acceleration in processing of an encoded input bit stream, comprising: input means for receiving the input bit stream and for providing a decoding window that includes a sequence of bits which include one or more code words to be decoded at an output thereof; code word length decoding means for determining the combined length of a combination of two or more code words received from said input means in response to a first value of a control signal and for generating a combined length signal representative of the determined combined length, and for determining the length of an individual code word received from said input means in response to a second value of said control signal and for generating an individual word length signal representative of the determined length of said individual code word; computation loop means for receiving said combined length signal or said individual word length signal from said code word length decoding means and, in response thereto, shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input means; code word value decoding means for decoding the values of said combination of two or more code words provided by said input means in response to said first value of said control signal, and for decoding the value of said individual code word in response to said second value of said control signal; and, control means for generating said control signal, and controlling the operation of said variable length decoder according to a decoding protocol.

Claim 2

Dependent Claim 270 words

A variable length decoder with adaptive acceleration in processing of an encoded input bit stream, comprising: input means for receiving the input bit stream and for providing a decoding window that includes a sequence of bits which include one or more code words to be decoded at an output thereof; code word length decoding means for determining the combined length of a combination of two or more code words received from said input means in response to a first value of a control signal and for generating a combined length signal representative of the determined combined length, and for determining the length of an individual code word received from said input means in response to a second value of said control signal and for generating an individual word length signal representative of the determined length of said individual code word; computation loop means for receiving said combined length signal or said individual word length signal from said code word length decoding means and, in response thereto, shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input means; code word value decoding means for decoding the values of said combination of two or more code words provided by said input means in response to said first value of said control signal, and for decoding the value of said individual code word in response to said second value of said control signal; and, control means for generating said control signal, and controlling the operation of said variable length decoder according to a decoding protocol.

Claim 3

Dependent Claim 62 words

The variable length decoder as set forth in claim 1, wherein said code word length computation means includes a combination word length decoder for determining the combined length of said combination of two or more code words received from said input means, and an individual word length decoder for determining the length of said individual code word received from said input means.

Claim 4

Dependent Claim 47 words

The variable length decoder as set forth in claim 2, wherein said two or more code words of said combination of code words are part of a selected group of code words in said input bit stream whose lengths are less than a prescribed number of bits.

Claim 5

Dependent Claim 42 words

The variable length decoder as set forth in claim 3, wherein the combined lengths of all possible combinations of code words of said selected group of code words are stored as entries in a look-up table in said combination word length decoder.

Claim 6

Dependent Claim 50 words

The variable length decoder as set forth in claim 4, wherein said code word value decoding means includes an individual word value decoder for decoding the value of said individual code word, and a combination value decoder for decoding the value of said combination of two or more code words.

Claim 7

Dependent Claim 42 words

The variable length decoder as set forth in claim 5, wherein the combined values of all possible combinations of code words of said selected group of code words are stored as entries in a look-up table in said combination word value decoder.

Claim 8

Dependent Claim 126 words

The variable length decoder as set forth in claim 6, wherein said computation loop means includes: a multiplexer having a first input coupled to said individual word length signal, and a second input coupled to said combined word length signal, wherein said individual word length signal is selected as an output of said multiplexer in response to said first value of said control signal, and said combined word length is selected as said output of said multiplexer in response to said second value of said control signal; and, an adder having a first input coupled to said output of said multiplexer, and a second input coupled to an output of said adder which comprises a word pointer for shifting said decoding window of said input means.

Claim 9

Dependent Claim 44 words

The variable length decoder as set forth in claim 7, wherein said adder generates a carry output for requesting a new sequence of bits from said input bit stream to be loaded into said input means in the event of overflow of said adder.

Claim 10

Dependent Claim 37 words

The variable length decoder as set forth in claim 8, wherein said control means includes a state machine and associated logic circuitry for controlling the operation of the variable length decoder in accordance with said decoding protocol.

Claim 11

Dependent Claim 96 words

The variable length decoder as set forth in claim 9, wherein said control means determines the type and number of the next code words to be processed by said code word length decoding means and said code word value decoding means based upon previously and currently decoded code words, in accordance with said decoding protocol, and generates said control signal in response to this determination, and also generates an additional control signal for selecting proper look-up tables in said code word length decoding means and said code word value decoding means in response to this determination.

Claim 12

Dependent Claim 21 words

The variable length decoder as set forth in claim 10, wherein said input bit stream is a Huffman encoded bit stream.

Claim 13

Dependent Claim 21 words

The variable length decoder as set forth in claim 1, wherein said input bit stream is a Huffman encoded bit stream.

Claim 14

Dependent Claim 37 words

The variable length decoder as set forth in claim 11, wherein said selected group of code words includes all code words in said Huffman encoded input bit stream which have less than said prescribed number of bits.

Claim 15

Dependent Claim 129 words

The variable length decoder as set forth in claim 8, wherein said input means comprises: a first register for receiving said input bit stream, and for outputting a first parallel sequence of input bits; a second register coupled to an output of said first register, and for outputting a second parallel sequence of input bits; a barrel shifter having an input coupled to said first and second parallel sequences of input bits to thereby provide a parallel sequence of available input bits equal in number to the total of said first and second parallel sequences of input bits, and for providing said decoding window at an output thereof; and, wherein said decoding window is shifted in response to said word pointer across said parallel sequence of available input bits.

Claim 16

Dependent Claim 51 words

The variable word length decoder as set forth in claim 14, wherein a new sequence of bits from said input bit stream is loaded into said first register and the contents of said first register are transferred into said second register in response to said carry signal generated by said adder.

Claim 17

Dependent Claim 37 words

The variable length decoder as set forth in claim 15, wherein the bit width of said decoding window is at least equal to the bit length of the maximum length code word in said input bit stream.

Claim 18

Dependent Claim 32 words

The variable length decoder as set forth in claim 16, wherein the bit width of said parallel sequence of available input bits is greater than the bit width of said decoding window.

Claim 19

Dependent Claim 36 words

The variable length decoder as set forth in claim 17, wherein the bit width of said parallel sequence of available input bits is sixty-four bits, and the bit width of said decoding window is thirty-two bits.

Claim 20

Independent Claim 208 words

A method for processing an input bit stream with adaptive acceleration, comprising the steps of: receiving the input bit stream and providing a decoding window that includes a sequence of bits which include one or more code words to be decoded; determining the combined length of a combination of two or more code words in said decoding window in response to a first value of a control signal and generating a combined length signal representative of the determined combined length, and determining the length of an individual code word in said decoding window in response to a second value of said control signal and generating an individual word length signal representative of the determined length of said individual code word; shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input means, in response to said combined length signal or said individual word length signal; and, decoding the values of said combination of two or more code words in said decoding window in response to said first value of said control signal, and decoding the value of said individual code word in response to said second value of said control signal.

Claim 21

Independent Claim 208 words

A method for processing an input bit stream with adaptive acceleration, comprising the steps of: receiving the input bit stream and providing a decoding window that includes a sequence of bits which include one or more code words to be decoded; determining the combined length of a combination of two or more code words in said decoding window in response to a first value of a control signal and generating a combined length signal representative of the determined combined length, and determining the length of an individual code word in said decoding window in response to a second value of said control signal and generating an individual word length signal representative of the determined length of said individual code word; shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input means, in response to said combined length signal or said individual word length signal; and, decoding the values of said combination of two or more code words in said decoding window in response to said first value of said control signal, and decoding the value of said individual code word in response to said second value of said control signal.

Claim 22

Dependent Claim 45 words

The method as set forth in claim 19, wherein said two or more code words of said combination of code words are part of a selected group of code words in said input bit stream whose lengths are less than a prescribed number of bits.

Claim 23

Dependent Claim 46 words

The method as set forth in claim 20, wherein the combined lengths of all possible combinations of code words of said selected group of code words are stored as entries in a look-up table in a combination word length decoder used in performing the determining step.

Claim 24

Dependent Claim 40 words

The method as set forth in claim 21, wherein the combined values of all possible combinations of code words of said selected group of code words are stored as entries in a look-up table used in performing the determining step.

Claim 25

Dependent Claim 19 words

The method as set forth in claim 20, wherein said input bit stream is a Huffman encoded bit stream.

Claim 26

Dependent Claim 34 words

The method as set forth in claim 23, wherein said selected group of code words includes all code words in said Huffman encoded bit stream which have less than said prescribed number of bits.

Claim 27

Dependent Claim 275 words

A variable length decoder with adaptive acceleration in processing of an encoded input bit stream, comprising: an input circuit for receiving the input bit stream and for providing a decoding window that includes a sequence of bits which include one or more code words to be decoded at an output thereof; a code word length decoding circuit for determining the combined length of a combination of two or more code words received from said input circuit in response to a first value of a control signal and for generating a combined length signal representative of the determined combined length, and for determining the length of an individual code word received from said input circuit in response to a second value of said control signal and for generating an individual word length signal representative of the determined length of said individual code word; a computation loop circuit for receiving said combined length signal or said individual word length signal from said code word length decoding circuit and, in response thereto, shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input circuit; a code word value decoding circuit for decoding the values of said combination of two or more code words provided by said input circuit in response to said first value of said control signal, and for decoding the value of said individual code word in response to said second value of said control signal; and, a control circuit for generating said control signal, and controlling the operation of said variable length decoder according to a decoding protocol.

Claim 28

Dependent Claim 275 words

A variable length decoder with adaptive acceleration in processing of an encoded input bit stream, comprising: an input circuit for receiving the input bit stream and for providing a decoding window that includes a sequence of bits which include one or more code words to be decoded at an output thereof; a code word length decoding circuit for determining the combined length of a combination of two or more code words received from said input circuit in response to a first value of a control signal and for generating a combined length signal representative of the determined combined length, and for determining the length of an individual code word received from said input circuit in response to a second value of said control signal and for generating an individual word length signal representative of the determined length of said individual code word; a computation loop circuit for receiving said combined length signal or said individual word length signal from said code word length decoding circuit and, in response thereto, shifting said decoding window to provide a new sequence of bits that include one or more additional code words to be decoded at said output of said input circuit; a code word value decoding circuit for decoding the values of said combination of two or more code words provided by said input circuit in response to said first value of said control signal, and for decoding the value of said individual code word in response to said second value of said control signal; and, a control circuit for generating said control signal, and controlling the operation of said variable length decoder according to a decoding protocol.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2000-07-21	2001-01-20	2001-07-22	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2004-07-21	2005-01-20	2005-07-22	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2008-07-21	2009-01-20	2009-07-22	$7700.00	Window Closed / Lapsed

Variable length decoder with adaptive acceleration in processing of Huffman encoded bit streams

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag