DE3587137T2

DE3587137T2 - Inhaltsadressierbarer speicher.

Info

Publication number: DE3587137T2
Application number: DE8585113907T
Authority: DE
Inventors: Kousuke Takahashi; Hachiro Yamada
Original assignee: NEC Corp; Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1984-10-31
Filing date: 1985-10-31
Publication date: 1993-09-09
Anticipated expiration: 2005-11-01
Also published as: EP0180239A2; JPS61107596A; EP0180239A3; EP0180239B1; US4755974A; DE3587137D1; JPH0519238B2

Description

GEBIET DER ERFINDUNG

Die vorliegende Erfindung betrifft einen inhalts-adressierbaren Speicher oder eine Speicher-Anordnung, welche entsprechend den Speicherinhalten adressiert werden kann.

BESCHREIBUNG DES STANDES DER TECHNIK

Gegenwärtig wird eine Vielfalt inhalts-adressierbarer Speicher (CAMs) als wichtige Komponente der Computer für verschiedene Zwecke verwendet. In einigen Anwendungen wird ein CAM zur Speicherung der Übereinstimmung zwischen den Sektoren eines Puffer-Speichers und den Adressen des Hauptspeichers verwendet, so daß durch Mittel der Speicher- Inhalts-Suche eine Adressen-Auflistung von der logischen zur physikalischen Adresse mit hoher Geschwindigkeit durchgeführt werden kann. Diese Art des CAMs benötigt inhaltsadressierbare Speicherzellen, bei denen jede mit einer Schaltung zur Ermittlung einer Äquivalenz oder Koinzidenz zwischen dem Speicherinhalt und der Suchinformation für jede Speicherzelle ausgerüstet ist. Folglich sind die Speicher-Zellen für diesen CAM komplizierter, als jene, die in einer konventionellen Speicheranordnungen verwendet werden, auf die auf der Grundlage der Adresse eines Speicherplatzes, welcher die gewünschten Daten speichert, zugegriffen wird. Als Folge davon werden die Kosten pro Bitmenge einige zehn Mal so hoch, wie die der konventionellen Speicher.
Um die Kosten zu reduzieren, wurde ein verbesserter CAM entwickelt, in welchem konventionelle Speicherzellen für die Speicherung der Information verwendet werden, und für jede Worteinheit eine Äquivalenz-Ermittlungs-Schaltung vorgesehen ist. Dieser CAM ist jedoch immer noch unvorteilhaft, weil Such-Operationen so oft durchgeführt werden müssen, wie jedes Wort Bits enthält.
Als ein Beispiel einer weiteren Verbesserung wurde ein anderer CAM vorgeschlagen, der aus zwei konventionellen Speichern besteht:
der erste Speicher speichert Daten unter Verwendung der Suchinformation als Adresseneingangs-Signal, während der zweite Speicher Daten oder Lese-Ausgangs-Signale von dem ersten Speicher als Adressen-Eingangssignal empfängt und Such-Informationen speichert. Dieser CAM ist in der japanischen Patent-Offenlegung 73039/74 veröffentlicht worden. Es ist vorteilhaft, daß der CAM nur mit konventionellen Speicherzellen aufgebaut ist. Der CAM hat jedoch einen solchen Nachteil, daß die Anzahl der benötigten Speicherzellen sehr schnell mit der Erhöhung der Anzahl der Bits der Suchinformation oder der Daten ansteigt, was zu einer extremen Erhöhung der Kosten führt.
Die US-A-3 644 904 veröffentlicht einen Hybrid-Assoziativ- Speicher, der eine ausgewählte Anzahl von Chips enthält, von denen jeder ein Array von nichtassoziativ-adressierbaren binären Speicher-Schaltungen besitzt, welche in einer Zeilen- und Spalten-Matrix angeordnet sind, worin jede Spalte eine Bitposition des im Speicher ausgewählten Wortes darstellt, und die Zeilen eine zusätzliche Wort-Kapazität bereitstellen. Die Speicher enthalten ferner ein Suchregister, das ein Wort speichert, das identisch mit dem in dem Speicher zu suchende ist. Somit kann dieser Speicher nur eine Speicher-Information suchen, die identisch mit der Suchinformation ist, aber keine Speicher-Informationen, die eine Hamming-Distanz besitzt.
Andererseits ist ein CAM mit einer mehrdeutigen Charakteristik für Anwendungen auf Gebieten der Mustererkennung oder der Verarbeitung natürlicher Sprache erwünscht. Mit anderen Worten, es wird ein solcher CAM gewünscht, der Daten innerhalb einer Hamming-Distanz suchen kann. Im Stand der Technik wird eine derartige Suche durch Einführung eines Fehler-Korrektur-Codes durchgeführt. Deshalb wird die Konstruktion des CAMs kompliziert, was zum Ansteigen der Kosten führt.

ZUSAMMENFASSUNG DER ERFINDUNG

Demgemäß ist es eine Aufgabe der vorliegenden Erfindung, einen inhalts-adressierbaren Speicher (CAM) bereitzustellen, der die Probleme im oben erwähnten Stand der Technik löst.
Es ist eine andere Aufgabe der vorliegenden Erfindung einen CAM mit einer großen Speicherkapazität bereitzustellen, welcher mit einer hohen Geschwindigkeit arbeitet und eine Vielzahl von Funktionen besitzt, und welcher preiswert mit konventionellen Speicherzellen, auf die auf der Grundlage von Adressen zugegriffen wird, konstruiert wird.
Es ist noch eine andere Aufgabe der vorliegenden Erfindung einen CAM bereitzustellen, der die Such-Operation ausführen kann, während ein Teil der Such-Information als Maske verwendet wird.
Es ist eine weitere Aufgabe der vorliegenden Erfindung einen CAM bereitzustellen, der zur Ausführung eines mehrfachen Vergleichs-Prozesses in der Lage ist.
Es ist noch eine weitere Aufgabe der vorliegenden Erfindung einen CAM bereitzustellen, der die Speicher-Kapazität einfach erhöhen kann.
Es ist noch eine weitere Aufgabe der vorliegenden Erfindung, einen CAM bereitzustellen, der Speicher-Informationen innerhalb einer gegebenen Hamming-Distanz von der Such-Information suchen kann.
Entsprechend eines ersten Aspektes der vorliegenden Erfindung wird eine inhalts-adressierbare Speicher-Anordnung zum Suchen von Datenworten und ihren zugehörigen Adressen j bereitgestellt, wobei die Speicher-Anordnung N Datenworte speichert, und alle Datenworte aus k oder in Stücken bestehen, wobei jedes Stück aus m Bits besteht, mit k, m = 1, 2, 3 . . ., n, und seine Daten in einem "1 aus M"-Code kodiert wurden; und jedes Datenwort, das seine zugehörige Adresse j besitzt, wobei die inhalts-adressierbare Speicher-Anordnung enthält: eine Speicher-Vorrichtung mit einer Matrix aus konventionellen Speicherzellen mit k·2M Zeilen und m·N Paaren von Spalten, worin jedes Datenwort entsprechend seiner zugehörigen Adresse j in in Spalten-Paaren gespeichert ist, und wobei in jeder ersten Spalte eines Paares das Datenwort selbst gespeichert ist, während in der anderen Spalte ein Datenwort gespeichert ist, welches eine bestimmte funktionale Beziehung zu dem gespeicherten Datenwort besitzt; eine Zeilenwahl-Vorrichtung, die mit der Speicher-Vorrichtung gekoppelt ist, und im Falle einer Such-Operation sequentiell alle k Zeilen der Matrix der Speicherzellen entsprechend dem "1 aus M"-Code auswählen kann; eine Spaltenwahl-Vorrichtung, die mit der Speicher- Vorrichtung gekoppelt ist, und im Falle einer Speicher-Operation alle in Spalten-Paare der Matrix aus Speicherzellen entsprechend der Datenwort-Adresse j sequentiell auswählen kann; einen Kodierer, der im Falle einer Such-Operation Zeile für Zeile alle Daten empfangen kann, die in den Speicherzellen der k ausgewählten Zeilen gespeichert sind, und von den darin aktivierten in Spalten die erforderliche Such-Adresse j kodieren kann.
Diese inhalts-adressierbare Speicher-Anordnung kann ferner enthalten: eine Schalter-Vorrichtung mit einer Vielzahl von Schaltern, die jeder ein Paar von Eingängen besitzen, die mit der ersten Spalte beziehungsweise der zweiten Spalte des gleichen Paares von Spalten in der Matrix der Speicher- Vorrichtung gekoppelt sind, um den Inhalt der Speicherzellen der ersten beziehungsweise der zweiten Spalte jeden Paares zu empfangen, das zu der durch die Zahlenwahl-Vorrichtung ausgewählten Zeile gehört, eine Schalter-Vorrichtung, die als Antwort auf das Referenz-Signal den Inhalt der Speicherzelle mindestens einer der Spalten der ersten oder der zweiten Spalte jeden Paares, das zu der von der Zeilenwahl-Vorrichtung ausgewählten Zeile gehört, ausgibt; und worin der Kodierer das Ausgangs-Signal der Schalter- Vorrichtung empfängt und es in eine Adresse für mindestens einen der Suchdaten und den diesen zugehörigen Daten kodiert.
In diesem Fall kann die Zeilenwahl-Vorrichtung einen Dekoder enthalten, der die Suchdaten empfängt und ein Signal ausgibt, das die Zeile der Matrix der Speicher-Vorrichtung bezeichnet, die dem Inhalt der Such-Daten entspricht. Vorzugsweise enthält die Zeilenwahl-Vorrichtung: einen Dekoder, der die Daten empfängt und die Daten in Signale dekodiert, die der Zeile der Speicherzellen-Matrix entsprechen und die die Zeilenposition der Speicherzellen-Matrix repräsentieren, die dem Inhalt der Daten entsprechen; und eine Anzahl von OR-Gates, von denen jedes zwei Eingänge besitzt, die jeweils eins der kodierten Signale und ein Betriebs-Moden-Signal empfangen, das die Speicher-Operation oder die Such-Operation anzeigt.
In einem speziellen Ausführungsbeispiel ist das dekodierte Signal, das der Zeilenposition der Matrix entspricht, welche mit dem Inhalt der Daten übereinstimmt, "1" , während die anderen dekodierten Signale "0" sind, und das Betriebs- Moden-Signal ist "1", wenn die Speicheroperation angefordert wird, während es "0" ist, wenn die Such-Operation angefordert wird.
Weiterhin kann die inhalts-adressierbare Speicher-Anordnung enthalten:
eine Speicherwahl-Vorrichtung, die als Antwort auf das Speicher-Operations-Signal eine Spaltenpaar der Matrix der Speicher-Vorrichtung entsprechend der Eingangs-Adresse auswählt; und eine Daten-Schreib-Vorrichtung zum Schreiben der Eingangsdaten in die erste Spalte des Spaltenpaares der von der Spaltenwahl-Vorrichtungen ausgewählten Matrix und der zugehörigen Daten in die zweiten Spalte des von der Spaltenwahl-Vorrichtung ausgewählten Spaltenpaares.
Die obige Spalten-Wahl-Vorrichtung kann in der Dekoder-Vorrichtung enthalten sein, die die Eingangs-Adresse empfängt und ein Signal ausgibt, das das Spaltenpaar der Matrix der Speicher-Vorrichtung entsprechend der Eingangsadresse anzeigt. Genauer dekodiert der Dekoder die Eingangs- Adresse, um als Antwort auf ein Spaltenwahl-Signal ein Signal auszugeben, das der ersten und der zweiten Spalte des Spaltenpaares in der Speicherzellen-Matrix entsprechend der Eingangs-Adresse entspricht.
Die inhalts-adressierbare Speicher-Anordnung enthält ferner:
einen Dekodierer, der eine Eingangs-Adresse als Signal höherer Ordnung und das Spaltenwahl-Signal als das Signal mit geringerer Wertigkeit empfängt, und dieselben in Signale dekodiert, die die erste und die zweite Spalte des Spaltenpaares darstellen, die in Übereinstimmung mit der Veränderung des Spaltenwahl-Signals der Eingangs-Adresse entsprechen; und mehrere OR-Gates, von denen jedes den Spalten der Speicherzellen der Speicher-Vorrichtung entspricht und die die entsprechenden dekodierten Signale und ein inventiertes Betriebs-Moden-Signal empfangen.
Vorzugsweise sind die dekodierten Signale, die die Position des Spaltenpaares der Matrix entsprechend der Eingangs- Adresse repräsentieren, "1", während die anderen dekodierten Signale "0" sind, und das Betriebs-Moden-Signal ist "1", wenn die Speicher-Operation angefordert wird, während es "0" ist, wenn die Such-Operation angefordert wird.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 stellt ein Blockschaltbild dar, das ein Ausführungsbeispiel des CAM entsprechend des ersten Aspekts der vorliegenden Erfindung zeigt;
Fig. 2 ist eine Darstellung des Speichermusters in dem Speicher, der in dem in Fig. 1 gezeigten CAM verwendet wird;
Fig. 3 ist eine Tabelle, die die Beziehung zwischen dem Lese-Signal und der Hamming-Distanz zeigt;
Fig. 4 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Zeilen-Wählers;
Fig. 5 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Spalten-Wählers 130;
Fig. 6 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Schreibdaten-Generators 140;
Fig. 7 stellt ein Blockschaltbild dar, das ein Ausführungsbeispiel des CAM entsprechend eines zweiten Aspekts der vorliegenden Erfindung zeigt;
Fig. 8 ist eine Illustration des Speichermusters in dem in Fig. 7 gezeigten Speicher;
Fig. 9 zeigt ein Ausführungsbeispiel der in Fig. 7 gezeigten Such- und Verarbeitungs-Anordnung;
Fig. 10 ist ein Blockschaltbild, das ein Ausführungsbeispiel eines CAM entsprechend eines dritten Aspekts der vorliegenden Erfindung zeigt;
Fig. 11 zeigt ein Ausführungsbeispiel einer in Fig. 10 gezeigten Such- und Verarbeitungs-Anordnung;
Fig. 12 ist ein Blockschaltbild, das ein Ausführungsbeispiel eines CAMs entsprechend eines vierten Aspekts der vorliegenden Erfindung zeigt;
Fig. 13 zeigt ein Ausführungsbeispiel eines in Fig. 12 gezeigten Spalten-Wählers;
Fig. 14 ist ein Blockschaltbild, das ein Ausführungsbeispiel eines CAMs entsprechend eines fünften Aspekts der vorliegenden Erfindung zeigt; und
Fig. 15 zeigt ein Ausführungsbeispiel der in Fig. 14 gezeigten Daten-Ausgabe-Anordnung.

BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSBEISPIELE

Bezieht man sich nun genauer auf die Zeichnungen, so zeigt
Fig. 1 ein Ausführungsbeispiel eines CAMs entsprechend einem Aspekt der vorliegenden Erfindung.
Kurz gesagt enthält der CAM im wesentlichen eine Speicherzellen-Matrix und besitzt zwei Basis-Funktionen: die Datenspeicherung und die Daten-Suche. Als Antwort auf ein Betriebs-Moden-Signal führt der CAM entweder die Speicher Operation oder die Such-Operation aus. Bei der Speicher Operation empfängt der CAM Eingangs-Daten und eine Registrier-Adresse und schreibt das Datenwort in eine Spalte der Speicherzellen-Matrix, die von der Registrier-Adresse bezeichnet wird. Andererseits empfängt der CAM bei der Such-Operation ein Suchdaten-Wort und liest alle Speicherzellen einer Zeile der Speicherzellen-Matrix, die durch das Suchwort spezifiziert werden, um die Speicherzelle herauszufinden, die das vorbestimmte Bit gespeichert hat. Dann wird die Spaltenposition der Speicherzelle, die das vorbestimmte Bit gespeichert hat, in eine Adresse j gewandelt, weiche den Speicherplatz bezeichnet, die dasselbe Datenwort wie das Suchdatenwort speichert.
Zu diesem Zweck enthält der CAM einen Speicher 110, der eine große Anzahl Speicherzellen besitzt, die in Matrixform angeordnet sind und zum Empfang eines Schreib-Zeitgeber-Impulses über eine Schreib-Impuls-Leitung 104 vorgesehen sind. Wort- oder Zeilenleitungen dieses Speichers 110 sind in einem Eins-zu-eins-Verhältnis mit Zeilenwahl-Leitungen 121 des Zeilen-Wählers 120 verbunden, welcher über einen Daten-Bus 101 zum Empfang von Datenworten und über eine Leitung 103 zum Empfang eines Betriebs-Moden-Signals vorgesehen ist. Der Speicher 110 besitzt auch Bit- oder Spaltenleitungen, die mit den Spaltenwahl-Leitungen 131 und 131' des Spalten-Wählers 130 in einer solchen Weise verbunden sind, daß jedes Paar der angrenzenden gerade und ungerade numerierten Spalten des Speichers 110 mit dem entsprechenden Paar der angrenzenden geraden und ungeraden Spaltenleitungen 131 und 131 verbunden ist. Der Spalten-Wähler 130 ist zum Empfang des Modensignals über die Leitung 103, einer Registrier-Adresse über den Adressen-Bus 132 und eines Spalten-Wahl-Signals über eine Spaltenwahl-Leitung eingestellt. Weiter ist dem Speicher 110 ein Schreibdaten- Generator 140 zugeordnet, welcher zum Empfang der Eingangs- Daten am Daten-Eingangs-Bus 101 und des Spalten-Wahlsignals, das über die Leitung 133 eingespeist wird, vorgesehen ist, um eine oder mehrere Schreibdaten-Leitungen 141, die jeweils mit den Zeilen-Leitungen des Speichers 110 verbunden sind, selektiv zu aktivieren. Außerdem sind die Spalten-Leitungen des Speichers 110 durch Lese-Leitungen 151 und 151' mit einem Schalter-Array 150 verbunden. Jedes Paar der angrenzenden geraden oder ungeraden Lese-Leitungen 151 und 151', welche jedem Paar der angrenzenden geraden oder ungeraden Spaltenwahl-Leitungen 131 und 131' entsprechen, sind jeweils mit zwei Eingängen des entsprechenden Schalters 153 in dem Schalter-Array 150 verbunden. Jeder Schalter 153 des Schalter-Arrays 150 wird auf der Grundlage eines Referenz-Signals gesteuert, das über die Leitung 102 zur selektiven Verbindung jeder Leseleitung 151 oder 151' mit einer Such-Ergebnis-Leitung 152 eingespeist wird, welche mit einem Kodierer 160 verbunden ist, der eine Koinzidenz-Signal-Leitung 161 und einen Adressen-Ausgabe- Bus 162 besitzt.
Speziell ist der Speicher 110 mit konventionellen Speicherzellen konstruiert, auf die selbstverständlich in Übereinstimmung mit der Adresse des Datenwortes zugegriffen wird. Um einen CAM zu erhalten, der eine Speicherkapazität von N Worten mit M Bits besitzt, muß der Speicher 110 mit Speicherzellen aufgebaut werden, die in einer Matrixform mit 2M Zeilen und 2N Spalten angeordnet sind. Mit anderen Worten, eine Spalte enthält 2M Speicherzellen entsprechend der Anzahl der möglichen Informationen, welche von M Bits dargestellt werden können. Deshalb kann die erste bis 2M-te Speicherzelle in jeder Spalte betrachtet werden, jeweils den Dezimalzahlen (0) bis (2M-1) zu entsprechen. Andererseits entspricht ein Paar der Spalten einem Wort, wie nachfolgend deutlich wird.
Bei der Speicher-Operation steuert der Zeilen-Wähler 120 parallel alle Zeilenwahl-Leitungen 121 an, während der Spalten-Wähler 130 ein Paar der angrenzenden zwei Spaltenwahl-Leitungen 131 und 131' auswählt, die von der Registrier-Adresse am Bus 132 bezeichnet werden, und steuert eine der ausgewählten gepaarten Spaltenwahl-Leitungen 131 und 131' in Übereinstimmung mit dem Spalten-Wahl-Signal von der Leitung 133 an. Außerdem empfängt der Schreibdaten-Generator 140 das Datenwort, das über den Daten-Bus 101 eingespeist wird, und dekodiert es in eine Speicherzellen-Position oder Positionen in Zeilenrichtung, die von dem Datenwort im Hinblick auf das Spalten-Wahlsignal auf der Leitung 133 spezifiziert wird. Dann speist der Generator 140 ein Schreib-Signal, das der dekodierten Speicherzellen-Position oder Positionen in Zeilenrichtung entspricht, selektiv in die Schreibdaten-Leitung oder Leitungen 141 ein. Bei der Such-Operation steuert andererseits der Zeilen-Wähler 120 selektiv eine der Zeilen-Wahl-Leitungen 121 an, die von dem Datenwort oder der Such-Information 101 bezeichnet wird, während der Spaltenwähler 130 in Übereinstimmung mit dem Moden-Signal 103 parallel alle Spaltenwahl-Leitungen 131 und 131' ansteuert.
Das Referenz-Signal auf der Leitung 102 bestimmt die Suchbedingung: "0" steht für das Suchen der Daten, die identisch mit der Such-Information 101 sind, "1" steht für das Suchen der Daten, deren Hamming-Distanz von der Such-Information 1 beträgt. Gemäß eines derartigen Referenz-Signals 102 arbeiten alle Schalter 153 in dem Schalter-Array 150 in einer selektiven Verbindung entweder der ungeraden Spalten- Leseleitungen 151 oder der geraden Spalten-Leseleitungen 151' des Speichers 110 mit der entsprechenden Such-Ergebnis-Leitungen 152. Der Kodierer 160, welcher mit der Such- Ergebnis-Leitung 152 parallel verbunden ist, arbeitet zur Kodierung der Position der Such-Ergebnis-Leitung oder -Leitungen 152, die durch den Speicher 110 aktiviert sind, zur Such-Adresse, die den Platz der gewünschten Daten repräsentiert, welche dann über den Bus 162 ausgegeben wird. Zusätzlich wird, wenn mindestens eine der Leitungen 152 mit dem Kodierer 160, der von dem Speicher 110 aktiviert ist, verbunden ist, ein Koinzidenz-Signal von der Leitung 161 des Kodierers 160 ausgegeben.
Wie für das Betriebs-Moden-Signal auf der Leitung 103, steht "1" für die Speicher-Operation und "0" für die Such- Operation. Speicher-Operation und Such-Operation sollen unten im Detail beschrieben werden.
Wenn "1" über die Leitung 103 als Betriebs-Moden-Signal an den Zeilen-Wähler 120 und den Spalter-Wähler 130 angelegt wird, beginnt die Speicher-Operation. Die zu speichernde Information ist durch das Datenwort gegeben, das über den Datenbus 101 eingespeist wird, und die Adresse, bei welcher die Information zu speichern ist, wird durch die Registrier-Adresse bezeichnet, die über den Adressen-Bus 132 eingespeist wird. Das Spaltenwahl-Signal 133 wird in der Reihenfolge "0" und dann "1" geliefert. Da "1" als Betriebs-Signal gegeben ist, steuert der Zeilen-Wähler 120 parallel alle Zeilenwahl-Leitungen 121 des Speichers 110 an. Der Spalten-Wähler 130 bezeichnet auf der Basis der Registrier-Adresse, die über den Adressen-Bus 132 angelegt wird, ein Paar der angrenzenden Spaltenwahl-Leitungen 131 und 131' und steuert ferner in Übereinstimmung mit dem logischen Wert "0" oder "1" des Spaltenwahl-Signals 133 selektiv eine Spaltenwahl-Leitung des bezeichneten Spaltenwahl-Leitungs-Paares an: "0" wählt die gerade Nummer der Spaltenwahl-Leitung 131, links in dem bezeichneten Spaltenwahl-Leitungs-Paar; "1" wählt die ungerade Nummer der Spaltenwahl-Leitung 131', rechts in dem bezeichneten Spaltenwahl-Leitungs-Paar. Da das Spaltenwahl-Signal 133 in der Reihenfolge "0" und dann "1" geliefert wird, wie oben erwähnt wird, steuert der Spalten-Wähler 130 zuerst die gerade Spaltenwahl-Leitung 131 und dann die ungerade Spalte der Wahl-Leitung 131' des Spalten-Paares des Speichers 110 an, die durch die Registrier-Adresse 132 bestimmt wird.
Fig. 2 veranschaulicht den Inhalt des Speichers 110. Sie erklärt auch die Schreibdaten, die von dem Schreibdaten- Generator 140 generiert werden. Von dem Paar der angrenzenden Spalten in der Zeichnung ist die rechte eine ungerade Nummern-Spalte und die linke eine gerade Nummern-Spalte. Die Zahlen 0 bis 7, die die linke Seite beschriften, stellen Wort-Nummern oder Zeilen-Nummern dar.
Es soll die Funktion des Schreib-Daten-Generators 140 mit Bezug auf Fig. 2 erläutert werden. Der Schreib-Daten-Generator 140 empfängt das Datenwort 101 als die zu speichernde Information und wandelt sie in Übereinstimmung mit dem Betriebs-Mode, der von dem Spaltenwahl-Signal 133 bestimmt wird, in Schreibdaten und führt dann das Datenwort über die Leitungen 141 dem Speicher 110 zu. Wenn zum Beispiel der Dezimalwert "3" als die zu speichernde Information gegeben ist und das Spaltenwahl-Signal 133 "0" ist, erzeugt der Schreibdaten-Generator 140 Schreibdaten, die der geraden Spalte links in der Fig. 2 entsprechen, das heißt, er schreibt "1" nur in die dritte Zeile.
Als nächstes schreibt der Schreibdaten-Generator 140, wenn das Spaltenwahl-Signal auf "1" geändert wird, "1" in die Zeilen, die von allen Datenworten spezifiziert werden, die die Hamming-Distanz 1 von der über den Datenbus 101 eingespeisten Information besitzen. In dem Beispiel der Fig. 2 wird, da der Speicher 110 8 Zeilen besitzt und das Datenwort 101 aus 3 Bits besteht, der Dezimalwert "3" durch "011" in binärer Notation dargestellt. In diesem Fall können die Datenworte, die die Hamming-Distanz "1" von der zu speichernden Information besitzen, durch Invertierung nur eines Bits von "011" erhalten werden. Deshalb werden dort erhalten "010", "001" und "111", welche den Dezimalzahlen "2", "1" und "7" entsprechen. Schließlich führt der Schreibdaten-Generator 140 die Schreibdaten den Schreibdaten-Leitungen 141 entsprechend der rechten Seite zu, den ungeraden Spaltennummern der Fig. 2, um "1" in die zweite, erste und siebte Zeile zu schreiben. Somit werden die oben erwähnten Schreibdaten nacheinander in ein Paar angrenzenden Spalten des Speichers 110, das durch die Registrier- Adresse 132 bezeichnet wird, gespeichert, wie in Fig. 2 gezeigt wird. Die Speicher-Operation ist dann beendet. Wie aus dem Obigen zu ersehen ist, entspricht ein Paar der angrenzenden Spalten 131 und 131' einem Wort.
Bei der Such-Operation, bei der "0" als Betriebs-Moden- Signal angelegt wird, ist die Such-Information als das Datenwort 101 gegeben. Ferner wird das Referenz-Signal 102 an das Schalter-Array 150 angelegt. Durch das Betriebs-Moden- Signal 103 auf "0" getriggert, steuert der Zeilen-Wähler 120 selektiv die durch die Such-Information spezifizierte Zeile des Speichers 110 an, während der Spalten-Wähler 130 alle Spalten des Speichers 110 parallel ansteuert. Folglich wird das in der ausgewählten Zeile des Speichers 110 gespeicherte Datenwort, das durch die Such-Information bestimmt wird, über die geraden und ungeraden Lese-Leitungen 151 und 151' ausgegeben. Wie aus Fig. 2 gesehen werden kann, werden, wenn die gespeicherte Information gleich der Such-Information ist, die Lese-Signale von einem Paar der angrenzenden geraden Spalte 151 und ungeraden Spalte 151' des Speichers 110 (1,0). Wenn die gespeicherte Information sich nur durch 1 Bit von der Such-Information unterscheidet, werden die Lese-Signale von einem Paar der angrenzenden Spalten 151 und 151' (0,1); wenn die Differenz 2 Bits oder mehr beträgt, werden die Lese-Signale (0,0).
Fig. 3 zeigt die Beziehung zwischen den Lese-Signalen von der geraden Spalte 151 sowie der ungeraden Spalte 151' und der Hamming-Distanz H. Wenn die in dem Speicher 110 gespeicherte Information identisch mit der Such-Information ist, ist die Hamming-Distanz null. Wenn die Differenz zwischen der gespeicherten Information und der Such-Information 1 Bit beträgt, ist die Hamming-Distanz gleich 1; wenn die Differenz 2 Bit oder mehr beträgt, ist H nicht kleiner als 2. Deshalb zeigt in jedem Paar der geraden und ungeraden Spalten das Lese-Signal 151 von einer geraden Spalte an, ob die in der geraden Spalte gespeicherte Information identisch mit der Such-Inforination ist oder nicht. Andererseits zeigt das Lese-Signal 151 der ungeraden Spalte an, ob die in der angrenzenden geraden Spalte gespeicherte Information sich von der Such-Information durch 1 Bit unterscheidet oder nicht, da die ungerade Spalte das Datenwort mit der Hamming-Distanz 1 von der in der angrenzenden linksseitigen geraden Spalte gespeicherten Information speichert, wie oben erwähnt wird.
Die Lese-Signale 151 und 151' von jedem Paar der angrenzenden Spalten des Speichers 110 werden den entsprechenden Schaltern 153 des Schalter-Arrays 150 zugeführt. Gemäß des Referenz-Signals 102 wird jedem Schalter 153 selektiv entweder das Lese-Signal 151 von der geraden Spalte oder das Lese-Signal 151' von der ungeraden Spalte als Such-Signal 152 zugeführt, welches in den Kodierer 160 eingespeist wird: wenn "0" als Referenz-Signal 102 geliefert wird, wird das Lese-Signal 151 von der geraden Spalte als Such-Ergebnis-Signal 152 ausgegeben; wenn "1" als Referenz-Signal geliefert wird, wird das Lese-Signal 151' der ungeraden Spalte als Such-Ergebnis-Signal ausgegeben. Wenn die Such- Information identisch mit der gespeicherten Information ist, wird "1" als Such-Ergebnis-Signal 152 ausgegeben.
Wenn die Such-Ergebnis-Signale 152, die parallel in den Kodierer 160 eingegeben werden, "1" enthalten, gibt der Kodierer 160 ein Koinzidenz-Signal 161 an externe Geräte aus und wandelt die Position der Spalte, in die das Such-Ergebnis-Signal "1" eingespeist wird, in eine Adresse mit Binärcode. Das Koinzidenz-Signal 161 zeigt an, ob die Information identisch mit der im Speicher 110 gespeicherten Such- Information ist oder nicht, und die Such-Adresse j 162 zeigt die Position der Spalte an, wo das Such-Ergebnis- Signal 152, das "1" besitzt, enthalten ist, das heißt, die Adresse j des Platzes, in der die mit der Such-Information identische Information gespeichert ist.
Im Falle einer mehrfachen Koinzidenz, bei welcher mehrere im Speicher 110 gespeicherte Informationen unter der vom Referenz-Signal bestimmten Voraussicht gleich der Such-Information sind, wird ein Such-Signal 152 mit "1" von mehreren Schaltern 153 erzeugt. Gemäß dieser Situation ist ein Register für die zeitweilige Speicherung des Such-Ergebnis- Signals 152 zwischen jedem Schalter 153 und dem Kodierer 160 vorgesehen und es ist ein Dekodierer vorhanden, der auf die Such-Adresse j 162 zur Rücksetzung des Registers auf die Bit-Position, die durch die eingegebene Such-Adresse j 162 bestimmt wird, reagiert. In diesem Fall wandelt deshalb der Kodierer 160 selektiv die Position jedes Such-Ergebnis- Signals, das "1" besitzt, in die Such-Adresse j 162, so daß eine Vielzahl von Such-Adressen j 162 der gespeicherten Information, die gleich der Such-Information sind, erhalten werden kann.
Wie oben erläutert wird, kann ein CAM, der eine Kapazität von N Worten mit M Bits besitzt, unter Verwendung des Speichers 110, der Chips konventioneller Speicherzellen enthält, die in einer Matrix von 2M Zeilen und 2N Spalten angeordnet sind, konstruiert werden und deshalb ist dieser CAM sehr preiswert. Weiterhin können die Such-Operation und die Speicher-Operation jeweils nur mit einem Zugriffs- Schritt ausgeführt werden, so daß eine hohe Arbeits-Geschwindigkeit realisiert werden kann. Außerdem kann der CAM nicht nur die Speicher-Informationen suchen, die identisch mit der Such-Information sind, sondern auch die Speicher- Informationen, die eine Hamming-Distanz von "1" von der Such-Information besitzen. Mit anderen Worten, es kann ein mehrfunktionaler CAM erhalten werden.
Fig. 4 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Zeilen-Wählers 120. Der gezeigte Zeilen-Wähler 120 enthält einen Dekoder 410, der über den Datenbus 101 das Datenwort empfängt, welches in Abhängigkeit vom Betriebsmode als Speicher-Information oder als Such-Information verwendet wird. Dieser Dekoder arbeitet zur selektiven Ausgabe eines binären Signals von "1" an eine der 2M parallelen Ausgangs-Leitungen, die von dem Datenwort 101 angezeigt wird. Diese parallelen Ausgangs-Leitungen des Dekoders 410 sind jeweils mit einem Eingang der 2M OR-Gates 420 verbunden, welche parallel angeordnet sind, um ein Gate-Array 430 zu bilden. Die anderen Eingänge aller OR-Gates 420 sind zum Empfang des Moden-Signals mit der Leitung 103 verbunden und die Ausgänge der entsprechenden OR-Gates 420 sind jeweils mit den Zeilenwahl-Leitungen 121, die den entsprechenden Speichern zugeordnet sind, verbunden.
Bei der Speicher-Operation wird das Betriebs-Moden-Signal 103 von "1" an alle OR-Gates 420 angelegt und alle Ausgangs-Signale der OR-Gates 420 werden "1", so daß alle Zeilen-Wahl-Leitungen 121 parallel angesteuert werden. Bei der Such-Operation wird, da "0" als Betriebs-Moden-Signal 103 an die OR-Gates 420 angelegt wird, nur eine Wahl-Leitung 121, die von den Eingangs-Daten 101 bestimmt wird, selektiv angesteuert.
Fig. 5 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Spalten-Wählers 130. Der gezeigte Spalten-Wähler 130 enthält einen Dekoder 510, welcher das Spalten-Wahl-Signal 133 als das geringwertige Bit empfängt und die Registrier- Adresse 132 als die höherwertigen Bits. Dieser Dekoder dekodiert die Eingangs-Signale, um ein binäres Signal von "1" an zwei der 2N parallelen Ausgangs-Leitungen, welche jeweils mit einem Eingang der 2N parallelen OR-Gates 520 in dem Gate-Array 530 verbunden sind, selektiv auszugeben. Der Spalten-Wähler 130 enthält auch einen Inverter 540, dessen einer Eingang mit der Leitung 103 zum Empfang des Moden- Signals und dessen Ausgang mit den anderen Eingängen aller OR-Gates 520 verbunden ist, um die inventierten Modensignale in diese OR-Gates 520 einzuspeisen. Die Ausgänge der entsprechenden OR-Gates 520 sind jeweils mit den Spalten-Wahl-Leitungen 131 und 131' verbunden.
Bei der Speicher-Operation wird das Betriebs-Moden-Signal 103 von "1" an den Inverter 540 angelegt und damit wird das binäre Signal von "0" in die anderen Eingänge aller OR-Gates 520 eingespeist. Deshalb kann der Dekoder 510 selektiv eine der Spalten-Wahl-Leitungen 131 und 131' ansteuern, die von beiden, der Registrier-Adresse 132 und dem Spalten- Wahl-Signal 133 spezifiziert werden. Da das Spalten-Wahl- Signal 133 als das geringwertige Bit an den Dekoder 510 angelegt wird, bestimmt das Spalten-Wahl-Signal die Wahl entweder der geraden Spalte oder der ungeraden Spalte von jedem Paar der angrenzenden Spalten des Speichers 110. Wie vorhergehend erwähnt wird, ist die Information in die gerade Spalte und dann in die ungerade Spalte des einen Paares der angrenzenden Spalten des Speichers 110 eingeschrieben, die von der Registrier-Adresse 132 bestimmt wird, da das Spalten-Wahl-Signal 133 bei der Speicher-Operation in der Reihenfolge "0" und dann "1" angesteuert wird. Bei der Such-Operation gibt der Inverter 540, da "0" als Betriebs-Moden-Signal 103 an den Inverter 540 anliegt, das binäre Signal von "1" an alle OR-Gates 520 aus, um alle Spalten-Wahl-Leitungen 131 und 131' parallel anzusteuern, ohne von den Ausgangs-Signalen vom Dekoder 510 beeinflußt zu werden. Deshalb können alle Daten der Spalten des Speichers 110 parallel gelesen werden.
Fig. 6 zeigt ein Ausführungsbeispiel des in Fig. 1 gezeigten Schreibdaten-Generators 140 im Fall eines Drei-Bit Daten-Busses 101. Der Schreibdaten-Generator enthält einen Dekoder 610, dessen Ausgang mit dem Daten-Bus 101 zum Empfang des Datenwortes als Speicher-Information verbunden ist. Dieser Dekoder 610 besitzt acht Ausgangs-Leitungen und wird zur selektiven Ausgabe eines binären Signals von "1" an eine der acht Ausgangs-Leitungen verwendet, die von den Eingangs-Daten 101 angezeigt wird. Die acht Ausgangs-Leitungen des Dekoders 610 sind direkt mit einem der Eingänge der entsprechenden acht Schalter 620 verbunden, die parallel zueinander angeordnet sind, um ein Schalter-Array 630 zu bilden. Ferner sind die Ausgangs-Leitungen des Dekoders 610 über OR-Gates 640 des Gate-Arrays 650 mit den anderen Eingängen der Schalter 620 verbunden, wie in Fig. 6 gezeigt wird. Diese Schalter 620 werden von dem Spalten-Wahl-Signal gesteuert, das über die Leitung 133 zugeführt wird, um entweder ihren einen Eingang oder ihre anderen Eingänge mit ihren Ausgängen zu verbinden, welche mit den Schreibdaten- Leitungen 141 des Speicher 110 verbunden sind.
Wenn "0" als Spalten-Wahl-Signal 133 an die Schalter 620 angelegt ist, gibt jeder Schalter direkt jedes Ausgang- Signal des Dekoders 610 als Schreibdaten an die Schreib-Daten-Leitung 141 aus. In diesem Fall besitzen die Schreibdaten "1" nur einer Schreib-Daten-Leitung 141, die von der Speicher-Information spezifiziert wird.
Wenn "1" als Spalten-Wahl-Signal 133 an die Schalter 620 angelegt wird, verbinden die Schalter die Ausgänge der OR- Gates 640 mit den Schreib-Daten-Leitungen 141. Wie aus der Fig. 6 ersichtlich ist, sind die OR-Gates 640 mit den parallelen Ausgängen des Dekoders 610 verbunden, um die Schreib-Daten zu erzeugen, die "1"-en in die Zeilen geben, die von allen möglichen Datenworten, die die Hamming-Distanz "1" von dem Datenwort 101 oder der Speicher-Information besitzen, angezeigt werden. Wenn die OR-Gates 640 und die Ausgänge des Dekoders 610 von "null" an der höchsten Position in Fig. 6 in Richtung auf die unterste Position der Reihe nach ansteigend numeriert werden, dann ist der dritte Ausgang "3" des Dekoders 610 mit dem ersten, zweiten und siebten OR-Gate 620 gekoppelt. Deshalb werden, wenn "011" (die Dezimalzahl 3) als Datenwort 101 angelegt wird, die Schreibdaten, die "1" in der ersten, zweiten und siebten Zeile besitzen, von dem OR-Gate-Array 650 ausgegeben. Das bedeutet, daß die Schreibdaten "1"-en in den Zeilen besitzen, die von den Daten angezeigt werden, die sich von den Eingangs-Daten 101 nur durch 1 Bit unterscheiden, das heißt, von den Daten "011", "010" und "111", welche jeweils die Hamming-Distanz "1" von dem Datenwort "011" besitzen.
Fig. 7 ist ein Blockschaltbild, das ein Ausführungsbeispiel eines CAMs entsprechend eines anderen Aspektes der vorliegenden Erfindung zeigt. Dieser CAM kann Speicher-Informationen mit einer Bitanzahl größer als die in Fig. 1 gezeigte suchen. Der CAM ist auch zur Durchführung der Suche in der Lage, die einen Teil der Such-Information maskiert. Zu diesem Zweck wird zusätzlich zur Ausstattung des in Fig. 1 gezeigten CAMs eine Such- und Verarbeitungs-Einrichtung 710 und ein Zähler 720 für die Eingangs-Daten 101 eingeordnet.
Wenn dieser CAM eine Speicherkapazität von N Worten mit M · K Bits besitzt, wird der Speicher 110 mit Speicherzellen, die in Matrixform mit 2M·K Zeilen mit 2·N Spalten angeordnet sind, konstruiert. Das heißt, der Speicher 110 besitzt eine Speicher-Kapazität von 2M·K Worten von 2·N Bits, und die Bitanzahl des Zählers 720 ist log&sub2;K Bits. Deshalb ist der Speicher 110 in Fig. 7 aus K Blöcken zusammengesetzt, die den Speicher 110 mit 2M Zeilen von 2·N Spalten in Fig. 1 als einen Block enthält: die K Blöcke werden von dem Zähler 720 getrennt angezeigt. Die Such- Information und die Speicher-Information von M·K Bits werden in K Stücke von M Bitdaten geteilt, welche dann nacheinander in den Zeilen-Wähler 120 und in den Schreib- Daten-Generator 140 in der Reihenfolge von dem Daten-Stück mit dem höchstwertigen Bit (MSB) bis zu dem Daten-Stück mit dem niedrigstwertigen Bit (LSB) in K Teilen eingegeben werden, so daß die K Stücke des Datenwortes 101 getrennt in den entsprechenden Blöcken des Speichers 110 gespeichert sind, ein Daten-Stück in einem Speicherblock. Zum Beispiel ist die Speicher-Information A aus 4 Daten A&sub0;, A&sub1;, A&sub2; und A&sub3; zusammengesetzt, jedes besitzt die Länge von M Bits, die separat in 4 Blöcken des Speichers 110 gespeichert sind: die Daten A&sub0; im 0-ten Block, A&sub1; im ersten Block, A&sub2; im zweiten Block und A&sub3; im dritten Block, wie in Fig. 2 gezeigt wird.
Zur Sicherstellung der oben erwähnten Speicherweise, empfängt der Zeilen-Wähler 120 das Ausgangs-Signal des Zählers 720 als MSB-Daten-Teil und die Daten des Busses 101 als LSB Daten-Teil. Bei der Speicher-Operation steuert der Zeilen- Wähler 120 alle Zeilen in einem Block des Speichers 110 an, die von dem Zählwert des Zählers 720 spezifiziert werden. Bei der Such-Operation steuert der Zeilen-Wähler 120 selektiv eine Zeile in einem Block des Speichers an, die von dem Datenwort des Busses 101 spezifiziert wird, der den von dem Zählwert des Zählers 720 bestimmten Speicher anzeigt. Mit anderen Worten, der Zeilen-Wähler 120 wird in der Lage versetzt, selektiv nur eine Zeile des aus K Blöcken bestehenden Speichers 110 anzusteuern. Andererseits wird jede Schreib-Daten-Leitung 141 des Schreib-Daten-Generators 140 mit der gleichangeordneten und entsprechenden einen Zeile jeden Blockes verbunden. Der Schreib-Daten-Generator speist nämlich die Schreibdaten parallel in alle Blöcke des Speichers 110 ein.
Die Speicher- und die Such-Operation sollen im Detail erklärt werden. Zuerst soll die Erklärung der Speicher-Operation für das Speichern der Information A, die aus vier M Bitdaten A&sub0;, A&sub1;, A&sub2; und A&sub3; besteht, zur Adresse J erfolgen: A&sub0; ist das MSB-Daten-Stück und A&sub3; ist das LSB-Daten-Stück der Information A. Zuerst werden die MSB-Daten A&sub0; angelegt und dann werden die niedriger wertigen Daten A&sub1;, A&sub2; und A&sub3; nacheinander zugeführt. Nachdem die Erläuterung der Speicher-Operation abgeschlossen ist, soll die Such-Operation für den Fall der Suche der gleichen Information, wie die gespeicherte Information A, erläutert werden. Für beide Operationen wird zu Beginn der entsprechenden Operation über die Leitung 711 ein Initialisierungs-Signal an die Such- und Verarbeitungs-Einrichtung 710 und den Zähler 720 zur Initialisierung dieser Schaltungen angelegt.
Bei der Speicher-Operation wird das Betriebs-Moden-Signal 103 mit "1" geliefert, wenn das Initialisierungs-Signal 711 gegeben ist. Zur selben Zeit wird die Registrier-Adresse J über den Adressen-Bus geliefert. Von dem Initialisierungs- Signal wird der Zähler 720 gelöscht und gibt ein Signal an den Zeilen-Wähler 120 aus, so daß der Zeilen-Wähler 120 den 0-ten Block des Speichers 110 anzeigt. Als nächstes dekodiert der Schreibdaten-Generator 140, wenn die MSB-Datum A&sub0; der Speicher-Information A über den Datenbus 101 angelegt sind, die Eingangs-Daten A&sub0;. Zu dieser Zeit werden, wenn das Spalten-Wahl-Signal 133 auf "0" ist und der Schreib- Zeitgeber-Impuls 104 angelegt ist, die Schreibdaten von den Daten A&sub0; dekodiert, die in den 0-ten Blockteil der 2J-ten Spalte des Speichers 110 gespeichert sind. Danach wird, wenn das Spalten-Wahl-Signal 133 auf "1" geändert ist und zur selben Zeit weiterhin der Schreib-Zeitgeber-Impuls 104 angelegt wird, der 0-te Block der (2J+1)-ten Spalte des Speichers 110 mit den Schreibdaten versorgt, welche es möglich machen, "1" in die Zeilen-Positionen zu schreiben, die von allen den Datenworten bestimmt werden, die die Hamming- Distanz "1" von den Daten A&sub0; besitzen. Ferner wird, wenn das Spalten-Wahl-Signal auf "1" geändert wird, wird ein Takt-Signal 712 in den Zähler 720 eingespeist, das in den negativen Zustand gebracht und nach dem Schreib-Takt-Impuls 104 in den positiven Zustand zurückkehrt, so daß der Zähler 720 stufenweise beim Anstieg des Takt-Signal 104 ansteigt. Deshalb ist am Ende des Schreibens der Daten in den 0-ten Block des Speichers 110 der Inhalt des Zählers auf "1" angewachsen und der Zähler bestimmt den ersten Block des Speichers 110 für die Speicherung des Datenwort-Stückes A&sub1;.
Bei der Durchführung der obigen Operationen werden die partiellen Daten A&sub0; der Speicher-Informationen A in den Speicher 110 geschrieben. Die obige Schreib-Operation der partiellen Daten wird in zwei Schritte eingeteilt: der erste Schritt wird ausgeführt, wenn die Eingangsdaten 101, der Schreib-Zeitgeber-Impuls 104 und das Spalten-Wahl-Signal 133 mit "0" angelegt werden; und der zweite Schritt wird bei der Bedingung ausgeführt, bei welcher das gleiche Datenwort 101 erhalten wird, wenn der Schreib-Zeitgeber-Impuls 104, das Spalten-Wahl-Signal 133 mit "1" und das negative Takt-Signal 712 angelegt werden. Für eine perfekte Speicherung der Information A wird die oben erwähnte Schreib-Operation für die Datenwort-Stücke A0, A1, A2 und A3 viermal wiederholt.
Fig. 8 erläutert ein Beispiel eines in einem Paar angrenzender Spalten im Speicher 110 gespeicherten Datenwortes, der für den CAM in Fig. 7 verwendet wird. Die Darstellung zeigt die Bedingung, bei welcher die oben erwähnte Speicher-Information A, die aus vier partiellen Datenworten A&sub0;, A&sub1;, A&sub2; und A&sub3; besteht, unter der Registrier-Adresse J gespeichert wird. In diesem Beispiel besitzt jeder Block 8 Speicherzellen in jeder Spalte, um die Dezimalzahlen von "0" bis "7" zu speichern, welche durch 3 Bits ausgedrückt werden können. Deshalb stellen die gezeigten partiellen Datenworte A&sub0;, A&sub1;, A&sub2; und A&sub3; jeweils die Dezimalzahlen "3", "5", "1" und "0" dar. Wenn diese Speicher-Information gespeichert ist, sind die Daten so wie in der Zeichnung gezeigt, in der 2J-ten und (2J+1)-ten Zeile des Speichers 110 gespeichert: in der 2J-ten Spalte (gerade Spaltennummer) ist "1" in der dritten Zeile des 0-ten Blockes, in der fünften Zeile des ersten Blockes, in der ersten Zeile des zweiten Blockes und in der 0-ten Zeile des dritten Blockes gespeichert; in der (2J+1)-ten Spalte (ungerade Spaltennummer) ist "1" in allen Zeilen, die jeweils der Hamming-Distanz 1 von allen partiellen Daten 3, 5, 1 und 0 entsprechen, ähnlich des in Fig. 2 gezeigten Verfahrens, gespeichert.
Auf diese Weise kann die Schreib-Operation aller partiellen Daten genau so wie in dem in der Fig. 1 gezeigten CAM durchgeführt werden.
Als nächstes soll die Erläuterung eines Vorgangs zur Suche einer Information A erfolgen, wenn die gleiche Information A in der Adresse J gespeichert ist.
Bei dieser Such-Operation wird "0" als Betriebs-Moden- Signal 103 angelegt. Zur gleichen Zeit werden die Zähler 720 und die Such- und Verarbeitungs-Einrichtung 710 durch ein Initialisierungs-Signal 711 initialisiert. Dann werden die partiellen Datenworte A&sub0;, A&sub1;, A&sub2; und A&sub3; der Such-Information A nacheinander über den Datenbus 101 in den Zeilen- Wähler 120 eingegeben und die Takt-Signale werden ebenfalls nacheinander in Synchronisation mit der Eingabe der partiellen Datenworte A&sub0;-A&sub3; über die Takt-Signal-Leitung 712 in den Zähler 720 eingespeist, so daß der Zählwert des Zählers 720 schrittweise bei jedem eingegebenen Takt-Signal 712 anwächst. Somit steuert der Zeilen-Wähler 120 der Reihe nach die dritte Zeile des 0-ten Blockes, die von dem Datenwort A&sub0; bestimmt wird, die fünfte Zeile des ersten Blockes, die von dem Datenwort A&sub1; angezeigt wird, die zweite Zeile des zweiten Blockes, die von dem Datenwort A&sub2; spezifiziert wird und dann die erste Zeile des dritten Blockes, die von dem Datenwort A&sub3; angezeigt wird. Die Daten-Signale, die in der Zeile des mit jeder Zeilen-Wahl-Leitung 121 verbundenen Speichers gespeichert sind, werden so angesteuert und in Synchronisation mit dem Takt-Signal 712 für jeden Block über die Lese-Leitungen 151 und 151' ausgelesen. Die Lese- Signale 151 und 151' werden dann an die Such- und Verarbeitungs-Einrichtung 710 angelegt. Wie oben erwähnt wird, soll, da die Datenworte in dem Speicher 110 so wie in Fig. 8 gezeigt gespeichert sind, ein Paar der Lese-Signale 151 und 151' von der 2J-ten Spalte und der (2J+1)-ten Spalte (1,0) für alle Suchdatenworte A&sub0;, A&sub1;, A&sub2; und A&sub3; sein.
Als nächstes wird das oben erwähnte Beispiel verallgemeinert. Angenommen, daß als Datenwort 101 die Such-Information A angelegt wird, welche K Stücke mit M Bit partiellen Datenworten A&sub0;, A&sub1;, . . .., Ai, . . ., Ak-1 enthält, wobei A&sub0; die MSB-Daten sind. Jedes Paar der Lese-Signale 151 und 151' von dem Speicher 110 für jedes partielle Datenwort Ai zeigt das Ergebnis des Vergleichs zwischen dem partiellen Datenwort A&sub1; jeder Such-Information A und den partiellen von dem Schreib-Daten-Generator 140 kodierten und in jedem Paar der angrenzenden Spalten des Speichers 110 gespeicherten Daten. Jedes Lese-Signal 151 von einer geraden Spalte zeigt an, ob die Speicher-Information und die Such-Information identisch sind oder nicht, während jedes Lese-Signal 151' von einer ungeraden Spalte zeigt, ob die in der angrenzenden geraden Spalte gespeicherte Speicher-Information die Hamming-Distanz 1 von den partiellen Daten der Such- Information besitzt. Angenommen, daß die Lese-Signale 151 von der geraden Spalte und 151' von der ungeraden Spalte EVi beziehungsweise OVi (i=0 bis k=1) sind, dann wird das Koinzidenz-Prüfungs-Ergebnis E, das anzeigt, ob die Such- Information A und die in der geraden Spalte jeder angrenzenden zwei Spalten im Speichers 110 gespeicherte Speicher- Information identisch sind oder nicht, und das Hamming-Distanz-Prüfungs-Ergebnis H, das zeigt, ob sich die Such- Information A und die Speicher-Information nur um 1 Bit unterscheiden oder nicht, jeweils durch Eingabe E = Ek-1 und H = Hk-1 mit folgender Formel dargestellt:
Ei = Ei-1·EVi (1)
Hi = Hi-1·ODi + Hi-1·EVi (2)
wobei i die Anzahl der partiellen Daten Ai, i = 0 bis k-1, E&submin;&sub1; = 1 und H&submin;&sub1; = 0 sind.
Durch das Initialisierungs-Signal 711 wird der Anfangszustand auf i = 0, E&submin;&sub1; = 1 und H&submin;&sub1; = 0 eingestellt. Das Koinzidenz-Ergebnis E kann durch Prüfung der Koinzidenz zwischen der Speicher-Information und der Such-Information für alle partiellen Daten in Übereinstimmung mit der Formel (1) erhalten werden. Durch den ersten Term der Formel (2) wird die Prüfung gemacht, ob die im Speicher 110 gespeicherte Speicher-Information gleich den partiellen Daten A&sub0; bis Ai-1 der Such-Information ist oder nicht, und zur gleichen Zeit unterscheidet sich die Speicher-Information von dem partiellen Datenwort Ai um ein Bit. Durch den zweiten Term der Formel (2) wird ein Bit Differenz der Speicher-Information von dem partiellen Datenwort von A&sub0; bis Ai-1 der Such-Information und Koinzidenz der Speicher-Information mit dem partiellen Datenwort Ai der Such-Information geprüft. Das Hamming-Ergebnis H kann durch die obigen zwei Prüfungs-Schritte erhalten werden.
Die Such- und Verarbeitungs-Einrichtung 710 empfängt in Synchronisation mit dem Takt-Signal 712 die Lese-Signale 151 und 151' und führt nacheinander die logische Operation entsprechend den Formeln (1) und (2) durch. Dann gibt die Such- und Verarbeitungs-Einrichtung 710 selektiv entweder das Koinzidenz-Ergebnis E oder das Hamming-Ergebnis H als Such-Ergebnis-Signal 152 in Abhängigkeit von dem Referenz- Signal 102 aus.
Der Kodierer 160, der das Such-Ergebnis-Signal empfängt, arbeitet ähnlich wie der CAM in Fig. 1. Er erzeugt das Koinzidenz-Signal 161, das anzeigt, ob irgendeine Information identisch zur Such-Information im Speicher 110 gespeichert ist oder nicht, zusammen mit der Such-Adresse 162, die den Speicherplatz der Information anzeigt, die identisch mit der Such-Information ist.
Fig. 9 ist ein logisches Schaltbild, das eine Grund-Einheit der Such- und Verarbeitungs-Einrichtung 710 zur Erzeugung des Such-Ergebnis-Signals 152 zeigt. Diese Such- und Verarbeitungs-Einheit enthält erste und zweite einstufige Register 910 und 920, fünf AND-Gates 930, 931, 932, 933 und 934, zwei OR-Gates 940 und 941 und einen Inverter 950, welcher wie in Fig. 9 gezeigt wird angeschlossen ist, um zu sichern, daß das Koinzidenz-Ergebnis E und das Hamming-Ergebnis H auf der Grundlage der Formeln (1) und (2) berechnet wird, und dann jedes dieser Ergebnisse E und H selektiv in Übereinstimmung mit dem Referenz-Signal 102 ausgegeben wird.
Das Register 910 wird von dem Initialisierungs-Signal 711 so eingestellt, daß das Ausgangs-Signal des logischen Wertes "1", das heißt E&submin;&sub1; = 1, eingespeist wird und das Register 920 wird von demselben Initialisierungs-Signal 711 zurückgesetzt und ein Ausgangs-Signals des logischen Wertes "0", das heißt H&submin;&sub1; = 0, eingespeist. Diese Register 910 und 920 werden mit dem Takt-Signal 712 getaktet. Deshalb führen das AND-Gate 930, welches das Lese-Signal 151 der geraden Spalte empfängt, und das Ausgangs-Signal des Registers 910 die logische Operation der Formel (1) aus, und das erste Register 910 aktualisiert und hält das Ergebnis Ei der logischen Operation bei jedem Takt-Signal 712. Andererseits wirken die zwei AND-Gates 931 und 932 und das OR-Gate 940 zur Durchführung der logischen Operation der Formel (2) zusammen, und das zweite Register 920 aktualisiert und hält in Synchronisation mit dem Takt-Signal 712 das Ergebnis Hi der logischen Operation. Wenn die Lese-Signale 151 und 151' für alle partiellen Daten eingegeben sind, werden das Koinzidenz-Ergebnis E und das Hamming-Ergebnis H in den Registern 910 beziehungsweise 920 gehalten.
Die Ausgänge der Register 910 und 920 sind mit den Eingängen der AND-Gates 933 beziehungsweise 934 verbunden. Die anderen Eingänge dieser AND-Gates werden jeweils über den Inverter 950 oder direkt mit dem Referenz-Signal versorgt. Die Ausgänge der zwei AND-Gates 933 und 934 sind mit zwei Eingängen der OR-Gates 941 verbunden, deren Ausgang mit der Ausgangs-Leitung 152 der Such- und Verarbeitungs-Einrichtung verbunden ist. Deshalb werden das in den zwei Registern 910 und 920 gehaltene Koinzidenz-Ergebnis E und Hamming-Ergebnis H selektiv in Übereinstimmung mit dem Zustand des Referenz-Signals 102 in die Ausgangs-Leitung 152 eingespeist: wenn "0" als Referenz-Signal 102 eingegeben ist, wird das Koinzidenz-Ergebnis E in dem ersten Register 910 ausgegeben und wenn "1" als Referenz-Signal 102 eingegeben ist, wird das Hamming-Ergebnis H des zweiten Registers 920 ausgegeben.
Bisher wurde die Erläuterung für die Wirkungsweise vorgenommen, wenn die Such-Information nicht maskiert ist. Dieser CAM ist zur Datenuche von maskierten Such-Information für alle partiellen Daten in der Lage. Diese Operation kann durch Unterbindung der Zuführung des Takt-Signals 712 zur Zeit der Ausgabe der Lese-Signale 151 und 151' zur Such- und Verarbeitungs-Einrichtung 710, hinsichtlich der zu maskierenden partiellen Daten, durchgeführt werden. Wenn das Takt-Signal 712 zur Such- und Verarbeitungs-Einrichtung gesperrt ist, wenn das Such-Ergebnis aus den partiellen Daten Ai in die Einrichtung 710 eingespeist wird, werden die Berechnungen, die auf EVi und ODi in den Formeln (1) und (2) basieren, nebeneinander durchgeführt, und deshalb kann das Vergleichs-Ergebnis für maskierte partielle Daten Ai erhalten werden.
Wie oben erklärt wurde, kann ein CAM, der eine Kapazität von N Worten mit M·K Bits besitzt, unter Verwendung konventioneller Speicher 110 von 2M·K Worten mit 2N Bits, konstruiert werden. Andererseits wird in dem in Fig. 1 gezeigten CAM ein konventioneller Speicher von 2M·K Worten mit 2N Bits als Speicher 110 benötigt, der dieselbe Kapazität besitzt. Deshalb kann dieser CAM mit einer kleineren Anzahl von Speicherzellen konstruiert werden und wird so preiswerter. Weiterhin kann dieser CAM nicht nur die Speicher-Information suchen, die gleich der Such-Information ist, sondern auch die Speicher-Information, die eine Hamming-Distanz von 1 zur Such-Information besitzt. Es ist auch möglich, eine Such-Operation durchzuführen, in der ein Teil der Such-Information maskiert ist.
Fig. 10 zeigt ein Ausführungsbeispiel des CAMs entsprechend eines dritten Aspektes der vorliegenden Erfindung. Dieser CAM kann Informationen mit einer Bitanzahl größer als die in Fig. 1 gezeigte suchen und speichern. Der CAM ist auch in der Lage, die Such- und Speicher-Operation mit einer höheren Geschwindigkeit, als die in Fig. 7 gezeigte, durchzuführen. Der CAM kann ferner mehrfache Vergleichs-Prozesse durchführen. Wegen dieser Unterschiede zu dem in Fig. 1 gezeigten CAM, besitzt der CAM in Fig. 10 einige Modifikationen. Der CAM enthält eine Vielzahl von Speichern 110, jeder stellt ein Speicherblock dar, eine Vielzahl von Zeilen-Wählern 120, jeder ist einem Speicher 110 zugeordnet, und eine Vielzahl von Lese-Daten-Generatoren 140, jeder ist ebenfalls einem Speicher 110 zugeordnet. Ferner ist eine Such- und Verarbeitungs-Einrichtung 1010 vorhanden, die die Lese-Signale von den geraden Spalten 151 und und den ungeraden Spalten 151' jedes Speichers 110 empfängt, um die Such-Ergebnis-Signale 152 auszugeben, die anzeigen, wenn die empfangenen Signale unter der Such-Bedingung, die von dem Referenz-Signal 102 bestimmt wird, eine Identität oder Ähnlichkeit mit der Such-Information zeigen. Diese Such-Ergebnis-Signale 152 werden in ein Register-Array 1020, das parallel angeordnete Register derselben Anzahl wie die Such-Ergebnis-Signale 152 enthält, eingespeist und zeitweilig gehalten. Die Ausgänge des Register-Arrays 1020 werden parallel mit einem Kodierer 160 verbunden, der ein Such-Adressen-Ausgangs-Bus 162 besitzt, welcher mit dem Dekoder 1030 verbunden ist. Dieser Dekoder 1030 legt ein Reset-Signal 1031 an ein Register im Register-Array 1020 an, das durch die Such-Adresse des Kodierers 160 bestimmt wird. Zusätzlich empfängt der Spalten-Wähler 130 eine Registrier-Adresse 132 und steuert selektiv eine der Spalten- Wahl-Leitungen 131 jedes Speichers 110 an. Für den Zeilen- Wähler 120, den Spalten-Wähler 130 und den Schreib-Daten- Generator 140 kann der gleiche, wie der in Fig. 1 gezeigte CAM, verwendet werden.
Wenn ein derartiger CAM eine Speicher-Kapazität von N Worten mit M·K Bits besitzt, kann jeder Speicher 110 mit Speicherzellen konstruiert werden, die in einer Matrix von 2M Zeilen in 2N Spalten angeordnet sind, das heißt, es ist ein Speicher von 2M Worten mit 2N Bits und K Sätzen derartiger Speicher erforderlich. Ein Ansteigen der Bit-Anzahl wird im CAM der Fig. 7 durch das Ansteigen der Wort-Anzahl realisiert, während bei dem vorhandenen CAM die Bit-Anzahl durch die Erhöhung der Zahl der Speicher 110 vergrößert wird. Deshalb entspricht jeder Block im Speicher 110 im CAM der Fig. 7 jedem Speicher 110 des vorliegenden CAMs. Die Such-Information und die Speicher-Information, die eine Länge von M·K Bits besitzen, werden in K Stücke von M Bitdaten 101 geteilt, welche dann parallel den K Zeilen- Wählern 120 und den K Schreib-Daten-Generatoren 140 zugeführt werden. Fig. 10 ist eine Veranschaulichung für k = 3.
Bei der Speicher-Operation des in Fig. 10 gezeigten CAMs wird die zu speichernde Information als drei geteilte Daten-Stücke 101 angelegt. Jedes Stück der Eingangs-Daten 101 wird in jedem Speicher 110 in der in Fig. 2 gezeigen Weise gespeichert und registriert.
Bei der Such-Operation werden die in einer Spalte jedes Speichers 110 gespeichert Daten, die von der Such-Information (Eingangs-Daten) 101 bestimmt wird, als die geraden Spalten-Lese-Signale 151 und die ungeraden Spalten-Lese- Signale 151' an die Such- und Verarbeitungs-Einrichtung 1010 angelegt. Die Such- und Verarbeitungs-Einrichtung 1010 prüft die Lese-Signale 151 und 151', um zu bestimmen, wenn die gespeicherten Daten unter der Such-Bedingung, die von dem Referenz-Signal 102 bestimmt wird, identisch oder ähnlich den Such-Informationen sind, und legt dann die Ergebnisse als Such-Ergebnis-Signale 152 jeweils an die N Register des Register-Arrays 1020. Das Register-Array 1020 speichert die Such-Ergebnis-Signale 152 in Synchronisation mit dem Takt-Signal 712. Speziell wird in jedes Register- Array 1020 "1" eingegeben und gespeichert, wenn die gespeicherte Information in den entsprechenden Paaren der angrenzenden Spalten des Speichers 110 gleich der Such-Information (Eingangs-Daten) sind, während im anderen Fall "0" eingegeben und gespeichert wird. Wenn in einem Register im Register-Arrays 1020 "1" gespeichert ist, gibt der Kodierer 160 ein Koinzidenz-Signal 161 aus und liefert die Such- Adresse 162, die repräsentativ für den Platz des Registers ist, in dem "1" gespeichert ist. Die so ausgegebene Such- Adresse 162 zeigt die Adresse der Information an, welche auf der Basis der Such-Information unter der Such-Bedingung, die von dem Referenz-Signal 102 bestimmt wurde, gesucht wurde, ähnlich den in den Fign. 1 und 7 gezeigten CAMs. Mit anderen Worten, die Such-Adresse 162 zeigt die Adresse der Information an, welche die gleiche wie die Such-Information oder die durch die Hamming-Distsanz 1 von der Such-Information getrennte ist.
Im Falle des mehrfachen Vergleichs, wo die gespeicherten Daten unter der Such-Bedingung, die von dem Referenz-Signal bestimmt wird, in mehreren Adressen die Identität oder Ähnlichkeit erfüllen, wird "1" in mehreren Registern im Register-Array 1020 gespeichert. Unter diesen Umständen kann der Kodierer 160 die Plätze der Register kodieren, in denen "1" in der Reihenfolge des höchsten Registerplatzes zum niedrigsten Registerplatz oder umgekehrt gespeichert ist. Außerdem wird ein Reset-Signal 1031 an den Dekoder 1030 angelegt, so daß der Dekoder 1030 die Register 1021 zurücksetzt, die von der Such-Adresse 162 spezifiziert wurden. Als Folge davon gibt der Kodierer 160 die nächste Such- Adresse aus. Somit werden bei dem mehrfachen Vergleich alle Such-Adressen der Reihe nach bei einem fortlaufenden Zuführen des Reset-Signals 1031 an ein externes Gerät ausgegeben, bis das Koinzidenz-Signal "0" ist.
Wie oben erklärt wurde, kann der CAM der Fig. 10 die Bitanzahl der Such-Information und der Speicher-Information ohne erhebliche Vergrößerung der Speicher-Kapazität des Speichers 110 erweitern. Der CAM kann sowohl die Such-Operation für Datenworte, die die Hamming-Distanz 1 vom Suchwort besitzen, als auch die Such-Operation für Datenworte, welche identisch mit der Such-Information sind, durchführen. Es können auch Prozesse mehrfacher Vergleiche erreicht werden. Während der in Fig. 7 gezeigte CAM sequentiell die Speicherung oder die Suche von Informationen großer Bitanzahl durch ihre Teilung in mehrere Daten-Stücke durchführt, besitzt der in Fig. 10 gezeigte CAM außerdem eine vorteilhafte Fähigkeit zur parallelen Durchführung der Speicher- und der Such-Operation für Informationen mit großer Bitanzahl durch die Teilung der Information in mehrere Datenwort-Stücke. Deshalb kann im CAM der Fig. 10 die Such-Operation mit nur einem gleichzeitigen Zugriff auf alle Speicher 110 erfolgen, so daß eine höhere Arbeits-Geschwindigkeit realisiert werden kann.
Fig. 11 zeigt ein Ausführungsbeispiel der Such- und Verarbeitungs-Einrichtung 1010, die in dem in Fig. 10 gezeigten CAM verwendet wird. Die gezeigte Schaltung ist eine Grund-Einheit der Such- und Verarbeitungs-Einrichtung für die Erzeugung eines Such-Ergebnis-Signales, wobei die Einheit sechs AND-Gates 1110, 1120, 1130, 1140, 1150 und 1160, zwei OR-Gates 1170 und 1180 und einen Inverter 1190, welcher wie in Fig. 11 gezeigt angeschlossen ist, enthält. Diese Such- und Verarbeitungs-Einheit empfängt Lese-Signale von den gleichen gerade numerierten Spalten 151 und den gleichen ungerade numerierten Spalten 151' aller Speicher und das Referenz-Signal 102. Deshalb wird die gezeigte Such- und Verarbeitungs-Einheit für jedes Paar der angrenzenden Spalten der drei Speicher 110 eingesetzt.
Angenommen, daß die Lese-Signale 151 von derselben -spezifizierten gerade numerierten Spalte der K Speicher 110 EV&sub0; ... EVi . . . SEVk-1 sind und daß die Lese-Signale 151 von derselben ungerade numerierten Spalte der K Speicher 110, die an die obigen gerade numerierten Spalten angrenzen, OD&sub0; . . . ODi . . . ODk-1 sind, dann wird das Koinzidenz-Ergebnis E und das Hamming-Ergebnis H aus den Formeln (1) beziehungsweise (2) erhalten. Wenn wir K = 3 nehmen, wie in Fig. 10 gezeigt wird, werden das Koinzidenz-Ergebnis und das Hamming-Ergebnis wie folgt dargestellt:
E = EV&sub0;·EV&sub1;·EV&sub2; (3)
H = EV&sub0;·EV&sub1;·OD&sub2; + EV&sub0;·OD&sub1;·EV&sub2; + OD&sub0;·EV&sub1;·EV&sub2; (4)
Das AND-Gate 1110 führt die logische Operation der Formel (3) durch und gibt das Koinzidenz-Ergebnis E aus. Die AND-Gates 1120, 1130 und 1140 und das OR-Gate 1170 wirken zur Durchführung der Operation der Formel (4) zusammen und geben das Hamming-Ergebnis H aus. Jedes dieser Ergebnisse wird von einer Gate-Schaltung, welche aus den AND-Gates 1150 und 1160, dem OR-Gate 1180 und dem Inverter aufgebaut ist und von dem Referenz-Signal 102 gesteuert wird, selektiv als Such-Ergebnis-Signal 152 ausgegeben.
Die in Fig. 9 gezeigte Such- und Verarbeitungs-Einrichtung führt der Reihe nach die logischen Operationen der Formeln (1) und (2) in Synchronisation mit dem Takt-Signal 712 durch, während die Such- und Verarbeitungs-Einrichtung der Fig. 11 die in den Formeln (3) und (4) gezeigten Operationen parallel durchführt.
Fig. 12 zeigt ein Ausführungsbeispiel eines CAMs entsprechend eines vierten Aspektes der vorliegenden Erfindung. In dem in der Fig. 7 oder der Fig. 10 gezeigten CAM wird die Erweiterung der Bitanzahl der zu verarbeitenden Information durch den Anstieg der Wortanzahl des Speicher 110 oder der Anzahl der Speicher 110 realisiert; in dem vorliegenden CAM wird die Spaltenanzahl oder die Bitanzahl der Speicher 110 direkt erhöht. Zu diesem Zweck wird die Spaltenanzahl des Speichers 110 auf 2NK erhöht und ein erweiterter Spalten- Wähler 1210 eingeführt. Zusätzlich zu diesem Merkmal wird ein Zähler 720 für Zähl-Eingangs-Daten mit dem Spalten-Wäh- 1er 1210 gekoppelt.
Wenn der vorliegende CAM die Speicher-Kapazität von N Worten mit M·K Bits besitzt, wird der Speicher 110 mit konventionellen Speicherzellen, die in einer Matrix von 2M Zeilen in 2·N·K Spalten angeordnet sind, konstruiert. Das heißt, der Speicher 110 besitzt eine Speicher-Kapazität von 2M Worten mit 2·N·k Bits und die Bitanzahl des Zählers 1210 wird log&sub2;K Bits. Der Speicher 110 wird in N Blöcke geteilt, jeder Block besitzt 2K Spalten, wie durch die unterbrochene Linie gezeigt wird. Jeder Block entspricht einem Wort des CAMs, der von der Registrier-Adresse 132 bestimmt wird. Die Such-Information und die Speicher- Information von M·K Bits werden jeweils in K Stücke von M-Bit-Datenworte 101 geteilt und nacheinander k mal in der Reihenfolge vom MSB-Daten-Stück bis zum LSB-Daten-Stück eingegeben. Die in K Stücke der Datenworte 101 geteilte Speicher-Information, wird insgesamt in einem Block gespeichert, der von der Registrier-Adresse 132 in der Weise spezifiziert wird, daß jedes der Datenworte-Stücke in dem entsprechenden vorbestimmten Paar der angrenzenden Spalten desselben Blocks gespeichert wird.
Die Speicher-Operation und die Such-Operation des in Fig. 12 gezeigten CAMs sind die gleichen, wie die in dem in Fig. 7 gezeigten CAM, ausgenommen der folgenden zwei Punkte: die partielle Datenworte der Speicher-Information sind in Spaltenrichtung des Speichers 110 gespeichert und die auf dem partiellen Datenwort der Such-Information basierenden Lese-Signale 151 und 151, werden durch Abtastung in Spaltenrichtung erhalten. Das Zähler-Ausgangs-Signal 175 des Zählers 720 wird dem Spalten-Wähler 1210 zur Spezifizierung der angrenzenden zwei Spalten in jedem Block des Speichers 110 zugeführt. Der Zählwert des Zählers 720 wird für jedes als Datenwort 101 eingegebene partielle Datenwort erhöht. Deshalb steuert der Spalten-Wähler 1210 bei der Speicher- Operation eine gerade Spalten-Wahl-Leitung 131 und dann die angrenzende ungerade Spalten-Wahl-Leitung 131 in einem Block an, der von der Registrier-Adresse 132 für ein eingegebenes partielles Datenwort bestimmt wird, und wiederholt einen derartigen Ansteuerungs-Vorgang für jedes eingegebene partielle Datenwort, während das anzusteuernde Paar der geraden und ungeraden Spalten geschoben wird.
Bei der Such-Operation steuert andererseits der Spalten- Wähler 1210 die angrenzenden geraden und ungeraden zwei Spalten-Wahl-Leitungen 131 und 131' aller Speicherblöcke, die von dem Zähler 720 für jedes eingegebene partielle Datenwort spezifiziert werden, parallel an. Deshalb wird, da der Zähler 720 für jedes eingegebene partielle Datenwort erhöht wird, das Paar der angrenzenden geraden und ungeraden Spalten, die in jedem Speicherblock anzusteuern sind, der Reihe nach in Richtung der Spalte geschoben. Außerdem werden die mit den nicht angesteuerten Spalten-Wahl-Leitungen 131 und 131' verbunden Spalten des Speichers 110 in einem Zustand hoher Impedanz gehalten, und so werden die Daten nur der angrenzenden, mit den angesteuerten Spalten-Wahl- Leitungen verbundenen, zwei Spalten der Reihe nach für jedes eingegeben partielle Datenwort der Such-Information in die Such- und Verarbeitungs-Einrichtung 710 ausgegeben.
Als Zeilen-Wähler 120, Schreib-Daten-Generator 140, Such- und Verarbeitungs-Einrichtung 710 und Kodierer 160 können die gleichen eingesetzt werden, wie die, die in dem in Fig. 7 gezeigten CAM verwendet werden.
Wie oben erläutert wird, kann ein CAM, der eine Speicher- Kapazität von N Worten mit M·K Bits besitzt, unter Verwendung eines konventionellen Speichers von 2M Worten mit 2NK Bits konstruiert werden. In Hinblick auf die Tatsache, daß der in Fig. 1 gezeigte CAM einen konventionellen Speicher von 2MxKk Worten mit 2N Bits für das Ziel, dieselbe Speicher-Kapazität zu besitzen, erfordert, kann der vorliegende CAM mit einem Speicher einer geringeren Speicher-Kapazität konstruiert werden, und deshalb ist er sehr preiswert. Es ist ein anderer Vorteil, daß der CAM sowohl eine Such-Operation für Daten, die eine Hamming-Distanz 1 von der Such-Inforination besitzen, als auch für Daten, die identisch mit der Such-Information sind, durchführen kann.
Fig. 13 zeigt ein Ausführungsbeispiel des Spalten-Wählers 1210, der in dem in Fig. 12 gezeigten CAM verwendet wird. Dieser Spalten-Wähler enthält einen Block-Dekoder 1310, der die Registrier-Adresse 132 empfängt, und einen Spalten-Dekoder 1320, der das Ausgangs-Signal vom Zähler 720 empfängt. Der Block-Dekoder 1310 enthält mehrere parallele Ausgangs-Leitungen und steuert eine der zugeordneten Ausgangs-Leitungen selektiv an, die von der Registrier-Adresse 132 angezeigt wird. Die Ausgangs-Leitungen des Block-Dekoders 1310 sind jeweils in einer Eins-zu-eins Beziehung mit einem der Eingänge der Zwei-Eingangs-OR-Gates verbunden, welche zur Bildung eines OR-Gate-Arrays 1340 parallel angeordnet sind. Dem anderen Eingang jedes OR-Gates in dem Gate-Array 1340 wird über den Inverter 1330 das Betriebs- Moden-Signal 103 zugeführt, und die Ausgänge aller OR-Gates sind in einer Eins-zu-eins-Beziehung mit dem AND-Gate-Array 1380 verbunden, wobei jedes von ihnen einem der Speicherblöcke zugeordnet ist. Andererseits enthält der Spalten-Dekoder 1320 mehrere parallele Ausgangs-Leitungen und steuert selektiv eine der zugeordneten Ausgangs-Leitungen an, die von dem Zähler-Ausgang-Signal 175 des Zählers 720 spezifiziert wird. Zusätzlich wird jedes Ausgangs-Signal des Spalten-Dekoders 1320 in alle AND-Gate-Arrays 1380 eingespeist. Ferner ist der Ausgang des Inverters 1330 mit einem Eingang der zwei OR-Gates 1360 beziehungsweise 1370 verbunden. Einer der OR-Gates 1360 ist mit seinem anderen Eingang mit dem Ausgang des anderen Inverters 1350 verbunden, der das Spalten-Wahl-Signal 133 empfängt, und der andere Eingang des anderen OR-Gates 1370 ist zum direkten Empfang des Spalten-Wahl-Signals 133 angeschlossen. Die Ausgangs-Signale der zwei OR-Gates 1360 und 1370 werden jeweils in alle AND-Gate-Arrays 1380 eingespeist.
Jedes der AND-Gates-Arrays 1380 enthält parallel angeordnete Drei-Eingangs-AND-Gates in der doppelten Anzahl der Ausgangs-Leitungen des Spalten-Dekoders 1320. In jedem AND-Gate-Array sind die ersten Eingänge aller AND-Gates mit dem Ausgang des entsprechenden OR-Gates in dem OR-Gate-Array 1340 verbunden. Jedes Paar der angrenzenden AND-Gates sind mit ihrem zweiten Eingang gemeinsam mit der entsprechenden Ausgangs-Leitung des Spalten-Dekoders 1320 verbunden. Ein AND-Gate jedes AND-Gate Paares, das heißt, der dritte Eingang jedes gerade numerierten AND-Gates ist mit dem Ausgang des OR-Gates 1360 verbunden, und ein Ausgang ist mit einer geraden Spalten-Wahl-Leitung 131 verbunden. Das andere AND-Gate jedes AND-Gate-Paares, das heißt, der dritte Eingang jedes ungerade numerierten AND-Gates ist mit dem Ausgang des OR-Gates 1370 und sein Ausgang ist mit einer ungeraden Spalten-Wahl-Leitung 131' verbunden.
Bei der Such-Operation wird, da "0" als Betriebs-Moden- Signal 103 angelegt ist, "1" von den OR-Gates 1340, 1360 und 1370 ausgegeben. Dann wird ein Paar der Paare der Spalten-Wahl-Leitungen 131 und 131', die mit jedem Block des von dem Spalten-Dekoder 1320 bestimmten Speichers 110 gekoppelt sind, parallel angesteuert.
Bei der Speicher-Operation wird "1" als Betriebs-Moden- Signal 103 angelegt. Deshalb wählt der Block-Dekoder 1310 auf der Basis der Registrier-Adresse 132 einen der AND- Gate-Arrays 1380 aus und der Spalten-Dekoder 1320 wählt ferner in Übereinstimmung mit dem Ausgangs-Signal 175 des Zählers 720 in dem angezeigten AND-Gate-Array ein Paar der angrenzenden AND-Gate-Paare aus. Die OR-Gates 1360 und 1370 wirken zur Wahl jedes der ausgewählten angrenzenden AND- Gate-Paare bezüglich des Spalten-Wahl-Signals 133 zusammen, so daß die geraden beziehungsweise ungeraden Spalten-Wahl- Leitungen 131 und 131' mit den Ausgängen der ausgewählten angrenzenden AND-Gate-Paare selektiv und sequentiell in der erwähnten Reihenfolge angesteuert werden. Somit sind Daten in ein Spalten-Paar im Speicher, das mit einem Paar der so angesteuerten geraden und ungeraden Spalten-Wahl-Leitungen 131 und 131' verbunden ist, einzuschreiben.
Fig. 14 zeigt ein Ausführungsbeispiel des CAMs entsprechend eines fünften Aspektes der vorliegenden Erfindung. Der vorliegende CAM, der eine hohe Speicher-Kapazität erzielt, enthält mehrere CAM-Einheiten 1410 entsprechend des in den Fig. 1, 7, 10 und 12 gezeigten CAMs, mehrere Daten-Ausgabe- Einrichtungen 1420, die Daten von mehreren CAM-Einheiten 1410 empfangen, einen Kodierer 1430, der Daten von mehreren Daten-Ausgabe-Einrichtungen 1420 empfängt, und einen Dekoder 1440 für das Anlegen von Schreib-Zeitgeber-Impulsen 104 an jede CAM-Einheit 1410. Das Takt-Signal 712, das Referenz-Signal 102, das Initialisierungs-Signal 711, die Eingangs-Daten 101, das Betriebs-Moden-Signal 103, die Registrier-Adresse 132 und das Spalten-Wahl-Signal 133 werden parallel an alle cAM-Einheiten 1410 angelegt.
Der vorliegende CAM ist zur Verarbeitung mehrfacher Vergleiche in der Lage, wenn mehrere Informationen von der such-Information unter der Bedingung des im Speicher gespeicherten Referenz-Signals spezifiziert werden. Im Folgenden soll die Erläuterung der Verarbeitung eines mehrfachen Vergleichs erfolgen. Um die in den Fign. 1, 7 und 12 gezeigten CAMs als CAM-Einheit 1410 zu verwenden, müssen ferner einige Komponenten in die CAMs eingesetzt sein. Der in Fig. 1 gezeigte CAM muß mit einem Register ausgerüstet werden, das das Such-Ergebnis-Signal 152 empfängt. Ferner müssen die in den Fig. 1, 7 und 12 gezeigten CAMs mit einem Dekoder ausgerüstet werden, der die Such-Adresse 162 empfängt und ein Reset-Signal an das Register oder die Such- und verarbeitungs-Einrichtung 710 anlegt, die von der Such- Adresse spezifiziert wird. Bei dem Vorgang eines mehrfachen Vergleichs wird, wenn das Reset-Signal von dem Dekoder an das Register oder die Such- und verarbeitungs-Einrichtung angelegt wird, das Such-Ergebnis-Signal 152 entsprechend der Such-Adresse 162 ausgegeben, sofern es freigegeben ist. Im Ergebnis erzeugt der Kodierer 160 die nächste Such-Adresse 162, die den Vorgang des mehrfachen Vergleichs ermöglicht. Wie oben erläutert wird, kann der CAM, der als CAM-Einheit verwendet wird, die Daten eines mehrfachen Vergleichs verarbeiten.
Bei der Speicher-Operation werden das Betriebs-Moden-Signal 103 mit "1", das Initialisierungs-Signal 711, das Spalten- Signal 133, das Takt-Signal 712, die Eingangs-Daten 101 und die Registrier-Adresse 132 an jede CAM-Einheit 1410 angelegt, ähnlich den CAMs, die in den Fign. 1, 7 und 12 gezeigt werden. Die Registrier-Adresse wird in eine Registrier-Adresse 132 mit niedriger Ordnung und eine Registrier-Adresse 1441 mit hoher Ordnung eingeteilt: die erstere wird in jede CAM-Einheit eingespeist, die letztere wird an den Dekoder 1440 angelegt. Die Registrier-Adresse 1441 mit hoher Ordnung spezifiziert eine der CAM-Einheiten 1410, während die Registrier-Adresse 132 die Worte in den CAM-Einheiten 1410 bestimmt. Ein Schreib-Signal 1442, das die Schreib-Operation der Daten in den CAM einleitet, wird an den Dekoder 1440 angelegt, welcher dann das Schreib- Takt-Signal 104 selektiv an die CAM-Einheit 1410 anlegt, die von der Registrier-Adresse 1441 mit hoher Ordnung bestimmt wird.
Bei der Such-Operation wird das Takt-Signal 712, das Referenz-Signal 102, das Initialisierungs-Signal 711, die Eingangs-Daten 101 und das Betriebs-Moden-Signal 103 parallel an jede CAM-Einheit 1410 angelegt. Von den CAM-Einheiten 1410, die die von der Such-Information (Eingnags-Daten) 101 spezifizierten Daten unter der Bedingung des Referenz- Signal 103 speichern, wird das Koinzidenz-Signal 161 mit "1" zusammen mit der Such-Adresse 162 ausgegeben. Wenn "1" als Koinzidenz-Signal 161 von mehreren CAM-Einheiten 1410 ausgegeben wird, wird von der CAM-Einheit eine Priorität- Reihenfolge von rechts nach links gegeben, so daß die Daten-Ausgabe-Einrichtung 1420 die Such-Adresse 162 in der Reihenfolge von der CAM-Einheit 1410 mit der hohen Ordnung ausgeben. Um eine derartige Prioritäts-Ordnung der CAM-Einheiten einzurichten, wird ein Freigabe-Signal 1422 von "1" an die Daten-Ausgabe-Einrichtung 1420 der CAM-Einheit mit der höchsten Ordnung oder der am weitesten links liegenden CAM-Einheit 1410 angelegt und zur gleichen Zeit speist jede Daten-Ausgabe-Einrichtung 1420 ein Freigabe-Signal in die angrenzende rechtsseitige Daten-Ausgabe-Einrichtung ein. Wenn die Daten-Ausgabe-Einrichtung 1420 das Freigabe-Signal von "1" empfängt und wenn sie auch das Koinzidentz-Signal 161 von "1" empfängt, gibt sie die Such-Adresse 162 an den Adressen-Bus 1421 aus und speist zur gleichen Zeit ein Freigabe-Signal von "0" in die angrenzende linksseitige Daten-Ausgabe-Einrichtung 1420 ein. Wenn aber die Daten-Ausgabe-Einrichtung 1420 das Koinzidenz-Signal von "0" empfängt, wenn sie das Freigabe-Signal von "1" empfängt, speist sie das Freigabe-Signal von "1" in die angrenzende rechtsseitige Daten-Ausgabe-Einrichtung 1420 ein. Ferner setzt die Daten-Ausgabe-Einrichtung 1420, wenn sie ein Freigabe-Signal von "0" empfängt, einen internen Ausgabe- Puffer für die Such-Adresse, ungeachtet der Bedingung des Koinzidenz-Signals 161 in einen Zustand hoher Impedanz, und speist zur gleichen Zeit das Freigabe-Signal von "0" in die rechtsseitige Einrichtung ein. Deshalb halten alle Daten- Ausgabe-Einrichtungen, die rechts von der Daten-Ausgabe- Einrichtung angeordnet sind, welche die Such-Adresse 162 in den Bus 1421 einspeist, ihren internen Ausgabe-Puffer in einem Zustand hoher Impedanz.
Ferner gibt die Daten-Ausgabe-Einrichtung 1420, die die Such-Adresse 162 ausgibt, auch das Koinzidenz-Signal 161 von "1" als das erste Koinzidenz-Signal 1423 an den Kodierer 1430, während alle Daten-Ausgabe-Einrichtungen 1420, außer der Daten-Ausgabe-Einrichtung 1420, die die Such- Adresse ausgibt, das erste Koinzidenz-Signal 1423 mit "0" zum Kodierer 1430 erzeugen. Der Kodierer 1430, der diese ersten Koinzidenz-Signale 1423 empfängt, erzeugt ein zweites Koinzidenz-Signal 1431, das anzeigt, ob "1" als erstes Koinzidenz-Signal 1423 eingeben ist oder nicht, und er erzeugt auch eine Such-Adresse 1432 mit hoher Ordnung, die den Speicherplatz des ersten Koinzidenz-Signals 1423 mit "1" anzeigt. Das zweite Koinzidenz-Signal 1431 zeigt an, daß die Daten, die von der Such-Information unter der Bedingung des Referenz-Signals spezifiziert sind, in dem CAM gespeichert sind. Die Such-Adresse 1432 mit der hohen Ordnung zeigt den Speicherplatz der CAM-Einheit an, wo die gewünschten Daten gespeichert sind. Die Such-Adresse 1421 mit der niedrigen Ordnung zeigt die Such-Adresse 162 der CAM-Einheit an, das heißt, die Position der Spalte des Speichers, in der die gewünschten Daten gespeichert sind.
Externe Geräte (nicht gezeigt) überwachen das zweite Koinzidenz-Signal 1431 und lesen die Such-Adresse 1432 mit der hohen Ordnung und die Such-Adresse 1421 mit der niedrigen Ordnung und legen auch das erste Reset-Signal 1424 an jede Daten-Ausgabe-Einrichtung 1420 an. Das erste Reset-Signal 1424 macht es möglich, die Such-Adresse zu erhalten, die der Information der nächst höheren Prioritäts-Ordnung entspricht, wenn mehrere Information identisch mit der in dem CAM gespeicherten Such-Information sind. Die Daten-Ausgabe- Einrichtung 1420, die die Such-Adresse 162 ausgibt, antwortet auf das erste Reset-Signal 1424 und speist ein Reset- Signals 1031 in die zugeordneten CAM-Einheiten 1410 ein, so daß sie die nächste Such-Adresse 162 ausgibt.
Wie oben erklärt wird, kann der vorliegende CAM mit den in den Fig. 1, 7 und 12 gezeigten CAMs konstruiert werden. Deshalb ist die Erweiterung der Wortanzahl zur Bereitstellung einer hohen Speicher-Kapazität einfach realisiert.
Fig. 15 ist eine Darstellung der Daten-Ausgabe-Einrichtung 1420, die in dem in Fig. 14 gezeigten CAM verwendet wird. Die Daten-Ausgabe-Einrichtung enthält einen Ausgabe-Puffer 1510, drei AND-Gates 1520, 1530 und 1540 und einen Inverter 1550, welcher wie gezeigt angeschlossen ist.
Wenn beide, das Koinzidenz-Signal 161 und das Freigabe- Signal 1422, die in einen Freigabe-Signal-Eingabe-Anschluß 1560 an der linken Seite des Daten-Ausgabe-Einrichtung 1420 eingegeben werden, "1" sind, gibt das AND-Gate 1530 ein Signal mit "1" als erstes Koinzidenz-Signal 1423 aus und steuert den Ausgangs-Puffer 1510 an, so daß die Such- Adresse 162 über den Ausgabe-Puffer 1510 als Such-Adresse 1421 mit niedriger Ordnung ausgegeben wird. Ferner gibt das AND-Gate 1540 das Freigabe-Signal von "0" an einen Freigabe-Signal-Ausgabe-Anschluß 1570, welcher an einen Freigabe-Signal-Eingabe-Anschluß angeschlossen werden soll, an der rechten Seite der Daten-Ausgabe-Einrichtung 1420 ein. Deshalb ist der Ausgabe-Puffer 1510 an der rechten Seite der Einrichtung 1420 in den Zustand hoher Impedanz gebracht. Ferner passiert das erste Reset-Signal 1424 das AND-Gate 1520 und wird als Reset-Signal 1031 an die zugeordnete CAM-Einheit angelegt. In allen Daten-Ausgabe-Einrichtung 1420, die an der Seite der Daten-Ausgabe-Einrichtung 1420 angeordnet sind, die "1" als das erste Koinzidenz-Signal 1423 erzeugen, passiert das erste Reset-Signal 1424 nicht das AND-Gate 1520 und deshalb geben sie kein Reset-Signal 1031 aus.
Wie bisher im Detail erläutert wurde, kann ein CAM entsprechend der vorliegenden Erfindung mit preiswerten konventionellen Speicher-Einrichtungen konstruiert werden, auf die durch Anlegen der Adresse, die den Speicherplatz des gewünschten Datenwortes anzeigt, zugegriffen wird. Der in Fig. 1 gezeigte CAM, der eine Speicher-Kapazität von N Worten mit M Bits besitzt, kann durch Verwendung eines konventionellen Speichers von 2M Worten mit 2N Bits als der Speicher 110 konstruiert werden. Die in den Fig. 7, 10 und 12 gezeigten CAMs, die eine Speicher-Kapazität von N Worten mit M·K Bits besitzen, können mit einem konventionellen Speicher von 2M·K Worten mit 2N Bits oder 2M Worten mit 2NK Bits oder mit K Stücken konventioneller Speicher, die 2M Worte mit 2N Bits besitzen, konstruiert werden. Deshalb können die folgenden CAMs, die 1 MBit-Speicher-Chips verwenden, mit nur einem Chip konstruiert werden: ein CAM, der 512 Worte mit 10 Bits besitzt, wie in Fig. 1 gezeigt wird, oder der Eingangs-Daten 101 von 6 Bits voraussetzt und die Such-Information in acht Stücke (k=8) geteilt wird, ein 48 Kilo-Bit CAM mit 1 Kilo-Worten von 48 Bits, wie in den Fig. 7, 10 und 12 gezeigt wird. Die Untersuchung der auf dem Markt verfügbaren CAMs, zum Beispiel des CAM "IC 8220", der bei Signetics Corporation kommerziell verfügbar ist, besitzt eine Speicher-Kapazität von 4 Worten mit zwei Bits. Es ist deshalb deutlich, daß ein CAM entsprechend der vorliegenden Erfindung eine bedeutend größere Speicher-Kapazität besitzt.
Die Such-Operation und die Speicher-Operation können im CAM nur mit einem oder mehreren Zugriffen auf konventionelle Speicher durchgeführt werden. Deshalb kann die Arbeit des CAMs mit einer höheren Geschwindigkeit ausgeführt werden, als sie in konventionellen CAMs mit Wort-seriell/Bit-paraller und Wort-parallel/Bit-serieller Arbeitsweise realisierbar ist. Ferner ist es möglich, die Such-Operation bei Maskierung eines Teils der Such-Information auszuführen, sowie auch eine Verarbeitung eines mehrfachen Vergleichs durchzuführen, wenn die gewünschten Daten in mehreren Adressen gespeichert sind. Die Erweiterung der Speicherkapazität kann auch einfach realisiert werden. Es kann nicht nur die Such-Operation unter Koinzidenz-Bedingung sondern auch die Such-Operation innerhalb einer bestimmten Hamming-Distanz durchgeführt werden.
Insgesamt können entsprechend der vorliegenden Erfindung, eine hohe Operationsgeschwindigkeit, eine große Speicher- Kapazität, ein niedriger Preis und mehrfache CAM-Funktionen realisiert werden. Wenn ein derartiger CAM als Speicher eines Informations-Verarbeitungs-Systems verwendet wird, wie etwa einer Daten-Basis, einer Muster-Erkennung oder künstlichen Intelligenz, kann das System schnelle assoziative Prozesse und Vergleichs-Operationen durchführen.
In den vorgehenden erwähnten Ausführungsbeispielen wird "1" für die geraden Spalten-Nummern des Speichers 110 nur in einer Zeile gespeichert, die von der Speicher-Information bestimmt wird, und für die ungeraden Spalten-Nummern des Speichers 110 wird "1" in den Zeilen gespeichert, die von den Datenworten bestimmt werden, die die Hamming-Distanz "1" von der Such-Information besitzen. Dies ist nur ein Beispiel für die Datenwort-Speicherung. Es gibt einige andere Verfahren zur Speicherung von Daten-Worten. Für die Hamming-Distanz können verschiedene andere Distanzen gewählt werden. Zum Beispiel kann "1" in den Zeilen gespeichert werden, die von allen Daten innerhalb einer vorbestimmten Hamming-Distanz spezifiziert werden. Datenworte verschiedener Hamming-Distanzen können in mehreren Spalten in der Weise gespeichert werden, daß alle Datenworte derselben Hamming-Distanz in derselben Spalte gespeichert werden. Ferner kann die Hamming-Distanz zu Beginn der Speicher-Operation bestimmt werden. In den obigen Ausführungsbeispielen ist die Information in einem Paar angrenzender Spalten des Speichers 110 gespeichert, aber die zwei Spalten müssen nicht aneinander angrenzend sein. Wie oben erläutert wird, sind Veränderungen und Modifikationen des Schreib-Daten-Generators 140, der Such- und Verarbeitungs- Einrichtung 710 und der Spalten-Wähler 130 und 1210 möglich.
Die Anzahl der Eingangs/Ausgangs-Anschlüsse kann durch Verwendung derselben Anschlüsse für den Registrier-Adressen- Bus 132 und den Such-Adressen-Bus 162 reduziert werden.
Deshalb sind die Erfindungen in keiner Weise auf die Details der erläuterten Ausführungen begrenzt.

