Content addressable memory

• US 4,805,093 A
• Filed: 10/14/1986
• Issued: 02/14/1989
• Est. Priority Date: 10/14/1986
• Status: Expired due to Term

• Current Assignee: Calvin B. Ward
• Original Assignee: Calvin B. Ward
• Inventors: Ward, Calvin B.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): RUDOLPH, REBECCA
• Application Number:
  US06/918,766
• Time in Patent Office: 854 Days
• Field of Search: 364/200 MS File, 364/ 900 MS File
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

A content addressable memory for storing data words wherein each data word includes one or more characters is disclosed. One or more of the characters stored in said content addressable memory may be retrieved in response to commands from a controller coupled to the content addressable memory. The controller includes command circuitry for generating and coupling a plurality of control signals to the content addressable memory, including control signals defining a specification character. The controller also contains response circuitry for receiving a plurality of response signals from the content addressable memory. These response signals include signals specifying a character stored in the content addressable memory. The content addressable memory is constructed from a plurality of storage sections. Each storage section includes control bus coupling circuitry for coupling that storage section to the controller and to the other storage sections. Each storage section also includes circuitry for storing one data word and circuitry for separately selecting each character of the data word so stored. Each storage section may be in one of two states, active or inactive, specified by circuitry contained therein. Each storage section also includes processing circuitry for processing the selected character in response to the control signals. The processing employed is specified by on the control signals, the selected character, the state of the storage section, the specification character, and whether or not the storage section is the first active storage section.

Claims

1. A content addressable memory for storing a plurality of data words and selectively retrieving specified said data words in response to a specification word comprising a plurality of specification characters, said content addressable being adapted for use in a host data processing system, said content addressable memory comprising:

a plurality of storage sections; and

control bus means for coupling each said storage section to the other said storage sections and to said host data processing system, said control bus means including means for coupling a plurality of control signals to each said storage section and means for coupling a said specification character comprising W binary bits to each said storage section, wherein W is greater than 2 and wherein

each said storage section comprises;

data word storing means for storing a said data word comprising a plurality of characters, each said character comprising W binary bits, the number of said characters being greater than 2, said storing means including means for separately selecting each character in said data word, the character so selected being determined by a first one of said control signals;

flag means for specifying one of two states, active or inactive, for said storage section; and

processing means for causing said flag means to specify one of said two states operative in response to said control signals, said specification character, and said selected character, said processing means including;

means for causing said flag means to specify the active state for said storage section operative in response to a second one of said control signals; and

reset means for causing said flag means to specify the inactive state for said storage section operative in response to a third one of said control signals and a specified relationship between said specification character and said selected character,

wherein, said bus means further comprises means for determining if any of said flag means specifies the active state, said determining means including means for generating a signal if any of said flag means specifies the active state.

2. The content addressable memory of claim 1 wherein said reset means comprises comparing means for causing said flag means to indicate the inactive state for said storage section if said specification character does not match said selected character.

3. The content addressable memory of claim 1 wherein each means for selecting a character further comprises:

means for determining the position of said selected character relative to the first character of said stored data word; and

means for storing information specifying the maximum number of characters which may be stored in said data word storing means, and wherein

said reset means further comprising overflow means for causing said flag means to specify the inactive state for said storage section if the position of said selected character relative to the beginning of said stored data word is greater than said maximum number of characters, said reset means being responsive to a fourth one of said control signals.

4. The content addressable memory of claim 1 wherein each said means for selecting a character further comprises:

means for determining the position of said selected character relative to the first character of said stored data word;

means for storing information specifying the maximum number of characters which may be stored in said data word storing means; and

means for causing said selected character to comprise a predetermined character if said determined position is greater than said maximum number of characters in said storage section.

5. The content addressable memory of claim 1 wherein said plurality of storage sections are organized as a linearly ordered array having a first storage section, a last storage section, one or more intermediate storage sections, each said storage section further including path means comprising:

means for receiving a signal from the adjacent storage section closest to said first storage section in said linearly ordered array of storage sections, and means for coupling said received signal to the receiving means of the adjacent storage section closest to said last storage section of said linearly ordered array of storage sections if said storage section is not in the active state,

