PatentDe  


Dokumentenidentifikation DE69425209T2 15.03.2001
EP-Veröffentlichungsnummer 0644553
Titel Verbindungsverfahren und -anordnung für inhaltsadressierbaren Speicher
Anmelder Codex Corp., Mansfield, Mass., US
Erfinder Nusinov, Eugene, Sharon, Massachusetts 02067, US;
Pasco-Anderson, James, Needham, Massachusetts, 02194, US
Vertreter Pfeifer, L., Dipl.-Phys. Dr.-Ing., Pat.-Anw., 65388 Schlangenbad
DE-Aktenzeichen 69425209
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 15.09.1994
EP-Aktenzeichen 941145468
EP-Offenlegungsdatum 22.03.1995
EP date of grant 12.07.2000
Veröffentlichungstag im Patentblatt 15.03.2001
IPC-Hauptklasse G11C 15/00
IPC-Nebenklasse G11C 15/04   

Beschreibung[de]
Hintergrund der Erfindung

Die vorliegende Erfindung bezieht sich allgemein auf Datenkompressionsschemen und insbesondere auf die Verbindung eines inhaltsadressierbaren Speichers in einem Datenkompressor.

In der Technik sind Datenkompressionsschemen zum Codieren eines Stroms digitaler Datensignale in komprimierte digitale Daten wohlbekannt. Datenkompression bezeichnet allgemein einen Vorgang der Eingabe eines Datenstroms in einem Standardformat, beispielsweise 8 Bit ASCII-Zeichen, und der Ausgabe der gleichen Informationen in einem komprimierten Format mit weniger Bits als im ursprünglichen Format.

Der Komprimierungsvorgang ist bei Datenspeicherung und Datenübertragung vorteilhaft. Wenn Daten in eine kleinere Gesamtzahl von Bits komprimiert werden, die die gleichen Informationen darstellen, wird in der Massenspeichereinrichtung weniger Platz benötigt. Gleichfalls erfolgt eine Datenübertragung schneller, wenn weniger Bits übertragen werden. Durch die Reduzierung der Gesamtzahl von Einsen und Nullen, wird die Datenbehandlung im allgemeinen effektiver. Wenn die Daten verwendet werden sollen, müssen sie für die Verwendung durch die Endeinrichtung zurück in ihr ursprüngliches Format dekomprimiert werden.

Eine übliche Kompressionstechnik ist im US-Patent 5.003.307 beschrieben. Das Kompressionssystem enthält einen Datenkompressor, einen Datendekompressor, und ein Verbindungsmedium, wie etwa eine Übertragungsverbindung oder eine Massenspeichereinrichtung. Unkomprimierte Datenworte werden vom Datenkompressor seriell verarbeitet, der eine Kompressor- Vokabulartabelle aufbaut, die ein Archiv der Eingangsdaten enthält, und der eine Folge von Codeworten über die Übertragungsverbindung zum Datendekompressor oder zur Massenspeichereinrichtung sendet. Die Codeworte werden vom Datendekompressor seriell verarbeitet, um eine entsprechende Dekompressor-Vokabulartabelle aufzubauen und unkomprimierte Datenworte an die Endeinrichtung zu liefern.

Im Datenkompressor wird jedes eingehende Datenwort mit der vorhandenen Vokabulartabelle verglichen. Wenn keine Übereinstimmung festgestellt wird, sendet der Datenkompressor das Datenwort als Teil eines Codeworts über die Übertragungsverbindung oder zur Massenspeichereinrichtung und setzt das Datenwort ferner an das Ende der Vokabulartabelle. Wenn keine Übereinstimmung festgestellt wird, erfolgt keine wirkliche Datenkompression. Die Übertragungskapazität, die benötigt wird, um ein unkomprimiertes Datenwort zu senden, kann zehn Bits betragen: acht Bits für das unkomprimierte Datenwort und zwei Bits, beispielsweise "00", um die "Länge" der übereinstimmenden Zeichenfolge des Datenworts darzustellen - in diesem Fall null.

Wenn andererseits eine oder mehrere Übereinstimmungen in der Vokabulartabelle festgestellt werden, notiert der Datenkompressor die Speicherplätze der Übereinstimmungen in der Vokabulartabelle. Anfangs werden keine Daten gesendet, aber die eingehenden Daten werden trotzdem am Ende der Vokabulartabelle angefügt. Das nächste eingehende Datenwort wird nach einer Übereinstimmung mit dem Inhalt der nächsten Speicherplätze in der Vokabulartabelle, die den ersten Übereinstimmungen folgen, überprüft, wobei in der Vokabulartabelle effektiv nach Übereinstimmungen mit der Zeichenfolgenlänge Zwei gesucht wird. Wenn das zweite eingehende Datenwort nicht mit dem Inhalt der nächsten Speicherplätze übereinstimmt, wird die Länge der längsten übereinstimmenden Zeichenfolge mit Eins bestimmt. Die erste Übereinstimmung kann als ein Codewort übermittelt werden, das das unkomprimierte Datenwort enthält, wie in dem Fall, wenn keine Übereinstimmung festgestellt wurde. Die Übertragungskapazität, die benötigt wird, um ein Codewort zu senden, das eine übereinstimmende Zeichenfolge der Länge Eins übermittelt, kann zehn Bits betragen: acht Bits für das unkomprimierte Datenwort und zwei Bits, beispielsweise "01", um die Länge der übereinstimmenden Zeichenfolge des Datenworts darzustellen - in diesem Fall Eins. Alternativ kann der "Speicherplatz" einer Übereinstimmung der Länge Eins in der Vokabulartabelle gesendet werden. Da typische Realisierungen Vokabulartabellen verwenden, die mindestens 1024 Plätze enthalten, die zur Darstellung wenigstens 10 Bits benötigen, ist es oftmals bevorzugt, ein 8 Bit Datenwort mit einer Übereinstimmung der Länge Eins als Codewort einzuschließen.

Wenn das zweite eingehende Datenwort mit dem Inhalt von zumindest einem der nächsten Speicherplätze übereinstimmt, setzt sich der Vorgang fort, bis ein nachfolgendes Datenwort mit einem der nächsten Speicherplätze in der Vokabulartabelle nicht übereinstimmt. Der Datenkompressor notiert die Anzahl derartiger Übereinstimmungen in der Vokabulartabelle. Ein Codewort wird gesendet, das den Speicherplatz der ersten Übereinstimmung und die Länge der übereinstimmenden Zeichenfolge der Datenworte identifiziert. Wenn somit aufeinanderfolgend eingehende Datenworte "A", "B", "C" zufällig mit der gleichen zuvor gespeicherten Datenzeichenfolge übereinstimmen, würde das resultierende Codewort den Anfangsspeicherplatz der Übereinstimmung von "A" und eine Länge Drei aufweisen.

Die Übertragungskapazität, die benötigt wird, um das Codewort zu senden, hängt von der Anzahl der Bits ab, die benötigt werden, um die Längen- und Speicherplatzfelder darzustellen. Wie in der Technik wohlbekannt ist, wird die Größe des Speicherplatzfelds typischerweise entweder durch die momentane Anzahl der Einträge in der Vokabulartabelle oder durch die maximale Größe der Vokabulartabelle bestimmt. Die Größe des Längenfelds ist typischerweise so gewählt, daß sie gemäß eines Präfixcodes variiert, wobei die wahrscheinlicheren Längenwerte in Bezug auf die weniger wahrscheinlichen Längenwerte unter Verwendung einer geringeren Anzahl von Bits eindeutig codiert werden. Zum Beispiel kann die Größe des Codeworts, das die Zeichenfolge "ABC" mit der Länge Drei darstellt, ebenfalls zehn Bits betragen: sieben Bits zur Übermittlung des Speicherplatzes in der Vokabulartabelle (die weniger als 128 Speicherplätze enthält) und drei Bits, die die Länge der Übereinstimmung codieren, beispielsweise "101". Der Datenkompressor gibt zur Übertragung und/oder Speicherung ein 10 Bit Codewort aus, das eine Darstellung der gesamten Zeichenfolge ist. Ein 10 Bit Codewort benötigt weniger Raum zum Speichern und weniger Zeit zum Übertragen, verglichen mit drei einzelnen unkomprimierten Datenworten (24 Bits). Somit bietet der Datenkompressor dann, wenn Zeichenfolgenübereinstimmungen der Länge größer Eins festgestellt werden, das Leistungsmerkmal der Übertragung oder Speicherung einer kleineren Gesamtzahl von Bits im Vergleich zu unkomprimierten Formaten, um die gleichen Informationen darzustellen.

Auf der Dekompressionsseite empfängt der Datendekompressor die Folge der Codeworte vom Datenkompressor über die Datenverbindung oder von der Massenspeichereinrichtung. Der Datendekompressor fängt an, seine eigene Vokabulartabelle aus den eingehenden komprimierten Daten aufzubauen. Codeworte, die mit "00" beginnen, werden so aufgefaßt, daß sie unkomprimierte Datenworte enthalten, die direkt zur Endeinrichtung geliefert und an das Ende der Vokabulartabelle des Dekompressors angefügt werden. Andere Codeworte, die Speicherplatz- und Längenfelder enthalten, werden in das Standardformat umgewandelt, indem die bezeichnete Zeichenfolge aus der Vokabulartabelle ausgelesen wird. Diese Datenworte werden dann an das Ende der Vokabulartabelle angefügt und zur Endeinrichtung gesendet.

