Methods and apparatus for performing correlation operations

• US 6,401,106 B1
• Filed: 08/07/2000
• Issued: 06/04/2002
• Est. Priority Date: 08/07/2000
• Status: Expired due to Term

• Current Assignee: Divan Industries, LLC (Innovation Management Sciences, LLC)
• Original Assignee: Systems On Silicon, Inc. (Transwitch Corporation)
• Inventors: Juan, Yujen
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/633,693
• Time in Patent Office: 666 Days
• Field of Search: 708/422, 708/426, 708/319, 708/603
• US Class Current: 708/422
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00

Abstract

Methods and apparatus for implementing an enhanced digital signal processor through the addition of modular computation units which can be operated in parallel are described. In various embodiments the computation units are implemented as configurable computation cells which are arranged to form a computation engine which supplements conventional DSP circuitry. The computation cells can be used to perform frequently used DSP functions such a cross-correlation, sorting, FIR filtering quickly without the need for extensive iterative processing. By using the computation cells of the present invention in parallel, the computation of common DSP functions can be performed quickly and resulting in improvements in DSP performance as compared to convention DSPs.

Claims

1. A method of performing a correlation operation on two sequences of input numbers, comprising the steps of:

providing a sequence of M computation cells where M is an integer greater than two, each computation cell in the sequence of computation cells including circuitry for performing a correlation processing operation including multiplying one value corresponding to each one of the two sequences of input numbers together and adding a third value to the result;

operating a subset of N of said M computation cells in the sequence of computation cells, where N<

M, to perform correlation processing operations in parallel and to store the result of the processing performed by each of the computation cells in a different one of N storage locations, the third value added by at least one of said subset of N computation cells as part of performing a correlation processing operation being an accumulated result of multiplication performed by said at least one cell; and

reading out a result of the correlation processing operations by reading the results stored in the N storage locations.

2. The method of claim 1, further comprising, prior to operating the plurality of the computation cells:

supplying at least one number from each of said subset of N computation cells.

3. The method of claim 1,

wherein said correlation operation is an auto-correlation operation;

and

wherein said two sequences of input numbers are identical.

4. The method of claim 1,

wherein the correlation operation is a cross-correlation operation;

and

wherein the step of operating the subset of computation cells to perform correlation processing operations includes operating the subset of said plurality of computation cells to perform cross-correlation processing operations.

5. The method of claim 1,

wherein the correlation operation is a auto-correlation operation;

and

wherein the step of operating the sequence of computation cells to perform correlation processing operations includes operating the sequence of computation cells to perform auto-correlation processing operations.

6. The method of claim 1, further comprising the steps of:

operating a software controllable processing circuit to supply two sequences of values to a first one of the N computation cells in the subset of N computation cells, each sequence including N values.

7. The method of claim 6, further comprising the step of:

operating the software controllable processing circuit to send a control signal to the subset of N computation cells to control the operation of said computation cells.

8. A method of performing a correlation operation on two sequences of input numbers, comprising the steps of:

providing a sequence of M computation cells where M is an integer greater than two, each computation cell in the sequence of computation cells including circuitry for performing a correlation processing operation;

operating the sequence of computation cells to perform correlation processing operations in parallel and to store the result of the processing performed by each of the computation cells in a different one of M storage locations, each one of the M storage locations being a register included in a different one of the M computation cells; and

reading out a result of the correlation processing operations by reading the results stored in the M storage locations, the step of reading out a complete result of the correlation operation including;

shifting out the contents of each of the M registers so that the contents of the M registers exits the sequence of M computation cells through a data output of the last computation cell in the sequence of M computation cells.

9. The data processing method of claim 9, further comprising the step of:

providing a multi-bit control value to each of the M computation cells to control the operation of said computation cells.

10. The data processing method of claim 9, further comprising the step of:

setting the multi-bit control value to a first value to configure the M computation cells to perform the correlation processing operations; and

setting the multi-bit control value to a second value to configure the M computation cells to shift out the contents of the M registers.

11. The data processing method of claim 9, further comprising:

storing the multi-bit control value in a storage device; and

coupling an output of the storage device to each of the M computation cells.

12. A method of performing a cross-correlation operation comprising the steps of:

