DE2200744A1

DE2200744A1 - Verfahren und Vorrichtung zum Aussortieren

Info

Publication number: DE2200744A1
Application number: DE19722200744
Authority: DE
Inventors: Gerhard Dr Dirks; Dipl-Ing Schenck Paul F
Original assignee: Dirks Computer Systems Corp
Current assignee: Dirks Computer Systems Corp
Priority date: 1971-01-07
Filing date: 1972-01-07
Publication date: 1972-08-03
Also published as: GB1383991A; US3714634A

Description

DIRKS COMPUTER SYSTEMS CORPORATION, eine Gesellschaft nach den Gesetzen des Staates Californien, 754 North Pastoria Avenue, Sunnyvale, Californien 94086 (V.St.A.)

Verfahren und Vorrichtung zum Aussortieren

Die Erfindung befaßt sich mit einem Verfahren und einem System zum Mischen und Aussortieren von Satzeinheiten entsprechend dem Wert eines jeder Satzeinheit zugeordneten Schlüsselfeldes. Datenbearbeitende Systeme für den Umgang mit derartigen Satzeinheiten sind bekannt. Eine Satzeinheit kann beispielsweise den Namen einer Person, ihr Alter, ihre Adresse, ihre Sozialversicherungsnummer, ihre Jahresentlohnung und die Anzahl ihrer Krankheitstage umfassen. Natürlich können auch andere Posten je nach Wunsch und Bedarf in der Satzeinheit enthalten sein. Die angeführten? Posten stellen nur einfache Beispiele dar. Die Satzeinheiten werden dann entsprechend einem Schlüsselfeld-Wert in bestimmter Reihenfolge angeordnet, wobei "Schlüsselfeld" sich auf einen bestimmten Teil der Satzeinheit bezieht, wie beispielsweise die Jahresentlohnung des Beschäftigten. Jedes Feld einschließlich Schlüsselfeld enthält einen oder mehrere alphanumerische Zeichen. Die alphanumerischen Zeichen sind ihrerseits in Form meh-

209832/1032

rerer Bits codiert, wobei jedes Bit entsprechend seiner Stellung innerhalb des Feldes bewichtet bzw. mit einem Stellenwert versehen ist.

Datenbearbeitende Systeme für das Aussortieren und Vermischen derartiger Satzeinheiten entweder nach aufsteigendem oder absteigendem Wert des Schlüsselfeldes sind bekannt. Sie können eingeteilt werden in Allzweckrechner, die komplizierte wissenschaftliche Berechnungen wie auch einfache kalkulatorische Berechnungen ausführen können und deren Mietkosten sehr hoch liegen, während ihre Verarbeitungsgeschwindigkeit relativ gering ist. Andererseits sind für Spezialzwecke entwickelte Rechner bekannt, wie beispielsweise derjenige aus dem US-Patent 3 343 133. Derartige Spezialrechner besitzen Umlaufspeicher oder Schieberegister-Speicher, etc. und führen die Aussortieroperation durch direkten Vergleich der Schlüsselfelder in einer Anordnung von mehreren Vergleichern aus. Jedes Bit aus jedem Schlüsselfeld wird mit allen gleich bewichteten Bits aller anderen betroffenen Schlüsselfelder verglichen. Das Ergebnis ist ein Vergleich der Vergleichsergebnisse, was solange fortgesetzt werden kann, bis die gewünschte Sequenz von Satzeinheiten hergestellt worden ist.

Die vorliegende Erfindung beschreibt ein Verfahren zum Aussortieren mehrerer Satzeinheiten ohne Vergleich der Schlüsselfeld-Bits. Weiterhin wird ein Datenbearbeitungssystem beschrieben, das nach dem genannten Verfahren arbeitet und eine große Sortiergeechwindigkeit bei relativ geringem apparativen Aufwand ermöglicht.

Die Erfindung umfaßt ein Verfahren zum Aussortieren mehrerer Satzeinheiten, von denen jede ein Schlüsselfeld aufweist, entsprechend dem Code-Wert der Schlüaaelfelder. Jedes Schlüaeelfeld weist mehrere Schlüsselfeld-Bits auf,

209832/1032

22007ΑΛ

die in einer vorbestimmten Reihenfolge angeordnet sind. Auf jede Satzeinheit kann weiterhin mit einer entsprechenden Satzeinheit-Adresse zugegriffen werden. Nach dem · Verfahren werden die Satzeinheit-Adressen in einer ersten · Adressen-Sequenz angeordnet. Diese erste Adressen-Sequenz wird in eine erste und zweite Adressen-Unterfolge aufgeteilt, wobei in, den Adressen-Unterfolgen alle diejenigen Adressen enthalten sind, deren zugehörige Satzeinheiten als erstes Schlüsselfeld-Bit in der vorbestimmten Schlüsselfeld-Bit-Reihenfolge eine "0" oder eine "1" enthalten. Die ersten und zweiten Adressen-Unterfolgen werden zu einer zweiten Adressen-Sequenz verknüpft, in der die Ziffern aus der ersten Adressen-Unterfolge den Ziffern der zweiten Adressen-Unterfolge vorhergehen. Das Einteilen der Adressen-Sequenzen in Unterfolgen und das Verknüpfender Unterfolgen zu weiteren Sequenzen wird unter der Steuerung der verbleibenden Schlüsselfeld-Bits wiederholt. Nach Vervollständigung der unter der Steuerung des letzten Schlüsselfeld-Bits ausgeführten Verknüpfung der Unterfolgen befinden sich die Satzeinheit-Adressen in der Reihenfolge der Schlüsselfeldwerte. Die in dieser Ordnung angeordneten Satzeinheit-Adressen können dann zum Auslesen der Satzeinheiten in einer entsprechenden Reihenfolge herangezogen werden, wodurch sich die aussortierte Sequenz ergibt.

Die Erfindung betrifft weiterhin ein Datenverarbeitungssystem, das die Satzeinheiten wie vorbeschrieben behandelt. Das Datenverarbeitungssystem umfaßt Register, die Schlüsselfeld-Bits in adressierbaren Registerstellen speichern. Sie umfaßt weiterhin einen ersten und zweiten Satzeinheit-Adressenspeicher, von denen jeder eine einer ¹¹O" zugeordnete Speicherstelle und eine einer ¹¹I" zugeordnete. Speicherstelle aufweist. An den ersten Satzeinheit-Adres'senspeicher ist eine Eingabe an- ·

209832/1032

geschlossen, die Satzeinheitadressen zuführt, von denen jede Zugriff zu einer entsprechenden Satzeinheit ermöglicht. Mit den Registern sind Register-Adressiereinrichtungen verbunden und liefern ausgewählte Schlüsselfeld-Bits mindestens teilweise unter Steuerung der Satzeinheit-Adressen, die in dem ersten oder zweiten Satzeinheit-Adressenspeicher gespeichert sind. Schließlich verbinden Adressen-Übertragungseinrichtungen den ersten und zweiten Satzeinheit-Adressenspeicher und die Register und übertragen Adressen zwischen dem ersten und zweiten Satzeinheit-Adressenspeicher unter Steuerung der ausgewählten Schlüsselfeld-Bits auf solche Weise, daß alle Satzeinheit-Adressen unter Steuerung eines ¹¹Q"-Schlüsselfeld-Bits in aufeinanderfolgend adressierbare Satzeinheit-Adressenspeicherstellen, beginnend mit .... der der "O" zugeordneten Satzeinheit-Adressenspeic.hersteile,übertragen werden, und daß alle Satzeinheit-Adressen unter Steuerung eines ^Ml^lf-Schlüsselfeld-Bits in aufeinanderfolgend adressierbare Satzeinheit-Adressenspeichersteilen, beginnend mit der der "1". zugeordneten Satzeinheit-Adressenspeichersteile übertragen werden.

In einer speziellen Ausführungsform der Erfindung werden die Satzeinheiten von einem umlaufenden Datenspeicher in einer willkürlichen Reihenfolge geliefert und in der · sortierten Reihenfolge unter Steuerung der sortierten Satzeinheit-Adressen in dem ersten oder zweiten Satzeinheit-Adressenspeicher ausgelesen. Die Satzeinheiten können in dem ersten Umlaufspeicher auf ineinander verschachtelte Weise aufgezeichnet werden, in welchem Falle nur ein einziges Auslese-Element für den Umlaufspeicher erforderlich ist.

Alternativ können die Daten in dem ersten Umlaufspeicher auch in einer nicht ineinander verschachtelten Weise ge-

209832/1032

speichert werden, in welchem Fall gemäß einer zweckmäßigen Ausgestaltung der Erfindung mehrere Auslese-Elemente vorgesehen sind, um im wesentlichen gleichzeitig gleichbewichtete Schlüsselfeld-Bits aus jeder Satzeinheit zu liefern. In dem einen wie dem anderen Fall wird jede Übertragung von einem Satzeinheit-Adressenspeicher zu. dem anderen unter Steuerung eines Satzes von gloichfoewichteten Schlüsselfeld-Bits ausgeführt, ivobei von jeder Satzeinheit eines stammt. Jedes Schlüsselfeld-Bit steuert die Übertragung der entsprechenden Satzeinheit-Adresse in eine Speicherstell©, die entweder der d@r "¹¹O" zugeordneten Speicherstelle oder der der "1" zugeordneten Speicherstelle" zugehört _t was von dem Wert d©s Schlüsselfeld-Bits abhängt«

Die für die Erfindung als charakteristisch angesehenen Merkmale sind im einzelnen in den beigefügten Ansprüchen niedergelegt. Die Erfindung selbst, sowohl im Hinblick auf das ihr gemäße Arbeitsverfahren wie auf die zu seiher Ausführung dienende Einrichtung ₉ wird zusammen mit weiteren Vorteilen und Eigenschaften aus der nachfolgenden Beschreibung spezielle Ausführungsformsn deutlich, bei der aujf die beigefügte Zeichnung bezug genommen wird«. Im einzelnen zeigens

Fig_e jl eine das nach den Merkmalen der Erj· findung ausgestaltet© Verfahren erj läuternd® Tab©!!©?

/ Fig<5 2 Gin das srfindungsgsmSß® Verfahren

Figo 2 idQntischGS Diag rait d@s Ausnahm©ρ daß dia gsn₉ UiQ in dom BsispiGi Roch Fifo 1 iro^hasidon Si^d₉ als dielt© so Liffii©in₉ dia dort nicht

dünnom Linien und dig ungültiges^ terfolg©n für ©inen BCD=>C©dQ in go« strichelten Linien dargcetGllt sind?

^09832/1032

Fig. 4 ein Blockdiagramm einer mit den

Merkmalen der Erfindung ausgestatteten Aussortier-Einrichtung;

Fig. 5 ein Blockdiagramm, das das Zähler-Steuersystem aus Fig. 1 im Detail erläutert;

Fig. 6 ein Blockdiagramm eines Systems

gemäß der Einrichtung, nach Fig. 4, die mit nicht-ineinanderverschachtelten Daten arbeitet; und

Fig. 7 ein System nach Fig. 6, das mit in einander verschachtelten Daten arbeitet.

Die bevorzugte Ausführungsform der Erfindung wird jetzt unter Bezugnahme auf die Zeichnung beschrieben.

Ehe das erfindungsgemäße Verfahren gemäß Fig. 1 und 2 im einzelnen beschrieben wird, werden einige Definitionen und die Erklärung einiger in dieser Anmeldung verwendeten Auedrücke gegeben.

Die gemäß der Erfindunq auszusortierenden Satzeinheiten sind solche, wie, sie in der Beschreibungseinleitung bereits erwähnt wurden, und sollen entsprechend dem Schlüsselfeld-Wert aussortiert werden. Jedes Schlüsselfeld kann mehrere alphanumerische Zeichen umfassen; diese Zeichen sind in Bits codiert, wobei jedes Bit entweder einen

.¹¹O¹!- .oder einen «UlVWert besitzt, der., leweile

das Vorhandensein oder NichtVorhandensein eines mit.dem Bit verbundenen Wertes anzeigt· Die Bewichtung jedes Bits hHngtt von seiner Stellung in der Schlüsselfeld-Bit-Folge ab« Beispielsweise kann ein Schlüsselfeld-Wert yen 7.all Folge 111 dargestellt werden, in der das erste Bit ein· Qew^chtung von 1, das zweite eine Bewichtung von 2 und das dritte eine Bewichtung von 4 hat. In einer Seriell arbeitenden Ausführungsform des Systems können dieif Bits nacheinander geliefert werden, wie sie

209832/1032

