Asynchronous parallel arithmetic processor utilizing coefficient polynomial arithmetic (CPA)

• US 20030093449A1
• Filed: 11/18/2002
• Published: 05/15/2003
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: United States Secretary of the Army
• Original Assignee: United States Secretary of the Army
• Inventors: Carroll, Chester C.
• Granted Patent: US 6,618,741 B2
• Time in Patent Office: Days
• US Class Current: 708/490
• 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
• CPC Class Codes: G06F 2207/3832 Less usual number representations
• CPC Class Codes: G06F 7/48 using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
• CPC Class Codes: G06F 7/60 Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations , e.g. using difunction pulse trains, STEELE computers, phase computers conversion of digital data to or from non-denominational form H03M5/00, H03M7/00
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

Sets of coefficient polynomials are used to design embedded-component architectures that have capability for asynchronous parallel execution at an advantageous arithmetic level where algebraic merging is realized with other operations, algorithms or applications. Because of the particular hardware structures made possible by the use of CPA, higher computational granularities and complex modules are more easily feasible than by using conventional arithmetic and, additionally, increased efficiency is obtained for algorithmic computations involving single and multiple operations. This is achieved by the merging of operations and the integration of algorithms, and thereby avoiding the necessity of performing the entire basic arithmetic separately for each operation or algorithm. In the Asynchronous Parallel Arithmetic (APA) Processor Utilizing Coefficient Polynomial Arithmetic (CPA), the various sets of coefficient polynomials represent the merged operations or algorithms at much earlier time slots and their resolution to the final result level is accomplished with notably increased efficiency when compared to conventional structures.

Claims

1. Asynchronous Parallel Arithmetic (APA) processor utilizing Coefficient Polynomial Arithmetic (CPA) capable of processing given arithmetic operations on multiple sets of input binary numbers A and B, said APA processor comprising modular hardware components and being capable of achieving parallelism and concurrency at the data-path level, thereby facilitating the mapping of algorithms to hardware for embedded systems, said modular hardware components comprising:

a means for holding therein the input binary numbers A and B;

a parallel multiplier, coupled to said holding means, for processing said input binary numbers and producing therefrom a first set of coefficient polynomials p_n in CPA form, said first set of coefficient polynomials being organized into a plurality of columns;

a means for receiving and parallel-merging said first set of coefficient polynomials in said columns to produce a second set of coefficient polynomials and continuing said parallel-merging of the last set of coefficient polynomials until the degree of “

1”

for the resultant coefficient polynomial set is achieved; and

a two-stage adder coupled to said parallel-merging means for rendering the result of said arithmetic operations on said input binary numbers A and B in ordinary binary form.

2. An APA processor utilizing CPA as set forth in claim 1, wherein said parallel multiplier comprises a plurality of Cauchy product registers coupled to said holding means, said Cauchy product registers receiving the input binary numbers from said holding means and, in response, producing therefrom Cauchy products polynomial, said products polynomial being organized into multiple columns in said Cauchy product registers, each column-register representing different weights of said products polynomial;

and a first level of a plurality of identical counter cells, said counter cells being coupled on one-to-one correspondence to said multiple column-registers of said Cauchy registers, said first level of counter cells performing binary summation of the bits in their respective corresponding columns and yielding said first set of coefficient polynomials p_i in CPA form.

3. An APA processor utilizing CPA as set forth in claim 2, wherein each of said counters comprises a plurality of each of XOR-gate, AND-gate and OR-gate, said gates being interconnected so as jointly to produce the sum of interpreted counts.

4. An APA processor utilizing CPA as set forth in claim 3, wherein said means for receiving and parallel-merging said first set of coefficient polynomials comprises at least a second level of counters, said second level of counters parallel-merging said first set of coefficient polynomials in said columns to produce a second set of coefficient polynomials.

