PatentDe  


Dokumentenidentifikation DE69304382T2 03.04.1997
EP-Veröffentlichungsnummer 0564290
Titel Hochgeschwindigkeitssortiergerät
Anmelder Questech Ltd., Wokingham, Berkshire, GB
Erfinder Billing, Robert, Crownhorne, Berkshire, GB
Vertreter Schwan, G., Dipl.-Ing., Pat.-Anw., 81739 München
DE-Aktenzeichen 69304382
Vertragsstaaten DE, FR, GB, IT
Sprache des Dokument En
EP-Anmeldetag 01.04.1993
EP-Aktenzeichen 933025850
EP-Offenlegungsdatum 06.10.1993
EP date of grant 04.09.1996
Veröffentlichungstag im Patentblatt 03.04.1997
IPC-Hauptklasse G06F 7/24

Beschreibung[de]

Es besteht bei Datenverarbeitungsanwendungen ein häufiges Bedürfnis nach einer Anordnung zum Sortieren einer Liste von Daten in eine Reihenfolge. Dies geschieht gewöhnlich mittels eines digitalen Computers, auf welchem ein Programm abläuft, in welchem einer aus einer Vielzahl von Algorithmen implementiert ist, welche entweder wiederholt die Positionen der Daten innerhalb der Liste austauschen, bis die Liste geordnet ist, oder welche eine Steuerinformation manipulieren, so daß die Liste in einer geordneten Weise gelesen werden kann, obschon die Daten ungeordnet verbleiben.

Alle diese Verfahren leiden an zwei Problemen: erstens ist die zum Sortieren der Liste benötigte Durchschnittszeit lang und zweitens existieren mögliche Anfangsreihenfolgen der Liste, welche dazu führen, daß die erforderliche Zeit die Durchschnittszeit um einen großen Betrag übersteigt.

Bei der Erzeugung von digitalen Videoeffekten mittels der Manipulation der Positionen von Pikseln eines Original-Videobilds kann eine Anforderung auftreten, bei welcher Datensätze, welche die Eingabe/Ausgabe-Abbildung der Verschiebung von Pikseln von dem Eingabe- zu dem Ausgabebild beschreiben, in eine Reihenfolge entsprechend der sequentiellen Abtastung des Ausgabebilds sortiert werden müssen.

Die veröffentlichte Patentanmeldung EP-A-0 369 415 offenbart bereits eine Anordnung zum schnellen Sortieren von Videodaten. Jedoch kann in Abhängigkeit von der Bitlänge des Schlüssels, nach welchem die Videodaten sortiert werden müssen, die Zuweisung von Speichermitteln ineffizient sein.

Es ist folglich eine Aufgabe der vorliegenden Erfindung, eine neue Vorrichtung zum Sortieren von Datensätzen zu schaffen, welche das obige Problem löst. Es versteht sich jedoch, daß die Erfindung, welche für die erforderliche Lösung sorgt, auf konventionelle Datenverarbeitung anwendbar ist, bei welcher jede Art von Daten in eine Reihenfolge sortiert werden soll.

Folglich schafft die Erfindung eine Vorrichtung zum Sortieren einer Liste von Datensätzen in einer Reihenfolge, die durch die entsprechenden Werte eines jeden Satzes einer Reihe von Schlüsselfeldern bestimmt ist, die in einer aufsteigenden Bedeutungsfolge sortiert sind, wobei die Vorrichtung eine erste Speicheranordnung aufweist, die über eine Anzahl von Adressen, welche mindestens gleich der Maximalzahl der zu sortierenden Sätze ist, und für jede Adresse über einen Speicherbereich verfügt, der die Daten eines Satzes aufnehmen kann; sowie eine Mehrzahl weiterer Speicheranordnungen, die jeweils über den Adressen der ersten Speicheranordnung entsprechende Adressen und für jede Adresse über einen Speicherbereich verfügen, der eine Adresse der ersten Speicheranordnung speichern kann, wobei die erste Speicheranordnung und die weiteren Speicheranordnungen unabhängig voneinander beschrieben und ausgelesen werden können; eine Anordnung zum Einschreiben einer Reihe von zu sortierenden Datensätzen in die erste Speicheranordnung; eine Logikschaltung um die Werte von Schlüsselfeldern, welche die gleiche Bedeutungsfolge haben, in einer vorgegebenen Sätze- Sortierfolge zusammen mit den Adressen in der ersten Speicheranordnung, an welchen die entsprechenden Sätze gespeichert sind, abzuleiten und um die abgeleiteten Adressen entsprechend der Bedeutungsfolge in eine der weiteren Speicheranordnungen als Zeiger einzuschreiben, welche für jeden Schlüsselwert eine verkoppelte Liste von Adressen von Sätzen bestimmen, die über den Schlüsselwert miteinander verknüpft sind, wobei die Logikschaltung für jede Bedeutungsfolge des Schlüsselfeldes, für das Werte abgeleitet werden, mit Ausnahme der niedrigsten Bedeutungsfolge , eine Anordnung zur Bestimmung der vorgegebenen Sortierfolge der Sätze aufweist, indem in der Sortierfolge der Schlüsselwerte entsprechend den Sätzen die verkoppelten Listen aus der besagten weiteren Speicheranordnung entsprechend dem Schlüsselfeld der nächst niedrigeren Bedeutungsfolge genommen werden und von jeder Liste in der Reihenfolge die entsprechenden Satzadressen ausgelesen werden, sowie zum Einschreiben der abgeleiteten Adressen in eine andere der weiteren Speicheranordnungen entsprechend der besagten Bedeutungsfolge als Zeiger, welche für jeden Schlüsselwert eine verkoppelte Liste von Satzadressen bestimmen, die über den Schlüsselwert miteinander verknüpft sind; und einer Anordnung zum Steuern des wiederholten Betriebs der Logikschaltung für aufsteigende Bedeutungsfolgen der Schlüsselfelder und zum Steuern der Vorzeichen der Reihenfolgen, in welchen die verkoppelten Listen und die darin befindlichen Sätze gelesen werden, so daß bei einem abschließenden Betrieb der Logikschaltung die Adressen der Sätze von einer entsprechenden weiteren Speicheranordnung in sortierter Reihenfolge ausgelesen werden können, um die Datensätze in sortierter Reihenfolge von der ersten Speicheranordnung entsprechend wiederherstellen zu können.