beispielsweise aus einem Umlaufspeicher ausgelesen worden sind. Die Zeit, bei der ein Bit mit einer speziellen Bewichtung für das Abtasten zur Verfügung steht, ist eine Bit-Zeit. Zu jeder Bit-Zeit gehört ein Zeitgeber-Signal, das ein Bit-Zeit-Taktimpuls (btcl) genannt wird» Wenn die Bits aus einer speziellen Satzeinheit in Sequenz ausgelesen werden und ihnen die Bits der nachfolgenden Satzeinheit folgen, ist das System ein ohne Ineinariderverschachtelung arbeitendes System«. Bei einem ineinanderverschachtelten System wird jede Bit-Zeit in gleiche Teile unterteilt, wobei jeder Teil eine Sub-Bit-Zeit genannt wird. In einem derartigen verschachtelten System umfaßt jeder Satz von Bits, die die zwischen aufeinanderfolgenden Bit-Zeiten enthaltenen Bits aufweisen, ein gleichbewichtetes Bit aus jeder Satzeinheit. Somit ist die Bit-Zahl in jedem Satz von Bits, die zwischen aufeinanderfolgenden Bit-Zeiten auftreten, gleich der Anzahl von Satzeinheiten, die sortiert werden sollen. Bits der gleichen Satzeinheit treten immer in der gleichen Sub-Bit-Zeit auf. Wenn beispielsweise nach einer ersten Bit-Zeit Bits der Satzeinheiten A, B., C und D in Sub-Bit-Zei» ten in dieser Reihenfolge geliefert werden_s wird die gleiche Anordnung in der folgenden nächsten Bit-Zeit maßgebend sein. Mit anderen Worten; Ein Bit steht mit einer speziellen Satzeinheit durch seine Stellung innerhalb des Satzes von gleichbewichteten Bits in Beziehung.

Es wird weiterhin bemerkt, daß die Sub-Bit-Zeiten hier alternativ als Zeitmarken bezeichnet werden.

Das erfindungsgemäße Verfahren, dessen Aufgabe es ist, diese Satzeinheiten in einer Folge entsprechend der Ordnung von Schlüsselfeldwerten zu sortieren, wird jetzt unter Bezugnahme auf Tabelle 1 beschrieben.

209832/1032

Tabelle IA zeigt die Schlüsselfeldwerte von acht Satzeinhei.ten in der Sequenz, in der diese Satzeinheiten
ursprünglich gespeichert waren. Dies ist die'erste Adressensequenz und stellt eine völlig willkürliche Folge dar. Die Satzeinheit-Adressen 0-7 gemäß Zeile 1 sind willkürlich den Schlüsselfeldern und den entsprechenden Satzeinheiten zugewiesen. Die Adressenwörter dienen als Bezeichnung unabhängiger Satzeinheiten und liefern Zugriff zu diesen Satzeinheiten.

Spalte 1, Zeilen 3-9, zeigen die Bewichtungen der Bits in den Bit-Positionen, die die Schlüsselfeldwerte repräsentieren. In den Spalten 2 - 9 ist die Binärdarstellung der acht Schlüsselfeldwerte wiedergegeben. Die Schlüsselfeldwerte sind unter 20 gehalten worden, um das Beispiel übersichtlich zu halten. Alle Bits, die eine höhere Bewichtung als 20 repräsentieren, sind O-Bits und haben
keinerlei Wirkung im Arbeitsablauf· Das erste Schlüsselfeld besitzt einen Wert von 7, repräsentiert durch die
Bitfolge 111000. Diesem Schlüsselfeld ist die Adresse
0 zugewiesen. Das zweite Schlüsselfeld aus Spalte 3 besitzt den Wert 5, seine Bitfolge lautet 101000 und kann
über die Satzeinheit-Adresse 1 erhalten werden. Das
dritte Schlüsselfeld, Spalte 4, besitzt den Wert 13,
repräsentiert durch die Bitfolge 110010, lokalisiert
an der Satzeinheit-Adresse 2.

Die Satzeinheit-Adressen und die Schlüsselfeld-Werte der verbleibenden Einheiten können auf die ähnliche Weise
abgeleitet werden.

Es werde angenommen, daß die Satzeinheit-Adressen in einer ersten Adressen-Sequenz geliefert werden, nämlich
0 bis 7 in numerischer Ordnung, und daß sie in dem Adressenregister A (0) gespeichert sind. Diese erste Adressen-

209832/1032

Sequenz wird nach dem"erfindungsgemäßen Verfahren unterteilt in eine erste und zweite Adressen-Unterfolge ₉ die jeweils diejenigen Adressen enthalten₉ deren signifikan-

.testes (bzw« am wenigsten signifikantes) Bit eine "0¹^ ist,_ bzw· die jenigen Adressen enthalten ₉" deren signifikantestes Schlüsselfeld-Bit eine "1" ist_?' _ .' " Es werde angenommen^ daß die erste Adressen-Sequenz als willkürliche Sequenz unabhängig von dem Schlüsselfeld-= wert in einem Adressen-Register A (Ziffer 0) gespeichert wird (man möge bemerken, daß die Unterteilung der ersten

. Adressen-Sequenz.in eine erste Adressen-Unterfolge und eine zweite Adressen-Unterfolge entsprechend der nachfolgenden in einzelne gehenden Erörterung von der erfindungsgemäßen Einrichtung während des anfänglichen Einlesens der Satzeinheit-Adressen in den ersten Satzeinheit-Adressenspeicher A ausgeführt wird«)Zur Erleichterung des Verständnisses wird dieser Schritt an dieser Stelle

weggelassen^ und es werde angenommen^ daß die Satzeinheit-Adres sen in dem ersten Satseinheit-Speicher in willkürlicher Sequenz anfänglich gespeichert seien» Der Satzeinhej t-»Adressenspeicher A (genannt Adressen-Register A) besitzt eine eine "0" zugewiesene Speicherstelle und eine eine "1" zugewiesene Speicherstelle,, Entsprechendes gilt für das Adressenregister B, In'den Tabellen cjer Fig_o 1 beziehen sich ,die als Adresseare-= gister A Ip) .und A (1) bezeichneten Speichers tollen.' j©=> wells auf/Stellen in dem Adressenregister A₉ die der der "0" -zugewiesenen Speicherstelle und der der "1" zugewiesenen £Spelcherstelle nachfolgst Entsprachendes gilt wiederum für das .Adressenregister B₀

Die Tabelle IB erläutert, was bei <ä@ra 'ersten Durchgang In der Sortieroperatiqn ausgeführt wird«. Die Satzeinheit» Adressen Werdens von dem Adressenregister A (o) in der

209832/1032

