Plural-step chunk-at-a-time decoder for variable-length codes of Huffman type

Claim 2

A decoder for variable-length codewords of Huffman type supplied in a codestream having data segments in which each successive codeword comprises a pointer code segment followed by a target code segment, said decoder comprising: selection circuitry for successively selecting chunks of the pointer code segment and the target code segment of each successive variable-length codeword, the beginning of the pointer code segment of a first one of said variable-length codewords being determined responsive to a start of data segment command, and the beginning of the pointer code segment of each further one of said variable-length codewords being determined responsive to the accumulated bit-lengths of the complete variable-length codewords processed by the decoder since said start of data segment command, the beginning of the target code segment of each said variable-length codeword being determined with respect to the beginning of the pointer code segment of that same said variable-length codeword by an indication of the bit-length of the pointer code segment of that same said variable-length codeword; circuitry for generating and temporarily storing first partial memory addresses responsive to respective ones of said pointer code segments as successively selected by said selection circuitry, each said first partial memory address being such as to furnish said indication of the bit-length of the respective one of said pointer codes, each of said first partial memory addresses being temporarily stored while said selection circuitry successively selects the target code segment next after the one of said pointer code segments responsive to which the temporarily stored first partial memory address was generated; circuitry for generating second partial memory addresses responsive to respective ones of said target codes as successively selected by said selection circuitry; first memory addressed by said first and second partial addresses for storing look-up tables of decoder output signal; means for supplying the bit-lengths of just the target code portions of the complete variable-length codewords; and circuitry combining said first partial memory addresses and the bit-lengths of just the target code portions of the complete variable-length codewords for determining the bit-lengths of the complete variable-length codewords.

Claim 3

A decoder as set forth in claim 1, wherein said means for supplying the bit-lengths of just the target code portions of the complete variable-length codewords comprises: second memory addressed by at least portions of said first and second partial addresses for storing the bit-lengths of just the target code portions of the complete variable-length codewords.

Claim 4

A decoder as set forth in claim 1, wherein said means for supplying the bit-lengths of just the target code portions of the complete variable-length codewords comprises: second memory addressed by at least portions of said first partial addresses for storing the bit-lengths of just the target code portions of the complete variable-length codewords.

Claim 5

A decoder as set forth in claim 1, wherein said means for supplying the bit-lengths of just the target code portions of the complete variable-length codewords is simply a wired application of a binary number indicative of the bit length of all said target code portions of the complete variable-length codewords.

Claim 6

A decoder as set forth in claim 1 for decoding variable-length codewords of Huffman type in which each successive codeword comprises a pointer code segment composed of leading ONEs and a final ZERO, said decoder further comprising: circuitry for bit-complementing each non-leading ONE in each successively considered portion of the Huffman codestream to generate a unary signal; and an accumulator used for controlling the selection of the portion of the Huffman codestream to be successively considered and processed during each processing step, during each step of processing pointer code accumulating the sums of the bits of the corresponding unary signal, and during each step of processing target code accumulating the bit-length of the target code.

Claim 7

A decoder as set forth in claim 5, wherein said selection circuitry comprises a shifting apparatus for shifting the successively considered portions of the Huffman codestream, the shift being controlled by accumulated output signal from said accumulator so said shifting apparatus in selected steps of a plural-step operation justifies the leading bit of the pointer code of each Huffman codeword and justifies the leading bit of the target code of each Huffman codeword.

Claim 8

A decoder as set forth in claim 1 for decoding variable-length codewords of Huffman type in which each successive codeword comprises a pointer code segment composed of leading ZEROs and a final ONE, said decoder further comprising: circuitry for bit-complementing each leading ZERO and each ONE in each successively considered portion of the Huffman codestream to generate a unary signal; and an accumulator used for controlling the selection of the portion of the Huffman codestream to be successively considered and processed during each processing step, during each step of processing pointer code accumulating the sums of the bits of the corresponding unary signal, and during each step of processing target code accumulating the bit-length of the target code.

