DE1774607C3 - Speicheranordnung mit einem informationszerstörend lesbaren Speicher - Google Patents

Description

Die Erfindung betrifft eine Speicheranordnung mit einem informationszerstörend lesbaren Speicher, dessen Speicherplätze jeweils ein Wort aufnehmen, mit einer die Speicherplätze in einer vorbestimmten Reihenfolge jeweils in Abhängigkeit von einem ersten Weiterschaltsignal ansteuernden Einrichtung, mit einem Ausgangsregister zur Aufnahme eines aus dem Speicher ausgelesenen Wortes, mit einem Register zum Speichern eines gesuchten Wortes als Bezugswort und mit

b5 einer Einrichtung zum Vergleichen des Inhalts des Bezugswortregisters mit dem Speicherinhalt.

Eine Speicheranordnung dieser Art enthält in der Regel einen Kernspeicher. Bislang werden bei derarti-

gen Speicheranordnungen nacheinander so viele Wörter ausgelesen und mit dem Bezugs- bzw. Suchwort verglichen, bis das gesuchte Wort ermittelt ist Wenn ein Wort durch das nicht zerstörungsfreie Auslesen im Speicher gelöscht wird, aber dennoch am ursprünglichen Speicherplatz gespeichert bleibt η soll, was zumindest dann der Fall ist, wenn es sich nicht um das gesuchte Wort handelt, muß nach dem Lesen die ursprüngliche Information wieder eingespeichert werden. Dieses bei allen ausgelesenen Wörtern, die nicht mit dem gesuchten übereinstimmen, erforderliche Wiedereinspeichern erhöht die Suchzeit erheblich.

Sodann ist eine assoziative Speicheranordnung bekannt (Zeitschrift »Frequenz«, März 1966, Seiten 69 bis 82), bei der ein gesuchtes Wort in einem einzigen Zugriffzyklus aus dem assoziativen Speicher ausgelesen werden kann. Dies ist dadurch möglich, daß jedem Speicherplatz ein eigener Vergleicher zugeordnet ist, so daß der Inhalt aller Bit-Speicherelemente gleichzeitig mit allen Bits des Suchwortes verglichen werden kann. Dies ergibt eine sehr kurze Zugriffszeit, stellt jedoch einen sehr großen Aufwand an Vergleichern dar. Der Aufwand an Vergleichern, die zudem jeweils mehrere Bits erfassen müßten, steigt proportional mit der Anzahl der Speicherplätze (der zu speichernden Stichwörter). Hinzu kommt, daß das Auslesen der Bitelemente grundsätzlich zerstörungsfrei sein muß, da ein gleichzeitiges Zurückspeichern in sämtliche Plätze völlig ausgeschlossen ist Zerstörungsfrei auslesbare Speicher sind jedoch wesentlich aufwendiger als nicht zerstörungsfrei auslesbare Speicher.

Der Erfindung liegt die Aufgabe zugrunde, eine Speicheranordnung der eingangs genannten Art anzugeben, bei der ein Suchvorgang in kürzerer Zeit abgeschlossen werden kann.

Nach der Erfindung ist diese Aufgabe dadurch gelöst, daß eine die Bitspeicherelemente in einer vorbestimmten Reihenfolge jeweils in Abhängigkeit von einem zweiten Weiterschaltsignal ansteuernde Bitfolgesteuereinrichtung vergesehen ist, so daß nur das Bit im angesteuerten Bitspeicherelement des angesteuerten Wortspeicherplatzes in das Ausgangsregister übertragbar ist, daß die Vergleichseinrichtung eine an die Ausgänge des Ausgangsregisters über ein ODER-Gatter und an einen Ausgang des als Schieberegister ausgebildeten Bezugswortregisters, dem das zweite Weiterschaltsignal als Schiebesignal zuführbar ist, angeschlossene Ein-Bit-Vergleichsvorrichtung aufweist, daß die Ein-Bit-Vergleichsvorrichtung das erste Weiterschaltsignal, das zweite Weiterschaltsignal, ein das NichtVorhandensein des gesuchten Wortes im Speicher anzeigendes erstes Suchabschlußsignal und ein das Wiedereinschreiben des aus dem Speicher ausgelesenen Bits auslösendes Signal erzeugt, und zwar das erste Weiterschaltsignal dann, wenn das Bit im Ausgangsregister kleiner als das mit diesem verglichenen Bit im Bezugswortregister ist, das zweite Weiterschaltsignal dann, wenn die verglichenen Bits gleich sind, das erste Suchabschlußsignal dann, wenn das Bit im Ausgangsregister größer als das mit diesem verglichene Bit im Bezugswortregister ist, und das Wiedereinschreibsignal dann, wenn das Bit im Ausgangsregister ein nicht zerstörungsfrei aus dem Speicher ausgelesenes Bit ist, und daß die Bitfolgesteuereinrichtung und das Speicheradressierregister bei Ansteuerung des in der vorbe- t>^r> stimmten Reihenfolge letzten Bitspeicherelements eines Speicherplatzes bzw. des letzten Speicherplatzes ieweils ein zweites und drittes Suchabschlußsignal auslösen, bei deren Auftreten das Wort aus dem gerade angesteuerten Speicherplatz in das Ausgangsregister auslesbar und mit dem Bezugswort im Bezugswortregister mittels eines in der Vergleichsvorrichtung enthaltenen Wortvergleichers vergleichbar ist