Der zuvor beschriebene Datenkompressor kann einen inhaltsadressierbaren Speicher (CAM) enthalten, um seine Vokabulartabelle zu halten. Jede CAM-Matrix Speicherzelle ist mit Lese/Schreib-Möglichkeit einzeln adressierbar. Jedes eingehende Datenwort wird parallel mit dem vorhandenen Inhalt der CAM-Matrix verglichen und wird nachfolgend in der nächsten verfügbaren CAM-Matrix Speicherzelle abgelegt. Wenn die CAM-Matrix die Kapazität ausschöpft, schlägt die Adressierung zum Beginn der Matrix um, wobei nachfolgend der Inhalt der ältesten CAM-Matrix Speicherzelle überschrieben wird.

Wenn das physische Layout der CAM-Matrix auf dem Chip einer integrierten Schaltung (IC) betrachtet wird, ist es wichtig, die Ausbreitungsverzögerungen zwischen den Zellen zu reduzieren und die Gesamtfläche zu minimieren, die auf dem IC benötigt wird. Ein 2-dimensionales Layoutschema besteht darin, die Zellen in n Zeilen anzuordnen, die jeweils m Spalten enthalten, die in einer Folge von links nach rechts, von der niederwertigsten Adresse zur höchstwertigen Adresse, auf benachbarten Plätzen bis zum Ende des zugewiesenen Bereichs geordnet sind. Die nächste logische Zelle (niederwertigste Zelle) in der zweiten Zeile ist direkt unter der ganz linken (niederwertigsten) Zelle in der ersten Zeile plaziert. Dies vereinfacht während der Datenkompression das Codieren der Zeilen- und Spaltenadressen für das Codewort. Der Ausgang der ganz rechten (höchstwertigen) Zelle in der ersten Zeile muß jedoch über die gesamte Länge der ersten Zeile zum Eingang der ganz linken (niederwertigsten) Zelle in der zweiten Zeile zurückgeführt werden. Alle benachbarten Zeilen sind in ähnlicher Weise untereinander verbunden, indem das Ende einer Zeile über die Länge der Zeile zum Anfang der nächsten Zeile zurückgeführt wird. Die resultierenden Ausbreitungsverzögerungen begrenzen die Leistungsfähigkeit des Systems. Überdies vergrößert der Bereich der zurückführenden Leiterzüge längs jeder Zeile die Größe des IC und verkompliziert den Layoutentwurf.

Es besteht somit eine Notwendigkeit, die CAM-Matrixzellen untereinander so zu verbinden, daß die Ausbreitungsverzögerung reduziert und der Leiterzugverlauf minimiert werden.

EP-A-341 897 offenbart ein inhaltsadressierbares Speichersystem, das eine Vielzahl von Speicherzellen enthält, die in Zeilen und Spalten in einer Matrix von N Bit-Worten mal M Wort-Zellen angeordnet sind, wobei sich eine Vielzahl von Wortleitungen zur Adressierung unterschiedlicher Worte in den Speicherzellen durch die Matrix erstrecken, wobei jedes der Worte eine Vielzahl benachbarter Zellen umfaßt, die sich auf der Matrix in einer ersten Richtung erstrecken, eine Vielzahl von Übereinstimmungsleitungen sich parallel zu den Wortleitungen in der ersten Richtung durch die Matrix erstrecken, eine Vielzahl von Bitleitungen sich in einer zweiten Richtung senkrecht zur ersten Richtung durch die Matrix erstrecken, wobei jede der Bitleitungen mit den Zellen in einer der Spalten kommuniziert, die sich in der zweiten Richtung erstrecken, und ein Registerpaar zur Ausführung einer Ausblendoperation an den Bits in der Matrix mit den Bitleitungen verbunden ist.

Dieses Dokument EP-A-341 897 offenbart die Leistungsmerkmale in der Präambel der Ansprüche 1 und 9.

Zusammenfassung der Erfindung

Die vorliegende Erfindung umfaßt eine inhaltsadressierbare Speicher- (CAM) Matrix und ein Verfahren des Datenzugriffs von dieser gemäß den angefügten Ansprüchen 1 und 9.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Blockschaltbild, das einen Datenkompressor und einen Datendekompressor erläutert;

Fig. 2 ist ein Blockschaltbild, das die Übereinstimmungsprüfeinrichtung der längenvariablen Zeichenfolge von Fig. 1 erläutert;

Fig. 3 ist ein Prinzipschaltplan, der den Spaltendecodierer von Fig. 2 erläutert;

Fig. 4 ist ein Prinzipschaltplan, der den Spaltenwähler von Fig. 2 erläutert;

Fig. 5 ist ein Prinzipschaltplan und Blockschaltbild, die die CAM-Zelle von Fig. 2 erläutern;

Fig. 6 ist ein Prinzipschaltplan, der das Flipflop von Fig. 5 erläutert;

Fig. 7 ist ein Prinzipschaltplan, der die Steuerschaltung von Fig. 5 erläutert; und

Fig. 8 ist ein Prinzipschaltplan, der den Spaltenprioritätscodierer von Fig. 2 erläutert.

Detaillierte Beschreibung der bevorzugten Ausführung

In Fig. 1 liefert eine Hoststeuereinheit 10 16 Bit-Datenworte HDATA an die Hostschnittstelle 12, die den Datenfluß zwischen der Hoststeuereinheit 10 und dem Datenkompressor 14 und dem Datendekompressor 16 steuert. HADDR (Hostadresse) adressiert den Speicherplatz in der Hoststeuereinheit 10 zum Lesen und Schreiben der HDATA. Nach dem Lesen der Daten legt die Hostschnittstelle 12 die Daten im Eingangs-FIFO-Puffer 20 (First-in first-out, Puffer nach dem Siloprinzip) zusammen als 8 Bit Segment ab. Die eingehenden Daten Verschieben sich im Eingangs-FIFO-Puffer 20 zu dessen Ausgang. Die Daten vom Eingangs-FIFO-Puffer 20, d. h. IBDATA (Eingangsbusdaten) werden an den Datenkompressor 14 und an den Datendekompressor 16 zur Kompression oder Dekompression angelegt.

Der Kompressionsvorgang ist bei der Datenspeicherung und der Datenübertragung vorteilhaft, speziell in Computernetzwerksystemen. Wenn Daten in eine geringere Gesamtzahl von Bits komprimiert werden und die gleichen Informationen darstellen, wird in Massenspeichereinrichtungen weniger Platz benötigt.

Zur Datenkompression werden die unkomprimierten Datenworte sequentiell durch eine VLSM (Übereinstimmungsprüfeinrichtung einer längenvariablen Zeichenfolge) 22 verarbeitet, die eine lokale Vokabulartabelle aktualisiert, die ein Archiv aller kürzlich eingegangenen Datenworte in einer internen assoziativen CAM- (inhaltsadressierbarer Speicher) Matrix mit 1024 Zellen enthält. Die VLSM 22 sucht nach der längsten Zeichenfolge von Übereinstimmungen zwischen den eingehenden IBDATA und den Datenworten, die bereits in der vorhandenen Vokabulartabelle der CAM-Matrix gespeichert sind. Wenn keine Übereinstimmung festgestellt wird, erhält die Codierlogik 24 das unkomprimierte Datenwort von IBDATA und aktualisiert die in der CAM-Matrix befindliche Vokabulartabelle. VADDR (Vokabulartabellenadresse) von der Codierlogik 24 liefert den Aktualisierungsspeicherplatz in der CAM-Matrix. Die Codierlogik 24 sendet außerdem das unkomprimierte CHAR- (Zeichen) Signal, das direkt aus IBDATA abgeleitet ist, zur Bitpackeinrichtung 26. Ein LEN- (Länge der Übereinstimmung) Signal von Null kennzeichnet die Daten an die Bitpackeinrichtung 26 als nicht komprimiert. Die Übertragungskapazität, die benötigt wird, um ein unkomprimiertes Datenwort zu übertragen, beträgt zehn Bits: acht Bits für das unkomprimierte Datenwort und zwei Bits für den Längencode, beispielsweise "00".

Wenn eine oder mehrere Übereinstimmungen zwischen den eingehenden Daten und der Vokabulartabelle festgestellt werden, bestimmt die VLSM 22 die Speicherplätze dieser Übereinstimmungen. Zu diesem Zeitpunkt werden keine Daten gesendet, die ankommenden Daten werden jedoch weiterhin am Ende der Vokabulartabelle in der CAM-Matrix angefügt. Die VLSM 22 signalisiert der Codierlogik 24 über das Signal CAM_HIT, wenn eine Datenwortübereinstimmung festgestellt wird. Die Codierlogik 24 verfolgt die Anzahl der festgestellten aufeinanderfolgenden Übereinstimmungen (LEN) in einem 4 Bit-Längenzähler (nicht gezeigt), der durch CAM_HIT erhöht wird. Das nächste eingehende Datenwort wird nach einer Übereinstimmung mit dem Inhalt der nächsten Speicherplätze in der Vokabulartabelle, die den ersten Übereinstimmungen folgen, überprüft, indem in der Vokabulartabelle effektiv nach Übereinstimmungen von Zeichenfolgen der Länge Zwei gesucht wird. Der Vorgang setzt sich fort, bis ein nachfolgendes Datenwort mit keinem der nächsten Speicherplätze in der Vokabulartabelle übereinstimmt.

