DE1449765C3 - Einrichtung zur Abfrage eines assoziativen Speichers - Google Patents

Description

die erste, ganz rechts befindliche Zeichenstelle des Registers 3 durch die Schiebeimpulse transportiert wird. Zum Register 2 gehört weiter ein Masken-Zeichengeber 4, der mit der ersten Zeichenstelle so verbunden ist, daß beim Auftreten der Schiebeimpulse ein Masken-Zeichen in die erste Zeichenstelle eingeschrieben wird. Die Vorgabe-Register 2 und 3 enthalten auch die Zwischenspeicherstellen, die für Schiebeoperationen nötig sind. Die Zwischenspeicher sind in Fig. 1 nicht dargestellt; gezeigt ist lediglich die letzte Zeichenstelle des zum Vorgabe-Register 2 gehörenden Zwischenspeichers. Sie ist in F i g. 1 mit dem Bezugszeichen 9 versehen und so angelegt, daß sie danach abgefragt werden kann, ob in ihr ein FeIdgrenz-Zeichen /fa, enthalten ist.

Ehe in die Register 2 und 3 ein Vorgabewert eingetragen wird, ist dort in jeder Zeichenstelle ein Maskenzeichen enthalten. Das Vorgabe-(Feld-)Wort wird in das Register 2 so eingetragen, daß sein rechtes Feldgrenz-Zeichen (niedrigste Stelle) die erste Zeichenstelle einnimmt. Die Anordnung eines typischen Datenwortes im Speicher 1 und eines Vorgabewertes im Register 2 ist symbolisch in F i g. 5 gezeigt, bei der Maskenzeichen durch den Buchstaben M dargestellt sind. Bei der mit F i g. 1 übereinstimmenden Darstellung in Fig. 5 enthält der Speicher 1 zwei Datenworte: das erste erstreckt sich von der sechsten Zeichenstelle des Speicherwortes W₁ bis zur sechsten Zeichenstelle des Wortes W₃; das zweite Datenwort erstreckt sich von der fünften Zeichenstelle des Speicherwortes W₃ bis zur dritten Zeichenstelle des Speicherwortes W₅. In dem Beispiel haben die Speicherworte eine Länge von sechs Zeichen; in praxi sind sie von größerer Länge.

Der Vorgabewert wird in das Register 2 in üblicher Weise eingetragen; sein rechtes Feldgrenz-Zeichen kommt in die erste Zeichenstelle. Die Zeichenstellen der Register 2 und 3, die keine Zeichen oder Feldgrenz-Zeichen enthalten, sind mit Masken-Zeichen gefüllt.

Unter den.in Fig. 5 gezeigten Bedingungen möge nun der Taktgeber6 (Fig. 1) gestartet werden. Der Taktgeber wird noch ausführlicher beschrieben werden; vorläufig genügt es festzustellen, das er pro Takt fünf Impulse A, B, C, D und E erzeugt. Wenn der Taktgeber gestartet wird, beginnt er mit der Aussendung eines /4-Impulses, und nach Erhalt eines Stopp-Impulses läuft er weiter bis zur Aussendung eines Ε-Impulses, ehe er anhält. Wenn der Taktgeber nicht gestoppt wird, läuft er ununterbrochen weiter unter Aussendung der Impulse Λ, B, C, D, E, ²A, ²B, ²C, ²D, 2£ usw.

Der A -Impuls versetzt den Speicher 1 in die Vergleichs-Lage und befragt die letzte Zeichenstelle 9 des Zwischenspeichers von Register 2, um festzustellen, ob ein Feldgrenz-Zeichen dort von einer früheren Operation her enthalten ist. Mit der in Fig. 5 gezeigten Bedingung ist das nicht der Fall.

Der B-Impuls verursacht einen getrennten Br-Impuls, der die bistabilen Schaltungen im Sofort-Vergleicher 7 in den Zustand »nicht gleich« rückstellt, so daß sie bei der späteren Befragung des Speichers 1 zur Anzeige einer Übereinstimmung umgeschaltet werden können. Der ß-Impuls veranlaßt weiter, daß die im Vorgaberegister 2 enthaltene Information in den Speicherl eingelesen wird, wo sie parallel, Spalte für Spalte mit der Information im Speicher verglichen wird. Es wird z. B. das Feldgrenz-Zeichen in der ersten Zeichenstelle von Register 2 mit der Information in der ersten Zeichenstelle jedes Speicherwortes W₁ bis W_n verglichen; weiter wird die »2« der zweiten Zeichenstelle (des Registers 2) verglichen mit der Information in der zweiten Zeichenstelle jedes Speicherwortes W₁ bis W_n usw.

Die Schaltung des Speichers 1 und die Art und Weise, in welcher der Inhalt der Vorgabe-Register zum Speicher übertragen und mit dessen Inhalt verglichen wird, sowie die Art und Weise, in der die Übereinstimmung zwischen einem Speicherfeld und dem Vorgabewert aus den Registern in einer Anzeige bei den Vergleichern 7 und 8 umgewandelt wird, sind an sich bekannt und entsprechen der Arbeitsweise üblicher assoziativer Speicher. Die Beschreibung braucht sich deshalb hier nicht darauf zu erstrecken.

Unter der in F i g. 5 dargestellten Bedingung kann