Bei dieser Speicheranordnung kann jedesmal, wenn ein ausgelesenes Bit eine Information, z. B. eine »0«, darstellt, bei deren Auslesen, im Gegensatz zur entgegengesetzten Information, z.B. der »1«, keine Änderung des Zustande des betreffenden Speicherelementes auftritt, ein erneutes Einschreiben der Information unterbleibt Auf diese Weise verringert sich die Suchzeit gegenüber dem Fail eines parallelen woriweisen Auslesens, Wiedereinschreibens und Vergleichens im statistischen Mittel mit zunehmender Speichergröße. Bei einer Speicherung der Wörter in einer vorbestimmten numerischen Reihenfolge wird erreicht, daß der Suchvorgang abgebrochen werden kann, wenn festgestellt wird, daß die ausgelesene Information in der Reihenfolge hinter dem Bezugswort liegt Gegebenenfalls brauchen daher weder sämtliche Bits des Bezugswortes durchgeprüft noch alle gespeicherten Wörter ausgelesen und mit dem Bezugswort verglichen zu werden. Unter Umständen kann bereits der erste Vergleich zeigen, daß das gesuchte Wort nicht im Speicher enthalten ist, ohne daß sämtliche gespeicherten Wörter ausgelesen werden müssen, bis feststeht daß das gesuchte Wort nicht im Speicher enthalten ist Ein einmaliger Gesamtwortvergleich ist lediglich dann erforderlich, wenn bei allen Bitstellen eine Übereinstimmung vorlag. Auf diese Weise ist mit Sicherheit festgestellt, ob das Bezugswort an dem zuletzt angewählten Speicherplatz steht oder nicht Der Fall, daß sich eine Übereinstimmung in allen Bitstellen ergibt, aber dennoch das Bezugswort nicht im Speicher enthalten ist, wird daher im richtigen Sinne ausgewertet.

Ein bevorzugtes Ausführungsbeispiel der erfindungsgemäßen Speicheranordnung ist in der Zeichnung dargestellt Es zeigt

F i g. 1 ein Blockschaltbild der Speicheranordnung,

F i g. 2 drei Beispiele für den Abtastverlauf durch die Speicherlogik,

F i g. 3 den Arbeitsablauf für einen Adressierzyklus bei der Speicheranordnung gemäß der Erfindung.

Die Wörter werden im Speicher derart angeordnet, daß die bezüglich des Wortteiles, der von der Adressierung betroffen wird, numerisch geordnet sind. Der Speicher besitzt eigene Pufferregister und Gatter, um den Verschiebezyklus auszuführen. Es sind ferner Logikeinrichtungen im Speicher vorgesehen, d^;; es ermöglichen, den Verschiebezyklus in einen Löschzyklus umzukehren. Während dieses Löschzyklus werden unerwünschte Wörter unterdrückt und der entsprechende Teil des Speichers in einem Speicherzyklus weiterverschoben, um die leeren Speicherplätze aus dem Speicher zu eliminieren.

Bei dem erfindungsgemäßen Speicher braucht nur jeweils ein Bit ausgelesen und mit dem entsprechenden Bit des Bezugswortes verglichen zu werden. Dadurch wird die Logikschaltung vereinfacht, was gleichzeitig eine Verringerung der Kosten bringt. Wenn das aus dem Speicher ausgelesene Bit eine Null ist, ist kein Wiedereinschreibzyklus erforderlich, da das dem Zugriff unterworfene Wort nicht geändert bzw. nicht zerstört wird. Ein Wiedereinschreibzyklus ist lediglich erforderlich, wenn eine 1 aus dem Speicher ausgelesen wird. Bei der beschriebenen Anordnung für die Speicheradressierung sind im Durchschnitt nur 25 Wiedereinschreib-

zyklen erforderlich, um Wörter mit 48 Bits unabhängig von der Anzahl der im Speicher untergebrachten Wörter zu adressieren.

Zur inhaltlichen Organisation des Speichers können folgende Kriterien verwendet werden:

Der Name in alphabetischer Reihenfolge für die Verwendung bei einer Adressenspeicherung für Kaufhäuser, Banken, Regierungsstellen usw. In diesem Fall kann z. B. der Speicherinhalt mit einem Telephonverzeichnis verglichen werden, um im Rahmen einer Speicherabfragung einen bestimmten Namen festzustellen. Die mit dem Namen verbundene Information, im vorliegenden Beispiel die Telephonnummer, wird dann für den Gebrauch ausfindig gemacht.

Die Zahl in gelisteter Reihenfolge z. B. für Versicherungsnummern, die Angestelltennummer für Lohnzahlungen, die Nummern von Dokumenten usw.

Das Alter zur Erfassung von Wehrpflichtigen oder des Pensionsaltes.

Eine Zeitdauer z. B. zur Erfassung von Urlaubszeiten, automatischen Lohnerhöhungen, zur Überwachung der Dauer von Versicherungen usw.

Eine numerische Ordnung z. B. als Ergebnis einer Vielfachkalkulation oder für statistische Analysen.

Die Kennzeichnung von Fingerabdrücken, wenn die Fingrabdrücke durch eine digitale Information zur automatischen Abfragung erfaßt sind, wobei die digitalen Daten rasch eingespeichert und bei geringem Schaltungsaufwand auch relativ schnell auffindbar sind.

In Fig. 1 ist die Speicheranordnung gemäß der Erfindung im Prinzip dargestellt. Sie wird im folgenden anhand einer Speicherabfragung beschrieben. Zuerst werden die Wörter im Speicher 1-10 in numerischer Reihenfolge angeordnet. Das Wort, nach dem der Speicher 1-10 abgefragt wird, wird im folgenden als Bezugswort bezeichnet. Das Bezugswort steht im Bezugswortregister 1-34, dessen Inhalt nach links verschoben werden kann, und zwar umlaufend.

