Vector handling capable processor and run length encoding

Details Vector handling capable processor and run length encoding Vector handling capable processor and run length encoding

2002-10-24

2004-08-24

Williams, Howard L. (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from bit count codes

C341S065000, C708S210000

Reexamination Certificate

active

06781528

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 run 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 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 run length encoding using a vector processing unit are described here.
In one aspect of the invention, a method for execution by a microprocessor in response to the microprocessor receiving a single instruction includes: receiving a first list of a plurality of elements from a first vector register; generating a plurality of run values respectively for the first list of elements, at least one of the plurality of run values indicating the number of consecutive elements of a first value immediately preceding the corresponding element in the first list; and outputting the plurality of run values into a second vector register; where the above operations are performed in response to the microprocessor receiving the single instruction. In one example according to this aspect, the method further includes: receiving a second element before generating the plurality of run values. The second element indicates the number of consecutive elements of the first value immediately preceding a first element in a second list of elements, in which the first element immediately precedes the first list of elements. Each of the plurality of run values indicates the number of consecutive elements of the first value in the second list immediately preceding a corresponding element in the second list. In one example, the first value is zero; and the instruction is for computing zero run values of a vector of elements in a list of elements.
In another aspect of the invention, a method to perform zero run length encoding includes: computing the run value of the last element of a list of elements; computing a first index pointing to the fast non-zero element in the list from an index indicating the number of elements in the list and the run value of the last element; and processing elements of the list to zero run length encode the list of elements until the last non-zero element indicated by the first index is zero run length encoded without going through elements located after the last non-zero element in the list. Methods according to this aspect can be used in encoding images stream in accordance with MPEG2, MPEG4, DV, H.261, H.263 and other standards.
The present invention includes apparatuses which perform these methods, include 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: 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: 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: 6298438 (2001-10-01), Thayer et al.
patent: 6529554 (2003-03-01), Craver
patent: 2003/0146858 (2003-08-01), Chen et al.
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.
AltiVec Technology, Programming Interface Manual, Motorola, Rev. 0, Jun. 1999, p. 4-84.
AltiVec Technology, Programming Environments Manual, Motorola, Rev. 0, Nov. 1998, pp. 1-1—1-12, p. 6-113.

Affiliated with

Also associated with

Rating

Vector handling capable processor and run 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 Vector handling capable processor and run length encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vector handling capable processor and run length encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3323334