Entropy coding using adaptable prefix codes
AssigneeSun Microsystems, Inc.
InventorRussell A. Brown
Life of this patent
Estimating the term…
Abstract
The present invention provides an entropy coding scheme using an adaptable prefix code. The prefix code is a binary representation of the algorithm used to compress and decompress the data. There are prefix zeros that represent the number of significant binary digits that follow the first one. According to one embodiment, this scheme works on both positive and negative integers and encodes lower order integers with a smaller length of codeword. In another embodiment, the zero integer is encoded as a special case with the shortest codeword. In yet another embodiment, the present scheme is preferred by data sets that are clustered about zero, such as image data sets that have been transformed via a wavelet transform or a discrete cosine transform.
Claims14
An entropy coding scheme comprising:
- receiving an integer to be coded;
- converting the integer to its binary representation;
- counting a number of prefix zeros equal to the number of significant bits in the binary representation;
- catenating a single bit whose binary value equals one to the number of prefix zeros to form a string;
- and
- catenating the binary representation of the integer to the string to yield the coded value of the integer.
An entropy decoding scheme comprising:
- receiving a binary string;
- counting and discarding any prefix zeros preceding the first one bit of the binary string to yield the number of significant bits in the binary representation of an integer;
- discarding the first one bit;
- checking for a string or length equal to the prefix zeros discarded;
- and
- converting the binary value of the string to a decoded integer.
An article of manufacture comprising:
- a computer usable medium having computer readable program code embodied therein for an entropy coding scheme, said computer readable program code in said article of manufacture comprising:
- computer readable program code configured to cause said computer to receive an integer to be coded;
- computer readable program code configured to cause said computer to convert the integer to its binary representation;
- computer readable program code configured to cause said computer to count a number of prefix zeros equal to the number of significant bits in the binary representation;
- computer readable program code configured to cause said computer to catenate a single bit whose binary value equals one to the number of prefix zeros to form a string;
- and
- computer readable program code configured to cause said computer to catenate the binary representation of the integer to the string to yield the coded value of the integer.
An article of manufacture comprising:
- a computer usable medium having computer readable program code embodied therein for an entropy decoding scheme, said computer readable program code in said article of manufacture comprising:
- computer readable program code configured to cause said computer to receive a binary string;
- computer readable program code configured to cause said computer to count and discard any prefix zeros preceding the first one bit of the binary string to yield the number of significant bits in the binary representation of an integer;
- computer readable program code configured to cause said computer to discard the first one bit;
- computer readable program code configured to cause said computer to check for a string or length equal to the prefix zeros discarded;
- and
- computer readable program code configured to cause said computer to convert the binary value of the string to a decoded integer.
Dependencies are inferred from the claim text.