Die logische Schaltung enthält ferner eine Bitfolgesteuerung 1-22, die feststellt, welches Bit eines Speicherwortes aus dem Speicher 1-10 ausgelesen und mit dem entsprechenden Bit des Bezugswortregisters 1-34 verglichen werden soll. Die Bitfolgesteuerung 1-22 wird vor dem Beginn des Abfragezyklus auf Null zurückgestellt Sie tastet mit ihren Ausgängen 0 bis 7 nacheinander UND-Gatter 1-38 auf, die ihrerseits je einer Bitstelle des adressierten Speicherplatzes im Speicher 1-10 aus einer Quelle 1-40 einen Leseimpuls zuführen.

Die Bitstelle 0 entspricht dem Bit des Bezugswortes mit der höchsten Stellenwertigkeit. Es ist ferner ein herkömmliches Speicheradressenregister (MAR) 1-14 vorgesehen, das auf die Maschinenadresse des unter Zugriff stehenden Speicherwortes eingestellt ist. Dieses Speicheradressenregister 1-14 wird auf Null zurückgestellt oder auf den Platz des ersten Speicherwortes des Adressenwort-Teils des Speichers. Die Logikschaltung enthält ferner ein herkömmliches Ausgangsregister (MIR) 1-26, das zu dieser Zeit ebenfalls zurückgestellt ist Das Ausgangsregister 1-26 enthält normalerweise den Inhalt des letzten aus dem Speicher 1-10 ausgelesenen Wortes. Jedoch enthält es während des Abfragezyklus in der Regel nur ein Bit des Speicherwortes.

Mit den vorausgehend beschriebenen Anfangsbedingungen kann der Abfragezyklus beginnen. Die dem Inhalt des Speicheradressenregisters 1-14 entsprechende Bitstelle 0 des Speicherwortes wird in das

Ausgangsregister 1-26 eingelesen. Wenn diese aus dem Speicher 1-10 ausgelesene Bitstelle eine 1 ist, was durch die Vergleichsstufe t-32 festgestellt wird, wird dieses Bit unmittelbar in den Speicher 1-10 zurückgeschrieben, während es im Ausgangsregister 1-26 festgehalten wird. Dieses Bit wird sodann mit der Bitstelle 0 des Bezugswortregisters 1-34 verglichen. Da die Bitstelle 0 jedes der beiden miteinander verglichenen Worte entweder eine 0 oder eine 1 sein kann, leiten sich daraus

in vier mögliche Ergebnisse ab. Im folgenden wird das Verhalten des Speichers 1-10 in Abhängigkeit von einem der vier Möglichkeiten wiedergegeben.

a) Die beiden verglichenen Bitstellen haben den Wert 0.

b) Die beiden verglichenen Bitstellen haben den Wert 1.

Wenn die Bitstelle im Ausgangregister 1-26 und die entsprechende Bitstelle im Bezugswortregister gleich

2(i sind, d. h. beide den Wert 0 oder den Wert 1 aufweisen, braucht das dem Zugriff unterworfene Wort deswegen noch nicht gleich dem Wort im Bezugswortregister 1-34 zu sein. Die Bitfolgesteuerung 1-22 wird daher um den Wert 1 weitergeschaltet, so daß die Bitstelle mit der

2^r) nächstniedrigeren Stellenwertigkeit desselben Speicherwortes ausgelesen und mit der entsprechenden Bitstelle des Bezugswortregisters 1-34 verglichen werden kann. Das Ausgangsregister 1-26 ist zu dieser Zeit zurückgestellt.

c) Die Bitstelle des Ausgangsregisters 1-26 hat den Wert 0 und die entsprechende Bitstelle des Bezugswortregisters 1-34 den Wert 1.

Unter diesen Bedingungen kann das dem Zugriff unterworfene Wort nicht gleich dem im Bezugswortregister stehenden Wort sein. Deshalb wird das Speicheradressenregister 1-14 um den Wert 1 weitergeschaltet, so daß dieselbe Bitstelle des nächsten Wortes im Speicher dem Zugriff unterworfen und mit der entsprechenden Bitstelle des Bezugswortregisters verglichen werden kann.

d) Die zu untersuchende Bitstelle im Ausgangsregister 1-26 hat den Wert 1 und die entsprechende Bitstelle im Bezugswortregister 1 -34 hat den Wert 0.

Wenn sich diese Bedingung einstellt, hat das im Speicheradressenregister 1-14 stehende Wort mit Bezug auf den Zugriff eine numerisch höhere Position als das Wort im Bezugswortregister. Da der Inhalt des

so Speichers in einer bestimmten Ordnung organisiert ist werden auch alle nachfolgenden Wörter von einer höheren numerischen Ordnung sein. In diesem Fall können weder die zuvor dem Zugriff unterworfener Wörter, das im Augenblick dem Zugriff unterworfene Wort, noch die nachfolgend dem Zugriff unterworfener Wörter mit dem Bezugswort gleich sein. Der Abfragezyklus hält somit an diesem Punkt und liefert ein Signal das anzeigt, daß das Bezugswort nicht im Speichel vorhanden ist

M) Im Speicher sind Vorkehrungen getroffen, um di< Zahl in der Bitfolgesteuerung 1-22 zu überprüfen Hierfür findet eine Vergleichsstufe 1-24 Verwendung Wenn die Anzahl der Bits in der Bitfolgesteuerunf gleich der Anzahl der Bits in dem Bezugswort ist, sine

6^r> alle Bitstellen des Bezugswortes dem Vergleict unterzogen worden. Dies wird durch ein von dei Vergleichsstufe 1-24 abgegebenes Suchabschlußsigna am Anschluß 1-S2 angezeigt Nachdem die Bitstelle mi