Claims

1. Inhaltsadressierbarer Speicher zum Suchen von Datenworten und ihren zugehörigen Adressen j, welcher N Datenworte speichert, welche alle aus k oder in Stücken bestehen, wobei jedes Stück aus M-Bits besteht, k, in = 1, 2, . . .n, und seine Daten kodiert hat in einem "1 aus M"-Code; und wobei jedes Datenwort seine zugehörige Adresse j hat, wobei der inhaltsadressierbare Speicher enthält:

eine Speichervorrichtung (110) mit einer Matrix aus herkömmlichen Speicherzellen aus k·2M Reihen und m·N Paaren von Spalten, wobei jedes Datenwort (101) in den in-Paaren der Spalten gespeichert ist, die seiner zugehörigen Adresse j (162) entsprechen und wobei in jeder ersten Spalte des Paares das Datenwort (101) selbst gespeichert ist, während in der anderen Spalte ein Datenwort gespeichert ist, welches eine bestimmte funktionale Beziehung zu dem Datenwort (101) hat;

eine Zeilenwahlvorrichtung (120), die mit der Speichervorrichtung (110) verbunden ist und im Falle einer Suchoperation sequentiell alle k-Zeilen der Matrix der Speicherzellen entsprechend dem "1 aus M-Code" sequentiell auswählen kann;