5. An APA processor utilizing CPA as set forth in claim 4, wherein said receiving and parallel-merging means further comprises additional levels of counters, the number of levels being dependent on the word length of the binary input numbers, said additional levels of counters co-operating to merge said coefficient polynomials until a final resultant coefficient polynomial set is achieved, each coefficient polynomial set representing the result of corresponding level of counters and said final resultant coefficient polynomial set having the degree of “

1”

.

6. An APA processor utilizing CPA as set forth in claim 5, wherein said two-stage adder comprises a parallel adder for receiving and performing initial parallel addition on said final resultant coefficient polynomial set in totally parallel CPA form to produce carry bits and sum bits;

and a sequential adder, said sequential adder being connected to said parallel adder for receiving said carry bits and sum bits from said parallel adder and, in response, producing a final result in ordinary binary form.

7. An APA processor utilizing CPA as set forth in claim 6, wherein said parallel adder is comprised of a plurality of parallel cells and said sequential adder is comprised of a plurality of sequential cells, the number of said parallel cells equaling the number of bits in said final resultant coefficient polynomial set that are being added therein and the number of sequential cells being greater than the number of parallel cells by 1.

8. An APA processor utilizing CPA as set forth in claim 7, wherein said parallel and sequential cells are coupled to each other via conventional wire connection in one-to-one correspondence except for the very last one of said sequential cells.

9. An APA processor utilizing CPA as set forth in claim 8, wherein each of said sequential cells comprises an XOR-gate, an AND-gate and an OR-gate, said gates being interconnected with each other so as to enable each sequential cell to accept a sum bit and a carry bit from corresponding parallel cell and processing said bits to yield a final sum in ordinary binary form.

10. A computer-readable medium containing instructions therein for controlling a computer system and causing the computer system to utilize Coefficient Polynomial Arithmetic (CPA) to process given arithmetic operations on multiple sets of input binary numbers A and B, so as to achieve parallelism and concurrency at the data-path level, by:

(a) processing the input binary numbers and consequently producing a first set of coefficient polynomials p_n in CPA form;

(b) organizing the first set of coefficient polynomials into a plurality of columns;

(c) parallel-merging the first set of coefficient polynomials in the columns to produce a second set of coefficient polynomials;

(d) continuing the parallel-merging of the last preceding set of coefficient polynomials until the degree of “

1”

is achieved for each resultant coefficient polynomial in the final set, said resultant coefficient polynomial set representing the final result in binary form.

(e) performing initial parallel addition on the final resultant coefficient polynomial set in totally parallel CPA form to produce carry bits and sum bits; and

(f) sequentially adding the carry bits and sum bits to render a final result in ordinary binary form.

11. A computer-readable medium containing instructions therein as set forth in claim 10, wherein said processing and producing step includes inputting a pair of binary numbers A and B into each of a plurality of Cauchy product register sets.

12. A method in a computer system for computing a correlation value between a target image and a filter image, for greater accuracy and ease in the recognition of an intended target, by obtaining the sum of all the individual products of corresponding pixels from the target image and the filter image, said method comprising the steps of:

(a) scanning the target scene and creating an electronic image of the scene;

(b) converting the target image into an array of pixels and inputting the array of pixels and the filter image pixels to multiple Cauchy product registers;

(c) producing products, in the multiple Cauchy product registers, of pixels from the target image and the filter image, the products each having individual bit positions;

(d) accumulating corresponding bits of the individual bit positions of the products within each of the Cauchy product registers into a first set of coefficient polynomials;

(e) organizing the first set of coefficient polynomials into a plurality of columns;

(f) parallel-merging the first set of coefficient polynomials in the columns to produce a second set of coefficient polynomials;

(g) continuing the parallel-merging of the last preceding set of coefficient polynomials until coefficient polynomials having the final cross-correlation value are produced.

(h) Applying the final cross-correlation value to a tracking means to aid in the recognition of the intended target.

13. A method in a computer system for computing a correlation value between a target image and a filter image as set forth in claim 12, wherein said step of continuing the parallel-merging is accomplished in three levels of CPA, each of said levels being suitable to support the exercise of pre-determined decision algorithms based on the instant correlation value.