Rapid entropy coding for data compression or decompression
First Claim
Patent Images
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 ofsubdividing 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
15 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. - View Dependent Claims (6)
-
-
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. - View Dependent Claims (3)
-
-
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. - View Dependent Claims (12)
-
-
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. - View Dependent Claims (9)
-
-
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. - View Dependent Claims (14)
-
-
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.
-
Specification