Signal processing distributed arithmetic architecture

• US 6,477,203 B1
• Filed: 10/30/1998
• Issued: 11/05/2002
• Est. Priority Date: 10/30/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Poplin, Dwight, Gibson, Jonathan S.
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): WONG, ALLEN C
• Application Number:
  US09/183,196
• Time in Patent Office: 1,467 Days
• Field of Search: 375/240.2, 375/240.16, 375/245, 382/302, 382/303, 382/304, 382/305, 708/402, 708/520, 708/620
• US Class Current: 375/240.2
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

An apparatus computes an inner product vector of a matrix and a vector. The matrix has a first set of coefficients and the vector has a second set of coefficients. At least one input register is used to store the second set of coefficients. A plurality of storage elements are used to store partial sums that are pre-calculated from the first set of coefficients of the matrix. The outputs of the at least one input register are used as the address inputs to the plurality of storage elements to select a subset of the partial sums. In addition, a select circuit is coupled to the storage elements'"'"' address lines to determine which row in the matrix the vector forms one element of the resultant inner product for that row. The subset of partial sums from the outputs of the storage elements are added in an adder circuit to create a summation output that presents the element of the inner product vector of the matrix multiplied by the vector. The apparatus has the advantages of reduced integrated circuit area and the ability to create elements of the inner product vector in any desired order.

Claims

1. An apparatus for computing an inner product vector of a matrix and a vector, the inner product vector having a set of elements, the matrix having a first set of coefficients arranged in a set of rows and a set of columns, the vector having a second set of coefficients, comprising:

at least one input register, said at least one input register storing the second set of coefficients, said at least one input register having a set of outputs;

a plurality of storage elements, said storage elements storing a set of partial sums derived from the first set of coefficients, said plurality of storage elements having a set of address inputs and a set of data outputs, said set of address inputs coupled to said set of outputs of said at least one input register, said a set of data outputs presenting a subset of said set of partial sums, said subset of said set of partial sums selected by said set of address inputs;

a select circuit, said select circuit coupled to said set of address inputs of said plurality of storage elements, said select circuit selecting a row in the matrix for computation of one element of said inner product vector from said selected row of the matrix and the vector;

an adder circuit, said adder circuit having a summation output and a plurality of addend inputs, said plurality of addend inputs coupled to said set of data outputs of said storage elements, wherein each data output of said plurality of storage elements is coupled to one addend input to form one addend of the summation output, said summation output presenting said one element of the inner product vector.

2. The apparatus of claim 1 further comprising a clock circuit, said clock circuit coupled to said at least one input register and said storage bank select circuit, said clock circuit creating a set of clock cycles corresponding to the number of rows of the matrix, and wherein said adder circuit presents said one element of the inner product vector corresponding to said selected row of the matrix multiplied by the vector for each clock cycle of said set of clock cycles.

3. The apparatus of claim 1, wherein said apparatus is fabricated as an integrated circuit.

4. The apparatus of claim 1, wherein said plurality of storage elements store multiple sets of partial sums, and said plurality of storage elements further comprise a selector, said selector coupled to said plurality of storage elements to select that set of partial sums to be presented on said data outputs of said plurality of storage elements.

5. The apparatus of claim 4, wherein said selector selects a set of partial sums which allows the apparatus to perform a discrete cosine transform.

6. The apparatus of claim 4, wherein said selector selects a set of partial sums which allows the apparatus to perform an inverse discrete cosine transform.

7. The apparatus of claim 1, wherein said plurality of storage elements is comprised of at least one read only memory and wherein said set of partial sums derived from the first set of coefficients is static.

8. The apparatus of claim 7 wherein said at least one read only memory is comprised of logic based elements.

9. The apparatus of claim 1, wherein said plurality of storage elements is comprised of at least one random access memory and wherein said set of partial sums derived from the first set of coefficients is dynamically updated.

10. An image encoder comprising the apparatus of claim 1.

11. An image decoder comprising the apparatus of claim 1.

12. An image processing device comprising the apparatus of claim 1.

13. A digital camera comprising the apparatus of claim 1.

14. A method for computing an inner product vector of a matrix and a vector, the matrix having a first set of coefficients arraigned in a set of rows and a set of columns, the vector having a second set of coefficients, comprising the steps of:

generating a set of register outputs from the second coefficients of the vector;

storing a set of pre-calculated partial sums derived from the first coefficients in a plurality of storage elements;

selecting a matrix row to be multiplied with the vector to form a portion of the inner product vector;

selecting a subset of pre-calculated partial sums from said stored set of pre-calculated partial sums based on said set of register outputs into said plurality of storage elements;

adding said subset of pre-calculated partial sums in said adder circuit to create said portion of the inner product; and

repeating the steps of selecting a matrix row, selecting a subset of pre-calculated partial sums, and adding said subset or pre-calculated partial sums for each row of the matrix.

15. The method of claim 14, wherein said step of selecting a subset of pre-calculated partial sums comprises the step of selecting from multiple sets of pre-calculated partial sums.

16. The method of claim 15, wherein said step of selecting from multiple sets of pre-calculated partial sums comprises the step of selecting a set of pre-calculated partial sums adapted to perform a discrete cosine transform.

17. The method of claim 15, wherein the step of selecting from multiple sets of pre-calculated partial sums comprises the step of selecting a set of pre-calculated partial sums adapted to perform an inverse discrete cosine transform.

18. The method of claim 14, further comprising the step of writing said plurality of storage elements with a set of pre-calculated partial sums.

19. An image processing device using the method of claim 14.

20. A digital camera using the method of claim 14.

21. A digital camera, comprising:

a lens;

an image sensor, said image sensor having an image capture area optically coupled to said lens, and said image sensor having a data output;

an image processing integrated circuit, said image processing integrated circuit coupled to said data output of said image sensor, said image processing integrated circuit further comprising,

a circuit for computing a set of inner product results of a matrix and a vector, the matrix having a first set of coefficients arranged in a set of rows and a set of columns, the vector having a second set of coefficients derived from said image sensor, and further comprising,

a plurality of input registers, said plurality of input registers storing the second set of coefficients, said plurality of input registers having a set of outputs,

a plurality of storage elements, said storage elements storing a set of partial sums derived from the first set of coefficients, said plurality of storage elements having a set of address inputs and a set of data outputs, said set of address inputs coupled to said set of outputs of said plurality of input registers, said plurality of storage elements having a set of data outputs for presenting a subset of said set of partial sums, said subset of said set of partial sums selected by said set of address inputs,

a storage bank select circuit, said storage bank select circuit coupled to said set of address inputs of said plurality of storage elements, said storage bank select circuit selecting a row in the matrix to compute one inner product result from the selected row and the vector,

a clock circuit, said clock circuit coupled to said plurality of input registers and said storage bank select circuit, said clock circuit creating a set of clock cycles corresponding to the number of rows of the matrix, and

an adder circuit, said adder circuit having a summation output and a plurality of addend inputs, said plurality of addend inputs coupled to said set of data outputs of said storage elements, wherein each data output of said plurality of storage elements is coupled to one addend input to form one addend of the summation output, said summation output presents one inner product result of the set of inner product results corresponding to a row of the matrix multiplied by the vector for each clock cycle of said set of clock cycles;

a camera controller, said camera controller coupled to said summation output of said image processing integrated circuit, said camera controller creating an image processed data output; and

a image storage device, said image storage device coupled to said camera controller, said image storage device storing the image processed data output from said camera controller.