DE2459476A1

DE2459476A1 - Schaltungsanordnung fuer nichtzyklische datenpermutationen

Info

Publication number: DE2459476A1
Application number: DE19742459476
Authority: DE
Inventors: Werner Dipl Ing Dr Rer N Kluge
Original assignee: MATHEMATIK und DATENVERARBEITU
Current assignee: MATHEMATIK und DATENVERARBEITU
Priority date: 1974-12-16
Filing date: 1974-12-16
Publication date: 1976-06-24
Also published as: DE2459476B2; GB1518697A; US4030078A

Description

Schaltungsanordnung für nichtzyklische Datenpermutationen

Die Erfindung betrifft eine Schaltungsanordnung für nichtayklische Datenperrautationen zwischen den Speicherzellen eines dynamischen Speichers mit einem Permutationsnetzwerk zum Transferieren des Inhaltes einer vorbestimmten Speicherzelle in den Schreib-Lesekopf und einem Zugriffssteuerwerk zum Erzeugen einer Permutationssequenz .

Zum Abspeichern großer Datenmengen in Rechenanlagen werden vorwiegend Platten- und Trommelspeicher eingesetzt. Bei diesen Speichern sind die Daten auf einem magnetischen Medium aufgezeichnet, das gegenüber einem festen Schreib/Lesekopf eine fortwährende rotierende Bewegung mit konstanter Umlaufgeschwindigkeit ausführt. Ein Nachteil dieser zyklischen Datenbewegung relativ zum Lesekopf besteht darin, daß die Zugriffszeit zu einem beliebigen Datum von dessen jeweiliger Position gegenüber dem Lesekopf im Augenblick der Adressierung abhängt, so daß im statistischen Mittel eine halbe Umdrehung des Aufzeichnungsträgers ausgeführt werden muß, bevor das gewünschte Datum ge-

60 9 8 26/0057

2459478

lesen oder geschrieben werden kann. Die dafür notwendige Zeit liegt in Bereich von Millisekunden, so daß ein direkter Zugriff der um etv/a drei bis vier Größenordnungen schneller arbeitenden Zentraleinheit ökonomisch nicht vertretbar ist. Deshalb werden diese dynamischen Speicher als Hintergrundspeicher eingesetzt, von denen zusammenhängende Datenblöcke über selbständig arbeitende Kanalwerke zunächst in den Arbeitsspeicher der Zentraleinheit übertragen werden, bevor dem Rechnerkern der Zugriff ermöglicht wird. Die Zentraleinheit kann auf diese Weise die durch den Abruf eines Datenblocks vom Hintergrundspeicher entstehende Zugriffszeitlücke durch anderweitige Aktivität überbrücken. Dieses Verfahren ist jedoch mit erheblichem Verwaltungsaufwand, z.B. für die Freistellung eines Arbeitsspeicherbereichs, die Erstellung eines Kanalprogrammes und die Behandlung von Interrupts verbunden. Zudem ist oftmals der Transfer eines zusammenhängenden Datenblocks überhaupt nicht notwendig, wenn z.B. nur einzelne Daten inspiziert werden müssen. Aus diesen Gründen ist es zweckmäßig, der Zentraleinheit einen schnellen Direktzugriff sowohl auf einzelne Daten als auch auf zusammenhängende Datenblöcke zu verschaffen, die in Hintergrundspeichern sehr großer Kapazität gehalten werden.

Für die Realisierung von Hintergrundspeichern kommen nur Technologien in Frage, die sich durch niedrige Kosten pro Bit und extrem hohe Datenpackungsdichte auszeichnen. Unter diesem Gesichtspunkt erscheinen "Charge-Transfer-Devices" anstelle von Trommelspeichern und "Magnetic-Domain-Devices" anstelle von Plattenspeichern besonders geeignet. Diese Technologien erfordern im Gegensatz zu Platten- und Trommelspeichern eine fortwährende Datenbewegung sowohl relativ zum Speichermedium selbst als auch relativ zu einem fest auf dem Speichermedium angebrachten Schreib/Lesekopf. Aufgrund der Bewegung relativ zum Speichermedium wird es möglich, Schaltfunktionen zu implementieren, so daß die Datenbewegung nicht auf eine zyklische Bewegung beschränkt bleiben muß. Vielmehr kann der Inhalt einer Speicherzelle wahlweise auf eine von zwei oder mehreren Nachfolgerzellen übertragen

609826/0057

werden, während die Zelle selbst -zum selben Zeitpunkt den Inhalt einer von zwei oder mehreren Vorgängerzellen übernimmt. Auf diese Weise stehen mehrere Wege oder genau ein sehr kurzer Weg zur Verfügung, auf denen der Inhalt einer beliebig ausgewählten Zelle zum Schreib-Lesekopf transportiert werden kann.

Es ist ein Permutationsnetzwerk bekannt (IEEE Transactions on computers Vol. C-2/No. 4 (1972), p. 359-366), das auf einer baumartigen Verbindungsstruktur basiert, bei der jede Speicherzelle genau zwei Nachfolgerzellen und zwei Vorgängerzellen besitzt. Alle Verbindungen innerhalb des Netzwerkes sind zwei Permutationen zugeordnet, von denen die Verbindungen jeweils einer Permutation simultan aktiviert werden. Die beiden Permutationen sind so angelegt, daß in einem Speicher mit 2 Zellen der Inhalt jeder Zelle in höchstens k Schritten zum Schreib-Lesekopf gebracht werden kann. _/;

Bei einem anderen bekannten Permutationsnetzwerk (IEEE Transactions on computers Vol. C-23, No. 3 (1974), p. 272-276) sind die Verbindungen zwischen den Zellen so angelegt, daß bei einer

k
Gesamtkapazität von 2 .-1 Zellen mit ebenfalls zwei Permutationen der Inhalt einer Zelle in der Größenordnung von k Schritten, jedoch der Inhalt von allen in fortlaufender Numerierung nachfolgenden Zellen mit jeweils einem weiteren Schritt Verzögerung zum Schreib-Lesekopf transportiert v/erden kann.

Ein entscheidender Nachteil beider Hetzwerke besteht darin/ daß Verbindungen zwischen nicht benachbarten Speicherzellen hergestellt werden müssen/ die b.ei sinnvollen Speicherkapazitäten ein komplexes, nicht-planares Verbindungsnetzwerk mit einer erheblichen Anzahl von Leitungskreuzungen erfordern, das einen beträchtlichen Anteil der auf dem Speicherchip zur Verfügung stehenden Fläche beansprucht. Gänzlich ungeeignet sind diese Netzwerke für "Magnetic-Domain-Devices", da hier ein Datentransport über größere Distanzen nicht in einem Permutationstakt ausgeführt werden kann.

609826/0057

2459471

Der Erfindung liegt aeshalb die Aufgabe zugrunde, das Permutationsnetzwerk so zu strukturieren, daß ein Datenaustausch lediglich zttfischen unmittelbar benachbarten Speicherzellen stattfindet, daß das Verbindungsnetzwerk kreuzungsfrei bleibt, und daß der Zugriff zu einer Speicherzelle in der Größenordnung von k Takten, der Zugriff zu 2™ aufeinanderfolgenden Zellen

in der Größenordnung von 2^ Takten bei einer Gesamtspeicher-

Y
kapazität von 2 "-1 (k^ g) Zellen erfolgen kann.

Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß als Perinutationsnetzwerk 2 -1 Speicherzellen in Form einer Baumstruktur in k von 0 bis k-1 numerierten Ebenen so angeordnet sind, daß die Ebene i aus 2^X Speicherzellen gebildet ist, daß jede Speicherzelle der Ebene i mit zwei ihr benachbarten miteinander verbundenen Speicherzellen der Ebene i + 1 so verbunden ist, daß diese drei Speicherzellen ein Dreieck bilden, in dem die Inhalte der Speicherzellen im Uhrzeigersinn zyklisch vertauschbar sind, daß jede der Speicherzellen der Ebenen 1 — i - k - 2 zwei Dreiecken und die als Schreib-Lesekopf dienende eine Speicherzelle der Ebene 0 und jede der Speicherzellen der Ebene k-1 nur einem Dreieck angehört, daß ein Zugriffssteuerwerk zum simultanen Transferieren der Inhalte der in geradzahlig numerierten Ebenen angeordneten Speicherzellen in zugeordnete Speicherzellen der nächsthöheren ungeradzahlig numerierten Ebenen (Permutation A) und zum simultanen Transferieren der Inhalte der in ungeradzahlig numerierten Ebenen angeordneten Speicherzellen in zugeordnete Speicherzellen der nächsthöheren geradzahlig numerierten Ebene (Permutation B) vorgesehen ist, das entweder die Permutation A oder die Permutation B bewirkt, daß das Zugriffssteuerwerk im wesentlichen aus einem Permutationsstatusregister SAR zum Kennzeichnen des aktuellen Permutationszustandes mit Hilfe des Binärcodes der Adresse, deren Inhalt sich im Lesekopf befindet und einem Speicheradressregister MAR zum Aufnehmen des Binärcodes der Adresse, deren Inhalt anschließend zu lesen oder zu schreiben ist, besteht, und daß den

609826/0057

245947S

Registern MAR und SAR ein logisches Vergleichsnetzwerk zum Erzeugen der kürzesten Permutationssequenz zum Transferieren des Zellinhaltes einer vorbestimmten Speicherzelle in den Schreib-Lesekopf nachgeschaltet ist.

Dabei ist es zweckmäßig, daß jede Speicherzelle einen ersten und einen zweiten Dateneingang zum übernehmen eines Datums und einen ersten und einen zweiten Datenausgang zum Abgeben eines in der Speicherzelle gespeicherten Datums besitzt, daß jede Speicherzelle einen Steuereingang zum Eingeben eines L-Signales und dadurch zum öffnen des ersten Dateneinganges und des ersten Datenausganges oder zum Eingeben eines O-Signales und dadurch zum öffnen des zweiten Dateneinganges und des zweiten Datenausganges besitzt, daß jede Speicherzelle eine Einrichtung zum Aufnehmen von den Datentransfer bewirkenden Synchronisationstakten besitzt, und daß bei den Speicherzellen der Ebenen 0 und k-1 der erste Datenausgang auf den ersten Dateneingang oder der zweite Datenausgang auf den zweiten Dateneingang der gleichen Speicherzelle geschaltet ist.

