Method and apparatus for fast implementation of inverse discrete cosine transform in a digital image processing system using low cost accumulators

Claim 2

In a digital image processing system, a method for efficiently performing inverse discrete cosine transformation (IDCT) on n×n input vectors that has relatively low implementation cost, where n is a power of 2, said method comprising the steps of: (a) selecting a non-zero quantized transform domain coefficient by a controller of an IDCT processor of an image signal processing subsystem of said digital image processing system from n 2 quantized transform domain coefficients of an IDCT input vector, said n 2 quantized transform domain coefficients being quantized input values corresponding to a plurality of digitized image signals of an image, said digitized image signals being generated by said image signal processing subsystem using analog image signals received from an image sampling subsystem of said digital image processing system; (b) generating k kernel values of said selected quantized transform domain coefficient's scaled reconstruction kernel under the control of said controller, where k equals at most (n 2 +2n)/8; (c) generating a symmetry selection indicator and an operation configuration selection indicator for each of said generated k kernel values by said controller; (d) providing each of said generated k kernel values and its corresponding symmetry and operation configuration indicators sequentially to an array of n×n accumulators of said IDCT processor by said controller; and

Claim 3

The method as set forth in claim 1, wherein, each of said n×n accumulators is equipped to perform any one of four distinct operations: ______________________________________ Axy ← 1 (Load) Axy ← Axy (Nop) Axy ← Axy + 1 (Add) Axy ← Axy - 1 (Sub) ______________________________________ where A xy denotes the accumulator at row x and column y of said array of n×n accumulators.

Claim 4

The method as set forth in claim 2, wherein, sad n×n accumulators are logically grouped into accumulator group symmetrical to each other in one of 2 p ways, each of said accumulator group being further operationally configured in one of less than 2 q operation configurations, where 2 q equals n 4 , for determining which one of said four distinct operations is to be performed by each of said n×n accumulators for each of said generated unique kernel values; said symmetry selection indicator comprises p bits indicating one of said 2 p symmetries, said operation configuration selection indicator comprises less than q bits indicating one of said less than 2 q configurations.

Claim 5

The method as set forth in claim 3, wherein, n equals 8; p equals 2; and said operation configuration selection indicator comprises 9 bits.

Claim 6

The method as set forth in claim 4, wherein, the array of 8×8 accumulators are grouped by quadrants, and the accumulator groups are symmetrical to each other in one of four ways as follows: ##EQU9## where W is the top left quadrant of said 8×8 accumulators; H=Q, R,±H is the top right quadrant of said 8×8 accumulators; V=R Q,±V is the bottom left quadrant of said 8×8 accumulators; D=R Q R,±D is the bottom right quadrant of said 8×8 accumulators; and R is a reflection matrix equaling: ##EQU10##

Claim 7

The method as set forth in claim 1, wherein, said steps (a) through (e) are repeated for all non-zero quantized transform domain coefficients of said input vector by said controller of said IDCT processor.

Claim 8

The method as set forth in claim 1, wherein, said steps (a) through (e) are repeated for less than all non-zero quantized transform domain coefficients of said input vector by said controller of said IDCT processor.

Claim 9

The method as set forth in claim 7, wherein, said steps (a) through (e) are repeated for less than all non-zero quantized transform domain coefficients of said input vector by said controller of said IDCT processor in a priority basis.

Claim 10

In a digital image processing system, an inverse discrete cosine transform (IDCT) processor for efficiently performing IDCT on n×n input vectors that has relatively low implementation cost, where n is a power of 2, said IDCT processor comprising: (a) control and generation means for selecting a non-zero quantized transform domain coefficient from n 2 quantized transform domain coefficients of an IDCT input vector, generating k kernel values of said selected quantized transform domain coefficient's scaled reconstruction kernel, where k equals at most (N 2 +2n/8, and generating a symmetry selection indicator and an operation configuration selection indicator for each of said generated by k kernel values, said n 2 quantized transform domain coefficients being quantized input values corresponding to a plurality of digitized image signals of an image, said digitized image signals being generated by said image signal processing subsystem using analog image signals received from an image sampling subsystem of said digital image processing system; (b) accumulation means coupled to said control and generation means comprising an array of n×n accumulators for receiving each of said generated k kernel clues sequentially, each of said generated k kernel values being received with its corresponding symmetry and operation configuration selection indicators, and accumulating each of said k kernel values into said n×n accumulators selectively according to said symmetry and operation configuration selection indicators.