also keine Übereinstimmung zwischen dem Feld im Vorgabe-Register 2 und dem zugehörigen Feld sowohl im ersten als auch im zweiten Datenwort des Speichers 1 festgestellt werden. Der nächste Impuls aus dem Taktgeber 6, der C-Impuls, der normalerweise die bistabilen Vergleichs-Schaltungen im Sofort-Vergleich-Register 7 in den Zustand »gleich« umschaltet, wird eine solche Umschaltung nicht vornehmen, da keine Gleichheit festgestellt wird.

Die nächsten beiden Impulse aus dem Taktgeber 6, mit D und E bezeichnet, verschieben den Inhalt der Register 2 und 3 um eine Zeichenstelle nach links, wie es aus F i g. 6 hervorgeht. Der Taktgeber 6 beginnt eine neue Folge von Impulsen; die Impulse ²A, '²B und ²C verursachen dasselbe Ergebnis »nicht gleich« wie es für den ersten Takt beschrieben wurde. Anschließend verschieben die Impulse ²D und ²E wieder den Inhalt der Register 2 und 3 um eine Zeichenstelle nach links, so daß sich die in Fig. 7 gezeigte Lage ergibt.

Jetzt ist das erste Feldgrenz-Zeichen in die erste Zeichenstelle des Registers 3 eingelaufen. Der Zeitpunkt, zu dem ein ursprünglich in das Register 2 eingegebenes Feldgrenz-Zeichen in das Register 3 einzulaufen beginnt, wird nachstehend als »Überlauf« bezeichnet. Der Impuls ³A des nächsten Taktes versetzt den Speicher 1 wiederum in die Vergleichs-Lage und fragt die Position 9 des Zwischenspeichers von Register 2 nach einem Feldgrenz-Zeichen ab. Mit den in F i g. 7 gezeigten Bedingungen befindet sich jetzt ein Feldgrenz-Zeichen in dieser Speicherstelle. Unter diesen veränderten Umständen ist der Arbeitsablauf ein anderer (die zugehörige Schaltung wird später beschrieben). Eine Änderung besteht darin, daß jetzt der Inhalt des Registers 3 (bisher 2) beim Auftreten des Impulses ³B in den Speicher 1 eingelesen wird. Der Impuls ³C, der den Speicher 1 nach Gleichheit abfragt, liefert unter den gegebenen Bedingungen die Anzeige »nicht gleich«. Es ist darauf hinzuweisen, daß nur die höchste Zeichenstelle des Vorgabe-Feldes im Register 3 enthalten ist und mit dem Speicher 1 verglichen wird. Da keine Übereinstimmung vorliegt, ist es unnötig, auch noch den Vergleich auf die niedrigeren Zeichenstellen des Registers 2 zu erstrecken. Mangels Gleichheit verursachen die folgenden Impulse ³D und ³E eine Verschiebung in den Registern 2 und 3; es ergibt sich die in Fig. 8 dargestellte Lage.

Die Übereinstimmung des Feldgrenz-Zeichens im Register 3 mit dem Feldgrenz-Zeichen in Wort W₂ des Speichers 1 spielt hier keine Rolle, weil nur das Feldgrenz-Zeichen selbst vorhanden ist.

Nun befindet sich das Zeichen »9« des Vorgabewertes in der äußersten rechten Zeichenstelle von Register 3. Während des nächsten Taktes bringt der Impuls M den Speicher 1 in die Vergleichs-Lage und befragt die letzte Zeichenstelle9 des Vorgaberegisters 2 nach einem Feldgrenz-Zeichen. Ein solches FeIdgrenz-Zeichen war beim vorhergehenden Takt in dieser Zeichenstelle vorhanden und verursachte den »Überlauf«. Der »Überlauf«-Zustand bleibt erhalten bis ein zweites Feldgrenz-Zeichen in der Zeichenstelle 9 des Zwischenspeichers erscheint und damit anzeigt, daß der Vorgabewert vollständig im Register 3 enthalten ist. Der Impuls ⁴B liest den Inhalt des Registers 3 in den Speicher 1 ein. Der Impuls ⁴C bewirkt die Abfrage nach dem Vergleichsergebnis; mit dem in F i g. 8 gegebenen Zustand ist der Vergleich negativ. Es ist zu beachten, daß zwar das Zeichen »9« in der ersten Zeichenstelle von Register 3 mit dem Zeichen »9« in der ersten Ziffernstelle des Speicherwortes W₃ übereinstimmt, daß aber keine Übereinstimmung besteht zwischen dem Feldgrenz-Zeichen in der zweiten Zeichenstelle von Register 3 mit irgendeiner zweiten Zeichenstelle von Speicherwörtern. Deshalb verursacht der Impuls ⁴C die Anzeige »nicht gleich«, und die Impulse ⁴D und ⁴E verursachen in den Registern 2 und 3 eine Verschiebung zu dem in F i g. 9 gezeigten Zustand.

Der Impuls M versetzt den Speicher 1 wieder in die Vergleichs-Lage, und der Impuls ⁵B liest den Inhalt des Registers 3 in den Speicher 1. Nun besteht die Übereinstimmung zwischen dem Inhalt des Registers 3 und den ersten drei Zeichenstellen des Speicherwortes W₁; nur das Speicherwort W₁ liefert also die Anzeige »gleich«. Der Impuls ⁵C fragt den Speicher 1 nach dem Vergleichsergebnis ab und stellt die Gleichheit für das Wort W₁ fest. Die Gleichheit betrifft nicht den ganzen Vorgabewert, sondern nur die ersten drei Zeichenstellen »φ.95« des Feldes im Register 3. Diese Übereinstimmung wird im Sofort-Vergleicher 7 gespeichert. Die niedrigen Zeichen »2« und A^. des Vorgabewertes befinden sich noch im Register 2 und dieses muß jetzt noch mit dem Speicher 1 in Beziehung gebracht werden. Die Schiebeimpulse ⁵D und ⁵E werden nun gesperrt, um die Zeichenstellen für die Zeichen »2« und ζφ> nicht zu stören.