Wenn aufeinanderfolgend ankommende Datenzeichen, beispielsweise "A" und "B", zufällig mit der gleichen zuvor gespeicherten Datenzeichenfolge übereinstimmen, wird das resultierende Codewort dem entsprechenden Anfangsspeicherplatz in der CAM-Matrix und einer Länge Zwei zugewiesen. Die VLSM 22 leitet 6 Bit ROW- und 4 Bit COL-Signale, die den Speicherplatz der am kürzesten zurückliegenden Übereinstimmung in der Vokabulartabelle identifizieren, zur Codierlogik 24. Die Codierlogik 24 kombiniert die ROW- und COL-Signale in ein 10 Bit LOC-Signal, das den Anfangsspeicherplatz der längsten Zeichenfolgenübereinstimmung in der Vokabulartabelle angibt. Der Anfangsspeicherplatz wird durch Subtrahieren von LEN von der am kürzesten zurückliegenden Übereinstimmung abgeleitet. Die Codierlogik 24 kann gleichzeitig über die Vokabularspeicherschnittstelle 34 eine Kopie der Vokabulartabelle aktualisieren, die sich im Vokabular-RAM 36 befindet. Die Busse VDATA und VADDR liefern den Datenwortwert bzw. den zu aktualisierenden Speicherplatz.

Die Übertragungskapazität, die benötigt wird, um ein Codewort zu übertragen, das komprimierte Daten darstellt, variiert in Abhängigkeit von der Anzahl der Bits, die benötigt werden, um die Längen- und Speicherplatzcodes darzustellen. Die Größe des Speicherplatzcodes wird typischerweise entweder durch die momentane Anzahl der Einträge in der Vokabulartabelle oder durch die maximale Größe der Vokabulartabelle bestimmt, wie beschrieben wurde. Die Größe des Längencodes wird typischerweise so gewählt, daß sie entsprechend eines Präfixcodes variiert, in dem wahrscheinlichere Längencodes in Bezug auf weniger wahrscheinliche Längenwerte unter Verwendung einer geringeren Anzahl von Bits eindeutig codiert sind.

Die Bitpackeinrichtung 26 leitet von den Eingängen mit feststehender Länge LEN, LOC und CHAR längenvariable Codeworte ab und packt sie in eine Folge von 8 Bit-Bytes, die für den Ausgangs-FIFO-Puffer 44 geeignet sind. Das 10 Bit LOC-Signal wird in einen längenvariablen Speicherplatzcode umgewandelt, der in der Größe in Abhängigkeit von der Anzahl der in der Vokabulartabelle verwendeten Speicherplätze von fünf bis zehn Bits variiert, siehe Fig. 2 und zugehörigen nachfolgenden Text. Wenn beispielsweise die Anzahl der verwendeten Speicherplätze 31, 63, 127, 255 und 511 übersteigt, paßt sich die Größe des Speicherplatzcodes jeweils von fünf auf sechs, sieben, acht, neun bzw. zehn Bits an. Das 4 Bit LEN-Signal wird in einen längenvariablen Längencode codiert, der in der Größe von zwei bis fünf Bits variiert, siehe Fig. 2 und zugehörigen nachfolgenden Text. Auf diese Weise werden die Länge und der Speicherplatz der längsten übereinstimmenden Zeichenfolge zu einem längenvariablen Codewort kombiniert, das die Daten in komprimierter Form darstellt. Das Codewort übermittelt den Speicherplatz des Beginns der längsten Zeichenfolgeübereinstimmung in der Vokabulartabelle und die Anzahl der von diesem Startpunkt aus aufeinanderfolgenden übereinstimmenden Zeichen. Ein Steuersignal ENC von der Steuerschaltung 32 gibt den Dreistufen-Puffer 30 frei, die Ausgangsdaten als OBDATA über den Ausgangs-FIFO-Puffer 44 zur Hostschnittstelle 12 zu leiten. Die Hostschnittstelle 12 sendet die Daten zur Hoststeuereinheit 10 zur Speicherung oder bei Bedarf zur Weiterübertragung. Der Datenkompressor überträgt somit, wenn Übereinstimmungen festgestellt werden, eine geringere Gesamtzahl von Bits im Vergleich zu unkomprimierten Formaten. Die Einsparungen an Platz bei der Massenspeicherung und/oder an Zeit bei der Datenübertragung von komprimierten Daten kann beträchtlich sein.

Auf dem Datendekompressionsweg analysiert die Bit-Entpackeinrichtung 38 die eingehenden komprimierten 8 Bit Daten IBDATA in eine Folge von sich abwechselnden Längen- und Speicherplatzcodes oder Längencodes und unkomprimierten Datenworten.

Die Bit-Entpackeinrichtung 38 decodiert die längenvariablen Codes und erzeugt abwechselnd Felder mit feststehender Länge LOC und LEN oder CHAR und LEN. LEN und LOC werden in VADDR umgewandelt und mit Hilfe der Vokabularspeicherschnittstelle 34 gesendet, um die richtige Anzahl von Datenworten aus dem Vokabular-RAM 36 wiederzugewinnen. VMA ist die Vokabularspeicheradresse in den Vokabular-RAM 36, und VMD sind die Vokabularspeicherdaten, die vom Vokabular-RAM 36 gelesen und in diesen geschrieben werden. Die Daten vom Vokabular-RAM 36 kehren zur Decodierlogik 40 zurück zur Ausgabe an den Ausgangs-FIFO-Puffer 44 und zum Aktualisieren der Dekompressor-Vokabulartabelle, die im Vokabular-RAM 36 gespeichert ist. Wenn LEN gleich null ist, erhält die Decodierlogik 40 das Datenwort direkt von CHAR ohne vom Vokabular-RAM 36 zu lesen, da es sich um ein unkomprimiertes Datenwort handelt. Bei jedem Datenwort, das in den Ausgangs-FIFO-Puffer 44 geschrieben wird, aktualisiert die Decodierlogik 40 gleichzeitig die Dekompressor-Vokabulartabelle, die sich im Vokabular-RAM 36 befindet, über die Vokabularspeicherschnittstelle 34. Ein Steuersignal DEC von der Steuerschaltung 32 gibt den Dreistufen-Puffer 42 frei, das unkomprimierte Datenwort als OBDATA (Ausgangsbusdaten) über den Ausgangs- FIFO-Puffer 44 zu leiten. Die Hostschnittstelle 12 sendet OBDATA zur Hoststeuereinheit 10 zur Speicherung oder Weiterübertragung.

Jeder Eingangsstrom digitaler Datensignale, der durch ein entsprechendes Paar Kompressions- und Dekompressions- Vokabulartabellen verarbeitet wird, wird als Kanal bezeichnet. Im Fall einer Anwendung der Einzelkanal-Datenkompression liefert die CAM-Matrix die einzige Kompressor-Vokabulartabelle. Im Fall einer Anwendung Einzelkanal-Datendekompression muß der Vokabular-RAM die einzige Dekompressions-Vokabulartabelle enthalten.

Im Fall der Anwendung einer Mehrkanal-Kompression und -Dekompression ist eine andere Situation vorhanden. Im letzteren Fall können die Daten von mehreren Kanälen in Datenrahmen übertragen werden, die multiplexiert werden. Jeder Rahmen kann Informationen in Bezug auf den Kompressionsstatus und eine Beziehung zu vorhergehenden Rahmen enthalten, z. B. Kanalinformationen. Wenn eine Vokabulartabelle aufgebaut wird, die sich auf einen speziellen Rahmen bezieht, ist es erwünscht, dieses Archiv für eine spätere Anwendung an auf dem gleichen Kanal nachfolgende Rahmen zu sichern. Wenn der Datenkompressor 14 einen oder mehrere Rahmen unter Verwendung einer ersten Vokabulartabelle, die sich in der CAM-Matrix befindet, verarbeitet und anschließend einen Rahmen empfängt, der unter Verwendung der zweiten Vokabulartabelle komprimiert werden soll, kann auf diese Weise die erste Vokabulartabelle im Vokabular-RAM 36 gespeichert werden und die zweite Vokabulartabelle kann in die CAM-Matrix geladen werden. Wenn der Datenrahmen ankommt, um unter Verwendung der zweiten Vokabulartabelle komprimiert zu werden, wird die CAM-Matrix zurückgesetzt und mit der zweiten Vokabulartabelle, die im Vokabular-RAM 36 gespeichert ist, neu geladen, was es der VLSM 22 effektiv ermöglicht, die Verarbeitung dort fortzusetzen, wo der erste Kanal aufhörte. Dies spart den grundhaften Neuaufbau der Vokabulartabelle jedesmal dann, wenn ein Rahmen von einem anderen Kanal zur Kompression ankommt.

