Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
2002-10-24
2004-08-24
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
C341S067000
Reexamination Certificate
active
06781529
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to data processing systems using vector processing and Very Long Instruction Word (VLIW) architecture, more particularly to variable length encoding.
BACKGROUND OF THE INVENTION
A frame of image can be represented by a matrix of points referred to as pixels. Each pixel has one or more attributes representing the color associated with the pixel. Video streams are represented by consecutive frames of images. To efficiently store or transport image and video information, it is necessary to use data compression technologies to compress the data representing the attributes of each pixel of each frame of the images.
Various standards have been developed for representing image or video information in compressed formats, which includes Digital Video (DV) formats, MPEG2 or MPEG4 fomiats from Moving Picture Expert Group, ITU standards (e.g., H.261 or H.263) from International Telecomunication Union, JPEG formats from Joint Photographic Expert Group, and others.
Many standard formats (e.g., DV, MPEG2 or MPEG4, H.261 or H.263) use block based transform coding techniques. For example, 8×8 two-dimensional blocks of pixels are transformed into frequency domain using Forward Discrete Cosine Transformation (FDCT). The transformed coefficients are further quantized and coded using zero run length encoding and variable length encoding.
Zero run length encoding is a technique for converting a list of elements into an equivalent string of run-level pairs, where each non-zero eleiment (level) in the list is associated with a zero run value (run) which represents the number of consecutive elements of zero immediately preceding the corrusponding non-zero element in the list. After zero run length encoding, strings of zeros in the list are represented by zero run values associated with non-zero elements. For example, the non-zero elements and their associated zero run values can be interleaived into a new list to represent the original list of elements with strings of zeros.
Variable length coding is a coding technique often used for lossless data compressing. Codes of shorter lengths (e.g., Huffman codewords) are assigned to frequently occurring fixed-length data (or symbols) to achieve data compression. Variable length encoding is widely used in compression video data.
After the Forward Discrete Cosine Transformation and quantization, the frequency coefficients are typically reordered in a zigzag order so that the zero coefilcients are grouped together in a list of coefficients, which can be mnore effectively encoded using a zero run length encoding technique. The energy of a block of pixels representing a block of image is typically concentrated in the lower frequency area. When the coefficients are reordered in a zigzag order, the coefficients for the lower frequencies are located relatively before those for higher frequencies in the reordered list of coefficients. Thus, non-zero coefficients are more likely to concentrate in the front portion of the reordered coefficient list; and zero coefficients are more likely to concentrate in the end portion of the reordered list.
Since compressing images is a computational intensive operation, it is desirable to have highly efficient methods and apparatuses to perform run length encoding and variable length encoding.
SUMMARY OF THE DESCRIPTION
Methods and apparatuses for variable length encoding using a vector processing unit arc described here.
In one aspect of the invention, a method for execution by a microprocessor to perform variable length encoding including: receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded; generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols; generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords; and outputting the plurality of first codewvords and the plurality of lengths; where the above operations are perfonned in respionse to the microprocessor receiving a single instruction.
In one example according to this aspect, the plurality of parameters includes a plurality of indices; and to generate concurrently the plurality of first codewords, a plurality of entries are looked up simultaneously from a plurality of look up tables, which are configured from a plurality of look up units to function as the plurality of look up tables. Each of the look up tables utilizes more than one of the plurality of look up units. Each entry of the plurality of entries includes a first bit segment representing a second codeword and a second bit segment representing a bit length of the second codeword.
The plurality of parameters further includes a plurality ol sign indicators, each of which indicates the value of a sign bit of a corresponding one of the plurality of symbols. Each of the plurality of entries further includes a third bit segmnent indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols. A sign bit of a first symbol in the plurality of symbols, which corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.
The plurality of parameters further includes a plurality of type indicators for the plurality of symbols respectively; and the plurality of parameters and the plurality of entries are combined to generate the plurality of first codewords.
When one of the plurality of type indicators, which corresponds to a first symbol in the plurality of symbols, has a first value, a zero is generated as one of the plurality of first codewords to represent the first symbol.
The plurality of parameters further includes a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality ofsymbols.
When one of the plurality of type indicators, which corrcsponds to a first symbol in the plurality of symbols, has a second value, one of the plurality of third codewords is used as one of the plurality of first codewords to represent the first symbol.
When one of the plurality of type indicators, which corresponds to a first symbol in the plurality of symbols, has a third value, one of the plurality of first codewords that represents the first symbol is generated from concateinating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol.
The present invention includes apparatuses which perfonn these methods, including data processing systems which perform these methods, and cmputer readable media which when executed on data processing systems cause the systems to perform these methods.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follow.
REFERENCES:
patent: 3016527 (1962-01-01), Gilbert et al.
patent: 3675212 (1972-07-01), Raviv et al.
patent: 5173695 (1992-12-01), Sun et al.
patent: 5510852 (1996-04-01), Shyu
patent: 5740283 (1998-04-01), Meeker
patent: 5754186 (1998-05-01), Tam et al.
patent: 5768445 (1998-06-01), Troeller et al.
patent: 5798767 (1998-08-01), Poole et al.
patent: 5812791 (1998-09-01), Wasserman et al.
patent: 5844854 (1998-12-01), Lee
patent: 5875355 (1999-02-01), Sidwell et al.
patent: 5878267 (1999-03-01), Hampapuram et al.
patent: 5943058 (1999-08-01), Nagy
patent: 5946113 (1999-08-01), Pritchett
patent: 5963744 (1999-10-01), Slavenburg et al.
patent: 5974380 (1999-10-01), Smyth et al.
patent: 5990812 (1999-11-01), Bakhmutsky
patent: 6021420 (2000-02-01), Takamuki
patent: 6122690 (2000-09-01), Nannetti et al.
patent: 6122722 (2000-09-01), Slavenburg
patent: 6145077 (2000-11-01), Sidwell et al.
patent: 6195026 (2001-02-01), Acharya
patent: 620153
Lai Mike
Lin Chien-Hsin
Oslick Mitchell
Sarwar Mushtaq
Apple Computer Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Lauture Joseph
Young Brian
LandOfFree
Methods and apparatuses for variable length encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for variable length encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for variable length encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329386