Rapid entropy coding for data compression or decompression

• US 5,818,369 A
• Filed: 03/07/1996
• Issued: 10/06/1998
• Est. Priority Date: 03/07/1996
• Status: Expired due to Fees

• Current Assignee: Pegasus Imaging Corporation (Accusoft Corporation)
• Original Assignee: Pegasus Imaging Corporation (Accusoft Corporation)
• Inventors: Withers, Wm. Douglas
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/613,392
• Time in Patent Office: 943 Days
• Field of Search: 341/107, 341/67, 341/58, 341/94, 341/106
• US Class Current: 341/107
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

A method of manipulating a series of data units comprising distinct data values, including the steps of modelling the occurrence probability of each distinct data value, repeatedly performing the steps of narrowing a manipulation result number into a subinterval determined by the occurrence probability for each successive data value and outputting the more significant digits of the manipulation result number, that can no longer change due to further narrowing, such that the sequence of the output digits are the manipulated data.

Claims

1. A method of manipulating a series of data units comprising distinct data values comprising the step of:

modelling the occurrence probability of each distinct data value;

repeatedly performing, the steps of

subdividing a byte into at least nine units, each of said units corresponding to one occurrence of a theoretically most probable data value;

narrowing a manipulation result number using, said units into a subinterval determined by the occurrence probability for each successive data value; and

outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing,

such that the sequence of said output digits comprise the manipulated data.

6. The method of claim 1, further comprising the steps of:

converting said occurrence probability to a subinterval using a table, for each successive data value;

adapting said occurrence probabilities to actual occurrences in said series by shifting said table in a probability dimension; and

outputting said more significant digits in units of at least one byte.

2. A method of manipulating a series of data units comprising distinct data values comprising the steps of:

modelling the occurrence probability of each distinct data value;

repeatedly performing the steps of

narrowing a manipulation result number using a table into a subinterval determined by the occurrence probability for each successive data value; and

outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing,

such that the sequence of said output digits comprise the manipulated data.

3. The method of claim 2, further comprising the step of adapting said occurrence probabilities to actual occurrences in said series by shifting said table in a probability dimension.

4. A method of manipulating a series of data units comprising distinct data values comprising the steps of:

modelling the occurrence probability of each distinct data value;

repeatedly performing the steps of

narrowing a manipulation result number into a subinterval determined by the occurrence probability for each successive data value; and

outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing in units of at least one byte,

such that the sequence of said output digits comprise the manipulated data.

5. A method of manipulating a series of data units comprising distinct data values comprising the steps of:

modelling the occurrence probability of each distinct data value;

repeatedly performing the steps of

narrowing a manipulation result number outside a subinterval determined by the occurrence probability for each successive data value, whereby control information is encoded in said manipulated data; and

outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing,

such that the sequence of said output digits comprise the manipulated data.

7. An apparatus for manipulating a series of data units comprising distinct data values, further comprising:

means for modelling the occurrence probability of each distinct data value;

means for subdividing a byte into at least nine units, each of said units corresponding to one occurrence of a theoretically most probable data value;

means for narrowing a manipulation result number into a subinterval determined by the occurrence probability for each successive data value; and

means for outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing, such that the sequence of said output digits comprise the manipulated data.

12. The apparatus of claim 7, further comprising:

means for converting said occurrence probability to a subinterval using a table, for each successive data value;

means for adapting said occurrence probabilities to actual occurrences in said series by shifting said table in a probability dimension; and

means for outputting said more significant digits in units of at least one byte.

8. An apparatus for manipulating a series of data units comprising distinct data values, comprising:

means for modelling the occurrence probability of each distinct data value;

means for narrowing a manipulation result number using a table into a subinterval determined by the occurrence probability for each successive data value; and

means for outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing, such that the sequence of said output digits comprise the manipulated data.

9. The apparatus of claim 8, further comprising means for adapting said occurrence probabilities to actual occurrences in said series by shifting said table in a probability dimension.

10. An apparatus for manipulating a series of data units comprising distinct data values, comprising:

means for modelling the occurrence probability of each distinct data value;

means for narrowing a manipulation result number into a subinterval determined by the occurrence probability for each successive data value; and

means for outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing in units of at least one byte, such that the sequence of said output digits comprise the manipulated data.

11. An apparatus for manipulating a series of data units comprising distinct data values, comprising:

means for modelling the occurrence probability of each distinct data value;

means for narrowing a manipulation result number outside a subinterval determined by the occurrence probability for each successive data value, whereby control information is encoded in said manipulated data; and

means for outputting the more significant digits of the manipulation result number that can no longer change due to further narrowing, such that the sequence of said output digits comprise the manipulated data.

13. A method of compressing a data stream expressed as a sequence of binary-decision signals comprising, for each such signal, the steps of:

storing a minimum consistent value;

storing a data counter value;

storing a plurality of first and a plurality of second code-length values;

identifying one of said first code-length values as the current one, and identifying one of said second code-length values as the current one;

calculating a threshold value based on said data counter value and said current identified first and second code-length values;

updating said minimum consistent value by adding said threshold value in response to the binary-decision signal;

increasing said data-counter value;

outputting data, such that said data comprises a compressed data stream; and

updating said consistent minimum value in response to said data-counter value dropping below a predetermined minimum.

14. The method of compressing the data stream of claim 13, further comprising expanding the compressed data stream, further comprising the steps of:

storing an internal buffer value;

comparing said internal buffer value with said threshold value and generating an expanded binary-decision signal in response to said comparison;

updating said data counter value by subtracting either said current identified first code-length value or said current identified second code-length value, in response to said comparison;

updating said internal buffer value in response to said comparison;

increasing said data counter value and updating said internal buffer value using said internal buffer value and data from said output data in response to the data counter value dropping below a prescribed minimum.

15. A method of expanding a data stream comprising the steps of:

storing an internal buffer value;

calculating a threshold value based on a stored data counter value and an identified one of a plurality of first and second stored code-length values;

comparing said internal buffer value with said threshold value and generating an expanded binary-decision signal in response to said comparison;

updating said data counter value by subtracting either said current identified first code-length value or said current identified second code-length value, in response to said comparison;

updating said internal buffer value in response to said comparison;

increasing said data counter value and updating said internal buffer value using said internal buffer value and data from said output data in response to the data counter value dropping below a prescribed minimum.