Fuzzy pattern comparator having automatic update threshold function

• US 5,272,657 A
• Filed: 07/26/1991
• Issued: 12/21/1993
• Est. Priority Date: 07/26/1991
• Status: Expired due to Fees

• Current Assignee: Microchip Technology Incorporated
• Original Assignee: American Neuralogix Incorporated
• Inventors: Trocine, Thomas M., Basehore, Paul M.
• Primary Examiner(s): NGUYEN, LONG
• Application Number:
  US07/735,518
• Time in Patent Office: 879 Days
• Field of Search: 364/715.06, 364/728.03, 364/715.01, 395/3, 395/21, 340/146.2, 382/30, 382/34
• US Class Current: 708/422
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation

Abstract

An apparatus and method for automatically updating a threshold in a fuzzy pattern comparator. A bit-field of an input data is simultaneously compared to simultaneously-input data patterns. An accumulated distance value is obtained for each data pattern, and the accumulated distance values are simultaneously compared with each other and a threshold to determine a minimum. The comparison is performed by a multipath feed-forward network which starts with the most significant bit and determines on a bit-by-bit basis and identifies which of the accumulated distance values and the threshold are a minimum. The threshold value is automatically updated to the minimum value during the comparison process if it is determined the threshold value is not a minimum. The automatic update threshold function is effective in pattern recognition systems which require periodic adaptation or adjustment in response to slowly changing pattern conditions.

Claims

1. A pattern comparator comprising:

means for simultaneously comparing a serial input signal to at least one pattern data signal, the comparing means simultaneously outputting at least one accumulated distance signal representing an accumulated difference between said serial input signal and said at least one pattern data signal;

means for determining whether said at least one accumulated distance signal is an optimum value relative to a threshold, said determining means outputting a threshold win signal when said at least one accumulated distance signal is not equal to said threshold; and

means for storing said threshold, said storing means updating said threshold with said optimum value in response to said threshold win signal and when said at least one accumulated distance signal is an optimum value relative to said threshold.

2. A pattern comparator as recited in claim 1, wherein said determining means determines a minimum value as said optimum value, said storing means updating said threshold with said minimum value in response to said threshold win signal and when said at least one accumulated distance signal is less than said threshold.

3. A pattern comparator as recited in claim 2, wherein said determining means simultaneously determines said minimum value from at least one of a plurality of said accumulated distance signals and said threshold value, said determining means including means for identifying a winner from said plurality of said accumulated distance values and said threshold value, said winner corresponding to said minimum value.

4. A pattern comparator as recited in claim 2, wherein said determining means comprises:

first means for determining a relative minimum signal between said at least one accumulated distance signal and a feedback signal, said determining means outputting a win signal when said at least one signal is output as said relative minimum signal;

second means for determining a relative minimum threshold signal between said threshold and said feedback signal simultaneously with said means for determining a relative minimum signal, said relative minimum threshold determining means outputting said threshold win signal when said threshold is output as said relative minimum signal;

means for generating said feedback signal in response to said relative minimum signal and said relative minimum threshold signal, said feedback signal generating means comparing corresponding significant bits of said relative minimum signal and said relative minimum threshold signal and outputting said feedback signal in response thereto.

5. A pattern comparator as recited in claim 1, wherein said means for comparing comprises at least one accumulator circuit comprising:

a distance determining circuit for determining a distance between said serial input signal and said corresponding at least one pattern data signal and outputting a distance signal representing said determined distance; and

means for accumulating said distance signal for a predetermined number of successive inputs of said serial input signal, said means for accumulating outputting said corresponding at least one accumulated distance signal.

6. A pattern comparator as recited in claim 5, wherein said means for accumulating comprises:

an adder circuit for adding said distance signal to a partial accumulated distance signal and for outputting an overflow signal and an addition result;

a register for storing said addition result as a partial updated accumulated distance signal, said register outputting said partial updated accumulated distance signal to said adder circuit as said partial accumulated distance signal; and

an array of ring counters outputting a counter signal, said counter signal being incremented by said array in response to said overflow signal, said counter signal and said partial accumulated distance signal output from said register forming said corresponding at least one accumulated distance signal.

7. A pattern comparator as recited in claim 1, wherein said means for determining comprises a multipath feedforward network for determining said optimum value.

8. A pattern comparator as recited in claim 7, wherein said multipath feedforward network comprises:

a first network layer comprising;

