Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2002-10-24
2004-03-16
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S050000
Reexamination Certificate
active
06707397
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 the concatenation of codewords of variable length.
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 formats from Moving Picture Expert Group, ITU standards (e.g., H.261 or H.263) from International Telecommunication 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 element (level) in the list is associated with a zero run value (run) which represents the number of consecutive elements of zero immediately preceding the corresponding 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 interleaved 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 coefficients are grouped together in a list of coefficients, which can be more 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 concatenating codewords of variable lengths using a vector processing unit are described here.
In one aspect of the invention, a method for execution by a microprocessor to concatenate codewords of variable lengths includes: receiving a plurality of codewords from a first vector register; receiving a plurality of lengths representing bit lengths of the plurality of codewords respectively; generating a first bit stream from concatenating the plurality of codewords; summing the plurality of lengths to generate the bit length of the first bit stream; and outputting the first bit stream and the first length; wherein the above operations are performed in response to the microprocessor receiving a single instruction.
In one example according to this aspect, summing the plurality of lengths is performed concurrently while generating the first bit stream. The plurality of lengths are received from the first vector register; and the first bit stream and its bit length are output into a vector register. A plurality of indicators are generated, each of which indicates whether or not a corresponding one of the plurality of lengths is zero. Each of the plurality of indicators is stored in a bit in a condition register. In one example, generating the plurality of indicators is also performed concurrently while generating the first bit stream.
The present invention includes apparatuses which perform these methods, including data processing systems which perform these methods, and computer 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: 5343540 (1994-08-01), Mitani
patent: 5446916 (1995-08-01), Derovanessian et al.
patent: 5510852 (1996-04-01), Shyu
patent: 5652583 (1997-07-01), Kang
patent: 5675331 (1997-10-01), Watanabe et al.
patent: 5740283 (1998-04-01), Meeker
patent: 5754186 (1998-05-01), Tam et al.
patent: 5768445 (1998-06-01), Troeller et al.
patent: 5781134 (1998-07-01), Son
patent: 5798767 (1998-08-01), Poole et al.
patent: 5812791 (1998-09-01), Wasserman et al.
patent: 5844854 (1998-12-01), Lee
patent: 5857088 (1999-01-01), Keith et al.
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: 5973627 (1999-10-01), Bakhmutsky
patent: 5974380 (1999-10-01), Smyth et al.
patent: 5990812 (1999-11-01), Bakhmutsky
patent: 6012077 (2000-01-01), Tai
patent: 6021420 (2000-02-01), Takamuki
patent: 6122690 (2000-09-01), Nannetti et al.
patent: 6122722 (2000-09-01), Slavenburg
patent: 6133859 (2000-10-01), Deygas et al.
patent: 6145077 (2000-11-01), Sidwell et al.
patent: 6195026 (2001-02-01), Acharya
patent: 6201530 (2001-03-01), Thadani et al.
patent: 6219457 (2001-04-01), Potu
patent: 6232990 (2001-05-01), Poirion
patent: 6246347 (2001-06-01), Bakhmutsky
patent: 6332188 (2001-12-01), Garde et al.
patent: 6339386 (2002-01-01), Cho
patent: 6389171 (2002-05-01), Washington
patent: 6437712 (2002-08-01), Aoki
patent: 6501398 (2002-12-01), Toyokura
Linley Gwennap, “MediaGX Targets Low-Cost PCs”,Microprocessor Report,vol. 11, No. 3, Mar. 10, 1997, pp. 1-8.
Proposed SMPTE Standard for Television, SMPTE 314M,pp. 1-46, 2001.
AltiVec Technology, Programming Interface Manual,Motorla, Rev. 0, Jun. 1999, p. 4-84.
AltiVec Technology, Programming Environments Manual,Motorla, Rev. 0, Nov. 1998, p. 1-1-1-12, p. 6-113.
Apple Computer Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Jean-Pierre Peguy
LandOfFree
Methods and apparatus for variable length codeword... 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 apparatus for variable length codeword..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for variable length codeword... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231286