Claim 9

A decoder as set forth in claim 7, wherein said selection circuitry comprises a shifting apparatus for shifting the successively considered portions of the Huffman codestream, the shift being controlled by accumulated output signal from said accumulator so said shifting apparatus in selected steps of a plural-step operation justifies the leading bit of the pointer code of each Huffman codeword and justifies the leading bit of the target code of each Huffman codeword.

Claim 10

A decoder for variable-length codewords of Huffman type supplied in a codestream having data segments in which each successive codeword comprises a pointer code segment with leading ONEs and a final ZERO followed by a target code segment, said decoder comprising: a selector for selecting successive uniform-bit-length portions of said codestream as a selector output signal, selection being in response to a modular count of the bits of a data segment within said codestream, each said uniform-bit-length portion being at least as long as the longest target code segment in any said codeword; an AND gate chain for complementing non-leading ONEs in each uniform-bit-length portion of the codestream selected by said selector, to generate a respective unary signal; adder circuitry for summing the bits of each said unary signal to generate a respective sum signal; a NOR gate responsive to the bits of the current one said sum signals, for detecting when the current one said sum signals is arithmetic zero to generate an indication of a final step in decoding a code word; a first accumulator for accumulating each said respective sum generated by said adder circuitry to generate a first accumulated output signal, said first accumulated output signal being reset to zero arithmetic value responsive to said first accumulator having a first accumulator reset signal applied thereto; first memory addressed by said first accumulated output signal and selected bits of said selector output signal, for storing look-up tables of decoder output signal; second memory for indicating the bit-lengths of just the target code portions of the complete Huffman codes that during the final steps of decoding variable-length code words access decoder output signals stored in said first memory; a two-input, single-output multiplexer receiving said respective sums generated by said adder circuitry as its first input signal, receiving said binary numbers read from said second memory as its second input signal, and selecting one of its first and second input signals as its output signal responsive to a control signal; a second accumulator for accumulating output signal from said multiplexer to generate a second accumulated output signal that controls the selecting by said selector, said second accumulated output signal being reset to zero arithmetic value responsive to said second accumulator having a second accumulator reset signal applied thereto; an output data latch for temporarily storing read-out from said first memory in response to a latching signal; and decoding control circuitry for generating said latching signal during each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, for generating said first accumulator reset signal at the beginning of each data segment and after each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, and for generating said second accumulator reset signal at the beginning of each data segment.

Claim 11

A decoder for variable-length codewords of Huffman type supplied in a codestream having data segments in which each successive codeword comprises a pointer code segment with leading ONEs and a final ZERO followed by a target code segment, said decoder comprising: a selector for selecting successive uniform-bit-length portions of said codestream as a selector output signal, selection being in response to a modular count of the bits of a data segment within said codestream, each said uniform-bit-length portion being at least as long as the longest target code segment in any said codeword; an AND gate chain for complementing non-leading ONEs in each uniform-bit-length portion of the codestream selected by said selector, to generate a respective unary signal; adder circuitry for summing the bits of each said unary signal to generate a respective sum signal; a NOR gate responsive to the bits of the current one said sum signals, for detecting when the current one said sum signals is arithmetic zero to generate an indication of a final step in decoding a code word; a first accumulator for accumulating each said respective sum generated by said adder circuitry to generate a first accumulated output signal, said first accumulated output signal being reset to zero arithmetic value responsive to said first accumulator having a first accumulator reset signal applied thereto; first memory addressed by said first accumulated output signal and selected bits of said selector output signal, for storing look-up tables of decoder output signal; second memory for indicating the bit-lengths of just the target code portions of the complete Huffman codes that during the final steps of decoding variable-length code words access decoder output signals stored in said first memory; a two-input, single-output multiplexer receiving said respective sums generated by said adder circuitry as its first input signal, receiving said binary numbers read from said second memory as its second input signal, and selecting one of its first and second input signals as its output signal responsive to a control signal; a second accumulator for accumulating output signal from said multiplexer to generate a second accumulated output signal that controls the selecting by said selector, said second accumulated output signal being reset to zero arithmetic value responsive to said second accumulator having a second accumulator reset signal applied thereto; an output data latch for temporarily storing read-out from said first memory in response to a latching signal; and decoding control circuitry for generating said latching signal during each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, for generating said first accumulator reset signal at the beginning of each data segment and after each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, and for generating said second accumulator reset signal at the beginning of each data segment.