Bei einer vorteilhaften Weiterbildung der erfindungsgemäßen Schaltungsanordnung ist das Permutationsnetzwerk gebildet aus einer Speicherkapazität von 2(2 -1) Zellen, die gleichmäßig auf zwei baumartige Speichernetzwerke so verteilt sind, daß das erste Netzwerk alle Zelladressen enthält, in deren Binärcode das Bit mit der Wertigkeit 2 eine O führt und das zweite Netzwerk alle Zelladressen enthält, deren Binärcode an dieser Stelle eine 1 hat und daß eine vom Zugriffssteuerwerk betriebene Auswahlschaltung automatisch die Verbindung zu einem der beiden Leseköpfe der Speichernetzwerke herstellt.

Bei einer anderen vorteilhaften Ausgestaltung der Erfindung besteht das Zugriffssteuerwerk im wesentlichen aus einem als Vorwärts-Rückwärtsschieberegister ausgebildeten Speicheradressregister MAR mit k Binärstellen zum Laden des aus k + 1 Bits

609826/005 7

bestehenden Adressencodcs, ausgenommen aas Bit mit der Wertigkeit 2, einem einstelligen Oberlaufregister HM_r das mit dem Speicheradressenregister MAR zu einem Ringschieberegister zusammengeschaltet ist, einem einstelligen Register MPF zum Aufnehmen des Bits der Wertigkeit 2 der Adresse, einem als Vorwärts-Rückwärtsschieberegister ausgebildeten Permutationsstatusregister SAR mit k Binärsteilen, das in jedem Permutationszustand den Binärcode der Adresse der Speicherzelle - ausgenommen das Bit der Wertigkeit 2 - enthält, deren Inhalt sich im Lesekopf des ersten Netzwerkes befindet, einem einstelligen Überlaufregister HS, das beim Rechtsshift des Permutationsstatusregisters SAR dessen Bit der Wertigkeit 0 übernimmt, wobei im überlaufregister HS der vor der Übernahme vorhandene Inhalt gelöscht wird und das beim Linksshift des Permutationsstatusregisters SAR seinen Inhalt an das Bit der Wertigkeit O in SAR abgibt und den Inhalt des überlaufregisters HM übernimmt, einem Vorwärts-Rückwärtsschieberegister SPR mit k Binärstellen, das einen Zeiger der Form enthält, daß nur eine Binärstelle den Wert 1 führt und alle anderen Binärstellen den Wert 0 führen, einem einstelligen Register SFF zum Kennzeichnen der zuletzt ausgeführten Permutation A mit 1 oder der Permutation B mit 0, einem einstelligen Register MHF zum Kennzeichnen der ersten Permutation A mit 1 oder B mit 0 der für den Zugriff auf die in MAR enthaltene Adresse erforderlichen Permutationssequenz, einem einstelligen Register SHF zum Anzeigen der ersten Permutation A mit^1 oder B mit 0 der für den Inhalt des Permutationsstatusregisters SAR notwendigen Permutationssequenz, einem einstelligen Steuerregister HH zum Duplizieren des Inhaltes des überlaufregisters HS, einem m-stelligen Zählregister CNT zum Zählen der mit dem Speicheradressregister MAR ausgeführten Rechtsshifts durch Hochzählen und der Linksshifts durch Herunterzählen, einem Schieberegister DEL mit drei Binärstellen, dessen Inhalt mit jeder Permutation nach rechts shiftet, in dessen linker Binärstelle eine Permutation A mit 1, eine Permutation B mit 0 markiert ist und von dessen rechter Binärstelle nach zwei Permutationstakten das Steuersignal für die Permutationen im Netzwerk 2 abgreifbar ist, einem Schieberegister READ, dessen Inhalt mit jeder Permutation nach rechts shiftet

- 6 -609826/0057

und dessen linke Binärstelle auf 1 gesetzt ist_f wenn das Register MFF eine 1 führt, die Inhalte des Speicheradressregisters MAR und des Permutationsstatusregisters SAR deckungsgleich sind und bei einer 1 in der rechten Binärstelle der Lesekopf des Netzwerkes 2 angesteuert ist, einem logischen Netzwerk COMP zum Auswerten der Inhalte des Speicheradressregisters MAR, des Permutationsstatusregisters SAR und des Zeigerregisters SPR und zum Erzeugen von Steuersignalen sowie einem internen Leitwerk zum Ausführen der für das Steuern der Register und der Permutationen erforderlichen Mikroprogramme,

Die mit dem erfindungsgemäßen Permutationsnetzwerk für dynamische Speicher erzielbaren Vorteile bestehen darin, daß gegenüber

k k

Speichern gleicher Kapazität von 2 bzw. 2 -1 Zellen mit zyklischer Datenpermutation die Zugriffszeit zu einem beliebigen

k-1
Datum drastisch von im Mittel 2 Permutations takten auf höchstens 3k Permutationstakte verkürzt wird, daß der Transfer einer Speicherseite mit 2" aufeinanderfolgenden Zellinhalten genau m+3(2^g -1) Permutationstakte in Anspruch nimmt, wobei m — 2(k-g) ist, und daß gegenüber bekannten Permutationsnetzwerken, mit denen Zugriffszeiten der gleichen Größenordnung erzielbar sind, das erfindungsgemäße Netzwerk aufgrund seiner planaren, kreuzungsfreien Struktur , bei der nur Verbindungen zwischen unmittelbar benachbarten Zellen erforderlich sind, technologisch erheblich einfacher zu realisieren ist.

Ein Ausführungsbeispiel der Erfindung ist in der Zeichnung dargestellt und wird im folgenden näher beschrieben. Es zeigen : ·

Fig. 1 Schematische Darstellung einer Speicherzelle, Fig. 2 Struktur eines Speichernetzwerkes,

Fig. 3 Permutationsnetzwerk aus zwei simultan betriebenen Speichernetzwerken ,

Fig. 4 Blockdiagramm des ZugriffsSteuerwerkes, Fig. 5 Schaltbild der Vergleichslogik des ZugriffsSteuerwerkes.

«· 7 —

609826/0057

Im Falle eines zyklisch permutierenden Speichers, also eines

k k

dynamischen Schieberegisterspeichers werden 2 von 0 bis 2 -1 numerierte Speicherzellen so miteinander verbunden, daß der Ausgang der Zelle i auf den Eingang der Zelle i+1 und der Ausgang der Zelle 2 -1 auf den Eingang der Zelle O, die als Schreib-Lesekopf dient, geführt ist. Bei der Ausführung einer Permutation geben alle Zellen gleichzeitig,-ihre.,Inhalte an die jeweils in der Verbindungsstruktur nachfolgenden Zellen ab. Um den Inhalt der Zelle i in den Schreib-Lesekopf zu überführen, sind demnach 2 -i zyklische Permutationen erforderlich. Daraus folgt, daß die

k-1 mittlere Zugriffszeit zu einer Zelle 2 Permutationen, also einer halben Umdrehung des ringförmig geschlossenen Schieberegisters entspricht, d.h. die mittlere Zugriffszeit ist direkt proportional der Speicherkapazität.

Eine prinzipielle Verkürzung dieser mittleren Zugriffszeit kann dadurch erzielt werden, daß die zyklische Verbindungsstruktur durch ein wesentlich komplexeres Netzwerk ersetzt wird, bei dem einige oder alle Zellen durch externe Steuersignale wahlweise mit je einer von mehreren Vorgängerzellen, deren Inhalt übernommen wird, sowie mit je einer von mehreren Nachfolgerzellen, an die gleichzeitig der gegenwärtige Inhalt abgegeben wird, verbunden werden können. Dadurch wird es möglich, wesentlich kürzere Wege zwischen einer vorbestimmten Zelle und dem Schreib-Lesekopf zu schalten als bei einer rein zyklischen Permutation und damit die Anzahl der auszuführenden Permutationen entsprechend zu reduzieren. Aus.Gründen der Informationserhaltung muß jede Zelle, die den Inhalt einer ersten anderen Zelle aufnimmt, auch gleichzeitig ihren Inhalt an eine zweite andere Zelle abgeben und umgekehrt. Daraus folgt zwangsläufig, daß jede Zelle während jeder Datenpermutation Glied eines Zyklus sein muß, daß jedoch im Gegensatz zur o.a. einen zyklischen Permutation, der alle Zellen gleichzeitig angehören, eine Zelle alternativ mehreren kleinen Permutationszyklen angehören kann, deren Anzahl bestimmt ist durch die größere Zahl von Eingangs- bzw. Ausgangsverbindungen der Zelle, von denen jedoch höchstens eine Permutation pro Zelle ausgeführt werden darf.

- 8 609826/0057

2459Α7Θ

Ικι Hinblick auf eine technologische Realisierung mit vertretbarem Aufwand sind Speicherzellen mit höchstens zwei Eingängen und zwei Ausgängen als sinnvoll zu betrachten. Eine solche Speicherzelle ist in Fig. 1 schematisch dargestellt. Die eigentliche Datenspeicherung findet in der Speicherzelle FF statt. Der Eingangsschalter ES und der Ausgangsschalter AS werden über eine Steuerleitung SL simultan durch ein binäres Steuersignal C so geschaltet, daß im deaktivierten Fall (d.h. C=O) die Zelle FF den Inhalt der dem Eingang E1 vorgeschalteten Speicherzelle übernimmt, und ihren gegenwärtigen Inhalt an die dem Ausgang A1 nachgeschaltete Speicherzelle abgibt, während im Falle des aktivierten Schalters (d.h. C=T) Information von Eingang Ξ2 übernommen, und über Ausgang A2 abgegeben wird.