der niedrigsten Stellenwertigkeit verglichen worden ist, wird der Abfragezyklus beendet und das gesamte Speicherwort aus der Maschinenposition des Speicheradressenregisters 1-14 parallel in das Ausgangsregister 1-26 eingelesen und mit dem Bezugswort im Register 1-34 durch die Vergleichsstufe 1-36 verglichen. Die Bits befinden sich nun im Bezugswortregister in derselben Stelle, in der sie sich vor dem Beginn des Abfragezyklus befunden haben. Wenn beide Wörter einander gleich sind, wird der gewünschte Speicherplatz festgestellt und im Speicheradressenregister 1-14 festgehalten. Die Information des Speicherwortes zusätzlich zu der für den Zugriff verwendeten steht somit für das Programm augenblicklich zur Verfugung. Wenn die beiden Wörter, wie vorausgehend angedeutet, parallel zueinander ts verglichen werden, wird bei diesem Vergleich durch die Vergleichsstufe 1-36 manchmal eine Nichtübereinstimmung angezeigt. Für diesen Fall befindet sich das Bezugswort nicht im Speicher. Dieser Zustand wird an der Klemme 1-46 durch ein entsprechendes Signal angezeigt.

Der Speicher besitzt außerdem eine Vergleichsstufe 1-16, um die Zahl im Speicheradressenregister 1-14 zu überprüfen. Wenn die Maschinenadresse des letzten Wortes des Adressenteiles des Speichers 1-10 das Speicheradressenregister passiert, wird der Abfragezyklus beendet. Da der gesamte Speicher erfolglos nach dem Bezugswort angefragt wurde, bedeutet dies, daß das Bezugswort nicht im Speicher vorhanden ist. Dieser Zustand wird durch ein an der Klemme 1 -46 anliegendes Suchabschlußsignal angezeigt.

Gemäß Fig. 1 wird der Inhalt des Ausgangsregisters 1-26 über ein ODER-Gatter 1-28 zwei bitweise arbeitenden Vergleichsstufen 1-30 und 1-32 zugeführt. Somit wird eine 1 irgendeiner Bitstelle des Ausgangsregisters 1-26 der Vergleichsstufe zugeleitet. Für den Fall, daß alle Bitstellen des Ausgangsregisters 1-26 eine 0 enthalten, würde der Vergleichsstufe 1-30 eine 0 zugeführt werden. Diese Logikanordnung ermöglicht in Verbindung mit der Anwendung des Bezugswortregisters 1-34 als Schieberegister den Vergleich jeder durch die Bitfolgesteuerung 1 -22 ausgewählten Bitposition mit der Bitposition mit höchster Stellenwertigkeit im Bezugswortregister 1-34 nur unter der Verwendung der einfachen Vergleichsstufe 1-30.

Die Art und Weise, in der der Speicher arbeitet, wird im folgenden anhand der drei Beispiel A, B und C gemäß F i g. 2 erklärt. Der Einfachheit halber wird angenommen, daß die Speicherplätze 33 bis 45 je mit einem aus 8 Bitstellen bestehenden Wort besetzt sind. Die stufenförmig verlaufenden Linien durch die Zahlenfolge kennzeichnen den Weg der Logikschaltung durch den Speicher beim Versuch, das dem Bezugswort entspechende Wort zu finden. Im Beispiel A verlangt das Programm, den Speicherplatz zu finden, in dem das Wort 00111010 und die diesem Wort zugeordnete Information gespeichert ist Die einzelnen Schritte des Rechenablaufes für die Speicherabfragung nach dem Beispiel A sind in Fi g. 3 dargestellt Der Speicherinhalt für das Beispiel A ist in F i g. 2 dargestellt.

Die Beispiele B und C zeigen Speicherabfragungen, bei denen das gesuchte Wort im Speicher nicht vohanden ist Bei einem platzadressierten Speicher müßte, um dies feststellen zu können, der gesamte Speicherinhalt ausgelesen, verglichen und wieder Wort für Wort zurückgeschrieben werden, bevor feststehtdaß das dem Bezugswort entsprechende Wort nicht im Speicher vorhanden ist Der Speicher gemäß der Erfindung ist viel schneller, wie an den Beispielen B und C erkennbar ist. Gegenüber den ebenfalls bekannten assoziativen Speichern aber ist ein geringerer Aufwand an Vergleichsschaltungen gegeben.

Beispiel A
Speicherabfragung unter Bezugnahme auf F i g. 1

In das Bezugswortregister 1-34 wird das Bezugswort 00111010 eingespeichert.

Die Bitfolgesteuerung 1-22, das Speicheradressenregister 1-14 und das Ausgangsregister 1-26 werden zurückgestellt. Der Wert der Bitposition mit der höchsten Stellenwertigkeit (Bitposition 0) des im Speicherplatz 33 des Speichers 1-10 befindlichen Wortes wird in das Ausgangsregister 1-26 überführt und überprüft, um festzustellen, ob der Wert gleich 0 ist. Da der Wert der dem Zugriff unterworfenen Bitstelle 0 ist, wird er nicht in den Speicher zurückgeschrieben. Er wird mit der entsprechenden Bitstelle des Bezugswortregisters 1-34 verglichen. Die Vergleichsstufe 1-30 stellt fest, daß die Bitstelle im Ausgangsregister 1-26 denselben Wert wie die entsprechende Bitstelle im Bezugswortregister 1-34 besitzt. Deshalb wird die Bitfolgesteuerung 1-22 weitergeschaltet, so daß die Bitstelle 1 dem Zugriff unterworfen und verglichen werden kann. Jedoch muß die Bitfolgesteuerung überprüft werden, um sicherzustellen, daß die nicht auf eine Zahl eingestellt ist, die höher als die Zahl der Bits des Bezugswortes (im vorliegenden Beispiel 8) ist. Dies ist in Fig.3 durch den mit 3-34 bezeichneten Block angedeutet.