Der Impuls ⁶A des nächsten Taktes bringt wiederum den Speicher in die Vergleichs-Lage. Dieser Vorgang beeinflußt die Vergleichsanzeige des Sofort-Vergleichers 7 nicht. Die Vergleicher 7 und 8 werden nur durch einen besonders erzeugten Impuls Br oder durch eine andere Bedingung zurückgestellt.

Beim Auftreten des Impulses ⁶B wird der Inhalt des Registers 2 in den Speicher 1 zwecks Vergleich eingelesen. Dieses Mal liegt Gleichheit während des Abfrageimpulses vor, und die ansprechende Anzeige gelangt zum Folge-Vergleich 8. Ein Signal aus dem letzteren zeigt die vorgefundene Gleichheit an und dient auch zum Anhalten des Taktgebers nach dem Impuls ⁰E; es muß jetzt das Auslesen des übereinstimmenden Wortes aus dem Speicher stattfinden.

Diese Speicherentnahme kann in an sich bekannter Weise geschehen. In F i g. 1 ist die dafür vorgesehene Anordnung durch den Block 8 a dargestellt. Das Entnahme-Signal erscheint zur Zeit des Impulses ⁶C, ebenso das Stoppsignal für den Taktgeber 6. Dieser läuft zwar weiter bis zum Impuls ⁶E, die Impulse ⁰D und ⁰E haben jedoch auf das Entnahme-Signal keinen Einfluß mehr. Der Zustand der Register 2 und 3 nach dem Auftreten des Impulses ⁶E ist in Fig. 10 dargestellt.

Der Taktgeber 6 startet von neuem und der Speicher 1 wird durch den Impuls ⁷A zurückgestellt, der Inhalt des Registers 3 wird mit den Speicherwörtern beim Auftreten des Impulses ⁷B verglichen, der Impuls ⁷C zeigt die Bedingung »nicht gleich« an, und die Impulse ⁷D und ⁷E verschieben den Inhalt der Register 2 und 3 zu der in Fig. 11 gezeigten Lage. Diescr Figur ist zu entnehmen, daß das zweite Feldgrenz-Zeichen in der letzten Zeichenstelle 9 des Zwischenspeichers enthalten sein muß. Dieser Zustand wird beim Auftreten des Taktimpulses M festgestellt, und er hat den Stopp des Taktgebers 6 (nach dem Auftreten des Impulses ⁸E) zur Folge und zeigt an, daß der Vergleich mit dem derzeitigen Vorgabewert vollendet ist. Weiter wird ein Rückstellimpuls erzeugt, der die Steuerschaltung 5 zurückstellt. Die Anordnung ist nun in der Lage, einen neuen Vorgabewert zu einem weiteren Vergleich aufzunehmen.

Bei der bisherigen Betrachtung der Anordnung war »Überlauf« notwendig, bevor eine Übereinstimmung angezeigt werden konnte. Natürlich kann das im Speicher 1 befindliche Feld, dessen Übereinstimmung festgestellt werden soll, auch gänzlich in einem Speicherwort enthalten sein, z. B. das Feld ^ 608 <φ. im Speicherwort W₂ der Fig. 5. In diesem Falle kann die Übereinstimmung beim ersten Takt festgestellt werden, und das Erscheinen des »Überlaufs« ist nicht nötig. Die Schaltung ist so eingerichtet, daß ein Entnahme-Vorgang nach Übereinstimmung jederzeit stattfinden kann, nachdem der Sofort-Vergleich vollständig aufgetreten ist, auch wenn kein »Überlauf« auftrat. Nach dem Auftreten eines »Überlaufs« kann jedoch nur der Folge-Vergleich einen Entnahme-Vorgang herbeiführen.

Bisher wurde die Arbeitsweise der Anordnung in allgemeinen Ausdrücken besprochen, nun soll eine eingehende Erläuterung der Arbeitsweise der einzelnen Schaltungen folgen.

F i g. 2 zeigt Einzelheiten des Taktgebers 6 für die Register 2 und 3. Ein Impuls-Generator 10 erzeugt in zyklischer Folge die vorher schon besprochenen fünf Impulse A, B, C, D, E. Der Impuls A erscheint auf Leitung 11 und dient (über Leitung 12) zur Herstellung der Vergleichs-Lage im Speicher 1 und (über Leitung 13) zur Abfrage der letzten Zeichenstelle 9 des Zwischenspeichers in Fig. 1. Der Impuls B erscheint auf Leitung 14 und dient als »Lese«-Strom zum Einlesen des Inhalts von Register 2 oder 3 in den Speicher 1 über die Leitung 15. Der Impuls B dient weiter als je ein Eingang zu den UND-Schaltungen 16 und 17; als weitere Eingänge dienen das Signal »Wahl-Register 3« auf Leitung 18 für die UND-Schaltung 16 und das Signal »vor Überlauf« auf Leitung 19 für die UND-Schaltung 17. Die Signale auf den Leitungen 18 und 19 kommen aus der Steuerschaltung 5 von F i g. 1, die noch besprochen wird. Die Ausgangssignale der UND-Schaltungen 16 und 17 bilden hinter der ODER-Schaltung 20 den Impuls »Br« auf Leitung 21, welcher zur Rückstellung der bistabilen Schaltungen im Sofort-Vergleicher 7, im Folge-Vergleicher 8 und in der Steuerschaltung 5 dient. Der Impuls Br ist nur dann nicht vorhanden, wenn ein Überlauf stattgefunden hat, das Vorgabe-Register 3 verglichen worden ist und der Inhalt des Vorgabe-Registers 2 in den Speicher 1 eingelesen wird. Der Impuls Br ist dann unerwünscht,