at least one primary neuron for simultaneously comparing corresponding significant bytes of said at least one accumulated distance signal and a feedback signal and outputting a corresponding first optimal comparison signal, said at least one primary neuron outputting an inverted WON signal when said corresponding first optimal comparison signal represents said at least one accumulated distance signal as an optimal value compared to said feedback signal, and

a primary threshold neuron for comparing, simultaneously with said at least one primary neuron, said corresponding significant bytes of said feedback signal and said threshold and outputting a first optimal threshold signal, said primary threshold neuron outputting said threshold win signal when said first optimal threshold signal represents said threshold as an optimal value compared to said feedback signal;

a second network layer comprising a NAND tree for determining different values for corresponding significant bits of said at least one corresponding first optimal comparison signal and said first optimal threshold signal, said NAND tree outputting said corresponding byte of said feedback signal representing a bit suppression signal, said feedback signal representing an inverse of said optimum value;

means for outputting said optimal value in response to said feedback signal; and

means for outputting a best match signal in response to said at least one inverted WON signal, said best match identifying said at least one pattern data signal as a best match to said serial input signal.

9. A pattern comparator as recited in claim 1, wherein said means for determining comprises a central processing unit for determining whether said at least one accumulated distance signal is said optimum value.

10. A pattern comparator as recited in claim 1, wherein said means for storing comprises a threshold register, said optimum value being latched by said threshold register in response to said threshold win signal.

11. A pattern comparator as recited in claim 1, wherein said optimum value is a minimum value.

12. A pattern comparator as recited in claim 1, wherein said optimum value is a maximum value.

13. A pattern comparator as recited in claim 1, wherein said optimal value is user-selectable as one of a minimum and maximum value.

14. A method of updating a threshold value in a pattern comparator comprising the steps of:

determining and outputting at least one accumulated distance signal representing an accumulated difference between a serial input signal input to said pattern comparator and at least one pattern data signal;

determining whether said at least one accumulated distance signal is an optimum value relative to a threshold stored in said pattern comparator; and

updating said threshold stored in said pattern comparator with said at least one accumulated distance signal if said at least one accumulated distance signal is said optimum value.

15. A pattern comparator comprising:

a pattern error accumulator for receiving input data representing a detected pattern and a plurality of pattern data representing a corresponding plurality of patterns, said pattern error accumulator simultaneously comparing said input data with each of said plurality of pattern data and outputting a plurality of distance signals corresponding to said plurality of pattern data, respectively;

means for simultaneously comparing said distance signals with a threshold value and outputting an optimum value signal relative to said threshold value, said simultaneously comparing means outputting a threshold win signal when said optimum value signal is an optimum value relative to said threshold value; and

means for storing said threshold, said storing means updating said threshold with said optimum value signal in response to said threshold win signal.

16. A pattern comparator as recited in claim 15, wherein said simultaneously comparing means determines a minimum value as said optimum value, said storing means updating said threshold with said minimum value when said minimum value is less than said threshold.

17. A pattern comparator as recited in claim 16, wherein said simultaneously comparing determining means simultaneously determines said minimum value from at least one of a plurality of said accumulated distance signals and said threshold value, said simultaneously comparing means including means for identifying a winner as said minimum value from said plurality of said accumulated distance values and said threshold value.

18. A pattern comparator as recited in claim 16, wherein said simultaneously comparing means comprises:

first means for determining a relative minimum signal between said distance signals and a feedback signal;

second means for determining a relative minimum threshold signal between said threshold and said feedback signal simultaneously with said first means, said second means outputting said threshold win signal when said threshold is output as said relative minimum threshold signal; and

means for generating said feedback signal in response to said relative minimum signal and said relative minimum threshold signal, said feedback signal generating means comparing corresponding significant bits of said relative minimum signal and said relative minimum threshold signal and outputting said feedback signal in response thereto.

19. A pattern comparator comprising:

means for simultaneously comparing an input signal to at least one pattern data signal, the comparing means outputting at least one accumulated distance signal representing an accumulated difference between said input signal and said at least one pattern data signal;

a feedforward network for simultaneously comparing said at least one distance signal with a threshold signal representing a current threshold value, said feedforward network outputting an optimized value signal representing an optimized value from said comparison of said at least one distance signal with said threshold signal, said feedforward network outputting a threshold win signal when said optimized value signal is an optimum value relative to said threshold signal; and

means for storing said threshold, said storing means updating said threshold with said optimum value in response to said threshold win signal and when said at least one accumulated distance signal is an optimum value relative to said threshold.

20. A pattern comparator as recited in claim 19, wherein said means for comparing comprises at least one accumulator circuit comprising:

