1. A computer method for encoding non-repeating data values, the method comprising:
receiving an input stream having a plurality of non-repeating literals to be encoded into an output stream having a preamble and a payload, each of the non-repeating literal being represented by a unique data value;
identifying a lowest value among data values representing the plurality of non-repeating literals to be encoded and a literal count representing a number of the plurality of non-repeating literals to be encoded;
determining a bit count representing a number of bits required to encode each of the non-repeating literals;
emitting the lowest value, the literal count, and the bit count into the preamble of the output stream; and
for each literal of the input stream, emitting into the payload of the output stream a code value representing a predetermined relationship between the data value associated with each literal and the identified lowest value.
2. The method of claim 1, wherein determining a bit count representing a number of bits required to encode each of the plurality of non-repeating literals comprises:
identifying a highest value among the data values representing the plurality of non-repeating literals; and
performing a predetermined mathematical operation between the highest value and the lowest value to derive the bit count.
3. The method of claim 2, wherein the bit count is performed based on a base-two logarithm operation based on a difference between the highest and lowest values.
4. The method of claim 1, wherein the code value represents a difference between the data value associated with each literal and the identified lowest value.
5. The method of claim 2, wherein the code value represents an index of an entry of a possibility table, the entry having a value representing the difference between the data value associated with each literal and the identified lowest value.
6. The method of claim 5, further comprising:
constructing the possibility table having a plurality of entries, each representing a possible difference between a possible literal and a literal associated with the lowest value;
for each literal, locating an entry in the possibility table that has a value equivalent to the difference between the data value associated with each literal and the identified lowest value;
determining an index associated with the located entry to be used as part of the code value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
7. The method of claim 5, further comprising generating a bit stream using a mixed base representation to represent each index associated with each literal, and wherein the bit stream is emitted into the payload of the output stream.
8. The method of claim 7, wherein generating a bit stream comprises:
initializing an accumulator as zero and a counter having a value representing a largest possible index of the possibility table;
for each index until all indices have been processed, multiplying the accumulator with the counter and storing a result of multiplication in the accumulator;
decrementing the counter;
adding a current index into the accumulator; and
emitting a value stored in the accumulator as a bit stream into the payload of the output stream when all indices have been processed.
9. The method of claim 2, wherein the code value represents an index of an entry of a possibility table, the entry having a value representing each literal.
10. The method of claim 9, further comprising:
constructing the possibility table having a plurality of entries, each representing a possible literal;
for each literal, locating an entry in the possibility table that has a value equivalent to an actual code representing the respective literal;
determining an index associated with the located entry;
emitting an output code representing the respective literal into the output stream, the output code representing a difference between the actual code of the respective literal and the identified lowest value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
11. A machine-readable medium having instructions stored therein, which when executed by a machine, cause the machine to perform a method for encoding non-repeating data values, the method comprising:
receiving an input stream having a plurality of non-repeating literals to be encoded into an output stream having a preamble and a payload, each of the non-repeating literal being represented by a unique data value;
identifying a lowest value among data values representing the plurality of non-repeating literals to be encoded and a literal count representing a number of the plurality of non-repeating literals to be encoded;
determining a bit count representing a number of bits required to encode each of the plurality of non-repeating literals;
emitting the lowest value, the literal count, and the bit count into the preamble of the output stream; and
for each literal of the input stream, emitting into the payload of the output stream a code value representing a predetermined relationship between the data value associated with each literal and the identified lowest value.
12. The machine-readable medium of claim 11, wherein determining a bit count representing a number of bits required to encode each of the plurality of non-repeating literals comprises:
identifying a highest value among the data values representing the plurality of non-repeating literals; and
performing a predetermined mathematical operation between the highest value and the lowest value to derive the bit count.
13. The machine-readable medium of claim 12, wherein the bit count is performed based on a base-two logarithm operation based on a difference between the highest and lowest values.
14. The machine-readable medium of claim 11, wherein the code value represents a difference between the data value associated with each literal and the identified lowest value.
15. The machine-readable medium of claim 12, wherein the code value represents an index of an entry of a possibility table, the entry having a value representing the difference between the data value associated with each literal and the identified lowest value.
16. The machine-readable medium of claim 15, wherein the method further comprises:
constructing the possibility table having a plurality of entries, each representing a possible difference between a possible literal and a literal associated with the lowest value;
for each literal, locating an entry in the possibility table that has a value equivalent to the difference between the data value associated with each literal and the identified lowest value;
determining an index associated with the located entry to be used as part of the code value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
17. The machine-readable medium of claim 15, wherein the method further comprises generating a bit stream using a mixed base representation to represent each index associated with each literal, and wherein the bit stream is emitted into the payload of the output stream.
18. The machine-readable medium of claim 17, wherein generating a bit stream comprises:
initializing an accumulator as zero and a counter having a value representing a largest possible index of the possibility table;
for each index until all indices have been processed, multiplying the accumulator with the counter and storing a result of multiplication in the accumulator;
decrementing the counter;
adding a current index into the accumulator; and
emitting a value stored in the accumulator as a bit stream into the payload of the output stream when all indices have been processed.
19. The machine-readable medium of claim 11, wherein the code value represents an index of an entry of a possibility table, the entry having a value representing each literal.
20. The machine-readable medium of claim 19, wherein the method further comprises:
constructing the possibility table having a plurality of entries, each representing a possible literal;
for each literal, locating an entry in the possibility table that has a value equivalent to an actual code representing the respective literal;
determining an index associated with the located entry;
emitting an output code representing the respective literal into the output stream, the output code representing a difference between the actual code of the respective literal and the identified lowest value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
21. A computer-implemented method for decoding non-repeating data values, the method comprising:
receiving an input stream having a preamble and a payload including a plurality of non-repeating literals encoded therein, each literal being encoded via a unique code value that is different from code values associated with a remainder of the plurality of non-repeating literals;
extracting from the preamble of the input stream a lowest data value among data values that represent the plurality of non-repeating literals, a bit count representing a number of bits required to encode each unique code value, and a literal count representing a number of the plurality of non-repeating literals currently encoded within the input stream;
for each literal up to the literal count, extracting from the payload of the input stream a unique code value associated with each literal, the unique code value representing a predetermined relationship between each literal and a literal associated with the lowest data value; and
determining an actual data value representing each literal based on the lowest data value and the unique code value associated with each literal to recover each literal.
22. The method of claim 21, wherein the associated unique code value is extracted from a location determined based on the bit count and a sequential position within the plurality of non-repeating literals, and wherein the actual data value is determined by adding the associated unique code value with the lowest data value.
23. The method of claim 21, wherein the unique code value represents an index of an entry of a possibility table, the entry having a value representing the difference between a data value associated with each literal and the lowest value.
24. The method of claim 23, further comprising:
constructing the possibility table having a plurality of entries, each representing a possible difference between a possible literal and a literal associated with the lowest value;
for each literal, locating an entry in the possibility table that has a value equivalent to the difference between the data value associated with each literal and the lowest value;
determining an index associated with the located entry to be used as part of the code value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
25. A machine-readable medium having instructions stored therein, which when executed by a machine, cause the machine to perform a method for decoding non-repeating data values, the method comprising:
receiving an input stream having a preamble and a payload including a plurality of non-repeating literals encoded therein, each literal being encoded via a unique code value that is different from code values associated with a remainder of the plurality of non-repeating literals;
extracting from the preamble of the input stream a lowest data value among data values that represent the plurality of non-repeating literals, a bit count representing a number of bits required to encode each unique code value, and a literal count representing a number of the plurality of non-repeating literals currently encoded within the input stream;
for each literal up to the literal count, extracting from the payload of the input stream a unique code value associated with each literal, the unique code value representing a predetermined relationship between each literal and a literal associated with the lowest data value; and
determining an actual data value representing each literal based on the lowest data value and the unique code value associated with each literal to recover each literal.
26. The machine-readable medium of claim 25, wherein the associated unique code value is extracted from a location determined based on the bit count and a sequential position within the plurality of non-repeating literals, and wherein the actual data value is determined by adding the associated unique code value with the lowest data value.
27. The machine-readable medium of claim 25, wherein the unique code value represents an index of an entry of a possibility table, the entry having a value representing the difference between a data value associated with each literal and the lowest value.
28. The machine-readable medium of claim 27, wherein the method further comprises:
constructing the possibility table having a plurality of entries, each representing a possible difference between a possible literal and a literal associated with the lowest value;
for each literal, locating an entry in the possibility table that has a value equivalent to the difference between the data value associated with each literal and the lowest value;
determining an index associated with the located entry to be used as part of the code value;
removing the located entry from the possibility table; and
sorting remaining entries in the possibility table.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A rounding computing method comprising the steps of:
determining whether a specific area of upper n bits (where z>n\u22672) of input data comprising z bits (where z\u22672) is being used;
when the specific area is not used in the result of determination, discarding the upper n nits and lower (z2\u2212n) bits in the input data and rounding the corresponding data to z2-bit values; and
when the specific area is used in the result of determination, discarding lower z2 bits in the input data and rounding the corresponding data to z2 bits.
2. A rounding computing method comprising the steps of:
determining how many bits a specific area of upper z2 bits of input data comprising z bits (where z\u22672) uses; and
if the specific area uses x bits (where 0\u2266x\u2266z2) in the input data, discarding upper (z2\u2212x) bits and lower x bits in the input data and rounding the corresponding data to z2 bits.
3. A rounding computing method comprising the steps of:
detecting at what bits specific areas of upper z2 bits of a plurality of input data respectively comprising z bits (where z\u22672) are used in the input data and thereby determining the maximum value x (where 0\u2266x\u2266z2) of the used number of bits; and
discarding upper (z2\u2212x) bits and lower x bits in the respective input data and rounding the data to z2 bits respectively.
4. A computing device comprising:
rounding processing means for inputting therein multiplier factors and multiplicands respectively constituted of z bits (where z\u22672), determining whether specific areas of respective upper n bits (where z>n\u22672) of the multiplier factors and the multiplicands are respectively being used, discarding the upper n bits and lower (z2\u2212n) bits in the multiplier factors and the multiplicands if the specific areas are not used and rounding the corresponding multiplier factors and multiplicands to z2 bits respectively, and discarding lower z2 bits in the multiplier factors and the multiplicands if the specific areas are used and rounding the corresponding multiplier factors and multiplicands to z2 bits respectively;
memory means for storing information about the discarded respective numbers of bits respectively;
a z2-bit multiplier for performing multiplication on the multiplier factors and multiplicands rounded by the rounding processing means and outputting multiplication results therefrom; and
digit adjusting means for shifting the multiplication results on the basis of the number-of-bits information stored in the memory means to adjust digits.
5. A computing device comprising:
rounding processing means for inputting therein multiplier factors and multiplicands respectively constituted of z bits (z\u22672), determining at what bits specific areas of respective upper z2 bits of the multiplier factors and the multiplicands are being used, discarding upper (z2\u2212x) bits and lower x bits in the multiplier factors and the multiplicands if the specific areas use x bits (where 0\u2266x\u22662), and rounding the corresponding multiplier factors and multiplicands to z2 bits respectively;
memory means for storing information about the discarded respective numbers of bits therein respectively;
a z2-bit multiplier for performing multiplication on the multiplier factors and multiplicands rounded by the rounding processing means and outputting multiplication results therefrom; and
digit adjusting means for shifting the multiplication results on the basis of the number-of-bits information stored in the memory means to adjust digits.
6. A computing device comprising:
rounding processing means for inputting therein a plurality of multiplier factors and multiplicands respectively constituted of z bits (where z\u22672), detecting at what bits specific areas of respective upper z2 bits of the plurality of multiplier factors and multiplicands are being used, thereby determining the maximum value x (where 0\u2266x\u2266z2) of the used number of bits, discarding upper (z2\u2212x) bits and lower x bits in the multiplier factors and the multiplicands and rounding the corresponding multiplier factors and multiplicands to z2 bits respectively;
memory means for storing information about the discarded respective numbers of bits therein respectively;
a z2-bit multiplier for performing multiplication on the multiplier factors and multiplicands rounded by the rounding processing means and outputting multiplication results therefrom; and
digit adjusting means for shifting the multiplication results on the basis of the number-of-bits information stored in the memory means to adjust digits.