da die Rückstellung der bistabilen Schaltungen die gespeicherten Übereinstimmungs-Ergebnisse beseitigen würde, die durch Vergleich mit dem Vorgabe-Register 3 erlangt wurden.

Der Impuls C erscheint auf Leitung 22 (Fig. 2) und prüft im Sofort-Vergleicher 7 der Fig. 1 auf Übereinstimmung. Der Impuls D auf Leitung 23 wird den UND-Schaltungen 24 und 25 zugeführt, deren Ausgangssignale hinter der ODER-Schaltung 26 über Leitung 27 zu den Vorgabe-Registern 2 und 3 zur Verschiebung des Inhaltes dieser Register in ihre Zwischenspeicher dient. Der Impuls E auf Leitung 28 gelangt zu den UND-Schaltungen 29 und 30, deren Ausgangssignal hinter der ODER-Schaltung 31 den Inhalt der Zwischenspeicher wieder in die folgende Stelle der Vorgabe-Register 2 und 3 verschiebt. Die jeweils zweiten Eingänge der UND-Schaltungen 24 und 29 stammen aus der Steuerschaltung5 der Fig. 1 und führen den Impuls »Wahl-Register 2«. Die weiteren Eingänge der UND-Schaltungen 25 und 30 sind einerseits das Signal »Wahl-Register 3« auf Leitung 18 und andererseits »nicht gleich« auf Leitung 34 aus der Steuerschaltung 5. Dadurch ist sichergestellt, daß eine Schiebc-Operation stattfindet, wenn eines der Register 2 oder 3 ausgelesen und Ungleichheit festgestellt wurde. Eine Stellenverschiebung ist nur dann nicht erwünscht, wenn nach einem Überlauf der Inhalt des Registers 3 ein positives Vergleichsergebnis liefert. Dann muß der Inhalt des Registers 2 ohne vorherige Verschiebung in den Speicher 1 eingelesen werden. Es besteht dann ein Signal »Wahl-Register 3« auf Leitung 18, aber keine Signale auf den Leitungen 33 und 34. Die Impulse D und E sind dann durch die UND-Schaltungen 24, 25, 29 und 30 gesperrt und eine Stellenverschiebung unterbleibt.

Zum Anhalten des Taktgebers 10 dient die Leitung 36, die vom Folge-Vergleicher kommt und bei einem positiven Vergleichsergebnis den Taktgeber nach dem Impuls E anhält, um das Auslesen des übereinstimmenden Wortes zu ermöglichen. Die Startleitung 35 kommt von der Entnahmeschaltung, so daß ein Impuls aus dieser Schaltung den Taktgeber starten kann, sobald feststeht, daß keine weitere Übereinstimmung bei der gegebenen Verschiebe-Lage der Register 2 und 3 vorliegt. Einzelheiten dieser Entnahmeschaltung (8a, Fig. 1) sind für die vorliegende Erfindung ohne Bedeutung.

Die Steuerschaltung 5 von F i g. 1 ist in F i g. 3 in größerer Ausführlichkeit gezeigt. Vor einem Vergleichsvorgang sind die verschiedenen bistabilen Schaltungen rückgestellt. Die Schaltung 37 liefert dabei das Signal »vor Überlauf« zur Leitung 19 und »kein Signal« zur UND-Schaltung 43. Die bistabile Schaltung 38 liefert »kein Signal« zur UND-Schaltung 39; die Schaltung 40 liefert »kein Signal« zur UND-Schaltung 41, und die Schaltung 42 liefert ein Signal »Wahl-Register 2« auf Leitung 33.

Die Steuerschaltung5 der Fig. 3 liefert nun die Signale für den erstmaligen Vergleichsvorgang, d. h. für die Zeit vor dem Überlauf, wenn nur der Inhalt des Vorgabe-Registers 2 in Beziehung gesetzt wird. Während der Takte vor dem Überlauf gelangen die Impulse/1 aus dem Taktgeber 10 (Fig. 2) als Eingangssignale zur Leitung 13 und die Impulse B zur Leitung 15. Sie können jedoch zu dieser Zeit die UND-Schaltungen 43, 46 mangels weiterer Eingangssignale nicht passieren.

In dem Takt nach dem Überlauf gelangt der Impuls A zur letzten Zeichenstelle 9 des Zwischenspeichers von Register2 (Fig. 1). Die Anwesenheit des ersten Feldgrenz-Zeichens in dieser Stelle erzeugt auf Leitung 47 ein Signal (»nach Überlauf«). Der Impuls A auf Leitung 13 (F i g. 3) ist von solcher Dauer, daß er noch an der UND-Schaltung 43 anliegt, wenn das Signal »nach Überlauf« über Leitung 47 die bistabile Schaltung 37 umgeschaltet und zur UND-Schaltung 43 gelangt ist. Das Ausgangssignal dieser ίο UND-Schaltung passiert auch die UND-Schaltung 48, da zu dieser Zeit die UND-Schaltung 49 nicht durchlässig ist und der Inverter 50 dazwischenliegt. Die UND-Schaltung 48 schaltet die bistabile Schaltung 42 um, so daß auf Leitung 18 das Signal »Wahl-Register 3« entsteht. Auf diese Weise wird das Register 3 beim Vorliegen eines Überlaufs vor dem Register 2 gelesen. Beim Umschalten der bistabilen Schaltung 37 entsteht auf Leitung 51 das Signal »nach Überlauf«, und das Signal auf Leitung 19 verao schwindet.

