Parallel data compression and decompression

• US 5,654,703 A
• Filed: 06/17/1996
• Issued: 08/05/1997
• Est. Priority Date: 06/17/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Clark, Airell R. II
• Primary Examiner(s): DeBoer, Todd
• Application Number:
  US08/664,901
• Time in Patent Office: 414 Days
• Field of Search: 341/51, 341/60, 341/106, 341/52, 341/55, 341/87, 348/408
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An apparatus and method for parallel data compression and decompression uses packing and unpacking of data which has multi-variable components, for example, relational multi-variable content data such as tristimulus color space data used in color hard copy applications. Multiple input words are compressed in parallel compression engines and fed in parallel to a packer device which configures the codes in an order determined by order of compression and byte count for each word into a single bit string code. In the decompression cycle of the process, an unpacker device separates the single bit string code based upon length of a data string represented by a code word last decoded by either the decompression engine for that code word if the decompression engine is idle, or the length of the string that has been decoded so far if the decompression engine is currently working on a code.

Claims

1. Apparatus for parallel data compression and decompression, comprising:

N data compression engines, where "N"=number of data words to be compressed in parallel;

packing means for receiving from the N data compression engines N data word codes in parallel, for serially packing received N data word codes in an order determined by order of compression and byte count for each of the N data word codes, and for transmitting N packed data word codes as a single code word data string;

N data decompression engines; and

unpacking means for receiving from the packing means the single code word data string, unpacking the single code word data siring, and sending N unpacked data word codes on N parallel outputs to the N data decompression engines in a order based on length of a single code word data string represented by an unpacked data word code last decoded by either the decompression engine for that unpacked data word code if the decompression engine is idle, or the length of the single code word data string that has been decoded so far if the decompression engine is currently working on an unpacked data word code.

2. The apparatus as set forth in claim 1, further comprising:

the packing means having N, first in, first out input buffers for receiving the N data word codes in parallel and a code word data string output means for transmitting N packed data word codes as a single code word data string.

3. A method for parallel encoding of a data set wherein the data set of relational multi-variable content data set forth in data words, one for each variable of the data, the method comprising the steps of:

encoding data words in parallel into coded data words, one for each variable of the data;

transmitting the coded data words in parallel;

receiving the coded data words in a means for packing the coded data words into a single word bit string;

packing the coded data words into a single word bit string in an order based upon order of compression and byte count for each of the coded data words, respectively; and

transmitting the single word bit string from the means for packing.

4. The method as set forth in claim 3, further comprising the step of:

repeating the steps for each data word of the data set.

5. The method as set forth in claim 3, the step of packing further comprising:

setting a byte output count for each of "N" input coded data words to zero, where "N"=the number of data words to be encoded in parallel, one for each variable of the data;

receiving N coded data words in a first in, first out order;

resetting the byte output count to a first byte count comprising consecutive coded data word byte counts and bit string lengths for a current coded data word;

comparing each consecutive byte output count to a next previous consecutive byte output count for a next coded data word; and

ordering the coded data words in an order based upon the step of comparing in an order of compression and byte count for each coded data word.

6. A method for parallel decoding of data wherein the data comprises a series of single word bit strings containing a code for multiple coded data code words comprising data of relational multi-variable content, one data word for each of the variables, the method comprising the steps of:

receiving each of the single word bit strings in a means for unpacking the multiple coded data words;

providing a plurality of decompression engines, one for each of the variables of the data;

unpacking each of the single word bit strings in an order based upon length of a data string represented by a coded data word last decoded by either the decompression engine for that coded data word if the decompression engine is idle, or the length of the single word bit string that has been decoded so far if the decompression engine is currently working on a coded data word;

sending each unpacked coded data word to a respective decompression engine for the respective variable of the data.

7. The method as set forth in claim 6, the step of unpacking further comprising:

setting a byte output count for each plurality of "N" decompression engines to zero, where "N"=the number of coded data words to be decoded in parallel;

receiving each of the single word bit strings consecutively;

testing each byte count of a next coded data word for each of the plurality of "N" decompression engines against each other of the plurality of "N" decompression engines for the shortest byte output count; and

sending the next coded data word to a decompression engine in an order based upon order of compression and byte count for each coded data word, respectively.

8. The method as set forth in claim 7, further comprising the steps of:

prior to the step of testing, determining if a decompression engine is idle; and

if a decompression engine is idle, proceeding with the step of testing, or

if no decompression engine is idle, waiting one clock cycle and repeating the step of determining.

9. A parallel data compression and decompression method for the transmission of tristimulus color space data for a color image comprising a plurality of pixels, the method comprising the steps of:

providing at least three parallel data compression engines and at least three parallel data decompression engines;

compression encoding in parallel at least three primary color space data words representative of a pixel into at least three data codes, one for each primary color variable of the data, in one each of the at least three parallel data compression engines, respectively;