Claim 12

A decoder as set forth in claim 9, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 13

A decoder as set forth in claim 10, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 14

A decoder as set forth in claim 11, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 15

A decoder as set forth in claim 10, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 16

A decoder as set forth in claim 9, wherein said first and second memories are addressed in parallel, with said second memory addressed by said first accumulated output signal and said selected bits of said selector output signal.

Claim 17

A decoder as set forth in claim 14, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 18

A decoder as set forth in claim 15, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 19

A decoder as set forth in claim 16, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 20

A decoder as set forth in claim 15, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 21

A decoder as set forth in clam 9, wherein said second memory is addressed solely by said first accumulated output signal.

Claim 22

A decoder as set forth in clam 9, wherein said second memory is addressed solely by said first accumulated output signal.

Claim 23

A decoder as set forth in claim 19, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 24

A decoder as set forth in claim 20, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 25

A decoder as set forth in claim 21, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 26

A decoder as set forth in claim 20, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 27

A decoder for variable-length codewords of Huffman type supplied in a codestream having data segments in which each successive codeword comprises a pointer code segment with leading ZEROs and a final ONE followed by a target code segment, said decoder comprising: a selector for selecting successive uniform-bit-length portions of said codestream as a selector output signal, selection being in response to a modular count of the bits of a data segment within said codestream, each said uniform-bit-length portion being at least as long as the longest target code segment in any said codeword; circuitry for bit-complementing each uniform-bit-length portion of the codestream selected by said selector, and an AND gate chain for complementing non-leading ONEs in the resulting signal, to generate a respective unary signal; adder circuitry for summing the bits of each said unary signal to generate a respective sum signal; a NOR gate responsive to the bits of the current one said sum signals, for detecting when the current one said sum signals is arithmetic zero to generate an indication of a final step in decoding a code word; a first accumulator for accumulating each said respective sum generated by said adder circuitry to generate a first accumulated output signal, said first accumulated output signal being reset to zero arithmetic value responsive to said first accumulator having a first accumulator reset signal applied thereto; first memory addressed by said first accumulated output signal and selected bits of said selector output signal, for storing look-up tables of decoder output signal; second memory for indicating the bit-lengths of just the target code portions of the complete Huffman codes that during the final steps of decoding variable-length code words access decoder output signals stored in said first memory; a two-input, single-output multiplexer receiving said respective sums generated by said adder circuitry as its first input signal, receiving said binary numbers read from said second memory as its second input signal, and selecting one of its first and second input signals as its output signal responsive to a control signal; a second accumulator for accumulating output signal from said multiplexer to generate a second accumulated output signal that controls the selecting by said selector, said second accumulated output signal being reset to zero arithmetic value responsive to said second accumulator having a second accumulator reset signal applied thereto; an output data latch for temporarily storing read-out from said first memory in response to a latching signal; and decoding control circuitry for generating said latching signal during each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, for generating said first accumulator reset signal at the beginning of each data segment and after each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, and for generating said second accumulator reset signal at the beginning of each data segment.

Claim 28