Da im vorliegenden Beispiel die Bitfolgesteuerung nun auf die Bitstellung 1 eingestellt ist wiederholt sich die Abfragung, indem Punkt A am Ausgang des Blockes 3-36 gemäß Fig.3 zurück zum Punkt 3-14 am Anfang des Abfragezyklus geschaltet wird.

Die Bitstelle 1 des Wortes im Speicherplatz 33 wird in das Ausgangsregister 1-26 überführt und mit der entsprechenden Bitsteile des Bezugswortregisters 1-34 verglichen. Da beide Bitstellen den Wert 0 besitzen, wird die Bitfolgesteuerung 1-22 auf Bitstelle 2 weitergeschaltet. Der Wert der Bitstelle 2 desselben Wortes wird in das Ausgangsregister 1-26 eingelesen und durch die Vergleichsstufe 1-30 verglichen.

Im vorliegenden Beispiel hat die Bitstelle 2 im Ausgangsregister den Wert 0; dagegen besitzt die Bitstelle 2 im Bezugswortregister den Wert 1. Das Speicheradressenregister 1-14 wird über den Anschluß 1-48 weitergeschaltet und überprüft, um festzustellen, daß die Bitstellenzahl des Adressenteils nicht überschritten wird. Sodann wird die Abfragung vom Block 3-36 über die Leitung 3-14 vom Punkt A aus zum Punkt A am Eingang des Abfrageablaufs zurückgeschaltet Da das Speicheradressenregister 1-14 im vorausgehenden Schritt weitergeschaltet wurde, wird die Bitstelle 2 des im Speicherplatz 34 befindlichen Wortes in das Ausgangsregister 1-26 Obertragen und mit der 1 im Bezugswortregister 1-34 verglichen. Da die beiden Werte nicht gleich sind, wird der Inhalt des Speicheradressenregisters erneut weitergeschaltet, wodurch nunmehr der Speicherplatz 35 dem Zugriff unterliegt Diese unmittelbare Weiterschaltung von Speicherplatz zu Speicherplatz erfolgt so lange, bis der Speicherplatz 37 ausgelesen wird.

Wenn die Bitstelle 2 des Wortes im Speicherplatz 37 in das Ausgangsregister 1-26 eingelesen worden ist stellt die 1-Bit-Vergleichstufe 1-32 nach Vergleich mit

einer von einer Quelle 1-56 abgegebenen binären 1 durch Abgabe eines Wiedereinschreibsignals am Anschluß 1-54 fest, daß die Bitstelle 2 den Wert 1 hat. Daher wird der Wert dieser Bitstelle in den Speicher zurückgeschrieben, so daß sich das Wort im Speicher nicht ändert. Anschließend wird die Bitstelle 2 des Ausgangsregisters mit der Bitstelle 2 des Bezugswortregisters verglichen. Da beide Bitstellen den Wert 1 besitzen, wird das Ausgangsregister zurückgestellt, wobei gleichzeitig die Bitfolgesteuerung 1-22 weitergeschaltet und damit die Bitstelle 3 der Überprüfung unterworfen wird. Der Abfragevorgang beginnt nun wieder am Punkt A des in F i g. 3 dargestellten Ablaufes. Jetzt wird der Wert der Bitstelle 3 des Wortes im Speicherplatz 37 in das Ausgangsregister 1-26 eingelesen. Da dieser Wert 0 ist und die Bitstelle 3 des Bezugswortes den Wert 1 besitzt, wird das Spcichcradressenregister weitergeschaltet, so daß der Speicherplatz 38 einer Überprüfung unterzogen wird. Die Bitstelle 3 dieses Speicherplatzes wird nunmehr in das Ausgangsregister 1-26 übertragen, und da diese Bisteile 3 den Wert 0 und die Bitstelle 3 des Bezugswortes den Wert 1 besitzt, wird das Speicheradressenregister weitergeschaltet, so daß nunmehr der Speicherplatz 39 überprüft wird. Hierbei wird der Wert der Bitstelle 3 des Speicherplatzes 39 in das Ausgangsregister 1-26 eingelesen. Dieser Wert ist 1 und wird sofort in den Speicher 1-10 zurückgeschrieben. Da die beiden 3itstellen den Wert 1 besitzen, wird das Ausgangsregister 1-26 zurückgestellt, während die Bitfolgesteuerung 1-22 weitergeschaltet wird und damit die Bistelle 4 der Abfragung unterwirft

Die Bitstelle 4 des Wortes im Speicherplatz 39 wird in das Ausgangsregister 1-26 eingelesen, und da diese Bitstelle des Speicherplatzes und die entsprechende Bitstelle des Bezugswortes einander gleich sind, wird das Ausgangsregister zurückgestellt. Infolge davon wird die Bitfolgesteuerung weitergeschaltet, so daß die Bitstelle 5 der Abfragung unterworfen wird. Darauf wird die Bitstelle 5 des Wortes im Speicherplatz 39 in das Ausgangsregister 1-26 eingelesen, und da sowohl die Bitstelle 5 des Ausgangsregisters als auch die Bitstelle 5 des Bezugswortes beide den Wert 0 besitzen, d. h. einander gleich sind, wird die Bitfolgesteuerung 1-22 weitergeschaltet und die Abfragung der Bitstelle 6 eingeleitet. Nachdem die Bitstelle 6 des Wortes im Speicherplatz 39 in das Ausgangsregister eingeschrieben wurde, wird festgestellt, daß der Wert dieser Bitstelle 6 im Ausgangsregister 0 ist, wogegen der entsprechende Wert des Bezugswortes 1 ist. Damit wird das Speicheradressenregister weitergeschaltet und wird abgefragt Anschließend wird die Bitstelle 6 des Wortes im Speicherplatz 40 in das Ausgangsregister eingeschrieben.