Sequenz ausgewählt, in der sie Anfänglich eingespeichert worden sind. Die Tabelle IB, Zeile 1, zeigt die erste Adressen-Sequenz, nämlich die Adressenwörter, die in aufsteigender Reihenfolge in dem Adressenspeicher A (o) gespeichert sind. Somit wird die Satzeinheitadresse O zuerst gelesen werden. Das erste Bit des Schlüsselfeldes, das mit der Satzeinheit-Adresse O verbunden ist, ist ein 1-Bit, das bewirkt, daß die Satzeinheit-Adresse O der zweiten Adressen-Unterfolge zugeordnet wird, die in dem Adressenregister B (1) gespeichert wird. Die nächste Satzeinheit-Adresse von Interesse ist die Satzeinheit-Adresse 1. Das am wenigsten signifikante Schlüsself eld-Bit, das mit der bei der Satzeinheit-Adresse 1 zugreifbaren Satzeinheit verbunden ist, ist ebenfalls eine 1, die bewirkt, daß die Satzeinheit-Ädresse 1 der zweiten Adressen-Unterfolge zugeordnet und in dem Adressen-Register B (Ziffer Dnach der Satzeinheit-Adresse O gespeichert wird. Danach werden die Satzeinheit-Adressen 2 und 3 betrachtet. Jede dieser Adressen hat ein am wenigsten signifikantes Schlüsselfeld-Bit von 1 in dem zugeordneten Schlüsselfeld der zugeordneten Satzeinheit« Die Satzeinheit-Adressen 2 und 3 werden daher ebenfalls der zweiten Adressen-Unterfolge zugeordnet und in dem Adressen-Register B (ij gespeichert, und zwar in Speicherstellen nach derjenigen Stelle, der die Satzeinheit-Adresse 1 zugewiesen worden war. Die fünfte Satzeinheit-Adresse, nämlich die Satzeinheit-Adresse 4, zeigt eine in der Schlüsselfeld-Position mit einem Bitwert vjon 1. Daher wird die Satzeinhei.t-Adresse 4 der ersten Adressen-Unterfolge zugeordnet und in der der "O" zugeordneten Speicherstelle des Adressen-Registers B (O) gespeichert· Die Satzeinheit-Adressen 5, 6 und 7 haben jeweils ebenfalls eine 0 in der am wenigsten signifikanten Schlüsselfeld-Bit-Position und werden daher der ersten Adressen-Unterfolge zugeordnet und in dem Adressen-Register B

209832/1032

(O) nach der Satzeinheit-Adresse 4 gespeichert· Somit wurde die erste Adressen-Seqaenz unterteilt in eine erste Adressen-Unterfolge, die die Satzeinheit-Adressen 4, 5, 6 und 7 enthält, und in eine zweite Adressen-Unterfolge, die die Satzeinheit-Adressen 0, 1, 2 und 3 enthält.

Die erste Adressen-Unterfolge und zweite Adressen-Unterfolge werden danach zur Bildung einer zweiten Adressen-Sequenz verknüpft, in der die Elemente der ersten Adressen-Unterfolge den Elementen der zweiten Adressen-Unterfolge vorhergehen. Die Satzeinheit-Adressen 4, 5, 6 und gehen daher den Satzeinheit-Adressen O, 1, 2 und 3 vorher, und die zweite Adressen-Sequenz enthält die Satzeinheit-Adressen in folgender Reihenfolge: 4, 5, 6, 7, 0, 1, 2, 3. Dies ist in der. oberen Halfte der Tabelle IC dargestellt. Der erste Teil der zweiten Adressen-Sequenz ist in einem Adressen-Register B (G) gespeichert, während der zweite Teil in dem Adressen-Register B (1) gespeichert ist. Diese zweite Adressen-Sequenz wird jetzt in eine dritte und vierte Adressen-Unterfolge unterteilt, und zwar entsprechend dem Schlüsselfeld-Bit der nächsthöheren Bewichtung, im betrachteten Fall also entsprechend dem Schlüsselfeld-Bit mit einer Bewichtung von 2. Diese Schlüsselfeld-Bits finden sich in Zeile 4 der Tabelle IA. Für die Satzeinheit-Adresse 4 lautet damit das Schlüsselfeld-Bit von der Bewichtung 2 auf 1. Die Satzeinheit-Adresse 4 wird somit der vierten Adressen-Unterfolge zugewiesen. Danach wird die Satzeinheit-Adresse 5 in die dritte Adressen-Unterfolge übertragen, da deren Schlüsselfeld-Bit mit der Bewichtung 2 eine O ist. Entsprechendes gilt für die Satzeinheit-Adresse 6. Die Satzeinheit-Adresse 7 weist ein Schlüsselfeld-3it von 1 in der zweiten Schlüsselfeld-Position auf und wird daher der vierten Adressen-Unterfolge zugewiesen, genau so wie die Satzeinheit-Adresse O. Die Satzeinheit-Adresse

209832/1032

22007U

besitzt ein O-Schlüsselfeld-Bit in der Schlüsselfeld-Bit-Position mit der Bewichtung 2 und wird daher der dritten Adressen-Unterfolge zugewiesen, während die Satzeinheit-Adressen 2 und 3 jeweils eine Ziffer 1 in dem Schlüsselfeld-Bit der Bewichtung 2 haben und daher der vierten Adressen-Unterfolge zugewiesen werden. Dies ist in der unteren Hälfte der Tabelle IC erläutert, wonach das Adressen-Register A (0) die Satzeinheit-Adreesen 5, 6 und 1 enthält, während das Adressen-Register A (1) die Satzeinheit-Adressen 4, 7, 0, 2 und 3 enthält.

Die dritten und vierten Adressen-Unterfolgen werden jetzt zu einer dritten Adressen-Sequenz verknüpft, die die Satzeinheit-Adressen in der folgenden Reihenfolge enthält: 5, 6, 1, 4, 7, 0, 2, 3. Die untere Hälfte der Tabelle ID zeigt dann die Unterteilung der dritten Adressen-Sequenz in eine fünfte und sechste Adressen-Unterfolge, während die obere Hälfte der Tabelle IE die Verknüpfung der fünften und sechsten Adressen-Unterfolgen in eine vierte Adressen-Sequenz erläutert, die die Satzeinheit-Adressen in der Reihenfolge 5, 6, 4, 2, 1, 7, 0 und 3 enthalten. Die auf diese Weise abgeleitete vierte Adressen-Sequenz wird wiederum unterteilt in eine siebente und achte Adressen-Unterfolge unter Steuerung der Schlüsselfeld-Bits mit einer Bewichtung von 8, wie das in Tabelle 1ψ ausgeführt ist.

Die sechste Adressen-Sequenz im oberen Teil der Tabelle IF wird unterteilt in eine neunte und zehnte Adressen— Unterfolge in Abhängigkeit von den Schlüsselfeld-Bits mit der Bewichtung 10. Die neunte und zehnte Adressen-Unterfolge wird dann wiederum verknüpft zu einer sechsten Adressen-Sequenz, die im oberen Teil der Tabelle IG zu erkennen ist und die Satzeinheit-Adressen in der folgenden Reihenfolge enthält: 4, 1, 7, 0, 5, 6, 2, 3. Man bemerke jetzt, daß die sechste Adressen-Sequenz jetzt in

2v 332/103 2

die elfte und zwölfte Adressen-Unterfolge in Abhängigkeit von den Schlüsselfeld-Bits mit der Bewichtung 20 unterteilt werden sollte. Es wurde jedoch im vorliegenden Beispiel angenommen, daß alle Schlüsselfeld-Bits von der Bewichtung 20 und höher eine. 0 aufweisen· Daher werden alle Satzeinheit-Adressen in der sechsten Adressen-Sequenz der elften Adressen-Unterfolge zugewiesen werden. Diese elfte Adressen-Unterfolge ist in der unteren Hälfte der Tabelle IG dargestellt und enthält die Satzeinheiten in der gleichen Reihenfolge wie die sechste Adressen-Sequenz. Die Tabelle IH zeigt, daß die elfte Adressen-Unterfolge, die die Satzeinheit-Adressen in der Reihenfolge 4, 1, 7, O, 5, 6, 2 und 3 enthält, eine Folge von Satzeinheit-Adressen in der Reihenfolge aufsteigender Schlüsselfeldwerte bildet. Die Satzeinheit-Adresse 4 greift somit auf eine Satzeinheit zu, deren Schlüsselfeldwert 2 beträgt $ die Satzeinheit-Adresse 1 greift auf eine Satzeinheit zu, deren Schlüsselfeldwert 5 beträgt, etc. Wie in Tabelle IH gezeigt, sind die Schlüsselfeldwerte, die den Satzeinheiten zugeordnet sind, auf die durch die Satzeinheitadressen zugegriffen werden kann, von zunehmendem Wert. Damit wurde die Aufgabe der vorliegenden Erfindung, nämlich das Sortieren der Satzeinheit-Adres$en in vorbestimmter Reihenfolge (aufsteigender Reihenfolge) von Schlüsselfeldwerten gelöst.

·. Die theoretische Basis für das vorbeschriebene Verfahren wird jetzt-im Zusammenhang mit Fig· 2 beschrieben· Das Sortierpri^izip wird anhand derjenigen Schlüsselfelder erläutert, in denen das am wenigsten signifikante Bit zuerst betrachtet wird. An der linken Seite der Figur ist zu erkennen, daß die Satzeinheit-Adressen in eine «rate und zweite-Adressen-Unterfolge aufgetrennt werden« die * diejenigen Elemente aufweist, die ein O-Bit in der am wenigsten signifikanten Bit-Position und ein 1-Bit an der

203832/1032 ^ : *

- 22007U

am wenigsten signifikanten Schlüsselfeld-Bit-Position besitzen. Die Linie 1 zeigt somit diejenige Satzeinheit-Adressen-Unterfolge an, die alle geradzahligen Schlüsselfeldwerte umfaßtι während die Linie 2, die zweite Adressen-Unterfolge, alle Satzeinheit-Adressen mit ungeradzahligen Schlüsselfeldwerten aufweist·

Die erste Adressen-Unterfolge wird dann in eine dritte und vierte Unterfolge unter Steuerung des nächst signifikantes Schlüsselfeld-Bits in denjenigen Schlüsselfeldern unterteilt, die den Satzeinheit-Adressen in der ersten Adressen-Unterfolge zugeordnet sind. Dies führt zu Unterfolgen, die in Fig. 2 mit 3a und 4a bezeichnet sind. Die Sequenz 3a enthält alle Satzeinheit-Adressen, der ersten· Adressen-Unterfolge, deren zweit-signifikantes Bit eine 0 ist, während die Unterfolge 4a alle diejenigen Satzeinheit-Adressen der ersten Adressen-Unterfolge umfaßt, deren zweites Schlüsselfeld-Bit eine 1 ist. In ähnlicher Weise wird die zweite Adressen-Unterfolge in die mit 3b und 4b bezeichneten Unterfolgen unterteilt, die Satzeinheit-Adressen enthalten, deren zweites Schlüsselfeld-Bit eine 0 oder eine 1 ist. Die Linien 3a und 3b bezeichnen daher zusammengenommen alle Satzeinheit-Adressen der dritten Adressen-Unterfolge in Fig. 1, nämlich die Satzeinheit-Adressen 5, 6 und 1. Man bemerke, daß die Satzeinheit-Adressen 5 und 6 in der Unterfolge 3a aus Fig. 2 enthalten ist, während die Satzeinheit-Adresse 1 schematisch durch die Linie 3b angedeutet ist. Da die Satzeinheit-Adressen stets in Sequenz geprüft werden, ist eine körperliche Differenzierung zwischen der Unterfolge 3a und der Unterfolge 3b nicht notwendig· In Ähnlicher Weise sind die Satzeinheit- Adressen 4 und 7 durch die Linie 4a in Fig. 2 bezeichnet, während die Satzeinheit-Adressen 0, 2 und 3 in der Unterfolg· 4b aus Fig. 2 enthalten sind.

209832/1032

Theoretisch kann dann jede dieser Unterfolgen 3a, 3b, 4a und 4b in Adressen-Unterfolgen 5 und 6 mit den Komponenten 5a, 5b, 5c und 5d sowie 6a, 6b, 6c und 6d unter Steuerung des nachst-signifikanten Schlüsselfeld-Bits unterteilt werden. Die nach unten geneigten. Linien sind jeweils mit 5 bezeichnet und gehören zu der fünften Unterfolge, nämlich derjenigen Unterfolge, die durch die Satzeinheit-Adressen mit einem O-Schlüsselfeld-Bit an der Stelle des geprüften Schlüsselfeldes gebildet werden. Die nach oben geneigten Linien sind der sechsten Adressen-Unterfolge zugeordnet und enthalten sämtliche Satzeinheit-Adressen mit einem Schlüsselfeld-Bit vom Werte 1 an der untersuchten Schlüsselfeld-Bit-Position. An dieser Stelle hat das Schlüsselfeld-Bit den Wert

Während gemäß der Theorie die Satzeinheit-Adressen in einer der Unterfolgen von 5a bis 6d enthalten sein können, ist dies in dem in Fig. 1 gezeigten Beispiel nicht der Fall. Man bemerke, daß in Fig. 1 die Unterteilung in die fünfte und sechste Adressen-Unterfolge unter Steuerung des Schlüsselfeld-Bits von der Bewichtung 4 stattfinden soll. Dies ist in Tabelle ID dargestellt. Weiterhin muß festgehalten werden, daß die dritte Adressen_Unterfolge die Satzeinheit-Adressen 5, 6 und 1 enthält, von denen 5 und 6 zu der Unterfolge 3a und die Satzeinheit-Adresse 1 zur Unterfolge 3b gehören; Tabelle ID zeigt, daß das Schlüsselfeld-Bit von der Bewichtung 4 für beide Satzeinheit-Adressen 5 und 6 eine 0 ist. Wenn daher die dritte Adressen-Sequenz in eine fünfte und sechste Adressen-Unterfolge unterteilt wird, enthält die Unterfolge 3a keine der Satzeinheit-Adressen, die einem Schlüsselfeld-Bit von 1 in der in der Prüfung befindlichen Bewichtung 4 zugeordnet ist· Daher ist die Unterfolge 6a in Wirklichkeit leer. Fig. 3 zeigt, daß die die Unterfolge 6a symbolisierende Linie dünn ausgeführt ist und dadurch anzeigt, daß sie zu einer Un-

209832/1032

22007AA

terfolge gehört, die vorhanden sein könnte, in dem betrachteten Beispiel jedoch nicht vorhanden ist. In Fig. 3 sind diejenigen Linien, die in dem Beispiel tatsächlich vorhandene Unterfolgen anzeigen, stark ausgeführt; diejenigen Linien, die gültige Unterfolgen in einem binär codierten Dezimalsystem anzeigen, sind dünn gehalten, wenn sie in dem in Fig. 1 diskutierten Beispiel nicht vorhanden sind, während diejenigen Linien, die in einem binär codierten Dezimalcode nicht gültige Kombinationen anzeigen, in Fig. 3 gestrichelt eingetragen sind. Daher ist wiederum die Unterfolge 5b leer, da keine Satzeinheit-Adresse mit einem O-Bit in der Schlüsselfeld-Position mit der Bewichtung 4 in der Unterfolge 3b vorhanden ist. Die Adressen-Unterfolge 3b enthält lediglich die Satzeinheit-Adresse 1 (Tabelle IC). Die restlichen Linien in Fig. 3 können auf analoge Weise bestimmt werden. Man sieht, daß Fig. 3 acht gültige Ausgänge hat, die die acht Satzeinheiten in der Reihenfolge ihrer Schlüsselfeldwerte bezeichnen.

Ks wird jetzt eine bevorzugte Ausführungsform eines Systems zur Neuordnung von Adressen, das mit den Merkmalen der Erfindung ausgestattet ist, zunächst mit Bezug auf Fig. 4 beschrieben. Schon vorab wird bemerkt, daß kein Vergleicher für das Vergleichen von Daten-Bits in diesem System benutzt wird und daß das oben beschriebene Verfahren zur Adressen-Umordnung für das Sortieren benutzt wird. In dem bevorzugten Ausführungsbeispiel finden Satzeinheit-Adressenspeicher Verwendung, die wahlweise adressierbare Speicherstellen haben.

Es werde zur Beschreibung des bevorzugten Ausführunqsboispiels zunächst angenommen, daß die Satzeinheiten in einem Umlaufspeicher gespeichert seien und daß die von ihm zu gewinnenden Bits in Reihe ruureifbar sind. Ks werde weiter zunächst angenommen, daß das Schlüsselfeld den

209832/1032

anderen Feldern in den Satzeinheiten vorangeht. Die Daten können in dem vorerwähnten Umlaufspeicher entweder auf ineinander verschachtelte oder nicht verschachtelte Weise gespeichert sein. Geeignete Auslese-Einrichtungen für jede Art von Speichern werden weiter unten erläutert. Für die Betrachtung der Fig. 4 ist es lediglich wesentlich, daß die Satzeinheit-Adressen von einem ersten Satzeinheit-Adressenspeicher, nämlich dem Adressenregister A, in einen zweiten Satzeinheit-Adressenspeicher, nämlich das Adressenregister B und umgekehrt übertragen werden. Die Übertragung aller Satzeinheit-Adressen findet innerhalb einer Bit-Zeit statt, und die Übertragung einer einzelnen Satzeinheit-Adresse wird während einer Sub-Bit-Zeit oder Zeitmarke bewirkt. Man erinnere sich, daß die Unterteilung der Sequenz von Satzeinheit-Adressen in Unterfolgen unter Steuerung gleichbewichteter Schlüsselfeldbits stattfand., wobei eines von jeder Satzeinheit stammte. Die Schlüsselfeld-Bits seien die ersten aus dem die Satzeinheiten enthalten Umlaufspeicher ausgelesenen Bits. Sie werden an einem Anschluß aufgenommen, der in Fig. 4 als Dateneingang bezeichnet ist. Wenn sie in Reihe aufgenommen werden, gelangen sie zuerst in einen Serien-Parallel-Wandler und werden dann in ein Zwischenregister 11 unter Steuerung eines Ladesignals 53 übertragen. Das Zwischenregister 11 wird so gesteuert, daß - beginnend mit dem am wenigsten signifikanten .Schlüsselfeld-Bit - die nächst signifikanten Schlüsselfeld-Hits aus allen Satzeinheiten am Anfang jeder Bit-Zeit in es eingegeben werden. Sie werden in ihm solange gehalten, bis alle Satzeinheit-Adressen übertragen worden sind, und zwar jedes unter Steuerung des geeigneten Schlüsselfeld-Bits. Das nächst-signifikante Schlüsselfeld-Bit von jeder Satzeinheit wird dann am Anfang der nachfolgenden Bit-Zeit eingeführt. Bits einer gegebenen

209832/1032

Satzeinheit werden stets in die gleiche Stelle des Zwischenregisters 11 eingegeben. Die einzelnen Stellen in dem Zwischenregister 11 können für das Auslesen über Register-Adressiereinrichtungen 10, 13 zugreifbar sein. Der Multiplexer 10 ermöglicht die Auswahl irgendeines der in dem Zwischenregister 11 gespeicherten Bits unter Steuerung von Signalen auf der Leitung 12. Man bemerke, daß Leitung 12 zwar als Einzelleitung dargestellt ist, tatsächlich jedoch mehrere Leitungen· notwendig sind, um jede Stelle im Zwischenregister mit Hilfe des Multiplexers zu adressieren. Diese Vereinfachtung, nach der zur Darstellunq einer Mehrzahl von Leitungen für die parallele Übertragung von Signalen eine einzelne Leitung dargestellt ist, wird insqesamt in diese Figur zum Zwecke der besseren Übersichtlichkeit benutzt. Entsprechendes gilt für alle Tore, die mit solchen Leitungen zur Parallelübertraqung verbunden sind,beispielsweise die ODER-Tore 13. Der Multiplexer 10 zusammen mit den ODER-Toren 13 und den Leitungen 12 bildet die Reqister-Adressiereinrichtunq.

Eine Betriebsart-Steuerung 40 dient zur Steuerung der Ubertraqungsrichtunq, d. h., ob die Übertragung vom Adressenregister A zum Adressenregister B oder umgekehrt stattfinden soll. Diese Betriebsart-Steuerung kann in einfacher Weise durch ein Flip-Flop realisiert seinj das vom einen stabilen Zustand in den anderen durch die zur Bit-i'eit auftretenden Takt impulse während aufeinanderfolgender Schlüsselfeld-Zeiten umgestellt wird.

Das Flip-Flop wird vom einen stabilen Zustand in den anderen durch einen Ausgang von dem UND-Tor 59 umgestellt, das einen ersten Eingang aus den Taktimpulsen zur Bit-/eit während der Sch lüsself eld-'/ei t aufnimmt und dessen

209832/1032

zweiter Eingang der Ausgang eines ODER-Tores 60 ist. Die Eingänge zu dem ODER-Tor 60 sind LADE-ENDE-Signale, die · das Ende des Ladens der Register A und B anzeigen. Die Ableitung dieser Signale wird weiter unten im Zusammenhang mit Fig. 5 Erörtert.

Während der Zeit, während der das erste Bit aus jedem Schlüsselfeld in dem Zwischenregister 11 gespeichert wird, werden Adressen auf den Leitungen 12, die den Multiplexer 10 steuern, durch einen Zähler 14 über Leitungen 15 _t UND-Tore 16, Leitungen und ODER-Tore 13 zugeführt. Der Zähler 14 wird durch Sub-Bit-Taktimpulse auf der Leitung 19 gesteuert. Der Zähler 14 wird durch so viele Taktimpulse auf der Leitung 19 weitergestellt, wie Bit-Speicherstellen im Zwischenregister 11 enthalten sind. Die Zähler-Ausgangs-Signale aus dem Zähler 14 bilden die Satzeinheit-Adressen, da jedes Zähler- Ausgangs-Signal eine entsprechende Stelle im Zwischenregister 11 adressiert und jede Stelle im Zwischenregister 11 mit den Bits einer vorbestimmten Satzeinheit in Zeitsequenz versorgt wird, was im einzelnen in Verbindung mit Fig. 6 und 7 erklärt werden wird. Die UND-Tore 16 werden während dieser Zeit durch ein Zeitgeber-Signal auf der Leitung 18 aktiviert, das die UND-Tore 21 und 22 sperrt (bzw. die Ausgänge des Adressenregisters B und des Adressenregisters A steuert) über den Inverter 20. Die Adressensignale, die die UND-Tore 16 (erste Tore) während der ersten Bit-Zeit der Schlüsselfelder von einer Datengruppe passieren, werden über Leitungen 23, ODER-Tore 24, Leitungen 25 auf den Dateneingano zum Adressenregister A übertragen. Der Adressen-Eingang des Adressenregisters A wird durch einen O-Adressen-Zähler 26 und einen 1-Adressen-Zähler 27 gesteuert. Adressen-Zähler-Steuerung 28 und die Betriebsart-Steuerung 40 arbeiten wie folgt: Die Betriebsart-Steuerung 40 liefert ein Ausqangssdqnal auf Leitung 29a, das die Adressen-Zähler-Steuerunq ?8 in Betrieb setzt.

20983 2/1032

Die Adressen-Zähler-Steuerung 28 aktiviert den O-Adressen-Zähler 26 über die Leitung 31 und den 1-Adressen-Zähler 27 über Leitung 32. Die UND-Tore 33 und 34 geben die Adressen aus dem O-Adressen-Zähler 26 und 1-Adressen-Zähler 27 auf das Adressen-Register A. Die UND-Tore 33 und 34 werden durch Signale auf den Leitungen 35 und aktiviert. Entweder der Adressen-Zähler 26 oder der Adressen-Zähler 27 können zur Adressierung des Registers A benutzt werden. Die Auswahl geschieht durch das Signal auf der Leitung 37a, dem Ausgangs-Signal des Multiplexers 10. Wenn der Multiplexer 10 durch ein Signal auf den Leitungen 12 auf eine ein 1-Bit speichernde Speicherstelle des Zwischenregisters 11 adressiert wird, wird das Signal auf der Leitung 37a den 1-Adressen-Zähler 27 aktivieren, der eine Register-Adresse über Leitungen 50, UND-Tore 34 an das Adressen-Register A liefert. Wenn die adressierte Registerstelle in dem Zwischenregister 11 ein O-Bit speichert, wird das Signal auf der Leitung 37a in dem Inverter 58 invertiert und aktiviert den Adressen-Zähler 26, der seine Adresse über die Leitungen 38 und die UND-Tore 33 an das Adressenregister A liefert. Der erste Ausgang (Adresse), der von dem Zähler 26 geliefert wird, ist die der "0" zugewiesene Speicherstelle des Adressenregisters B.

Ein aktivierter 1-Adressen-Zähler 27 liefert ein Adressen-Signal auf den Leitungen 50 an die UND-Tore 34 zur Steuerung des Adressenregisters A und über die Leitungen 39 an die Adressen-Zähler-Steuerung 28, die ihrerseits Steuersignale auf der Leitung 32 zur Weiterstellung des 1-Adressen-Zählers 27 auf die nächste Speicher-Adresse erzeugt. Der erste Ausgang (Adresse) , der durch den Zähler 27 geliefert wird, adressiert die der "1" zugewiesene Speicherstelle im Adressen-Register A.

209832/ 1 032

Der O-Adressen-Zähler 26 liefert gleichwertige Signale über die Leitungen 41 an die Adressen-Zähler-Steuerung

28 und nimmt Zählerweiterstell-Signale über die Leitung 31 auf. Während der ersten Bit-Zeit eines Schlüsselfeldes steuern die Adressen-Zähler 26 und 27 das Speichern der von dem Zähler 14 gelieferten Satzeinheit-Adressen in dem Adressen-Register A.

Sobald die erste Gruppe von gleichbewichteten Bits der in dem Zwischenregister 11 gespeicherten Schlüsselfelder geprüft worden sind, wird das Signal auf der Leitung entfernt, wodurch das UND-Tor 16 gesperrt und die Tore, 21 und 22 (zweite und erste Tore) geöffnet werden, so daß sie auf Signale an ihren anderen zwei Eingängen ansprechen können. Gleichzeitig nimmt die Betriebsart-Steuerung 40 einen ersten Impuls auf der Leitung 43 auf, der den Anfang einer anderen Bit-Zeit anzeigt. Die Betriebsart-Steuerung 40 ändert die Signale auf den Ausgangsleitungen

29 und 30. In dem neuen Zustand steuert die Betriebsart-Steuerung 40 die Übertragung von in dem Adressen-Register A gespeicherten Adressen in das Adressen-Register B. Die Adressen-Zähler-Steuerung 28 wird auf "Lesen" geschaltet, während die Adressen-Zähler-Steuerung 46 im "Schreib"-Betriebszustand arbeitet. Die Arbeitsweise des 0-Adressenzählers 44, 1-Adressen-Zählers 45 der Adressen-Zähler-Steuerung 46 sowie der UND-Tore 47 und 48 ist mit der oben für die gleichwertigen Komponenten 26, 27, 28, 33 und 34 des Adressen-Registers A beschriebenen Betriebsweise identisch. Die auf "Lesen" geschaltete Adressen-Zähler-Steuerung 28 aktiviert den O-Adressen-Zähler 26 über die Leitung 31, damit er die Satzeinheit-Adressen aus dem Adressen-Register A auslesen kann. Zu diesem Zweck wird der O-Adressen-Zähler 26 in die O-Position zurückgesetzt, während der 1-Adressen-Zähler 27 in seiner letzten Position verbleibt. Der O-Adressenzähler 26

209832/1032

wird,von der der ¹¹O" zugewiesenen Speicherstelle beginnend, alle Speicherstellen des Adressen-Registers B in Sequenz adressieren, bis seine Adresse gleich jener ist, die in dem 1-Adressen-Zähler 27 gespeichert ist. Jedesmal, wenn O-Adressen-Zähler 26 eine andere Stelle in dem Adressen-Register B adressiert, passiert die in dieser Stelle gespeicherte Adresse die UND-Tore 22 und gelangt in den Multiplexer IO über die Leitungen 49b, ODER-Tore 13 und Leitungen 12· Die gleiche Adresse wird in den Daten-Eingang des Adressenregisters A über die Leitung 49c gegeben. Sie wird in dem Adressen-Register A unter Steuerung der Adressen-Zähler-Steuerung 46 und entweder, des O-Adressen-Zählers 44 oder des I-Adressen-Zählers 45 gespeichert, was von dem Inhalt der adressierten Registerstelle im Zwischenregister 11 abhängt. Sobald der G-Adressen-Zähler 26 einen Zustand erreicht, der gleich dem Zustand des I-Adressen-Zählers 27 ist, sperrt die Adressen-Zähler-Steuerung 28 den O-Adressen-Zähler 26 und stellt den 1-Adressen-Zähler 27 auf seinen ursprünglichen Zustand zurück. Der 1-Adressen—Zähler 27 wird mit dem Lesen der Satzeinheit-Adresse von der der "1" zugewiesenen Speicheradresse des Adressen-Registers A beginnen und mit aufeinanderfolgend adressierbaren Satzeinheit-Adressen-Speicherstellen in dem Adressen -Register A fortfahren. Der 1-Adressen-Zähler 27 liefert die Stellen-Adressen an den Adressen-Eingang des^yAdressen-Registers A über die Leitungen 50 und die UND-Tore 34. Die gleiche Adresse wird weiterhin auf die Adressen-Zähler-Steuerung 28 über die Leitungen 39 gegeben für den Vergleich mit der in dem O-Adressen-Zähler 26 gespeicherten Adresse. Der Zyklus, währenddessen die Adressen von dem Adressen-Register A über die UND-Tore 22 und die Leitung 49c an das Adressen-Register B übertragen werden, wird beendet, sobald der 1-Adressen-Zähler 27 ei-

209832/1032

220074.«

nen Zustand erreicht, der demjenigen des O-Adressen-Zählers 26 gleicht, was weiter unten im Zusammenhang mit Fig. 5 beschrieben werden wird.

Zu dieser Zeit sind alle in dem Zwischenregister 11 gespeicherten Schlüsselfeld-Bits untersucht worden und zur Relokalisierung der Satzeinheit-Adressen vom Adressen-Register A in das Adressen-Register B benutzt worden. Signale, die den Inhalt der adressierten Register-Stelle in dem Zwischenregister 11 bezeichnen, wurden dem 1-Adressen-Zähler 45 über die Leitung 37b und 37c zugeführt, während der O-Adressen-Zähler 44 das invertierte Signal auf der Leitung 37b über den Inverter 51 und Leitung 52 empfangen hat. Zur gleichen Zeit wurde der Serien-Parallel-Wandler mit der nächsten Gruppe von gleichbewichteten Schlüsselfeld-Bits geladen. Diese Bit-Gruppe wurde durch ein Signal auf der Leitung 53 in das Zwischenregister

11 übertragen, während gleichzeitig die Betriebsart-Steuerung 40 einen Schaltimpuls auf Leitung 43 empfängt. Die Betriebsart-Steuerung 40 ändert ihren Betriebszustand und steuert die Übertragung von Adressen aus dem Adressen-Register B in das Adressen-Register A ähnlich der Weise, wie sie vorstehend beschrieben wurde.. Während dieser Phase werden Satzeinheit-Adressen von dem Adressen-Register B dem UND-Tor 21 zugeführt und erreichen den Daten-Eingang des Adressen-Registers A über die ODER-Tore 24 und die Leitungen 25. UND-Tore 21 geben die gleichen Signale über Leitungen 49a auf das ODER-Tor und Leitung

12 für die wahlweise Steuerung des Multiplexers 10.

Die wechselseitige Übertragung von Satzeinheit-Adressen aus dem Adressen-Register B in das Adressen-Register A und umgekehrt wird gesteuert durch die Betriebsart-Steuerung 40, die einen Impuls pro Bit-Zeit auf der Leitung 43 empfängt, und zwar gleichzeitig mit der Aufnahme eines Ladesignal· auf Leitung 53 durch das Zwischenregi-

209832/1032

22007U

ster 11 mit der Ausnahme, daß das Signal auf der Leitung 43, das die Betriebsart-Steuerung 40 schaltet, nur dann erzeugt wird, wenn das Zwischenregister 11 Bits empfängt, die mit dem Schlüsselfeld in Verbindung stehen. Sobald das gesamte Schlüsselfeld untersucht worden ist und diejenigen Daten-Bits, die mit dem Schlüsselfeld nicht in Beziehung stehen, in das Zwischen-Register 11 gelangen, verbleibt die Betriebsartsteuerung 40 in ihrem letzten Zustand. Jetzt ist die Folge der Satzeinheit-Adressen, die entweder in dem Adressen-Register A oder in dem Adressen-Register B (entsprechend dem letzten Zustand der Betriebsart-Steuerung 40) gespeichert sind, in Übereinstimmung mit den Werten der Schlüsselfelder relativ zueinander. Ein Daten-Übertragungssignal auf der Leitung 54 aktiviert UND-Tor 55 und liefert einen Daten-Ausgang auf der Leitung 56 für Bits, die vom Zwischenregister 11 über Leitungen 37a und 57 ausgewählt worden sind. Da die Betriebsart-Steuerung 40 ihren Zustand während der Daten-Auslesung nicht ändert, werden die· Satzeinheit-Adressen wiederholt aus dem Adressen-Register A oder dem Adressen-Register B ausgelesen, je nachdem, welches die sortierte Folge während jeder Bit-Zeit enthält. Es ist ohne Bedeutung, daß das andere der beiden Adressen-Register A und B (welches gerade auf "Schreiben" gesetzt ist) diese Satzeinheit-Adressen aufzeichnet.

Man nehme nun an, daß die Schlüsselfelder der Satzeinheiten, die sortiert werden sollen, vor den anderen Feldern angeordnet sind und daß das Signal "erste Bit-Zeit im Schlüsselfeld" identisch ist mit der rrsten Bit-Zeit nach dem Start der Satzeinheit. Wenn das Schlüsselfeld innerhalb der Satzeinheit angeordnet ist, kann ein äquivalentes Steuersignal, das das erste Zeichen des Schlüsselfeldes anzeigt, zur Identifizierung der ersten Bit-

209832/ 1 032

- 25 - . ■

Zeit innerhalb des ersten Zeichens des Schlüsselfeldes herangezogen werden.

Man entnimmt dem Vorstehenden, daß das UND-^Tor 55 ein Daten-Ausgangs-Tor bildet, das durch ein Signal auf der Leitung 54 aktiviert wird, nämlich das Ausgangs-Signal. Das Signal, das an dem in Fig. 4 mit "Daten-Ausgang" bezeichneten Anschluß auftritt, ist ein verschachteltes Signal, in welchem die Bits der gleichen Satzeinheit stets die gleiche Sub-Bit-Zeit besetzen. Die Reihenfolge, in der während jeder Bit-Zeit die Bits der verschiedenen Satzeinheiten auftreten, entspricht den Schlüsselfeld-Werten der Satzeinheiten.

Der Anschluß eines vorbeschriebenen Systems an ein Gesamt-System mit beispielsweise Eingangs- und Ausgangs-Umlauf speichern, die Signale am Daten-Eingang abgeben und Signale vom Daten-Ausgang aus Fig. 4 aufnehmen, wird weiter unten erörtert, und zwar nach der Diskussion der Adressen-Zähler-Steuerung gemäß Fig. 5.

Man bemerke, daß die Adressen-Register A und B und der Multiplexer 10 Standardeinrichtungen sind, die überall vorrätig sein können..So kann insbesondere für die Adressen-Register A und B ein Fairchild read-write memory 9035 verwendet werden, der ein nichtlöschender Halbleiter-Speicher ist. Die Fairchild-Einheit 9309 oder 9312 kann als Multiplexer dienen. Die Taktsignale können direkt von dem Umlaufspeicher abgeleitet werden, der, wie weiter unten beschrieben wird, die Daten liefert.

Fig. 5 zeigt eine Adressen-Zähler-Steuerschaltung, die zur Verwendung in der Schaltung gemäß Fig. 4 geeignet ist.Einige der Schaltungskomponenten aus Fig. 4 sind auch in Fig. 5 gezeigt, um die Art der wechselseitigen Verknüpfung zu erläutern. Entsprechende Teile in Fig. 5

209832/103 2

tragen das Bezugszeichen aus Fig. 4, das lediglich um ' den Summand 100 erhöht wurde. Diejenigen Schaltungskomponenten, die ohne entsprechendes Gegenstück in Fig. sind, sind mit Bezugszeichen über 164 versehen.

Fig. 5 zeigt eine Ausführungsform eines ersten Satzeinheit-Adressen-Speichers, nämlich das Adressen-Register A, das das gleiche Adressen-Register wie dasjenige aus Fig. 4 ist. Adressen-Register A hat eine Kapazität von 32 Wörtern von je 5 Bits. Das Adressen-Register A hat .Ein-

■i_ ς ■ ' l—5""*-

gangsleitungen 125 sowie Ausgangsleitungen 165 ,

1—5 sowie Stellen-Auswahlleitungen 166 , um eine der 32

1— 5

Stellen zu adressieren. Die Leitungen 125 entsprechen den Leitungen 25 aus Fig. 4. Auf diesen Leitungen werden Satzeinheit-Adressen dem Adressen-Register A im "Schreib^Zustand zugeführt. Die Leitungen 149¹"⁵ führen Satzeinheit-Adressen zur Übertragung in das Adressen-Register B während derjenigen Zeit, während der das Adressen-Register A im "Lese"-Zustand ist. Die Leitungen

1—5

166 stellen Platzwähler-Leitungen dar, die die spezielle Speicherstelle in dem Adressen-Register A, in die eine Satzeinheit-Adresse gespeichert oder von der eine Satzeinheit-Adresse gelesen- werden soll, auswählt. Weiter empfängt das Adressenregister A ein Betriebsart-Signal auf der Leitung 129a, die in diesem Fall ein "Schreib"-Signal ist. Der einzig verbleibende Eingang zu dem Adressen-Register A ist der Takteingang 167.

Das Adressen-Register A nimmt die Wähler-Ausgangs-'Signale

1-5

auf den Platzauswahlleitungen 166 auf. Die Wähler-Ausgangs-Signale stammen aus einem zweiten Multiplexer 168. Der Multiplexer 168 entspricht einer Kombination von UND-Toren 33 und UND-Toren 34 aus Fig. 4. Die Wähler-Ausgangs-Signale entsprechen, abwechselnd, den "1^M-Wähler-^signalen, die am Eingang 2 des Multiplexers 168 aufgenommen werden, oder den "Ο''-Wähler-Signalen, die am

209832/1032'

Eingang .1 des Multiplexers 168 auftreten. Die "O"-Wähle*~ Ausgangs-Signale werden von dem "O"-Adressenzähler 126 geliefert, während die "1"-Wähler-Ausgangssignale von dem

1— "1"-Adressen-Zähler 127 herkommen. Die Leitungen 138 verbinden den Ausgang des "O"-Adressen-Zählers 126 mit dem ersten Eingang des Multiplexers 168, während die

1-5
Leitungen 161 den Ausgang des "Ι''-Adressen-Zählers 127 mit dem zweiten Eingang des Multiplexers 168 verbinden.

Es hängt von der Betriebsart ab, ob entweder der '¹¹I"-Adressen-Zähler 127 oder der "O"-Adressen-Zähler~ 126. .

•als Quelle zur Aktivierung der Platzwähler-Leitungen

1—5

166 ausgewählt wird, die die Adressen-Registerstelle bestimmen, in welche eine Satzeinheit-Adresse gespeichert oder aus welcher ausgelesen werden soll. Zunächst werde diejenige Betriebsart betrachtet, in der das Adressen—Register A geladen wird. Zu Beginn dieser Schreib- oder Lade-Betriebsart wird der "O"-Adressen-Zähler 126 insgesamt auf Nullen gesetzt, während der "l"_Adressen-Zähler 127 insgesamt auf Einsen gesetzt wird.

Während des Ladens führen alle Leitungen 129a, die in Fig. 5 als LADEN bezeichnet sind, ein Aktiviersignal. Dieses Signal entspricht den Signalen auf der Leitung 29a am Ausgang der Betriebsart-Steuerung in Fig. 4. Das Lade-Signal wird auf ODER-Tore 169 und 170 gegeben, wodurch Aktiviersignale an den Ausgängen dieser Tore auftreten. Diese Signale öffnen ihrerseits die UND-Tore 171 und 172. UND-Tor 171 steuert die Übertragung der Speicherplatz-Adressen vom "1"-Adressen-Zähler 127 zum Ausgang des Multiplexers 168, während das UND-Tor 172 die Übertragung der Ausgänge des "O"-Adressen-Zählers auf die Leitungen 166 ~ steuert. Der zweite Eingang

209832/ 1 032

des UND-Tores 172 wird vom Ausgang eines Inverters 173 abgeleitet, während der zweite Eingang des UND-Tores vom Ausgang eines Inverters 174 kommt. Man bemerke, daß der Inverter 173 das Ausgangssignal der "1"-Zähler-Toreinrichtung, nämlich des UND-Tores 175, invertiert, während der Inverter 174 den Ausgang des "0"-Zähler-Tores, nämlich des UND-Tores 176, umkehrt. Die UND-Tore 175 und 176 führen ein Aktivier-Ausgangssignal, wenn das Schlüsselfeld-Bit, unter dessen Steuerung die Übertragung stattfindet, eine "1" oder eine "O" ist. Dieser Teil der Schaltung arbeitet so, daß dadurch die Stelle im Adressen-Register A durch den "1^M-Adressen-Zähler bestimmt wird, wenn das Schlüsselfeld-Bit eine "1" ist und durch den "O"-Adressen-Zähler bestimmt wird, wenn das Schlüsselfeld-Bit eine "O" ist.

Die UND-Tore 175 und 176 dienen weiterhin dazu, den "1"-Adressen-Zähler 127 bzw. den "O"-Adressen-Zähler 126 zu aktivieren. Der Ausgang des UND-Tores 176 ist mit dem Aktivier—Eingang des "O"-Adressen-Zählers 126 über ein ODER-Tor 177 verbunden, während der Ausgang des UND-Tores 175 mit dem Aktiviereingang des "1"-Adressen-Zähler über das ODER-Tor 178 verbunden 1st.

Während das Adressen-Register A durch Signale auf den Leitungen 166¹""⁵ aktiviert wird und die "0"- sowie "1"-Adressen-Zähler durch die vorbeschriebenen Signale aktiviert werden, findet die tatsächliche Übertragung in das Adressen-Register A bei Auftreten eines Taktimpulses auf der Leitung 167 statt, während der gerade aktivierte Zähler um einen Zählschritt weitergestellt wird durch ein Taktsignal, das er über Leitung 179 aufnimmt. Das Taktsignal auf der Leitung 179 muß mit kleiner Verzögerung dem Taktsignal auf Leitung 167 folgen. Das Ende des Lade-Zyklus ist erreicht, wenn der Adressen-Zähler 126 in einer Position neben der des Adressen-Zählers 127 steht, da

209 B 3 2/1032

der "1"-Adressen-Zähler umgekehrt gezählt hat, während der "O"-Adressen-Zähler für jede: in dem Adressen-Register A gespeicherte Satzeinheit-Adresse vorwärts gezählt hat, und zwar unter Steuerung eines "1"- bzw. eines "O"-Schlüsselfeld-Bits.

Diese Beziehung in den Positionen zwischen dem "O"-Adressen-Zähler und dem "1"-Adressen-Zähler wird durch einen Komparator 180 bestimmt, dessen Ausgangssignal auf einer Leitung 181 steht, wenn die beiden Zähler die vorerwähnten benachbarten Ausgänge haben. Ein Aktiviersignal auf der Leitung 181 stellt ein Komparator-Ausgangs-Signal dar. Die Anwesenheit eines Komparator-Ausgangs-Signals und eines Lade-Signals wird angezeigt durch ein LADEN-.ENDE-Signal am Ausgang des UND-Tores 182. Das LADEN-ENDE-Signal läßt die Steuer- und Programmiereinrichtung (Betriebsart-Steuerung) sämtliche LADE-Signale entfernen. Als nächstes werden die Lese-Signale für das Adressen-Register A aktiviert. Diese entsprechen den Signalen auf der Leitung 30b in Fig. 4. Diese Signale aktivieren die UND-Tore 183 und 184. Ein START-Signal auf der Leitung 188, das ein Zeitgeber-Signal vor dem ersten Sub-Bit-Taktimpuls jeder Bit-Zeit ist, läßt das Flip-Flop 185 zurücksetzen und das Flip-Flop 186 setzen. Ein START-Signal auf der Leitung 188 und ein Komparator-Ausgangs-Signal auf der Leitung 181 öffnen ein UND-Tor 189, dessen Ausgangssignal den "O"-Adressen-Zähler 126 auf sämtlich Nullen zurückstellt. Der totale Null-Zustand entspricht der der "0" zugewiesenen Speicherstelle in dem Adressen-Register B. Das Zurückstellen des "O"-Zählers, 126 läßt das Komparator-Ausgangs-Signal inaktiv werden. Dadurch wiederum wird das UND-Tor 189 gesperrt,und der "O"-Adressen-Zähler 126 wird nicht mehr länger festgehalten.

209832/ 1 032

Ein Aktiviersignal am RücJcstell-Ausgang des Flip-Flops 185 läßt ein Signal auf der Leitung 190 entstehen, das, zusammen mit dem Lese-Signal auf Leitung 130a, das UND-Tor 184 aktiviert und, über.das ODER-Tor 177, den Aktivier-Ausgang des "O"-Adressen-Zählers 126 aktiviert.' Der "O"-Adressen-Zähler wird somit Schritt für Schritt weitergestellt für jedes auf der Leitung 179 aufgenommene Zeitgeber-Signal. Weiterhin wird das Signal auf der Leitung 190 über das ODER-Tor 170 auf einen Eingang eines UND-Tores 172 gegeben, dessen anderer Eingang aktiviert ist, da am Ausgang des UND-Tores 175 kein Signal steht. Somit wird der Multiplexer 168 in der Weise gesteuert, daß "O"-Wähler-Ausgangs-Signale, nämlich der Ausgang des "O"-Adressen-Zählers 126, die Signale auf

1-5
den Leitungen 166 bilden, wodurch die Stelle in dem Adressen-Register A, aus der ausgelesen werden soll, bestimmt wird. Die-Satzeinheit-Adresse in der so adres-

1-5 · sierten Stelle steht damit auf den Leitungen 165 zur Verfügung und wird auf die Adressen-Sammelleitung über Tore 121 übertragen, die bei Abwesenheit eines Lade-Signales auf der Leitung 129a aktiviert sind. Die auf

1-5

der Adressen-Sammelleitung 149 erscheinende Satzeinheit-Adresse wird auf den Multiplexer 110 (Fig. 4) zur Auswahl eines entsprechenden Schlüsselfeld-Bits gegeben und wird dann auf die· Einganga-Adressen-Sammelleitung des Adressen-Registers A gemäß Fig. 4 weitergeführt. Während dieses Arbeitsablaufs nimmt das Adressen-Register A sämtliche Satzeinheit-Adressen auf und speichert sie in der richtigen Reihenfolge in den richtigen stellen, wie sie von den ausgewählten Schlüsselfeld-Bits bestimmt werden.

Für jede aus dem Adressen-Register B ausgelesene Satzeinheit-Adresee wird der "O"-Adreesen-Zähler 126 um eine

209832/103 2

Zählstufe weitergezählt, bis der Komparator 180 ein Komparator-Ausgangs-Signal auf der Leitung 181 abgibt. Bei im wesentlichen gleichzeitigem Auftreten eines Komparator-Ausgangs-Signals und eines Signals am Setz-Ausgang des Flip-Flops 186 wird das Flip-Flop 185 aktiviert und springt in den gesetzten Zustand auf das nächste Zeitgeber-Signal auf der Leitung 187 hin.

Die gleichzeitige Anwesenheit eines Lese-Signals, eines Komparator-Ausgangs—Signals und eines Signals an dem Setzausgang (Q) des Flip-Flops 186 aktiviert ein UND-Tor 191 und läßt den "1"-Adressen-Zähler 127 über ein ODER-Tor 192 insgesamt auf Einsen zurücksetzen. Dieses Zurücksetzen des "1"-Adressen-Zählers 127 läßt das Komparator-Ausgangssignal inaktiv werden.

Der Ausgang bei Q des Flip-Flops 185 gelangt weiterhin auf einen Eingang eines ODER-Tores 169 und durch es hindurch auf einen Eingang eines UND-Tores 171, dessen anderer Eingang bei Abwesenheit eines Lade-Signales am Eingang eines UND-Tores 176 aktiviert wird. Der Multiplexer 168 arbeitet daher so, daß die Wähler-Ausgangs-Signale, die die Stelle in dem Adressen-Register B bestimmen, aus der Satzeinheit Adressen ausgelesen werden sollen, von dem "1^M-Adressenzähler 127 statt vom "0"-Adressen-Zähler 126 abgeleitet werden. Weiterhin aktiviert der Q-Ausgang des Flip-Flops 185 ein UND-Tor 183 und läßt den "1"-Adressen-Zähler 127 über ein ODER-Tor 178 aktiviert werden. Der "!"-Adressen-Zähler 127 wird dann bei jedem über die Leitung 179 aufgenommenen Taktimpuls rückwärts zählen. Das Taktsignal auf Leitung 167, das während der gleichen Sub-Bit-Zeit wie das Taktsignal auf Leitung 179 auftritt, muß wiederum dem letzteren etwas vorhergehen, so daß das Auslesen abgeschlossen ist,

209832/10 32

ehe der "Ι''-Adressen-Zähler weitergestellt wird.

Die unter Steuerung des "1"-Adressen-Zählers 127 ausgelesenen Satzeinheit-Adressen dienen zur Auswahl eines Schlüsselfeld-Bits (und zwar jede ein entsprechendes Schlüsselfeld-iBit) und werden in dem. Adressen-Register B (Fig. 4) gespeichert auf genau die gleiche Weise, wie das für die Satzeinheit-Adressen beschrieben wurde, die unter Steuerung des "O"-Adressen-Zählers 126 geliefert wurden.

Das Auslesen der Satzeinheit-Adressen aus dem Adressen-Register B setzt sich fort, bis ein Komparator-Ausgangs-Signal wiederum auf der Leitung 181 erscheint. Dieses Komparator-Ausgangs-Siqnal in Verbindung mit einem Aktivier-Signal auf dem Q-Ausgang des Flip-Flops 185 läßt ein LESEN-ENDE-Signal am Ausgang des UND-Tores 193 erscheinen. Dieses LESEN-ENDE-Signal stellt den "1"-Adressen-Zähler in den Eins-Zustand und den "O"-Adressen-Zähler in den Zustand sämtlicher Nullen über das ODER-Tor 192 bzw. 194 zurück.

Der Multiplexer 168 bildet zusammen mit den UND-Toren 171 und 172 eine Auswahlschaltung, während das UND-Tor 189 eine Rückstellschaltung darstellt. Das UND-Tor 182 ist die LADEN-ENDE-Schaltung, während das UND-Tor 191 die auf "!"-Rücksetz-Schaltung bildet. Die Flip-Flops 185 und 186 bilden erste und zweite Flip-Flop-Einrichtungen.

Ein die Anordnung nach Fig. 4 umfassendes Gesamtsystem wird jetzt unter Bezugnahme auf Fig. 6 beschrieben, in der diejenigen Komponenten, die die gleichen wie in Fig, 4 sind, die gleichen Bezugszeichen, jedoch um den Summand 200 vergrößert, erhalten haben. Man sieht, daß Fig.

20983 2/103 2

6 einen ersten Umlaufspeicher 200 sowie eine zugeordnete Ausles-Einrichtung, hier ein einziges Auslese-Element 201, zeigt. Der erste Umlaufspeicher kann eine Spur auf einer Trommel, einer Platte oder jeder anderen geeigneten Form eines UmlaufSpeichers sein. In der in dieser Figur dargestellten Ausführungsform sind die Daten im ersten Umlaufspeicher in verketteter Form gespeichert. Eine Register-Eingangs-Einrichtung, die ein UNDLTor 202 umfaßt, sowie ein Serien-Parallel-Wandler 203 liefern Signale an das Zwischenregister 211. Man bemerke, daß die in dem Umlaufspeicher gespeicherten Daten durch das UND-Tor 202 seriell ausgelesen und durch den Serien-Parallel-Wandler in Sätze von Bits umgewandelt werden, wobei jeder Satz von Bits alle Bits während einer Bit-Zeit umfaßt. Somit wird während der Zeit, bei der das Schlüsselfeld ausgelesen wird, der Serien-Parallel-Wandler seinerseits Schlüsselfeld-Bits von gleicher Bewichtung von jeder Satzeinheit enthalten, beginnend (in diesem Beispiel) mit dem am wenigsten signifikanten Bit und sich fortsetzend bis zu dem signifikantesten Bit. Man bemerke, daß es für die Sortier-Operation notwendig ist, daß die Schlüsselfeld-Bits zuerst ausgelesen werden. Es müssen somit Synchronisiereinrichtungen vorgesehen sein, die das UND-Tor 202 erst dann öffnen und damit auf die Daten aus dem ersten Umlaufspeicher ansprechen lassen, wenn die Schlüsselfeld-Bits ausgelesen werden. Die Synchronisiereinrichtung 207 kann beispielsweise ein Flip-Flop umfassen, das von einem vom Umlaufspeicher 200 über ein zusätzliches Lese-Element 208 geliefertes Synchronisiersignal gesetzt wird. In jedem Falle wird der Serien-Parallel-Wandler zu einem Zeitpunkt gleichbewichtete Bits des gleichen Feldes in jeder Satzeinheit enthalten. Die in dem Serien-Parallel-Wandler gespeicherten Daten werden dann in das Zwischenregister weitergegeben, und zwar

209832/1032

ter Steuerung des Lade-Signals. Dieses Lade-Signal läßt die Daten von dem Serien-Parallel-Wandler 203 in das Register 211 schieben, und zwar am Beginn jeder Bit-Zeit. Der Multiplexer 210 wird durch die Satzeinheit-Adressen unter Steuerung der Sortiereinrichtung gemäß Fig. 4 adressiert. Man bemerke, daß die Leitungen 212 (wenn auch als Einzelleitung dargestellt, so jedoch Mehrfachleitungen repräsentierend) von einer Sortiereinrichtung, die hier mit 204 bezeichnet ist, den Inhalt einer speziellen Registerstelle (ein Bit) am Ausgang des Multiplexers 210 erscheinen lassen und dafür sorgen, daß er von diesem Ausgang auf einen zweiten Umlaufspeicher 206 über Torschaltungen, nämlich das UND-Tor 255,und Schreibeinrichtungen 205 übertragen wird. In dieser speziellen Ausführungsform sind die Schreibeinrichtungen ein einzelnes Element. Daten.werden in dem.zweiten Umlaufspeicher in einer verschachtelten Art.gespeichert. Während der Schlüsselfeld-Zeit dienen die Ausgänge des Multiplexers 210 auch ' als Eingang für die Sortiereinrichtung 204, um den Sortierprozeß zu steuern. Während dieser Eingang bei der Übertragung anderer Felder andauert, dient er keiner nutzbaren Funktion mit Ausnahme während der Schlüsselfeld-Zeit.

Man bemerke, daß in diesem System Daten aus dem ersten Umlaufspeicher ausgelesen, sortiert und in den zweiten Umlaufspeicher in sortierter Folge eingegeben werden, und zwar alles innerhalb eines Umlaufs des UmlaufSpeichers. Das Sortieren findet während der Schlüsselfeld-Zeit statt, die dem Auslesen anderer Daten vorhergeht. Die Satzeinheit-Adressen, sortiert entsprechend den Schlüsselfeld-Werten, steuern dann die Übertragung der restlichen Daten aus dem Zwischenregister in den zweiten Umlaufspeicher, in dem sie die Reihenfolge, in der die Bits gleicher Bewichtung innerhalb eines Satzes von Bits von dem Zwischenregister gelesen werden, umordnen.

2 09832/1032

Das UND-Tor 255 wird natürlich durch ein Daten-Übertragungssignal aktiviert, das von der Steuerung der Einrichtung erst dann geliefert wird, wenn die Entwicklung des Schlüsselfeldes während der Schlüsselfeld-Zeit stattgefunden hat.

Ein dem System nach Fig. 6 sehr ähnliches, weiteres System istin Fig. 7 dargestellt. Diejenigen Komponenten, die dem gleichen Element in Fig. 6 entsprechen, haben
wiederum gleiche Bezugszeichen, nur um 100 vergrößert.
Man bemerke, daß das System nach Fig. 7 fast identisch
mit demjenigen aus Fig. 6 ist, mit der Ausnahme, daß die einzelne Auslesvorrichtung 201 durch Mehrfachleser 301 "~ ersetzt worden sind, wobei η die Zahl der zu sortierenden Satzeinheiten repräsentiert, oder - damit gleichbedeutend - gleich der Anzahl von Sub-Bit-Zeiten innerhalb
einer Bit-Zeit ist» Die Leser 301 ~ sind relativ zum ersten Umlaufspeicher 300 so angeordnet, daß sie genau eine Satzeinheit auseinanderstehen, d. h., gleichbewichtete Bits eines aus jeder Satzeinheit werden gleichzeitig ausgelesen. Damit entfällt die Notwendigkeit, einen Serien-Parallel-Wandler wie in Fig. 6 vorzusehen. Die auf diese Weise ausgelesenen Bits werden sofort in dem Zwischenregister 311 gespeichert. Die Übertragung muß wiederum zeitlich durch ein Ladesignal gesteuert werden, das nicht dargestellt ist und das von dem ersten Umlaufspeicher abgeleitet werden kann. Beispielsweise kann es eine . Marke auf einer Platte, auf der Trommel, etc. sein. Der Multiplexer 310 arbeitet in Verbindung mit der Sortiereinrichtung 304 in genau der gleichen Weise, wie das im Zusammenhang mit Fig. 6 beschrieben wurde. Während der Datenübertragungszeit sind die Ausgangs-Tore 355 leitend, und Daten werden seriell in einen Serien-Parallel-Wandler 307 eingegeben. Der Ausgang des Serien-Parallel-Wandlers, wenn nämlich sämtliche Bits in einer speziellen

209832/1032

Bit-Zeit versammelt sind, wird in ein Zwischenregister 308 unter Steuerung eines zweiten Lade-Signals übertra- ■ gen, -das ebenfalls von dem ersten Umlaufspeicher abgeleitet sein kann, da der erste und der zweite Umlaufspeicher synchron betrieben werden, z. B. indem beide in dem gleichen Groß-Umlauf-Speicher angeordnet sind.

Der Ausgang des Zwischenregisters wird auf Schreiber

1—η
305 übertragen, die die Daten gleichzeitig in den zweiten Umlaufspeicher 306 eingeben. Die Schreibköpfe

1—η
305 sind ebenfalls um eine Satzeinheit gegeneinander versetzt. Jeder Kopf 305 ~ ist mit einer entsprechenden Zwischenregisterstel^Le verbunden. Man sieht, daß in diesem System der erste und zweite Umlaufspeicher Daten in nicht verm.isch.ter Form speichern. Wiederum ist das Tor 355 nur zu solchen Zeiten aktiviert, die der Schlüsselfeld-Zeit folgen, und nicht während der Schlüsselfeld-Zeit. Weiterhin wird nach der Schlüsselfeld-Zeit ..die Sortiereinrichtung 304 dafür sorgen, daß Bits von dem Zwischenregister 311 in sortierter Sequenz gelesen werden und daß sie in den Serien-Parallel-Wandler in dieser Sequenz eingegeben werden. Daher ist die Zwischenregisterstelle und der Aufzeichnungskopf 305 ~ⁿ, der für Bits einer speziellen Satzeinheit ausgewählt wurde, im allgemeinen nicht der gleiche wie der Lesekopf 301, der die entsprechende Satzeinheit von dem ersten Umlaufspeicher gelesen hat. Die Sortiereinrichtung 304 bestimmt die Zuordnung eines der Aufzeichnungsköpfe 305 "~ zu einer speziellen Aufzeichnungs-Einheit in Übereinstimmung mit dem Schlüsselfeld-Wert dieser Einheit. Die Daten sind in dem Datenspeicher 306 dann in sortierter Folge angeordnet.

Die in den Fig. 6 und 7 gezeigte Anordnung kann natürlich gleich gut für .Sortiersysteme Verwendung finden, in denen die Schlüsselfeld-Bits in absteigender Ordnung ihrer Signifikanz vorhanden sind, obaleich das hier in

209832/1032

Fig. 1 - Fig. 5 erläuterte Beispiel mit solchen Schlüsselfeld-Bits befaßt war, die in aufsteigender Reihenfolge ihrer Signifikanz angeordnet sind.

Das in den Fig. 1, 2 und 3 erläuterte Sortierverfahren
ist natürlich in gleicher Weise anwendbar auf Daten, die von statischen Speichern geliefert werden.

Ohne weitere Analyse offenbart das Vorstehende vollständig den geistigen Gehalt der vorliegenden Erfindung, so daßÄncJere mit Hilfe ihres Durchschnittswissens sie
leicht für verschiedene Anwendungsmöglichkeiten ausnutzen können, ohne daß dabei Merkmale, die vom Standpunkt der Technik aus wesentliche Eigenschaften bilden, weggelassen werden, so daß derartige Anwendungsfälle als im Rahmen der Erfindung liegend .anzusehen sind.

Zusammengefaßt sind somit Satzeinheit-Adressen, die Zugriff zu entsprechenden Satzeinheiten mit Schlüsselfeldern liefern, in einem ersten Speicher gespeichert, und zwar jeweils unter Steuerung des entsprechenden, am wenigsten signifikanten Schlüsselfeld-Bits. O-Schlüsselfeld-Bits bedeuten ein Speichern der Satzeinheit-Adressen in aufeinanderfolgenden Stellen nach einer der "O"
zugeordneten Speicherstelle; "1"-Schlüsselfeld-Bits bedeuten das Speichern von Satzeinheit-Adressen in aufeinanderfolgenden Stellen nach einer der "1" zugewiesenen Speicherstelle. Satzeinheit-Adressen in den der "O" zugewiesenen Speicherstellen des ersten Speichers werden dann in einen zweiten Speicher in der gleichen Weise unter Steuerung des nächst-signifikanten Schlüsselfeld-Bits übertragen· Danach werden die Satzeinheit-Adressen in den der "l'i zugewiesenen Speicherstellen des ersten
Speichers so in den zweiten Speicher übertragen· Die
Übertragungen werden wiederholt unter Steuerung sämtli-

209832/1032

eher Schlüsselfeld-Bits, wobei das Auslesen aus den der "O" zugewiesenen Speicherstellen jeweils den Auslesungen aus den der "1" zugewiesenen Speicherstellen vorhergeht.

209832/1032

Claims

ANSPRUCHE

^l. Verfahren zum Sortieren mehrerer, jeweils ein Schlüsselfeld aufweisender Satzeinheiten entsprechend einem Code-Wert der Schlüsselfelder, wobei jedes Schlüsselfeld mehrere,in vorbestimmter Reihenfolge angeordnete Schlüsselfeld-Bits umfaßt, dadurch gekennzeichnet, daß mehrere Satzeinheit-Adressen, von denen jede dem Zugriff auf eine ihr entsprechende Satzeinheit ermöglicht, in einer ersten Adressensequenz angeordnet werden und aus der ersten Adressen-Sequenz eine erste und eine zweite Adressen-Unterfolge gebildet wird, wobei eine der Adressen-Unterfolgen alle Adressen enthält, deren entsprechende Satzeinheiten als erstes Schlüsselfeld-Bit eine "O" und die andere Adressen-Unterfolge alle Adressen enthält, deren entsprechende Satzeinheiten als erstes Schlüsselfeld-Bit eine "1" haben; daß die erste und zweite Adressen-Unterfolge zu einer zweiten Adressen-Sequenz kombiniert werden, in der die Adressen aus der ersten Adressen-Unterfolge den Adressen aus der zweiten Adressen-Unterfolge vorhergehen; und daß die Bildung von Adressen-Unterfolgen aus Adressen-Sequenzen und das Kombinieren zu neuen Adressen-Sequenzen unter Steuerung der verbleibenden Schlüsselfeld-Bits fortgesetzt wird.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Satzeinheiten in der Reihenfolge der sortierten Satzeinheit-Adressen-Sequenz ausgelesen werden.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Satzeinheit-Adressen in der ersten Adressen-Unterfolge und in der zweiten Adressen-Unter-

209832/1032

folge in der gleichen Reihenfolge wie in der ersten
Adressen-Sequenz angeordnet sind.
4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß nach dem Kombinieren der ersten und zweiten Adressen-Unterfolge alle Satzeinheit-Adressen in der ersten Adressen-Unterfolge der zweiten Adressen-Unterfolge vorhergehen.
5. "Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß jedes Schlüsselfeld-Bit einen Codewert in einem bewichteten Binär-Code repräsentiert.
6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß jedes Schlüsselfeld-Bit einen Codewert in einem binär codierten Dezimal-Code repräsentiert.
7. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß die vorbestimmte Reihenfolge der Schlüsselfeld-Bits nach aufsteigenden Bit-Werten angeordnet ist.
8. Datenverarbeitungsanlage zur Bearbeitung von jeweils ein Schlüsselfeld aufweisenden Satzeinheiten, wobei jedes Schlüsselfeld mehrere in vorbestimmter Reihenfolge von Stellenwerten angeordnete Schlüsselfeld-Bits umfaßt, insbesondere zur Ausführung des Verfahrens nach einem
der vorhergehenden Ansprüche, gekennzeichnet durch ein Register (11) mit adressierbaren Registerstellen für
die Speicherung der Schlüsselfeld-Bits; durch einen ersten und zweiten Satzeinheit-Adressen-Speicher (A, B), von denen jeder eine der "O" und eine der "1" zugewiesene Speicherstelle besitzt; durch eine mit dem ersten Satzeinheit-Adressen-Speicher (A) verbundene Eingangs-Einrichtung (16, 23, 25 ...) für die Eingabe von Satz-

209832/10 3 2

einheit-Adressen, von denen jede einen Zugriff auf eine ihr entsprechende Satzeinheit ermöglicht, in den ersten Satzeinheit-Adressen-Speicher (A); durch mit dem Register (11) sowie mit dem ersten und zweiten Satzeinheit-Adressen-Speicher (A₁ B) verbundene Register-Adressier-Einrichtungen (10, 13), die ausgewählte Schlüsselfeld-Bits mindestens teilweise unter Steuerung der Satzeinheit-Adressen liefert; sowie durch eine den ersten und zweiten Satzeinheit-Adressenspeicher und das Register verbindende Adressen-Übertragungs-Einrichtung (21, 22, 49c, 24 ...) zur Übertragung von Satzeinheit-Adressen zwischen dem ersten und zweiten Satzeinheit-Adressen-Speicher mindestens teilweise unter Steuerung der ausgewählten Schlüsselfeld-Bits, derart, daß alle Satzeinheit-Adressen unter Steuerung von ausgewählten "O"-Schlüsselfeld-Bits in aufeinanderfolgend adressierbare Satzeinheit-Adressen-Speicherstellen, beginnend mit der der "0" zugewiesenen Satzeinheit-Adressen-SpeichersteHe,übertragen werden und daß alle Satzeinheit-Adressen unter Steuerung eines ausgewählten "1"-Schlüsselfeld-Bits in aufeinanderfolgend adressierbare Satzeinheit-Adressen-Speicherstellen, beginnend mit der der "1" zugewiesenen Satzeinheit-Speicheradressen-Stelle, übertragen werden.
9. Datenverarbeitungsanlage nach Anspruch 8, gekennzeichnet durch eine Register-Eingangs-Einrichtung zur Eingabe mehrerer Sätze von Schlüsselfeld-Bits in Sequenz in das Register, wobei jeder Satz ein Schlüsselfeld-Bit von vorbestimmtem Platzwert aus jeder Satzeinheit umfaßt.
10. Datenverarbeitungsanlage nach Anspruch 9, dadurch gekennzeichnet, daß der vorbestimmte Platzwert für jede Satzeinheit der gleiche ist.

20 9832/10 3 2
11. Datenverarbeitungsanlage nach einem der Ansprüche 8-10, gekennzeichnet durch eine. Einrichtung zur Abgabe von Bit-Zeitsignalen, durch eine Arbeitsart-Steuerung (40), die zwischen die Bit-Zeit-Signalgeber-Einrichtung (59, 60) und die Adressen-Übertragungs^-Einrichtung" geschaltet ist, derart, daß Übertragungen zwischen dem ersten und zweiten Satzeinheit-Adressen-Speicher in Abhängigkeit von Bit-Zeit-Signalen eingeleitet werden.
12. Datenverarbeitungsanlage nach einem der Ansprüche

8 bis 11, dadurch gekennzeichnet, daß die Register-Eingangs-Einrichtung die Schlüsselfeld-Bits in aufsteigen-. der Reihenfolge des Platzwertes liefert.
13. Datenverarbeitungsanlage nach Anspruch 11, dadurch gekennzeichnet, daß die Bit-Zeit-Signalgeber-Einrichtung zusätzlich mehrere Sub-Bit-Zeit-Signale zwischen aufeinanderfolgenden Bit-Zeit-Signalen abgibt; daß die Eingangs-Einrichtung Zähler (14) aufweist, die Ausgangs-Sig.nale in Abhängigkeit von den Sub-Bit-Zeit-Signalen abgeben; und daß erste Torschaltungen (16) den Zähler mit dem ersten Satzeinheit-Adressen-Speicher verbinden.
14. Datenverarbeitungsanlage nach Anspruch 11, dadurch gekennzeichnet, daß die Register-Adressier-Einrichtung einen Multiplexer (10) aufweist.
15. Datenverarbeitungsanlage nach einem der Ansprüche 11 bis 14, dadurch gekennzeichnet, daß die Arbeitsart-Steuerung (40) eine bistabile Schaltung aufweist, die ein erstes und ein zweites Betriebsart-Steuersignal in einem ersten und zweiten stabilen Zustand abgibt und vom einen zum anderen stabilen Zustand in Abhängikeit von jedem Bit-Zeit-Signal wechselt.

209832/1032 \

43 - .
16: Datenverarbeitungsanlage nach Anspruch 15, dadurch gekennzeichnet, daß die Adressen-Übertragungs-Einrichtung ein erstes Ausgangstor aufweist, dessen erster Eingang mit dem Ausgang des ersten Satzeinheit-Adressen-Speichers verbunden ist, dessen zweiter Eingang mit der Betriebsart-Steuerung (40) verbunden ist und deren Ausgang mit dem Eingang des zweiten Satzeinheit-Adresseh-Speichers verbunden ist; daß ein zweites Ausgangstor mit seinem ersten Eingang an den Ausgang des zweiten Satzeinheit-Adressen-Speichers, mit seinem zweiten Eingang mit der Betriebsart-Steuerung und dessen Ausgang mit dem Eingang des ersten Satzeinheit-Adressen-Spieichers verbunden ist.
17. Datenverarbeitungsanlage nach Anspruch 16, dadurch gekennzeichnet, daß die Adressen-Übertragungs-Einrichtung weiterhin erste und zweite Speicherplatz-Wähler (168) aufweist, die mit dem ersten und dem zweiten Satzeinheit-Adressen-Speicher jeweils verbunden sind und von denen jeder ein Wähler-Ausgangs-Signal abgibt, das eine ausgewählte Speicherstelle in dem zugeordneten Satzeinheit-Adressen-Speicher zum Auslesen oder Einschreiben aktiviert in Abhängigkeit von einem entsprechenden Betriebsart-Steuerungs-Signal und einem ausgewählten Schlüsselfeld-Bit.
18. Datenverarbeitungsanlage nach Anspruch 17, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler einen "O"-Adressen-Zähler (126) und einen "1"-Adressen-Zähler (127) aufweist, die ein "O"-Wähler-Ausgangs-Signal für jede unter "Steuerung "eines "O"-SchlÜsseifeld-M"ts übertragene Satzeinheit und ein "Ι''-Wähler-Ausgangs-Signal für jede unter Steuerung eines "Ι''-Schlüsselfeld-Bits übertragene Satzeinheit liefert.

20 9832/1032
19. Datenverarbeitungsanlage nach Anspruch 18, dadurch gekennzeichnet, daß der "O"-Adressen-Zähler (126) einen '" Aktiviereingang, einen Zählereingang und einen Rückstell-, eingang aufweist; und daß ein "0"-Zählertor vorgesehen ist, das ein Aktiviersignal auf den Aktiviereingang in Abhängikeit vom gleichzeitigen Auftreten eines "O"-Schlüsselfeld-Bits und eines ersten Betriebsart-Steuer-Signals gibt.
20. Datenverarbeitungsanlage nach Anspruch 18 oder 19, dadurch gekennzeichnet, daß der "1"-Adressen-Zähler (127) einen Aktiviereingang, einen Zählereingang sowie einen Rückstelleingang aufweist; und daß ein "1"-Zählertor vorgesehen ist, das ein Aktiviersignal auf den Aktiviereingang in Abhängigkeit vom gleichzeitigen Auftreten eines "1"-Schlüsselfeld-Bits und eines ersten Betriebsart-Steuerungs-Signals gibt.
21. Datenverarbeitungsanlage nach Anspruch 19 oder 20, dadurch gekennzeichnet, daß das "0"-Zählertor und das "1"-Zählertor jeweils ein UND-Tor aufweisen.
22. Datenverarbeitungsanlage nach einem der Ansprüche 8 bis 21, dadurch gekennzeichnet, daß die Bit-Zeit-Signalgeber-Einrichtung mehrere Sub-Bit-Zeit-Signale zwischen aufeinanderfolgenden Bit-Zeit-Signalen in solcher Anzahl liefert, die mehreren Satzeinheit-Adressen entspricht; und daß die Sub-^it-Zeit-Signale auf die Zähler-Eingänge der "0"- und "1"-Adressen-Zähler gegeben werden.
23. Datenverarbeitungsanlage nach einem der Ansprüche 8 bis 22, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler einen Vergleicher (180) mit einem ersten und zweiten Vergleicher-Eingang aufweist, die an den Ausgang des "0"- und des "1"-Adressen-Zählers an-

209832/1032

geschlossen sind,derart, daß ein Vergleicher-Ausgangs-Signal am Vergleicher-Ausgang auftritt, wenn das "O"-Wähler-Ausgangs-Signal und das "1"-Wähler-Ausgangs-Signal eine vorbestimmte Wechselbeziehung zueinander haben.
24. Datenverarbeitungsanlage nach einem der Ansprüche 8 - 23,dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler weiterhin eine Lade-Ende-Torschaltung zur Abgabe eines "LADEN-ENDE"-Signals in Abhängigkeit vom gleichzeitigen Auftreten des ersten Betriebsart-Steuer-Signals und des Vergleicher-Ausgangs-Signals aufweist.-
25. Datenverarbeitungsanlage nach einem der Ansprüche 8-24, gekennzeichnet durch eine Einrichtung zur Erzeugung eines"BEGINNE-LESEN"-Signals, das zeitlich auf das "LADEN-ENDE"-Signal_folgt.
26. Datenverarbeitungsanlage nach einem der Ansprüche 8-25, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler ein "0"-Rückstell-Tor aufweist, das auf die gleichzeitige Anwesenheit des "BEGINNE-LESEN"-Signals und des Vergleicher-Ausgangs-Signals zur Abgabe eines Rückstell-Signals auf den Ruckstell-Eingang des "O"-Adressen-Zählers anspricht.
27. Datenverarbeitungsanlage nach einem der Ansprüche 8-26, dadurch gekennzeichnet, daß der erste Speicher-

platz-Wähler ein erstes und zweites Flip-Flop (185, 131) aufweist, von denen jedes einen Setz- und einen Rücksetz-Ausgang, einen Setz- und einen Rücksetz-Aktivier-Eingang sowie einen Takteingang aufweist; und daß das zweite Flip-Flop weiterhin einen direkten Löscheingang aufweist; und daß das "BEGINNE-LESEN"-Signal auf den direkten Lösch-Eingang und den Setz-Aktivier-Eingang des ersten Flip-Flops gegeben wird.

209832/1032
28. Datenverarbeitungsanlage nach einem der Ansprüche 8-27, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler weiterhin ein "0"-Zählertor umfaßt, das ein Aktivier-Signal auf den Aktiviereingang des "0"-Adressen-Zählers in Abhängigkeit von dem gleichzeitigen Auftreten des Ruckstell-Ausgange des zweiten Flip-Flops und des zweiten Betriebsart-Steuerungs-Signals gibt.
29. Datenverarbeitungsanlage nach einem der Ansprüche 8-28, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler weiterhin erste und zweite Flip-Flops sowie UND-Tore aufweist, von denen jeweils ein erster Eingang mit dem Setzausgang des ersten Flip-Flops und ein zweiter Eingang mit dem Ausgang des Vergleichers verbunden ist; und daß das erste Flip-Flop-UND-Tor mit seinem Ausgang an den Setz-Eingang des zweiten Flip-Flops angeschlossen ist, und daß das zweite Flip-Flop-UND-Tor mit seinem Ausgang an den ersten Rückstell-Aktivier-Eingang des zweiten Flip-Flops angeschlossen ist.
30. Datenverarbeitungsanlage nach einem der Ansprüche 8-29, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler weiterhin ein "Ι''-Ruckstelltor aufweist, das auf die gleichzeitige Anwesenheit des Setz-Ausgangs des ersten Flip-Flops, des Komparator-Ausgangs-Signals und des zweiten Betriebsart-Steuersignals anspricht'und ein Rückstell-Signal auf den Rückstell-Eingang des Adressen-Zählers gibt.
31. Datenverarbeitungsanlage nach einem der Ansprüche 8-30, dadurch gekennzeichnet, daß der erste Speicherplatz-Wähler weiterhin ein zusätzliches "1"-Zählertor zur Abgabe eines Aktivier-Signals auf den Aktivier-Eingang des "1"-Adressen-Zählers in Abhängigkeit vom gleichzeitigen Auftreten des zweiten Betriebsart-Steuer-Signals und des Setz-Ausgangs des zweiten Flip-Flops gibt.

209832/103 2
32. Datenverarbeitungsanlage nach einem der Ansprüche

8 - 31, dadurch gekennzeichnet, daß der erste Speicher-Stellen-Wähler weiterhin eine Auswahlschaltung für die Auswahl eines "O"-Wähler-Ausgangs-Signals aufweist, um das Wähler-Ausgangs-Signal beim Auftreten eines "0"-Zähler-Aktiviersignals zu bilden, und zur Auswahl eines "!"-Wähler-Auegangs-Signals, um die Wähler-Ausgangs-Signale bei Auftreten eines "1"-Zähler-Aktiviersignals zu bilden.
33. Datenverarbeitungsanlage nach Anspruch.32, dadurch gekennzeichnet, daß die Wählerschaltung einen zweiten Multiplexer umfaßt, dessen erster Eingang mit dem Ausgang des "O"-Adressen-Zählers, dessen zweiter Eingang mit dem Ausgang des "!"-Adressen-Zählers verbunden ist und der einen ersten und zweiten Wähler-Eingang aufweist; und daß ein zweiter Multiplexer-Ausgang mit dem ersten Satzeinheit-Adressen-Speicher verbunden ist; und daß der erste und zweite Wähler-Eingang des zweiten Multiplexers mit dem Ausgang des "0"-Zählertores und des "1"-Zählertores jeweils verbunden sind.
34. Datenverarbeitungsanlage nach einem der Ansprüche 8-33, gekennzeichnet durch einen ersten Umlaufspeicher (200), auf dem die Satzeinheiten in willkürliche Reihengefolge gespeichert sind; durch Auslese-Einri'chtungen (201) für den ersten Umlaufspeicher (200); durch Register-Eingangs-Einrichtungen (202), die die Auslese-Einrichtungen und die Register zum Speichern mehrerer Sätze von Satzeinheit-Bits in Sequenz in den adressierbaren Register-Speicher-Stellen verbinden, wobei jeder Satz ein entsprechendes Bit von jeder Satzeinheit aufweist.

209832/ 1032
35· Datenverarbeitungsanlage nach einem der Ansprüche 8 - 34, dadurch gekennzeichnet, daß eine Zeitgeber-Einrichtung Bit-Zeit-Signale sowie mehrere Sub-Bit-Zeit-Signale in solcher Anzahl abgibt, die der Anzahl von Satzeinhei.ten zwischen aufeinanderfolgenden Bit-Zeit-Signalen entspricht; und daß die Register-Eingangs-Einrichtung die Sätze von Satzeinheits-Bits synchron mit den Bit-Zeit-Signalen liefert.
36. Datenverarbeitungsanlage nach einem der Ansprüche 34 und 35, dadurch gekennzeichnet, daß der erste Umlaufspeicher die Satzeinheiten in einem ineinander verschachtelten Muster speichert; daß die Ausleseeinrichtungen ein einzelnes LeseeXeihent aufweisen; und daß die Register-Eingangs-Einrichtuhgen einen Serien-Parallel-Wandler (203) umfassen.
37. Datenverarbeitungsanlage nach einem der Ansprüche 34 - 36, dadurch gekennzeichnet, daß der erste Umlaufspeicher die Satzeinheiten auf nicht-verschachtelte Weise speichert; und daß die Auslese-Einrichtungen mehrere Leser-Elemente, entsprechend der Anzahl der Satzeinheiten, aufweist.
38. Datenverarbeitungsanlage nach einem der Ansprüche 34 - 37, gekennzeichnet durch eine Synchronisier-Ein-«· richtung (207), die die Register-Eingangs-Einrichtung des ersten Umlauf-Speichers derart synchronisiert, daß mehrere Sätze von Schlüsselfeld-Bits allen anderen Sätzen von Satzeinheit-Bits zeitlich vorhergehen.
39. Datenverarbeitungsanlage nach einem der Ansprüche 8-38, dadurch gekennzeichnet, daß die Adressen-Über-

209832/ 1 032

tragungs-Einrichtung Ausgangstore aufweist, die ausgewählte Satzeinheit-Adressen, die in einem der Satzeinheit-Adressen-Speicher gespeichert sind, synchron mit •den Sub-Bit-Zeit—Signalen abgibt; daß die Register-Adressiereinrichtung in Abhängigkeit von jeder.der ausgewählten Satzeinheit-Adressen die Speicherstelle· in dem Register,entsprechend der ausgewählten Satzeinheit-Adresse adressiert, wodurch das ausgewählte Schlüsselfeld-Bit das Schlüsselfeld-Bit der entsprechenden Satzeinheit ist'; und daß die Adressen-Übertragungs-Einrichtung weiterhin Vorrichtungen aufweist, die die Satzeinheit-Adresse in eine einer '!O" zugewiesenen Speicherstelle oder in eine einer "1" zugewiesenen Speicherstelle im anderen Satzeinheit-Speicher einführt in Abhängigkeit von dem Wert des ausgewählten Schlüsselfeld-Bits.
40. Datenverarbeitungsanlage nach einem der Ansprüche 8 bis 39, dadurch gekennzeichnet, daß der erste und zweite Satzeinheit-Adressen-Speicher ein nicht-löschender Lese-Speicher ist; daß die Arbeitsart-Steuerung die Übertragungs-Richtung zwischen dem ersten und zweiten Satzeinheit-Adressen-Speicher bestimmt; daß eine dritte Steuerung an den Eingang der Arbeitsart-Steuerung zur Richtungsänderung der Übertragung in Abhängigkeit von jedem Bit-Zeit-Signal während der Schlüsselfeld-Lesezeit angeschlossen ist; daß ein Ausgangs-Umlauf-Speichef (206) vorgesehen ist; daß ein Daten-Übertragungs-Tor das Register mit dem Ausgangs-Umlauf-Speicher bei Aufnahme von Daten-Übertragungs-Torsignalen verbindet; und daß Daten-Ubertragungs-Torsignale nach der Schlüsselfeld-Auslese-Zeit erzeugt werden.

209832/1032