Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2002-04-09
2004-05-18
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S050000
Reexamination Certificate
active
06737991
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention is based on a method for compressing data. In the run-length encoding method (RLE method), a method for data compression is already known in which no data loss occurs. This method is used for example with so-called PCX data. The aim of the method is to combine repeating data elements and to store them along with the number of repetitions. If the data elements are bytes made up of eight bits, then the compression occurs in such a way that bytes up to a value of 63 which do not repeat are stored uncompressed; the two highest bits must have the value 0. Bytes with a value between 64 and 255, as well as bytes between zero and 63 which repeat, are stored encoded in a data element made up of two bytes. In the first byte in this instance, the highest two bits are set equal to one. The subsequent bits indicate the repetition factor for the second byte. In this method, it is disadvantageous that for individual bytes with a value between 64 and 255, the storage space requirement is doubled. In an unfavorable case, compression using the RLE method can result in the required storage space being greater after compression than before compression. Also known for a data compression is the Lempel-Ziv algorithm, in which a data sequence to be compressed is tested for repetitions of partial sequences, repeating elements are stored in a code table, and the partial sequences are replaced by an assigned code symbol. A table of an unknown size must be set up for the decompression.
SUMMARY OF THE INVENTION
The method according to the invention, has the advantage over the prior art that the information as to whether a data element is stored in a compressed or uncompressed form is stored in another additional data element. This makes it possible to use the compression method according to the invention for all data elements, independent of their value, since no additional compression information must be contained in the individual data elements themselves. It is also advantageous to embody the compression as dependent upon preceding and subsequent data elements, since this permits a particularly effective compression.
It is particularly advantageous that multiple identical data elements that repeat in sequence with one another are counted and stored with a repetition factor in the manner according to the invention. The repetition factor can then assume a maximal value of the data element since the information as to whether the data element is stored in a compressed or uncompressed form is stored in a different data element. It is also advantageous to store the compressed or uncompressed data elements in a storage region provided for this and to store the data element, which contains the information as to which data elements have been stored in a compressed or uncompressed form, in a different storage region since this storage permits an effective access to the data elements. With sequences of data elements which exceed a predeterminable size, it is also advantageous to execute a storage in different data packets. As a result, even graphics which require a great deal of storage space can be broken dow into data packets whose size, for example, is optimally adapted to the sector size of a data storage medium or the data packet size is adapted for transmission via an interface or via the Internet, es.g. via e-mail.
It is also particularly advantageous to provide a method for decompression of the data elements which have been compressed according to the invention. The decompression method here has the advantage that the data elements stored in a first region contain information as to which of the data elements stored in the second region are stored in a compressed or uncompressed form. A simpler processing of the data in comparison to the prior art is thus possible because for example with the RLE method for PCX data, it is not possible for their to be a separation of this kind and the information as to whether a data element is stored in a compressed or uncompressed form is stored directly with this data element.
It is also advantageous to execute a decompression of a number of data packets connected to one another since this permits the data sequence extracted from the data packets to be arbitrary in size.
It is also advantageous to use the above-mentioned method preferably for compressing and decompressing image data. For decompression, it is advantageous to provide a device which is connected to a calculating unit and a display device. The decompression method, which is rapid and favorable in terms of required storage space, makes it possible to read information stored in a storage unit, where for example the storage unit is a part of the calculating unit, by means of a decompression unit and to display it with the aid of the display device. A particularly advantageous application is to provide the decompression device for a freely programmable combination instrument in a motor vehicle. Because in particular for the instrument display in a motor vehicle, a graphic depiction with the simplest structure possible must be chosen, if only for the sake of clarity. As a result of this simple structure of the image data to be displayed, repetitions of identical image elements and therefore also repetitions of identical data elements are particularly frequent. The compression and decompression method according to the invention can therefore be used in a particularly efficient manner. As a result, both the storage space requirement and the costs that it involves can be reduced for a freely programmable combination instrument. Furthermore, a relatively slow storage device is generally used for storing images in a freely programmable combination instrument. But with highly compressed images, the storage access time has significantly less effect than with images which are stored in an uncompressed form. With a sufficiently high processing speed and a slow storage device, compressed images can therefore be displayed faster than uncompressed images because these uncompressed images require a greater storage region.
It is also advantageous that a single bit is selected as a base element and determines whether a data element is stored in a compressed or uncompressed form. As a result, in the worst case scenario, the data quantity is only increased by one bit per uncompressed data element. By contrast, in the RLE method for PCX data mentioned in the prior art, an increase in the data quantity by one byte. i.e. by eight bits, occurs when data elements are stored in an uncompressed form. A temporary storage, e.g. in the form of a code table of the kind required with the Lempel-Ziv algorithm, is not required. Two registers are sufficient for the decompression: a first register for a data element to be decompressed and a second register for the data element which contains the information as to whether the data element in the first register is stored in a compressed form. An additional volatile memory is not required.
REFERENCES:
patent: 4586027 (1986-04-01), Tsukiyama et al.
patent: 4872009 (1989-10-01), Tsukiyama et al.
patent: 4937681 (1990-06-01), Fujinawa et al.
patent: 5805932 (1998-09-01), Kawashima et al.
patent: 5894588 (1999-04-01), Kawashima et al.
patent: 37 42 098 (1988-06-01), None
patent: 0 372 970 (1990-06-01), None
patent: 0 766 469 (1997-04-01), None
patent: 0 810 532 (1997-12-01), None
patent: 86/01660 (1986-03-01), None
patent: 96 11546 (1996-04-01), None
“Data Compression” Techniques and Applications Hardware and Software Considerations by Gilbert Held, A Wiley Heyden Publication, John Wiley & Sons, pp. 26-33., 1983.
Geisler Thomas
Meroth Ansgar
Lauture Joseph
Striker Michael J.
Tokar Michael
LandOfFree
Method and device for compressing and decompressing data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for compressing and decompressing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for compressing and decompressing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267230