Apparatus and method for fast discrete cosine transform with...

Details Apparatus and method for fast discrete cosine transform with... Apparatus and method for fast discrete cosine transform with...

2000-01-05

2004-05-25

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06742009

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus and a method for carrying out a fast discrete cosine transform (to be called DCT below) with same positions of input and output data, and also relates to a recording medium which is readable by a computer with a program loaded thereon. Particularly, the present invention relates to an apparatus and a method for carrying out a fast discrete cosine transform with same positions of input and output data, and also relates to a recording medium readable by a computer with a program loaded thereon, in which in the case where a one-dimensional or two-dimensional forward or inverse discrete cosine transform is used for converting or inverse-converting digital signals, the required arithmetic amount is effectively reduced, and the positions of the input and output data are same, thereby making an additional memory needless.
2. Description of the Prior Art
Conventionally, there have been fast arithmetic methods for realizing one-dimensional and two-dimensional forward and inverse DCT. That is, there is U.S. Pat. No. 5,831,881 entitled “Method and Circuit for Forward/Inverse Discrete Cosine Transform” issued on Nov. 3, 1998 to Fiedrich et al. Further, there is U.S. Pat. No. 5,719,963 entitled “Two-Dimensional Discrete Cosine Transform Computing Circuit” issued on Feb. 17, 1998 to Kazui et. al. Furthermore, there is U.S. Pat. No. 5,748,514 entitled “Forward and Inverse Discrete Cosine Transform Circuits” issued on May 5, 1998 to Okada et. al.
In the above cited methods, in order to carry out a fast discrete cosine transform, there are included: a procedure of transposing the sequence of the input data; a butterfly arithmetic procedure; a repeated addition arithmetic procedure; and a procedure of transposing the sequence of the output data.
Thus the conventional methods undergo many procedures, and therefore, the arithmetic amount is enormously increased.
Particularly, in the conventional methods, the positions of the input and output data are not same in the intermediate arithmetic procedure. Therefore, in using the one-dimensional and two-dimensional forward/inverse DCT, there has to be used an additional memory.
SUMMARY OF THE INVENTION
The present invention is intended to overcome the above described disadvantages of the conventional techniques.
Therefore it is an object of the present invention to provide an apparatus and a method for carrying out a fast discrete cosine transform (DCT) with same positions of input and output data, and a recording medium readable by a computer with a program loaded thereon, in which, in the intermediate arithmetic procedure of the of the one-dimensional or two-dimensional forward or inverse DCT, the positions of the input and output data are same so as to make an additional memory needless.
It is another object of the present invention to provide an apparatus and a method for carrying out a fast discrete cosine transform with same positions of input and output data, and a recording medium readable by a computer with a program loaded thereon, in which the required arithmetic amount is effectively reduced.
In achieving the above objects, a first apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: an input data sequence transposing means for transposing the sequence of an externally inputted input data by using a transposing matrix E; a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a G
t−1
B
t−1
.G
t−2
B
t−2
. . . G
0
B
0
matrix on a data obtained as a result of transposing the sequence of the input data by the input data sequence transposing means; and a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using an F
k
Q
0
Q
1
. . . Q
t−1
matrix on a data obtained as a result of the butterfly arithmetic operation by the butterfly arithmetic means.
In a second aspect of the present invention, a first method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) transposing the sequence of an externally inputted input data by using a transposing matrix E; b) carrying out a butterfly arithmetic operation by using a G
t−1
B
t−2
. G
t−2
B
t−2
. . . G
0
B
0
matrix on a data obtained as a result of transposing the sequence of the input data at the step b); and c) carrying out a repeated addition and regularization arithmetic operation by using an F
k
Q
0
Q
1
. . . Q
t−1
matrix on a data obtained as a result of the butterfly arithmetic operation at the step b).
In a third aspect of the present invention, a second apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using an Q
t−1
T
Q
t−2
T
. . . Q
0
T
.F
k
matrix on an externally inputted data; a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a B
0
G
0
.B
1
G
1
. . . B
t−1
G
t−1
matrix on a data obtained as a result of carrying out a repeated addition and regularization arithmetic operation by the repeated addition and regularization arithmetic means; and an input data sequence transposing means for transposing the sequence of an output data by using a transposing matrix E
T
on a data obtained by carrying out the butterfly arithmetic operation by the butterfly arithmetic means.
In a fourth aspect of the present invention, a second method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) carrying out a repeated addition and regularization arithmetic operation by using an Q
t−1
T
Q
t−2
T
. . . Q
0
T
.F
k
matrix on an externally inputted data; b) carrying out a butterfly arithmetic operation by using a B
0
G
0
.B
1
G
1
. . . B
t−1
G
t−1
matrix on a data obtained as a result of carrying out a repeated addition and regularization arithmetic operation by the repeated addition and regularization arithmetic means at the step a); and c) transposing the sequence of the data by using a transposing matrix E
T
on a data obtained by carrying out the butterfly arithmetic operation at the step b).
In a fifth aspect of the present invention, a third apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: an input data row sequence/column sequence transposing means for transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using transposing matrices E
T
and E; and a row/column DCT means for carrying out a one-dimensional forward DCT by using an F
k
·{Q
0
·Q
1
&Lgr;Q
t−1
}·{G
t−1
B
t−1
·G
t−2
B
t−2
&Lgr;G
0
B
0
} matrix on a row data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means, and for carrying out a one-dimensional forward DCT by using a {B
0
G
0
·B
1
G
1
&Lgr;B
t−1
G
t−1
}·{Q
t−1
T
·Q
t−2
&Lgr;Q
0
T
}F
k
matrix on a column data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means.
In a sixth aspect of the present invention, a third method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) transposing the sequences of rows and columns of an externally inputted two-dimens

Affiliated with

Also associated with

Rating

Apparatus and method for fast discrete cosine transform with... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for fast discrete cosine transform with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for fast discrete cosine transform with... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3266462