Wenn der Impuls B auf Leitung 15 erscheint, kann er die UND-Schaltung 46 passieren, da jetzt von Schaltung 42 ein Signal vorliegt. Die UND-Schaltung 46 schaltet die bistabile Schaltung 38 um, so daß die UND-Schaltung 39 beim nächsten Auftreten eines Signals »nach Überlauf« (von 52) durchlässig wird. Der nächste Impuls »nach Überlauf« während des Taktes »Wahl-Register 3« zeigt an, daß das ganze Feld in Vorgabe-Register 3 enthalten ist und daß die Vergleichsvorgänge beendet werden können. Dieser Impuls wird dann die UND-Schaltungen 52 und 59 passieren können und die bistabile Schaltung 40 umschalten, so daß der Impuls E auf Leitung 32 danach die UND-Schaltung 41 passieren kann und über Leitung 36 zum Taktgeber 10 einen Stopp-Impuls liefert. Die UND-Schaltung 52 stellt sicher, daß ein Stopp-Impuls nur am Ende eines Taktes »Wahl-Register 3« entstehen kann.

Das Verzögerungselement 45 ist der UND-Schaltung 52 vorgeschaltet, um jeden Irrtum unmittelbar nach einem Überlauf zu vermeiden, d. h., wenn das erste Feldgrenz-Zeichen des Vorgabewertes in der ersten Weichenstelle von Register 3 steht. (Dieses erste Feldgrenz-Zeichen wird dann auch in die letzte Zeichenstelle 9 des Zwischenspeichers eingegeben.) Wenn der Impuls »nach Überlauf« an der UND-Schaltung 52 eintrifft, bevor der Impuls A (Leitung 13) die UND-Schaltungen 43 und 48 passiert und die bistabile Schaltung 42 umgeschaltet und das Signal von Leitung 18 entfernt hat, dann könnte ein falsches Signal die UND-Schaltung 52 passieren, was schließlich während des Impulses E zu einem Stopp-Signal führen würde. Um diese Möglichkeit zu vermeiden, ist die Verzögerung 45 eingeschaltet. Die bistabile Schaltung 54 ermöglicht es, das Vorgabe-Register 2 beim Vorliegen einer Übereinstimmung unmittelbar nach dem Vorgabe-Register 3 zu lesen. Der Impuls Br auf Leitung 21 (vom Taktgeber kommend) bringt die Schaltung normalerweise in den Zustand »nicht gleich«. Das bedeutet, daß auf Leitung 55 ein Signal ansteht und daß die UND-Schaltung 49 vorbereitet ist. Dadurch ist für die Dauer eines Signals »Wahl-Register 3« die Schaltung 49 durchlässig und hinter dem Inverter 50 die UND-Schaltung 48 gesperrt, so daß kein Impuls A über die UND-Schaltung 43 zur bistabilen Schaltung 42 gelangen kann. Die Folge ist, daß nach dem Überlauf und solange keine Übereinstimmung vorliegt, nur das

409 534/303

Register 3 gelesen wird. Beim Auftreten einer Übereinstimmung soll dann das Vorgabe-Register 2 gelesen werden. Das Signal »gleich« auf Leitung 53 aus der Folge-Vergleichs-Schaltung 3 der F i g. 1 schaltet dann die bistabile Schaltung 54 um und beseitigt das Signal »nicht gleich« von den Leitungen 55 und 34. Für die Leitung 34 wurde dieser Zustand schon in Verbindung mit F i g. 2 besprochen. Das Entfernen des Signals »nicht gleich« von Leitung 55 sperrt die UND-Schaltung 49, so daß der nächste Impuls A die UND-Schaltung 48 passieren und die bistabile Schaltung 42 umschalten kann; es entsteht dann das Signal »Wahl-Register 2«, und der Inhalt des Vorgabe-Registers 2 wird mit dem Speicherinhalt verglichen. Dieser Zustand kann nur nach einem Überlauf eintreten, wenn Übereinstimmung mit dem Inhalt des Vorgabe-Registers 3 vorgefunden wurde.

Die F i g. 4 zeigt Einzelheiten des Sofort-Vergleichers 7 (linke Hälfte) und des Folge-Vergleichers 8 (rechte Hälfte) von F i g. 1. Die Eingangsleitungen 60-1, 60-2 ... 60-(/i-l), 60-/1 sind die Ausgangsleitungen vom Speicher 1 (Fig. 1), die zu den Speicherwörtern W₁, W₂.. .W_n gehören. Ein Signal auf einer dieser Leitungen zeigt an, daß Übereinstimmung zwischen dem Inhalt eines Vorgabe-Registers und dem Inhalt des zugehörigen Speicherwortes vorliegt. Die Eingangsleitungen führen zu den Eingängen von UND-Schaltungsgruppen. Leitung 33 (Signal »Wahl-Register 2«), Leitung 18 (Signal »Wahl-Register 3«) und Leitung 19 (Signal »vor Überlauf«) aus F i g. 3 führen zu bestimmten UND-Schaltungen der Gruppen.

