Neural comprising means for calculating a norm or a distance

• US 5,548,686 A
• Filed: 12/21/1994
• Issued: 08/20/1996
• Est. Priority Date: 04/29/1992
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Deville, Yannick
• Primary Examiner(s): Lane, Jack A.
• Assistant Examiner(s): HAFIZ, TARIQ R
• Application Number:
  US08/363,556
• Time in Patent Office: 608 Days
• Field of Search: 395/20-27, 364/752, 382/12-15, 382/155-159
• US Class Current: 706/41
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 2207/4802 Special implementations
• CPC Class Codes: G06F 2207/5525 Pythagorean sum, i.e. the square root of a sum of squares
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology

Abstract

A neural processor, comprising neural calculation apparatus (30, NQ, RQ) which extracts a root Q of a quantity X, said root constituting either a norm of a data or a distance between data. The calculation apparatus calculates (30) by iteration a series of contributions ΔQ_i which are used (NQ, RQ) to update a partial root QP which becomes the root Q at the end of calculation. The calculation can be performed on an arbitrary arithmetic base which determines the number of neurons utilized and also the accuracy of calculation. It is possible to execute the calculation of a partial remainder (NR, RR). Several programming modes are presented.

Claims

1. A neural processor, comprising neural calculation means for extracting a root Q of a quantity X, which root constitutes either a norm of data or a distance between data, the neural calculation means comprising:

at least one first neuron for recursively calculating a series of contributions Δ

Q_i =q_i ·

Bⁱ which together form an expression of the root Q on an arbitrary base;

at least one second neuron, fed by said at least one first neuron, for recursively updating a partial root QP by accumulating said contributions Δ

Q_i in order to deliver the root Q

where i is an integer index and q_i is an integer coefficient of the i^th power of base B.

2. A processor as claimed in claim 1, wherein, the partial root QP initially is zero, for the calculation of a root of degree d, said neural calculation means is for performing the following operations:

calculating a plurality of quantities SD_j according to the following equation;

space="preserve" listing-type="equation">SD.sub.j =X-(QP.sub.i+1 +j·

B.sup.i).sup.d

said plurality of quantities resulting from B-1 operations performed by at least one neuron for an index j varying from 1to B-1, i being an integer index initially equal to a predetermined maximum;

first determining a value j=q_i for which;

space="preserve" listing-type="equation">sgn(SD.sub.j)≠

sgn(SD.sub.j+1)

where SD₀ ≦

0, SD_i <

0, and sgn(0) =+1;

second determining a contribution Δ

Q_i =q_i ·

Bⁱ ;

third determining a new partial root such that;

space="preserve" listing-type="equation">QP.sub.i =QP.sub.i+1 +Δ

Q.sub.i ;

decrementing i; and

recursively iterating through the operations until a minimum value of i is reached so as to determine the root Q to a predetermined accuracy.

3. A processor as claimed in claim 2, wherein the execution of the B-1 operations is distributed between several groups of at least one neuron each.

4. A processor as claimed in claim 2, wherein the second and third determining operations are executed by at least one neuron.

5. A processor as claimed in claim 2, wherein for B=2, the at least one first neuron (NA) executes the calculating and first and second determining operations and the at least one second neuron executes the third determining operation.

6. A processor as claimed in claim 1, the neural calculation means are for performing the following additional operations:

setting a partial remainder RP_i initially to X;

updating the partial remainder by recursion so that one of the following equations holds;

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 +(QP.sub.i+1).sup.d -(QP.sub.i+1 +Δ

Q.sub.i).sup.d ;

or

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 +(QP.sub.1 -Δ

Q.sub.i).sup.d --(Qpi)d,

so that a partial remainder RP_i =X-(QP_i)^d is calculated, where

i is an integer index which is initialized to a maximum value and decremented to a predetermined minimum value which yields a desired precision for Q; and

d is an integer representing the degree of the root Q.

7. A processor as claimed in claim 6, the neural calculation means are for calculating also a plurality of quantities SD_j according to the following equation

8. A processor as claimed in claim 6,

wherein for B=2, the at least one first neuron executes the calculating and first and second determining operations and the at least one second neuron (NQ) executes the updating of the partial root;

and

further comprising a third neuron (NR) for executing the updating of the partial remainder.

9. A processor as claimed in claim 1, wherein the calculation means are further for calculating a square root by calculating a partial remainder RP_i, by performing the following additional operations:

setting the partial remainder initially to the quantity X,

updating the partial remainder by iteration so that one of the following equations holds;

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 -Δ

Q.sub.i ·

(2·

QP.sub.i+1 +Δ

Q.sub.i) or

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 -Δ

Q.sub.i (2·

QP.sub.i -Δ

Q.sub.i)

where

i is an integer index which is initialized to a maximum value and decremented to a predetermined minimum value which yields a desired precision for Q; and

d is an integer representing the degree of the root Q.

10. A processor as claimed in claim 9, wherein the calculation means are further for calculating a plurality of quantities SD_j according to the following equation

11. A processor as claimed in claim 1, wherein the processor performs a root calculation at one instant and performs neural resolving and/or learning tasks at another instant.

12. A processor as claimed in claim 1, wherein the processor receives components of a vector and calculates said quantity X to be equal to the sum of powers of degree d of each of said components.

13. A processor as claimed in claim 1, wherein the processor receives vector components and calculates said quantity X, for vectors taken two by two, so that X is equal to the sum of the powers of degree d of the differences between said components of the same order.

14. A neural processor for extracting a root Q of a quantity X, which root constitutes either a norm of a data or a distance between data, the processor comprising a first neuron (NA) for

calculating a plurality of quantities SD_j according to the following equation:

space="preserve" listing-type="equation">SD.sub.j =X--(QP.sub.i+1 +j·

B.sup.i).sup.d

said plurality of quantities resulting from B-1 operations performed by at least one neuron for an index j varying from 1 to B-1, i being an integer index initially equal to a predetermined maximum;

first determining a value j=q_i for which;

space="preserve" listing-type="equation">sgn(SD.sub.j)≠

sgn(SD.sub.j+1)

where SD₀ ≧

0, SD_B <

0, sgn(0)=+1, B is 2, and d is the degree of the root; and

a second neuron (NQ) for

second determining a contribution Δ

Q_i =q_i ·

Bⁱ ;

third determining a new partial root such that;

space="preserve" listing-type="equation">QP.sub.i =Qpi+1+Δ

Qi.

15.

15. A processor as claimed in claim 14, further comprising a third neuron (NR) for updating a partial remainder by recursion so that one of the following equations holds:

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 +(QP.sub.i+1).sup.d -(QP.sub.i+1 +Δ

Q.sub.i).sup.d ;

or

space="preserve" listing-type="equation">RP.sub.i =RP.sub.i+1 +(QP.sub.i -Δ

Q.sub.i).sup.d -(Qpi)d,

so that a partial remainder RP_i =X-(QP_i)^d is calculated.