said means for determining if any of said flag means specify the active state comprising;

means for coupling a signal to the receiving means of said first storage section; and

means for detecting a signal from the coupling means of said last storage section.

6. The content addressable memory of claim 1 wherein said data word storage means comprises:

shift register means comprising;

means for receiving a shift signal; and

register means comprising an ordered array of storage locations, one said storage location for storing each character of said stored data word, each said storage location including input means for receiving signals specifying a character to be stored therein upon the receipt of said shift signal and an output means for coupling signals specifying the character stored therein upon receipt of said shift signal;

the input means of each storage location being operatively coupled to the output means of the preceding storage location, except for the last said storage location in which the input means is coupled to the output means of the first storage location, and

wherein said mean for specifying a character of said data word specifies the character stored in a predetermined one of said storage locations, said predetermined storage location being operatively coupled to said processing means.

7. The content addressable memory of claim 1 wherein said data word storage means comprises:

random access storage means comprising a plurality of storage locations, one character of said data word being stored in each said storage location, each said storage location comprising means for storing W binary bits;

pointer means for selecting one of said storage locations, said selected storage location being determined by a storage control signal comprising one of said control signals; and

coupling means for coupling the storage location selected by said pointer means to said processing means.

8. The content addressable memory of claim 7 wherein said storage locations are arranged in a predetermined order and said pointer means includes means, responsive to a reset memory signal comprising one of said control signals, for selecting the first said storage location and means for selecting the next sequential storage location relative to the currently selected storage section, said means being responsive to an increment memory control signal comprising one of said control signals.

9. The content addressable memory of claim 7 wherein said coupling means for coupling the storage location specified by said pointer means to said processing means comprises:

data bus means for coupling said selected storage location to said processing means, said data bus means comprising a plurality of data bus conductors, each said data bus conductor being used to couple a signal corresponding to one of said binary bits to said processing means.

10. The content addressable memory of claim 9 wherein said control bus means includes specification character coupling means for coupling said specification character to each said processing means, said specification character coupling means comprising a plurality of conductors, one said conductor corresponding to each of said data bus conductors in said data bus means.

11. The content addressable memory of claim 10 wherein said processing means further comprises means for comparing the signal on each data bus conductor in said data bus means to the signal on the corresponding conductor in said specification character coupling means;

and said reset means comprises means for causing said flag means to specify the inactive state for said storage section if the signal on one of said data bus conductors does not match the signal on the corresponding conductor in said specification character coupling means.

12. The content addressable memory of claim 10 wherein each of said storage locations comprises a storage location conductor and a plurality of storage links for selectively coupling a potential to selected ones of said data bus conductors if a predetermined potential is present on said storage location conductor, said selected data bus conductors being determined by whether or not the corresponding binary bit in said stored character is a "1", said storage link allowing a current to flow in only one direction between said storage location conductor and said selected data bus conductors,

wherein said pointer means comprises means for coupling said predetermined potential to the storage location conductor corresponding to said selected character, and

wherein said processing means further comprises means for sensing a potential on each of said data bus conductors.

13. The content addressable memory of claim 12 wherein each said storage link comprises a diode connecting said storage location conductor to one of said selected data bus conductors.

14. The content addressable memory of claim 10 wherein each of said storage locations comprises a storage location conductor and a plurality of storage links, each said storage link coupling said storage location conductor to one of said data bus conductors, each said storage link comprising a two terminal circuit comprising a fuse link in series with a diode means for restricting the flow of current in said two terminal circuit to one direction, one of said terminals being coupled to said storage location conductor and the other of said terminals being coupled to one of said data bus conductors, said fuse link having two states, a closed state in which said fuse link will pass a current in response to a potential applied across said fuse link and an open state in which said fuse link will not pass a current, said fuse link being in the closed state in those storage links which couple said storage location conductor to a data bus conductor corresponding to a binary bit having a first binary value in the character stored in said storage location, and in the open state in all other storage links, and

wherein said pointer means comprises means for coupling a predetermined potential to the storage location conductor in the selected storage location, and wherein said processing means includes means for sensing a potential on each of said data bus conductors.