a distance determining circuit for determining a distance between said serial input signal and said corresponding at least one pattern data signal and outputting a distance signal representing said determined distance; and

means for accumulating said distance signal for a predetermined number of successive inputs of said serial input signal, said means for accumulating outputting said corresponding at least one accumulated distance signal.

21. A pattern comparator as recited in claim 20, wherein said means for accumulating comprises:

an adder circuit for adding said distance signal to a partial accumulated distance signal and for outputting an overflow signal and an addition result;

a register for storing said addition result as a partial updated accumulated distance signal, said register outputting said partial updated accumulated distance signal to said adder circuit as said partial accumulated distance signal; and

an array of ring counters outputting a counter signal, said counter signal being incremented by said array in response to said overflow signal, said counter signal and said partial accumulated distance signal output from said register forming said corresponding at least one accumulated distance signal.

22. A pattern comparator as recited in claim 19, wherein said means for storing comprises a threshold register, said optimum value being latched by said threshold register in response to said threshold win signal.

23. A pattern comparator as recited in claim 19, wherein said optimum value is a minimum value.

24. A pattern comparator as recited in claim 19, wherein said optimum value is a maximum value.

25. A pattern comparator as recited in claim 19, wherein said optimum value is user-selectable as one of a minimum and maximum value.

26. A pattern comparator as recited in claim 19, wherein said means for simultaneously comparing outputs a selected significant byte of each of a plurality of said accumulated distance signals.

27. A pattern comparator as recited in claim 26, wherein said feedforward network simultaneously compares said selected significant bytes of said accumulated distance signals with a corresponding significant byte of said threshold signal, said feedforward network outputting a corresponding significant byte of said optimized value signal.

28. A pattern comparator as recited in claim 26, wherein said feedforward network simultaneously compares said selected significant bytes of said accumulated distance signals and said threshold signal with a corresponding significant byte of an external optimum distance value, said corresponding significant byte of said optimized value signal representing an optimized value from said comparison of said corresponding significant bytes of said accumulated distance signals with said threshold signal and said external optimum distance value.

29. A pattern comparator as recited in claim 19, wherein said feedforward network simultaneously compares said accumulated distance signals and said threshold signal with an external optimum distance value, said optimized value signal representing an optimized value from said comparison of said distance signals with said threshold signal and said external optimum distance value.

30. A pattern comparator as recited in claim 19, wherein said multipath feedforward network comprises:

a first network layer comprising;

a plurality of primary neurons for simultaneously comparing corresponding significant bytes of a plurality of said respective accumulated distance signals with a feedback signal and outputting first optimal comparison signals, respectively, at least one of said primary neurons outputting an inverted WON signal when said respective first optimal comparison signal is an optimal value compared to said feedback signal, and

a primary threshold neuron for comparing, simultaneously with said plurality of primary neurons, said corresponding significant bytes of said feedback signal and said threshold and outputting a first optimal threshold signal, said primary threshold neuron outputting said threshold win signal when said first optimal threshold signal is an optimal value compared to said feedback signal;

a second network layer comprising a NAND tree for determining different values for corresponding significant bits of said first optimal comparison signal and said first optimal threshold signal, said NAND tree outputting said corresponding byte of said feedback signal representing a bit suppression signal, said feedback signal representing an inverse of said optimum value;

means for outputting said optimal value in response to said feedback signal; and

means for outputting a best match signal in response to said at least one inverted WON signal, said best match identifying said at least one pattern data signal as a best match to said serial input signal.

31. A pattern comparator comprising:

means for comparing a serial input signal to at least one pattern data signal, the comparing means outputting at least one accumulated distance signal representing an accumulated difference between said serial input signal and said at least one pattern data signal;

means for determining whether said at least one accumulated distance signal is an optimum value relative to a threshold and for outputting said optimum value, said determining means outputting a threshold win signal when said at least one accumulated distance signal is not equal to said threshold; and

a memory for storing said threshold, said memory updating said threshold with said optimum value in response to said threshold win signal and when said at least one accumulated distance signal is an optimum value relative to said threshold.

32. A pattern comparator as recited in claim 31, wherein said determining means determines a minimum value as said optimum value, said memory updating said threshold with said minimum value in response to said threshold win signal and when said at least one accumulated distance signal is less than said threshold.

33. A pattern comparator as recited in claim 32, wherein said determining means simultaneously determines said minimum value from at least one of a plurality of said accumulated distance signals and said threshold value, said determining means including means for identifying a winner from said plurality of said accumulated distance values and said threshold value, said winner corresponding to said minimum value.