providing a set of M computation cells capable of performing correlation processing operations in parallel, wherein M is an integer greater than 2, the set of M computation cells including first and second inputs;

supplying two sequences of N data values, wherein N<

M, to the set of M computation cells, each sequence of N data values being supplied to a different one of the first and second inputs; and

operating N of said M computation cells to perform correlation processing operations in parallel, the processing performed by each of said at least N computation cells including multiplying one value corresponding to each of the first and second sequences together and adding a third value to the result, the step of operating at least one of the N cells including generating the third value added by said at least one cell by accumulating the result of the multiplication performed by said at least one cell; and

outputting from said set of M computation cells a set of N values representing a cross-correlation result.

13. The method of claim 12, wherein the M computation cells are coupled together in series to form a series of M computation cells, the step of outputting from said set of M computation cells including shifting out at least N values from the Mth computation cell in the series of M computation cells.

14. The method of claim 12, wherein the step of outputting from said set of M computation cells including reading out in parallel N values from N of said M computation cells.

15. A method of performing a correlation operation comprising the steps of:

providing a set of M computation cells capable of performing correlation processing operations in parallel, the M computation cells being coupled together in series to form a series of M computation cells, wherein M is an integer greater than 2;

supplying two sequences of N values, wherein N<

M, to the set of M computation cells;

operating at least N of said M computation cells to perform correlation processing operations in parallel; and

outputting from said set of M computation cells a set of N values representing a correlation result, the step of outputting from said set of M computation cells including shifting out at least M values from the Mth computation cell in the series of M computation cells.

16. The method of claim 15,

wherein the step of outputting from said set of M computation cells further includes discarding M-N of the M values shifted out of the Mth computation cell.

17. A device for performing a cross-correlation operation on digital data, the device comprising:

a plurality of M sequentially coupled cross-correlation computation cells; and

means for controlling a subset of N of said M cross-correlation computation cells to perform a cross-correlation operation on two sets of N input values and to control each one of said N computation cells to output one value of an N value cross-correlation result, where N and M are integers and where N<

M;

each cross-correlation computation cell having first, second and third inputs and a data output, each of the first and second inputs of the first computation cell in said sequence for receiving at least a portion of said digital data, the data output of the first computation cell being coupled to the third input of the next computation cell in the sequence of N computation cells, the data output of the last computation cell being for outputting at least a portion of a result of said cross-correlation operation, each cross-correlation cell further comprising;

a multiplying device including first and second inputs coupled to the first and second inputs of the computation cell, respectively, and an output;

an adding device coupled to the output of said multiplier device; and

a data storage device coupled to an output of said adding device.

18. The device of claim 17, further comprising:

a control register, coupled to each of M cross-correlation computation cells for storing a control value used to control the internal configuration of connections inside the subset of the N computation cells.

19. The device of claim 17, wherein N is at least 3.

20. A device for performing a correlation operation on digital data, the device comprising:

a plurality of N sequentially coupled correlation computation cells, each correlation computation cell having a data input and a data output, the data input of the first computation cell in said sequence for receiving at least a portion of said digital data, the data output of the first computation cell being coupled to the data input of the next computation cell in the sequence of N computation cells, the data output of the last computation cell being for outputting a result of said correlation operation, each correlation cell further comprising;

a multiplying device coupled to the data input of the computation cell;

an adding device coupled to said multiplier device; and

a data storage device coupled to an output of said adding device; and

means for shifting out from the last computation cell, in the sequence of N computation cells, one value generated by each of the N computation cells to form a sequence of N correlation values representing the result of a correlation operation.

21. The device of claim 20, wherein N is at least 3.

22. A device for performing a correlation operation on digital data, the device comprising:

a plurality of N sequentially coupled correlation computation cells, wherein N is an integer multiple of 8, each correlation computation cell having a data input and a data output, the data input of the first computation cell in said sequence for receiving at least a portion of said digital data, the data output of the first computation cell being coupled to the data input of the next computation cell in the sequence of N computation cells, the data output of the last computation cell being for outputting a result of said correlation operation, each correlation cell further comprising;

a multiplying device coupled to the data input of the computation cell;

an adding device coupled to said multiplier device; and

a data storage device coupled to an output of said adding device.

23. The device of claim 22, wherein N is at least 80.