15. The content addressable memory of claim 1 wherein said plurality of storage sections are organized as a linearly ordered array beginning with a first storage section, ending with a last storage section, and having one or more intermediate storage sections, each said storage section further comprising:

first active means for determining if said storage section is the first storage section having a flag means specifying the active state relative to the beginning of said linearly ordered array, said first active means including means for generating a first active signal in response to said determination, and

readout means for coupling response signals specifying said selected character to said control bus means, said readout means being responsive to said first active signal and a fourth one of said control signals.

16. The content addressable memory of claim 15 wherein each said flag means further comprising

disconnect means, responsive to a disconnect signal coupled to said storage section on said control bus means and said first active signal, for specifying a disconnected state for said storage section, said disconnected state being specified by the coincidence of said first active signal and first disconnect signal, wherein when said disconnected state is specified for said storage section, said flag means specifies the inactive state for said storage section.

17. The content addressable memory of claim 15 wherein said flag means comprises first and second one bit memory cells and a two input AND circuit, each said memory cell providing a "false" output when a "0" is stored therein, said first memory cell including means for storing a "1" in said memory cell operative in response to said first control signal and means for storing a "0" in said memory cell operative in response to said reset means, said second one bit memory cell including means for storing a "0" therein operative in response to the coincidence of said first active signal and said first disconnect signal, the inputs of said two input AND gate being the outputs of said first and second memory cells, said AND gate generating a "true" output if both said inputs are "1" and a "true" output of said two input AND gate comprising a signal indicating that said storage section is in the active state.

18. The content addressable memory of claim 17 further comprising means for causing said second one bit memory cell to store a "1" operative in response to a second disconnect signal being coupled to said storage section.

19. The content addressable memory of claim 17 wherein said second one bit memory cell comprises a fuse link.

20. The content addressable memory of claim 17 wherein said second one bit memory cell comprises an electrically programmable read-only memory cell.

21. The content addressable memory of claim 15 wherein said first active means comprises:

path means comprising means for receiving a signal from the adjacent storage section closest to said first storage section in said linearly ordered array of storage sections, and means for coupling said received signal to the receiving means of the adjacent storage section closest to said last storage section of said linearly ordered array of storage sections if said storage section is not in the active state,

said content addressable memory further comprises means for coupling a signal to the receiving means of said first storage section;

said first active means in each said storage section comprises;

means for detecting a signal on the receiving means of said path means in coincidence with said flag means specifying the active state for said storage section, and

said means for determining if any of said flag means specify the active state comprises means for detecting a signal from the coupling means of said last storage section.

22. The content addressable memory of claim 21 wherein said content addressable memory further comprising:

by-pass means for coupling the receiving means of the path means of said first storage section to the receiving means of the path means of the storage section determined to be the first storage section having a flag means specifying the active state relative to said first said storage section.

23. The content addressable memory of claim 22 wherein said by-pass means comprises:

a conductor coupled to the receiving means of said first storage section; and

gate means in each said storage section for coupling the coupling means of the path means of said storage section to said conductor if a predetermined signal is coupled to the receiving means of said storage section and the flag means in said storage section indicates the inactive state for said storage section.

24. The content addressable memory of claim 15 wherein said data word storage means comprises:

shift register means comprising;

means for receiving a shift signal; and

register means comprising an ordered array of storage locations, one said storage location for storing each character of said stored data word, each said storage location including input means for receiving signals specifying a character to be stored therein upon the receipt of said shift signal and an output means for coupling signals specifying the character stored therein upon receipt of said shift signal;

the input means of each storage location being operatively coupled to the output means of the preceding storage location, except for the last said storage location in which the input means is coupled to the output means of the first storage location, and

wherein said mean for selecting a character of said data word specifies the character stored in a predetermined one of said storage locations, said predetermined storage location being operatively coupled to said processing means and said readout means.

25. The content addressable memory of claim 15 wherein said data word storage means comprises:

random access storage means comprising a plurality of storage locations, one character of said data word being stored in each said storage location, each said storage location comprising means for storing W binary bits;

pointer means for selecting one of said storage locations, said selected storage location being determined by a storage control signal comprising one of said control signals; and