Nunmehr wird festgestellt, daß die Bitstelle 6 im Ausgangsregister und die Bitstelle 6 des Bezugwortes gleich sind und dem Wert 1 entsprechen. Damit wird das Ausgangsregister, nachdem die 1 in den Speicher zurückgeschrieben wurde, zurückgestellt, während die Bitfolgesteuerung weitergeschaltet wird und die Bitstelle 7 der Abfragung zuführt

Damit beginn der Abfrageprozeß erneut am Punkt A gemäß F i g. 3, wodurch entsprechend die Bitstelle 7 des Wortes im Speicherplatz 40 in das Ausgangsregister eingeschrieben wird. Sowohl die Bitstelle 7 des Ausgangsregisters als auch die entsprechende Bitstelle des Bezugswortes besitzen den Wert 0, wodurch die Weiterschaltung für die Bitfolgesteuerung ausgelöst und die Abfragung der Bitstelle 8 eingeleitet wird. Damit ist die Anzahl der für die Speicherabfragung eingestellten Bitstellen gleich der Anzahl der Bitstellen des Bezugswortes, d. h. alle 8 Bitstellen des Bezugswortes wurden für den Vergleich verwendet. Deshalb wird das gesamte im Speicherplatz 40 befindliche Wort parallel in das Ausgangsregister 1-26 eingelesen und mit dem gesamten Inhalt des Bezugswortregisters 1-34 unter Verwendung der Mehrfach-Bit-Vergleichsstufe 1-36

ίο gemäß F i g. 1 verglichen. Der Vergleich ergibt, daß das gesuchte Wort in dem Speicherplatz steht, auf den das Speicheradressenregister eingestellt ist. Da der Speicherplatz 40 den Wert 00111010 enthält, ist somit die Speicherabfragung erfolgreich abgeschlossen, was durch ein entsprechendes Sugnal am Anschluß 1-44 angezeigt wird.

_M Beispiele

Suche nach einem nicht vorhandenen Wort im Speicher

Die Abfragung verläuft für das in F i g. 2 dargestellte Beispiel B in derselben Weise wie im Beispiel A. Zuerst wird die Bitstelle 0 aus dem Speicher gelesen und mit der Bitstelle 0 des Bezugswortes verglichen. Da beide Bitstellen den Wert 0 aufweisen, wird die Bitfolgesteuerung zur Bitstelle 1 weitergeschaltet und die Abfragung gemäß F i g. 3 auf den Punkt A zurückgestellt.

Anschließend wird die Bitstelle 1 des Wortes im Speicherplatz 33 ausgelesen und festgestellt, daß der Wert 0 ist Der Wert der Bitstelle 1 des Bezugswortes ist dagegen 1. Deshalb wird das Speicheradressenregister weitergeschaltet, wodurch die Bitstelle 1 des Speicher-

platzes 34 ausgelesen und verglichen wird. Derselbe Ablauf erfolgt mit der Bitstelle 1 der Wörter in den Speicherplätzen 35 bis 41.

Beim Auslesen der Bistelle 1 des Speicherplatzes 41 stellt man fest, daß dessen Wert 1 ist. Dieser Wert wird sofort in den Speicher 1-10 zurückgeschrieben. Dies wird direkt von dem Ausgangsregister 1-12 bewirkt

Die Bitstelle 1 des Ausgangsregisters wird nun mit der Bitstelle 1 des Bezugswortes verglichen. Da beide den Wert 1 besitzen, wird das Ausgangsregister zurückge-

stellt während die Bitfolgesteuerung eine Weiterschaltung zur Bitstelle 2 bewirkt Nunmehr wird der Wert der Bitstelle 2 des Speicherplatzes 41 in das Ausgangsregister eingelesen und, da dieser Wert 1 ist sofort in den Speicher zurückgeschrieben. Die Bitstelle 2 des

so Ausgangsregisters wird nun mit der Bitstelle 2 des Bezugswortes verglichen. Die entsprechende Bitstelle des Ausgangsregisters enthält den Wert 1, wogegen die Bitstelle 2 des Bezugswortes den Wert 0 enthält Diese Bedingung zeigt an, daß das in dem Speicheradressenregister (Speicherplatz 41 im Beispiel B) und alle folgenden Wörter einen numerischen höheren Wert aufweisen als das Bezugswort Das vorausgehende Wort im Speicherplatz 40 hat dagegen einen numerischen Wert, der kleiner als der des Bezugswortes ist, da die Bitstelle 1 des Wortes im Speicherplatz 40 den Wert 0 aufweist während die Bitstelle 1 des Bezugswortes den Wert 1 besitzt Damit ist festgestellt, daß das Bezugswort nicht im Speicher vorhanden ist, und am Anschluß 1-50 erscheint ein Suchabschlußsignal. Es sei darauf hingewiesen, daß nur drei Bitstellen durch die Bitfolgesteuerung für den Zugriff anzusteuern waren, um festzustellen^ daß das gewünschte Wort nicht im Speicher vorhanden ist

Beispiel C

Suche nach einem nicht vorhandenen Wort