eine Spaltenauswahlvorrichtung (130), die mit der Speichervorrichtung (110) gekoppelt ist und im Falle einer Speicheroperation alle in-Paare von Spalten der Matrix aus Speicherzellen entsprechend der Datenwortadresse J sequentiell auswählen kann;

einen Codierer (160), der im Falle einer Suchoperation Zeile für Zeile alle Daten empfangen kann, die in den Speicherzellen der k-ausgewählten Spalten gespeichert sind und von den darin aktivierten in-Spalten die erforderliche Suchadresse j codieren kann.

2. Inhaltsadressierbarer Speicher nach Anspruch 1, der weiterhin aufweist:

eine Schaltvorrichtung (150) mit einer Vielzahl von Schaltern (153), die jeweils ein Paar von Eingängen haben, die mit der ersten Spalte bzw. der zweiten Spalte des gleichen Paares von Spalten in der Matrix der Speicherzellen (110) verbunden sind, um so den Inhalt der Speicherzelle der ersten bzw. der zweiten Spalte jedes Paares zu empfangen, welches zu der durch die Zeilenauswahlvorrichtung (120) ausgewählten Zeile gehört, und welche den Inhalt der Speicherzellen mindestens einer Spalte der ersten und zweiten Spalte jedes Paares ausgeben kann, welches zu der Zeile gehört, die durch die Zeilenwahlvorrichtung (120) ausgewählt wurde; und