34. A pattern comparator as recited in claim 32, wherein said determining means comprises:

first means for determining a relative minimum signal between said at least one accumulated distance signal and a feedback signal;

second means for determining a relative minimum threshold signal between said threshold and said feedback signal simultaneously with said first means, said second means outputting said threshold win signal when said threshold is output as said relative minimum threshold signal; and

means for generating said feedback signal in response to said relative minimum signal and said relative minimum threshold signal, said feedback signal generating means comparing corresponding significant bits of said relative minimum signal and said relative minimum threshold signal and outputting said feedback signal in response thereto.

35. A pattern comparator as recited in claim 31, wherein said means for comparing comprises at least one accumulator circuit comprising:

a distance determining circuit for determining a distance between said serial input signal and said corresponding at least one pattern data signal and outputting a distance signal representing said determined distance; and

means for accumulating said distance signal for a predetermined number of successive inputs of said serial input signal, said means for accumulating outputting said corresponding at least one accumulated distance signal.

36. A pattern comparator as recited in claim 35, wherein said means for accumulating comprises:

an adder circuit for adding said distance signal to a partial accumulated distance signal and for outputting an overflow signal and an addition result;

a register for storing said addition result as a partial updated accumulated distance signal, said register outputting said partial updated accumulated distance signal to said adder circuit as said partial accumulated distance signal; and

an array of ring counters outputting a counter signal, said counter signal being incremented by said array in response to said overflow signal, said counter signal and said partial accumulated distance signal output from said register forming said corresponding at least one accumulated distance signal.

37. A pattern comparator as recited in claim 31, wherein said means for determining comprises a multipath feedforward network.

38. A pattern comparator as recited in claim 37, wherein said multipath feedforward network comprises:

a first network layer comprising;

at least one primary neuron for simultaneously comparing corresponding significant bytes of said at least one accumulated distance signal and a feedback signal and outputting a corresponding first optimal comparison signal, said at least one primary neuron outputting an inverted WON signal when said corresponding first optimal comparison signal represents said at least one accumulated distance signal as an optimal value compared to said feedback signal, and

a primary threshold neuron for comparing, simultaneously with said at least one primary neuron, said corresponding significant bytes of said feedback signal and said threshold and outputting a first optimal threshold signal, said primary threshold neuron outputting said threshold win signal when said first optimal threshold signal represents said threshold as an optimal value compared to said feedback signal;

a second network layer comprising a NAND tree for determining different values for corresponding significant bits of said at least one corresponding first optimal comparison signal and said first optimal threshold signal, said NAND tree outputting said corresponding byte of said feedback signal representing a bit suppression signal, said feedback signal representing an inverse of said optimum value;

means for outputting said optimal value in response to said feedback signal; and

means for outputting a best match signal in response to said at least one inverted WON signal, said best match identifying said at least one pattern data signal as a best match to said serial input signal.

39. A pattern comparator as recited in claim 31, wherein said means for determining comprises a central processing unit.

40. A pattern comparator as recited in claim 31, wherein said optimum value is a minimum value.

41. A pattern comparator as recited in claim 31, wherein said optimum value is a maximum value.

42. A method of updating a threshold value in a pattern comparator comprising the steps of:

simultaneously inputting a serial input signal and a plurality of pattern data signals to said pattern comparator and causing said pattern comparator to simultaneously generate a partial distance signal for each of said plurality of pattern data signals, said partial distance signal representing a distance between said serial input signal and said respective pattern data signal;

causing said pattern comparator to accumulate said partial distance signal for a predetermined number of successive inputs of said serial input signal to obtain an accumulated distance signal;

causing said pattern comparator to simultaneously output said accumulated distance signal for each of said pattern data signals;

simultaneously comparing said plurality of accumulated distance signals and a threshold stored in said pattern comparator to determine whether any of said accumulated distance signals is selected as an optimum value relative to said threshold; and

updating said threshold stored in said pattern comparator with said selected accumulated distance signal if said selected accumulated distance signal is said optimum value.

43. A pattern comparator that continually updates a threshold value, comprising:

a pattern error accumulator for receiving input data representing a detected pattern and a plurality of pattern data representing a corresponding plurality of patterns, said pattern error accumulator outputting a plurality of distance signals corresponding to said plurality of pattern data, respectively;

a feedforward network for simultaneously comparing said distance signals with a threshold signal representing a current threshold value, said feedforward network outputting an optimized value signal representing an optimized value from said comparison of said distance signals with said threshold signal, said feedforward network outputting a threshold win signal when said optimized value signal is an optimum value relative to said threshold signal; and