Es wird angenommen, daß der Speicher nach dem Bezugswort 00111011 gemäß Fig.2 abgefragt wird. Das Bezugswort ist fast dasselbe wie im Beispiel A, da lediglich die Bitstelle 7 einen anderen nämlich den Wert 1 besitzt. Deshalb verläuft die Speicherabfragung bis zum Speicherplatz 40, d. h. bis zur Bitstelle 6 des Ausgangsregisters und des Bezugswortregisters beide aen Wert 1 aufweisen, wird das Ausgangsregister zurückgestellt, während die Bitfolgesteuerung zur Bitstelle 7 weitergeschaltet wird. Die Bitstelle 7 des Speicherplatzes 40 wird in das Ausgangsregister eingelesen. Da diese Bitstelle den Wert 0, die Bitstelle 7 des Bezugswortes jedoch den Wert i besitzt, wird das Speicheradressenregister weitergeschaltet und die Bitstelle 7 des Wortes im Speicherplatz 41 ausgelesen. Es sei darauf hingewiesen, daß die Bitstelle 1 dieses Wortes im Speicherplatz 41 den Wert 1 aufweist. Daher kann das Bezugswort nicht im Speicher sein. Da jedoch jeweils nur 1 Bit Oberprüft wird, kann noch nicht festgestellt werden, ob das Bezugswort gefunden werden wird. Deshalb geht die Speicherabfragung weiter. Es wurde festgestellt, daß die Bitstelle 7 des im Speicherplatz 41 befindlichen Wortes den Wert 0 hat, während die Bitstelle 7 des Bezugswortes den Wert 1 besitzt. Deshalb wird das Speicheradressenregister weitergeschaltet und die Bitstelle 7 des Wortes im Speicherplatz 42 überprüft und festgestellt, daß sie nicht gleich der Bitstelle 7 des Bezugswortes ist. Schließlich wird die Bitstselle 7 des Wortes im Speicherplatz 43 ausgelesen und festgestellt, daß deren Wert 1 ist. Dieser Wert wird sofort wieder in den Speicher 1-10 zurückgeschrieben. Dies erfolgt direkt über das Ausgangsregister und die Informationsansteurungseinrichtung 1-lZ Der anschließende Vergleich ergibt, daß die beiden Bitstellen den Wert 1 besitzen. Das Ausgangsregister wird zurückgestellt, während die

Bitfolgesteuerung zur Bitstelle 8 zu deren Überprüfung weitergeschaltet wird. Damit ist die Anzahl der Bitstellen im Bezugswort gleich der Anzahl der Bitstellen im Speicher, nämlich 8. Der gesamte Inhalt des Wortes im Speicherplatz 43 wird nun parallel in das Ausgangsregister 1-26 eingelesen und mit dem Inhalt des Bezugswortregisters 1-34 durch die Mehrfach-Bit-Vergleichsstufe 1-36 verglichen. Der Vergleich ergibt, daß die beiden Wörter nicht gleich sind. Dadurch wird ein Signal zum Anschluß 1 -46 ausgelöst, das anzeigt, daß das gesuchte Bezugswort nicht im Speicher 1-10 ist. Beim Beispiel C wurde das Speicheradressenregister nicht an der Stelle angehalten, an der sich das Bezugswort befände, wenn es sich im Speicher befinden würde. Vielmehr wird das Speicheradressenregister über diesen Speicherplatz hinausgeschaltet, bevor festgestellt wird, daß das Bezugswort nicht im Speicher ist. Jedoch ist es auch bei diesem Beispiel nicht notwendig, den gesamten Speicherinhalt abzufragen, um dies feststellen zu können. Es ist von besonderer Bedeutung, daß mit einer zunehmenden Wortzahl in einem derartigen Speicher der Abfragezyklus umso schneller endet, im Gegensatz zu einem platzadresierten Speicher, bei dem der gesamte Speicherinhalt überprüft werden muß. Dadurch wird die Wirtschaftlichkeit der Speicherabfragung im Gegensatz zu denen bei herkömmlichen Speichern mit zunehmender Speichergröße verbessert.

Die vorausgehend beschriebene Logikschaltung hat nicht nur den Vorteil einer sehr viel schnelleren Speicherabfragung bei geringeren Kosten, vielmehr kann sie auch vorteilhaft dazu benutzt werden, um neue Wörter in den Speicher einzuführen oder unerwünschte Wörter in diesem zu löschen. In jedem dieser beiden Fälle muß eine listenförmige Ordnung hergestellt werden.

Die Logikschaltung muß einen Wortzähler umfassen, wie er allgemein in Rechnern Verwendung findet Auf die Beschreibung seiner Wirkungsweise kann daher verzichtet werden.

Hierzu 3 Blatt Zeichnungen

Claims (7)

Patentansprüche:

