Circuit for searching/sorting data in neural networks

• US 5,740,326 A
• Filed: 06/07/1995
• Issued: 04/14/1998
• Est. Priority Date: 07/28/1994
• Status: Expired due to Term

• Current Assignee: Associative Computing, Inc., in2H2, Inc., Silicon Recognition Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Tannhof, Pascal, Boulet, Jean-Yves, Paillet, Guy
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): SHAH, SANJIV
• Application Number:
  US08/486,658
• Time in Patent Office: 1,042 Days
• Field of Search: 395/22, 395/23, 395/27, 382/14
• US Class Current: 706/27
• CPC Class Codes: G06F 18/24133 Distances to prototypes
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: G06N 3/063 using electronic means
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/19173 Classification techniques

Abstract

In a neural network of N neuron circuits, having an engaged neuron'"'"'s calculated p bit wide distance between an input vector and a prototype vector and stored in the weight memory thereof, an aggregate search/sort circuit (517) of N engaged neurons'"'"' search/sort circuits. The aggregate search/sort circuit determines the minimum distance among the calculated distances. Each search/sort circuit (502-1) has p elementary search/sort units connected in series to form a column, such that the aggregate circuit is a matrix of elementary search/sort units. The distance bit signals of the same bit rank are applied to search/sort units in each row. A feedback signal is generated by ORing in an OR gate (12.1) all local search/sort output signals from the elementary search/sort units of the same row. The search process is based on identifying zeroes in the distance bit signals, from the MSB'"'"'s to the LSB'"'"'s. As a zero is found in a row, all the columns with a one in that row are excluded from the subsequent row search. The search process continues until only one distance, the minimum distance, remains and is available at the output of the OR circuit. The above described search/sort circuit may further include a latch allowing the aggregate circuit to sort remaining distances in increasing order.

Claims

1. In a neural network comprised of N neuron circuits (11-1, . . . , 11-i, . . . , 11-N), a plurality of said N neuron circuits having calculated a distance between an input vector (A) and the prototype vector (B), said distance being p bits wide and stored in the neuron'"'"'s weight memory, an aggregate circuit (517) comprising:

a plurality of search/sort circuits, each of said plurality of search/sort circuits being in one of said plurality of N neuron circuits, each search/sort circuit (502-i) comprising;

at least p series connected elementary search/sort units (510-1i to 510-pi), each said elementary search/sort unit (510-ki) receiving a distance bit signal (dki), an exclude output signal (EXCLINki) and a feedback signal ORk) and, generating therefrom a local (neuron) output signal (NOUTk-i) and an exclude output signal (EXCLOUTki), and

said exclude output signal of each said series connected elementary search/sort unit being the exclude input signal of the next said series connected elementary search/sort unit;

each of said plurality of search/sort circuits forming a column, such that each said search/sort circuit'"'"'s at least p series connected elementary search/sort units of said aggregate circuit form a matrix;

said distance bit signals of the same bit rank forming an input row for each said elementary search/sort unit in said matrix row;

each said neuron circuit'"'"'s local output signal (NOUTk-i) being equal to the complemented value of the neuron circuit'"'"'s distance bit signal (dki) if the elementary search/sort unit'"'"'s exclude input signal is inactive (EXCLINki=0) or being equal to the true value thereof if the elementary search/sort unit'"'"'s exclude input signal is active;

the elementary search/sort unit'"'"'s exclude output signal is active (EXCLOUTki=1) if the feedback bit signal (ORk) is the complement of the distance bit signal (dki);

each feedback bit signal (ORk) resulting from ORing all of the local output bit signals (NOUTk-1 to NOUTk-N) generated by each of the elementary search/sort units of row k for all the columns of the matrix, each of the elementary search/sort unit comprising;

first logic circuit means (520) comprised of inverting means (524-i) connected to the last elementary search/sort unit (510-pi) processing the last bit (dpi) for producing a signal (XOR-i) equal to the complement of the exclude output signal (EXCLOUTpi) generated therein; and

,

second logic circuit means (519) for processing the first distance bit signal (d1i) as an exclude input signal (EXCLIN-i) and comprised of a two-way OR gate (522-i) connected in series with a latch (523-i), the output of said latch being connected to the first elementary search/sort unit (510-1i) and connected to the first input terminal of said two-way OR gate, the other input of said two way OR gate receiving said signal (XOR-i) generated by the said first logical circuit means.

2. The aggregate of claim 1, each search/sort circuit (502-i) further including a two-way OR gate (521-i) between the latch and said first elementary search/sort unit, the output of said latch being a first input and, a selection signal (SELECT-i) being a second input of said two-way OR gate.

3. The aggregate unit of claim 1 wherein each said elementary search/sort unit (510-ki) consists of:

a two-way NOR gate (513) driven by said distance bit signal (dki) and said exclude input signal (EXCLINki) to generate said local output signal (NOUTk-i);

a two-way AND gate (514) driven by said distance bit signal (dki) and said feed-back signal (ORk) to generate an intermediate signal; and

,

a two-way OR gate (515) driven by said intermediate signal and said exclude input signal (EXCLINki) to generate said exclude output signal (EXCLOUTki).