Coded data generation or conversion – Digital code to digital code converters – To or from run length limited codes
Reexamination Certificate
2002-05-10
2004-05-18
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from run length limited codes
C341S063000, C341S067000
Reexamination Certificate
active
06737993
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to manipulating data, for example for encoding or decoding digital video signals.
It is becoming increasingly common for video signals to be transmitted or stored in a digital, rather than an analog, format. Digital video signals are usually compressed before transmission or storage (using a standard compression system such as MPEG-2, H.261 or H.263) and decompressed before playback. Several video compression standards use block-format video encoding, in which the pixels of the image to be compressed are split into blocks of adjacent pixels and each block is then compressed by a series of steps. This is efficient because most naturally-occurring images have areas which look fairly uniform and when compressing the image in this way the local uniformity reduces the amount of data needed to describe the image.
The first step of a typical block-format compression process is to split the image into smaller component blocks of adjacent pixels. Typically, the image is split into macroblocks (MBs), which consist of 256 pixels in a 16×16 array. The image in a macroblock is characterised by a luminance value (Y) for each pixel and two chrominance values (U and V) which in what is known as the 4:2:0 format (as used in many video compression standards), are each in an 8×8 array. Thus in this format each chrominance sampling point covers four luminance pixels (see FIG.
1
). The main purpose of splitting the image in this way is to make the job of spatial compression easier; only a small section of the image needs to be examined, and so the task—although less efficient—is less complicated.
The technique usually used next is a discrete cosine transform (DCT). This works in much the same way as the Fourier transform, but in two dimensions on a set of pixels. Each coefficient in the DCT output represents a wave in the pixel domain, with the amplitude determined by the value of the coefficient, and the frequency in both dimensions determined by the position in the coefficient matrix. Moving to the right or the bottom of the DCT coefficient matrix increases the frequency of this wave. A superposition of a number of these waves leads to a reconstruction of the original image.
At this point, compression can begin on each DCTed luminance and chrominance matrix by removing some of the coefficients from the matrix, and quantising others. This leads to inaccuracies in the reconstituted image (lossy compression) but this is often acceptable, and the resulting matrix is easier to compress since it contains less information.
Another refinement to the compression process is the use of run-length encoding. This is a useful way of compressing sparse matrices. The technique involves thinking of the matrix as a long string of data, much as would be the case in a computer's memory. Run-length encoding (RLE) then describes that string as a number indicating the number of zero bytes (on in general the length of a series of zeroes), followed by a non-zero data element, followed by a number indicating the length of a series of zeroes, followed by a non-zero data element, and so on. (See FIG.
2
).
To improve compression yet further, these RLE strings are Huffman-encoded. Huffman encoding consists of expressing some data item as a symbol—in this case, the number of zeroes (the run-length) followed by the data item. Huffman encoding relies on previous knowledge of the probability of occurrence of a particular symbol, such that the most likely symbols are encoded with fewer bits than the original, whereas the least likely symbols are encoded with more bits than the original. With sufficient knowledge of the likely data set, the number of bits required to represent that set are reduced, since the most frequently occurring symbols are represented in a small number of bits.
The success of a Huffman encoder relies on the predictability of its input data. In the example of the block of DCT coefficients outlined above, a raster scanning mechanism does not give particularly predictable data since the values tend to cluster in the top-left corner of the matrix (the low-frequency area). Thus scanning the first few lines will tend to give a data burst, followed by a few zeroes, followed by a slightly shorter data burst, followed by a few more zeroes, and so on. It is more efficient to group the non-zero data together, leading to a more predictable run-length, and so better Huffman compression. This is achieved by zigzag scanning, as illustrated in FIG.
3
.
The zigzag scanned data is then Huffman encoded, so a simplified I-frame (spatial only) compression method could be summarised as the steps shown in FIG.
4
.
In order to perform real-time video compression or decompression there is a need to perform these steps very quickly.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method for run-length encoding two or more data values, the method comprising: loading the data values into storage by forming a first data string, the data string comprising a plurality of data sub-strings and each data sub-string representing at least one of the data values; generating a second data string having a data sub-string corresponding to each data sub-string of the first data string, all the bits of each of the data sub-strings of the second data string having a first predetermined value if all the bits of the corresponding data sub-string of the first data string have a second predetermined value and having a third predetermined value if any of the bits of the corresponding data sub-string of the first data string has other than the second predetermined value; starting from a predetermined end of the second data string, counting the number of consecutive bits of the second data spring having the first predetermined value; and dividing the said number by the number of bits in each data sub-string.
Preferably, the first predetermined value is zero. Preferably the second predetermined value is zero. Preferably the third predetermined value is one. Preferably the first and second values are equal.
The data strings are preferably of a predetermined length, for instance 32, 64 or 128 bits. The data-sub-strings in each data string are preferably of equal length, for instance 8, 16 or 32 bits. Each data string is suitably stored in a register in which, preferably, the sub-strings are not individually accessible or addressable. Preferably the data sub-strings all have the same length. All the data sub-strings are suitably at least two bits long.
Preferably some or all of the steps of the method are performed by executing one or more data processing instructions, suitably in a computer. The computer preferably has processing means, comprising one or more processors, and memory. The instructions are preferably capable of being executed by dedicated apparatus (software or hardware) in the computer. The memory preferably comprises a data memory for storing the data strings, most preferably in the form of registers in which the sub-strings are suitably not individually accessible, and program memory for storing a series of instructions for the processor(s) to execute the desired method. The processor(s) preferably include dedicated hardware and/or software for performing one or more of the instructions. The instructions may include an instruction to perform the said step of generating the second data string. The step of generating the second data string is preferably performed by executing an instruction to compare the first data string with a third data string all of whose bits are of the second predetermined value. The step of dividing is preferably performed by executing a bit shift instruction.
In a further step of the method, there is preferably a step of generating a fourth data string by masking the first data string with the second data string.
The method is preferably for data compression.
Other operations may be performed during the execution of the method.
Preferably the series of data values represents a matrix (suitably a square matrix) of dat
Jorgenson Lisa K.
Mai Lam
Morris James H.
STMicroelectronics Limited
Tokar Michael
LandOfFree
Method and apparatus for run-length encoding data values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for run-length encoding data values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for run-length encoding data values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241672