Coded data generation or conversion – Digital code to digital code converters – To or from particular bit symbol
Reexamination Certificate
2002-05-07
2004-07-13
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from particular bit symbol
Reexamination Certificate
active
06762700
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of lossless data compression and storage. In particular, the method and system of this invention improve the efficiency of communication as well as signal processing. The coding method of this invention is variable length coding method.
2. Description of the Related Art
Arithmetic coding is one of the most successful methods in this field. It offers a simple way to approach a good compression ratio. However, there are some drawbacks to using arithmetic coding. First, it takes several arithmetic operations to encode one single symbol. This leads to massive calculation while processing compression since the today's data generally contains millions of symbols. It is obvious that the compression will take longer if there are too many arithmetic operations—especially multiplications or divisions. Recently, much research focused on this problem recently. Some research has tried to reduce the number of operations without too much loss of compression performance. The other drawback to arithmetic coding is the floating point precision problem. After an long sequence floating point multiplications (or divisions), the result can only be expressed by a high precision floating point number. This demand really constrains some software and hardware design. Finally, if there is any error or loss during the process of compressing data by arithmetic coding, we can hardly recover the rest of the data. This is a really intractable but unavoidable situation when we transmit data via media.
There are many researchers focusing their efforts to solve these problems. However, it is not easy to balance these problems with high performance results due to the nature of arithmetic coding. Unlike the arithmetic coding method, this invention uses non-increasing order coding instead of interval coding. It introduces the non-increasing encoding order (hereafter: NEO) method to encode a set of data items in a non-increasing encoding length order to achieve a high compression ratio. Moreover, the major operations for this method are addition, bit-wise and comparison on integers. All of these operations are very efficient in software or hardware implementation. Also the compression system of this invention encodes input data block by block. It is highly appreciated in parallel processing and communication.
BRIEF SUMMARY OF THE INVENTION
The invention introduces the NEO method, which uses a non-increasing encoding length to encode a set of data values. Also it includes many variations to improve the performance of the NEO method. One modified method uses a shorter encoding length with a flag bit to achieve more efficient compression. Others focus on how to reduce the range of values of the sequence to reduce the encoding length. High compression performance is one advantage of the method. Low use of multiplications and divisions (avoiding them is possible) is another advantage of the method. Its major operations are addition, bit-wise and comparison on integers. Therefore, the run time for the compression or decompression is fast. Another contribution of the method is that it doesn't require floating point precision. That is, the NEO method can easily adapt to different platforms or devices. However, for variable length coding, it needs a method to delimit each encoded string. This is another aspect of this invention. The delimitation method employs both headers and end-of-string symbols to help the decoder avoiding any loss in the decoding stage.
Another object of this invention is to provide a lossless compression system which employs NEO method. The compression system separates input data into several blocks. For each data block, it separates the block into binary strings with equal size. The size of these strings is determined by the frequency of the LPS (less probable symbol) in this block. It then encodes the positions of the LPS of each string with the NEO method.
REFERENCES:
patent: 6420980 (2002-07-01), Ejima
LandOfFree
NEO method and system for lossless compression and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with NEO method and system for lossless compression and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NEO method and system for lossless compression and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3188934