Um das Laden und Entladen zu realisieren, sind die VLSM 22 und die Codierlogik 34 über eine Vokabularspeicherschnittstelle 34 mit dem Vokabular-RAM 36 verbunden. Die VLSM 22 kann Zeichen in der lokalen CAM-Matrix speichern und die entsprechende Stelle in der im Vokabular-RAM 36 gespeicherten Vokabulartabelle vollständig von der CAM-Matrix aktualisieren, wenn ein Rahmen von einem anderen Kanal ankommt. Eine weitere Möglichkeit besteht darin, sowohl die CAM-Matrix als auch den Vokabular-RAM 36 immer dann zu aktualisieren, wenn ein Datenwort durch die VLSM 22 und die Codierlogik 24 verarbeitet wird.

Als Teil der vorliegenden Erfindung ist in Fig. 2 eine Ausführung der VLSM 22 als eine vereinfachte 2 · 2 CAM-Matrix mit den CAM-Zellen 50, 52, 54 und 56 gezeigt. In der Praxis kann die CAM-Zellen-Matrix 50-56 bei einer Gesamtzahl von 1024 Zellen aus vierundsechzig Zeilen mit sechzehn Zellen in jeder Zeile bestehen. Die Funktionsweise einer Großraum-CAM- Matrix ergibt sich direkt aus dem nachfolgenden Beispiel einer 2 · 2 CAM-Matrix.

Die VLSM 22 empfängt unkomprimierte eingehende Datenworte IBDATA und testet nach Übereinstimmungen in dem lokalen Vokabular, das in den CAM-Zellen 50-56 gespeichert ist, die ein Archiv der vorherigen Daten enthalten. Das Register 58 speichert IBDATA zur Verwendung durch die CAM-Matrix. Der Übereinstimmungsvorgang beinhaltet eine Reihe von abwechselnden Vergleichs- und Aktualisierungsphasen. Die Steuersignale INIT (siehe Fig. 5), CMP und UPD stammen aus der Zustandseinrichtung (nicht gezeigt) in der Codierlogik 24. Für eine Vergleichsphase wird das Signal CMP auf logisch eins geschaltet, und für eine Aktualisierungsphase wird das Signal UPD auf logisch eins eingeschaltet. Die Steuersignale UPD und CMP sind zueinander exklusiv. Der Vergleichs- und Aktualisierungsvorgang setzt sich fort, bis keine. Übereinstimmungen mehr festgestellt werden oder bis eine vorgegebene maximale Anzahl von Übereinstimmungen erreicht ist, d. h. die VLSM 22 hat die längste aufeinanderfolgende Zeichenfolge von Übereinstimmungen zwischen den eingehenden Datenworten und dem Inhalt der Vokabulartabelle festgestellt. INIT initialisiert am Beginn jeder Suche nach Zeichenfolgeübereinstimmungen die Signale CM0-CM3 auf null. CAM_HIT vom Zeilenpriori tätscodierer 70 signalisiert an die Codierlogik 24 immer dann, wenn eine Übereinstimmung festgestellt wird.

Es wird die Zeichenfolge "A", "B", "A", "B" und "C" betrachtet, die chronologisch an die VLSM 22 gesendet wird. Es wird angenommen, daß die CAM-Matrix auf null initialisiert worden ist. Während der ersten Vergleichsphase mit dem ersten Datenwort "A", gibt der Spaltendedodierer 60 den Spaltenwähler 62 frei, um IBDATA und deren Komplement gleichzeitig zu allen CAM-Zellen 50-56 zu leiten. Das heißt, jede Zelle in jeder Spalte ist freigegeben, das eingehende Datenwort "A" mit dem Inhalt der CAM-Matrix zu vergleichen. Das erste Zeichen "A" findet während der ersten Vergleichsphase keine Übereinstimmung in den CAM-Zellen 50-56, da die CAM-Matrix anfangs leer war. Die Steuersignale CM0, CM1, CM2 und CM3 (Zellenübereinstimmung) sind logisch null, was der nächsten CAM-Zelle keine Übereinstimmung anzeigt. Das Ausgangssignal CAM_HIT bleibt inaktiv.

Anschließend aktiviert eine logische Eins auf dem Steuersignal UPD (Aktualisieren) die Aktualisierungsphase. Das Datenwort "A" wird während der Aktualisierungsphase auf dem nächsten verfügbaren Speicherplatz, d. h. in der CAM-Zelle 50, abgelegt. Ein externer Zähler (nicht gezeigt) in der Codiererlogik 24 verfolgt den nächsten verfügbaren Speicherplatz in der CAM-Zellenmatrix und liefert seine Adresse als VADDR (Vokabularadresse). Die VLSM 22 spaltet VADDR in ROW_ADDR (Zeilenadresse) und COL_ADDR (Spaltenadresse) auf. ROW_ADDR stellt die höchstwertigen Bits und COL_ADDR stellt die niederwertigsten Bits der Adresse des nächsten verfügbaren Speicherplatzes dar. Während der Aktualisierungsphase steuern COL_ADDR und ROW_ADDR den Spaltenwähler 62, um eine bestimmte Spalte freizugeben, siehe Fig. 3 und den nachfolgenden zugehörigen Text. Das CMP-Signal ist während der Aktualisierungsphase logisch null, um den Multiplexer 63 zu steuern und um das Signal ROW_ADDR weiterzuleiten, das mit dem Steuersignal WR0 (Schreiben Zeile) eine Schreiboperation in der richtigen Zeile freigibt. Wenn es aktiviert ist, gibt das Steuersignal WR1 ein Schreiben auf den CAM-Zellen 54 und 56 frei. Die Zeilen- und Spaltenadresse gewährleistet somit die Aktualisierung des Datenworts "A" in der CAM-Zelle 50.

Da keine Übereinstimmung vorhanden war, wird das erste Datenwort "A" außerdem zur Codierlogik 24 gesendet zur Übertragung zur Hoststeuereinheit 10 in einem unkomprimierten Format. Ein Code "00" mit 2 Bit Länge wird gesendet, um "A" als unkomprimierte Daten zu kennzeichnen. Das erste "B" findet gleichfalls keine Übereinstimmung in der CAM-Matrix und wird in der CAM-Zelle 52 abgelegt. Das Datenwort "B" wird ebenfalls zur Codierlogik 24 gesendet zur Übertragung zur Hoststeuereinheit 10 in einem unkomprimierten Format. Die CAM-Matrix weist nun ein Vokabulararchiv von "A" und "B" in den CAM-Zellen 50 bzw. 52 auf.

Wenn das dritte Datenwort "A" eintrifft, gibt der Spaltendecodierer 60 wiederum den Spaltenwähler 62 frei, um IBDATA und deren Komplement gleichzeitig zu allen CAM-Zellen 50- 56 zu leiten. Die Transistoren 64 und 66 laden RMATCH0 und RMATCH1 bei jedem H-Zustand des Taktes CLOCK1 auf logisch eins vor. Die Zeilen der CAM-Zellen, die eine Übereinstimmung enthalten, werden durch eine logisch Null für RMATCH0 und/oder RMATCH1 (Zeilenübereinstimmung) angezeigt. Die CAM- Zelle 50 erkennt eine Übereinstimmung zwischen dem eingehenden Datenwort "A" und dem zuvor gespeicherten "A". Das Signal CM1 geht zu logisch eins und wird in der CAM-Zelle 52 gespeichert. Die Steuersignale CM0, CM1, CM2 und CM3 geben den Zustand einer Übereinstimmung in der vorherigen CAM-Zelle an die nächste logische CAM-Zelle weiter. Eine Übereinstimmung in der CAM-Zelle 50 aktiviert das Steuersignal CM1 zur CAM-Zelle 52, während eine Übereinstimmung in der CAM-Zelle 52 das Steuersignal CM2 zur CAM-Zelle 54 aktiviert. Eine Übereinstimmung in der CAM-Zelle 54 aktiviert das Steuersignal CM3 zur CAM-Zelle 56 und eine Übereinstimmung in der CAM-Zelle 56 aktiviert das Steuersignal CM0 zur CAM-Zelle 50. Eine alternative Ausführung der CAM-Zellen 50-56 würde an Stelle des Übereinstimmungsstatusses Datensignale weiterleiten.