Eine erfindungsgemäße Vorrichtung kann unterschiedliche Formen annehmen. Bei einer besonders zweckmäßigen Ausführungsform werden die erste Speicheranordnung und die weiteren Speicheranordnungen durch eine Speichervorrichtung gebildet, welche Speicherbereiche aufweist, die gemeinsam adressierbar sind, jedoch unabhängig voneinander beschrieben und ausgelesen werden können. Die weiteren Speicheranordnungen können dann durch zwei Sätze von Speicherbereichen realisiert sein, die abwechselnd beschrieben und ausgelesen werden können, so daß den Schlüsselwerten eines Schlüsselfeldes einer niedrigeren Bedeutungsfolge entsprechende Adressen aus einem Speicherbereich gelesen werden können, während die Schlüsselwerten eines Schlüsselfeldes der nächsthöheren Bedeutungsfolge entsprechende Adressen in den zweiten Speicherbereich geschrieben werden.

Die Logikanordnung kann zwei weitere Speicheranordnungen zum Speichern von Daten, die die Adressen innerhalb jeder der weiteren Speicheranordnungen identifiziert, bei welchen entsprechende verknüpfte Listen beginnen, sowie eine programmierte Anordnung aufweisen, die vorgesehen ist, um zu bewirken, daß die Speicher in abwechselnden Vorgängen beschrieben und ausgelesen werden, um die Adressen von verknüpften Listen in einem Vorgang zu speichern und die vorgegebene Reihenfolge der Datensätze in dem nächsten Vorgang zu erzeugen.

Weitere bevorzugte Merkmale und Vorteile der erfindungsgemäßen Vorrichtung ergeben sich aus der folgenden Beschreibung in Verbindung mit den beigefügten Zeichnungen, bei welchen:

Fig. 1 ein Diagramm ist, welches die Struktur eines Beispiels eines mittels einer erfindungsgemäßen Vorrichtung zu sortierenden Datensatzes veranschaulicht,

Fig. 2 ein Blockschaltdiagramm einer Ausführungsform einer erfindungsgemäßen Vorrichtung darstellt,

Fig. 3 und 4 Diagramme sind, welche Betriebsschritte der Vorrichtung von Fig. 2 veranschaulichen, und

Fig. 5 ein Diagramm ist, welches den von der Vorrichtung von Fig. 2 ausgeführten Sortierprozeß veranschaulicht.

Unter Bezugnahme auf die Zeichnungen wird die Vorrichtung nun in Bezug auf Fig. 1 und 2 beschrieben. Fig. 1 veranschaulicht in Diagrammform die Struktur eines Eingabedatensatzes, der in der Realität eine immaterielle Anordnung von Informationen darstellt. Der Schlüsselabschnitt des Datensatzes ist eine Anzahl von Binärstellen, die in Felder von jeweils n Stellen gruppiert sind, in diesem Fall fünf Felder mit drei Stellen. Die erforderliche Datensatzreihenfolge ist diejenige, bei welcher aufeinanderfolgende Sätze ansteigende Werte des als Ganzes gesehenen Schlüsselfelds aufweisen. Dies kann dadurch erzielt werden, daß die Liste in der Reihenfolge des mit der höchsten Zahl versehenen Abschnitts, d.h. dem niederwertigsten Abschnitt, des Schlüssels sortiert wird, und dann in der Reihenfolge des mit der nächstniedrigeren Zahl versehenen Abschnitts sortiert wird usw., wobei die mittels der früheren Sortierdurchläufe erzeugte Reihenfolge beibehalten wird, bis die Liste vollständig sortiert ist.