A decoder for variable-length codewords of Huffman type supplied in a codestream having data segments in which each successive codeword comprises a pointer code segment with leading ZEROs and a final ONE followed by a target code segment, said decoder comprising: a selector for selecting successive uniform-bit-length portions of said codestream as a selector output signal, selection being in response to a modular count of the bits of a data segment within said codestream, each said uniform-bit-length portion being at least as long as the longest target code segment in any said codeword; circuitry for bit-complementing each uniform-bit-length portion of the codestream selected by said selector, and an AND gate chain for complementing non-leading ONEs in the resulting signal, to generate a respective unary signal; adder circuitry for summing the bits of each said unary signal to generate a respective sum signal; a NOR gate responsive to the bits of the current one said sum signals, for detecting when the current one said sum signals is arithmetic zero to generate an indication of a final step in decoding a code word; a first accumulator for accumulating each said respective sum generated by said adder circuitry to generate a first accumulated output signal, said first accumulated output signal being reset to zero arithmetic value responsive to said first accumulator having a first accumulator reset signal applied thereto; first memory addressed by said first accumulated output signal and selected bits of said selector output signal, for storing look-up tables of decoder output signal; second memory for indicating the bit-lengths of just the target code portions of the complete Huffman codes that during the final steps of decoding variable-length code words access decoder output signals stored in said first memory; a two-input, single-output multiplexer receiving said respective sums generated by said adder circuitry as its first input signal, receiving said binary numbers read from said second memory as its second input signal, and selecting one of its first and second input signals as its output signal responsive to a control signal; a second accumulator for accumulating output signal from said multiplexer to generate a second accumulated output signal that controls the selecting by said selector, said second accumulated output signal being reset to zero arithmetic value responsive to said second accumulator having a second accumulator reset signal applied thereto; an output data latch for temporarily storing read-out from said first memory in response to a latching signal; and decoding control circuitry for generating said latching signal during each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, for generating said first accumulator reset signal at the beginning of each data segment and after each final step in decoding a code word as signaled by said NOR gate for detecting that the current one said sum signals is arithmetic zero, and for generating said second accumulator reset signal at the beginning of each data segment.

Claim 29

A decoder as set forth in claim 24, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 30

A decoder as set forth in claim 25, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 31

A decoder as set forth in claim 26, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 32

A decoder as set forth in claim 25, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 33

A decoder as set forth in claim 24, wherein said first and second memories are addressed in parallel, with said second memory addressed by said first accumulated output signal and said selected bits of said selector output signal.

Claim 34

A decoder as set forth in claim 29, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 35

A decoder as set forth in claim 30, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 36

A decoder as set forth in claim 31, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 37

A decoder as set forth in claim 30, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 38

A decoder as set forth in claim 24, wherein said second memory is addressed solely by said first accumulated output signal.

Claim 39

A decoder as set forth in claim 34, wherein said selector comprises: means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal for N-bit-wide bytes of said codestream; a first N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port; and a funnel shifter having an N-bit-wide output port, having a 2N-bit-wide input port the leading half of which connects from the input port of said first N-bit-wide parallel-in/parallel-out register and the trailing half of which connects from the output port of said first N-bit-wide parallel-in/parallel-out register, and selecting from its input port to its output port in accordance with a binary-number shift command supplied by less significant bits of said second accumulated output signal, N being a plural integer at least one more than the number of bits in the longest of said target codes.

Claim 40

A decoder as set forth in claim 35, wherein said selector further comprises: a second N-bit-wide parallel-in/parallel-out register, having an N-bit-wide input port for receiving an N-bit wide byte of said codestream as clocked thereto in response to said clocking signal, and having an N-bit-wide output port connected to the input port of said first N-bit-wide parallel-in/parallel-out register.

Claim 41

A decoder as set forth in claim 36, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.

Claim 42

A decoder as set forth in claim 35, wherein said means for detecting change in a more significant bit of said second accumulated output signal for generating a clocking signal comprises: means for delaying said more significant bit of said second accumulated output signal by one sample time; and an exclusive-OR gate responsive to said more significant bit of said second accumulated output signal and said more significant bit of said second accumulated output signal as delayed by one sample time.