RMATCH0 wird eingeschaltet, da das eingehende Datenwort "A" mit dem Inhalt der CAM-Zelle 50 in der ersten Zeile übereinstimmt. Der Zeilenprioritätcodierer 70 wählt die niederwertigste CAM-Zeile, die ein aktives Signal RMATCH anzeigt. Die CAM-Zeile 50-52 ist niederwertiger als die CAM- Zeile 54-56 definiert. Wenn RMATCH0 einer logischen Null zugewiesen ist, ist ROW logisch null. Wenn RMATCH1 einer logischen Null zugewiesen ist, und RMATCH0 ist nicht zugewiesen, ist ROW logisch eins. Wenn sowohl RMATCH0 als auch RMATCH1 zugewiesen sind, ist ROW logisch null, denn RMATCH0 ist niederwertiger. Der Zeilenprioritätscodierer 70 gibt für die Zeilenadresse nur ein Bit aus, denn die CAM- Matrix ist lediglich eine 2 · 2 Matrix. Für eine vollständige CAM-Matrix mit vierundsechzig Zeilen und einer Gesamtzahl von 1024 Zellen, ist ROW eine 6 Bit Adresse. Der Zeilenprioritätscodierer 70 schaltet außerdem das Signal CAM_HIT immer dann ein, wenn ein RMATCH-Signal eingeschaltet wird. Ein Beispiel eines Zeilenprioritätcodierers 70 ist der Prioritätscodierer von MotorolaTM Teilenummer MC14SB2B.

Das dritte Datenwort "A" wird ebenfalls in der CAM-Zelle 54 abgelegt, um die Vokabulartabelle zu aktualisieren, wie obenstehend beschrieben wurde. Die ROW-Adresse vom Zeilenprioritätcodierer 70 wird zum Zeilendecodierer 72 gesendet, um eine der 2n Freigabeleitungen gemäß der ROW-Adresse zu wählen, wobei "n" die Anzahl der Adreßbits ist. Das Signal ENC0 gibt die CAM-Zeile 50-52 frei, da sie die niederwertig ste Zeile mit einer Übereinstimmung ist. Das ENC0-Signal aktiviert außerdem die Signale CMATCH0 oder CMATCH1 (Spaltenübereinstimmung) für die CAM-Zelle, die eine cm- Übereinstimmung von der vorherigen Zelle gespeichert hat. Die Transistoren 75 und 76 laden CMATCH0 und CMATCH1 bei jedem CLOCK1-Zylus auf logisch eins vor. So lange ist die logische Eins von CM1 ist der CAM-Zelle 52 gespeichert.

Das vierte Datenwort "B" wird mit dem Inhalt der CAM-Zelle 52 verglichen, und es wird eine weitere Übereinstimmung festgestellt. Ein Signal CM2 auf logisch eins geht zur CAM- Zelle 54 über. RMATCH0 wird wieder auf logisch null geschaltet, und der Zeilenprioritätscodierer 70 gibt eine ROW-Adresse mit logisch null aus. Das vierte Datenwort "B" wird in der CAM-Zelle 56 abgelegt.

Die Signale ENC0 und ENC1 (Codieren) werden nur dann tatsächlich verwendet, wenn das nächste ankommende Datenwort keine Übereinstimmung findet, siehe die nachfolgende Erläuterung der CAM-Zelle 50 in Fig. 5. Andernfalls aktualisiert, eine nachfolgende Übereinstimmung das ROW-Signal gemäß dem Zeilenprioritätscodierer 70 und möglichen Veränderungen der aktiven Steuersignale ENC0 und ENC1. Es ist möglich, daß zwei oder mehrere Zeilen in der CAM-Matrix jeweils eine Übereinstimmung mit dem zuerst eingehenden Datenwort feststellen. Zu diesem Zeitpunkt ist unbekannt, welche Zeile die längste Zeichenfolgenübereinstimmung mit dem noch ausstehenden Datenstrom enthält.

Wenn das nächste ankommende Datenwort "C" nicht mit der nächsten CAM-Zelle 54 übereinstimmt, liefern die am kürzesten zurückliegenden Signale RMATCH und CMATCH die Zeilen- und Spalteninformationen des Speicherplatzes. In diesem Beispiel sind RMATCH0 und CMATCH1 eingeschaltet und der Zeilenprioritätscodierer 70 und der Spaltenprioritätscodierer 74 erzeugen ROW- bzw. COL-Signale, die die Adresse der CAM-Zelle 52 darstellen. Die ROW- und COL-Signale werden zur Codierlogik 24 geleitet, um LEN und LOC zu erzeugen. Die Kombination von ROW und COL zeigt tatsächlich auf den letzten Speicherplatz in der Zeichenfolgeübereinstimmung. Die Codierlogik 24 subtrahiert LEN von der ROW- und COL-Adresse, um die Anfangsadresse der Zeichenfolgeübereinstimmung zu finden.

Ein Hauptmerkmal der vorliegenden Erfindung ist das Layout der CAM-Matrix in einer integrierten Schaltung. Die erste Zeile verbundener CAM-Zellen ist so in einem IC in benachbarten Speicherplätzen angeordnet, daß die CM-Leitung von einer CAM-Zelle zur nächsten CAM-Zelle mit einem minimalen Leiterzugverlauf verbunden ist. Der logische Fluß der Zellenübereinstimmungssignale CM1 ist von links nach rechts, z. B. von der CAM-Zelle 50 über die CAM-Zellen der ersten Zeile zur CAM-Zelle 52. Eine zweite Zeile CAM-Zellen befindet sich in der IC direkt unter der ersten Zeile. Es können zusätzliche Zeilen angelegt werden, wodurch eine zweidimensionale Matrix gebildet wird. Der logische Fluß der Zellenübereinstimmungssignale CM1 setzt sich von links nach rechts fort, z. B. von der CAM-Zelle 54 über die Zellen der zweiten Zeile zur CAM-Zelle 56. Somit besitzen die CAM-Zellen 50-56 jeweils eine ansteigende Wertigkeit. Die in der ersten Zeile ganz rechts liegende CAM-Zelle, z. B. die CAM-Zelle 52, ist mit der in der zweiten Zeile ganz rechts liegenden CAM- Zelle, z. B. der CAM-Zelle 54 verbunden, wodurch der Leiterzugverlauf minimiert ist. In ähnlicher Weise ist die in der zweiten Zeile ganz links liegende CAM-Zelle mit der in der dritten Zeile ganz links liegenden CAM-Zelle verbunden. Die letzte CAM-Zelle in der letzten Zeile ist mit der in der ersten Zeile ganz links liegenden CAM-Zelle verbunden, wodurch die Schleife geschlossen ist. Das resultierende serpentinenförmige Verbindungsschema besitzt den Vorteil, daß der Leiterzugverlauf zwischen den CAM-Zellen minimiert und der Layoutentwurf vereinfacht ist.

Sowohl dem Spaltendecodierer 60 als auch dem Spaltenprioritätscodierer 70 muß jedoch besondere Beachtung gewidmet werden. Die niederwertigste CAM-Zelle in den geradzahligen Zeilen der CAM-Matrix ist die ganz linke Zelle. Die niederwertigste CAM-Zelle in den ungeradzahligen Zeilen der CAM-Matrix ist die ganz rechte Zelle. Somit besitzen die niederwertigsten CAM-Zellen in den geradzahligen Zeilen und die niederwertigsten CAM-Zellen in den ungeradzahligen Zeilen Priorität. Dennoch bestimmt das serpentinenförmige Verbindungsschema, daß die nächste logische CAM-Zelle, die der ganz rechten, höchstwertigen CAM-Zelle in einer geradzahligen Zeile folgt, die ganz rechte, niederwertigste CAM-Zelle in einer ungeradzahligen Zeile ist. Überdies ist die niederwertigste CAM-Zelle in der geradzahligen Zeile mit der gleichen CMATCH-Leitung verbunden wie die höchstwertige CAM-Zelle in der ungeradzahligen Zeile. Deswegen muß der Spaltenprioritätscodierer 74 die physische Reihenfolge seiner Eingänge in jeder zweiten Zeile umkehren, siehe nachfolgende Erläuterung bezüglich Fig. 8. Das niederwertigste Bit (bzw. die niederwertigsten Bits) von ROW aus dem Zeilenprioritätscodierer 70 steuert (bzw. steuern) den Spaltenprioritätscodierer 74.

In Fig. 3 ist eine weitere Einzelheit des Spaltendecodierers 60 gezeigt, der das NAND-Gatter 78 enthält, das CLOCK1 als eine Phase des Systemtakts empfängt. Die Signale CLOCK1 und CLOCK2 sind nicht überlappende entgegengesetzte Phasen des Systemtakts, der beispielsweise bei 20 MHz betrieben wird (siehe Fig. 5).

Das ODER-Gatter 80 empfängt UPD und RESET an seinen Eingängen, um einen zweiten Eingang zum NAND-Gatter 78 zu liefern. Wenn RESET auf logisch eins geschaltet wird, geht der Ausgang des NAND-Gatters 78 beim Hochpegelzustand von CLOCK1 auf logisch null und schaltet die Transistoren 82 und 88 ein und die Transistoren 100 und 102 aus. Der Eingang des Negators 84 und der Eingang des Negators 90 werden durch den Versorgungsleiter 86 logisch eins, der auf einem positiven Potential betrieben wird, wie etwa VDD. Das Signal COL_SEL1 am Ausgang des Negators 84 und das Signal COL_SEL0 am Ausgang des Negators 90 werden logisch null und sperren die Übertragung von IBDATA und über den Spaltenwähler 62 zu den CAM-Zellen 52 und 54 bzw. zu den CAM-Zellen 50 und 56.