wobei der Codierer (160) den Ausgang der Schaltvorrichtung (150) einfängt und ihn in einer Adresse j (162) bei mindestens einem von Datenwort oder assoziiertem Datum codiert.

3. Inhaltsadressierbarer Speicher nach Anspruch 2, wobei die Zeilenwahlvorrichtung (120) einen Decodierer (410) enthält, der das Datenwort (101) empfängt und ein Signal ausgibt, welches die Zeile der Matrix der Speichervorrichtung (110) repräsentiert, die dein Inhalt des Datenwortes (101) entspricht u

4. Inhaltsadressierbarer Speicher nach Anspruch 1, welcher ferner aufweist:

eine Datenschreibvorrichtung (140) zum Schreiben des Datenwortes (101) in die erste Spalte des Paars von Spalten der Matrix, welche durch die Spaltenwahlvorrichtung (130) ausgewählt wurde und des Datums, welches zum Datenwort gehört, in der zweiten Spalte des Paares von Spalten, die durch die Spaltenwahlvorrichtung (130) ausgewählt wurde.

5. Inhaltsadressierbarer Speicher nach Anspruch 4, dadurch gekennzeichnet, daß die Zeilenauswahlvorrichtung aufweist:

einen Decodierer (410), der das zu suchende oder gespeicherte Datenwort (101) empfängt und das Datenwort dekodiert in Signale, die der Zeile der Speicherzellenmatrix entsprechen und die Zeilenposition der Speicherzellenmatrix darstellen, die dein Inhalt des Datenwortes entspricht;