1. Speicheranordnung mit einem informationszerstörend lesbaren Speicher, dessen Speicherplätze jeweils ein Wort aufnehmen, mit einer die Speicherplätze in einer vorbestimmten Reihenfolge jeweils in Abhängigkeit von einem ersten Weiterschaltsignal ansteuernden Einrichtung, mit einem Ausgangsregister zur Aufnahme eines aus dem Speicher ausgelesenen Wortes, mit einem Register zum Speichern eines gesuchten Wortes als Bezugswort und mit einer Einrichtung zum Vergleichen des Inhalts des Bezugswortregisters mit dem Speicherinhalt, dadurch gekennzeichnet, daß eine die Bitspeicherelemente in einer vorbestimmten Reihenfolge jeweils in Abhängigkeit von einem zweiten Weiterschaltsignal ansteuernde Bitfolgesteuereinrichtung (1-22) vorgesehen ist, so daß nur das Bit im angesteuerten Bitspeicherelement des angesteuerten Wortspeicherplatzes in das Ausgangsregister (1-26) übertragbar ist, das die Vergleichseinrichtung (1-30, 1-32, 1-36) eine an die Ausgänge des Ausgangsregisters (1-26) über ein ODER-Gatter (1-28) und an einen Ausgang des als Schieberegister ausgebildeten Bezugswortregisters (1-34), dem das zweite Weiterschaltsignal als Schiebesignal zuführbar ist, angeschlossene Ein-Bit-Vergleichsvorrichtung (1-30, 1-32) aufweist, daß die Ein-Bit-Vergleichsvorrichtung (1-30, 1-32) das erste Weiterschaltsignal (1-48), das zweite Weiterschaltsignal, ein das NichtVorhandensein des gesuchten Wortes im Speicher anzeigendes erstes Suchabschlußsignal (1-50) und ein das Wiedereinschreiben des aus dem Speicher ausgelesenen Bits auslösendes Signal (1-54) erzeugt, und zwar das erste Weiterschaltsignal (1-48) dann, wenn das Bit im Ausgangsregister (1-26) kleiner als das mit diesem verglichene Bit im Bezugswortregister (1-34) ist, das zweite Weiterschaltsignal dann, wenn die verglichenen Bits gleich sind, das erste Suchabschlußsignal (1-50) dann, wenn das Bit im Ausgangsregister (1-26) größer als das mit diesen verglichene Bit im Bezugswortregister (1-34) ist, und das Wiedereinschreibsignal (1-54) dann, wenn das Bit im Ausgangsregister (1-26) ein nicht zerstörungsfrei aus dem Speicher (1-10) ausgelesenes Bit ist, und daß die Bitfolgesteuereinrichtung (1-22) und das Speicheradressierregister (1-14) bei Ansteuerung des in der vorbestimmten Reihenfolge letzten Bitspeicherelements eines Speicherplatzes bzw. des letzten Speicherplatzes jeweils ein zweites und drittes Suchabschlußsignal (1-52; 1-42) auslösen, bei deren Auftreten das Wort aus dem gerade angesteuerten Speicherplatz in das Ausgangsregister (1-26) auslesbar und mit dem Bezugswort im Bezugswortregister (1-34) mittels eines in der Vergleichsvorrichtung enthaltenen Wortvergleichers (1-36) vergleichbar ist.

2. Speicheranordnung nach Anspruch 1, dadurch gekennzeichnet, daß die Bitfolgesteuereinrichtung (1-22) mehrere Ausgangsklemmen (0, 1, 2, ..., 7) aufweist, die nacheinander in Abhängigkeit von aufeinanderfolgenden zweiten Weiterschaltsignalen der Ein-Bit-Vergleichsvorrichtung (1-30) aktivierbar sind, daß jeweils ein UND-Gatter einer Vielzahl von UND-Gattern (1-38) mit einer der Ausgangsklemmen der Bitfolgesteuereinrichtung (1-22) verbunden ist. daß die UND-Gatter (1-38) jeweils die Wahl

eines Bitspeicherelements innerhalb des adressierten Wortspeicherplatzes bewirken und daß der Inhalt dieses Bitspeicherelements durch Anlegen eines Lesesignals auslesbar ist. das aus einer allen UND-Gattern (1-38) gemeinsamen Quelle (1-40) zuführbar ist

3. Speicheranordnung nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß Informationstreibereinrichtungen (1-12) zum Einlesen einer Information in entsprechende Bitspeicherelementspalten mit dem Speicher (1-10) und daß eine Vielzahl von Leseverstärkern (1-20) mit den Bitspeicherelementspalten des Speichers (1-10) und mit dem Ausgangsregister (1-26) verbunden sind.

4. Speicheranordnung nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß der Wort-Vergleicher eine zwischen das Bezugswortregister (1-34) und das Ausgangsregister (1-26) geschaltete Mehrfach-Bit-Vergleichsstufe (1-36) für einen gleichzeitigen Vergleich von mehr als einer Bitstelle des Bezugswortregisters (1-34) mit mehr als einer Bitstelle des Ausgangsregisters (1-26) aufweist

5. Speicheranordnung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Ein-Bit-Vergleichsvorrichtung eine bitweise arbeitende Vergleichsstufe (1-32) zwischen dem ODER-Gatter (1-28) und einer Quelle (1-56) für eine binäre 1 und dem Speicher für das Wiedereinschreiben einer aus dem Speicher (1-10) ausgelesenen binären 1 in dasselbe Speicherelement aufweist.

6. Speicheranordnung nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß eine Speicheradressenvergleichsstufe (1-16) zwischen das Speicheradressierregister (1-14) und eine Informationsquelle mit der Speicherplatzadresse des letzten Speicherwortes geschaltet ist und daß diese Vergleichsstufe (1-16) eine Anzeigeeinrichtung (1-42) enthält, die das Ende des Abfragezyklusses anzeigt, wenn der Inhalt des Speicheradressierregisters (1-14) der Speicherplatzadresse des letzten Speicherwortes entspricht.

7. Speicheranordnung nach Anspruch 3, dadurch gekennzeichnet, daß ein Pufferregister (1-18) parallel zwischen die Informationstreibereinrichtungen (1-12), das Ausgangsregister (1-26) und das Bezugswortregister (1-34) geschaltet ist und die Erzeugung eines Verschiebezyklus zuläßt, bei dem der Inhalt des Ausgangsregisters (1-26) parallel in den Speicher (1-10) zurückführbar und auf den nächstfolgenden Speicherplatz in der vorbestimmten Reihenfolge vorrückbar ist.