Unter Bezugnahme auf Fig. 2 weist eine Vorrichtung zur Verwendung beim Sortieren der Datensätze von Fig. 1 einen Eingabedatenbus 1 auf, welcher mit einem Speicher 2 verbunden ist, der in Speicherbereiche mit einer gemeinsamen Adresse unterteilt ist, wie dies schematisch mittels der sich senkrecht erstreckenden gestrichelten Linien veranschaulicht ist. Bei jeder Adresse weist der Speicher 2 vier Speicherbereiche 2A, 2B, 2C, 2D auf, welche unabhängig voneinander beschrieben und ausgelesen werden können. Zum Zwecke der nachfolgenden Erklärung sei angenommen, daß der Bereich 2D Daten entsprechend dem Schlüsselteil eines jeden in Fig. 1 gezeigten Datensatzes erhalten soll, wohingegen der Speicherbereich 2C den Datenteil des Datensatzes erhalten soll. Obschon die beschriebene Ausführungsform sich auf einen Datensatz des Typs bezieht, bei welchem Daten enthalten sind, die nicht Teil des Schlüssels des Datensatzes sind, versteht es sich, daß das Prinzip der Erfindung auf einen Datensatz, der nur Schlüsselfelder enthält, anwendbar ist, wobei in diesem Fall die Speicherbereiche 2C und 2D zu einem einzigen Bereich kombiniert werden könnten. Die Speicherbereiche 2A und 2B werden zur Speicherung von Zeigern verwendet, die Adressen des Speichers 2 darstellen, wie dies nachstehend detaillierter beschrieben ist. Der Speicher 2 weist ferner einen Ausgabebus 5 auf, von welchem die Datensätze von den Speicherbereichen 2C und 2D ausgelesen werden können.

Der Eingang list ferner mit einem Pol eines Umschalters 8 verbunden, wobei der andere Pol mit einem Ausgang 7 von dem Speicherbereich 2D des Speichers 2 verbunden ist. Ein Ausgang des Schalters 8 ist mit einer Datenauswahlvorrichtung 14 verbunden, welche in bekannter Weise Daten selektiv von einem beliebigen der Schlüsselfelder des Datensatzes von Fig. 1 passieren lassen kann.

Ein Zähler 12 ist mit einem Eingang eines Wahlschalters 9 verbunden, dessen Ausgang mit einem Adreßbus 15 des Speichers 2 verbunden ist, wobei die an dem Bus 15 anliegende Adresse die Adresse bestimmt, zu bzw. von welcher Daten in allen Bereichen 2A bis 2D des Speichers gerichtet bzw. geholt werden sollen. Ein weiterer Eingang des Schalters 9 ist angeordnet, um Daten selektiv von einem der beiden Bereiche 2A und 2B des Speichers zu empfangen, wie dies nachstehend detaillierter erläutert ist. Der Ausgang des Schalters 9, der mit dem Adreßeingang 15 des Speichers 2 verbunden ist, ist ferner mit einem Eingang eines weiteren Wählschalters 16 verbunden, dessen Ausgänge selektiv mit einem von zwei weiteren Hochgeschwindigkeitsspeichern 3 verbunden werden können. Jeder Speicher 3 ist breit genug, um die Adresse einer Stelle in dem Hauptspeicher 2 zu halten und ist lang genug, um mittels der Daten, welche ein Feld des Schlüssels eines Datensatzes, wie er in Fig. 1 gezeigt ist, ausmachen, adressiert zu werden. Die Speicher 3 sind schnell genug, um einen Lese- und einen Schreibvorgang pro Zyklus des Systems auszuführen, d.h. sie haben die doppelte Geschwindigkeit des Hauptspeichers 2. Adreßeingänge eines jeden der Speicher 3 sind mit Ausgängen eines Wahlschalters 11 verbunden, dessen Eingänge mit einem Ausgang der Datenauswahlvorrichtung 14 und einem Eingang eines Zählers 13 verbunden sind. Steuereingänge eines jeden der Speicher 3 sind mit einer Logikanordnung 4 verbunden, die angeordnet ist, um den zeitlichen Ablauf der Lese- und Schreibvorgänge der Speicher 2 und 3 und die Betätigung aller in Fig. 2 veranschaulichten Schalter mittels Verbindungen zu steuern, die in der Zeichnung aus Klarheitsgründen weggelassen wurden. Datenausgänge der Speicher 3 sind jeweils einerseits mit einem Eingang des Schalters 9 und andererseits mit einem Eingang eines weiteren Umschalters 10 verbunden, dessen Ausgang mit einem Datenbus 6 verbunden ist, der selektiv mit einem der beiden Speicherbereiche 2A und 2B des Speichers 2 verbunden werden kann.

Die Funktionsweise der Vorrichtung von Fig. 2 wird nun detaillierter beschrieben, wobei es sich versteht, daß der Vorgang des Übertragens von Daten zwischen den betreffenden Einheiten der Vorrichtung in einer Serie von Zyklen stattfindet, die auf normale Weise mittels eines Taktoszillators erzeugt werden und den Betrieb der Logikanordnung 4 und der damit verbundenen Speicher und Schalter steuern.

Anfänglich wird der Wahlschalter 3 so eingestellt, daß der Eingang 1 mit der Datenauswahlvorrichtung 14 verbunden ist, der Wahlschalter 9 ist so eingestellt, daß der Ausgang des Zählers 12 mit dem Adreßbus 15 des Speichers 2 verbunden ist, und die Schalter 10, 11 und 16 sind so eingestellt, daß nur ein Speicher 3 verwendet wird, wobei der Adreßeingang über den Schalter 11 mit der Datenauswahlvorrichtung 14 verbunden ist, der Dateneingang über den Schalter 16 mit dem Adreßbus 15 verbunden ist und der Datenausgang über den Schalter 10 mit einem Eingang des Speicherbereichs 2A des Speichers 2 verbunden ist.

Es versteht sich, daß, obschon die Datenübertragungswege in Fig. 2 durch einzelne Linien veranschaulicht sind, die einzelnen Linien tatsächlich Datenbusse mit parallelen Leitern darstellen, wobei die Anzahl der Leiter in jedem Fall der Anzahl der Datenbits des entsprechenden zu übertragenden Signals entspricht.

Eingabedatensätze mit der in Fig. 1 veranschaulichten Struktur werden nacheinander auf dem Datenbus 1 synchron zu der Tätigkeit des Zählers 12 übertragen, so daß aufeinanderfolgende Datensätze in die Speicherbereiche 2C und 2D bei aufeinanderfolgenden Speicheradressen eingelesen werden. Zur gleichen Zeit gelangt der Schlüsselabsehnitt eines jeden Eingabedatensatzes über den Schalter 8 zu der Datenauswahlvorrichtung 14, welche das niederwertigste Schlüsselfeld auswählt und dieses zu dem Adreßeingang desjenigen der Hochgeschwindigkeitsspeicher 3 leitet, der tätig ist. Dieser Speicher enthält ursprünglich an jeder Stelle ein Bitmuster, welches keine gültige Adresse in dem Hauptspeicher darstellt. Wenn eine Stelle in dem Speicher 3 mittels dieses Eingangssignals adressiert wird, wird dieser Speicher von der Logikanordnung 4 mit aufeinanderfolgenden Lese- und Schreibsignalen versorgt, wodurch die Inhalte der adressierten Speicherstellen in den Speicherbereich 2A geschrieben werden, welcher mittels des Busses 15 adressiert wird, und dann wird die auf dem Bus 15 dargestellte Adresse über den Schalter 16 in den Speicher eingelesen. Somit wird bei jedem Zyklus des Speichers 2, während welchem Daten in die Speicherbereiche 2C, 2D und 2A geschrieben werden, der Hochgeschwindigkeitsspeicher 3 zwei aufeinanderfolgenden Arbeitszyklen unterworfen, in welchen Daten von und zu der gleichen Adresse des Speichers gelesen bzw. geschrieben werden.

Da der Speicher 3 von dem Wert des niederwertigsten Schlüsselfelds eines jeden Datensatzes adressiert wird und eine Gruppe von Datensätzen eine Anzahl von Datensätzen mit dem gleichen Wert für dieses Schlüsselfeld einschließt, wohingegen der Zähler 12 dafür sorgt, daß jede Adresse des Speichers 2 nur einmal angewählt wird, versteht es sich, daß bestimmte Adressen des Speichers 3 mehrmals angewählt werden können und jeweils die gespeicherte Adresse des vorhergehenden Datensatzes mit dem gleichen Schlüsseiwert bei einer neuen Adresse in den Speicherbereich 2A geschrieben wird, während die neue Adresse dann in die gleiche Adresse des Speichers 3 zurückgeschrieben wird.

Wenn man eine einzelne Stelle innerhalb des Hochgeschwindigkeitsspeichers 3 betrachtet, wird, falls keine Datensätze mit dem Wert des ersten Schlüsselfelds eingelesen wurden, welcher eine Adressierung dieser Stelle bewirken wurde, die Stelle in dem Hochgeschwindigkeitsspeicher das anfängliche Bitmuster enthalten, welches keine gültige Hauptspeicheradresse darstellt. Falls ein Datensatz eingelesen wurde, enthält die Stelle die Adresse des Datensatzes in dem Hauptspeicher und der Speicherbereich 2A bei dieser Adresse enthält das anfängliche Bitmuster. Jeder Speicherbereich 2A dient somit als Zeigerfeld, welches auf den vorhergehenden Datensatz mit dem gleichen Schlüsselwert zeigt, und falls zwei oder mehr Datensätze eingelesen wurden, enthält die Hochgeschwindigkeits-Speicherstelle die Adresse des letzten Datensatzes, das Zeigerfeld des letzten Datensatzes enthält die Adresse des vorletzten usw., bis der früheste Datensatz das anfängliche Bitmuster in seinem Zeigerfeld enthält. Diese Struktur, die als verknüpfte Liste bekannt ist, ist in der Datenverarbeitungstechnik bekannt und sie ist sehr detailliert in "Fundamental Algorithms" von Donald Knuth beschrieben.

Die oben beschriebenen Schritte sind in Fig. 3 schematisch dargestellt, die die Stellung am Ende des ersten Durchlaufs zeigt. Die Liste 3 enthält die Datensätze 4, 2 und 1, die Liste 4 enthält den Datensatz 3 und die Liste 7 enthält die Datensätze 5 und 0.

Wenn der Zähler 12 alle Adressen des Speichers 2 in einem ersten Durchlauf erzeugt hat, wobei angenommen wird, daß die Gesamtzahl von an dem Eingang 1 angelegten Datensätzen der Anzahl der Adressen in dem Speicher entspricht, oder wenn die Steuerlogik 4 ein Daten- Endesignal am Eingang 1 erfaßt, bewirkt die Steuerlogik 4 nun, daß der Schalter 8 den Eingang der Datenauswahlvorrichtung 14 mit dem Ausgang 7 des Abschnitts 2D des Speichers 2 verbindet, während der Schalter 9 den Adreßeingang 15 des Speichers 2 mit dem Ausgang desjenigen Speichers 3 verknüpft, welcher während des ersten Durchlaufs tätig war. Der Eingang 1 des Speichers 2 ist nun nicht tätig, so daß die Inhalte der Abschnitte 2C und 2D des Speichers unverändert bleiben. Der Schalter 11 wird betätigt, um die Adreßeingänge des obigen Speichers 3 mit dem Ausgang des Zählers 13 zu verbinden, während der Adreßeingang des anderen Speichers 3 mit dem Ausgang der Datenauswahlvorrichtung 14 verbunden wird. Die Schalter 16 und 10 werden betätigt, um den Dateneingang des anderen Speichers mit dem Adreßbus 15 und den Datenausgang des anderen Speichers mittels dem Adreßbus 6 mit dem Speicherbereich 2B des Speichers 2 zu verbinden. Die Datenauswahivorrichtung 14 wird eingestellt, um das nächste Schlüsselfeld der dem Speicherbereich 2D entnommenen Schlüsseldaten auszuwählen. Die Schlüsselfelder sind von 1 (höchste Bedeutung) bis n (niedrigste Bedeutung) numeriert. Falls die Nummer des ausgewählten Schlüsselfelds ungerade ist, wird der Zähler 13 so eingestellt, daß er von Null auf eine Zahl hochzählt, welche die letzte Adresse des Iiochgeschwindigkeitsspeichers 3 darstellt, falls die Nummer des Schlüsselfelds gerade ist, dann wird der Zähler so eingestellt, daß er von dem Maximalwert auf Null herunterzählt.

Für jeden von dem Zähler 13 erzeugten Wert wird die entsprechende Stelle in dem ausgewählten Hochgeschwindigkeitsspeicher gelesen. Die entsprechenden aus dem Hochgeschwindigkeitsspeicher gelesenen Daten werden mittels eines geeigneten Logikelements der Logikanordnung 4 (nicht gezeigt) überprüft, um sicherzustellen, ob der aus dem Speicher gelesene Wert eine gültige Adresse des Speichers 2 darstellt, wobei in diesem Fall der gelesene Wert über den Schalter 9 zu dem Adreßbus 15 gelangen kann, wo er verwendet wird, um von der entsprechenden Adresse von Speicherbereich 2D die Schlüsseldaten zu lesen, welche von dem Ausgang 7 zu der Datenauswahlvorrichtung 14 gelangen, sowie die Adresse innerhalb des Speicherbereichs 2A zu lesen, welche auf den entsprechenden Eingang des Schalters 9 gegeben wird.

Die Datenauswahlvorrichtung 14 läßt die Daten des gegenwärtig ausgewählten Schlüsselfelds zu dem relevanten Hochgeschwindigkeitsspeicher 3 gelangen und die Daten werden von diesem Speicher auf die gleiche Weise wie bei dem vorhergehenden Vorgang ausgelesen und in diesen eingeschrieben, d.h. der aus dem Speicher gelesene Wert wird verwendet, um den Adreßzeiger auf den von dem Datenbus 15 adressierten Speicherbereich 28 des Speichers 2 zu liefern, und die Adresse auf dem Datenbus 15 wird in den Hochgeschwindigkeitsspeicher 3 zurückgelesen.

Die an dem Ausgang des Speicherbereichs 2A des Speichers 2 dargestellten Daten werden nun mittels der Logikvorrichtung 4 durch eine nicht gezeigte Anordnung überprüft, um sicherzustellen, daß die Daten eine gültige Adresse des Speichers 2 darstellen, wobei in diesem Fall die Logikvorrichtung 4 ein Anhalten der Inkrementierung des Speichers 13 und eine Betätigung des Umschalters 9 bewirkt, um den Adreßbus 15 mit dem Ausgang des Speicherbereichs 2A des Speichers 2 zu verbinden. Die von dem Speicherbereich 2A angelieferte entsprechende Adresse bestimmt nun die nächste Adresse des Speichers 2, aus welcher Daten gelesen werden sollen. Der vorhergehende Vorgang wird wiederholt, bis als Ausgabe von dem Speicherbereich 2A das ursprüngliche Bitmuster erfaßt wird, worauf die Inkrementierung des Zählers 13 neu gestartet und der Schalter 9 rückgesetzt wird, um die nächste Adresse von dem Datenausgang des Speichers 3, der von dem Zähler 13 adressiert wird, abzugreifen.

Falls während des obigen Vorgangs die Datenausgabe von dem von dem Zähler 13 adressierten Speicher 3 keine gültige Adresse des Hauptspeichers 2 darstellt, werden die Vorgänge des Lesens von dem Speicher 2 und Schreibens in den Speicher 2 ausgelassen, und der Zähler 13 wird inkrementiert, bis wieder eine gültige Adresse erzeugt wird.

Die Funktionsweise der Vorrichtung in diesem Stadium versteht sich deutlicher unter Bezugnahme auf Fig. 3 und 4. Der von dem Zähler 13 adressierte Speicher 3 entspricht dem Speicher 3 von Fig. 3, und wenn der Zähler 13 inkrementiert wird, werden ursprüngliche Bitmuster von dem Speicher 3 ausgegeben, wenn der Zähler 13 die ersten drei Adressen in dem Speicher anwählt. Die erste gültige am Adreßbus 15 angelegte Adresse ist demgemäß die Adresse des Datensatzes 4 des Speichers 2, welcher bei der Adresse 3 des Speichers 3 enthalten ist. Der Speicherbereich 2A der Adresse 4 des Speichers 2 enthält die Adresse des Datensatzes 2 usw., so daß die in Fig. 3 gezeigten Datensätze in einer Vorwärtsreihenfolge gelesen und in der Reihenfolge 4, 2, 1, 3, 5, 0 abgegriffen werden.

Fig. 4 zeigt die entsprechende Situation am Ende des zweiten Durchlaufs für den Speicher 3, dessen Adreßbus mit dem Ausgang der Datenauswahlvorrichtung 14 verbunden war. Somit enthält in diesem Fall die Liste 2 die Datensätze 0, 5, 2 und 4, und die Liste 5 enthält die Datensätze 3 und 1. Falls dies nun in umgekehrter Reihenfolge gelesen wird, werden die Datensätze in der Reihenfolge 3, 1, 0, 5, 2, 4 abgegriffen. Es versteht sich, daß jeder Speicher 3 rückgesetzt werden muß, um das originale Bitmuster an allen Adressen aufzuweisen, bevor er verbunden wird, um die Daten von der Datenauswahlvorrichtung 14 zu empfangen, und dies wird mittels eines geeigneten, von der Logikvorrichtung 4 festgesetzten Programmschritts erzielt.

Mittels dieses Verfahrens kann auf die Hauptspeicherstellen entweder in normaler oder umgekehrter Reihenfolge des Felds zugegriffen werden, welches mittels der Datenauswahlvorrichtung 14 bei dem vorhergehenden Durchlauf ausgewählt wurde. Innerhalb eines bestimmten Werts eines Schlüsselfelds erscheinen die Daten in einer Reihenfolge, die zu der Reihenfolge, in welcher die Daten in dem vorhergehenden Durchlauf erschienen, umgekehrt ist. Es ist deshalb nötig, wie es oben beschrieben wurde, bei Feldern mit gerader Nummer in umgekehrte Reihenfolge zu sortieren und bei Feldern mit ungerader Nummer in normaler Reihenfolge zu sortieren, was die Zahl an Umkehrungen der Liste widerspiegelt, die noch folgen werden.

Der Vorgang wird nun so oft wie nötig wiederholt, bis die Datensätze unter Verwendung aller Schlüsselfelder sortiert sind. Der gleiche Vorgang des Zugreifens auf Datensätze in einer Reihenfolge wird nun auf die endgültige Liste angewandt, und die Daten und die Schlüsselfelder werden von der Vorrichtung bei 5 ausgegeben.

Das Verfahren kann anhand einer in Fig. 5 dargestellten manuellen Analogie veranschaulicht werden. Dabei sind zwei Tische A und B gezeigt, auf welchen die Datensätze in numerierten Stapeln, wie sie auf Tisch B gezeigt sind, gesammelt werden können, die mittels Kartenstapeln veranschaulicht sind und Datensätze darstellen.

Um den Vorgang manuell auszuführen, wird angenommen, daß die unsortierten Karten, welche Datensätze darstellen, ursprünglich von einem oder mehreren ungeordneten Stapeln von Tisch A genommen werden. Jede Karte wird inspiziert und in den Stapel gelegt, der mittels der drei Binärstellen in Feld 5 des Schlüssels angezeigt ist. Wenn alle Karten auf dem Tisch B plaziert wurden, nimmt der Spieler alle Karten vom Stapel 0 in Reihenfolge, dann alle Karten vom Stapel 1 usw., bis das Ende des Stapels 7 erreicht ist. Die so aufgenommenen Karten werden auf den Tisch A in dem Stapel plaziert, der durch die Stellen in Feld 4 des Schlüssels angezeigt ist. Die Situation am Ende dieses Vorgangs ist dergestalt, daß alle Karten auf Tisch A in Stapeln angeordnet sind, welche mittels des Werts in dem Feld 4 ausgewählt sind, und innerhalb jedes Stapels befinden sich die Karten in umgekehrter Reihenfolge bezüglich des Werts in Feld 5, d.h. der größte Wert befindet sich oben auf dem Stapel und der kleinste Wert befindet sich auf dem Tisch. Der Spieler bewegt nun die Karten vom Tisch A zum Tisch B, wobei er sie vom Stapel 7 aufnimmt, bis dieser erschöpft ist, dann vom Stapel 6 usw., bis der Stapel 0 erschöpft ist. Jede Karte wird inspiziert und in den Stapel plaziert, der durch das Feld 3 des Schlüssels angezeigt ist. Der Vorgang wird fortgesetzt, indem abwechselnd die Karten vom Tisch A zu dem Tisch B und zurück bewegt werden, wobei jedes Mal ein mit einer kleineren Zahl numeriertes Feld des Schlüssels verwendet wird. Wenn ein ungeradzahlig bezeichnetes Feld inspiziert wird, werden die Karten von A nach B bewegt, die Karten werden in absteigender Reihenfolge der Stapelnummer von A genommen und die Karten gelangen in absteigender Reihenfolge des Werts in den bereits verwendeten Feldern durch die Hände des Spielers. Wenn ein geradzahlig bezeichnetes Feld inspiziert wird, dann werden die Karten von B nach A bewegt, die Karten werden in aufsteigender Reihenfolge der Stapelnummer von B genommen und die Karten gelangen in aufsteigender Reihenfolge der bereits verwendeten Felder durch die Hände des Spielers.

Am Ende des Verfahrens liegen alle Karten auf dem Tisch B. Wenn man den gesamten Stapel 0, dann den Stapel 1 usw. bis zu Stapel 7 aufnimmt, befinden sich die Karten in der richtigen Reihenfolge. Das Verfahren funktioniert für jede Anzahl von Feldern, jede Anzahl von Karten sowie in Fällen, in welchen die Schlüsselfelder von verschiedener Größe sind.

Die zum Sortieren der Daten in die richtige Reihenfolge erforderliche Zeit kann nicht F × (N + K - 1)-Zyklen übersteigen, und sie kann nicht kleiner als F × N Zyklen sein, wenn der Schlüssel F Felder und die Liste N Posten enthält und jeder Hochgeschwindigkeitsspeicher K Stellen aufweist.

Die Kosten des Hochgeschwindigkeitsspeichers steigen mit der Stellenanzahl in einem Schlüsselfeld, jedoch nimmt die zum Sortieren erforderliche Zeit mit der Anzahl der Felder ab, und bei praktischen Anwendungen bestehen die Schlüsselfelder typischerweise aus zwischen 10 und 20 Binärstellen.

Wie anfangs erwähnt wurde, ist die oben beschriebene Sortiervorrichtung besonders vorteilhaft, wenn sie als Teil einer Vorrichtung für digitale Videoeffekte zum Umwandeln von Videobildern verwendet wird, obwohl sie allgemein verwendet werden kann. Solch eine Vorrichtung für Videoeffekte kann eine Anordnung zum Erzeugen einer Serie von Datensätzen, die jeweils ein die Attribute eines Piksels des Videobilds definierendes Datenfeld und ein die Position des Piksels in einem Halbbild definierendes Schlüsselfeld aufweisen, eine Anordnung zum Umwandeln der Werte der Schlüsselfelder der Datensätze zum Festlegen einer Ausgangsabbildung der Verlagerung von Pikseln von dem Eingangs- zu dem Ausgangsbild, sowie eine Sortiervorrichtung der oben beschriebenen Art zum Sortieren der umgewandelten Datensätze in der Reihenfolge der Schlüsselfelder aufweist, um die Erzeugung des umgewandelten Videohalbbildsignals mittels des Abtastens der Datensätze in der sortierten Reihenfolge zu ermöglichen.


Anspruch[de]

1.Vorrichtung zum Sortieren einer Liste von Datensätzen in einer Reihenfolge, die durch die entsprechenden Werte eines jeden Satzes einer Reihe von Schlüsselfeldern bestimmt ist, die in einer aufsteigenden Bedeutungsfolge sortiert sind, gekennzeichnet durch eine erste Speicheranordnung (2C, 2D), die über eine Anzahl von Adressen, welche mindestens gleich der Maximalzahl der zu sortierenden Sätze ist, und für jede Adresse über einen Speicherbereich verfügt, der die Daten eines Satzes aufnehmen kann; eine Mehrzahl weiterer Speicheranordnungen (2A, 2B), die jeweils über den Adressen der ersten Speicheranordnung (2C, 2D) entsprechende Adressen und für jede Adresse über einen Speicherbereich verfügen, der eine Adresse der ersten Speicheranordnung speichern kann, wobei die erste Speicheranordnung (2C, 2D) und die weiteren Speicheranordnungen (2A, 2B) unabhängig voneinander beschrieben und ausgelesen werden können; eine Anordnung (1, 12, 15) zum Einschreiben einer Reihe von zu sortierenden Datensätzen in die erste Speicheranordnung; eine Logikschaltung (3, 4) um die Werte von Schlüsselfeldern, welche die gleiche Bedeutungsfolge haben, in einer vorgegebenen Sätze-Sortierfolge zusammen mit den Adressen in der ersten Speicheranordnung (2C, 2D), an welchen die entsprechenden Sätze gespeichert sind, abzuleiten und um die abgeleiteten Adressen entsprechend der Bedeutungsfolge in eine der weiteren Speicheranordnungen (2A, 2B) als Zeiger einzuschreiben, welche für jeden Schlüsselwert eine verkoppelte Liste von Adressen von Sätzen bestimmen, die über den Schlüsselwert miteinander verknüpft sind, wobei die Logikschaltung (3, 4) für jede Bedeutungsfolge des Schlüsselfeldes, für das Werte abgeleitet werden, mit Ausnahme der niedrigsten Bedeutungsfolge, eine Anordnung zur Bestimmung der vorgegebenen Sortierfolge der Sätze aufweist, indem in der Sortierfolge der Schlüsselwerte entsprechend den Sätzen die verkoppelten Listen aus der besagten weiteren Speicheranordnung (2A, 2B) entsprechend dem Schlüsselfeld der nächst niedrigeren Bedeutungsfolge genommen werden und von jeder Liste in der Reihenfolge die entsprechenden Satzadressen ausgelesen werden, sowie zum Einschreiben der abgeleiteten Adressen in eine andere der weiteren Speicheranordnungen entsprechend der besagten Bedeutungsfolge als Zeiger, welche für jeden Schlüsselwert eine verkoppelte Liste von Satzadressen bestimmen, die über den Schlüsselwert miteinander verknüpft sind; und einer Anordnung (4) zum Steuern des wiederholten Betriebs der Logikschaltung (3, 4) für aufsteigende Bedeutungsfolgen der Schlüsselfelder und zum Steuern der Vorzeichen der Reihenfolgen, in welchen die verkoppelten Listen und die darin befindlichen Sätze gelesen werden, so daß bei einem abschließenden Betrieb der Logikschaltung (3, 4) die Adressen der Sätze von einer entsprechenden weiteren Speicheranordnung (3, 4) in sortierter Reihenfolge ausgelesen werden können, um die Datensätze in sortierter Reihenfolge von der ersten Speicheranordnung (2C, 2D) entsprechend wiederherstellen zu können.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die erste Speicheranordnung und die weiteren Speicheranordnungen von einem einzelnen Speichergerät (2) bereitgestellt werden, weiches über Speicherbereiche (2A, 2B, 2C, 2D) verfügt, die gemeinsam adressiert werden können, in die bzw. aus denen jedoch unabhängig voneinander eingeschrieben und ausgelesen werden kann.

3. Vorrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die weitere Speicheranordnung zwei Speicheranordnungen (2A, 2B) aufweist und daß die Logikschaltung eine Anordnung (8, 9, 12, 13) zum Auslesen der Schlüsselfelder der in der ersten Speicheranordnung (2C, 2D) enthaltenen Datensätze in der vorgegebenen Reihenfolge aufweist, sowie daß zwei zusätzliche Speicheranordnungen (3), eine Anordnung (14) zum Auswählen einer Ziffer einer gegebenen Bedeutung von jedem der Schlüsselfelder und zum Auswählen einer Adresse einer der zusätzlichen Speicheranordnungen (3), die von dem Wert dieser Ziffer bestimmt wird, eine Anordnung (10) zuni Einschreiben von Daten von der gewählten Adresse der besagten zusätzlichen Speicheranordnungen (3) in einer der weiteren Speicheranordnungen (2A, 2B) an die Adresse in der ersten Speicheranordnung (2C, 2D) des gelesenen Satzes und eine Anordnung (16) zum Speichern der letztgenannten Adresse an die gewählte Adresse der zusätzlichen Speicheranordnung (3) vorgesehen sind, wobei die Anordnung so getroffen ist, daß alternierende der beiden weiteren Speicheranordnungen (2A, 2B) und der beiden zusätzlichen Speicheranordnungen (3) in aufeinanderfolgenden Schritten beschrieben werden, wobei Ziffern der Schlüsselfelder mit aufsteigender Bedeutungsfolge entsprechend ausgewählt werden.

4. Vorrichtung nach Anspruch 3, dadurch gekennzeichnet, daß ein erster Zähler (12) so angeordnet ist, daß er die erste Speicheranordnung (2C, 2D) in einem ersten Schritt zum Auslesen der Schlüsselfelder der Datensätze, die in der ersten Speicheranordnung (2C, 2D) enthalten sind, in der vorgegebenen Reihenfolge adressiert, und daß die Anordnung zum Lesen in der vorgegebenen Reihenfolge einen weiteren Zähler (13) zum Adressieren einer entsprechenden der zusätzlichen Speicheranordnungen (3) in nachfolgenden Schritten aufweist, um Adressen der ersten Speicheranordnung (2C, 2D) von der zusätzlichen Speicheranordnung (3) und von verkoppelten Adressenlisten abzuleiten, die in einer entsprechenden der weiteren Speicheranordnungen (2A, 2B) gehalten werden, an welche die zusätzliche Speicheranordnung Zeiger liefert.

5. Vorrichtung nach Anspruch 4, dadurch gekennzeichnet, daß die Anordnung zum Lesen in vorgegebener Reihenfolge ferner einen Wählschalter (9) aufweist, der dafür angeordnet ist, unter der Steuerung der Logikschaltung (4) eine Adresseneingabe von der ersten Speicheranordnung (2C, 2D) und der weiteren Speicheranordnungen (2A, 28) selektiv an den ersten Zähler (12), einen Ausgang von einer der zusätzlichen Speicheranordnungen (3) oder an einen Ausgang von einer der weiteren Speicheranordnungen (2A, 2B) anzukoppeln.

6. Vorrichtung nach Anspruch 5, dadurch gekennzeichnet, daß die Logikschaltung (4) eine Anordnung zum Prüfen von Daten, die aus der zusätzlichen Speicheranordnung (3) und aus den weiteren Speicheranordnungen (2A, 2B) ausgelesen werden, sowie zum Steuern der Inkrementierung des weiteren Zählers (13) und zur Betätigung des Wählschalters (9) in Abhängigkeit davon, ob die gelesenen Daten einer gültigen Adresse der ersten Speicheranordnung (2C, 2D) entsprechen, aufweist.

7. Vorrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß sie in eine Vorrichtung zum Erzeugen digitaler Videoeffekte integriert und so angeordnet ist, daß sie Sätze sortiert, die jeweils ein Schlüsselfeld aufweisen, welches die Position in einem Videohalbbild eines Piksels definiert, dessen Attribute in einem Datenfeld des gleichen Satzes festgelegt sind.

8. Vorrichtung nach Anspruch 7, dadurch gekennzeichnet, daß die Vorrichtung zum Erzeugen digitaler Videoeffekte eine Überlagerungsanordnung zum Überlagern von Schlüsselwerten einer Gruppe von Sätzen, die ein Halbbild bestimmen, gemäß den Ausgabeabbildungsfunktionen der Verlagerung von Pikseln von dem Eingabe- zu dem Ausgabebild sowie zum Bereitstellen entsprechend überlagerter Sätze zwecks Sortierung und eine Abtastanordnung zum Abtasten der sortierten Sätze aufweist, uni ein Videosignal zur Reproduktion des überlagerten Bildes zu erzeugen.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com