Parallel associative memory having improved selection and decision mechanisms for recognizing and sorting relevant patterns

• US 5,014,327 A
• Filed: 02/16/1988
• Issued: 05/07/1991
• Est. Priority Date: 06/15/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Worrell, Glen C., Potter, Terry W.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/156,542
• Time in Patent Office: 1,176 Days
• Field of Search: 382/14, 382/30, 382/33, 382/34
• US Class Current: 382/220
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

A parallel associative memory provides a way of recognizing or identifying observed data patterns. Each of a plurality of memories stores a plurality of recognition patterns. In response to receipt of a recall pattern to be identified, the recall pattern is contemporaneously compared to the recognition patterns stored in the memories and an exact or best match recognition pattern is selected. In a preferred embodiment, the memories may store multiple data bases each of which includes patterns having different lengths and different radii of attraction. The comparison process is controlled by masks which specify respective portions of the patterns which may include the radii of attraction, bits which must identically match, bits which are ignored, bits which are compared in a bit-wise fashion, and bytes which are compared by multiplication. A correlation is computed and selectively adjusted by the respective radii of attraction. A specified number of the patterns having the best correlation are identified, subject to selected threshold conditions, and sorted according to their respective correlations. The parallel nature of the memory lends itself to a hierarchical organization for increased storage capacity and to parallel processing which increases the speed of the identification or recognition process and thereby allows a broad range of applications. These applications includes fast retrieval of exact or inexact data, diagnosis, image processing and speech recognition.

Claims

1. A method of recognizing patterns, said method comprising the steps of:

storing a plurality of recognition patterns in at least one memory, and storing in said memory respective parameters defining respective radii of attraction for the recognition patterns;

receiving a recall pattern;

comparing certain bits of said recall pattern to certain bits of said plurality of recognition patterns and rejecting certain of the recognition patterns based on the bit-wise comparison;

correlating said recall pattern with at least said plurality of recognition patterns in said memory which are not rejected to determine respective measures of closeness for the recognition patterns which are not rejected, wherein said correlating includes adjusting the respective correlations by the respective parameters to determine the respective measure of closeness for the recognition patterns which are not rejected; and

inspecting said measures of closeness to identify at least one closest one of the recognition patterns which are not rejected.

2. The method as claimed in claim 1, wherein said recall pattern and said recognition patterns include respective vector portions distinct from said bits, and wherein said correlating is performed by computing respective scalar products of the vector portion of said recall pattern and the vector portions of the respective recognition patterns which are not rejected.

3. The method as claimed in claim 1, wherein said certain bits are designated by at least one mask.

4. A parallel associative memory, comprising:

means for inputting a recall pattern;

a plurality of associative memories, each associative memory comprising;

means for storing a plurality of recognition patterns,

means for receiving said recall pattern from said means for inputting, and

means for outputting an indication of at least one recognition pattern that closely matches said recall pattern from said plurality of recognition patterns in said means for storing;

means for selecting at least one recognition pattern that most closely corresponds to said recall pattern indicated by the outputs of said plurality of associative memories; and

means for outputting an indication of said at least one recognition pattern selected by said means for selecting;

wherein each of said plurality of associative memories further comprises;

means for comparing said recall pattern from said means for receiving to said plurality of recognition patterns in said means for storing, and

means for selecting as the output of said means for outputting an indication of said at least one recognition pattern that closely matches said recall pattern based upon the comparison by said means for comparing; and

wherein said means for storing a plurality of recognition patterns includes means for storing recognition patterns of different bit lengths in sequence in contiguous addressable memory locations, and wherein said means for comparing includes.

5. The parallel associative memory of claim 4, wherein said means for comparing includes means for comparing said recall pattern to end portions of said recognition patterns, said end portions having the same bit lengths as the bit length of said recall pattern.

6. A parallel associative memory, comprising;

means for receiving a recall pattern;

a plurality of addressable memory means for storing and recalling a plurality of recognition patterns at respective addresses;

means for addressing said addressable memory means to contemporaneously recall a sequence of said stored recognition patterns from each of said addressable memory means;

means for contemporaneously comparing said recall pattern to the recognition patterns recalled from each of said addressable memory means;

means for selecting at least one recognition pattern that closely matches said recall pattern based upon the comparison by said means for comparing; and

means for outputting an indication of at least one recognition pattern selected by said means for selecting, wherein said addressable memory means include means for storing and recalling recognition patterns of different lengths in sequence in contiguous addressable memory locations, and wherein said means for contemporaneously comparing includes means for comparing said recall pattern from said means for receiving to recognition patterns of different lengths.

7. The parallel associative memory as claimed in claim 6, wherein said addressable memory means includes means for storing information specifying the different lengths of the recognition patterns, and said means for addressing includes means for computing the address of a next one of the patterns by adding a current pattern length to the address of a current one of the patterns.

8. A parallel associative memory, comprising;

means for receiving a recall pattern;

a plurality of addressable memory means for storing and recalling a plurality of recognition patterns at respective addresses;

means for addressing said addressable memory means to contemporaneously recall a sequence of said stored recognition patterns from each of said addressable memory means;

means for contemporaneously comparing said recall pattern to the recognition patterns recalled from each of said addressable memory means;

means for selecting at least one recognition pattern that closely matches said recall pattern based upon the comparison by said means for comparing; and

means for outputting an indication of at least one recognition pattern selected by said means for selecting, wherein said addressable memory means includes means for storing and recalling a parameter defining a radius of attraction for each recognition pattern, and said means for comparing includes means for correlating the recall pattern with each recalled recognition pattern and adjusting the correlation for each recalled recognition pattern by an amount based on the respective parameter.