coupling means for coupling the storage location selected by said pointer means to said processing means and said readout means.

26. The content addressable memory of claim 25 wherein said storage locations are arranged in a predetermined order and said pointer means includes means, responsive to a reset memory signal comprising one of said control signals, for selecting the first said storage location and means for selecting next sequential storage location relative to the currently selected storage section, said means being responsive to an increment memory control signal comprising one of said control signals.

27. The content addressable memory of claim 25 wherein said coupling means for coupling the storage location specified by said pointer means to said processing means and said readout means comprises:

data bus means for coupling said selected storage location to said processing means and said readout means, said data bus means comprising a plurality of data bus conductors, each said data bus conductor being used to couple a signal corresponding to one of said binary bits to said processing means and said readout means.

28. The content addressable memory of claim 27 wherein said specification character coupling means includes a plurality of conductors, one said conductor corresponding to each of said data bus conductors in said data bus means.

29. The content addressable memory of claim 28 wherein said processing means further comprises means for comparing the signal on each data bus conductor in said data bus means to the signal on the corresponding conductor in said specification character coupling means and means for causing said flag means to specify the inactive state for said storage section if the signal on one of said data bus conductors does not match the signal on the corresponding conductor in said specification character coupling means.

31. The content addressable memory of claim 28 wherein each of said storage locations comprises a storage location conductor and a plurality of storage links for selectively coupling a potential to selected ones of said data bus conductors, if a predetermined potential is present on said storage location conductor, said selected data bus conductors being determined by whether or not the corresponding binary bit in said stored character is a "1", said storage link allowing a current to flow in only one direction between said storage location conductor and said selected data bus conductors,

wherein said pointer means comprises means for coupling said predetermined potential to the storage location conductor corresponding to said selected storage location, and

wherein said processing means further comprises means for sensing a potential on each of said data bus conductors

32. The content addressable memory of claim 31 wherein each said storage link comprises a diode connecting said storage location conductor to one of said selected data bus conductors.

33. The content addressable memory of claim 28 wherein each of said storage locations comprises a storage location conductor and a plurality of storage links, each said storage link coupling said storage location conductor to one of said data bus conductors, each said storage link comprising a two terminal circuit comprising a fuse link in series with a diode means for restricting the flow of current in said two terminal circuit to one direction, one of said terminals being coupled to said storage location conductor and the other of said terminals being coupled to one of said data bus conductors, said fuse link having two states, a closed state in which said fuse link will pass a current in response to a potential applied across said fuse link and an open state in which said fuse link will not pass a current, said fuse link being in the closed state in those storage links which couple said storage location conductor to a data bus conductor corresponding to a binary bit having a first binary value in the character stored in said storage location, and in the open state in all other storage links, and

wherein said pointer means comprises means for coupling a predetermined potential to the storage location conductor corresponding to the selected storage location, and wherein said processing means includes means for sensing a potential on each of said data bus conductors.

34. The content addressable memory of claim 15 wherein each said storage section further comprises:

means for selecting an input character comprising one of the characters of said stored data word, said input character selecting means being responsive to a fifth one of said control signals;

means for generating an input signal operative in response to said first active signal and a sixth one of said control signals; and

input means for causing said input character to match the character of said specification word coupled to said storage section on said control bus means, said input means being responsive to said input signal.

35. The content addressable memory of claim 34 wherein said first active means comprises:

path means comprising for receiving a signal from the adjacent storage section closest to said first storage section in said linearly ordered array of storage sections, and means for coupling said received signal to the receiving means of the adjacent storage section closest to said last storage section of said linearly ordered array of storage sections if said storage section is not in the active state,

wherein said content addressable memory further comprises means for coupling a signal to the receiving means of said first storage section;

wherein said first active means in each said storage section comprises

means for detecting a signal on the receiving means of said path means in coincidence with said flag means specifying the active state for said storage section, and

wherein said means for determining if any of said flag means specify the active state comprises means for detecting a signal from the coupling means of said last storage section.

36. The content addressable memory of claim 34 wherein said data word storage means comprises:

shift register means comprising;

means for receiving a shift signal; and

