Apparatus and method for fast 1D DCT

• US 5,943,502 A
• Filed: 05/11/1998
• Issued: 08/24/1999
• Est. Priority Date: 12/09/1994
• Status: Expired due to Fees

• Current Assignee: Mikamonu Group Ltd. (GSI Technology Incorporated)
• Original Assignee: Neomagic Israel Ltd.
• Inventors: Sariel, Aviram, Adar, Rutie
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US09/075,178
• Time in Patent Office: 470 Days
• Field of Search: 395/500.8, 395/309, 395/800.17, 395/800.16, 395/200.31, 395/200.32, 395/800.18, 395/800.19, 348/465, 348/458, 348/467, 348/397, 348/423, 364/725.03, 364/DIG. 1, 364/DIG. 2, 712/16, 712/27, 712/19, 712/18, 712/17, 712/14
• US Class Current: 712/16
• 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: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

A method and apparatus is disclosed for a fast, one-dimensional, discrete cosine transform (1D DCT) of eight samples, and for a fast, one-dimensional, inverse discrete cosine transform (1D IDCT) for eight coefficients, requiring five parallel additions, five parallel subtractions and one parallel multiply operation. According to one embodiment, the parallel additions and subtractions are executed by performing a parallel add/subtract operation. The data are manipulated in a processor operable to execute add, subtract and multiply operations on a plurality of pairs of data values in parallel. According to a preferred embodiment of the invention, this processor is an associative memory array, typically consisting of several thousands of memory words. The inherent scalability of the associative memory enables increasing throughput by simply increasing the size of the associative memory, enabling performing the 1D DCT for large numbers of samples.

Claims

1. A method of performing a one-dimensional discrete cosine transform (1D DCT) on eight samples, the method comprising:

A. providing an associative processor array featuring a plurality of memory words made up of associative memory cells, said cells being operative to compare values stored therein to a value broadcast to a plurality of said memory words and to write thereto a value broadcast to a plurality of said memory words, operable to implement at least one arithmetic operation in parallel on a plurality of pairs of input values;

B. inputting at least eight data samples to said associative processor array; and

C. executing five additions, five subtractions and one multiplication, each of said arithmetic operations being executed in parallel on a plurality of pairs of data elements, said data elements being said input data samples, results of said arithmetic operations and constant values.

2. The method of claim 1, wherein at least one of said additions is executed concurrent to at least one of said subtractions.

3. The method of claim 1, wherein said arithmetic operations are executed by:

I. arranging, in a plurality of said memory words, at least a portion of two associated of said data elements within a single of said memory words;

II. broadcasting a value to a plurality of said memory words and locating instances of said value; and

,

III. writing a broadcast result value, in parallel, to said memory words based on said located instances.

4. The method of claim 3, wherein at least one of said additions and subtractions is executed by performing an associative add/sub operations.

5. The method of claim 4, wherein said associative processor array features a register array operative to store responders arriving from said memory cells and to communicate said responders to said memory cells, and wherein said arranging is carried out by said register array receiving said responders from a first plurality of said memory cells, shifting said responders in said register array and communicating said responders to a second plurality of said memory cells.

6. The method of claim 1, wherein said input data samples include a plurality of 8×

8 blocks of samples, the method performing the 1D DCT for said plurality of 8×

8 blocks of samples in parallel.

7. The method of claim 1, wherein said associative processor array calculates the DCT in less than two machine cycles per each of said input data samples.

8. A method of performing a one-dimensional inverse discrete cosine transform (1D IDCT) of eight coefficients, the method comprising:

A. providing an associative processor array featuring a plurality of memory words made up of associative memory cells, said cells being operative to compare values stored therein to a value broadcast to a plurality of said memory words and to write thereto a value broadcast to a plurality of said memory words, operable to implement at least one arithmetic operation in parallel on a plurality of pairs of input values;

B. inputting at least eight DCT coefficients to said associative processor array; and

C. executing five additions, five subtractions and one multiplication, each of said arithmetic operations being executed in parallel on a plurality of pairs of data elements, said data elements being said input DCT coefficients, results of said arithmetic operations and constant values.

9. The method of claim 8, wherein at least one of said additions is executed concurrent to at least one of said subtractions.

10. The method of claim 8, wherein said arithmetic operations are executed by:

(I) arranging, in a plurality of said memory words, at least a portion of two associated of said data elements within a single of said memory words;

(II) broadcasting a value to a plurality of said memory words and locating instances of said value; and

,

(III) writing a broadcast result value, in parallel, to said memory words based on said located instances.

11. The method of claim 10, wherein at least one of said additions and subtractions is executed by performing an associative add/sub operation.

12. The method of claim 10, wherein said associative processor array features a register array operative to store responders arriving from said memory cells and to communicate said responders to said memory cells, and wherein said arranging is carried out by said register array receiving said responders from a first plurality of said memory cells, shifting said responders in said register array and communicating said responders to a second plurality of said memory cells.

13. The method of claim 8, wherein said input includes a plurality of 8×

8 blocks of DCT coefficients, the method performing the 1D IDCT for said plurality of 8×

8 DCT coefficients in parallel.

14. The method of claim 8, wherein said associative processor array performs the IDCT in less than two machine cycles per each of said input DCT coefficients.