Apparatus and associated method for compressing and decompressing digital data
AssigneeInternational Business Machines Corporation
InventorsRonald L. Heiney, Keith E. Duvall, Anthony F. Stuart, Claude A. Bugg, Gregory S. Felderman, Steven M. Scott
Life of this patent
Estimating the term…
Abstract
A data compression and decompression technique compresses a binary stream of digital data into compressed form and decompresses a compressed data stream into decompressed form without any loss of fidelity. The techniques require very little processing time to permit compression and decompression of digital data quickly. Once the digital data is compressed into compressed form, the amount of memory required to store the compressed digital data is much less than the amount of memory required to store the corresponding data in uncompressed form.
Claims20
A data compression and decompression method for compressing and then decompressing an input data stream that is formed of at least one input digital word, each input digital word formed of at least one signal bit, said input data stream being compressed into a compressed data stream that is formed of at least a control word, and said compressed data stream being decompressed to form an output data stream corresponding to said input data stream, said method comprising the steps of:
- determining individual bit values of the signal bits of the input digital words of the input data stream;
- when an input digital word of the input data stream includes at least one bit of a first logical value, concatenating the input digital word to the compressed data stream to form a portion thereof;
- and marking a bit of the control word associated with the input digital word with a first selected value, each bit of the control word associated with a different input digital word of the input data stream;
- when an input digital word of the input data stream includes bits of only a second logical value, marking the bit of the control word associated with the input digital word with a second selected value, thereby to form the compressed data stream of the control word and input digital words having at least one bit of the first logical value;
- reading the control word of the compressed data stream;
- determining which bits of the control word are of the first selected value and which bits of the control word are of the second selected value;
- when the bit of the control word is of the first selected value, reading an associated concatenated digital word of the compressed data stream, the associated concatenated digital word forming an output digital word of the output data stream;
- and
- when the bit of the control word is of the second selected value, generating an output digital word formed of bits which are all of a second logical value, thereby to form the output data stream of digital words corresponding to the input data stream.
A data compression method for compressing an input data stream formed of at least one input digital word into a compressed data stream formed of at least a control word, each input digital word formed of at least one signal bit, said method comprising the steps of:
- determining individual logical bit values of the signal bits of the input digital words of the input data stream;
- when an input digital word of the input data stream includes at least one bit of a first logical value concatenating the input digital word to the compressed data stream to form a portion thereof;
- and marking a bit of the control word associated with the input digital word with a first selected value, each bit of the control word being associated with a different input digital word of the input data stream;
- and
- when an input digital word of the input data stream includes bits of only a second logical value, marking the bit of the control word associated with the input digital word with a second selected value, thereby to form the compressed data stream of the control word and concatenated input digital words having at least one bit of the first logical value.
A data decompression method for decompressing a compressed data stream that including digital words and a control word having a plurality N of bits, to form an uncompressed output data stream formed of a plurality N of output digital words, said method comprising the steps of:
- determining which bits of the control word are of a first selected value and which bits of the control word are of a second selected value;
- when the bit of the control word is of the first selected value, reading a digital word of the compressed data stream, the read digital word forming an output digital word of the output data stream;
- and
- when the bit of the control word is of the second selected value, generating an output digital word that is formed of bits, all of second logical values, thereby to form the output data stream of digital words that are responsive to values of the bits of the control word.
Circuitry for compressing an input data stream formed of a plurality N of input digital words, each input digital word formed of at least one signal bit, into a compressed data stream formed of uncompressed input digital words and a control word having N bits, said circuitry comprising:
- a bit value-determining device for determining individual values of the signal bits within each one of the N input digital words of the input data stream;
- and
- a compressed data stream generator operative responsive to signal bit values determined by said bit value-determining device, said compressed data stream generator for marking an associated bit of the control word with a first selected value and concatenating the input digital word to the compressed data stream when the input digital word of the input data stream includes at least one bit of a first logical value, and for marking the associated bit of the control word with a second selected value when the input digital word includes bits of only a second logical value.
Apparatus for compressing an input-data-stream having a plurality N of input-words, each of said input-words containing a plurality of binary-bits, said apparatus operating to compress said input-data-stream into an output-data-stream having (1) a control-word containing said plurality N of binary-bits, and (2) a number of said input-words, said number of input-words in said output-data-stream being determined by a binary-state of said binary-bits contained in each one of said plurality N of input-words, said apparatus comprising:
- bit-state-determining means for determining said binary state of said binary-bits within each one of said plurality N of input-words, and
- output-data-stream generator means responsive to said bit-state-determining means;
- said output-data-stream generator means responding to a determination that a given input-word includes at least one binary-bit of a first binary-state, and operating in response thereto to (1) concatenate said given input-word to said output-data-stream, and (2) set an associated binary-bit of said control-word to a given binary-state, and
- said output-data-stream generator means responding to a determination that a given input-word includes only binary-bits of a second binary-state, and operating in response thereto to (1) set an associated binary-bit of said control-word to a binary-state that is opposite said given binary-state;
- whereby said output-data-stream contains (1) said control-word having said plurality N of binary-bits wherein each of said binary-bits corresponds to a different one of said plurality N of input-words, and (2) said number of concatenated input-words, each of which is identical to those input words that have at least one bit of said first binary-state.
Dependencies are inferred from the claim text.