a threshold logic circuit for outputting said threshold signal representing said current threshold value, said threshold logic circuit updating said current threshold value with said optimized value signal in response to threshold win signal.

44. A pattern comparator as recited in claim 43, wherein said input data and each of said pattern data each comprise a user-selectable bit-field.

45. A pattern comparator as recited in claim 43, wherein each of said distance signals represent an accumulated error between a predetermined number of successive samples of said input data and said corresponding pattern data.

46. A pattern comparator as recited in claim 43, wherein said pattern error accumulator simultaneously outputs a selected significant byte of each of said distance signals.

47. A pattern comparator as recited in claim 46, wherein said feedforward network simultaneously compares said selected significant bytes of said distance signals with a corresponding significant byte of said threshold signal, said feedforward network outputting a corresponding significant byte of said optimized value signal.

48. A pattern comparator as recited in claim 46, wherein said feedforward network simultaneously compares said selected significant bytes of said distance signals and said threshold signal with a corresponding significant byte of an external optimum distance value, said corresponding significant byte of said optimized value signal representing an optimized value from said comparison of said corresponding significant bytes of said distance signals with said threshold signal and said external optimum distance value.

49. A pattern comparator as recited in claim 43, wherein said feedforward network simultaneously compares said distance signals and said threshold signal with a an external optimum distance value, said optimized value signal representing an optimized value from said comparison of said distance signals with said threshold signal and said external optimum distance value.

50. A pattern comparator as recited in claim 43, wherein said feedforward network comprises:

a first network layer comprising;

a plurality of primary neurons for simultaneously comparing corresponding significant bytes of said respective distance signals with a feedback signal and outputting first optimal comparison signals, respectively, at least one of said primary neurons outputting an inverted WON signal when said respective first optimal comparison signal is an optimal value compared to said feedback signal, and

a primary threshold neuron for comparing, simultaneously with said plurality of primary neurons, said corresponding significant bytes of said feedback signal and said threshold and outputting a first optimal threshold signal, said primary threshold neuron outputting said threshold win signal when said first optimal threshold signal is an optimal value compared to said feedback signal;

a second network layer comprising a NAND tree for determining different values for corresponding significant bits of said first optimal comparison signals and said first optimal threshold signal, said NAND tree outputting said corresponding byte of said feedback signal representing a bit suppression signal, said feedback signal representing an inverse of said optimum value;

means for outputting said optimal value in response to said feedback signal; and

means for outputting a best match signal in response to said at least one inverted WON signal, said best match identifying said at least one pattern data signal as a best match to said serial input signal.

51. A pattern comparator that continually updates a threshold value, comprising:

a pattern error accumulator for receiving input data representing a detected pattern and a plurality of pattern data representing a corresponding plurality of patterns, said pattern error accumulator simultaneously comparing said input data with each of said plurality of pattern data and outputting a plurality of distance signals corresponding to said plurality of pattern data, respectively;

a feedforward network for simultaneously comparing said distance signals with a threshold signal representing a current threshold value and an external input signal, said feedforward network outputting an optimized value signal representing an optimized value from said comparison of said distance signals with said threshold signal and said external input signal, said feedforward network outputting a threshold win signal when said threshold signal is not an optimum value relative to said distance signals and said external input signal;

an expansion bus interface for outputting said optimized value signal onto an expansion bus adapted to connect said pattern comparator to other pattern comparators, said expansion bus interface reading from said expansion bus an optimum value relative to said optimized value signal and said other pattern comparators, said expansion bus interface outputting said external input signal representing said optimum value read from said expansion bus; and

a threshold logic circuit for outputting said threshold signal representing said current threshold value, said threshold logic circuit updating said current threshold value with said external input signal in response to said threshold win signal.

52. A pattern comparator as recited in claim 51, wherein said input data and each of said pattern data each comprise a user-selectable bit-field.

53. A pattern comparator as recited in claim 52, wherein each of said distance signals represent an accumulated error between a predetermined number of successive samples of said input data and said corresponding pattern data.

54. A pattern comparator as recited in claim 53, wherein said pattern error accumulator simultaneously outputs a selected significant byte of each of said distance signals.

55. A pattern comparator as recited in claim 54, wherein said feedforward network simultaneously compares said selected significant bytes of said distance signals with a corresponding significant byte of said threshold signal, said feedforward network outputting a corresponding significant byte of said optimized value signal.