einer Anzahl von OR-Gates (420), die jeweils zwei Eingänge haben, die jeweils das decodierte Signal bzw. ein Betriebsmodensignal empfangen, welches die Speicheroperation oder Suchoperation anzeigt.

6. Inhaltsadressierbarer Speicher nach Anspruch 5, dadurch gekennzeichnet, daß das decodierte Signal, das der Zeilenposition der Matrix entspricht, welche dein Inhalt des Datenwortes "1" entspricht, ist, während das andere dekodierte Signal "0" ist, und das Betriebsmodensignal (103) "1" ist, wenn die Speicheroperation angefordert ist, während es Null ist, wenn die Suchoperation angefordert ist.

7. Inhaltsadressierbarer Speicher nach Anspruch 4, dadurch gekennzeichnet, daß die Spaltenwahlvorrichtung (130) einen Decodierer (510) aufweist, welcher die Adresse j (162) empfängt und ein Signal ausgibt, das die Stellung des Paares von Spalten der Matrix in der Speichervorrichtung (110) repräsentiert, welche der Adresse j entspricht.

8. Inhaltsadressierbarer Speicher nach Anspruch 7, dadurch gekennzeichnet, daß die Spaltenwahlvorrichtung (130) die Eingangsadresse decodiert, um so in Antwort auf ein Spaltenwahlsignal (133) ein Signal auszugeben, welches der ersten und zweiten Spalte des Paares der Spalten in der Speicherzellenmatrix entspricht, welche der Eingangsadresse entspricht.

9. Inhaltsadressierbarer Speicher nach Anspruch 4, wobei die Spaltenwahlvorrichtung aufweist:

einen Dekoder (510) der die Adresse j als Signal höherer Ordnung und das Spaltenwahlsignal 133 als Signal mit geringster Signifikanz empfängt und diese Signale in Signale decodiert, welche den ersten oder zweiten Spalten des Paars von Spalten entspricht, die der Adresse j entsprechen, in Übereinstimmung mit der Variation des Spaltenwahlsignals (133) und

eine Vielzahl von Or-Gates (520), die jeweils den Spalten der Speicherzellen der Speichervorrichtung (110) entsprechen und die entsprechenden decodierten Signale und ein invertiertes Betriebsmode-Signal empfangen.

10. Inhaltsadressierbarer Speicher nach Anspruch 9, wobei die decodierten Signale, die die ersten und zweiten Spalten des Paares der Spalten der Matrix entsprechend der Adresse j repräsentierten "1" sind, während die andere decodierten Signale "0" sind, und das Betriebsmode-Signal (103) "1" ist, wenn die Speicheroperation angefordert ist, während es Null ist, wenn die Suchoperation angefordert ist.