Eine solche Speicherzelle bildet den Grundbaustein eines sich baumartig verzweigenden Speichernetzwerkes, dessen Struktur schematisch in Fig. 2 dargestellt ist. Die Speicherzellen sind in fortlaufend numerierten Ebenen angeordnet, wobei die Ebene 0 eine Speicherzelle, die als Schreib-Lesekopf benutzt wird, und jede Ebene 2¹ Speicherzellen enthält. Die Verbindungsstruktur zwischen den Zellen ist derart aufgebaut, daß jede Zelle einer Ebene i im Bereich 1 ^ i ^ k-2, wobei k-1 der Index der höchsten Ebene des Baumes ist, je eine eingangsseitige und ausgangsseitige Nachbarzelle in der Ebene i+1 hat. Entsprechend der in Fig. 2 gezeigten Zellnumerierung hat außerdem jede geradzahlige Zelle in der Ebene i eine eingangsseitige Nachbarzelle in der Ebene i sowie eine ausgangsseitige Nachbarzelle in der Ebene i-1, und jede ungeradzahlige Zelle in i eine ausgangsseitige Nachbarzelle in i, sowie eine eingangsseitige Nachbarzelle in i-1. Die Eingänge und Ausgänge der Speicherzellen sind so geschaltet, daß jede Zelle einer Ebene i im Bereich 1 ^ i £ k-2 entweder mit den beiden in der Ebene i+1 befindlichen Nachbarzellen oder mit den in den Ebenen i bzw. i-1 befindlichen Nachbarzellen zu einem im Uhrzeigersinn ablaufenden Permutationszyklus verbunden werden kann, der insgesamt drei Zellen umfaßt. Da der Schreib-Lesekopf keine Nachbarzellen

609826/0057

2459470