9. The parallel associative memory as claimed in claim 8, wherein said means for adjusting the correlation includes means for adding the correlation to the parameter defining the respective radius of attraction to compute a distance measure for each recalled recognition pattern.

10. The parallel associative memory as claimed in claim 8, wherein said recall pattern and said recognition patterns include vectors, and said correlation is computed as the vector scalar product.

11. The parallel associative memory as claimed in claim 8, wherein said recall pattern and said recognition patterns include bit strings, and said correlation is computed based on a bit-wise comparison of said bit strings.

12. The parallel associative memory as claimed in claim 11, further comprising means for monitoring the number of differences in the bit-wise comparison of said recall pattern to a given recognition pattern by said means for comparing, and means for halting said means for comparing from further comparison of said recall pattern to said given recognition pattern when the number of differences exceeds a predetermined threshold.

13. The parallel associative memory of claim 11, further comprising means for monitoring the number of differences in the bit-wise comparison of said recall pattern to a given recognition pattern;

and means for halting said means for comparing from comparing said recall pattern to any recognition patterns not yet compared when the number of differences is less than a predetermined threshold.

14. The parallel associative memory as claimed in claim 11, wherein said means for comparing further includes means for receiving an "Ignore Mask" designating bit positions of the recall key for which the comparison between the recall key and each recognition pattern is ignored.

15. The parallel associative memory as claimed in claim 11, wherein said means for comparing further includes means for receiving a "Subspace Mask" designating bit positions of the recall key for which the recall key and each recognition pattern must match for the recognition pattern to be selected by said means for selecting.

16. The parallel associative memory as claimed in claim 11, wherein said means for comparing further includes a multi-bit multiplier unit for performing a vector scalar product comparison between said recall pattern and each of the recalled recognition patterns.

17. The parallel associative memory as claimed in claim 16, wherein said means for comparing further includes means for receiving at least one mask for designating some portions of said recall pattern and each recognition pattern for said bit-wise comparison, and for designating other portions of said recall pattern and each recognition pattern for said vector scalar product comparison.

18. A parallel associative memory, comprising;

means for receiving a recall pattern;

a plurality of addressable memory means for storing and recalling a plurality of recognition patterns at respective addresses;

means for addressing said addressable memory means to contemporaneously recall a sequence of said stored recognition patterns from each of said addressable memory means;

means for contemporaneously comparing said recall pattern to the recognition patterns recalled from each of said addressable memory means;

means for selecting at least one recognition pattern that closely matches said recall pattern based upon the comparison by said means for comparing; and

means for outputting an indication of at least one recognition pattern selected by said means for selecting, wherein said means for comparing includes means for providing respective numerical values indicating the closeness of the recognition patterns compared to the recall pattern, and wherein said means for selecting includes means for identifying a certain number of the closest recognition patterns which are compared to the recall pattern, and means for sorting said certain number of the closest recognition patterns according to their respective numerical values indicating their closeness.

19. The parallel associative memory as claimed in claim 18, wherein said addressable memory means includes means for storing and recalling a parameter defining a radius of attraction for each recognition pattern, and said means for providing numerical values includes means for correlating the recall pattern with each recalled recognition pattern and adjusting the correlation for each recalled recognition pattern by an amount based on the respective parameter.

20. The parallel associative memory as claimed in claim 18, wherein said means for selecting includes means for rejecting recognition patterns which were compared to the recall pattern and have respective numerical values indicating that they are closer by at least a predetermined threshold value.

21. The parallel associative memory as claimed in claim 18, wherein said means for selecting includes means for rejecting recognition patterns which were compared to the recall pattern and which have respective numerical values indicating that they are further by at least a predetermined threshold value.

22. The parallel associative memory as claimed in claim 18, wherein said means for selecting includes means for rejecting recognition patterns which have portions selected by a "Subspace Mask" which fail to match corresponding portions of the recall pattern.

23. A parallel associative memory, comprising;

means for receiving a recall pattern;

a plurality of addressable memory means for storing and recalling a plurality of recognition patterns at respective addresses;

means for addressing said addressable memory means to contemporaneously recall a sequence of said stored recognition patterns from each of said addressable memory means;

means for contemporaneously comparing said recall pattern to the recognition patterns recalled from each of said addressable memory means;

means for selecting at least one recognition pattern that closely matches said recall pattern based upon the comparison by said means for comparing; and

means for outputting an indication of at least one recognition pattern selected by said means for selecting, wherein;

said means for comparing includes means for providing respective numerical values indicating the closeness of the recognition patterns compared to the recall pattern,

said means for selecting includes means for identifying a certain number of the closest recognition patterns which are compared to the recall pattern, and means for sorting said certain number of the closest recognition patterns according to their respective numerical values indicating their closeness,

said addressable memory means includes means for storing and recalling a parameter defining a radius of attraction for each recognition pattern, and said means for providing numerical values includes means for correlating the recall pattern with each recalled recognition pattern and adjusting the correlation for each recalled recognition pattern by an amount based on the respective parameter, and

said means for selecting includes means for rejecting recognition patterns which have portions selected by a "Subspace Mask" which fail to match corresponding portions of the recall pattern.

24. The parallel associative memory as claimed in claim 23, wherein said means for selecting includes means for rejecting recognition patterns which were compared to the recall pattern and have respective numerical values indicating that they are closer by at least a predetermined threshold value.