Multiplex communications – Generalized orthogonal or special mathematical techniques – Fourier transform
Reexamination Certificate
1997-12-30
2002-06-04
Ton, Dang (Department: 2661)
Multiplex communications
Generalized orthogonal or special mathematical techniques
Fourier transform
C370S203000
Reexamination Certificate
active
06400680
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to data transformation of the inverse-fourier type such as, for example, an inverse discretecosine transformation. An input data block comprising frequency coefficients is transformed into an output data block comprising spatial coefficients. The invention also relates to a receiver in which a received data stream is subjected to various processing steps, one of the steps being a transformation of the inverse-fourier type. The received data stream may contain, for example, video information which has been coded in accordance with an MPEG standard.
BACKGROUND ART
U.S. Pat. No. 5,467,131 describes an inverse discrete-cosine transform (IDCT) implementation specifically for the decompression of JPEG, MPEG and Px64 encoded image and video data. A preprocessing step embedded in a Huffman decoding process classifies data blocks for sparseness. Each data block is defined as a sparse matrix H and is placed into one of the following classes based upon data occupancy within the data block:
type-0—only H[0,0] is non-zero;
type-1—only one of the H[i,j] is zero and H[
0,0] is zero;
type-2—only an upper 2×2 submatrix of H has nonzero values, where some or all of H[0,0], H[0,1], H[1,0] and H[1,1] are non-zero;
type-3—only an upper 4×4 submatrix of H has non-zero values, where some or all of H[i,j], i=0,1, . . . ,3, j=0,1, . . . ,3 are non-zero; and
type-4—H is not a member of any of the above-mentioned classes, where the occupancy pattern in H is random. The IDCT is based upon the data block classification. That is, pruned IDCTs are used for type-0,-1,-2 and -3 data blocks so as to reduce the total number of multiply and addition operations.
U.S. Pat. No. 5,467,131 describes a basic computation procedure for an inverse quantization and IDCT of an 8×8 data block. It requires 144 multiplication operations and 465 addition operations. For a type-0 or a type-1 8×8 data block, the multiply operation count is reduced to one multiply operation and the addition operation count is reduced to one addition operation. For a type-2 8×8 data block, the multiply operation count is reduced to 34 multiply operations and the addition operation count is reduced to 121 addition operations. For a type-3 8×8 data block, the multiply operation count is reduced to 61 multiply operations and the addition operation count is reduced to 253 addition operations. For a type-4 8×8 block, the basic computation procedure is applied. There are no savings in the number of required multiply and addition operations.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a transformation of the above-identified type which allows a greater variety of input data blocks to be transformed into output data blocks with relatively little computational effort.
The invention takes the following aspects into consideration. Any given data block may be regarded as a linear combination of various basic data blocks each of which has a certain weighing factor. With regard to this, a transformation from the frequency domain to the spatial domain has the following property. If the basic data blocks are transformed individually and thereafter linearly combined using identical weighing factors, the result will be identical to the transformation of the given data block itself.
The transformation of an input data block in which all frequency-coefficients but one are zero, results in an output data block having spatial coefficients which follow a certain two-dimensional pattern. The pattern depends on the position in the input data block of the frequency coefficient which is not zero, but does not depend on the value of that frequency coefficient.
In accordance with the invention, an input data block transformed as follows. For each frequency coefficient which is not zero, an individual block of spatial coefficients is established on the basis of pre-stored data pertaining to a two-dimensional pattern associated to the frequency coefficient. The individual block of spatial coefficients may be, for example, the output data block which would be obtained if all other frequency coefficients in the input data block were zero. The individual blocks of spatial coefficients are accumulated to obtain the output data block.
It requires relatively little or no computational effort to provide the individual block of spatial coefficients for a certain frequency coefficient on the basis of the pre-stored data. For example, the pre-stored data may be the individual block of spatial coefficients itself in which case a simple read operation is sufficient to provide the individual block of spatial coefficients. As an other example, the pre-stored data may comprise a basic pattern associated to the frequency coefficient. In that case, the individual block of spatial coefficients can be obtained by copying the basic pattern which requires relatively little computational effort. In addition, it requires relatively little computational effort to accumulate the individual blocks of spatial coefficients. Thus, in the invention, an input data block can be transformed with relatively little computational effort.
In the invention, the computational effort which is required to transform an input data block increases substantially proportionally with the number of frequency coefficients which are not zero, whereas, in the background art, the computational effort increases to a much greater extent. Moreover, in the background art, an input data block can only be transformed with relatively little computational effort if non-zero frequency coefficients are located in a particular region. For example, let it be assumed that an input data block contains few non-zero coefficients which are located in the lower right portion of the input data block. In the background art, the input data block will be classified as type-4 and, cosnsequently, a relatively great computational effort is used to obtain the output data block. In the invention, the computational effort which is required to transform an input data block having a certain number of non-zero frequency coefficients, in principle, does not depend on where the non-zero frequency coefficients are located. For this reason, and because the computational effort increases with the number of non-zero frequency coefficients to a relatively small extent only. Consequently, the invention allows a greater variety of input data blocks to be transformed with relatively little computational effort.
The invention may be applied to advantage in a receiver in which a received data stream is subjected to a transformation of the inverse-fourier type such as, for example, an inverse discrete-cosine transformation. In practical applications, the transformation is carried out on successive blocks of data comprised in, or derived from, the received data stream. The transformation of a data block has to be carried out within a certain period of time to keep in pace with the rate at which new data blocks become available. Since, the invention allows a relatively great variety of data blocks to be transformed with relatively little computational effort, the transformation can be completed, on average, within relatively few clock cycles. Consequently, for a given clock frequency, the invention allows data blocks to be processed at a relatively high rate and, thus, the invention allows reception of data stream having relatively high bit rates. Alternatively, for a given data rate, the invention allows the transformation to be carried out at a relatively low clock frequency which contributes to a modest power consumption and to an interference-free operation.
The invention may be also applied to advantage in a data-processing arrangement which carries out a transformation of input data blocks comprising frequency coefficients into output data blocks comprising spatial coefficients. In practice, the number of operations which the data-processing arrangement can carry
Gross Russell
Nguyen Brian
Ton Dang
LandOfFree
Data transformation of the inverse-fourier type does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data transformation of the inverse-fourier type, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data transformation of the inverse-fourier type will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2913558