Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-15
2001-02-13
Ngo, Ohuong Dinh (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S402000
Reexamination Certificate
active
06189021
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method for performing discrete cosine transform (DCT) and its inverse, more particularly to a method for performing two-dimensional DCT/IDCT involving a reduced number of multiplication operations.
2. Description of the Related Art
U.S. Pat. No. 5,471,412 by the applicant discloses a discrete cosine transform (DCT) and an inverse discrete cosine transform (IDCT) method and apparatus that use six-stage DCT/IDCT fast algorithms to process a sequence of input data of an 8×8 data block. The six stages of the DCT/IDCT fast algorithms generally consist of interleaved butterfly operation stages and multiplication operation stages. The multiplication operation stages include intrinsic multiplication operations, post-addition multiplication operations, and post-multiplication subtraction operations. In the aforementioned U.S. Patent, the entire disclosure of which is incorporated herein by reference, a single butterfly operation unit performs the butterfly operation stages, while a single multiplication operation unit performs the multiplication operation stages. The butterfly operation unit and the multiplication operation unit operate in a recycling and parallel processing manner so that DCT and IDCT can be achieved efficiently with a relatively inexpensive hardware cost.
FIGS. 1 and 3
respectively illustrate flow graphs of the six-stage DCT and IDCT fast algorithms employed in the aforesaid U.S. patent. The DCT fast algorithm uses three kinds of arithmetic operations: butterfly, intrinsic multiplication, and post-addition multiplication, as shown in
FIGS. 2A
to
2
C. The IDCT fast algorithm also uses three kinds of arithmetic operations: butterfly, intrinsic multiplication, and post-multiplication subtraction, as shown in
FIGS. 2A
,
2
B and
2
D.
Referring again to
FIG. 1
, the six stages of the DCT fast algorithm include a first stage involving four butterfly operations, a second stage involving two post-addition multiplication operations, a third stage involving four butterfly operations, a fourth stage involving three post-addition multiplication operations, a fifth stage involving four butterfly operations, and a sixth stage involving eight intrinsic multiplication operations.
Referring to
FIG. 3
, the six stages of the IDCT fast algorithm include a first stage involving eight intrinsic multiplication operations, a second stage involving four butterfly operations, a third stage involving three post-multiplication subtraction operations, a fourth stage involving four butterfly operations, a fifth stage involving two post-multiplication subtraction operations, and a sixth stage involving four butterfly operations.
In general, multiplication operations for DCT/IDCT are relatively time-consuming and require relatively complex hardware. Although the aforementioned U.S. Patent employs a fast algorithm that involves only thirteen multiplication operations for one-dimensional transformation, or a total number of 208 (2×8×13) multiplication operations for two-dimensional transformation of an 8×8 data block, it is desirable to further reduce the number of multiplication operations in order to achieve a higher processing speed.
SUMMARY OF THE INVENTION
Therefore, the object of the present invention is to provide a method for performing two-dimensional DCT/IDCT involving a reduced number of multiplication operations.
According to one aspect of the present invention, there is provided a two-dimensional discrete cosine transform (DCT) method involving consecutive first and second one-dimensional DCT operations. Each of the first and second one-dimensional DCT operations uses a six-stage DCT fast algorithm to process a sequence of input data of an 8×8 data block so as to generate a sequence of transform data. The DCT fast algorithm includes first, third and fifth stages that involve a plurality of butterfly operations, second and fourth stages that involve a plurality of post-addition multiplication operations, and a sixth stage that involves a plurality of intrinsic multiplication operations. The two-dimensional DCT method comprises the steps of:
(a) providing an input unit to receive the input data;
(b) controlling the input unit to provide the input data to a butterfly operation unit in order to enable the butterfly operation unit to perform the first stage of the DCT fast algorithm for the first one-dimensional DCT operation;
(c) controlling a data register unit to store first-stage output data from the butterfly operation unit therein;
(d) controlling the data register unit to provide predetermined ones of the first-stage output data to a multiplication operation unit in order to enable the multiplication operation unit to perform the second stage of the DCT fast algorithm when the predetermined ones of the first-stage output data have been stored in the data register unit;
(e) controlling the data register unit to store second-stage output data from the multiplication operation unit therein;
(f) controlling the data register unit to provide the first-stage and second-stage output data in a predetermined sequence to the butterfly operation unit in order to enable the butterfly operation unit to perform the third stage of the DCT fast algorithm after the butterfly operation unit has finished performing the first stage of the DCT fast algorithm;
(g) controlling the data register unit to store third-stage output data from the butterfly operation unit therein;
(h) controlling the data register unit to provide predetermined ones of the third-stage output data to the multiplication operation unit in order to enable the multiplication operation unit to perform the fourth stage of the DCT fast algorithm when the predetermined ones of the third-stage output data have been stored in the data register unit;
(i) controlling the data register unit to store fourth-stage output data from the multiplication operation unit therein;
(j) controlling the data register unit to provide the third-stage and fourth-stage output data in a predetermined sequence to the butterfly operation unit in order to enable the butterfly operation unit to perform the fifth stage of the DCT fast algorithm after the butterfly operation unit has finished performing the third stage of the DCT fast algorithm;
(k) controlling the data register unit to store fifth-stage output data from the butterfly operation unit therein, the fifth-stage output data serving as scaled one-dimensional transform data;
(l) controlling the data register unit to provide a transposed order of the scaled one-dimensional transform data to the butterfly operation unit in order to enable the butterfly operation unit to perform the first stage of the DCT fast algorithm for the second one-dimensional DCT operation;
(m) repeating steps (c) to (j) to perform the second to fifth stages of the DCT fast algorithm for the second one-dimensional DCT operation;
(n) controlling the data register unit to store the fifth-stage output data from the butterfly operation unit therein, the fifth-stage output data serving as scaled two-dimensional transform data;
(o) controlling the data register unit to provide the scaled two-dimensional transform data to the multiplication operation unit in order to enable the multiplication operation unit to perform the sixth stage of the DCT fast algorithm for the second one-dimensional DCT operation based on a set of scaled weighing coefficients stored in a coefficient ROM of the multiplication operation unit, thereby resulting in the two-dimensional transform data corresponding to the input data, the scaled weighing coefficients being a product of sixth-stage weighing coefficients of the DCT fast algorithms for the first and second one-dimensional DCT operations; and
(p) controlling an output unit to receive the two-dimensional transform data from the multiplication operation unit.
According to another aspect of the present invention, there is provided a two-dimensional inverse discrete cosine transform (IDCT) method invo
Christensen O'Connor Johnson & Kindness PLLC
Ngo Ohuong Dinh
Winbond Electronics Corp.
LandOfFree
Method for forming two-dimensional discrete cosine transform... 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 for forming two-dimensional discrete cosine transform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for forming two-dimensional discrete cosine transform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2613205