Das Aktualisieren einer CAM-Zelle erfolgt während CLOCK2. CLOCK1 ist somit logisch null, um am Ausgang des NAND-Gatters 78 eine logische Eins zu erzeugen. Die Transistoren 100 und 102 sind durch eine logische Eins am Ausgang des NAND-Gatters 78 freigegeben. Das niederwertigste Bit von ROW_ADDR steuert den Multiplexer 94, um COL_ADDR oder dessen Komplement mit Hilfe des Negators 96 zu seinem Ausgang zu leiten, um während der Aktualisierungsphase eine Spalte der CAM-Matrix zu wählen. Eine logische Eins am Ausgang des Multiplexers 94 schaltet den Transistor 98 ein und zieht den Eingang des Negators 84 auf logisch null und COL_SEL1 auf logisch eins. Der Spaltenwähler 62 leitet IBDATA und zu den CAM-Zellen 52 und 54. Eine logische Null am Ausgang des Multiplexers 94 schaltet den Transistor 98 aus und schaltet wegen des Negators 108 den Transistor 106 ein. Der Eingang des Negators 90 geht nach logisch null und COL_SEL wird logisch eins, um IBDATA und zu den CAM-Zellen 50 und 56 freizugeben.

In der Vergleichsphase ist das Steuersignal CMP logisch eins und RESET ist logisch null, um am Ausgang des UND-Gatters 110 eine logische Eins zu schaffen und die Transistoren 112 und 114 einzuschalten. Die Eingänge der Negatoren 84 und 90 werden auf logisch null gezogen. Die Steuersignale COL_SEL0 und COL_SEL1 gehen nach logisch eins und geben IBDATA und frei, damit sie durch den Spaltenwähler 62 zu allen CAM-Zellen 50-56 geleitet werden.

Der Spaltenwähler 62 ist in Fig. 4 gezeigt. Eine logische Eins auf COL_SEL1 schaltet die Transistoranordnung 116 ein, um IBDATA und zu den CAM-Zellen 52 und 54 zu leiten. Eine logische Null auf COL_SEL1 schaltet die Transistoranordnung 116 aus, um IBDATA und zu sperren. Eine logische Eins auf COL_SEL0 schaltet die Transistoranordnung 118 ein, um IBDATA und zu den CAM-Zellen 50 und 56 zu leiten. Eine logische Null auf COL_SEL0 schaltet die Transistoranordnung 118 aus, um IBDATA und zu sperren.

In Fig. 5 ist stellvertretend für die weiteren CAM-Zellen die CAM-Zelle 50 gezeigt.

Kurz beschrieben führt das CAM-Byte 120 eine Vergleichsfunktion zwischen IBDATA und dem vorhandenen Inhalt des CAM-Bytes aus. Wenn IBDATA mit dem zuvor gespeicherten Inhalt übereinstimmt, wird MATCH auf logisch eins geschaltet. Das Steuersignal CM1 wird auf logisch eins geschaltet, wenn MATCH, CLOCK2 und HIT vom Master-Slave-Flipflop 122 an den Eingängen des UND-Gatters 124 auf logisch eins sind. CM1 geht zu einem Flipflop in der CAM-Zelle 52, das dem Flipflop 122 ähnlich ist. Das Steuersignal CM0 von der CAM-Zelle 56 gibt den Transistor 126 frei, um RMATCH0 auf logisch null zu schalten. Eine logische Eins des HIT-Signals vom Flipflop 122 gibt außerdem das Übertragungsgatter 128 frei, das Steuersignal ENC0 vom Zeilendecodierer 72 weiterzuleiten, um den Transistor 130 einzuschalten und CMATCH0 auf logisch null zu schalten, wenn ENC0 aktiv ist. Wenn logisch eins ist, ist das Übertragungsgatter 128 gesperrt und der Transistor 132 wird eingeschaltet, um den Transistor 130 ausgeschaltet zu lassen. Die Steuerschaltung 136 liefert RD (Lesen) und LD (Laden), um das Flipflop 122 zu takten, wie nachfolgend beschrieben wird. Es wird angemerkt, daß lediglich eine Steuerschaltung 136 verwendet wird, um die Steuersignale LD und RD zu den Flipflops wie das Flipflop 122 in allen CAM- Zellen zu senden. Das CAM-Byte 120 speichert IBDATA beim Empfang eines Steuersignals WR0. In einer alternativen Ausführung könnte das CAM-Byte 120 an Stelle eines Übereinstimmungsstatussignals Ausgangsdaten ausgeben.

Alle hier beschriebenen Übertragungsgatter können als P- Kanal- und N-Kanal Gegentakt-Transistoren (nicht gezeigt) realisiert sein, deren Drains und Sources zusammengeschaltet sind, wie wohlbekannt ist. Der negierte Eingang ist das Gate des P-Kanal Transistors und der nicht negierte Eingang ist das Gate des N-Kanal Transistors.

In Fig. 6 ist ein Flipflop 122 gezeigt, das ein Übertragungsgatter 140 enthält, das das Steuersignal CM0 von der CAM- Zelle 56 empfängt. Das Steuersignal LD und sein Komplement geben das Übertragungsgatter 140 über den Negator 142 frei. Entweder das Steuersignal CM0 oder ein Steuersignal INIT (Initialisieren) von der Zustandseinrichtung (nicht gezeigt) in der Codiererlogik 24 erzeugen eine logische Eins am Ausgang des ODER-Gatters 144. INIT wird am Beginn jeder Zeichenfolgeübereinstimmung auf logisch eins geschaltet. Das Übertragungsgatter 140 speichert die logische Eins, wenn die Steuersignale LD und den Zustand auf logisch null bzw. logisch eins wechseln. Das Steuersignal RD und sein Komplement geben das Übertragungsgatter 150 über den Negator 148 frei, um den Ausgangszustand des ODER-Gatters 144 zu den Negatoren 152 und 154 zu leiten. wird am Ausgang des Negators 152 gewonnen, während HIT am Ausgang des Negators 154 gewonnen wird. Das Signal LD lädt das Signal CM0 in den Masterabschnitt des Flipflops 122, z. B. die Schaltung 140-146. Das Signal RD leitet den gespeicherten logischen Zustand zum Ausgang des Flipflops 122. Das Signal LD wird nur während CMP und CLOCK2 auf logisch eins geschaltet. Andernfalls wird das Signal RD eingeschaltet. Somit sind RD und LD gegenseitig exklusiv und nicht überlappend. Das Flipflop 122 arbeitet, um die Übereinstimmung der benachbarten CAM-Zelle zu speichern, die während der vorherigen Vergleichsphase erzeugt wurde. Deswegen hat eine Übereinstimmung, die im CAM-Byte 120 erfaßt wurde, zur Folge, daß ein Flipflop wie das Flipflop 122 in der CAM-Zelle 52 eine logische Eins von CM1 speichert.

Fig. 7 erläutert die Steuerschaltung 136, die CMP, CLOCK1 und CLOCK2 empfängt. Es wird angemerkt, daß lediglich eine Steuerschaltung 136 verwendet wird, um die Steuersignale LD und RD zu den Flipflops, wie zum Flipflop 122, in allen CAM- Zellen zu senden. Ein D-Flipflop 156 empfängt CMP an seinen Daten- und Rücksetzeingängen und CLOCK1 an seinem Takteingang. Der Ausgang des Flipflops 156 wird an einen Eingang des UND-Gatters 158 angelegt. Der Ausgang des UND-Gatters 158 liefert das Steuersignal RD zum Flipflop 122. Die Signale CMP und CLOCK2 werden an das UND-Gatter 160 angelegt, das einen Eingang des UND-Gatters 162 und über den Negator 166 einen Eingang des UND-Gatters 166 steuert. Der Ausgang des UND- Gatters 162 wird an den zweiten Eingang des UND-Gatters 158 und außerdem, negiert durch den Negator 168, an den zweiten Eingang des UND-Gatters 164 angelegt. Der Ausgang des UND- Gatters 164 wird über die Verzögerungsschaltung 170 an einen Eingang des UND-Gatters 172 und außerdem, negiert durch den Negator 174, an den zweiten Eingang des UND-Gatters 162 angelegt. Das UND-Gatter 172 empfängt außerdem das Signal CLOCK2 und liefert das Steuersignal LD an seinem Ausgang zum Flipflop 122.

Die durch das Flipflop 122 benötigte Verzögerung kann in Abhängigkeit von dem Intervall zwischen den Vergleichsphasen, das von der Verfügbarkeit der Datenworte im Eingangs-FIFO- Puffer 20 und von der Anzahl der Taktzyklen abhängt, die benötigt werden, um während der dazwischenliegenden Aktualisierungsphasen Datenworte in den Vokabular-RAM 36 zu schreiben, variieren. Unter Anerkennung, daß in der CAM- Matrix für jede CAM-Zelle lediglich ein Flipflop 122 benötigt wird, das typischerweise die Fläche in der IC dominiert, ist es wichtig, die Anzahl der Gatter in jedem Flipflop 122 zu minimieren. Um den Zustand des Flipflops 122 während einer unbestimmten Verzögerung zu erhalten, werden die Steuersignale RD und LD in einer alternativen Weise gegenüber den Schemen des Standes der Technik mit mehreren Flipflops verwendet, die durch den Systemtakt direkt gesteuert werden. Das Flipflop 122 ist ein einzelnes Flipflop, das eine unbestimmte Verzögerung schaffen kann. Durch Auswahl der Steuersignale RD und LD derart, daß sie nicht überlappend und zueinander exklusiv sind, benötigt die Slave-Stufe des Flipflops 122 keine Auffrischlogik.