Die zwei möglichen Wege, auf denen eine vollkommene Übereinstimmung eintreten kann, sind erstens: ein vollständiges Feld in einem einzigen Speicherwort zeigt Übereinstimmung mit dem Vorgabewort in Register 2 vor Eintritt des Überlaufs; zweitens: die Zeichen höhrerer Ordnung des Vorgabewortes in Register 3 zeigen Übereinstimmung mit einem Teil eines Feldes in einem Speicherwort nach Eintritt des Überlaufs, gefolgt von einer Übereinstimmung der Zeichen niedriger Ordnung in Register 2 mit dem restlichen Teil des Feldes in einem Speicherwort, das den Speicherwörtern mit einem Zeichen höherer Ordnung benachbart ist.

Der erste Fall soll zusammen mit F i g. 4 betrachtet werden. Ein vollkommen im Speicherwort W₂ enthaltenes Wort stimmt mit dem Vorgabewort in Register 2 vor Eintreten des Überlaufs überein. Es wird dann über Leitung 60-2 an je einem Eingang der UND-Schaltungen 63, 64 und 65 ein Signal erscheinen. Da noch kein Überlauf vorliegt, führt die Leitung 19 das Signal »vor Überlauf«, und da das Register 2 im Spiel ist, wird die Leitung 33 ein Signal »Wahl-Register 2« führen; die UND-Schaltung 64 wird durchlässig und liefert ein Signal über die ODER-Schaltung 72 zur UND-Schaltung 76. Mit einem Impuls C auf Leitung 22 wird die UND-Schaltung 76 durchlässig und stellt die bistabile Schaltung 82 um. Auf Leitung 86 erscheint ein Signal. Durch einen Impuls Br wurden vorher die bistabilen Schaltungen 81, 82, 83 und 84 rückgestellt, so daß auf den Leitungen 85, 86, 88 und 90 kein Signal ansteht.

Das nun auf Leitung 86 erscheinende Signal passiert die ODER-Schaltung 92 des Folge-Vergleichers 8 und läuft über Leitung 53 zur bistabilen Schaltung 54 der Fig. 2, wie vorher beschrieben. Da an der UND-Schaltung 93 schon das Signal »vor Überlauf« von Leitung 19 anliegt, gelangt ein Signal über die ODER-Schaltung 94 als Stopp-Signal zum Taktgeber 10 über die Leitung 36. Das Signal auf Leitung 36 wird außerdem der Entnahmeschaltung 8a zur Anzeige des beendeten Vergleichsvorganges zugeleitet. Falls der Vergleichsvorgang gegenüber einem anderen Speicherwort als W₂ positiv verläuft, erscheint auf einem anderen der Leiter 60-1 bis 60-n ein Signal. Ergibt sich Gleichheit zwischen einem Zeichen höherer Ordnung in Register 3 und einem Zeichen in

ίο einem Speicherwort nach dem Überlauf, so erscheint zunächst auch ein Signal auf z. B. der Leitung 60-2. Da der Überlauf stattgefunden hat, besteht das Signal »Wahl-Register 3« auf Leitung 18, aber keine Signale auf den Leitungen 33 oder 19. Es wird also jetzt die UND-Schaltung 65 durchlässig, so daß mittels der ODER-Schaltung 72 und eines Impulses C die UND-Schaltung 76 geöffnet und die bistabile Schaltung 82 umgeschaltet werden kann. Das resultierende Signal auf der Leitung 86 passiert die ODER-Schaltung 92; die UND-Schaltung 93 ist jedoch gesperrt, da das Signal »vor Überlauf« auf Leitung 19 fehlt. Die ODER-Schaltung 94 kann deshalb über Leitung 36 den Taktgeber nicht anhalten. Über Leitung 53 wird jedoch die bistabile Schaltung 54 (F i g. 3) umgeschaltet; sie verursacht beim nächsten Impuls A das Signal »Wahl-Register 2« und damit den Vergleich der Vorgabezeichen aus dem Register 2 mit den Zeichen des benachbarten Speicherwortes. Wenn nämlich ein Feld im Speicher aufgeteilt ist, sg befindet sich ein Teil zwangläufig im benachbarten Speicherwort. Es muß jedoch sichergestellt sein, daß Übereinstimmung nur auftreten darf, wenn sie im Zusammenhang mit dem nächstbenachbarten Speicherwort eintritt. Das geschieht (im Beispiel) durch das Signal auf Leitung 86 der Fig. 4. Außer zu der ODER-Schaltung 92 gelangt dieses Signal noch zu der UND-Schaltung 66, die (im Beispiel) dem folgenden Speicherwort W_n-1 zugeordnet ist. Ergibt sich also eine Übereinstimmung zwischen Zeichen im Speicherwort W_n __t und den Zeichen niedrigerer Ordnung im Register 2, dann entsteht ein Signal auf Leitung 60-(«-l), das den UND-Schaltungen 66, 67 und 68 zugeführt wird. Da das Register 2 nach dem Überlauf gelesen wurde, wird ein Signal auf Leitung 33, aber keine Signale auf den Leitungen 18 und 19 zur Verfügung stehen. Es wird also die UND-Schaltung 66 durchlässig. | Beim Auftreten des nächsten Impulses C wird die j UND-Schaltung 77 ein Ausgangssignal zur Umschal- ! tung der bistabilen Schaltung 96 liefern. Es ist zu be- \

