Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression
Reexamination Certificate
2001-09-17
2002-12-03
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Unnecessary data suppression
Reexamination Certificate
active
06489902
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data compression (i.e., creation of compressed data from uncompressed data) and decompression (i.e., recovery of the uncompressed data from the compressed data).
Data compression systems are known in the prior art that compress a stream of digital data signals (uncompressed bits) into compressed digital data signals (compressed bits), which require less bandwidth (fewer bits) than the original digital data signals, and that decompress the compressed digital data signals back into the original data signals or a close approximation thereof. Lossless data compression systems decompress the compressed digital data signals back into the original data signals exactly. Thus, lossless data compression refers to any process that converts data into an alternative data form that requires less bandwidth, i.e., has fewer bits, than the data converted in a process that is reversible so that the original data can be recovered.
Accordingly, the objective of data compression systems is to effect a savings in an amount of storage required to hold the data or the amount of time (or bandwidth) required to transmit the data. By decreasing required space for data storage or required time (or bandwidth) for data transmission, data compression results in a monetary and resource savings.
A compression ratio is defined as the ratio of the length of the data in the alternative data form (compressed data) to the length of the data originally (original data). Thus defined, the smaller the compression ratio, the greater will be the savings in storage, time, or bandwidth.
If physical devices such as magnetic disks or magnetic tape are utilized to store the data, then a smaller space is required on the device for storing the compressed data than would be required for storing the original data, thereby, e.g., utilizing fewer disks or tapes for storage. If telephone lines, satellite links or other communications channels are utilized for transmitting digital information, then lower costs, i.e., shorter transmission times and/or smaller bandwidths, result when compressed data is employed instead of original data.
Data compression systems can be made particularly effective if the original data contains redundancies such as having symbols or strings of symbols appearing with high frequency. In fact, redundancies in the original data is a requirement for lossless data compression. A data compression system operating on original data containing redundancies may, for example, transform multiple instances of a symbol, or transform a string of symbols, in the original data into a more concise form, such as a special symbol or group of symbols indicating multiple occurrences of the symbol, or indicating the string of symbols, and thereafter translate or decompress the concise form back into the multiple instances of the symbol, or back into the string of symbols.
For example, it may be desirable to transmit the contents of a daily newspaper via a satellite link or other communications link to a remote location for printing. Appropriate sensors within a data compression system may convert the contents of the newspaper into a data stream of serially occurring characters for transmission via the satellite link. If the millions of bits comprising the contents of the daily newspaper were compressed before transmission and decompressed at the receiver, a significant amount, e.g., such as 50% or more, of transmission time (or bandwidth) could be saved. As a further example, when an extensive database such as an airline reservation database or a banking system database is stored for archival or backup purposes, a significant amount of storage space, such as 50% or more, can be saved if the database files are compressed prior to storage and decompressed when they are retrieved from storage.
To be of practical and general utility, a digital data compression system should satisfy certain criteria. Specifically, one criterion is that the system should provide high performance, i.e., compression/decompression rates, for both compression and decompression with respect to the data rates in the communications channel being utilized, be it a data bus, a wired network, a wireless network or the like. In other words, data transmission rates seen by a sender of uncompressed data and a receiver of the uncompressed data should not be reduced as a result of compression/ decompression overhead. In fact, effective data rates may be significantly increased over slow communications channels, because more original data can be transmitted per unit time, if the original data is compressed preceding and following transmission, since there is less compressed data to transmit than there would have been original data.
The rate at which data can be compressed (i.e., the compression rate) is the rate at which the original data can be converted into compressed data and is typically specified in millions of bytes per second (megabytes/sec). The rate at which data can be decompressed (i.e., the decompression rate) is the rate at which compressed data can be converted back into original data. High compression rates and high decompression rates are necessary to maintain, i.e., not degrade, data rates achieved in present day disk, tape and communication systems, which typically exceed one megabyte/sec. Thus, practical data compression systems must typically have compression and decompression rates matching or exceeding some application-dependent threshold, e.g., one megabyte/sec.
The performance of prior art data compression systems is typically limited by the speed of the random access memories (RAM) and the like utilized to store statistical data and guide the compression and decompression processes. High performance compression rates and decompression rates for a data compression system can thus be characterized by a number of cycles (read and write operations) required per input character into or out of the data compression system. Fewer memory cycles per input character leads to higher performance compression rates and decompression rates.
Another important criterion in the design of a data compression and decompression system is compression effectiveness. Compression effectiveness is characterized by the compression ratio of the system, i.e. a smaller compression ratio indicates greater compression effectiveness. However, in order for data to be compressible using a lossless data compression system, the data to be compressed must contain redundancies. As a result, the compression ratio, or compression effectiveness, in a lossless data compression system (and to a lesser degree in a lossy data compression system) is a function of the degree of redundancy in the data being compressed. The compression effectiveness of any data compression system is also affected by how effectively the data compression system exploits, for data compression purposes, the particular forms of redundancy in the original data.
In typical computer stored data, e.g., arrays of integers, text, programs or the like, redundancy occurs both in the repetitive use of individual symbology, e.g., digits, bytes or characters, and in frequent recurrence of symbol sequences, such as common words, blank record fields, and the like. An effective data compression system should respond to both types of redundancy.
A further criterion important in the design of data compression and decompression systems is that of adaptability. Many prior art data compression procedures require prior knowledge, or the statistics, of the data being compressed. Some prior art procedures adapt to the statistics of the data as it is received, i.e., adaptive data compression systems, and others do not, i.e., non-adaptive data compressions systems. Where prior art procedures do not adapt to the statistics of the data as it is received, compression effectiveness is reduced, but where such procedures do adapt to the statistics, an inordinate degree of complexity is required in the data compression system. An adaptive data compression system may be utilized over
Hughes Electronics Corporation
Sales Michael W.
Whelan John T.
Young Brian
LandOfFree
Data compression for use with a communications channel does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression for use with a communications channel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression for use with a communications channel will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984554