Multiple Technique Entropy Coding System And Method

Abstract

A system, method and computer program product having optimal matching to a known or measured probability distribution encodes data without the use of an excessively large lookup table. An encoder constructed according to the present invention uses two or more different encoding methods in combination. In one embodiment, Huffman coding by table lookup is combined with computational generation, such as by using an exponential Golomb equation. The most commonly occurring elements are looked up in a small Huffman table, while the remaining elements are coded with the equation. In another embodiment, data is encoded using two or more equations. In yet another embodiment, data is encoded using multiple tables in conjunction with one or more equations.

Description

RELATED APPLICATIONS[0001]The present application is a continuation of U.S. patent application Ser. No. 11 / 232,726, filed Sep. 21, 2005. The present application also claims priority from provisional applications filed Sep. 21, 2004 under U.S. Patent Application No. 60 / 612,311 entitled RATE CONTROL WITH VARIABLE SUBBAND QUANTIZATION; filed Sep. 22, 2004 under U.S. Patent Application No. 60 / 612,652 entitled SPLIT TABLE ENTROPY CODING; filed Sep. 22, 2004 under U.S. Patent Application No. 60 / 612,651 entitled PERMUTATION PROCRASTINATION; filed Oct. 12, 2004 under U.S. Patent Application No. 60 / 618,558 entitled MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCHITECTURE; filed Oct. 13, 2004 under U.S. Patent Application No. 60 / 618,938 entitled VIDEO MONITORING APPLICATION, DEVICE ARCHITECTURES, AND SYSTEM ARCHITECTURE; filed Feb. 16, 2005 under U.S. Patent Application No. 60 / 654,058 entitled MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCH...

AI Technical Summary

Benefits of technology

[0031]According to one aspect of the invention, Huffman coding by table lookup is combined with computational codeword generation, such as by using an exponential Golomb equation. The most commonly occurring elements are looked up in a small Huffman table, while the remaining elements are coded with the equation. This arrangement offers the advantages of Huffman coding by table lookup (namely, optimum matching to-a known or measured probability distribution) combined with the advantages of simple computed coding (namely, quick computation with no lookup) while avoiding the disadvantage of full Huffman coding (namely, the need to support a very large table).

Problems solved by technology

Unfortunately, most wavelet implementations use very complex algorithms, requiring a great deal of processing power, relative to DCT alternatives.

In addition, wavelets present unique challenges for temporal compression, making 3D wavelets particularly difficult.

For these reasons, wavelets have never offered a cost-competitive advantage over high volume industry standard codecs like MPEG, and have therefore only been adopted for niche applications.

Existing video coding standards and digital signal processors put even more strain on the battery.

However, in other implementations, random access to a large table is either relatively slow (because of cache memory loading) or relatively expensive (because of the cost of on-chip memory, as in an FPGA or ASIC).

However, in other implementations, multiple steps of computation may be needed and are relatively slow.

In video compression work, the probability distribution of quantized coefficients can sometimes be awkward.

In other words, the distribution is not one with a known fast computational encoding, but the number of possible values requires a codebook too large to fit in the available lookup storage.

Images