achten, daß die bistabilen Schaltungen 95, 96 und 97 j normalerweise kein Ausgangssignal liefern, da sie über Leitung 21 von dem Impuls Br rückgestellt sind. Nach der Umschaltung von 96 gelangt also ein Signal zur ODER-Schaltung 98, das zur UND-Schaltung 99 weiterläuft. Da ein Überlauf stattfand, führt die Leitung 51 ein Signal, die UND-Schaltung 99 ist durchlässig, und hinter der ODER-Schaltung 94 entsteht auf Leitung 96 die Anzeige für den beendeten Vergleich und ein Stopp-Signal für den Taktgeber.

Läßt sich keine Gleichheit mit einem Speicherwort feststellen, so wird auf keinen der Eingangsleiter 60-1 bis 60-/J ein Signal erscheinen, und die Schaltung der Fig. 4 wird nicht arbeiten. Wenn der Sofort-Vergleich ein positives Ergebnis zwischen den Vorgabewerten höherer Ordnung im Register 3 nach Überlauf ergibt, so wird die Schaltung 4, wie oben beschrieben, arbeiten, d. h., die Gleichheit wird angezeigt werden, und das Signal auf Leitung 53 wird das Signal »Wahl-

Register 2« in der Schaltung der F i g. 3 zur Folge haben. Ist bei dem Folge-Vergleich zwischen den Zeichen niedrigerer Ordnung im Register 2 keine Übereinstimmung feststellbar, dann ergibt sich kein Signal »gleich« aus dem benachbarten Speicherwort und kein Eingangssignal auf dem benachbarten Eingangsdraht (60), und die Ausgangsleitung 36 (F i g. 4) kann kein Signal abgeben; der Taktgeber läuft weiter und verschiebt den Vorgabewert in den Registern zu neuen Vergleichs-Vorgängen.

Sobald das gewünschte Feld im Speicher festgestellt wurde, muß das ganze Datenwort, welches dieses Feld enthält, ausgelesen werden. Das kann mit bekannten Schaltungen geschehen, da das Datenwort durch Anfangs- und Endmarkierungen eingegrenzt ist.

Die bisherige Beschreibung betrifft eine Assoziativspeicheranordnung, in dem Wörter variabler Länge miteinander in Beziehung gesetzt werden können und

in dem in den Datenwörtern enthaltene Felder Zeichenstellen in mehr als einem Speicherwort einnehmen können. Die Grundsätze der vorliegenden Erfindung können auf Speicheranordnungen mit z. B. supraleitenden Elementen oder Magnetkernen usw. angewendet werden.

Im beschriebenen Ausführungsbeispiel befinden sich die aufeinander zu beziehenden oder zu vergleichenden Felder in zwei aufeinanderfolgenden Speicherwörtern, und die Einrichtung enthält nur ein Überlauf-Register 3. Sollten für besondere Fälle die zu vergleichenden Felder von solcher Länge sein, daß sie drei oder mehr Speicherwörter überdecken, dann sind zwei oder mehr zusätzliche Überlauf-Register nötig. Als allgemeine Regel gilt, daß die Gesamtzahl der vSpeicherwörter, in denen sich ein betrachtetes Feld befindet, gleich der Gesamtzahl der Register sein muß.

Hierzu 4 Blatt Zeichnungen

Claims (1)