Claim 11

In a digital image processing system, an inverse discrete cosine transform (IDCT) processor for efficiently performing IDCT on n×n input vectors that has relatively low implementation cost, where n is a power of 2, said IDCT processor comprising: (a) control and generation means for selecting a non-zero quantized transform domain coefficient from n 2 quantized transform domain coefficients of an IDCT input vector, generating k kernel values of said selected quantized transform domain coefficient's scaled reconstruction kernel, where k equals at most (N 2 +2n/8, and generating a symmetry selection indicator and an operation configuration selection indicator for each of said generated by k kernel values, said n 2 quantized transform domain coefficients being quantized input values corresponding to a plurality of digitized image signals of an image, said digitized image signals being generated by said image signal processing subsystem using analog image signals received from an image sampling subsystem of said digital image processing system; (b) accumulation means coupled to said control and generation means comprising an array of n×n accumulators for receiving each of said generated k kernel clues sequentially, each of said generated k kernel values being received with its corresponding symmetry and operation configuration selection indicators, and accumulating each of said k kernel values into said n×n accumulators selectively according to said symmetry and operation configuration selection indicators.

Claim 12

The IDCT processor as set forth in claim 9, wherein, each of said n×n accumulators is equipped to perform any one of four distinct operations: ______________________________________ Axy ← 1 (Load) Axy ← Axy (Nop) Axy ← Axy + 1 (Add) Axy ← Axy - 1 (Sub) ______________________________________ where A xy denotes the accumulator at row x and column y of said array of n×n accumulators.

Claim 13

The IDCT processor as set forth in claim 10, wherein, said n×n accumulators are logically grouped into accumulator groups symmetrical to each other in one of 2 p ways, each of said accumulator group is operationally configured in one of less than 2 q operation configurations, where 2 q equals n 4 , for determining which one of said distinct operations is to be performed by each of said n×n accumulators for each of said generated unique kernel values; said symmetry selection indicator comprises p bits indicating one of said 2 p symmetries; said operation configuration selection indicator comprises less than q bits indicating one of said less than 2 q configurations.

Claim 14

The IDCT processor as set forth in claim 11, wherein, n equals 8; p equals 2; and said operation configuration selection indicator comprises 9 bits.

Claim 15

The IDCT processor as set forth in claim 12, wherein, the array of 8×8 accumulators are grouped by quadrants, and the accumulator groups are symmetrical to each other in one of four ways as follows: ##EQU11## where Q is the top left quadrant of said 8×8 accumulators; H=Q, R,±H is the top right quadrant of said 8×8 accumulators; V=R Q,±V is the bottom left quadrant of said 8×8 accumulators; D=R Q R,±D is the bottom right quadrant of said 8×8 accumulators; said R is a reflection matrix equaling: ##EQU12##

Claim 16

The IDCT processor as set forth in claim 9, wherein, said control and generation means repeats said selection of transform domain coefficient, said generation of k kernel values and corresponding operation configuration selection indicators for all non-zero quantized transform domain coefficients of said input vector.

Claim 17

The IDCT processor as set forth in claim 9, wherein, said control and generation means repeats said selection of transform domain coefficient, said generation of k kernel values and corresponding operation configuration selection indicators for less than all non-zero quantized transform domain coefficients of said input vectors.

Claim 18

The IDCT processor as set forth in claim 15, wherein, said control and generation means repeats said selection of transform domain coefficient, said generation of k kernel values and corresponding operation configuration selection indicators for less than all non-zero quantized transform domain coefficients of said input vecotr in a priority basis.