register means comprising an ordered array of storage locations including a first storage location, a last storage location, one said storage location for storing each character of said stored data word, each said storage location including input means for receiving signals specifying a character to be stored therein upon the receipt of said shift signal and an output means for coupling signals specifying the character stored therein upon receipt of said shift signal;

the input means of each storage location being operatively coupled to the output means of the preceding storage location, the input means of said first storage location being operatively coupled to said input means and the output means of said last storage location being operatively coupled to said readout means;

wherein said mean for selecting a character of said data word specifies the character stored in said last storage location, the output means of said last storage location being operatively coupled to said processing means and said readout means,

and wherein said input means comprises

means for coupling the output means of said last storage location to the input means of said first storage location if said input signal is not generated and means for coupling signals specifying said specification character to the input means of said first storage location if said input signal is generated.

37. The content addressable memory of claim 34 wherein said data word storage means comprises:

random access storage means comprising

a plurality of storage locations, one character of said data word being stored in each said storage location, each said storage location comprising means for storing W binary bits;

pointer means for specifying one of said storage locations, said specified storage location being determined by a storage control signal comprising one of said control signals; and

coupling means for coupling the storage location specified by said pointer means to said processing means, said readout means, and said input means,

wherein said input means comprises means responsive to said input signal for causing the character stored in the storage location specified by said pointer means to match said specification character.

38. The content addressable memory of claim 37 wherein said storage locations are arranged in a predetermined order and said pointer means includes means, responsive to a reset memory signal comprising one of said control signals, for selecting the first said storage location and means for selecting next sequential storage location relative to the currently selected storage section, said means being responsive to an increment memory control signal comprising one of said control signals.

39. The content addressable memory of claim 37 wherein said coupling means for coupling the storage location specified by said pointer means to said processing means and said readout means comprises:

data bus means for coupling said selected storage location to said processing means, said readout means, and said input means, said data bus means comprising a plurality of data bus conductors, each said data bus conductor being used to couple a signal corresponding to one of said binary bits to said processing means, said readout means, and said input means.

40. The content addressable memory of claim 39 wherein said specification character coupling means includes a plurality of conductors, one said conductor corresponding to each of said data bus conductors in said data bus means.

42. The content addressable memory of claim 40 wherein said readout means comprises a plurality of gate means for coupling each of said data bus conductors to the corresponding conductor in said specification character coupling means, each said gate means being responsive to the coincidence of said first active signal and a readout control signal comprising one of said control signals.

43. The content addressable memory of claim 40 wherein each of said storage locations comprises a storage location conductor and a plurality of storage links, each said storage link coupling said storage location conductor to one of said data bus conductors, each said storage link comprising a two terminal circuit comprising a fuse link in series with a diode means for restricting the flow of current in said two terminal circuit to one direction, one of said terminals being coupled to said storage location conductor and the other of said terminals being coupled to one of said data bus conductors, said fuse link having two states, a closed state in which said fuse link will pass a current in response to a potential applied across said fuse link and an open state in which said fuse link will not pass a current, said fuse link being in the closed state in those storage links which couple said storage location conductor to a data bus conductor corresponding to a binary bit having a first binary value in the character stored in said storage location, and in the open state in all other storage links, each said fuse link irreverseably changing from a first state comprising one of said open and closed states to a second state comprising the other of said open and closed states when a current greater than a predetermined current passes through said fuse link, and

wherein said pointer means comprises means for coupling one of two predetermined potentials to the storage location conductor in the selected storage location, said first predetermined potential being sufficient to cause a current greater than said predetermined current to pass through said fuse link if said fuse link is in said first state and said readout means couples the data bus conductor connected to the storage link containing said fuse link to a grounded conductor, and said second predetermined potential is insufficient to cause a current greater than said predetermined current to flow in said fuse link when said fuse link is in said first state and said readout means couples the data bus conductor connected to the storage link containing said fuse link to a grounded conductor, said first predetermined potential being coupled to said storage location conductor in response to said input signal and said second predetermined potential being coupled to said storage location conductor at all other times.