1. Der Nachteil eines solchen Speichers besteht jedoch Patentansprüche: _{darjn; daß ejn oder mehrere Fe}i_{der au}f_{getrennt sind}

   I Hinrichtung zur Abfrage eines assoziativen und in mehr als einem Speicherwort auftreten und

   S'-eicrjsrs mit Folge/Sofort-Vergleichern und mit daß deshalb das Prinzip des assoziativen Speichers

   zu2-i:cdnetem Suchregister, in dem das Suchwort 5 bisher bei variabler Wortlänge nicht angewandt wer-

   τηίί Fddgrenzzeichen steht, sowie mit in Speicher- den konnte.

   _WCra gleicher Länge angeordneten Speicher- Durch die vorliegende Erfindung soll dieser Man-

   eleTT.e^ien zur Speicherung von Datenworten gel behoben werden und der Vorteil des assoziativen

   variabler Länge, deren Anfang und Ende mar- Speichers auch bei Verwendung variabler Wortlänge

   kien sind, d a durch ge ken nzeichn et, daß io erhalten bleiben.

   minö±stens zwei Vorgaberegister (2 und 3) ange- Die erfindungsgemäße Lösung der Aufgabe besteht

   ordne: sind, die als Schieberegister ausgebildet darin, daß mindestens zwei Vorgaberegister angeord-

   UTiC kaskadenartig verbunden sind. net sind, die als Schieberegister ausgebildet und

   I. Einrichtung nach Anspruch 1, dadurch ge- kaskadenartig verbunden sind.

   kenr_zeichnct, daß zur Speicherung des Feldgrenz- 15 F i g. 1 ist ein Blockdiagramm des erfindungs-

   zeichens zwischen den beiden Vorgaberegistern gemäßen assoziativen Speichers;

   (2 ur.d 3) eine weitere Speicherstelle (9) angeord- Fig. 2 zeigt schematisch den in Fig. 1 verwende-

   net is.'. ^ten Taktgeber;

   F i g. 3 zeigt schematisch eine Steuerschaltung von 20 F i g. 1;

   F i g. 4 zeigt Schaltungen für den Sofortvergleich und den Folgevergleich aus Fig. 1;

   F i g. 5 bis 11 sind verschiedene Symboldarstellungen von Speicher- und Vorgabe-Registern der Fig. 1.

   Die Erfindung betrifft eine Einrichtung zur Abfrage 25 Die F i g. 1 zeigt in Blockform die neuartige eines assoziativen Speichers mit Folge/Sofort-Verglei- Assoziativspeicheranordnung mit einem Speicher 1 ehern und mit zugeordnetem Suchregister, in dem das von variabler Wortlänge, einem ersten und zweiten Suchwort mit Feldgrenzzeichen steht, sowie mit in Vorgabe-Register 2 bzw. 3, einem Masken-Zeichen-Speicherworten gleicher Länge angeordneten Spei- geber 4 zur Eingabe von Maskenzeichen in das Vorcherelementen zur Speicherung von Datenworten 30 gabe-Register 2, einer Steuerschaltung 5, einem Taktvariabler Länge, deren Anfang und Ende markiert geber 6, und mit Schaltungen 7 und 8 für Sofortsind, vergleich bzw. Folgevergleich.

   Ein üblicher assoziativer Speicher besteht im Der Speicher 1 ist eine übliche Speicheranordnung

   wesentlichen aus matrixartig angeordneten Speicher- mit Magnetkernen, Supraleitern od. dgl. Er enthält

   elementen; die in einer Zeile angeordneten Speicher- 35 mehrere Zeilen W₁ bis W_n zur Aufnahme von Daten,

   elemente werden als Speicherwort bezeichnet, sie Die Zeilen W_x bis W_n werden als Speicherworte be-

   können ein Datenwort aufnehmen. Weiter gehört ein zeichnet. Jedes Speicherwort enthält mehrere Zei-

   Register zur Aufnahme des Vergleichswertes, das chenstellen, die mit 1 bis m bezeichnet sind und aus

   Vorgaberegister, dazu und Einrichtungen zum gleich- je 6 Bits bestehen. Die Speicherworte W_x bis W₁₁

   zeitigen Vergleich des Inhalts des Vorgaberegisters 4° haben feste Länge und Lage. Die im Speicher 1 ent-

   mit dem gesamten Inhalt des Speichers. Beim Ver- haltene Information hat die Form von Datenworten

   gleich des Inhalts des Vorgaberegisters mit dem In- aus einem oder mehreren Feldern. Der Beginn jedes

   halt des Speichers werden alle Worte im Speicher Datenwortes wird durch das Sonderzeichen φ mar-

   nach Übereinstimmung mit dem Vorgabewort unter- kiert. Das Ende jedes Datenwortes ist durch das

   sucht, und alle Worte, welche übereinstimmen, werden 45 Zeichen φ gekennzeichnet. Anfang und Ende eines

   bei einer Operation festgestellt. Feldes innerhalb eines Datenwortes wird durch das

   Es ist sehr gebräuchlich, die Datenworte in »Fei- Zeichen/^ markiert.

   der« aufzuteilen. Ein typisches Beispiel: Ein Daten- Bei der vorliegenden Erfindung können die Datenwort, das sich auf einen bestimmten Angestellten be- worte mehr als ein Speicherwort einnehmen, und ein zieht, kann mehrere Felder enthalten, die den Namen, 50 oder mehr Felder können in verschiedenen Speicherdie Berufsbezeichnung, den Stundenverdienst, die Worten beginnen oder enden. Ein Datenwort kann Personalnummer usw. bezeichnen; diese Felder sind z. B. bei der Stelle m von W, beginnen und bei der durch einzelne Bits getrennt, welche die Grenzen der Stelle 4 von W₃ enden; dabei kann ein Feld in W₁ Felder festlegen. Durch Eintragen der Personalnum- beginnen und in W₂ enden. Wenn ein Vorgabefeld in mer in das Vorgaberegister und Vergleich mit den 55 ein übliches Vorgaberegister zum parallelen, spalten-Speicherworten kann das Auslesen des ganzen Daten- weisen Vergleich mit den Feldern der Speicherworte wortes des Angestellten bewirkt werden. Die Daten- eingeführt wird, so kann sich natürlich nie Übereinworte im Speicher brauchen jedoch nicht notwen- Stimmung ergeben, wenn das an sich übereinstimdigerweise dieselbe Länge wie die Speicherworte zu mende Feld im Speicher aufgeteilt und in mehr als haben. In diesem Falle hat es sich als zweckmäßig 60 einem Speicherwort untergebracht ist.
   erwiesen, ein Datenwort unmittelbar nach dem Ende Das System der F i g. 1 enthält nun ein erstes Vordes vorhergehenden Datenwortes beginnen zu lassen. gabe-Register 2 und ein zweites Vorgabe-Register 3. Wenn jedes Datenwort an der Zeichenstelle beginnt, Beide Vorgabe-Register 2 und 3 sind Schieberegister, die sich an das Ende des vorhergehenden Daten- die ein in ihnen enthaltenes Zeichen nach Zufuhr von wortes anschließt, statt mit dem Beginn eines neuen 65 zwei Schiebeimpulsen um je eine Stelle nach links Speicherwortes zusammenzufallen, kann die Speicher- verschieben. Die beiden Register sind so verbunden kapazität besser ausgenutzt werden. Man spricht daß die in der letzten, ganz links befindlichen Zeidar.n von einem Speicher für variable Wortlänge. chenstelle des Registers 2 enthaltene Information ir