transmitting the at least three data codes in parallel from the at least three parallel data compression engines;

receiving the at least three data codes in a means for packing the data codes into a single code bit string;

packing the at least three data codes in an order based upon order of compression and byte count for each data code, respectively;

transmitting the single code bit string;

receiving the single code bit string in a means for unpacking the data codes from the single code bit string;

unpacking the single code bit string in an order based upon length of a single code bit string represented by a data code last decoded by either the decompression engine for that code word if the decompression engine is idle, or the length of the single code bit string that has been decoded so far if the decompression engine is currently working on a data code; and

sending each unpacked data code to a respective decompression engine for the respective variable of the color space data.

10. The method as set forth in claim 9, further comprising the steps of:

prior to the step of unpacking, repeating the previous steps of the method for each pixel of the image, whereby a set of single code bit strings is generated;

storing the set of single code bit strings for the entire color image; and

retrieving each stored single code bit string serially in the means for unpacking the at least three data codes.

11. The method as set forth in claim 9, further comprising:

providing a fourth data compression engine and a fourth data decompression engine for compression encoding of pixels comprising the color black; and

running the steps of the method in parallel for the fourth data compression engine.

12. The method as set forth in claim 9, the step of packing further comprising:

setting a byte output count for each input data code to zero;

receiving each of the data codes in a first in, first out order;

resetting the byte output count to a first byte count comprising consecutive data code bit counts and single code bit string lengths for a current data code;

comparing each consecutive byte output count to a next previous consecutive byte output count for a next data code; and

ordering the data codes in an order based upon order of compression and byte count for each data code.

13. The method as set forth in claim 9, the step of unpacking further comprising:

setting a byte output count for each of the decompression engines to zero;

receiving each of the single code bit strings consecutively;

testing each byte count of a next code for each of the decompression engines against each other of the decompression engines for the shortest byte output count; and

sending the next code to a decompression engine in an order based upon order of compression and byte count for each data code.

14. The method as set forth in claim 13, the step of testing comprises:

testing in accordance with the formula;

space="preserve" listing-type="tabular">__________________________________________________________________________TEST.sub.-- CONDITION.sub.-- X= DECOMRESSION.sub.-- ENGINE.sub.-- X idle AND BYTE.sub.-- COUNT.sub.-- X+PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X≦

BYTE.sub.-- COUNT.sub.-- X+1+ PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X+1 AND BYTE.sub.-- COUNT.sub.-- X+PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X≦

BYTE.sub.-- COUNT.sub.-- X+2+ PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X+2, AND __________________________________________________________________________

et seq. through X+last engine count, where X=first decompression engine, X+1=second decompression engine, X+2=third decompression engine, et seq.

15. A color hard copy data compression and decompression system comprising:

data compression means having

at least three data compression engines, each having an input for receiving a color data word representative of a primary color variable for a pixel to be produced in hard copy and an output for providing at least three codes in parallel, one each representative of each respective color data word,

packing means for packing at least three respective codes received from the at least three data compression engines into a single pixel code, the packing means having

at least three first in, first out buffers for receiving the at least three respective codes, and

means for ordering the at least three respective codes determined by order of compression and byte count for each code,

a packing means output for transmitting all bits of the single pixel code; and

data decompression means having

at least three decompression engines;

unpacking means for receiving the single pixel code from the packing means output and for unpacking the single pixel code into the at least three respective codes and for transmitting the at least three respective codes to respective decompression engines based upon length of a data string represented by a code last decoded by either the decompression engine for that code if the decompression engine is idle, or the length of the string that has been decoded so far if the decompression engine is currently working on a code.

16. The system as set forth in claim 15, further comprising:

a fourth compression engine operating in parallel with the at least three compression engines, and

a fourth decompression engine operating in parallel with the at least three decompression engines, wherein the fourth compression engine and the fourth decompression engine encode a color data word representative of the color of a pixel comprising the color black.

17. The system as set forth in claim 15, said unpacking means further comprising:

means for applying a test condition for sending a next code to a decompression engine where;

space="preserve" listing-type="tabular">__________________________________________________________________________TEST.sub.-- CONDITION.sub.-- X= DECOMRESSION.sub.-- ENGINE.sub.-- X idle AND BYTE.sub.-- COUNT.sub.-- X+PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X≦

BYTE.sub.-- COUNT.sub.-- X+1+ PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X+1 AND BYTE.sub.-- COUNT.sub.-- X+PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X≦

BYTE.sub.-- COUNT.sub.-- X+2+ PREV.sub.-- CODE.sub.-- LENGTH.sub.-- X+2, __________________________________________________________________________

et seq. through X+N, where X=consecutive parallel decompression engine designations and N=total number of parallel decompression engine,

for repeating the step of applying a test condition for each consecutive parallel decompression engine versus each other consecutive parallel decompression engine until a test condition occurs as true test condition, and

for sending the next code to the decompression engine for which the true condition occurs.