in einer nächstniederen Ebene und die Zellen der Ebene k-1 keine Nachbarζeilen in einer nächsthöheren Ebene haben, nehmen diese Zellen nur an jeweils einem Permutationszyklus teil, d.h. bei Ausführung des jeweils anderen Permutationszyklus bleiben die Inhalte dieser Zellen erhalten. Um die. insgesamt im Speichernetzwerk möglichen Permutationszustände und die damit verbundene Komplexität des Zugriffssteuerwerkes gering zu halten, werden die Dreierpermutationen, die alle Zellinhalte in Ebenen mit geradzahliger Numerierung mit den Inhalten der jeweils zugeordneten Zellen in den nächsthöheren ungeradzahlig numerierten Ebenen austauschen, simultan als eine erste Permutation A ausgeführt, und die Dreierpermutationen, die alle Zellinhalte in Ebenen mit ungeradzahliger Numerierung mit den Inhalten der zugeordneten Zellen in den nächsthöheren geradzahlig numerierten Ebenen austauschen, simultan als eine zweite Permutation B ausgeführt. Bei entsprechender Orientierung der Ein- und Ausgänge der Speicherzellen ist es möglich, diese Permutationen durch eine einzige Steuerleitung S, die mit den Steuereingängen aller Zellen verbunden ist - in Fig. 2 dargestellt durch die unterbrochene Linie - derart zu manipulieren, daß bei deaktivierter Steuerleitung S(C=O) die Permutation B, und bei aktivierter Steuerleitung S(C=D die Permutation A im gesamten Netzwerk ausgeführt wird.

Eine wichtige Eigenschaft diesös Permutationsnetzwerkes, die von entscheidender Bedeutung für dessen Steuerung ist, besteht darin, daß - ausgehend von einem aktuellen Permutationszustand P, der durch eine beliebige Aufeinanderfolge von Permutationen A und B zustande gekommen ist - eine dreifache Ausführung ein und derselben Permutation, d.h. eine Sequenz PAAA oder PBBB wieder auf den ursprünglichen Permutationszustand P zurückführt. Diese Eigenschaft, die unmittelbar aus dem in Dreierzyklen aufgebauten Netzwerk herzuleiten ist, kann auf einfache Weise dazu benutzt werden, einen beliebigen Permutationszustand in den Ausgangszustand 0 , bei dem jede Zelle den ihr ursprünglich zugeordneten Inhalt zurückerhält, zurückzuversetzen.

- 10 -

609826/005 7

2459473 M.

Ist das in Fig. 2 dargestellte Speichernetzwerk in der Ausganqslage 0 und soll z.B. der Inhalt der Speicherzelle 22¹ in den Schreib-Lesekopf gebracht werden, so ist zunächst einmal die Permutation B, danach zweimal die Permutation A, danach zweimal die Permutation B, und einmal die Permutation A auszuführen, also insgesamt die Sequenz BAABBA. Wie aus Fig. 2 folgt, erfordert andererseits die überführung des Inhaltes des Schreib-Lesekopfes in die Zelle 22' die komplementäre Permutationssequenz AABABB. Eine Konkatenation der von Zelle 22' nach Zelle 1' führenden Permutationssequenz und der von Zelle 1' nach Zelle 22· führenden Permutationssequenz führt zu

BAABBAAABABB

Die konsequente Anwendung der Regel, daß drei aufeinanderfolgende gleichartige Permutationen sich kompensieren, und deshalb aus der Permutationssequenz herausgestrichen werden können (was durch die VerbindungsSymbole dargestellt ist), zeigt, daß die oben angegebene Sequenz auf den Ausgangszustand 0 des Netzwerkes zurückführt. Daraus folgt unmittelbar die nach dem Zugriff auf einen bestimmten Zellinhalt für die Wiederherstellung des Ausgangszustandes erforderliche PermutationsStrategie: die für den Hintransport zum Lesekopf notwendige Permutationssequenz wird dadurch schrittweise wieder abgebaut, daß - beginnend mit der zuletzt ausgeführten Permutation - alle angewandten Permutationen in umgekehrter Reihenfolge zu drei aufeinanderfolgenden Permutationen gleichen Typs ergänzt werden. Daraus folgt gleichzeitig, daß der Zugriff zu einem Zellinhalt in der Ebene i und die unmittelbar darauffolgende Wiederherstellung des Ausgangszustandes genau 3i Permutationen, d.h. im ungünstigsten Falle bei k Ebenen genau 3(k-1) Permutationen erfordert.

In vielen Fällen ist es jedoch nicht notwendig, den ursprünglichen Permutationszustand wiederherzustellen, wenn nämlich zwei aufeinanderfolgende Zugriffe auf Zellen erfolgen, für deren

r 11 τ
6 0 9 8 2 6/0057

2459478

erste eine Perrautationssequenz PQ₁ und für deren zweite eine Perrautationssequenz PQ₉ erforderlich ist, wobei Q₁ und Q- verschieden sind, und ebenso wie P eine beliebige Reihenfolge von Permutationen A und B darstellen. In einem solchen Falle braucht nach dem Zugriff auf die erste Speicherzelle der Permutationszustand durch Komplementieren der Teilsequenz Q₁ nur bis auf P abgebaut, und danach durch Q„ ergänzt zu werden.

Soll z.B. zuerst auf den Inhalt der Zelle 22' und danach auf den Inhalt der Zelle 26' zugegriffen werden, so wird zunächst die Sequenz BAABBA ausgeführt. Da der Zugriff zu Zelle 26' die Sequenz BAABAA erfordert, und diese Sequenz mit derjenigen für Zelle 22* bezüglich der ersten vier Permutationen BAAB übereinstimmt, wird insgesamt folgendermaßen permutiert:

BAABBAAABBAA

γ—τ

(die sich kompensierenden Permutationen sind unterstrichen). Dadurch wird die Sequenz auf insgesamt zwölf Permutationen verkürzt gegenüber vierundzwanzig Permutationen bei Wiederherstellung des Ausgangszustandes nach dem Zugriff auf Zelle 22*.

Der aufeinanderfolgende Zugriff auf zwei Zellen kann mit einer derart verkürzten Sequenz nur dann erfolgen, wenn mindestens die erste Permutation beider Sequenzen gleich ist, d.h. wenn beide Zellen entweder auf Ebenen mit geradzahligem oder mit ungeradzahligem Index liegen. Im Falle der Ungleichheit der ersten Permutation muß nach dem Zugriff auf die erste Zelle der Ausgangszustand wiederhergestellt werden, bevor der Zugriff auf die zweite Zelle erfolgen kann. Da nur die Permutation A den Inhalt des Lesekopfes ändert, ist diese immer die letzte Permutation einer Zugriffssequenz. Permutationssequenzen für den Zugriff auf Zellen der gleichen Ebene zeichnen sich dadurch aus, daß sie mit der gleichen Permutation beginnen und die gleiche

- 12 -

609826/0057

2459478

Anzahl von Wechseln zwischen A und B aufweisen, wobei bei jedem Wechsel zwischen A ΐΐηα B bzw. B und A der gewünschte Zellinhalt in eine Ebene mit niedrigerem Index übergeht, d.h. dichter an den Schreib-Lesekopf heranbewegt wird.

Zur überbrückung einer Ebene müssen mindestens eine, aber höchstens zwei Permutationen gleichen Typs ausgeführt werden. Die kürzeste Zugriffssequenz auf eine Zelle einer vorgegebenen Ebene ist demnach dadurch gekennzeichnet, daß sowohl Ä als auch B alternierend genau je einmal ausgeführt werden, während die längste Zugriffssequenz zu einer Zelle derselben Ebene gekennzeichnet ist dadurch, daß sowohl A als auch B alternierend genau je zweimal nacheinander ausgeführt werden. In Fig. 2 wird z.B. mit der kürzesten Sequenz für die Ebene 4, nämlich BABA, auf die Zelle 16^f zugegriffen, während mit der längsten Sequenz, nämlich BBAABBAA, der Inhalt der Zelle 3Ί' in den Schreib—Lesekopf transportiert wird.

Zur Vereinfachung des Zugriffssteuerwerkes wird der Permutationsspeicher so betrieben, daß der jeweils effektive Permutationszustand aus einer Permutationssequenz resultiert, die nach Streichung aller untersequenzen AAA oder BBB höchstens so viele Wechsel zwischen A und B enthält wie zum Zugriff auf Zellen der höchsten Ebene des Netzwerkes notwendig sind. Dies bedeutet, daß für das Hetzwerk der Fig. 2, das nur fünf Ebenen besitzt, zwar eine Sequenz BBABAA, die auf die Zelle 25* zugreift, erlaubt, aber eine Sequenz 3BABAABA, die auf die Zelle 9* zugreift, verboten ist, da der Zugriff auf Zelle 9* mit der wesentlich kürzeren Sequenz AABA erfolgen kann

Wenn unter dieser Einschränkung auf alle 2¹ Zellen einer Ebene i mit der kürzest möglichen Permutationssequenz zugegriffen werden soll, dann muß eine Strategie angewendet werden, bei der der gesamte zwischen dem Lesekopf und der Ebene i liegende Baum derart traversiert wird, daß die insgesamt auszuführende Anzahl der Permutationen genau der Anzahl der Verbindungskanten in diesem Baum entspricht. Diese Strategie wird anhand der Fig.

- 13 —

609826/0057

2459478

für den Zugriff auf alle Speicherzellen der Ebene 3 erläutert. Die kürzeste Sequenz, mit der z.B. die Speicherzelle 8¹ dieser Ebene erreicht werden kann, ist ABA. Ausgehend von dieser Sequenz kann die Speicherzelle 12* dieser Ebene unmittelbar durch Ausführung einer v/eiteren Permutation A_f also insgesamt durch die Sequenz A3AA erreicht werden. Die Fortsetzung dieser Sequenz sowohl rait A als auch mit B führt zu einer mit B endenden Sequenz, d.h. in keinem der beiden Fälle erscheint im Lesekopf der Inhalt einer weiteren Speicherzelle der S>ene 3, Im ersten Fall wird jedoch die Sequenz effektiv auf AB verkürzt, wonach durch einmalige Anwendung der Permutationen BA. eine resultierende Sequenz ABBA entsteht, die dem Lesekopf wieder einen Speicherzellinhalt der Ebene 3 zuführt. Auf die nächstfolgende Speicherzelle %Q^f kann nun wiederum unmittelbar durch eine weitere Permutation A, die die Sequenz auf ÄBBÄA verlängert, zugegriffen werden. Nachdem mit einer dritten Permutation A die Sequenz wieder auf ABB verkürzt wird, kann nunmehr nur durch die Permutationen BABA ein weiterer Speicherzellinhalt der Ebene 3 in den Lesekopf gebracht werden, auf den bisher noch nicht zugegriffen worden ist. Aus der konsequenten Fortsetzung dieses Schemas ergibt sich allgemein für den Zugriff auf die Speicherzellen einer Ebene i, daß zunächst die kürzest niögliche Permutationssequenz angewendet wird, daß die erste Permutation A_r die einen Speicherzellinhalt der Ebene i in den Lesekopf bringt, zu drei Permutationen AAA ergänzt wird, und daß danach die Zweiersequenz BA so oft angewendet wird, bis wiederum ein Zellinhalt der Ebene i im Lesekopf erscheint. D>anach wird wieder wie oben fortgefahren, bis die gesamte Permutationssequenz wieder auf den Ausgangszustand 0 zurückgeführt ist. Bd e vollständige Permutationssequenz für den Zugriff auf alle Zellinhalte der Ebene 3 in der Baumstruktur Fig. 2 ist in der nachfolgenden Tabelle dargestellt, die gleichzeitig die Adressen der Zellen auflistet, deren Inhalte sich nach Ausfüiirraig der korrespondierenden Permutationssequenzen im Lesekopf befinden.

- 14 -

609826/0057

2459478

Sequenz Adr. Sequenz Adr.

A	2¹
AB	2«
ABA	8«
ABAA	12«
ABAAA	2¹
ABB	2'
ABBA	10'
ABBAA	14·
ABBAAA	.2"
ABBB	2«

AA	3¹
AAB	3¹
AABA	9¹
AABAA	13'
AABAAA	3¹
AABB	3¹
AABBA	11 ·
AABBAA	15·
AABBAAA	3'
AABBB	3«
AAA "	1 '

Mit dem Symbol + sind alle diejenigen Sequenzen gekennzeichnet, die entweder den Inhalt des Lesekopfes nicht ändern bzw. bei denen der Inhalt des Lesekopfes nicht dem einer der Speicherzellen der Ebene 3 entspricht.

Die Tabelle zeigt, daß bei dieser Permutationssequenz höchstens zwei Zellinhalte der gewünschten Ebene durch unmittelbar aufeinanderfolgende Permutationen in den Lesekopf gebracht werden, und daß diesen beiden Permutationen mindestens zwei weitere folgen, bei denen der Lesekopfinhalt nicht mit dem aus einer der Zellen der Ebene 3 übereinstimmt. Dies gilt, wie sich aus Fig. 2 ergibt, für alle Ebenen. Die Anzahl der für die Ebene 3 insgesamt ausgeführten Permutationen ist 21, dies entspricht genau der Anzahl der in dem Baum zwischen dem Lesekopf und. der Ebene 3 vorhandenen Kanten, die durch die angegebene Permutationssequenz vom ursprünglichen Inhalt des Lesekopfes genau je einmal im Uhrzeigersinn durchlaufen werden. Allgemein gilt demnach, daß die' kürzest mögliche Permutatxonssequenz für den Zugriff auf alle 2 Zellen der Ebene i genau 3(2 -1) Permutationen verlangt.

Die Permutationseigenschaften der in Fig. 2 dargestellten Speicherstruktur können besonders vorteilhaft in einem sogenannten "paging" System eingesetzt werden, bei dem der virtuelle Speicherraum durch einen dynamischen Speicher realisiert wird. Beim "paging" werden jeweils Datenblöcke, die dem Inhalt von 2⁹ fort-

- 15 -

609826/0057

laufend adressierten Speicherzeilen, deren erste eine Adresse η 2r haben muß, entsprechen, zwischen dem (virtuellen) dynamischen Speicher und dem (reellen) Arbeitsspeicher des Systems transportiert. Ein solcher Datenblock, auch Seite oder "page" genannt, kann in den 2^g Zellen der Ebene g der angegebenen Speicherstruktur abgespeichert werden. Da jede Zelle der Ebene g ihrerseits jeweils Wurzel eines k-g Ebenen tiefen Unterbaumes

Y-Q

einer Kapazität von 2^{V y}-1 Zellen ist, können in dem gesamten Speicher 2 ~^g-1 vollständige Seiten derart abgespeichert werden, daß zur gleichen Seite gehörige Daten sich in jeweils den gleichen Zellen dieser Unterbäume aufhalten, wenn der Speicher sich im Ausgangszustand 0 befindet. Zwischen den Ebenen 0 und g-1 ist eine unvollständige Seite von 2^-1 Zellen untergebracht. Jede vollständige Seite kann demnach durch eine sogenannte Prefix-Sequenz, die im konventionellen Sinne der Seitenadresse im virtuellen Speicher entspricht, in die Ebene g permutiert, und von dort nach dem angegebenen minimalen Algorithmus gelesen bzw. beschrieben werden. Da diese Zugriffssequenz gewöhnlich nach fortlaufenden Zelladressen erfolgt, ist es zweckmäßig, die Zelladressen gegenüber der in Fig. 2 angegebenen Numerierung entsprechend zu ändern.

Die Eigenschaft der für den Zugriff auf eine in der Ebene g positionierte Seite der Länge 2^ erforderliche Permutationssequenz, daß je zwei aufeinanderfolgende Permutationen, die einen Zellinhalt dieser Seite in den Lesekopf transportieren, unmittelbar gefolgt werden von mindestens zwei Permutationen, die dem Lesekopf nicht benötigte Daten zuführen, wird genutzt, um ohne wesentliche Erweiterung des Zugriffssteuerwerkes die insgesamt zur Verfügung stehende Speicherkapazität sowie die Datenzugriffsrate beim "paging" zu verdoppeln. Dies geschieht dadurch, daß zwei Permutationsnetzwerke gleicher Kapazität simultan derart betrieben werden, daß die dem ersten Netzwerk •zugeführte Permutationssequenz mit genau zwei Permutationstakten

- 16 -

609826/0057

Verzögerung auch auf «las zweite Netzwerk angewendet wird. Die Ausführung der für den sequenziellen Zugriff auf die Zellen' der Ebene g erforderlichen Permutationssequenz führt dann dazu, daß während der unmittelbar nach dem Zugriff auf zwei Zellinhalte der Ebene g des ersten Wetzwerkes entstehende Lücke von mindestens zwei Permutationstakten im Lesekopf des zweiten Netzwerkes genau zwei Zellinhalte von dessen Ebene g erscheinen. Bei entsprechender Numerierung der Zellen in den beiden Netzwerken kann demnach auf genau acht fortlaufend numerierte Zellen in unmittelbarer Aufeinanderfolge zugegriffen werden, bevor eine Zugriffslücke entsteht. Dadurch wird die Zugriffsrate verdoppelt, d.h. gegenüber dem einfachen Netzwerk werden für den Zugriff auf die 2^ Zellen einer Seite, die nunmehr je zur Hälfte in den Ebenen g-1 der beiden simultan betriebenen

er—1

Netzwerke untergebracht sind, genau 3(2^J -1) Permutationstakte benötigt.

Die Fig. 3 zeigt schematisch ein solches Permutationsnetzwerk in Tandem-Baumstruktur, dessen Zellen fortlaufend so numeriert sind, daß bei Anwendung einer kürzesten Permutationssequenz. für eine Ebene i die Zellinhalte in der Reihenfolge monoton wachsender Adressen alternierend in dem jeweiligen Lesekopf erscheinen. Das Entwicklungsgesetz für diese Numerierung ist dadurch gegeben, daß im Netzwerk I, beginnend mit der Ebene i=1, jede Zelle in einer Ebene i mit einer Adresse x. je einen Nach-

i+1 i+2 barn in der Ebene i+1 mit den Adressen x.+2 und x.+2 hat.

Im Netzwerk II sind die korrespondierenden Zelladressen jeweils um 2 höher. Daraus ergibt sich unmittelbar, daß - abgesehen von der Adresse des jeweiligen Lesekopfes - die Binärcodes der Adressen im Netzwerk I im Bit mit der Wertigkeit 2 eine Null und im Netzwerk II alle Adressen an dieser Stelle eine 1 haben. Aus dieser Zuordnung der Zelladressen und den für den Zugriff auf die jeweiligen Zellen notwendigen Permutationssequenzen läßt sich der Aufbau und die Funktion des zum Betrieb des Speichers notwendigen Zugriffswerkes herleiten.

■- 17 609826/0057

2459473

Die funktionell wesentlichen Bestandteile eines solchen Zugriffs Steuerwerkes sind als Blockdiagramm in Fig. 4 dargestellt. Ein PermutationsStatusregister SAR stellt den aktuellen Permutations zustand des Netzwerkes in binärcodierter Form dar. In ein Speicheradressregister MAR wird die jeweils gewünschte Adresse der Zelle, deren Inhalt als nächster in den Lesekopf transportiert werden soll, geladen. Ein logisches Netzwerk erzeugt, unterstützt von einigen Hilfsregistern, aus einem Vergleich der Inhalte von MAR und SAR die für den Transport notwendige Permutationssequenz und die entsprechende Steuersignalfolge.

Aus der Verteilung der Adressen über die beiden simultan betriebenen Netzwerke wird unmittelbar klar, daß das Adressbit mit der Wertigkeit 2 insoweit eine Sonderstellung einnimmt, als es für die Herleitung der Permutationssequenz nicht erforderlich ist, da Adressen, die sich nur in diesem Bit unterscheiden, jeweils die gleiche Permutationssequenz erfordern. Dieses Bit ist lediglich notwendig, um dann, wenn der geforderte Zellinhalt im Lesekopf des jeweiligen Netzwerkes erscheint, die Auswahl vorzunehmen, über welchen Lesekopf zuzugreifen ist. Definitionsgemäß ist dies im Falle einer 0 der Lesekopf des Netzwerkes I, und im Falle einer 1 der Lesekopf des Netzwerkes II. Das Adressbit der Wertigkeit 2 wird deshalb nicht in das Register MAR, sondern in ein einstelliges Register MFF geladen.

Die für die Beschreibung des Permutationszustandes des Netzwerkes geeignete. Codierung wird aus der Tatsache gewonnen, daß aufgrund der o.a. Beschränkung der zulässigen Permutationssequenzen jeder Zellinhalt mit nur einer Permutationssequenz in den Lesekopf gelangen kann. Zur Angabe des Permutationszustandes eines 2 -1 Zellen umfassenden Baumnetzwerkes genügt demnach ein k-stelliges Register, das in binärcodierter Form die Adresse der Zelle enthält, deren Inhalt sich gerade im Lesekopf befindet. Im Falle des Permutations-Netzwerkes in Tandem-Struktur, dessen Gesamtkapazität 2(2 -1) Zellen umfaßt, genügt ebenfalls ein k-stelliges Register, da hier - wie im Falle

- 18 -

609828/00-57

1	Ό	\|0\|	O
	I		I
11	O		1

des Adressregisters - das Bit der Wertigkeit 2 irrelevant ist. Das Steuerproblem des Netzwerkes reduziert sich dann darauf, durch geeignete Permutationen den Inhalt des Registers SAR mit dem des Registers MAR zur Deckung zu bringen.

Der dafür notwendige Algorithmus und dessen schaltungstechnische Implementierung ergibt sich aus der Beziehung zwischen den Binärcodes der Zelladressen und den für den Zugriff auf die Zellen notwendigen Permutationssequenzen. Dieser Zusammenhang soll anhand von zwei Beispielen erläutert werden. Der Zugriff auf die Zelle 56, die sich im Netzwerk I des in Fig. 3 dargestellten Tandem-Speichers befindet, erfolgt - wie leicht aus der Struktur folgt - mit der Sequenz BBAABA. Wenn vereinbarungsgemäß die Permutation A durch eine 1 und die Permutation B durch eine 0 codiert wird, so ergibt sich folgender Zusammenhang zwischen Adresscode und Permutationscode :

■ -■ ■■'!

Adresscode 1 1

Permutationscode 00

Das höchstwertige Bit 1 im Adresscode, im folgenden auch Pilotbit genannt, identifiziert die Ebene, auf der sich die adressierte Zelle befindet, und damit die erste auszuführende Permutation. In diesem Falle gehört die Zelle der Ebene 4 an, die erste Permutation ist demnach B, dargestellt durch 0 im Permutationscode. Die Anzahl der Bits rechts vom Pilotbit, ausgenommen das umrahmte Bit der Wertigkeit 2, gibt die um 1 erhöhte Anzahl der erforderlichen Wechsel zwischen den Permutationen A und B an, da jedes Bit eine Ebene im Baum darstellt. Im Beispiel sind, beginnend mit der Permutation B, drei Wechsel, nämlich BABA, erforderlich. Damit wird auch die Korrespondenz zwischen den Bits im Adresscode und denen im Permutationscode offensichtlich. Ist das Adressbit 1, dann wird die zugehörige Permutation zweimal ausgeführt, ist das Adressbit jedoch 0, dann nur einmal. Dies zeigt auch das Beispiel für den Zugriff

- 19 60982 6/0057

auf die Zelle 39, die im Netzwerk II liegt, mit Hilfe der ^Sequenz BABBAA.

Adresscode : 1 0 0 1 [T] 1

I I JL _L Permutationscode : 0 1 00 11

Das Pilotbit im Adresscode zeigt wieder auf die vierte Ebene, d.h. die erste Permutation muß B sein. Da das erste Bit rechts vom Pilotbit eine 0 enthält, wird diese Permutation nur einmal ausgeführt. Das gleiche gilt für die nachfolgende Permutation A, während die darauffolgenden Permutationen B und A jeweils zweimal ausgeführt werden müssen. Aus dieser Zuordnung des Adresscodes zu den für den Zugriff auf die jeweiligen Zellen notwendigen Permutationen ergibt sich das in Fig. 4 schematisch dargestellte Zugriffssteuerwerk.

Es enthält

ein als Vorwärts/Rückwärts-Schieberegister ausgebildetes Speicheradressregister MAR, bestehend aus k Binärstellen entsprechend einer Speicherkapazität von 2(2"-I) Zellen im Tandem-Netzwerk, in das der aus k+1 Bits bestehende Adresscode - bis auf das Bit der Wertigkeit 2 - derart geladen wird, daß das i-te Bit der Adresse in der i-ten Binärstelle des Registers steht, wobei die Binärstellen von rechts nach links numeriert sind in der Reihenfolge 0,2,3,4,... k-1, k (dies wird kurz dargestellt in der Form MAR(k:2,0));

ein überlauf-Flipflop UM, das zusammen mit dem Register MAR ein Ringschieberegister bildet derart, daß beim Rechtsshift der Inhalt der Binärstelle MAR(O) nach HM, und der Inhalt von HM nach MAR(k) übertragen wird, während umgekehrt beim Linksshift der Überlauf von MAR(k) nach HM, und dessen Inhalt nach MAR(O) geshiftet wird;

ein einstelliges Register MFF, in das das Bit der Wertigkeit 2 des Adresscodes geladen wird;

- 20 -

609826/0057

2459473

ein ebenfalls als Vorwärts/Rückwärtsschieberegister ausgebildetes Permutationsstatusregister SAR(k:2,0), das in jedem Perrautationszustand den Binärcode der Adresse der Zelle (bis auf das Bit der Wertigkeit 2) enthält, deren Inhalt sich gerade im Lesekopf des Netzwerkes I befindet;

ein einstelliges überlaufregister HS, das beim Rechtsshift des Registers SAR den Inhalt von SAR(O) übernimmt, während sein eigener Inhalt verloren geht, und das beim Linksshift seinen Inhalt an SAR(O) abgibt, während es selbst den Inhalt des Überlaufflipflops HM übernimmt;

ein Zeigerregister (Vorwärts/Rückwärtsschieberegister) SPR(k:2,O), das einen Zeiger der Form enthält, daß immer nur genau eine Binärstelle SPR(i) den Wert 1 führt, während alle anderen Binärstellen den Viert 0 führen;

ein einstelliges Register SFF, das den Typ der zuletzt erfolgten Permutation darstellt derart, daß SFF=T der Permutation A und SFF=O der Permutation B entspricht;

ein einstelliges Register MHF, in dem festgehalten wird ob die Position des Pilotbits unmittelbar nach dem Laden von MAR einer für den Zugriff auf die entsprechende Zelle auszuführenden ersten Permutation A CMHF=I) oder B (MIF=O) entspricht;

ein einstelliges Steuerregister HH, in das gegebenenfalls der Inhalt von HS dupliziert werden kann;

ein einstelliges Register SHF, in dem die erste Permutation der in SAR enthaltenen Permutationssequenz festgehalten wird;

einen m-steiligen Binärzähier CNT(m-1:0), in dem die Anzahl der mit dem Register IiAR ausgeführten Rechtsshifts und Linksshifts abgezählt v/erden kann;

einen g-stelligen Binärzähler ADCT(g-1:0), der für die fortlaufende Adressierung von Zellen einer Seite derart eingesetzt wird, daß der Zählerstand - beginnend mit dem Wert 0 - in Schritten von 1 hochgezählt wird, bis wieder der Wert 0 erreicht

- 21 - *

609826/0Q57

2459479

ist, und daß nach jedem Hochzählen der Inhalt dieses Zählers auf die letzten g Binärstellen des Speicheradressregisters MAR übertragen wird;

ein aus drei Binärstellen bestehendes Schieberegister DEL(0:2), in dessen Bit DEL(O) eine 1 eingetragen wird, falls eine Permutation A ausgeführt wird, und eine 0 falls B ausgeführt wird, dessen Inhalt mit jeder Permutation um eine Binärstelle nach rechts geshiftet wird, und von dessen Bit DBL(2) nach genau zwei Permutationstakten die Steuersignale für das Netzwerk II abgeleitet werden können;

ein Schieberegister READ(0:2), das ebenfalls mit jeder Permutation nach rechts geshiftet wird, und in dessen Bit READ(O) dann eine 1 eingeschrieben wird, falls das Flipflop MFF auf 1 gesetzt ist, und gleichzeitig die Inhalte von MAR und SAR zur Deckung gebracht worden sind, und von dessen Bit READ(2) der Lesekopf des Netzwerkes II angesteuert wird, falls es eine 1 enthält;

ein logisches Netzwerk COMP, das die Inhalte der Register MAR, SAR und SPR auswertet und verschiedene Steuersignale erzeugt; sowie ein in Fig. 4 nicht explizit dargestelltes Steuerwerk, das die für die Steuerung der Register sowie des Speichernetzwerkes notwendigen Mikroprogramme ausführt. Der Datenaustausch mit dem Steuerwerk ist im Blockdiagramm der Fig. 4 durch Pfeile S dargestellt. _v

Der aktuelle Permutationszustand des Speichernetzwerkes ist gegeben durch den Inhalt des PermutationsStatusregisters SAR, das die Adresse des gerade im Lesekopf befindlichen Zellinhaltes angibt, sowie durch den Inhalt des einstelligen Registers SIIF, das die erste Permutation der zum Erreichen dieses Zustandes notwendigen Permutationssequenz angibt. Außerdem ist im Register SFF die zuletzt ausgeführte Permutation abgespeichert. Beim Laden einer neuen Adresse in das Speicheradressregister MAR wird mit der nachfolgend beschriebenen Prozedur der Inhalt dieser Zelle in den Lesekopf des jeweiligen Speichernetzwerkes gebrachti Mit Hilfe des

- 22 -

609826/0057

£459479

logischen Netzwerkes COMP wird zunächst der in SPR geführte Zeiger auf diejenige Binärstelle gesetzt, die dem höherwertigen der beiden Pilotbits in MAR und SAR entspricht. Gleichzeitig stellt ein Signal IMAX fest, ob die Zeigerstellung mit dem Pilotbit in MAR zusammenfällt, und ein Signal KMAX, ob die Zeigerstellung mit dem Pilotbit in SAR zusammenfällt. Falls IMAX = 1 und KMAX = 0, gehört das höherwertige Pilotbit dem Register MAR an. Nunmehr wird anhand der gesetzten Zeigerstellung in SPR bestimmt, ob dieses Pilotbit auf einer Position steht, die einer Permutation A oder B entspricht, und durch entsprechendes Setzen von MHF festgehalten. Danach wird der Zeiger in SPR simultan mit dem Inhalt des Registers 14AR solange schrittweise nach rechts geshiftet bzw. in der angegebenen Form zirkuliert, bis sowohl IMAX = 1 als auch KMAX = 1. Nunmehr befinden sich die Pilotbits in MAR und SAR in der gleichen Position.

Falls dagegen im Ausgangszustand IMAX = 0 und KMAX = 1 ist, wird der Inhalt von SAR zunächst zusammen mit SPR schrittweise nach rechts verschoben. In jedem Schritt wird das in das einstellige Überlaufregister HS übernommene Bit von SAR folgendermaßen ausgewertet. Da eine 1 bedeutet, daß die in SFF angegebene Permutation zweimal ausgeführt wurde, muß zur Kompensation dieser Permutationen die gleiche Permutation genau noch einmal ausgeführt werden, um den Rechtsshift des Registers SAR auch durch eine entsprechende Verkürzung der Permutationssequenz zu verifizieren. Enthält dagegen SFF eine 0, was bedeutet, daß die betreffende Permutation nur einmal ausgeführt wurde, so muß zur · Kompensation dieser einen Permutation dieselbe genau noch zweimal ausgeführt werden. Dies geschieht unter Zuhilfenahme des einstelligen Registers HH, in das der Inhalt von HS dupliziert und dort interpretiert wird. Enthält HH eine 1, so wird nach einmaliger Ausführung die Permutation abgebrochen, enthält HH dagegen eine 0, so wird HH nach Ausführung einer ersten Permutation auf 1 gesetzt, und dieselbe Permutation noch einmal ausgeführt. Nachdem die durch SFF gekennzeichnete Permutation zu drei ergänzt und

- 23 -

609826/0057

damit die effektive Permutationssequenz entsprechend verkürzt worden ist, wird der Inhalt von SFF invertiert. Nunmehr enthält SFF die Permutation, die mit dem durch den nächsten Rechtsshift von SAR in HS übertragenen Bit korrespondiert. Dieser Rechtsshift wird zunächst schrittweise solange wiederholt, bis sowohl IMAX = 1 als auch KMAX = 1 . In dem Moment, da IMAX den Wert 1 annimmt, wird MIF gesetzt, da nunmehr die in SPR gesetzte Zeigerposition auch mit dem Pilotbit in MAR zusammenfällt. Falls die Pilotbits bereits in der Ausgangsposition zusammenfallen, entfällt das separate Shiften von MAR und SAR.

Nunmehr werden sowohl MAR als auch SAR gemeinsam mit dem Zeiger in SPR, der jetzt auf die Pilotbits in beiden Registern zeigt, nach rechts geshiftet. Dabei v/erden, wie auch vorher, die nach rechts aus MAR herauslaufenden Bits von links wieder in MAR eingeschrieben, während die nach rechts aus SAR herauslaufenden Bits nach der bereits beschriebenen Interpretation in HS und HH verlorengehen.

Falls die Inhalte der einstelligen Register MHF und SHF, die die erste Permutation der für die in MAR abgespeicherte Adresse erforderliche Permutationssequenz bzw. die erste zur Realisierung des aktuellen Permutationszustandes notwendigen Permutationssequenz angeben, gleich sind, können u.U. Teile der beiden Permutationssequenzen identisch sein. Das Netzwerk COMP vergleicht deshalb die Inhalte von SAR und MAR nach jedem Rechtsshift zwischen der Zeigerposition und der Binärstelle 0. Falls die Inhalte nicht identisch sind, wird ein weiterer Rechtsshift durchgeführt, im Falle der Identität wird das Shiften nach rechts abgebrochen.

Für den Fall, daß die Inhalte von MIlF und SHF ungleich sind, existieren keine gleichen Teilsequenzen, und der Rechtsshift von MAR, SAR und SPR muß solange wiederholt werden, bis die Zeigerposition und damit die jeweiligen Pilotbits in der Binärstelle 0 angelangt sind. Auf diese Weise ist das Netzwerk in seinen Ausgangs zustand 0 zurückversetzt.

Bei jedem Rechtsshift, an dem das Register MAR beteiligt ist, wird gleichzeitig der Binärzähler CNT um jeweils eins hochgezählt, so daß CNT am Ende des Rechtsshifts die Anzahl von Linksshifts enthält, die bezüglich MAR ausgeführt werden müssen, um die Ausgangssituation in MAR wiederherzustellen.

Im Falle MHF gleich SHF bleibt nach Abschluß des Rechtsshifts der Inhalt von SFF'erhalten, während im Falle ICIF ungleich SIIF der Inhalt von MIF auf SFF übertragen wird.

Nunmehr wird ein gemeinsamer schrittweiser Linksshift der Register MAR, SAR und SPR durchgeführt. In jedem Schritt wird das im über lauf register HM des Registers IiAR erscheinende Bit gleichzeitig auch in HS und HH übertragen, ßine 1 in HH wird umgesetzt in eine zweifache Ausführung der in SFF angegebenen Permutation, eine 0 wird umgesetzt in eine einfache Ausführung der Permutation. Nach Abschluß dieser Aktion wird der Inhalt von SFF invertiert, der Zähler CNT wird um eins heruntergezählt, und der Linksshift der Register erfolgt. Die Prozedur wird dann gestoppt, wenn der Inhalt des Zählers CNT auf 0 heruntergezählt ist, d.h. die in MAR geladene Zelladresse ihre ursprüngliche Position wieder erreicht hat. Da in jedem Schritt das in HM enthaltene Bit in HS dupliziert wurde und die entsprechenden Permutationan ausgeführt wurden, ist bei CNT=O der Inhalt von MAR und SAR identisch, und im Lesekopf des Netzwerkes I erscheint der durch die in MAR enthaltene Adresse identifizierte Zellinhalt. Falls ein Zellinhalt des Netzwerkes II adressiert wird, was durch den Status des einstelligen Registers MFF angegeben ist, so wird dann, wenn CNT auf den Wert 0 zurückgesetzt ist, eine 1 in das Verzögerungsregister READ geladen, das den Zugriff auf den Lesekopf des Netzwerkes II nach zwei weiteren Permutationszyklen freigibt.

Diese Prozedur realisiert eine minimale Perimitationssequenz, für den Zugriff auf zwei beliebige, aufeinanderfolgend adressierte Zellinhalte entsprechend dem Beispiel für den Zugriff auf die Zellen 22 und 26 des in Fig. 2 dargestellten Neztwerkes. Da die

- 25 -

609826/0057

245947Θ • 36-

Zellen des Netzwerkes der Fig. 3 so numeriert sind, daß der Zugriff auf 2^ fortlaufend numerierte Zellen minimal ist, nachdem alle Zellinhalte in die Ebenen g-1 des Tanderanetzwerkes transportiert worden sind, kann diese Zugriffsfolge in dem angegebenen Zugriffswerk dadurch erzeugt werden, daß der g-stellige Binärzähler ADCT - beginnend mit der Zählerstellung jeweils um 1 hochgezählt wird, bis wieder der Zählerstand 0 erreicht ist. Die jeweilige Sählerstellung wird in die letzten g Binärstellen des Registers MAR übertragen, woraufhin die erforderliche Permutationssequenz für den kürzest möglichen Transport des Inhaltes der adressierten Zelle in den Lesekopf ausgeführt wird. Besondere Maßnahmen für die Adressierung der Zellen des Netzwerkes II sind nicht erforderlich, wenn das Kontrollbit MFF während dieses Vorganges durchgehend auf 1 gesetzt bleibt.

Ein wesentlicher Bestandteil des Zugriffssteuerwerkes ist das logische Netzwerk COMP, das die Inhalte der Register MAR, SAR und SPR miteinander korreliert. Entsprechend den k-1 Binärstellen dieser Register enthält das Netzwerk k-1 Zellen, die kaskadenförmig miteinander derart verbunden sind, daß logische Signale von links nach rechts, d.h. von den höherwertigen nach den niederwertigen Binärstellen, propagiert werden. Eine solche Zelle, die der Binärstelle !entspricht, ist in Fig. 5 dargestellt.

Das logische Netzwerk COMP setzt unmittelbar nach dem Laden des Registers 14AR mit einer neuen Adresse die Zeigerposition in SPR derart, daß sie mit dem höherwertigen der beiden Pilotbits in MAR und SAR zusammenfällt. Weiterhin erzeugt dieses Netzwerk ein Signal IMAX, das Koinzidenz der Zeigerstellung in SPR mit dem Pilotbit in MAR, und ein Signal KMAX, das Koinzidenz der Zeigerstellung in SPR mit dem Pilotbit in SAR anzeigt. Außerdem wird mit dieser Schaltung Identität von MAR und SAR zwischen der Zeigerstellung und der Binärstelle 0 festgestellt.

- 26 -

609826/0057

2Α59Α7Θ

Zu diesem Zweck werden die Inhalte der Biriärstellen MAR(i) über eine Leitung 60 und SAR(i) über eine Leitung 61 je einem Eingang des AND-Gatters 6 2 und des EXCLUSIV-OR-Gatters 63 zugeführt werden. Gleichseitig liegt an einem dritten Eingang des AND-Gatters 62 eine allen Zellen gemeinsame Steuerleitung 64 an, die ein Signal SET führt. Ein weiteres AND-Gatter 6 5 erhält von der linken Nachbarzelle i+1 über die Leitung 6 6 ein Signal 0UT(i+1), und gleichzeitig über die Leitung 67 den invertierten Inhalt der Binärstelle SPR(I) des Zeigerregisters. Die Ausgänge der Gatter 62, 63, 6 5 sind auf die Eingänge eines OR-Gatters 68 geführt, dessen Ausgangsleitung 69 ein dem von der linken Zelle i+1 über die Leitung 6 6 empfangenen Signal OUT(i+1) entsprechendes Signal ÖUT(i) an die rechte Nachbarzelle i-1 abgibt. Gleichzeitig wird die Leitung 69 an einen ersten Eingang des AND-Gatters 70 gelegt, auf dessen zweiten und dritten Eingang die Steuerleitung 64 sowie in invertierter Form der Ausgang des AND-Gatters 65 geschaltet sind. Die Ausgangsleitung 71 des Gatters 70 wird auf den Eingang der Binärs'telle SPR(i) des Zeigerregisters SPR geführt. Das an der Ausgangsleitung 69 anliegende Signal wird gebildet durch die logische Verknüpfung OUT(i) = (MAR(i) Θ SAR(i) + MAR(i) SAR(i) SET+0UT(i+1) SPR(i)) (1) Das an der Ausgangsleitung 71 gebildete Signal entsteht durch die logische Verknüpfung "

SPR(i) = OUU? (i+1) OUT(i) SET ' (2)

Dieser Teil des Netzwerkes kann zum Setzen der initialen Zeigerr position wie folgt benutzt werden : ' "

Vor dem Setzen von SPR gilt für alle Positionen SP⁵R(I) =0, d.h. SPR(i) = 1. Beim Setzen der Zeigerposition wird das Signal SET auf logisch 1 gelegt, wodurch an der Leitung 69 gemäß Gleichung (1) das Signal OUT(i) = MAR(i) + SÄR(i) + ÖUT(i+1) anliegt. Definitionsgemäß muß der Zeiger genau in die Binärstelle i gesetzt werden, für die OUT(i+1)=0 aber OUT(I)=T ist, d.h. sowohl das Register MAR als auch das Register SAR enthält links von i nur logisch 0, aber es ist MAR(i)=1 oder SAR(i)=1. Dieser Zustand wird festgestellt durch das AND-Gatter 70, an dessen Ausgang unter der Bedingung SET=I das Signal SPR(i) = OUT(i+1) OüT(i)

- 27 -

60982 6/005 7

entsprechend Gleichung (2) anliegt, das nur für genau eine Binärstelle den Wert 1 annehmen kann. Das gesamte Signalpattern SPR(i) wird in das Zeigerregister SPR eingesetzt und dadurch die Zeigerstellung fixiert.

Nunmehr ist SPR ψ O, wird SET = O an die Leitung 64 angelegt, so führt der Ausgang 69 jeder Zelle gemäß Gleichung (1) das Signal OUT(i) = (MAR(i) Θ SAR(i) + OUT(i+1) SPR(i)). Demgemäß erscheint an dem Ausgang der Zelle 0 ein Signal 0 nur dann, wenn zwischen der aktuellen Zeigerposition SPR(i)=1 und der Position 0 für alle Binärstellen i MAR(i) θ SAR(i) = 0 ist, d.h. wenn die Zellinhalte der beiden Registersegmente MAR(i:2,0) und SAR(i:2,0) identisch sind.

Das AND-Gatter 72 verknüpft die Leitungen 67 und 60, d.h. die Zeigerstellung SPR(i) mit dem Inhalt von MAR(i) derart, daß am Ausgang des AND-Gatters 72 eine 1 immer dann anliegt, wenn sowohl MAR(i)=1 als auch SPR(i)=1 ist, wobei letzteres für genau eine Binärstelle per Definition der Fall sein kann. Dieses Signal wird über eine Schutzdiode 73 mit den entsprechenden Gatterausgängen aller anderen Zellen zu einer OR-Funktion IMAX = Σ MAR(i) SPR(i) . (3)

auf der Sammelleitung 74 hart verdrahtet.

Die gleiche Funktion wird mit Hilfe des AND-Gatters 75 und der Schutzdiode 76 auf der Sammelleitung 77 für die Inhalte der Register SAR und SPR in der Form

KMAX ~ Σ SAR(i) SPR(i) .(4)

realisiert.

Da die Inhalte von MAR und SAR vereinbarungsgemäß synchron mit der Zeigerposition in SPR geshiftet werden, sobald der Zeiger von links kommend auf die Pilotbits von MAR bzw. SAR trifft, ist IMAX =0 nur solange sich der Zeiger noch links vom Pilotbit in MAR befindet, im anderen Fall ist IMAX = 1.

- 28 -

609826/0057

245947S

Definitionsgemäß sind damit die Bedingungen für die Steuerung der Shifts in den Registern MAR und SAR festgelegt.

Zur Feststellung, ob die Position des Pilotbits in MAR eine erste Permutation A oder B erfordert, werden die geradzahligen Binärstellen des Zeigerregisters SPR über Schutzdioden auf einer weiteren, in Fig. 4 nicht gezeigten Sammelleitung SMF zu einer OR~Funktion hart verdrahtet, die immer dann ein Signal 1 führt, wenn der Zeiger mit einer geradzahligen Position zusammenfällt, und ein Signal 0, wenn der Zeiger auf,,einer ungeradzahligen Position steht. In dem Moment, in dem der Zeiger von links kommend auf das Pilotbit in MAR trifft, d.h. wenn IMAX von 0 auf 1 umschaltet, wird demnach das auf SMF liegende, die Zeigerposition indizierende Signal auf das einstellige Register MIF übertragen.

Eine andere Variante des Permutationsnetzwerkes besteht darin, in dem Tandemnetzwerk nach Fig. 3 die Steuerung des zweiten Netzwerkes derart zu verändern, daß die Permutationen B und A bezüglich der Ebenen des Netzwerkes vertauscht werden. Dadurch liefert bei synchronem Betrieb beider Teilnetzwerke das erste immer dann einen neuen Zellinhalt in den Lesekopf, wenn die Permutation A ausgeführt wird, während das zweite Netzwerk immer dann den Lesekopfinhalt ändert, wenn die Permutation B ausgeführt wird. Die Ausführung des für das "Paging" angegebenen Algorithmus in einem solchen Tandemnetzwerk führt dann dazu, daß bei entsprechender Zellnumerierung baumartig organisierte Datenstruktüren, die in geeigneter Weise abgespeichert sind, traversiert werden können nach dem sogenannten "pre-order" oder "end-order" Prinzip.

Es ist weiterhin denkbar, einem solchen dynamischen Hintergrundspeicher mit schnellem Direktzugriff auf beliebig adressierte Daten sowie schnellem sequenziellen Zugriff auf Datenblöcke, die in 2™ fortlaufend adressierbaren Zellen abgespeichert sind, einen peripheren Processor vorzuschalten, der die Zentraleinheit

- 29 -

609826/0057

2459479

von einem Teil ihrer Arbeitslast befreit, indem er diverse Aktivitäten, wie z.B. Lxstenverarbeitung u.a. Verwaltungstätigkeiten direkt mit dem Hintergrundspeicher abwickelt.
Außerdem müßte ein solcher Processor in der Lage sein, die Funktion eines Kanals anzunehmen, falls ein Datentransport zwischen dem Hintergrundspeicher und dem Arbeitsspeicher der Zentraleinheit erforderlich wird.

- 30 -

60 9 8 26/0057

Claims

Patentansprüche ;

/' \\ Schaltungsanordnung für nichtzyklische Datenpermutationen zwischen den Speicherzellen eines dynamischen Speichers nit einem Permutationsnetzwerk zum Transferieren des Inhaltes einer vorbestimmten Speicherzelle in den Schreib-Lesekopf und einen Zugriffssteuerwerk zum Erzeugen einer Permutationssequenz, dadurch gekennzeichnet, daß als Permutationsnetzwerk 2 -1 Speicherzellen in Form einer Baumstruktur in k von 0 bis k-1 numerierten Ebenen so angeordnet sind, daß die Ebene i aus 2¹ Speicherzellen gebildet ist, daß jede Speicherzelle der Ebene i mit zwei ihr benachbarten miteinander verbundenen Speicherzellen der Ebene i + 1 so verbunden ist, daß diese drei Speicherzellen ein Dreieck bilden, in dem die Inhalte der Speicherzellen im Uhrzeigersinn zyklisch vertauschbar sind, daß jede der Speicherzellen der Ebenen 1 - i - k - 2 ■ zwei Dreiecken und die als Schreib-Lesekopf dienende eine Speicherzelle der Ebene 0 und jede der Speicherzellen der Ebene k-1 nur einem Dreieck angehört, daß ein Zugriffssteuerwerk zum simultanen Transferieren der Inhalte der in geradzahlig numerierten Ebenen angeordneten Speicherzellen in zugeordnete Speicherzellen der nächsthöheren ungeradzahlig numerierten Ebenen (Permutation A) und zum simultanen Transferieren der Inhalte der in ungeradzahlig numerierten Ebenen angeordneten Speicherzellen in zugeordnete Speicherzellen der nächsthöheren geradzahlig numerierten Ebene (Permutation B) vorgesehen ist, das entweder die Permutation A oder die Permutation B bewirkt, daß das Zugriffssteuerwerk im wesentlichen aus einem Permutationsstatusregister SAR zum Kennzeichnen des aktuellen Permutationszustandes einer ersten Speicherzelle mit Hilfe des Binärcodes der Zelladresse, deren Inhalt sich im Lesekopf befindet und einem Speicheradressregister MAR zum Aufnehmen des Binärcodes der Zelladresse einer zweiten Speicherzelle, deren Inhalt anschließend zu lesen oder zu schreiben ist, besteht,

- 31 -

609826/00 5 7

245947Q

und daß den Registern MAR und SAS ein logisches Vergleichsnetzwerk zum Erzeugen der kürzesten Permutationssequenz zum Transferieren des Zellinhaltes einer vorbestimmten Speicherzelle in den Schreib-Lesekopf nachgeschaltet ist.
2. Schaltungsanordnung nach Anspruch 1, dadurch gekennzeichnet, daß jede Speicherzelle einen ersten und einen zweiten Dateneingang (E1, E2) zum Übernehmen eines Datums und einen ersten und einen zweiten üatenausgang (A1 , Λ2) zürn Abgeben eines in der Speicherzelle gespeicherten Datums besitzt, daß jede Speicherzelle einen Steuereingang zum Eingeben eines L-Signales und dadurch zum öffnen des ersten Dateneinganges (Ξ1) und des ersten Datenausganges (A1) oder zum Singeben eines O~Signales und dadurch zum öffnen des zweiten Dateneinganges (E2) und des zweiten Datenausganges (A2) besitzt, daß jede Speicherzelle eine Einrichtung zum Aufnehmen von den Datentransfer bewirkenden Synchronisationstakten besitzt, und daß bei den Speicherzellen der Ebenen 0 und k-1 der erste Datenausgang auf den ersten Dateneingang oder der zweite Datenausgang auf den zweiten Dateneingang der gleichen Speicherzelle geschaltet ist.
3. Schaltungsanordnung nach Anspruch 1 "und 2, dadurch gekennzeichnet, daß das Permutationsnetzwerk gebildet ist aus einer Speicherkapazität von 2(2 -1) Zellen, die gleichmäßig auf zwei baumartige Speichernetzwerke so verteilt sind, daß das erste Netzwerk alle Zelladressen enthält, in deren Binärcode das Bit mit der Wertigkeit 2 eine 0 führt und das zweite Netzwerk alle Zelladressen enthält, deren Binärcode an dieser Stelle eine 1 hat, und daß eine vom Zugriffssteuerwerk betriebene Auswahlschaltung automatisch die Verbindung zu einem der beiden Leseköpfe der Speichernetzwerke herstellt.
4. Schaltungsanordnung nach einem oder mehreren der Ansprüche

1 bis 3, dadurch gekennzeichnet, daß das Zugriffssteuerwerk im wesentlichen besteht aus einem als Vorwärts-Rückwärtsschieberegister ausgebildeten Speicheradressregister MAR mit

- 32 -

609826/0057

2459Α7Θ

k Binärstellen zum Laden des aus k + 1 Bits bestehenden Adressencodes , ausgenommen das Bit mit der Wertigkeit 2, einem einstelligen überlaufregister HM, das mit dem Speicheradressenregister MAR zu einem Ringschieberegister zusammengeschaltet ist, einem einstelligen Register MFF zum Aufnehmen des Bits der Wertigkeit 2 der Adresse, einem als Vorwärts-Rückwärtsschieberegister ausgebildeten Permutationsstatus.-. register SAR mit k Binärstellen, das in jedem Permutationszustand den Binärcode der Adresse der Speicherzelle - ausgenommen das Bit der Wertigkeit 2 - enthält, deren Inhalt sich im Lesekopf des ersten Netzwerkes befindet, einem einstelligen Überlaufregister HS, das beim Rechtsshift des Permutationsstatusregisters SAR dessen Bit der Wertigkeit 0 übernimmt, wobei im überlauf register HS der vor der Übernahme vorhandene Inhalt gelöscht wird und das beim Linksshift des Permutationsstatusregisters SAR seinen Inhalt an das Bit der Wertigkeit 0 in SAR abgibt und den Inhalt des Überlaufregisters HM übernimmt, einem Vorwärts-•Rückwärtsschieberegister SPR mit k Binärstellen, das einen Zeiger der Form enthält, daß nur eine Binärsteile den Wert 1 führt und alle anderen Binärstellen den Wert 0 führen, einem einstelligen Register SFF zum .Kennzeichnen der zuletzt ausgeführten Permutationen A mit 1 oder der Permutation B mit O, einem einstelligen Register MHF zum Kennzeichnen der ersten Permutation A mit 1 oder B mit O der für den Zugriff auf die in MAR enthaltene Adresse erforderlichen Permutationssequenz, einem einstelligen Register SHF zum Anzeigen der ersten Permutation A mit 1 oder B mit O der für den Inhalt des Permutationsstatusregisters SAR notwendigen Permutationssequenz, einem einstelligen Steuerregister HH zum Duplizieren des Inhaltes des überlaufregisters HS, einem m~stelligen Zählregister CNT zum Zählen der mit dem Speicheradressregister MAR ausgeführten Rechtsshifts durch Hochzählen und der

- 33 -

609826/0057

245947Θ

3V

Linksshifts durch Herur-i:er?ahlP.>i, einew Schieberegister DEL mit drei Binärstellen, dessen Inhalt mit jeder Permutation nach rechts shiftet, in dessen linker Binärstelle eine Permutation A mit 1, eine Permutation B mit O markiert ist und von dessen rechter Binärstelle nach zwei Permutationstakten das Steuersignal für die Permutationen im Netzwerk 2 abgreifbar ist, einem Schieberegister READ mit drei Binärstellen, dessen Inhalt mit jeder Permutation nach rechts shiftet und dessen linke Binärstelle auf 1 gesetzt ist, wenn das Register MFF eine 1 führt, die Inhalte des Speicheradressregisters MAR und des Permutationsstatusregisters SAR deckungsgleich sind und bei einer 1 in der rechten Binärstelle der Lesekopf des Netzwerkes 2 angesteuert ist, einem logischen Netzwerk COMP zum Auswerten der Inhalte des Speicheradressregisters MAR, des Permutationsstatusregisters SAR und des Zeigerregisters SPR und zum Erzeugen von Steuersignalen sowie einem internen Leitwerk zum Ausführen der für das Steuern der Register und der Permutationen erforderlichen Mikroprogramme.
5. Schaltungsanordnung nach einem oder mehreren der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß jeder Binärstelle des Speicheradressregisters MAR, des Permutationsstatusregisters SAR und des Zeigerregisters SPR in dem logischen Netzwerk COMP eine Zelle zugeordnet ist, daß jede Zelle i vier Eingänge (60, 61, 67, 66) besitzt, daß der erste Eingang (60) mit dem Ausgang der i-ten Binärstelle des Registers MAR, der zweite Eingang (61) mit dem Ausgang der i-ten Binärstelle des Registers SAR, der dritte Eingang (67) mit dem Ausgang der i-ten Binärstelle des Zeigerregisters SPR und der vierte Eingang (66) mit dem Ausgang der (i+1)-ten Zelle von COMP verbunden ist, daß jede Zelle zwei Ausgänge (69, 71) besitzt, daß der erste Ausgang (69) mit dem korrespondierenden vierten Eingang (66) der (i-l)-ten Zelle von COMP und der zweite Ausgang (71) mit dem Eingang der i-ten Binärstelle des Registers SPR verbunden ist, und daß alle Zellen des logischen Netzwerkes COMP an eine erste und eine zweite Signalsammelleitung (74, 77) und eine Steuerleitung (64) angeschlossen sind.

- 34 -6098 2 6/0057

2459478 . ar.
6. Schaltungsanordnung nach Anspruch ". bis 5, dadurch gekennzeichnet, daß der erste Eingang (60) jeder Zelle des logischen Netzwerkes COIiP mit einem ersten Eingang eines ersten AND-Gatters (62) und einem ersten Eingang eines EXCLUSIV-OR-Gatters (63) verbunden ist, daß der zweite Eingang (61) auf die zweiten Eingänge des ersten AND-Gatters (62) und des EXCLUSIV-OR-Gatters (63) geschaltet ist, daß ein dritter Eingang des ersten AND-Gatters (62) auf die Steuerleitung (64) geführt ist, daß ein erster Eingang eines zweiten AND-Gatters (65) mit dem vierten Eingang (66) der Zelle und ein zweiter invertierter Eingang des zweiten AND-Gatters (65) mit dem dritten Eingang (67) der Zelle verbunden ist, daß die Ausgänge des ersten ■und zweiten AND-Gatters (62, 65) sowie der Ausgang des EXCLUSIV-OR-Gatters (63) auf die Eingänge eines OR-Gatters (68) gelegt sind, daß der Ausgang (69) des OR-Gatters (68) auf einen ersten Eingang eines dritten AND-Gatters (70) geschaltet ist, daß ein zweiter invertierter Eingang des dritten AND-Gatters (70) mit dem Ausgang des zweiten AND-Gatters (65) und ein dritter Eingang des dritten AND-Gatters (70) mit der Steuerleitung (64) verbunden ist, daß der Ausgang des dritten AND-Gatters (70) mit dem zweiten Ausgang (71) der Zelle identisch ist, daß der erste und dritte Eingang (60, 67) der Zelle auf die Eingänge eines vierten ATID-Gatters (72) geschaltet sind, dessen Ausgang über eine erste Schutzdiode (73) mit der ersten Sammelleitung (74) verbunden ist und daß der zweite und dritte Zelleingang (61, 67) auf die Eingänge eines fünften AND-Gatters (75) geführt sind, dessen Ausgang über eine Schutzdiode (70) . auf die zweite Sammelleitung (77) geschaltet ist.
7. Schaltungsanordnung nach Anspruch 1 bis 6, dadurch gekennzeichnet, daß zum sequentiellen Zugriff auf 2^g aufeinanderfolgende adressierbare Zellinhalte, deren erste Adresse ein ganzzahliges Vielfaches von 2^g sein muß, in das Zugriffswerk ein g-stelliger Binärzähler ADCT integriert ist, dessen Inhalt nach jedem Zählschritt in die letzten g Binärstellen des Speicheradressregisters MAR übertragen wird.

- 35 -

609826/0057