In Fig. 8 ist der Spaltenprioritätscodierer 74 für die Konfiguration der 2 · 2 CAM-Zelle gezeigt. Das Signal CMATCH0 wird an die Eingänge der Übertragungsgatter 176 und 178 angelegt. In ähnlicher Weise wird das Signal CMATCH1 an die Eingänge der Übertragungsgatter 180 und 182 angelegt. Die Ausgänge der Übertragungsgatter 176 und 180 sind zu einem ersten Eingang des UND-Gatters 184 zusammengeschaltet. Die Ausgänge der Übertragungsgatter 178 und 182 sind über einen Negator 186 zu einem zweiten Eingang des UND-Gatters 184 zusammengeschaltet. Die ROW-Adresse steuert den negierten Steuereingang des Übertragungsgatters 178 und den nicht negierten Steuereingang des Übertragungsgatters 180. Die ROW- Adresse steuert außerdem den negierten Steuereingang des Übertragungsgatters 182 und den nicht negierten Steuereingang des Übertragungsgatters 178. Die -Adresse nach dem Negator 188 steuert den negierten Steuereingang des Übertragungsgatters 180 und den nicht negierten Steuereingang des Übertragungsgatters 176. Die -Adresse steuert außerdem den negierten Steuereingang des Übertragungsgatters 178 und den nicht negierten Steuereingang des Übertragungsgatters 182.

Die Funktion des Prioritätscodierers 74 besteht darin, die Spalten in den geradzahligen Zeilen, d. h. in den CAM-Zellen 50-52, von der niederwertigsten Zelle (ganz links) zu der höchstwertigen Zelle (ganz rechts) zu priorisieren. Den niederwertigsten Zellen, z. B. der CAM-Zelle 54, wird in den ungeradzahligen Zeilen ebenfalls Priorität gegeben. In ungeradzahligen Zeilen, z. B. den CAM-Zellen 54-56, liegt jedoch die niederwertigste Zelle ganz rechts und die höchstwertige Zelle liegt ganz links. Deswegen muß die Priorisierung umgekehrt werden, um in ungeradzahligen Zeilen den niederwertigsten Zellen, z. B. der CAM-Zelle 54, Priorität zu geben. Die Notwendigkeit, die Wertigkeit von geradzahligen Zeilen zu ungeradzahligen Zeilen umzukehren, folgt aus der serpentinenartigen Konfiguration der CAM-Zellenmatrix. Der Fluß der Zellenübereinstimmungssignale CM1 wechselt von der CAM-Zelle 52 in der ersten Zeile zur CAM-Zelle 54 in der zweiten Zeile. Um die gewünschte Prioritätsumkehrung zu erzielen, kehrt der Spaltenprioritätscodierer 74 durch ein Eingangs-Multiplexierungsschema in einen Spaltenprioritätscodierer die physische Reihenfolge seiner Eingaben für ungeradzahlige Zeilen in Bezug auf geradzahlige Zeilen um.

Nun wird die in Fig. 8 unterstützte Anordnung der 2 · 2 CAM- Matrix betrachtet. Es wird angenommen, daß die Signale CMATCH0 und CMATCH1 beide auf logisch null geschaltet sind. Wenn ROW logisch null ist und logisch eins ist, d. h. die erste (geradzahlige) Zeile mit den CAM-Zellen 50-52 ist gewählt, leitet das Übertragungsgatter 176 CMATCH0 zum ersten Eingang des UND-Gatters 184 und das Übertragungsgatter 182 leitet CMATCH1 über den Negator 186 zum zweiten Eingang des UND-Gatters 184. Die COL-Adresse wird logisch null, wodurch CMATCH0 Priorität verliehen wird, da es in der ersten Zeile am niederwertigsten ist. Die Spalte mit den CAM-Zellen 50 und 56 ist gewählt. Wenn CMATCH0 logisch eins ist und CMATCH1 ist logisch null, empfängt das UND-Gatter 184 zwei logische Einsen und gibt COL mit logisch null aus, wodurch die Spalte mit den CAM-Zellen 52 und 54 gewählt ist.

Nun wird angenommen, daß ROW logisch eins ist und logisch null ist, d. h. die zweite (ungeradzahlige) Zeile mit den CAM-Zellen 54-56 ist gewählt. Wieder werden die beiden Signale CMATCH0 und CMATCH1 auf logisch null geschaltet. Das Übertragungsgatter 180 leitet CMATCH1 zum ersten Eingang des UND-Gatters 184 und das Übertragungsgatter 178 leitet CMATCH0 über den Negator 186 zum zweiten Eingang des UND-Gatters 184. Die COL-Adresse wird logisch null, wodurch CMATCH1 Priorität gegeben wird, denn es ist die niederwertigste Spalte in der zweiten (ungeradzahligen) Zeile. Die Spalte mit den CAM- Zellen 54 und 56 ist gewählt. Wenn CMATCH0 logisch null ist und CMATCH1 logisch eins ist, empfängt das UND-Gatter 184 zwei logische Einsen und gibt ein Signal COL mit logisch eins aus, wodurch die Spalte mit den CAM-Zellen 50 und 56 gewählt ist.

Bei größeren CAM-Matrizen kann die gewählte Priorität erweitert werden, damit sie so wirkt, wie obenstehend beschrieben ist. Beispielsweise können das UND-Gatter 184 und der Negator 186 durch den Spaltencodierer Motorola Teilenummer MC14532B ersetzt werden. Die Spalteneingaben können in einen Spaltenprioritätscodierer nach einem ähnlichen Eingangs-Multiplexierungsschema umgekehrt werden, wie in Fig. 8 gezeigt ist. Somit besteht ein Hauptmerkmal der vorliegenden Erfindung beim Layout der CAM-Matrix in einer integrierten Schaltung in einem serpentinenförmigen Verbindungsschema, um den Leiterzugverlauf zwischen den CAM- Zellen zu minimieren und um den Layoutentwurf zu vereinfachen. Ein Spaltenprioritätscodierer verleiht der niederwertigsten CAM-Zelle in den ungeradzahligen und geradzahligen Zeilen der CAM-Matrix Priorität, indem die physische Reihenfolge ihrer Eingaben in jeder zweiten Zeile umgekehrt wird.

Während spezielle Ausführungen der vorliegenden Erfindung gezeigt und beschrieben wurden, werden Fachmännern weitere Modifikationen und Verbesserungen einfallen.


Anspruch[de]

1. Inhaltsadressierbare Speicher- (CAM) Matrix, die eine Vielzahl von untereinander verbundenen CAM-Zellen enthält, wobei die CAM-Matrix enthält:

- eine erste Vielzahl von CAM-Zellen (50, 52), die von einer niederwertigsten Adresse zu einer höchstwertigen Adresse in einer Reihe angeordnet und seriell verbunden sind, damit sich Übereinstimmungssignale von der Zelle mit der niederwertigsten Adresse zu der Zelle mit der höchstwertigen Adresse ausbreiten, wobei diese erste Vielzahl von CAM-Zellen (50, 52) in einer ersten Zeile benachbarter Speicherplätze angeordnet ist;

- eine zweite Vielzahl von CAM-Zellen (54, 56), die von einer niederwertigsten Adresse zu einer höchstwertigen Adresse in einer Reihe angeordnet und seriell verbunden sind, damit sich Übereinstimmungssignale von der Zelle mit der niederwertigsten Adresse zu der Zelle mit der höchstwertigen Adresse ausbreiten, wobei diese zweite Vielzahl von CAM-Zellen (54, 56) in einer zweiten Zeile benachbarter Speicherplätze angeordnet ist;

und dadurch gekennzeichnet ist, daß

- diese zweite Vielzahl von CAM-Zellen (54, 56) so angeordnet ist, daß eine Zelle mit der niederwertigsten Adresse neben einer Zelle mit der höchstwertigen Adresse dieser ersten Vielzahl von CAM-Zellen (50, 52) angeordnet ist und von dieser ein Übereinstimmungssignal empfängt, und

- die CAM-Matrix ferner einen Spaltenprioritätscodierer (74) enthält, der Eingänge aufweist zum Empfangen von Spaltenübereinstimmungssignalen von diesen ersten und zweiten Vielzahlen von CAM-Zellen und der zum Umkehren der Reihenfolge seiner Eingaben von dieser zweiten Vielzahl von CAM-Zellen (54, 56) in Bezug auf diese erste Vielzahl von CAM-Zellen (50, 52) dient.

2. CAM-Matrix nach Anspruch 1, wobei der Spaltenprioritätscodierer (74) enthält:

- einen Multiplexer (176, 178, 180, 182) mit ersten und zweiten Eingängen und ersten und zweiten Ausgängen, wobei diese ersten und zweiten Eingänge zum Empfangen erster (CMATCH0) und zweiter (CMATCH1) Spaltenübereinstimmungssignale dieser Spalten dieser ersten bzw. zweiten Vielzahlen von CAM-Zellen geschaltet sind; und

- einen Spaltenprioritätswähler (184) mit ersten und zweiten Eingängen, die mit diesen ersten und zweiten Ausgängen dieses Multiplexers verbunden sind, um eine Spalte dieser ersten und zweiten Vielzahlen von CAM- Zellen zu wählen.

3. CAM-Matrix nach Anspruch 2, wobei diese erste Vielzahl von CAM-Zellen (50, 52) enthält:

- eine erste CAM-Zelle (50), die einen Dateneingang, einen Übereinstimmungseingang und einen Übereinstimmungsausgang aufweist, wobei dieser Übereinstimmungseingang geschaltet ist, um ein erstes Übertragungssignal (CM0) zu empfangen, dieser Dateneingang geschaltet ist, um ein Dateneingangssignal (IBDATA) zu empfangen, dieser Übereinstimmungsausgang geschaltet ist, um beim Erfassen einer Übereinstimmung zwischen diesem Dateneingangssignal und einem in dieser ersten CAM-Zelle gespeicherten Wert ein zweites Übereinstimmungssignal (CM1) zu liefern; und

- eine zweite CAM-Zelle (52), die einen Dateneingang, einen Übereinstimmungseingang und einen Übereinstimmungsausgang aufweist, wobei dieser Dateneingang geschaltet ist, um dieses Dateneingangssignal (IBDATA) zu empfangen, dieser Übereinstimmungseingang mit diesem Übereinstimmungsausgang dieser ersten CAM-Zelle verbunden ist, dieser Übereinstimmungsausgang geschaltet ist, um beim Erfassen einer Übereinstimmung zwischen diesem Dateneingangssignal und einem in dieser zweiten CAM- Zelle gespeicherten Wert ein drittes Übereinstimmungssignal (CM2) zu liefern; und

wobei diese zweite Vielzahl von CAM-Zellen (54, 56) umfaßt:

- eine dritte CAM-Zelle (54), die einen Dateneingang, einen Übereinstimmungseingang und einen Übereinstimmungsausgang aufweist, wobei dieser Dateneingang geschaltet ist, um dieses Dateneingangssignal (IBDATA) zu empfangen, dieser Übereinstimmungseingang mit diesem Übereinstimmungsausgang dieser zweiten CAM-Zelle verbunden ist, dieser Übereinstimmungsausgang beim Erfassen einer Übereinstimmung zwischen diesem Dateneingangssignal und einem in dieser dritten CAM-Zelle gespeicherten Wert ein viertes Übereinstimmungssignal (CM3) liefert; und

- eine vierte CAM-Zelle (56), die einen Dateneingang, einen Übereinstimmungseingang und einen Übereinstimmungsausgang aufweist, wobei dieser Dateneingang geschaltet ist, um dieses Dateneingangssignal (IBDATA) zu empfangen, dieser Übereinstimmungseingang mit diesem Übereinstimmungsausgang dieser dritten CAM-Zelle verbunden ist, dieser Übereinstimmungsausgang geschaltet ist, um beim Erfassen einer Übereinstimmung zwischen diesem Dateneingangssignal und einem in dieser vierten CAM- Zelle gespeicherten Wert ein fünftes Übereinstimmungssignal (CM0) zu liefern.

4. CAM-Matrix nach Anspruch 3, wobei

- die erste CAM-Zelle (50) ferner einen Spaltenübereinstimmungsausgang (CMATCH0) enthält, der mit einem ersten Eingang des Multiplexers (176, 178) verbunden ist;

- die zweite CAM-Zelle (52) ferner einen Spaltenübereinstimmungsausgang (CMATCH1) enthält, der mit einem zweiten Eingang des Multiplexers (180, 182) verbunden ist;

- die dritte CAM-Zelle (54) ferner einen Spaltenübereinstimmungsausgang (CMATCH1) enthält, der mit dem zweiten Eingang des Multiplexers (180, 182) verbunden ist;

- die vierte CAM-Zelle (56) ferner einen Spaltenübereinstimmungsausgang (CMATCH0) enthält, der mit dem ersten Eingang des Multiplexers (176, 178) verbunden ist.

5. CAM-Matrix nach Anspruch 3, wobei diese erste CAM-Zelle (50) enthält:

- ein CAM-Byte (120), das einen Dateneingang, einen Schreibeingang und einen Übereinstimmungsausgang enthält, wobei dieser Dateneingang geschaltet ist, um dieses Dateneingangssignal (IBDATA) zu empfangen, dieser Schreibeingang geschaltet ist, um ein Schreibfreigabesignal (WR0) zu empfangen, dieser Übereinstimmungsausgang geschaltet ist, um beim Erfassen einer Übereinstimmung zwischen dem Dateneingangssignal und einem in diesem CAM-Byte gespeicherten Wert dieses zweite Übereinstimmungssignal (MATCH) zu liefern;

- ein Flipflop (122), das einen Eingang, der geschaltet ist, um dieses erste Übereinstimmungssignal (CM0) zu empfangen, und einen Ausgang zum Liefern eines Treffersignals (HIT) aufweist; und

- ein UND-Gatter (124), das erste und zweite Eingänge und einen Ausgang aufweist, wobei dieser erste Eingang mit diesem Übereinstimmungsausgang dieses CAM-Bytes (120) verbunden ist, dieser zweite Eingang mit diesem Ausgang dieses Flipflops (122) verbunden ist und dieser Ausgang beim Empfangen eines Treffersignals dieses zweite Übereinstimmungssignal (MATCH) weiterleitet.

6. CAM-Matrix nach Anspruch 5, wobei diese erste CAM-Zelle ferner umfaßt:

- einen ersten Transistor (126), der ein Gate, einen Drain und eine Source aufweist, wobei dieses Gate geschaltet ist, um dieses erste Übereinstimmungssignal (CM0) zu empfangen, diese Source mit einem ersten Versorgungsleiter verbunden ist und dieser Drain geschaltet ist, um ein Zeilenübereinstimmungssignal (RMATCH0) zu liefern;

- ein Übertragungsgatter (128), das einen Eingang, einen Steuereingang und einen Ausgang aufweist, wobei dieser Eingang geschaltet ist, um ein Spaltencodiersignal (ENC0) zu empfangen, und dieser Steuereingang geschaltet ist, um von diesem Ausgang dieses Flipflops (122) dieses Treffersignal (HIT) zu empfangen;

- einen zweiten Transistor (130), der ein Gate, einen Drain und eine Source aufweist, wobei dieses Gate mit diesem Ausgang dieses Übertragungsgatters verbunden ist, diese Source mit diesem ersten Versorgungsleiter verbunden ist und dieser Drain geschaltet ist, um dieses Spaltenübereinstimmungssignal (CMATCH0) zu liefern; und

- einen dritten Transistor (132), der ein Gate, einen Drain und eine Source aufweist, wobei dieses Gate geschaltet ist, um ein negiertes Treffersignal (HIT) zu empfangen, diese Source mit diesem ersten Versorgungsleiter verbunden ist und dieser Drain mit diesem Gate des zweiten Transistors (130) verbunden ist.

7. CAM-Matrix nach Anspruch 1, die in einem Datenkompressionschip realisiert ist, wobei die Schaltungseinrichtung (74) einen Datenkompressor (14) umfaßt.

8. CAM-Matrix nach Anspruch 1, die in einem Datenkompressionschip realisiert ist, wobei die Schaltungseinrichtung einen Datendekompressor (16) umfaßt.

9. Verfahren zum Zugreifen auf Daten aus einer inhaltsadressierbaren Speicher- (CAM) Matrix, die eine Vielzahl von untereinander verbundenen CAM-Zellen enthält, die folgenden Schritte umfassend:

- Anordnen einer ersten Vielzahl von CAM-Zellen (50, 52) in einer Folge von einer niederwertigsten Adresse zu einer höchstwertigen Adresse in einer ersten Zeile benachbarter Speicherplätze;

- Anordnen einer zweiten Vielzahl von CAM-Zellen (54, 56) in einer Folge von einer niederwertigsten Adresse zu einer höchstwertigen Adresse in einer zweiten Zeile benachbarter Speicherplätze;

und gekennzeichnet durch

- Anordnung dieser zweiten Vielzahl von CAM-Zellen (54, 56), so daß eine Zelle, die die niederwertigste Adresse aufweist, neben einer Zelle, die die höchstwertige Adresse dieser ersten Vielzahl von CAM-Zellen (50, 52) aufweist, angeordnet ist und von dieser ein Übereinstimmungssignal empfängt; und

- Vorsehen eines Spaltenprioritätscodierers (74) zum Empfangen von Spaltenübereinstimmungssignalen von diesen ersten und zweiten Vielzahlen von CAM-Zellen und zum Umkehren der Reihenfolge seiner Eingaben von dieser zweiten Vielzahl von CAM-Zellen (54, 56) in Bezug auf diese erste Vielzahl von CAM-Zellen (50, 52).







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

  Patente PDF

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