US5572209A — Method and apparatus for compressing and decompre…

Claim 1

Independent Claim 155 words

An apparatus for processing compressed, variable length data items in a data compression system, said apparatus comprising: code storing means for storing variable length code items, each code item representing a corresponding variable length data item and comprising a corresponding number of code bits which are within one of a predetermined number of possible variable length code cases; means for decoding said stored code bits and outputting a signal identifying a length case within one of said possible variable length code cases; means for concurrently generating the sums of the number of code bits in each of said variable length code bit cases and a starting address of a first code item in order to generate a plurality of possible starting addresses for a second code item; and means for selecting one of said plurality of possible starting addresses for said second code item on the basis of the signal output by said decoding means.

Claim 2

Independent Claim 155 words

An apparatus for processing compressed, variable length data items in a data compression system, said apparatus comprising: code storing means for storing variable length code items, each code item representing a corresponding variable length data item and comprising a corresponding number of code bits which are within one of a predetermined number of possible variable length code cases; means for decoding said stored code bits and outputting a signal identifying a length case within one of said possible variable length code cases; means for concurrently generating the sums of the number of code bits in each of said variable length code bit cases and a starting address of a first code item in order to generate a plurality of possible starting addresses for a second code item; and means for selecting one of said plurality of possible starting addresses for said second code item on the basis of the signal output by said decoding means.

Claim 3

Dependent Claim 109 words

A processing apparatus as set forth in claim 1 further comprising: data item storing means for storing variable length data items, said data item storing means having a plurality of addresses and being of a predetermined size, wherein each data item necessarily has an actual length value, said actual length value being within one of a predetermined number of possible length cases and being represented by code bits which are within one of said predetermined number of possible variable length code cases; and wherein the number of code bits provided for each code case by said concurrent generating means relates to the size of said data item storing means.

Claim 4

Dependent Claim 69 words

A processing apparatus as set forth in claim 1 further comprising: code length storing means for storing each of said variable length possibilities and outputting a plurality of said possibilities in parallel; adder means for receiving each of said outputted variable length possibilities and said starting address for a first code item, said adder means providing in parallel said plurality of possible starting addresses for said second code item.

Claim 5

Independent Claim 216 words

An apparatus for processing a plurality of sequentially arranged compressed code tokens representing original data, each code token having one of a plurality of possible variable lengths and comprising compression information and code length information, said apparatus comprising: a) means for storing code tokens, said means being of sufficient size to store each of a first code token and a second code token, each said stored tokens being any one of said possible variable lengths; b) means for aligning said stored code tokens for providing aligned storage locations for said first and second code tokens irrespective of code token length; c) means for decoding said code length information for said first stored code token and identifying one of said plurality of code lengths; d) means for providing a current address, said current address being used to determine the location of said first code token in said token storing means; e) means for concurrently providing all of said plurality of possible variable code length values; f) means responsive to said plurality of possible variable code length values and said current address for generating a plurality of possible next addresses for said second code token; and g) means responsive to said decoding means for selecting a next address in said token storing means for said second code token.

Claim 6

Independent Claim 216 words

An apparatus for processing a plurality of sequentially arranged compressed code tokens representing original data, each code token having one of a plurality of possible variable lengths and comprising compression information and code length information, said apparatus comprising: a) means for storing code tokens, said means being of sufficient size to store each of a first code token and a second code token, each said stored tokens being any one of said possible variable lengths; b) means for aligning said stored code tokens for providing aligned storage locations for said first and second code tokens irrespective of code token length; c) means for decoding said code length information for said first stored code token and identifying one of said plurality of code lengths; d) means for providing a current address, said current address being used to determine the location of said first code token in said token storing means; e) means for concurrently providing all of said plurality of possible variable code length values; f) means responsive to said plurality of possible variable code length values and said current address for generating a plurality of possible next addresses for said second code token; and g) means responsive to said decoding means for selecting a next address in said token storing means for said second code token.

Claim 7

Dependent Claim 54 words

The processing apparatus as set forth in claim 4 wherein said length providing means comprises fixed length means for generating a predetermined plurality of variable fixed length values, and a plurality of adder means each for receiving a current address value and corresponding variable address size for generating a plurality of possible next addresses.

Claim 8

Dependent Claim 27 words

The processing apparatus as set forth in claim 4 wherein said alignment means comprises a barrel shifter memory operative to receive each of said code tokens separately.

Claim 9

Dependent Claim 19 words

The processing apparatus as set forth in claim 6 wherein said barrel shifter memory provides left-adjustment for received tokens.

Claim 10

Dependent Claim 35 words

The processing apparatus as set forth in claim 4 further comprising means for receiving at least part of each variable length code token and assembling said parts in said storage means as a complete token.

Claim 11

Dependent Claim 37 words

The processing apparatus as set forth in claim 4 further comprising means for determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.

Claim 12

