Programmable variable-length decoder

Details Programmable variable-length decoder Programmable variable-length decoder

2002-11-12

2004-08-03

Tokar, Michael J. (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Coding by table look-up techniques

C341S067000

Reexamination Certificate

active

06771196

ABSTRACT:

INCORPORATION BY REFERENCE OF RELATED APPLICATIONS
The following U.S. patent applications are related to the present application and are hereby specifically incorporated by reference: patent application Ser. No. 10/114,798, entitled “VIDEO DECODING SYSTEM SUPPORTING MULTIPLE STANDARDS”; patent application Ser. No. 10/114,679, entitled “METHOD OF OPERATING A VIDEO DECODING SYSTEM”; patent application Ser. No. 10/114,797, entitled “METHOD OF COMMUNICATING BETWEEN MODULES IN A DECODING SYSTEM”; patent application Ser. No. 10/114,886, entitled “MEMORY SYSTEM FOR VIDEO DECODING SYSTEM”; patent application Ser. No. 10/114,619, entitled “INVERSE DISCRETE COSINE TRANSFORM SUPPORTING MULTIPLE DECODING PROCESSES”; and patent application Ser. No. 10/113,094, entitled “RISC PROCESSOR SUPPORTING ONE OR MORE UNINTERRUPTIBLE CO-PROCESSORS”; all filed on Apr. 1, 2002. The following Provisional U.S. Patent Applications are also related to the present application and are hereby specifically incorporated by reference: Provisional Patent Application No. 60/369,144, entitled “VIDEO DECODING SYSTEM HAVING A PROGRAMMABLE VARIABLE LENGTH DECODER”; Provisional Patent Application No. 60/369,210 entitled “DMA ENGINE HAVING MULTI-LEVEL COMMAND STRUCTURE”; and Provisional Patent Application No. 60/369,217, entitled “INVERSE QUANTIZER SUPPORTING MULTIPLE DECODING PROCESSES”; all filed on Apr. 1, 2002.
FIELD OF THE INVENTION
The present invention relates generally to video decoding systems, and, more particularly, to variable-length decoding.
BACKGROUND OF THE INVENTION
Generally, large amounts of data being compressed and decompressed for numerous reasons, including transmission, storage, retrieval, and processing use at some stage means of variable-length coding, such as Huffman coding. Huffman coding was originally disclosed by D. A. Huffman in an article “A Method for the Construction of Minimum Redundancy Codes” Proc. IRE, 40: 1098, 1952. Huffman coding is a widely used technique for lossless data compression that achieves compact data representation by taking advantage of the statistical characteristics of the source. The Huffman code is a prefix-free variable-length code that assures that a code is uniquely decodable. In Huffman code, no codeword is the prefix of any other codeword. The run-length processed data are often subsequently coded by variable-length coding for further data compression.
Variable-length encoding allocates codes of different lengths to different input data according to the probability of occurrence of the input data, so that statistically, more frequent input codes are allocated shorter codes than the less frequent codes. The less frequent input codes are allocated longer codes. The allocation of codes may be done either statically or adaptively. For the static case, the same output code is provided for a given input datum, no matter what block of data is being processed. For the adaptive case, output codes are assigned to input data based on a statistical analysis of a particular input block or set of blocks of data, and possibly changes from block to block (or from a set of blocks to a set of blocks).
The combination of run-length coding and Huffman coding has been adopted in most compression/decompression standards. However, every standard has its own Huffman tables and run-length definitions. In principle, a programmable decoding table could be implemented by a random access memory (RAM) unit. However, it would require a 2{circumflex over ( )}16 word RAM (if the longest length of a codeword is 16 bits) which would be very wasteful. It is much more efficient to use a content addressable memory (CAM) whose sizes are determined only by the number of codebook entries. However, if it were implemented by CAM, it would result in a circuit much larger and complicated than a circuit using only a small RAM. Thus there is a need for a simple and flexible variable-length decoder that can speedily and efficiently decode variable length codes of varying standards.
Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art through comparison of such systems with the present invention, as set forth in the remainder of the present application with reference to the drawings.
SUMMARY OF THE INVENTION
One aspect of the present invention is directed to a data decoding system having a variable-length decoder (VLD) and an external memory unit. The variable-length decoder includes an address generator and a local memory unit. The address generator receives data from the data stream and generates a memory address at which to search for a codeword match in a VLD look-up table. The local memory unit stores at least a portion of the VLD look-up table. The external memory unit is external to the variable-length decoder and stores a portion of the VLD look-up table if the VLD look-up table does not fit entirely within the local memory unit.
Another aspect of the present invention is directed to a method of decoding a variable-length code data stream. Pursuant to the method, a base memory address is set equal to a start address. Then the next n bits in the data stream are retrieved. A memory location having an address equal to the sum of the base address, plus the value of the n retrieved bits, is accessed. The memory location includes status data indicating whether a codeword from the data stream is matched with its corresponding information. Each memory location that represents a codeword match includes the corresponding information. Each memory location that does not include a codeword match includes an offset value. If a codeword is matched with its corresponding information, the corresponding information is output, the base address is set equal to the start address, and the data in the data stream is shifted by a number of the retrieved bits that correspond to the outputted information. If a codeword is not matched with its corresponding information, the base address is set according to the offset value, and the data in the data stream is shifted n bits. This process, beginning with the retrieval of the next n bits in the data stream, is iteratively repeated.
Another aspect of the present invention is directed to another method of decoding a variable-length code data stream. Pursuant to this method, a first memory element is designated a memory element to be searched. Then the next n bits in the data stream are retrieved. A designated memory location in the memory element to be searched is accessed. The memory location includes status data indicating whether a codeword from the data stream is matched with its corresponding information. Each memory location that represents a codeword match includes the corresponding information. Each memory location that does not include a codeword match includes a next-search-location indicator indicating a memory element at which to perform the next search. If a codeword is matched with its corresponding information, the corresponding information is output, the first memory element is designated the memory element to be searched, and the data in the data stream is shifted by a number of the retrieved bits that correspond to the outputted information. If a codeword is not matched with its corresponding information, the memory element indicated by the next-search indicator is designated the memory element to be searched, and the data in the data stream is shifted n bits. This process, beginning with the retrieval of the next n bits in the data stream, is iteratively repeated.
It is understood that other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein embodiments of the invention are shown and described only by way of illustration of the best modes contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modification in various other respects, all without departing from the spirit and scope of the

Affiliated with

Also associated with

Rating

Programmable variable-length decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Programmable variable-length decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable variable-length decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3313224