System and method for compressing a stream of integer-valued data
AssigneeApple Inc.
InventorMitchell Howard Oslick
Life of this patent
Estimating the term…
Abstract
A method and system are provided to minimize the size and complexity of bitstreams associated with encoded data by using a new compression scheme. An entropy encoder receives a list of run/data value pairs and entropy encodes separately the runs and data values, selecting their codewords according to length and magnitude, respectively, and catenates the resulting codeword pairs—run codeword first—in an encoded bitstream.
Claims45
A method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each run based on its length;
- if the run is 1, selecting a first code with a length of 1;
- if the run is classified as short, selecting a first code with a first predetermined length, each first code of first predetermined length having a preamble to distinguish the other run classifications, and having a value based on the run's length;
- if the run is classified as long, selecting a first code with a second predetermined length, each first code of second predetermined length having a preamble to distinguish the other run classifications, and having a value based on the run's length;
- and
- outputting the selected first code to a channel.
A method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each data value based on its magnitude;
- if the data value is classified as small, selecting a first code with a first predetermined length, each first code of first predetermined length having a preamble to distinguish large data values, and having a value based on the data value;
- if the data value is classified as large, selecting a first code with a second predetermined length, each first code of second predetermined length having a preamble to distinguish small data values, and having a value based on the data value;
- and
- outputting the selected first code to a channel.
A method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each run based on its length;
- if the run is 1, selecting a first code comprising a single bit;
- if the run is classified as short, selecting a first code comprising n+1 bits from a first codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining n bits is based on the run's length;
- if the run is classified as long, selecting a first code comprising n+1+M bits from a second codebook, the selected first code having a predetermined preamble for the first n+1 bits and whose value for the remaining M bits is based on the run's length;
- and
- outputting the selected first code to a channel.
A method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each data value based on its magnitude;
- if the data value is classified as small, selecting a first code comprising k+2 bits from a first codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining k+1 bits is based on the data value;
- if the data value is classified as large, selecting a first code comprising N+1 bits from a second codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining N bits is based on the data value and N;
- and
- outputting the selected first code to a channel.
A system for entropy coding a list of run/data value pair data corresponding to a stream of integer-valued data, said system comprising:
- an entropy encoder having an input to receive the list, the entropy encoder to:
- entropy encode the list of run/data value pairs into a list of run codeword/data value codeword pairs, wherein the runs are encoded separately from the data values;
- and
- generate an encoded bitstream by catenating, for every run codeword/data value codeword pair, the data value codeword with its corresponding run codeword, wherein the data value codeword appears before the run codeword in the encoded bitstream.
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each run based on its length;
- if the run is 1, selecting a first code with a length of 1;
- if the run is classified as short, selecting a first code with a first predetermined length, each first code of first predetermined length having a preamble to distinguish the other run classifications, and having a value based on the run's length;
- if the run is classified as long, selecting a first code with a second predetermined length, each first code of second predetermined length having a preamble to distinguish the other run classifications, and having a value based on the run's length;
- and
- outputting the selected first code to a channel.
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each run based on its length;
- if the run is 1, selecting a first code comprising a single bit;
- if the run is classified as short, selecting a first code comprising n+1 bits from a first codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining n bits is based on the run's length;
- if the run is classified as long, selecting a first code comprising n+1+M bits from a second codebook, the selected first code having a predetermined preamble for the first n+1 bits and whose value for the remaining M bits is based on the run's length;
- and
- outputting the selected first code to a channel.
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each data value based on its magnitude;
- if the data value is classified as small, selecting a first code with a first predetermined length, each first code of first predetermined length having a preamble to distinguish large data values, and having a value based on the data value;
- if the data value is classified as large, selecting a first code with a second predetermined length, each first code of second predetermined length having a preamble to distinguish small data values, and having a value based on the data value;
- and
- outputting the selected first code to a channel.
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method for entropy coding run/data value pair data corresponding to a stream of integer-valued data, said method comprising:
- classifying each data value based on its magnitude;
- if the data value is classified as small, selecting a first code comprising k+2 bits from a first codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining k+1 bits is based on the data value;
- if the data value is classified as large, selecting a first code comprising N+1 bits from a second codebook, the selected first code having a predetermined preamble for the first bit and whose value for the remaining N bits is based on the data value and N;
- and
- outputting the selected first code to a channel.
Dependencies are inferred from the claim text.