Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-10-31
2001-06-26
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S495000
Reexamination Certificate
active
06253222
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to number representations and computations in a computer system. More particularly, it relates to the compression and decompression of floating point numbers.
BACKGROUND
Generally, a number used in a computer system requires a memory allocation specified by the operating system. In some cases, it is important to conserve memory by representing that number in a memory space smaller than that which the operating system defines. Such representations are especially valuable in applications that utilize large quantities of data. The process of reducing required memory is referred to as compression, and the opposite function, that of recovering the number to its original format, is called decompression.
Floating point numbers have been compressed using the subtract and multiply instructions to bias, as well as to scale a floating point number so that its value is in a desired range. The resulting floating point number is then converted to an integer. Due to the multiplication instructions, this technique is relatively slow.
Another technique is to separately truncate and store the exponent and the mantissa fields of the floating point number. The algebraic sign bit is also separately stored. Since not all combinations of bits in the compressed format represent floating point numbers in a desired range, the number of bits required is more than necessary. Also, two separate field store operations for compression, as well as two separate field extractions for decompression, are required—one each for the exponent and for the mantissa. There is also a store and a retrieve operation for the algebraic sign.
In order to better meet the dual requirements of reduced memory utilization which permits more data to be loaded into memory and of higher speed which increases application performance, a need exists for further improvements in methods of compressing and decompressing floating point numbers in computer systems.
SUMMARY OF THE INVENTION
Representative embodiments of the present invention present methods for the compression of numbers. In particular, the present patent document relates to methods for the high speed compression and decompression of limited range floating point numbers. Compression of a floating point number converts it to a much smaller representation of the number, and decompression converts a compressed representation of a floating point number back into a regular floating point number whose value is approximately that of the original floating point number, but may have somewhat less precision. Methods used in the present patent document are designed for rapid execution on a computer. For compression, these methods employ the very fast numerical steps of subtraction, extraction, and insertion. While for decompression, these methods employ comparably fast numerical steps of addition, extraction, and insertion.
Compression of floating point numbers is useful for reducing the storage space in computer memory required for either floating point data or any data structures which contain floating point numbers. Compression is also useful for reducing the bandwidth or speed required of a communication pathway to transmit either floating point data or any data structures which contain floating point numbers. Compressed floats may be used directly as data, without decompressing them. Specifically, the compressed float interpreted as an integer may be used as an index into an array. Used as such, it constitutes a rapid method of mapping floating point numbers to values stored in the array.
In a representative embodiment, prior to compression and decompression, six characteristics are either specified or determined: (1) the number of binary digits used in the compressed representation, (2) whether or not decompression results have mixed signed values, (3) whether or not decompression results include zero, (4) the largest non-compressed absolute value, (5) the smallest, non-zero non-compressed absolute value, and (6) the compression rounding method. In representative embodiments there are three compression rounding methods: (1) “Round down”, (2) “Round to Nearest”, and (3) “Round up”. The range of numbers to be compressed, referred to herein as the range of compressible numbers, is also specified.
The non-compressed number space and the compressed number space both comprise discrete values with the compressed number space having a lesser precision than the non-compressed number space. Decompressions of compressed numbers return discrete decompressed values in the non-compressed number space. In the “round down” compression rounding method any value in non-compressed number space between two such adjacent decompressed values is rounded down in compressed number space to the smaller or “floor” of the two corresponding adjacent compressed values. In the “round up” compression rounding method any value in non-compressed number space between two such adjacent decompressed values is rounded in compressed number space to the larger or “ceiling” of the two corresponding adjacent compressed values. While, in the “round nearest” compression rounding method any value in non-compressed number space between two such adjacent decompressed values is rounded in compressed number space to the nearest of the two corresponding adjacent compressed values.
Using these six characteristics, constants used in the compression/decompression process, as well as the resulting precision, can be determined.
The floating-point compression process begins by clearing the sign bit to zero. However, if decompression results have mixed signed values, the sign bit is extracted and stored before clearing. Next the compression bias constant, computed in accordance with the teachings of the present patent document, is subtracted from the modified floating-point value. The subtraction is performed as if both values are binary numbers. Such values are referred to herein as fixed-point-format binary numbers. The determined number of bits is extracted from the result and is stored in the compressed floating-point number. When the result of the subtraction is less than or equal to zero, zero is stored. Finally, if decompression results have mixed signed values, the saved floating-point sign bit is stored in the compressed floating-point number.
To decompress, the compressed floating-point value is deposited into a floating-point value. When the non-compressed results include zero and the compressed floating-point number is zero, the decompression process is complete. Otherwise, the decompression bias constant, computed in accordance with the teachings of the present patent document, is added to this value as if both values are binary numbers. Finally, if decompression results have mixed signed values, the compressed floating-point sign bit is stored in the floating-point sign.
Compressed representations of numbers and associated decompressed numbers obtained using methods of representative embodiments enable applications to utilize larger data sets with higher performance than would otherwise be possible without compression. The methods used in these representative embodiments are simple and fast. They can be implemented in special purpose computing hardware with minimal cost and complexity. The methods of the present patent document are applicable to floating point numbers bounded by upper and lower absolute magnitude values.
REFERENCES:
patent: 3835456 (1974-09-01), Angelle et al.
patent: 4750146 (1988-06-01), Dalqvist et al.
patent: 5325316 (1994-06-01), Koshiba
Dyer Don W.
Sands Samuel C
Hewlett--Packard Company
Mai Tan V.
LandOfFree
Compression of limited range floating point numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression of limited range floating point numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of limited range floating point numbers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2437073