54. The content addressable memory of claim 34 wherein said storage means further comprising means for storing a scratch character and means for selecting said scratch character, said selecting means including means for coupling said scratch character to said processing means operative in response to a scratch character coupling signal comprising one of said control signals.

55. The content addressable memory of claim 54 wherein said means for storing a scratch character comprises one storage location normally used for storing a character of a data word.

30. The content addressable memory of 28 wherein said readout means comprises a plurality of gate means for coupling each of said data bus conductors to the corresponding conductor in said specification character coupling means, each said gate means being responsive to the coincidence of said first active signal and a readout control signal comprising one of said control signals.

41. The content addressable memory of 40 wherein said processing means further comprises means for comparing the signal on each data bus conductor in said data bus means to the signal on the corresponding conductor in said specification character coupling means and means for causing said flag means to specify the inactive state for said storage section if the signal on one of said data bus conductors does not match the signal on the corresponding conductor in said specification character coupling means.

44. The content addressable memory of 15 wherein an order is defined for the characters stored in said content addressable memory, said order defining comparison relationships between said characters such that a first given character may be less than, equal to, or greater than a second given character and wherein said processing means further comprises:

compare state means for specifying three states, greater than, less than, and equal, for said storage section including means responsive to a compare reset control signal comprising one of said control signals for causing said compare state means to specify the equal state for said storage section;

ordered comparing means for comparing said specification character to said selected character, for causing said said compare state means to specify the greater than state for said storage section if said storage section was in the equal state and said selected character was greater than said character of said specification word, and for causing said compare state means to specify the less than state for said storage section if said storage section was in the equal state and said selected character was less than said character of said specification word, said ordered comparing means being responsive to a numerical compare control signal comprising one of said control signals;

means for causing said flag means to specify the inactive state for said storage section if said compare state means specifies the greater than state for said storage section, said means being responsive to a reset if greater than control signal comprising one of said control signals;

means for causing said flag means to specify the inactive state for said storage section if said compare state means specifies the less than state for said storage section, said means being responsive to a reset if less than control signal comprising one of said control signals; and

means for causing said flag means to specify the inactive state for said storage section if said compare state means specifies the equal state for said storage section, said means being responsive to a reset if equal control signal comprising one of said control signals.

45. The content addressable memory of claim 44 wherein said processing means further comprising means for causing said flag means to specify the inactive state for said storage section if said compare state means specifies the greater than state for said storage section, said means being responsive to a reset if greater than control signal comprising one of said control signals;

46. The content addressable memory of 44 wherein said ordered comparing means comprises means for comparing the numerical representation of said specification character to the numerical representation of said selected character.

47. The content addressable memory of 15 wherein each said storage section further comprising:

distance means for storing a number;

means for storing a predetermined number in said distance means operative in response to a distance register reset signal comprising one of said control signals;

means for computing a function value depending on said selected character and said specification character and for adding the said function value to the number stored in said distance mean operative in response to a distance calculating signal comprising one of said control signals; and

reset means for causing said flag means to specify the inactive state for said storage section if the number stored in said distance means has a specified numerical relationship to a number comprising a specification character communicated on said control bus, said reset means being responsive to a distance compare signal comprising one of said control signals.

48. The content addressable memory of claim 47 wherein said reset means comprises means for causing said flag to be specify the inactive state if the number stored in said distance means is greater than said the number comprising said specification character.

49. The content addressable memory of claim 47 wherein said reset means comprises means for causing said flag to be specify the inactive state if the number stored in said distance means is greater than or equal to said the number comprising said specification character.

50. The content addressable memory of claim 47 wherein said reset means comprises means for causing said flag to be specify the inactive state if the number stored in said distance means is less than to said the number comprising said specification character.

51. The content addressable memory of claim 47 wherein said function value depends on the difference of the numerical representation of said selected character and the numerical representation of said specification character.

52. The content addressable memory of claim 47 wherein each said storage section further comprises means for storing a plurality of character weights, one such character weight corresponding to each character of the data word stored in said storage section and wherein said function value depends on the selected character, the character weight corresponding to said character and the specification character.

53. The content addressable memory of claim 52 wherein said function value depends on the product of said character weight and the difference of the numerical representation of said selected character and the numerical representation of said specification character.