Dependent Claim 30 words

The processing apparatus as set forth in claim 9 further comprising output means for storing an entire adjusted code word from said adjusting means in response to said determining means.

Claim 13

Dependent Claim 37 words

The processing apparatus as set forth in claim 10 further comprising means responsive to said current address and available segment data for delaying the introduction of a new code token until a current code token is decompressed.

Claim 14

Dependent Claim 172 words

A data compression and decompression system comprising: a) a data compressor for receiving variable length data elements and generating variable length codes comprising raw data tokens, comprising raw data and a length code, and compressed word tokens for data elements that match previously received data elements, said compressed word tokens comprising a compression code, an address and a variable length code representing one of a predetermined number of variable length possibilities; and b) a data decompressor comprising: i) means for storing variable length tokens, said storage means having a plurality of addresses; ii) means for decoding said length code of a first variable length code and outputting a signal identifying one of said length possibilities; iii) means for adding in parallel all variable length possibilities of said first variable length code to its starting address to generate plural possible next addresses; and iv) means for selecting one of said possible next addresses as the starting addresses for a subsequent variable length code on the basis of the output of said decoding means.

Claim 15

Dependent Claim 172 words

A data compression and decompression system comprising: a) a data compressor for receiving variable length data elements and generating variable length codes comprising raw data tokens, comprising raw data and a length code, and compressed word tokens for data elements that match previously received data elements, said compressed word tokens comprising a compression code, an address and a variable length code representing one of a predetermined number of variable length possibilities; and b) a data decompressor comprising: i) means for storing variable length tokens, said storage means having a plurality of addresses; ii) means for decoding said length code of a first variable length code and outputting a signal identifying one of said length possibilities; iii) means for adding in parallel all variable length possibilities of said first variable length code to its starting address to generate plural possible next addresses; and iv) means for selecting one of said possible next addresses as the starting addresses for a subsequent variable length code on the basis of the output of said decoding means.

Claim 16

Dependent Claim 54 words

A compression and decompression system as set forth in claim 12 wherein said adding means comprises means for storing a predetermined plurality of variable fixed length values, and a plurality of adders each for receiving a common starting address value and a respective variable address size for generating said plurality of possible next addresses.

Claim 17

Dependent Claim 43 words

A compression and decompression system as set forth in claim 12 further comprising in said decompressor a means for determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.

Claim 18

Dependent Claim 74 words

A compression and decompression system as set forth in claim 12, said decompressor further comprising: history buffer means for storing decompressed raw data; output means for storing an entire code word position-adjusted in common with respect to all other code words and outputting said code word in response to said selecting means; and decode means for decoding said output code word and controlling storage of variable length data elements in said history buffer means.

Claim 19

Independent Claim 152 words

A method of decompressing compressed data, said compressed data being represented by a code token comprising a status code indicating its status as compressed data, a length code indicating its length within a predetermined plurality of length value cases and an address in a history memory, comprising: a) decoding said length code and identifying one of said plurality of length value cases, b) concurrently with said decoding step, determining an identity between a plurality of possible next code token addresses and an available code token storage area by (i) adding all possible code lengths to a current code token address for generating plural possible next addresses, and (ii) determining for said plural possible next code token addresses on the basis of an available storage segment an identity of values; and c) selecting a next code token address on the basis of said identified length value cases and said determined identity of values.

Claim 20

Independent Claim 152 words

A method of decompressing compressed data, said compressed data being represented by a code token comprising a status code indicating its status as compressed data, a length code indicating its length within a predetermined plurality of length value cases and an address in a history memory, comprising: a) decoding said length code and identifying one of said plurality of length value cases, b) concurrently with said decoding step, determining an identity between a plurality of possible next code token addresses and an available code token storage area by (i) adding all possible code lengths to a current code token address for generating plural possible next addresses, and (ii) determining for said plural possible next code token addresses on the basis of an available storage segment an identity of values; and c) selecting a next code token address on the basis of said identified length value cases and said determined identity of values.

Claim 21

Dependent Claim 25 words

The method as set forth in claim 16, further comprising: selecting said length code value on the basis of the size of said history memory.

Claim 22

Dependent Claim 32 words

The method as set forth in claim 16, further comprising: aligning said stored code tokens for providing aligned storage locations for said first and second code tokens irrespective of code token length.

Claim 23

Dependent Claim 21 words

The method as set forth in claim 18, wherein said aligning step comprises barrel shifting each of said code tokens separately.

Claim 24

Dependent Claim 56 words

The method as set forth in claim 16, comprising: receiving at least part of each variable length code token and assembling said parts in said storage means as a complete token; and determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-11-05	2000-05-06	2000-11-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-11-05	2004-05-06	2004-11-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-11-05	2008-05-06	2008-11-05	$7700.00	Window Closed / Lapsed

Method and apparatus for compressing and decompressing data

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag