DE69327421T2 - Anordnung und Verfahren zum parallelisierten Grössenvergleich von digitalen Daten - Google Patents

Description

• Die vorliegende Erfindung betrifft allgemein integrierte Schaltungen, und speziell eine Wertkomparatorschaltung.
• Diese Anmeldung ist bezogen auf die europäische Patentanmeldung, die unter der Nr. EP-A-0 564 137 veröffentlicht wurde. Diese Anmeldung ist auch auf die europäische Patentanmeldung bezogen, die unter der Nr. EP-A-0 568 373 veröffentlicht wurde, und gleichzeitig mit dieser Anmeldung eingereicht wurde.
• Wertkomparatorschaltungen werden verwendet, wenn es notwendig ist, die Beziehung zwischen den Werten zweier Zahlen zu bestimmen - ob eins Zahl hinsichtlich des Wertes gleich, kleiner als, oder größer als eine andere Zahl ist. Derartige Schaltungen finden in der Elektronikindustrie eine große Vielfalt von Anwendungen. Beispielsweise werden Wertkomparatoren zusammen mit Subtrahierern verwendet, um für FIFO (First In First Out bzw. Durchlauf-) Speicher eine Hochgeschwindigkeitsflaglogik bereitzustellen. Wertkomparatorschaltungen werden auch in Rechenwerken (ALUs bzw. Arithmetic Logic Units) verwendet, die in Personalcomputern (PCs) und in anderen Computern zu finden sind, und von Mikroprozessoren, zur Ausführung bestimmter Befehle.
• Im Stand der Technik sind serielle Wertkomparatoren eine übliche Ausgestaltung für Komparatorschaltungen. Sie weisen eine Anzahl einzelner Bitkomparatoren auf, die zusammen auf serielle Weise den Wert einer Zahl in Bezug auf eine andere Zahl bestimmen. Als erstes werden die Bits niedrigster Wertigkeit (LSBs bzw. Least Significant Bits) der zwei Zahlen verglichen, bevor die nächsten Bits, die LSB+1, verglichen werden. Dieser Vorgang wird auf serielle Weise fortgesetzt, bis die Bits höchster Wertigkeit (MSBs bzw. Most Significant Bits) verglichen wurden. Der serielle Vorgang kann ziemlich aufwendig sein; beim Vergleich zweier 16-Bit Wörter fallen mindestens 16 Gatterverzögerungen an.
• Die einzelnen Bitkomparatoren, die einen seriellen Wertkomparator bilden, haben vier Eingaben: zwei Eingaben, die von den zwei Bits bestimmt werden, die verglichen werden sollen, eine Eingabe von der Vergleichsausgabe des vorhergehenden Wertkomparators, und eine Eingabe, die gleich dem ersten Bit der zwei Bits ist, die verglichen werden sollen. Die Vergleichsausgabe eines Bitkomparators wird dem darauffolgenden Bitkomparator eingegeben, und spiegelt wieder, ob der Wert eines Bits gleich, kleiner als, oder größer als der Wert des anderen Bits ist. Wenn die zwei verglichenen Bits gleich sind, wird die Vergleichseingabe als die Vergleichsausgabe durch den Bitkomparator durchgegeben. Wenn jedoch die zwei Bits hinsichtlich des Werts ungleich sind, wird die Eingabe, die gleich dem ersten Bit der zwei Bits, die verglichen werden als die Vergleichsausgabe durchgegeben. Dieser Vergleichsvorgang beginnt mit dem Komparator für das Bit niedrigster Wertigkeit (LSB), und wird fortgesetzt, bis der Komparator für das Bit höchster Wertigkeit (MSB) seinen Vergleichsbetrieb beendet. Der Bitkomparator mit unterschiedlichen Bits der höchsten Ordnung bestimmt den Zustand der Vergleichsendausgabe.
• Die mit den seriellen Wertkomparatoren einhergehenden Gatterverzögerungen können einen ungünstigen Effekt auf die Gesamtsystemleistung haben. Bei FIFO (First In First Out) Speicheranwendungen wird ein Wertkomparator oft zusammen mit einer Subtrahierschaltung verwendet, um eine FIFO Flaglogik bereitzustellen. Ein FIFO Flag zeigt dem Anwender an, wie voll der FIFO ist. Flaglogikoperationen, die von dem Komparator und dem Subtrahierer abhängen, müssen schnell ausgeführt werden. Wenn der Wertkomparator langsam ist, hat er eine ungünstige Wirkung darauf, wie schnell Flaglogikoperationen durchgeführt werden können, und die Gesamtleistung des FIFO leidet. Ein grundsätzlicher Weg, die Geschwindigkeit zu erhöhen, mit der FIFO Logikoperationen durchgeführt werden, ist es, die mit den seriellen Wertkomparatoren einhergehenden Laufzeit- und Gatterverzögerungen zu minimieren. Es wäre wünschenswert, dies unter Verwendung aktueller Wertkomparatorkonstruktionen zu erreichen.
• Ein zur Verwendung bei einem FIFO Speicher geeigneter Wertkomparator wird modifiziert, um die Werte zweier Größen schneller zu vergleichen. Die Bitkomparatoren werden in zwei Gruppen unterteilt, die parallel zueinander Vergleichsausgabesignale erzeugen, dabei die Wertkomparatorgesamtverzögerung verringern, und so zu einem schnelleren Betrieb führen. Diese Vergleichsausgabesignale werden einem Steuerelement zugeführt, welches bestimmt, welchem Ausgabesignal ein Durchgang als Vergleichsendausgabesignal ermöglicht wird.
• Die Entgegenhaltung FR-A-1603654 des Standes der Technik offenbart einen Wertkomparator, der mehrere Bitkomparatoren aufweist, die in Komparatorgruppen unterteilt sind, die ein Gruppenausgabesignal erzeugen. Jeder Komparator vergleicht den Wert eines ersten Bits und eines zweiten Bits, und ein Steuerschaltkreis hat Eingänge, die mit den Ausgängen der Komparatorgruppen verbunden sind, um eine Komparatorausgabe zu liefern. Bei dieser Entgegenhaltung sind die Komparatoren als Addierer ausgebildet, die eine Übertragsausgabe aufweisen. Von jeder Gruppe wird eine Übertragsausgabe geliefert. Es wird eine weitere Gruppenausgabe geliefert, indem die Ausgänge der Addierer zusammengeschaltet werden. Ein Logikschaltkreis stellt eine Einzelausgabe von dem Komparator bereit.
• Gemäß einem ersten Aspekt der vorliegenden Erfindung wird ein Wertkomparator zur Verfügung gestellt, mit:
• Mehreren Bitkomparatoren (52-58), die in Komparatorgruppen (50-80) unterteilt sind, die ein Gruppenausgabesignal (59, 69, 79, 8a) erzeugen, wobei jeder Komparator den Wert eines ersten Bits und eines zweiten Bits vergleicht; und
• einem Steuerschaltkreis (90) mit Eingängen, die mit den Ausgängen der Komparatorgruppen verbunden sind, zum Liefern einer Komparatorausgabe (100), dadurch gekennzeichnet, daß der Steuerschaltkreis Logikeingaben hat, die durch Boolesche Operationen an den von den Bitkomparatoren zu vergleichenden Bits bestimmt werden, um den Steuerschaltkreis so zu betreiben, daß eines der Gruppenausgabesignale als die Komparatorausgabe gewählt wird, wobei die Komparatorgruppen und der Steuerschaltkreis ihre jeweiligen Funktionen gleichzeitig ausführen.
• Gemäß einem zweiten Aspekt der vorliegenden Erfindung wird ein Verfahren zum Vergleichen des Werts einer ersten Werteingabe und einer zweiten Werteingabe zur Verfügung gestellt, mit den Schritten:
• Vergleichen des Werts einer ersten Werteingabe und einer zweiten Werteingabe, indem Bitkomparatoren zu Komparatorgruppen gruppiert werden, die Gruppenvergleichsausgaben erzeugen, die einer Steuerschaltung zugeführt werden; und
• Bereitstellen eines Vergleichsausgabe-Endsignals von der Steuerschaltung, dadurch gekennzeichnet, daß an der ersten und der zweiten Werteingabe Boolesche Logikoperationen durchgeführt werden, wobei das Vergleichsausgabe- Endsignal aus einer der Gruppenvergleichsausgaben ausgewählt wird, und wobei der Vergleichsschritt und der Bereitstellschritt gleichzeitig ausgeführt werden.
• Die neuen Merkmale, die als für die Erfindung charakteristisch angesehen werden, sind in den beigefügten Ansprüchen definiert. Die Erfindung selbst jedoch, sowie eine bevorzugte Verwendungsweise, und ihre weiteren Ziele und Vorteile werden am besten verstanden, indem auf die fol gende detaillierte Beschreibung eines veranschaulichenden Ausführungsbeispieles Bezug genommen wird, wenn sie zusammen mit der begleitenden Zeichnung gelesen wird, bei welcher:
• Fig. 1 ein Blockdiagramm einer FIFO Flagerzeugungsschaltung gemäß dem Stand der Technik ist;
• Fig. 2 ein schematisches Diagramm eines seriellen Wertkomparators ist, der im Stand der Technik verwendet wird;
• Fig. 3 ein schematisches Diagramm eines parallelen Wertkomparators gemäß der vorliegenden Erfindung ist;
• Fig. 4 ein schematisches Diagramm eines Dreizustandsgatters gemäß der vorliegenden Erfindung ist.
• Ein FIFO ist ein Durchlaufspeicher, der typischerweise bei Anwendungen zwischen Maschinen verwendet wird, die Daten mit verschiedenen Geschwindigkeitsraten verwenden: beispielsweise zwischen einem Computer und einem Drucker. Der FIFO Speicher gibt unter Verwendung eines Flags seinen Status aus. Bei FIFO Speicherschaltungen werden häufig Komparatoren zusammen mit Subtrahierern verwendet, um FIFO Flags zu erzeugen. Die Flagausgaben zeigen beispielsweise an, daß der FIFO voll, halb voll, oder leer ist. Um den Status des FIFOs zu bestimmen, ist es notwendig, zu verfolgen, wieviele Bits in das FIFO geschrieben wurden, und wieviele Bits aus dem FIFO gelesen wurden. Auch ist es notwendig, die Beziehung zwischen den Werten von zwei Zahlen, und ob der Wert einer Zahl gleich, kleiner als oder größer als der Wert der anderen Zahl ist, zu wissen. Das Vergleichen des Werts dieser Zahlen wird erreicht, indem eine Wertkomparatorschaltung im FIFO verwendet wird.
• Bezogen auf Fig. 1 ist ein Blockdiagramm einer FIFO Flagerzeugungsschaltung gemäß dem Stand der Technik gezeigt. Die FIFO Flag weist einen Zählerblock 10, einen Subtrahierblock 12, einen Komparatorblock 14, und einen Entstörblock 16 auf. Ein Schreibtakt 18, ein Lesetakt 20, ein Schreibrücksetztakt 22 und ein Leserücksetztakt 24 stellen Eingabesignale sowohl zu dem Zählerblock 10 als auch zu dem Entstörblock 16 dar. Der Zählerblock 10 empfängt diese Eingabesignale, und erzeugt einen Schreibzählstand 26 und einen Lesezählstand 28, die dem Subtrahierblock 12 eingegeben werden, der wiederum ein Differenzsignal 30 ausgibt. Dieses Differenzsignal 30 und ein Programmwert 32 werden in den Komparatorblock 14 eingegeben, der sie vergleicht, um ein Ausgabevergleichssignal 34 zu erzeugen. Wie im Stand der Technik bekannt ist, wird der Programmwert 32 auf verschiedene Werte festgesetzt, in Abhängigkeit von der Art eines zu erzeugenden Flagsignals 36, wie z. B. leer, halb voll oder voll. Schließlich werden das Vergleichssignal 34 sowie der Schreibtakt 18, der Lesetakt 20, der Schreibrücksetztakt 22, und der Leserücksetztakt 24 in den Entstörblock 16 eingegeben, der das Flagausgabesignal 36 erzeugt.
• Fig. 2 zeigt ein schematisches Diagramm eines seriellen Wertkomparators 20, der im Stand der Technik verwendet wird. Der Wertkomparator 20 hat die Aufgabe, die Beziehung zwischen den Werten zweier Zahlen zu bestimmen. Der Wertkomparator 20 weist mehrere Bitkomparatoren 22, 24, 26 und 28 auf, die den Relativwertstand der zwei verglichenen Zahlen bestimmen. Die Anzahl der benötigten Bitkomparatoren ist eine Funktion der Anzahl von Bits in den zwei Zahlen, die verglichen werden. Jeder Bitkomparator vergleicht ein Bit von beiden Zahlen bei einer bestimmten Bitstelle. Beispielsweise wird der Wertstand des ersten zu vergleichenden Bits 40 mit demjenigen des zweiten Bits 42 verglichen, um zu bestimmen, ob es gleich, kleiner als, oder größer als das zweite Bit 42 ist. Jeder Bitkomparator hat vier Eingaben. Die zwei zu vergleichenden Bits 40 und 42 werden in ein exklusives ODER Gatter 44 eingegeben, dessen Ausgabe eine Eingabe 36 zu den Bitkomparatoren 22, 24, 26 und 28 darstellt; das Signal 36 wird invertiert, um eine Eingabe 38 zu liefern. Die Eingabe 38, die einfach das Inverse der Eingabe 36 ist, könnte auf einfache Weise intern im Bitkomparator erzeugt wer den; in diesem Fall würde es kein Eingabesignal darstellen. Weitere Eingaben zu den Bitkomparatoren sind die Ausgabe des vorhergehenden Bitkomparators 30, und eine Eingabe 34, das erste Bit der zwei Bits, die verglichen werden. Die Eingabe 34 ist von dem in Fig. 1 gezeigten Programmwert 32 verschieden. Fig. 2 zeigt zwei Binärzahlen, die verglichen werden, wohingegen Fig. 1 eine Binärzahl zeigt, die mit einem festen Wert, dargestellt durch den Programmwert 32, verglichen wird.
• Die Bitkomparatoren von Fig. 2 ermitteln den Relativwert der zwei Zahlen, die verglichen werden. Wenn der Wert der Bits 40 und 42 identisch ist, ist eine Vergleichsausgabe 32 gleich der Vergleichseingabe 30. Wenn jedoch der Wert von 40 und 42 verschieden ist, wird die Vergleichsausgabe 32 gemäß der folgenden Gestaltungsregel bestimmt: Wenn das Eingabebit 40 größer als das Eingabebit 42 ist, ist die Vergleichsausgabe 32 gleich 1. Umgekehrt ist, wenn das Eingabebit 40 kleiner als das Eingabebit 42 ist, die Vergleichsausgabe gleich 0. Die Biteingaben 40 und 42 gehen durch ein exklusives ODER Gatter hindurch. Deswegen ist, wenn das Bit 40 und das Bit 42 gleich sind, die Eingabe 36 gleich 0, und die Eingabe 38, die invertiert ist, gleich 1. Wenn jedoch der Wert des Bits 40 und des Bits 42 verschieden ist, ist die Eingabe 36 gleich 1 und die Eingabe 38 ist gleich 0. Die Wahrheitstabelle unten zeigt die Vergleichsausgabe 32 in Bezug auf die Eingaben 36 und 38. Tabelle I.
• Diese Tabelle zeigt, daß dann, wenn die beiden zu vergleichenden Bits, 40 und 42, verschieden sind, die Vergleichseingabe 34 als die Vergleichsausgabe 32 ausgegeben wird. Umgekehrt wird, wenn der Wert der Bits 40 und 42 gleich ist, die Vergleichseingabe von dem vorhergehenden Bitkomparator 30 als die Vergleichsausgabe 32 ausgegeben. Die Vergleichseingabe 30 des Anfangsbitkomparators 22 ist auf einen festen Wert festgelegt, der V oder wie in Fig. 2 gezeigt, Erde sein kann. Somit wird, wenn die Eingabebits 40 und 42 gleich sind, ein niedriger Pegel zu der Vergleichsausgabe 32 durchgegeben. Infolgedessen empfängt der Bitkomparator 24 ein niedriges Eingabesignal 30, und die Vergleichsausgabe 32 wird wieder 0 sein, wenn die Eingabebits 40 und 42 des Bitkomparators 24 den gleichen Wert haben, so daß die eingegebene Vergleichseingabe ausgegeben wird. Dieser Vorgang beginnt mit dem Komparator für das Bit niedrigster Wertigkeit (LSB) 22, und wird seriell fortgesetzt, bis der Komparator für das Bit höchster Wertigkeit (MSB) 28 seine Vergleichsoperation beendet hat. Erst wenn die Werte der Bits höchster Wertigkeit verglichen wurden, wird eine Vergleichsendausgabe 32 erzeugt. Der Bitkomparator höchster Ordnung, bei dem die Bits unterschiedlich sind, bestimmt den Zustand der Vergleichsendausgabe 32 des Bitkomparators 28.
• Fig. 2 zeigt, daß 16 Bitkomparatoren benötigt werden, um Zahlen mit 16 Bits zu vergleichen. Da der Vorgang seriell ist, kann es ziemlich zeitaufwendig sein, auf die Vergleichsendausgabe zu warten. Für einen Vergleich von 16 Bit müssen mindestens 16 Gatterverzögerungen anfallen, bevor ein Vergleichsendausgabesignal erscheint. Dies trifft auf Szenarien zu, bei denen sich im schlimmsten Fall nur die Bits niedrigster Wertigkeit unterscheiden, oder bei denen alle 16 Bits, die verglichen werden, im Wert gleich sind. Es ist wünschenswert, den seriellen Vergleichsvorgang zu beschleunigen, da viele Komparatoranwendungen einen Hochgeschwindigkeitsbetrieb erfordern.
• Fig. 3 zeigt ein schematisches Diagramm eines parallelen Wertkomparators gemäß der vorliegenden Erfindung. Bitkomparatoren haben die gleichen Eingaben und die gleiche Ausgabe wie in Fig. 2 gezeigt. Jedoch unterscheidet sich die vorliegende Erfindung dadurch, daß die Bitkomparatoren in Gruppen unterteilt sind, die unabhängig voneinander parallel arbeiten. Bezogen auf Fig. 3 sind die Bitkomparatoren in Komparatorgruppen 50, 60, 70 und 80 unterteilt. Die Eingaben und Ausgaben jedes Bitkomparators sind gleich denjenigen, die in Fig. 2 gezeigt sind. Eine Eingabe 36 wird dadurch bestimmt, daß zwei zu vergleichende Bits durch ein exklusives ODER Gatter hindurch gehen, und eine Eingabe 38 ist das Inverse der Eingabe 36. Die Eingabe 38 ist das Inverse der Eingabe 36, und könnte deshalb auch intern im Bitkomparator erzeugt werden, und braucht überhaupt keine Eingabe darstellen. Eine Eingabe 34 ist gleich dem ersten Bit der zwei Bits, die verglichen werden. Eine Vergleichsausgabe 32 hängt, wie in Fig. 2, von dem Relativwert der zwei Bits ab, die verglichen werden.
• Die oben für Fig. 2 gezeigte Wahrheitstabelle gilt auch für Fig. 3. Wenn das Eingabebit 36 logisch hoch ist, sind die beiden verglichenen Bits in Bezug zueinander verschieden, und die Eingabe 34 wird als die Vergleichsausgabe 32 ausgegeben. Wenn jedoch das Eingabebit 36 logisch niedrig ist, haben die beiden verglichenen Bits relativ zueinander den gleichen Wert, und es wird einfach eine Vergleichseingabe 30 als die Vergleichsausgabe 32 ausgegeben. Als Beispiel wird, wenn alle vier Bitkomparatoren 52, 54, 56 und 58 der Komparatorgruppe 50 Bits vergleichen, die gleich sind, die logisch niedrige Vergleichseingabe 30 des Anfangsbitkomparators 52 durch die darauffolgenden Bitkomparatoren 54, 56 und 58 hindurch gehen, bis sie eine Vergleichsausgabe 59 der Komparatorgruppe ist. Hier stellt das logisch niedrige Vergleichsausgabesignal 59 eine Eingabe zu einem Steuerelement 90 dar. Stets ist, wie bei diesem Beispiel, der Ausgabevergleichswert 59 der Komparatorgruppe 50 gleich der Ver gleichsausgabe 32 des Bitkomparators höchster Ordnung mit Bitunterschied.
• Bei einem Beispiel mit 16 Bit vergleicht die Komparatorgruppe 50 den Wert der vier Bits niedrigster Wertigkeit (LSB) der zwei Zahlen. Die Komparatorgruppen 60 und 70 vergleichen jeweils den Wert der Bits 5-8 und 9-12, während die Komparatorgruppe 50 den Wert der Bits höchster Wertigkeit (MSB), 13-16, vergleicht. Der Vergleich dieser Bits findet innerhalb der Komparatorgruppen auf serielle Weise statt, wobei die Komparatorgruppen 50, 60, 70 und 80 parallel zueinander arbeiten. Deswegen findet der Vergleich aller 16 Bits in der gleichen Zeit statt, wie sie zum Vergleich von 4 Bits in dem seriellen Wertkomparator von Fig. 2 benötigt wird. Selbstverständlich bedeutet dies eine Leistungsverbesserung für jedes System, das einen parallelen Wertkomparator verwendet. Ein Fachmann für Wertkomparatoren wird erkennen, daß das Aufteilen der Bitkomparatoren in Vierergruppen nur einer von vielen Wegen ist, die Bitkomparatoren zu gruppieren.
• Die Vergleichsausgabesignale 59, 69, 79 und 89 jeder Komparatorgruppe stellen Eingaben zu dem Steuerelement 90 dar. Nur eines dieser Vergleichsausgabesignale wird, ausgewählt von dem Steuerelement 90, durch das Steuerelement durchgegeben, um eine Vergleichsendausgabe 100 zu sein. Das Steuerelement 90 weist mehrere Übertragungsgatter 92, 94, 96 und 98 auf, die jeweils einer der Komparatorgruppen 50, 60, 70 und 80 entsprechen. Jedes Übertragungsgatter hat als Eingaben die Vergleichseingabe der entsprechenden Komparatorgruppe, und eine Logikeingabe, die durch boolesche Gleichungen bestimmt wird. Das Übertragungsgatter 92 hat die Vergleichsausgabe 59 der Komparatorgruppe 50, und eine Logikeingabe 93 als Eingaben. Die Logikeingaben 93, 95, 97 und 99 stellen sicher, daß nur die Vergleichsausgabe der Komparatorgruppe mit wertunterschiedlichen Bits der höchsten Ordnung von dem Steuerelement 90 als die Vergleichsendausgabe 100 ausgegeben wird. Wenn keines der Bits verschieden ist, wird die Vergleich sausgabe 59 der Komparatorgruppe niedrigster Ordnung 50 durch das Steuerelement 90 als die Vergleichsendausgabe 100 durchgegeben.
• Die Logikeingaben 93, 95, 97 und 99 werden durch die folgende Gleichung bestimmt: SN = XN + XN-1 + + XN-2 + XN-3, wobei XN das Ergebnis einer exklusiven ODER Operation auf die zwei zu vergleichenden Bits ist. Insbesondere sind die Logikeingaben wie folgt:
• Eingabe 99 = S&sub1;&sub6; = X&sub1;&sub6; + X&sub1;&sub5; + X&sub1;&sub4; + X&sub1;&sub3;
• Eingabe 97 = S&sub1;&sub2; * &sub1;&sub6; = (X&sub1;&sub2; + X&sub1;&sub1; + X&sub1;&sub0; + X&sub9;) * &sub1;&sub6;
• Eingabe 95 = S&sub8; * &sub1;&sub2; * &sub1;&sub6; = (X&sub8; + X&sub7; + X&sub6; + X&sub5;) * &sub1;&sub2; * &sub1;&sub6;
• Eingabe 93 = &sub8; * &sub1;&sub2; * &sub1;&sub6;
• Wenn eine der Logikeingaben 93, 95, 97 oder 99 hoch ist, wird das entsprechende Übertragungsgatter eingeschaltet, und läßt zu, daß die entsprechende Komparatorgruppenvergleichsausgabe 59, 69, 79 oder 89 durch das Übertragungsgatter hindurchgeht. Wenn jedoch die Logikeingabe niedrig ist, wird das entsprechende Übertragungsgatter ausgeschaltet, und läßt nicht zu, daß das entsprechende Vergleichsausgabesignal durch das Übertragungsgatter hindurch geht. Diese Gleichungen garantieren, daß die Vergleichsausgabe der Komparatorgruppe mit einem Bitunterschied bei der höchsten Ordnung als die Vergleichsendausgabe 100 ausgegeben wird. Beispielsweise stellen, wenn zwei Binärzahlen beim Bit 14 und auch beim Bit 2 verschiedene Werte haben, die Logikeingaben sicher, daß die Vergleichsausgabe 89 der Komparatorgruppe 80 als die Vergleichsendausgabe 100 ausgegeben wird, da das Bit 14 eine höhere Wertigkeit als das Bit 2 hat. Die Logikeingaben 93, 95, 97 und 99 werden zur gleichen Zeit bestimmt, zu der die Komparatorgruppen 50, 60, 70 und 80 Wertvergleichsoperationen durchführen. Dieser parallele Betrieb läßt zu, daß die richtige Vergleichsausgabe 59, 69, 79 oder 89 vom Steuerelement 90 ausgewählt wird, und als die Endvergleichsausgabe 100 ausgegeben wird, sofort nachdem die Komparatorgruppen die Vergleichsoperationen beendet haben. Das Steuerelement 90 führt zu keiner zusätzlichen Verzögerung bei der parallelen Wertkomparatorvergleichszeit, da das Steuerelement 90 seine Operationen beendet, bevor oder gleichzeitig dazu, daß die Gruppenvergleichsausgaben 59, 69, 79 und 89 dazu bereitstehen, durch das Steuerelement 90 durchgegeben zu werden.
• Die vorliegende Erfindung würde so, wie sie in Fig. 3 beschrieben ist, zu fünf Gatterverzögerungen führen: eine Gatterverzögerung bei jedem seriell in einer Komparatorgruppe arbeitenden Wertkomparator, wie zum Beispiel die Bitkomparatoren 52, 54, 56 und 58 in der Komparatorgruppe 50, und eine Gatterverzögerung beim Steuerelement 90. Die Erfindung benötigt keine Pufferung, da die Bitkomparatoren in Vierergruppen aufgeteilt sind. Dies ist eine deutliche Verbesserung gegenüber dem seriellen Wertkomparator, der in Fig. 2 gezeigt ist, welcher zumindest 16 Gatterverzögerungen führt, eine bei jedem Bitkomparator. Beim 16 Bit-Beispiel wird eine Pufferung benötigt, um eine Signalabschwächung zu vermeiden, die bei einem Durchlaufen von 16 seriell verbundenen Bitkomparatoren auftreten würde. Die Gatterverzögerung ist sogar noch größer, wenn bei dem seriellen Wertkomparator eine Pufferung verwendet wird. Wenn nach jedem vierten Bitkomparator ein Inverter angeordnet wäre, würde dies zu vier zusätzlichen Gatterverzögerungen führen, so daß insgesamt 20 Gatterverzögerungen auftreten würden.
• Ein alternatives Ausführungsbeispiel der Erfindung, welches ein Dreizustandsgatter anstelle eines Übertragungsgatters verwendet, ist in Fig. 4 gezeigt. Fig. 4 zeigt ein Dreizustandsgatter 110 mit drei Eingaben EINGABE, LOGIKEINGABE und . Die EINGABE ist das Vergleichsausgabesignal von der entsprechenden Komparatorgruppe, und ist analog zu den in Fig. 3 gezeigten Grup penvergleichsausgaben 59, 69, 79 und 89. Die LOGIKEINGABE ist analog zu den Logikeingaben 93, 95, 97 und 99 von Fig. 3; die LOGIKEINGABE wird durch die gleichen SN- Gleichungen bestimmt, wie oben dargestellt. Die -ist einfach das Inverse der LOGIKEINGABE. Ein AUSGABE Signal wird vom Zustand des LOGIKEINGABE Signals bestimmt. Wenn die LOGIKEINGABE logisch hoch ist, ist die logisch niedrig, und das LOGIKEINGABE Signal wird als die AUSGABE durchgegeben. Wenn die LOGIKEINGABE logisch niedrig ist, ist die logisch hoch, und das Dreizustandsgatter 110 ist folglich in einem Zustand hoher Impedanz und schließt, wobei nicht zugelassen wird, daß etwas hindurchgeht.
• Vier Dreizustandsgatter 110 würden den Platz der vier in Fig. 3 gezeigten Übertragungsgatter einnehmen, und würden innerhalb der gleichen Stufe sowohl Multiplexen als auch Puffern. Die Ausgaben dieser vier Durchgangsgatter würden zu einer einzigen Endvergleichsausgabe 100 zusammengeschlossen. In diesem Fall wäre immer noch kein Puffern bei dem in Fig. 3 gezeigten parallelen 16 Bit Wertkomparator notwendig.
• Der parallele Wertkomparator wurde in Bezug auf eine FIFO Flag Erzeugungsschaltung beschrieben. Der Wertkomparator kann auch bei einer Vielzahl weiterer Anwendungen verwendet werden, wie bei Rechenwerken (ALUs) von Computern, bei denen es notwendig ist, den Wert einer Zahl relativ zu demjenigen einer zweiten Zahl zu bestimmen.

Claims (26)

1. Wertkomparator mit:

mehreren Bitkomparatoren (52-58), die in Komparatorgruppen (50-80) unterteilt sind, die ein Gruppenausgabesignal (59, 69, 79, 89) erzeugen, wobei jeder Komparator den Wert eines ersten Bits und eines zweiten Bits vergleicht; und

einem Steuerschaltkreis (90) mit Eingängen, die mit den Ausgängen der Komparatorgruppen verbunden sind, zum Liefern einer Komparatorausgabe (100), dadurch gekennzeichnet, daß der Steuerschaltkreis Logikeingaben hat, die durch Boolesche Operationen an den von den Bitkomparatoren zu vergleichenden Bits bestimmt werden, um den Steuerschaltkreis so zu betreiben, daß eines der Gruppenausgabesignale als die Komparatorausgabe gewählt wird, wobei die Komparatorgruppen und der Steuerschaltkreis ihre jeweiligen Funktionen gleichzeitig ausführen.

2. Wertkomparator gemäß Anspruch 1, bei welchem jede Komparatorgruppe unabhängig von jeder anderen Komparatorgruppe ist.

3. Komparatorgruppe gemäß Anspruch 2, bei welcher die Komparatorgruppen mehrere Bits gleichzeitig vergleichen.

4. Wertkomparator gemäß Anspruch 1, bei welchem jeder Bitkomparator eine Vergleichsausgabe erzeugt, die dem darauffolgenden Bitkomparator eingegeben wird.

5. Wertkomparator gemäß Anspruch 4, bei welchem der Anfangsbitkomparator der Komparatorgruppe als Vergleichs eingabe ein Signal hat, das auf einen vorbestimmten Pegel eingestellt ist.

6. Wertkomparator gemäß Anspruch 4, bei welchem jeder Bitkomparator eine erste Werteingabe, eine zweite Werteingabe, und eine dritte Werteingabe hat.

7. Wertkomparator gemäß Anspruch 6, bei welchem die erste Werteingabe ein Einbitwert ist, der bestimmt wird, indem das erste Bit und das zweite Bit, die verglichen werden sollen, logisch verknüpft werden.

8. Wertkomparator gemäß Anspruch 7, bei welchem die zweite Werteingabe gleich dem Wert des ersten Bits ist, das verglichen werden soll.

9. Wertkomparator gemäß Anspruch 7, bei welchem das erste Bit und das zweite Bit, die verglichen werden sollen, jeweils ein FIFO-Lesezählstand, und ein FIFO- Schreibzählstand sind.

10. Wertkomparator gemäß Anspruch 6, bei welchem die dritte Werteingabe das Vergleichsausgabesignal ist, das von einem vorhergehenden Bitkomparator erzeugt wird.

11. Wertkomparator gemäß Anspruch 1, bei welchem das Steuerelement bestimmt, welche Komparatorgruppe die Bits höchster Ordnung enthält, die nicht übereinstimmen.

12. Komparator gemäß Anspruch 11, bei welchem das Steuerelement mehrere Gatter aufweist, die jeweils einer Komparatorgruppe entsprechen.

13. Komparator gemäß Anspruch 12, bei welchem das Steuerelement mehrere Übertragungsgatter aufweist, die jeweils einer Komparatorgruppe entsprechen.

14. Komparator gemäß Anspruch 12, bei welchem das Steuerelement mehrere Dreizustandsgatter aufweist, die jeweils einer Komparatorgruppe entsprechen.

15. Komparator gemäß Anspruch 12, bei welchem das Gatter eine erste und eine zweite Werteingabe empfängt, die bestimmt, ob das Gatter zuläßt, daß die erste Werteingabe von dem Gatter ausgegeben wird.

16. Komparator gemäß Anspruch 15, bei welchem die erste Werteingabe die Ausgabe von der entsprechenden Komparatorgruppe ist.

17. Komparator gemäß Anspruch 16, bei welchem die zweite Werteingabe davon bestimmt wird, ob die Bits, die in der momentanen Komparatorgruppe oder den Komparatorgruppen höherer Ordnung verglichen werden, übereinstimmen.

18. Komparator gemäß Anspruch 15, bei welchem das Gatter nicht zulassen kann, daß die erste Werteingabe aus dem Gatter ausgegeben wird.

19. Komparator gemäß Anspruch 15, bei welchem nur eines der mehreren Gatter zulassen kann, daß die erste Werteingabe des Gatters aus dem Gatter ausgegeben wird.

20. Komparator gemäß Anspruch 12, bei welchem es vier Komparatorgruppen gibt, die jeweils vier Bitkomparatoren aufweisen.

21. Komparator gemäß Anspruch 20, bei welchem jede der vier Komparatorgruppen einem der Gatter für eine sechszehn-Bit FIFO-Flag-Erzeugungschaltung entspricht.

22. Verfahren zum Vergleichen des Werts einer ersten Werteingabe und einer zweiten Werteingabe, mit den Schritten:

Vergleichen des Werts einer ersten Werteingabe und einer zweiten Werteingabe, indem Bitkomparatoren (52- 58) zu Komparatorgruppen (50-80) gruppiert werden, die Gruppenvergleichsausgaben (59, 69, 79, 89) erzeugen, die einer Steuerschaltung (90) zugeführt werden; und

Bereitstellen eines Vergleichsausgabe-Endsignals (100) von der Steuerschaltung, dadurch gekennzeichnet, daß an der ersten und der zweiten Werteingabe Boolesche Logikoperationen durchgeführt werden, wobei das Vergleichsausgabe-Endsignal aus einer der Gruppenvergleichsausgaben ausgewählt wird, und wobei der Vergleichsschritt und der Bereitstellschritt gleichzeitig ausgeführt werden.

23. Verfahren gemäß Anspruch 22, bei welchem die Komparatorgruppen, die parallel und unabhängig voneinander betrieben werden, Vergleichsausgaben erzeugen, die einem Steuerelement eingegeben werden.

24. Verfahren gemäß Anspruch 22, bei welchem das Steuerelement nur eine der Vergleichsausgaben auswählt, die als ein Vergleichsausgabe-Endsignal von dem Steuerelement ausgegeben werden soll.

25. Verfahren gemäß Anspruch 22, bei welchem die Komparatorgruppen und das Steuerelement unabhängig und parallel zueinander betrieben werden.

26. Verfahren gemäß Anspruch 22, bei welchem der Wertvergleich zwischen der ersten Werteingabe und der zweiten Werteingabe zum Erzeugen eines Flagsignal nutzbar ist, das für ein FIFO geeignet ist.