Fast DCT apparatus

• US 6,195,674 B1
• Filed: 02/18/1998
• Issued: 02/27/2001
• Est. Priority Date: 04/30/1997
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Pulver, Mark, Elbourne, Trevor Robert
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/025,506
• Time in Patent Office: 1,105 Days
• Field of Search: 708/400-410
• US Class Current: 708/402
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

An apparatus and a method for performing discrete cosine transformation (DCT) are presented. The apparatus includes an arithmetic circuit interconnected with a transpose memory. The arithmetic circuit includes a combinatorial circuit for calculating a DCT without using an intermediate clocked storage unit. The combinatorial circuit includes a predetermined number of sequentially arranged stages for implementing the DCT. The apparatus may optionally include a controller for controlling operation of the apparatus and a multiplexer for multiplexing data input to the apparatus and data from the transpose memory. An apparatus and a method for performing inverse discrete cosine transformation (IDCT) are also presented.

Claims

1. A discrete cosine transform (DCT) apparatus comprising:

a transpose memory unit; and

an arithmetic circuit interconnected with said transpose memory unit, said arithmetic circuit including a combinatorial circuit for calculating a DCT without a clocked storage unit.

2. The DCT apparatus according to claim 1, wherein the combinatorial circuit comprises a predetermined number of stages for implementing the DCT, the stages being arranged sequentially.

3. The DCT apparatus according to claim 1, further comprising a multiplexer for multiplexing input data provided to said DCT apparatus and data output by said transpose memory unit.

4. The DCT apparatus according to claim 1, further comprising a controller for controlling operation of said DCT apparatus.

5. An inverse discrete cosine transform (IDCT) apparatus, comprising:

a transpose memory unit; and

an arithmetic circuit interconnected with said transpose memory unit, said arithmetic circuit comprising a combinatorial circuit for calculating an inverse DCT without a clocked storage unit.

6. The inverse DCT apparatus according to claim 5, wherein the combinatorial circuit comprises a predetermined number of stages for implementing the inverse DCT, the stages being arranged sequentially.

7. The inverse DCT apparatus according to claim 5, further comprising a multiplexer for multiplexing input data provided to said inverse DCT apparatus and data output by said transpose memory unit.

8. The inverse DCT apparatus according to claim 5, further comprising a controller for controlling operation of said inverse DCT apparatus.

9. A method of performing discrete cosine transformation (DCT) of data, said method comprising the steps of:

calculating a DCT of input data in accordance with a first orientation of the data using an arithmetic circuit that comprises a combinatorial circuit for calculating the DCT without a clocked storage unit;

storing the transformed input data in accordance with the first orientation in a transpose memory unit interconnected with the combinatorial circuit; and

calculating a DCT of the transformed input data stored in the transpose memory unit in accordance with a second orientation of the data using the arithmetic circuit to provide transformed data.

10. The method according to claim 9, wherein the DCT is calculated in a predetermined number of stages, the stages being arranged sequentially.

11. The method according to claim 9, further comprising the step of multiplexing input data and data output by the transpose memory unit.

12. A method of inverse performing discrete-cosine transformation (IDCT) of data, said method comprising the steps of:

calculating an inverse DCT of input coefficients in accordance with a first orientation of the coefficients using an arithmetic circuit comprising a combinatorial circuit for calculating the inverse DCT without a clocked storage unit;

storing the inverse transformed input coefficients in accordance with the first orientation in a transpose memory unit interconnected with the combinatorial circuit; and

calculating an inverse DCT of the transformed input coefficients stored in the transpose memory unit in accordance with a second orientation using the arithmetic circuit to provide output inverse transformed data.

13. The method according to claim 12, wherein the inverse DCT is calculated in a predetermined number of stages, the stages being arranged sequentially.

14. The method according to claim 12, further comprising the step of multiplexing input data and coefficients output by the transpose memory unit.